Possible bug when creating or using mesh-based collision objects

[Rocketmagnet]

I am trying to do collision detection between objects using convex meshes as the collision bodies. These meshes come from STL files, and are all triangle based, however, I have written some code to carefully group together any coplanar triangles into polygonal faces. I have also made sure that the origin of the mesh is always inside.

The problem is that ReactPhysics3D seems to crash unpredictably in createPolyhedronMesh depending on the mesh I'm using. Sometimes the same mesh might work or not work depending on its orientation.

I am interested to know how throughly the mesh features have been tested.

[DanielChappuis]

Hello. Thanks for your feedback.

Can I ask you to post some simple code that you use to create the ConvexMeshShape and tell me where it crashes exactly ? Do you also have a mesh with this issue so that I can try on my side ?

You can also compile the ReactPhysics3D library in debug mode and post a complete stack trace when the crash occurs if possible.

[brizzly]

Hi Daniel, I have the exact same issue here. Can't understand WHY this is crashing with a simple cube created from Blender and exported to OBJ

reactphysics3d::PhysicsCommon::createPolyhedronMesh: 0x10013c960 <+0>: pushq %rbp 0x10013c961 <+1>: movq %rsp, %rbp 0x10013c964 <+4>: pushq %r15 0x10013c966 <+6>: pushq %r14 0x10013c968 <+8>: pushq %rbx 0x10013c969 <+9>: pushq %rax 0x10013c96a <+10>: movq %rsi, %r14 0x10013c96d <+13>: movq %rdi, %rbx 0x10013c970 <+16>: leaq 0x78(%rdi), %rdi 0x10013c974 <+20>: movl $0x90, %esi 0x10013c979 <+25>: callq 0x100188780 ; reactphysics3d::PoolAllocator::allocate(unsigned long) 0x10013c97e <+30>: movq %rax, %r15 0x10013c981 <+33>: leaq 0x10(%rbx), %rdx 0x10013c985 <+37>: movq %rax, %rdi 0x10013c988 <+40>: movq %r14, %rsi 0x10013c98b <+43>: callq 0x100129ba0 ; reactphysics3d::PolyhedronMesh::PolyhedronMesh(reactphysics3d::PolygonVertexArray*, reactphysics3d::MemoryAllocator&)

libc++abi.dylib: terminating with uncaught exception of type std::runtime_error: No item with given key has been found in the map

My mesh is a simple cube from Blender exported to OBJ number of faces = 12 number vertice = 36 number of indices = 36 3 vertice per face

//float vertices[]

-1.0 -1.0 -1.0 -1.0 -1.0 1.0 -1.0 1.0 1.0 -1.0 -1.0 -1.0 -1.0 1.0 1.0 -1.0 1.0 -1.0

1.0 1.0 -1.0 -1.0 -1.0 -1.0 -1.0 1.0 -1.0 1.0 1.0 -1.0 1.0 -1.0 -1.0 -1.0 -1.0 -1.0

1.0 -1.0 1.0 -1.0 -1.0 -1.0 1.0 -1.0 -1.0 1.0 -1.0 1.0 -1.0 -1.0 1.0 -1.0 -1.0 -1.0

-1.0 1.0 1.0 -1.0 -1.0 1.0 1.0 -1.0 1.0 1.0 1.0 1.0 -1.0 1.0 1.0 1.0 -1.0 1.0

1.0 1.0 1.0 1.0 -1.0 -1.0 1.0 1.0 -1.0 1.0 -1.0 -1.0 1.0 1.0 1.0 1.0 -1.0 1.0

1.0 1.0 1.0 1.0 1.0 -1.0 -1.0 1.0 -1.0 1.0 1.0 1.0 -1.0 1.0 -1.0 -1.0 1.0 1.0

// int indices[] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

My code

`
int nbVertices = (int)varray.size(); verticesss = new float[nbVertices3]; glm::vec3 avgvec = glm::vec3(0, 0, 0); for(int i=0 ; i<nbVertices ; i++) { glm::vec3 v = varray[i]; verticesss[i3 + 0] = v.x; verticesss[i3 + 1] = v.y; verticesss[i3 + 2] = v.z;

        avgvec.x += v.x;
        avgvec.y += v.y;
        avgvec.z += v.z;
    }
    avgvec.x /= nbVertices;
    avgvec.y /= nbVertices;
    avgvec.z /= nbVertices;
    for(int i=0 ; i<nbVertices ; i++)
    {
        verticesss[i*3 + 0] -= avgvec.x;
        verticesss[i*3 + 1] -= avgvec.y;
        verticesss[i*3 + 2] -= avgvec.z;

        printf("-> %f %f %f\n", verticesss[i*3 + 0], verticesss[i*3 + 1], verticesss[i*3 + 2]);
    }

    int nbindices = (int)iarray.size();
    indicesss = new int[iarray.size()];
    for(int i=0 ; i<iarray.size() ; i++)
    {
        int indice = iarray[i];
        indicesss[i] = indice;
    }

    // Description of the faces of the convex mesh
    int numFaces = (int) iarray.size()/3;
    polygonFaces = new PolygonVertexArray::PolygonFace[numFaces];
    PolygonVertexArray::PolygonFace * face = polygonFaces;
    for (int f=0; f<numFaces; f++)
    {
        face->indexBase = f * 3;    // First vertex of the face in the indices array
        face->nbVertices = 3;       // Number of vertices in the face
        face++;
    }

    polygonVertexArray = new PolygonVertexArray(
                                nbVertices, verticesss, 3*sizeof(float),
                                (const int*)indicesss, sizeof(int),
                                numFaces, polygonFaces,
                                PolygonVertexArray::VertexDataType::VERTEX_FLOAT_TYPE,
                                PolygonVertexArray::IndexDataType::INDEX_INTEGER_TYPE);

    // Create the polyhedron mesh
    polyhedronMesh = physicsCommon->createPolyhedronMesh(polygonVertexArray);`

