MADEAPPS / newton-dynamics

Newton Dynamics is an integrated solution for real time simulation of physics environments.
http://www.newtondynamics.com
Other
936 stars 182 forks source link

Generating mesh collider is very slow on 4.0 #249

Closed SamCZ closed 2 years ago

SamCZ commented 3 years ago

Hi, I have created mesh collider for my voxel mesh with around 12k vertices and it takes 24ms at minumum when generating.

This is my code:

dMatrix chunkMatrix(dGetIdentityMatrix());
chunkMatrix.m_posit = dVector((float)data.ChunkPos.x * 16.0f, (float)data.ChunkPos.y * 16.0f, (float)data.ChunkPos.z * 16.0f, 0.0f);

if(auto* specialVoxelMesh = dynamic_cast<SpecialVoxelMesh*>(mesh.get()))
{
    dPolygonSoupBuilder meshBuilder;
    meshBuilder.Begin();
    dVector face[3];

    const auto& indexBuffer = specialVoxelMesh->GetIndexBuffer(0);
    VertexBuffer<SpecialVoxelMeshVertexBufferEntry>* voxelBuffer = specialVoxelMesh->GetVertexBuffer(0);

    for (int i = 0; i < indexBuffer.size() / 3; ++i)
    {
        auto i0 = indexBuffer[i * 3 + 0];
        auto i1 = indexBuffer[i * 3 + 1];
        auto i2 = indexBuffer[i * 3 + 2];

        const SpecialVoxelMeshVertexBufferEntry& v0 = voxelBuffer->Get(i0);
        const SpecialVoxelMeshVertexBufferEntry& v1 = voxelBuffer->Get(i1);
        const SpecialVoxelMeshVertexBufferEntry& v2 = voxelBuffer->Get(i2);

        face[0].m_x = v0.Position.x;
        face[0].m_y = v0.Position.y;
        face[0].m_z = v0.Position.z;

        face[1].m_x = v1.Position.x;
        face[1].m_y = v1.Position.y;
        face[1].m_z = v1.Position.z;

        face[2].m_x = v2.Position.x;
        face[2].m_y = v2.Position.y;
        face[2].m_z = v2.Position.z;

        meshBuilder.AddFace(&face[0].m_x, sizeof(dVector), 3, 0);
    }

    meshBuilder.End(false);

    ndShapeInstance staticMeshInstance(new ndShapeStatic_bvh(meshBuilder));

    subObject->PhysicsBody = new ndBodyDynamic();
    //body->SetNotifyCallback(new ndDemoEntityNotify(scene, entity));
    subObject->PhysicsBody->SetMatrix(chunkMatrix);
    subObject->PhysicsBody->SetCollisionShape(staticMeshInstance);
    AuroraEngine::Physics->AddBody(subObject->PhysicsBody);
}

The lag happens when calling meshBuilder.End(false);.

My suspicion is that I'm doing something wrong, I could not find many examples on mesh colliders, could you please help me ? Thanks.

JulioJerez commented 3 years ago

12k vertices is a very small vertex load. My guess is that there are many overlapping faces.

If I understand correctly, the vowel mesh is made of regular size cubes. When two of more cubes are adjacent this will make two or more quad to face each other.

This is very bad for the collision mesh generator, because it assume the input mesh is a clean manifold, this means each edge can only be shared by one or two faces. Whe the mesh generator detect edge with more than rwo faces, it try to separate the mesh separate set. But it does not expect to be the rule, it expect that to be the exception, like a bug in the mesh. This is because separating non manifold meshes into a set of manifold meshes is a nonpolynomial time complexity algorithm.

The are few things you could do.

1- write the algorithm in a way that those opposing face are skipped. That should not be too difficult.

2-since this is a vowel, you probably want to general the collision in real time. For special effects like destruction or that kind of thing.

The is in the engine a file for generation similar king of meshes, marching cube, that I was going to use for that, but I found that I would have to put lot of time on visualization, so in end up just doing the static height field.

