Big performance drop in addTriangle in version 2.72

[Volker]

Hi,

I recently updated my bullet integration in the Horde3D engine from 2.69 to version 2.72.
I thought, newer version would be better, but after I already deleted the source code from 2.69 I realized that the addTriangle method in btTriangleMesh in version 2.72 is much much slower than in version 2.69. I used this method to import some of the mesh data from the graphics engine to the physics world. When importing a terrain mesh with 147744 triangles it takes now about 17 seconds, while
loading was done in ~2 seconds when using version 2.69.

It is especially slow in debug version when compiling with Visual Studio 2008, while in 2005 it finishes the import nearly as fast as in release build (~17 seconds) it takes very very long in with 2008 (I have to admit, that I stopped timing after one minute). In release mode it takes about 18 seconds with VS2008.

I guess it has something to do with the findOrAddVertex method in the btTriangleMesh class but since I don't have the source code from version 2.69 anymore I couldn't figure out what has been changed.

Are there any plans to fix this performance drop in 2.73? Or what was the reason for the change?
Is there any possibility to get the source code from older versions of bullet or is there a faster way to add triangles to a triangle mesh?

[Erwin Coumans]

Are there any plans to fix this performance drop in 2.73? Or what was the reason for the change?

We added a slow method to find and avoid duplicate vertices, to optimize run-time performance and memory. But the search can be very slow, so we probably make
it optional for Bullet 2.73.

You can find old/deprecated versions of Bullet at the googlecode repository here:
http://code.google.com/p/bullet/downloa ... nloadCount

Thanks for the report,
Erwin

[Volker]

Making it optional would be great, since I know for sure that there are no duplicate vertices in my data, so the test would only cost (lot of) performance.

Thanks also for the link to the previous releases.

[Erwin Coumans]

Previous version of btTriangleMesh::addTriangle created duplicates for all shared vertices, even if there were no duplicate vertices in your data.

So we should find a better interface for btTriangleMesh to avoid inserting duplicates, or a faster way to find duplicate vertices.
Issue created here: http://code.google.com/p/bullet/issues/detail?id=122

For best performance, it is better to use btTriangleIndexVertexArray instead.
Hope this helps,
Erwin

[squisher]

I too noticed an enormous performance drop in addTriangle, specifically for the btBvhTriangleMeshShape I constructed for the static world (walls, floors, etc). I use IrrLicht for my graphics engine, and was previously using one giant IMetaTriangleSelector to collect all the triangle data and pass to a btTriangleMesh via the addTriangle method. With ~100k triangles, this took forever.

For best performance, it is better to use btTriangleIndexVertexArray instead.

I took this advice to heart, and here is what I came up with. First, you'll need to save all your meshes and nodes in a staging area

Code: Select all

    std::list<std::pair<IMesh*, ISceneNode*> > staticStaging;
    // ...
    staticStaging.push_back(std::pair<IMesh*, ISceneNode*>(mesh, node)); // do this for every static node

Then when youre done creating all your static nodes and you're ready to add them all to the btBvhTriangleMeshShape:

Code: Select all