[brizzly]

Debug version of the lib shows this error :

Assertion failed: (false), function operator[], file /Users/julien/Documents/GIT/reactphysics3d/include/reactphysics3d/containers/Map.h, line 668.

f = 0 mEdges.size() = 0 ..

This IF is never TRUE : auto itEdge = edges.find(pairV2V1); if (itEdge != edges.end()) {

[DanielChappuis]

First, thanks for reporting this.

I am investigating this issue but I think it's coming from the fact that you are describing the convex mesh with duplicated vertices (you are using 36 vertices to describe a convex shape that has 8 real vertices). The algorithm that creates the convex mesh inside the engine needs to construct an half-edge structure of the whole mesh in order to have fast collision detection. With this structure, it is easy to iterate over neighboring faces, edges or vertices but the way you describe your mesh with duplicated vertices, the algorithm cannot really create this structure because it has no way to know for a given vertex all of its neighbors. In your representation a given vertex is only part of a single (triangular) face. In order for this algorithm to work, a vertex should be part of multiple faces (it should be shared among all the faces it is part of). For instance, each vertex of a real cube is part of three faces.

This kind of representation is quite bad for collision detection because the complexity of collision detection with a convex mesh is relative to the number of faces/edges/vertices of the mesh. Therefore, using 36 vertices instead of 8, 12 faces instead of 4 and 36 edges instead of 12 is quite bad for performance.

I am currently trying to see if I can make this kind of representation (with duplicated vertices) to work or not (even if it's not optimal at all). I will keep you updated on this.

If the library cannot support this representation, the best way would be to use the Quick Hull Algorithm with the set of points of a mesh to compute a valid convex mesh. This is not implemented yet in the library but will be in the future (not defined when exactly) but another library for this could be used in the mean time if you cannot change the representation of your mesh.

I will keep you updated ....

[DanielChappuis]

I can confirm that it is currently not supported in the library to create a convex mesh shape that contains duplicated vertices.

When a ConvexMeshShape is created, each vertex needs to be part of at least three polygon faces. I will add a test when creating a ConvexMeshShape that throw an error if this condition is not valid in order to detect when a user has created a convex mesh with duplicated vertices.

I will also modified the user manual to indicate that this is not supported.

As I said previously, I will try to add the Quick Hull algorithm in the library that will allow a user to create a ConvexMeshShape with any set of points. This way, it will be possible to create a ConvexMeshShape from a mesh even if it has duplicated vertices. I don't know when exactly I will be able to add this to the library.

I hope this is not too much of a problem for you and again thanks a lot for reporting this.

[brizzly]

This is not a problem, also this will be a great addition, thank you very much for your effort and quick answer!

[DEFAULTSAAS]

I can confirm that it is currently not supported in the library to create a convex mesh shape that contains duplicated vertices.

When a ConvexMeshShape is created, each vertex needs to be part of at least three polygon faces. I will add a test when creating a ConvexMeshShape that throw an error if this condition is not valid in order to detect when a user has created a convex mesh with duplicated vertices.

I will also modified the user manual to indicate that this is not supported.

As I said previously, I will try to add the Quick Hull algorithm in the library that will allow a user to create a ConvexMeshShape with any set of points. This way, it will be possible to create a ConvexMeshShape from a mesh even if it has duplicated vertices. I don't know when exactly I will be able to add this to the library.

I hope this is not too much of a problem for you and again thanks a lot for reporting this.

Does something similar also apply to concave mesh shapes?

[DanielChappuis]

It should not be too much of a problem with ConcaveMeshShape because a triangular mesh is processed as a set of independent triangles internally.

However, note that in this case you should provide your own vertices normals when you create the TriangleVertexArray of your mesh (use the constructor that takes vertices normals) because the automatic normals computation (if you do not provide normals) will not create correct normals. Vertices normals are computed as a weighted average of the normals of all the neighboring faces. If you create a triangle mesh with duplicated vertices and you do not provide your own vertices normals, after the automatic normals computation, all the vertices normals of the three vertices will be the normal of the triangle face because each vertex is only part of a single face.

[DEFAULTSAAS]

Ah okay, that is good to know. That explains why if I don't provide my own vertex normal's, an error occurs. Providing vertex normal's is not an issue though, as they are also used for lighting. Thanks for the quick response.

[DanielChappuis]

I am closing this issue. Do not hesitate to reopen it if you have more questions.