This is what I can do. I can add A new demo the generate a real time mesh, that is an infinite grid.

Them there you can see what methos has to be whiten and you can use that to implement you vowel call. Basically you subclass fro the static mesh and you find those function that are call by the contact solver Does that sound reasonably.?

On Thu, Aug 12, 2021, 2:02 AM Sam @.***> wrote:

Hi, I have created mesh collider for my voxel mesh with around 12k vertices and it takes 24ms at minumum when generating.

This is my code:

dMatrix chunkMatrix(dGetIdentityMatrix()); chunkMatrix.m_posit = dVector((float)data.ChunkPos.x 16.0f, (float)data.ChunkPos.y 16.0f, (float)data.ChunkPos.z * 16.0f, 0.0f);

if(auto specialVoxelMesh = dynamic_cast<SpecialVoxelMesh>(mesh.get())) { dPolygonSoupBuilder meshBuilder; meshBuilder.Begin(); dVector face[3];

const auto& indexBuffer = specialVoxelMesh->GetIndexBuffer(0); VertexBuffer* voxelBuffer = specialVoxelMesh->GetVertexBuffer(0);

for (int i = 0; i < indexBuffer.size() / 3; ++i) { auto i0 = indexBuffer[i 3 + 0]; auto i1 = indexBuffer[i 3 + 1]; auto i2 = indexBuffer[i * 3 + 2];

  const SpecialVoxelMeshVertexBufferEntry& v0 = voxelBuffer->Get(i0);
  const SpecialVoxelMeshVertexBufferEntry& v1 = voxelBuffer->Get(i1);
  const SpecialVoxelMeshVertexBufferEntry& v2 = voxelBuffer->Get(i2);

  face[0].m_x = v0.Position.x;
  face[0].m_y = v0.Position.y;
  face[0].m_z = v0.Position.z;

  face[1].m_x = v1.Position.x;
  face[1].m_y = v1.Position.y;
  face[1].m_z = v1.Position.z;

  face[2].m_x = v2.Position.x;
  face[2].m_y = v2.Position.y;
  face[2].m_z = v2.Position.z;

  meshBuilder.AddFace(&face[0].m_x, sizeof(dVector), 3, 0);

}

meshBuilder.End(false);

ndShapeInstance staticMeshInstance(new ndShapeStatic_bvh(meshBuilder));

subObject->PhysicsBody = new ndBodyDynamic(); //body->SetNotifyCallback(new ndDemoEntityNotify(scene, entity)); subObject->PhysicsBody->SetMatrix(chunkMatrix); subObject->PhysicsBody->SetCollisionShape(staticMeshInstance); AuroraEngine::Physics->AddBody(subObject->PhysicsBody); }

The lag happens when calling meshBuilder.End(false);.

My suspicion is that I'm doing something wrong, I could not find many examples on mesh colliders, could you please help me ? Thanks.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/MADEAPPS/newton-dynamics/issues/249, or unsubscribe https://github.com/notifications/unsubscribe-auth/AB6EPJBGIAYVLWSATR2XV4TT4OEZBANCNFSM5CAUOP4A . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&utm_campaign=notification-email .

JulioJerez commented 3 years ago

ok If you sync, yo uwill find a new demo called ndStaticProceduralMeshCollision.cpp this is going to create a procedural mesh liek you are tryin to do.

right now does it simple make a full polygonal bvh mesh, which is similar to what you are doing, but later today I will make the base class so that the application fill the overlapping faces at run time.

this is in the engine already if you look at class class ndShapeHeightfield: public ndShapeStaticMesh but need to be formalize with the proper class, an dthe functions that need to be populated by the application

please tell me if this is what you need of I am getting it all wrong.

JulioJerez commented 3 years ago

ok if you now sync you will see how the procedural collsion will work. in file ....\newton-4.00\applications\ndSandbox\toolbox\ndMakeProceduralStaticMap.cpp

there is this class.

class ndRegularProceduralGrid : public ndShapeStaticProceduralMesh
{
    public:
    ndRegularProceduralGrid(dFloat32 sizex, dFloat32 sizey, dFloat32 sizez, const dVector& planeEquation)
        :ndShapeStaticProceduralMesh(sizex, sizey, sizez)
        ,m_planeEquation(planeEquation)
    {
    }

    virtual dFloat32 RayCast(ndRayCastNotify&, const dVector& localP0, const dVector& localP1, dFloat32 maxT, const ndBody* const, ndContactPoint& contactOut) const
    {
        dVector segment(dVector::m_triplexMask & (localP1 - localP0));
        dFloat32 den = m_planeEquation.DotProduct(segment).GetScalar();
        dFloat32 num = m_planeEquation.DotProduct(localP0).GetScalar() + m_planeEquation.m_w;
        dFloat32 t = -num / den;
        contactOut.m_point = localP0 + segment.Scale(t);
        contactOut.m_normal = m_planeEquation;
        return dClamp (t, dFloat32 (0.0f), dFloat32 (1.2f));
    }

    virtual void GetCollidingFaces(const dVector& minBox, const dVector& maxBox, dArray<dVector>& vertex, dArray<dInt32>& faceList, dArray<dInt32>& faceMaterial, dArray<dInt32>& indexListList) const
    {
        //dAssert(0);
    }

    dVector m_planeEquation;
};

it has those two virtual functions that teh application implements.
the Ray cast is very simple, since the demo use a regular grid. for the second GetCollidingFaces, the application will make a small vertex list to index list mesh on these vectors.

and the engine will take from there. right know is not populating it, but IU will do it later.
It is not much different than the heightfield,

teh trick is that the collsion is relatively small, so the buidl of teh mesh at run time soudl no be hard, play teh app can implement all can of caching .

I hope this is what you were asking for.

JulioJerez commented 3 years ago

ok now ther is a procedural collsion mesh demo. it implements a regular grid. and the class look liek this

class ndRegularProceduralGrid : public ndShapeStaticProceduralMesh
{
    public:
    ndRegularProceduralGrid(dFloat32 gridSize, dFloat32 sizex, dFloat32 sizey, dFloat32 sizez, const dVector& planeEquation)
        :ndShapeStaticProceduralMesh(sizex, sizey, sizez)
        ,m_planeEquation(planeEquation)
        ,m_gridSize(gridSize)
        ,m_invGridSize(dFloat32 (1.0f)/ m_gridSize)
    {
    }

    virtual dFloat32 RayCast(ndRayCastNotify&, const dVector& localP0, const dVector& localP1, dFloat32, const ndBody* const, ndContactPoint& contactOut) const
    {
        dVector segment(dVector::m_triplexMask & (localP1 - localP0));
        dFloat32 den = m_planeEquation.DotProduct(segment).GetScalar();
        dFloat32 num = m_planeEquation.DotProduct(localP0).GetScalar() + m_planeEquation.m_w;
        dFloat32 t = -num / den;
        contactOut.m_point = localP0 + segment.Scale(t);
        contactOut.m_normal = m_planeEquation;
        return dClamp (t, dFloat32 (0.0f), dFloat32 (1.2f));
    }

    virtual void GetCollidingFaces(const dVector& minBox, const dVector& maxBox, dArray<dVector>& vertex, dArray<dInt32>& faceList, dArray<dInt32>& faceMaterial, dArray<dInt32>& indexListList) const
    {
        // generate the point cloud
        dVector p0(minBox.Scale(m_invGridSize).Floor());
        dVector p1(maxBox.Scale(m_invGridSize).Floor() + dVector::m_one);
        dVector origin(p0.Scale(m_gridSize) & dVector::m_triplexMask);
        dInt32 count_x = dInt32(p1.m_x - p0.m_x);
        dInt32 count_z = dInt32(p1.m_z - p0.m_z);

        origin.m_y = 0.0f;
        for (dInt32 iz = 0; iz <= count_z; iz++)
        {
            dVector point(origin);
            for (dInt32 ix = 0; ix <= count_x; ix++)
            {
                vertex.PushBack(point);
                point.m_x += m_gridSize;
            }
            origin.m_z += m_gridSize;
        }

        // generate the face array
        const dInt32 stride = count_x + 1;
        for (dInt32 iz = 0; iz < count_z; iz++)
        {
            for (dInt32 ix = 0; ix < count_x; ix++)
            {
                faceList.PushBack(4);
                indexListList.PushBack((iz + 0) * stride + ix + 0);
                indexListList.PushBack((iz + 1) * stride + ix + 0);
                indexListList.PushBack((iz + 1) * stride + ix + 1);
                indexListList.PushBack((iz + 0) * stride + ix + 1);

                faceMaterial.PushBack(0);
            }
        }
    }

    dVector m_planeEquation;
    dFloat32 m_gridSize;
    dFloat32 m_invGridSize;
};

all you need to do is to make the vertex list index list mesh of the part of you procedural mesh (the voxel map) that intersect the the aabb passed to function GetCollidingFaces I hope that fixe your problem.

finally one thing to remember, try to eliminate the interion faces. these are the faces that are shared by two adjacent boxes. I am sure teh graphics algorithm remove these for visualization, so it should not be hard make do that. thsi make the collsion mesh a much higher quality since is can generate edge share info.

later some day, I will probably make a demo using the marching cube to show a 3d version.

SamCZ commented 3 years ago

Hi, sorry for no response, I've not been here for few days, thank you for your update, I will try it and let you know.

SamCZ commented 2 years ago

Hello, just a quck info that it looks like it works now (I cound not find the code you mentioned, so I used just the old I have). https://cdn.discordapp.com/attachments/703626036503511081/905213562736234506/2021-11-02_22-53-23.mp4 (I just set wrongly same gravity value to all component of the vector :D)

EDIT: I will post timings when I fix compiling tracy...

SamCZ commented 2 years ago

And the problem was not in the voxel mesh having faces on same position, but the trees I generated (there was like 10 polygons on same location per every block)

JulioJerez commented 2 years ago

ja ja that video loos very cool. is that rolling tree a compound mesh?

SamCZ commented 2 years ago

righ now I just used ndShapeBox(0.25f, 0.25f, 0.25f) for the tree. Later I will create compounds from loaded fbx informations

JulioJerez commented 2 years ago

For a tires like those try using convex hulls, it will behave much nicer and will be equally fast.

On Tue, Nov 2, 2021, 11:37 PM Sam @.***> wrote:

righ now I just used ndShapeBox(0.25f, 0.25f, 0.25f) for the tree. Later I will create compounds from loaded fbx informations

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/MADEAPPS/newton-dynamics/issues/249#issuecomment-958686601, or unsubscribe https://github.com/notifications/unsubscribe-auth/AB6EPJC67MZGGE64GGX33Z3UKDKELANCNFSM5CAUOP4A . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

SamCZ commented 2 years ago

Hi what would you recommend as collider for these type of trees ? image Compaund of AABB's ? I want players to stand on the branches.

JulioJerez commented 2 years ago

I world use a compound collision with each major branch, a convex hull. should do it.

On Sun, Nov 21, 2021 at 9:34 AM Sam @.***> wrote:

Hi what would you recommend as collider for these type of trees ? [image: image] https://user-images.githubusercontent.com/5303066/142772784-c283b4fc-6664-4f56-a46e-d3501e290a98.png Compaund of AABB's ? I want players to stand on the branches.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/MADEAPPS/newton-dynamics/issues/249#issuecomment-974861103, or unsubscribe https://github.com/notifications/unsubscribe-auth/AB6EPJCBVPMIJUFH4U43CKDUNEUTRANCNFSM5CAUOP4A . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.