// (note, u32 is unsigned int, u16 is unsigned short, f32 is float, and s32 is signed int)
btTriangleIndexVertexArray* staticVertexArray = new btTriangleIndexVertexArray();
for (list<pair<IMesh*, ISceneNode*> >::iterator iStaging = staticStaging.begin(); iStaging != staticStaging.end(); ++iStaging)
{
    // extract index and vertex data from the irrLicht mesh
    const u32 cnt = mesh->getMeshBufferCount();
    for (u32 i=0; i<cnt; ++i)
    {
        IMeshBuffer* buf = mesh->getMeshBuffer(i);
        s32 idxCnt = buf->getIndexCount();
        s32 vertexCnt = buf->getVertexCount();
        f32* vtx3 = new f32[vertexCnt * 3];
        
        matrix4 mat;
        mat *= node->getAbsoluteTransformation();
        
        switch (buf->getVertexType())
        {
        case video::EVT_STANDARD:
            {
                video::S3DVertex* vtx = (video::S3DVertex*)buf->getVertices();
                for (s32 j=0; j<vertexCnt; ++j)
                {
                    vector3df pos = vtx[j].Pos;
                    mat.transformVect(pos);
                    vtx3[j*3+0] = pos.X;
                    vtx3[j*3+1] = pos.Y;
                    vtx3[j*3+2] = pos.Z;
                 }
            }
            break;
        case video::EVT_2TCOORDS:
            {
                video::S3DVertex2TCoords* vtx = (video::S3DVertex2TCoords*)buf->getVertices();
                for (s32 j=0; j<vertexCnt; ++j)
                {
                    vector3df pos = vtx[j].Pos;
                    mat.transformVect(pos);
                    vtx3[j*3+0] = pos.X;
                    vtx3[j*3+1] = pos.Y;
                    vtx3[j*3+2] = pos.Z;
                }
            }
            break;
        case video::EVT_TANGENTS:
            {
                video::S3DVertexTangents* vtx = (video::S3DVertexTangents*)buf->getVertices();
                for (s32 j=0; j<vertexCnt; ++j)
                {
                    vector3df pos = vtx[j].Pos;
                    mat.transformVect(pos);
                    vtx3[j*3+0] = pos.X;
                    vtx3[j*3+1] = pos.Y;
                    vtx3[j*3+2] = pos.Z;
                }
            }
            break;
        }
        
        // convert irrLicht's 'unsigned short' array of indices to
        // an array of 'unsigned int's that bullet can use. 
        u16* bufIndices = buf->getIndices();
        u32* u32bufIndices = new u32[idxCnt];
        for (s32 i=0; i<idxCnt; ++i)
            u32bufIndices[i] = bufIndices[i];
        
        btIndexedMesh bMesh;
        bMesh.m_numTriangles = idxCnt / 3;
        bMesh.m_triangleIndexBase = (const unsigned char *) u32bufIndices;
        bMesh.m_triangleIndexStride = 3*sizeof(u32);
        bMesh.m_numVertices = vertexCnt;
        bMesh.m_vertexBase = (const unsigned char *)vtx3;
        bMesh.m_vertexStride = 3*sizeof(f32);
        
        staticVertexArray->addIndexedMesh(bMesh);
    }
}
btCollisionShape* shape = new btBvhTriangleMeshShape(staticVertexArray, false);
btRigidBody* rigidBody = new btRigidBody(0, new btDefaultMotionState(), shape, btVector3(0,0,0));
world->addRigidBody(rigidBody);

Edit: it now works like a charm! And this method is much, much faster than using AddTriangle, even before the performance drop.

[Erwin Coumans]

The btTriangleIndexVertexArray is more error-prone, so debug drawing to verify all is ok is recommended.

• There is no need to convert to 32bit indices, Bullet supports 16 bit indices, just use
  meshIndex.m_indexType = PHY_SHORT;
• meshIndex.m_triangleIndexStride is the striding between each tuplet (3) indices, so use 3*sizeof(integer), or 3*sizeof(short) instead.
• There is no need to transform the vertices into worldspace, just make sure to assign the same Irrlicht world transform to the rigid body/collision object.

So no need for duplication of vertex array or index array, you can probably directly use the Irrlicht arrays.

Hope this helps,
Erwin

[squisher]

Hi Erwin,

Thank you so much for your help. It now works great and is very fast. I've updated the code I listed above to the working version.

* meshIndex.m_triangleIndexStride is the striding between each tuplet (3) indices, so use 3*sizeof(integer), or 3*sizeof(short) instead.

Done - thanks

* There is no need to convert to 32bit indices, Bullet supports 16 bit indices, just use
meshIndex.m_indexType = PHY_SHORT;
* There is no need to transform the vertices into worldspace, just make sure to assign the same Irrlicht world transform to the rigid body/collision object. So no need for duplication of vertex array or index array, you can probably directly use the Irrlicht arrays.

I tried this as you suggested but it resulted in a seg fault. Maybe irrLicht didnt design it's mesh buffer to be shared... who knows.

[Erwin Coumans]

The default behaviour for addTriangle has been reverted, so it should be fast now.

Thanks for the feedback,
Erwin