merging algorithm for coplanar faces is wrong

[fastflo]

consider a convex hull with these faces/vertices:

coplanar_merging.png

btPolyhedralConvexShape::initializePolyhedralFeatures() computes a convex hull and tries later to find coplanar faces and wants to merge them.

i have a test-case attached where the alg in bullet-2.79 does the following steps on that mesh:

- it decides that f0, f1 and f2 are coplanar and tries to merge them. it doesn't like f3 in that group because in reality f0,f1,f2 and f3 are NOT coplanar -- they are nearly coplanar.

Code: Select all

faceNormalA.dot(faceNormalB)>faceWeldThreshold

- it collects all vertices from these faces: v0, v1, v2, v4, v6 and computes a convex hull with GrahamScanConvexHull2D() -- the result of this computation is the hull consisting of these vertices: v0, v1, v2, v4 WITHOUT v6!
- this new merged face of v0, v1, v2, v4 replaces the existing faces f0, f1, f2

now we have a degenerated mesh.

later in m_polyhedron->initialize() it collects all edges and has an assertion checking that one edge has at most 2 faces using it:

Code: Select all

			if (edptr)
			{
				btAssert(edptr->m_face0>=0);
				btAssert(edptr->m_face1<0);
				edptr->m_face1 = i;
			} else
			{
				btInternalEdge ed;
				ed.m_face0 = i;
				edges.insert(vp,ed);
			}
		}

in this case this assertion is failing! -- and i think it is right to check that and to abort here!

the edge (v0, v4) is used by 3 faces: f3, f4 and the merged face (f0, f1,f2)

i think the right behaviour would have been not to merge f0, f1 and f2 at all.

[fastflo]

a simple fix to avoid the degeneration of the mesh is to check wether the GrahamScanConvexHull2D() rejected/did not use some of the vertices.

if so, check whether there is any other face (merged or not merged or not yet merged) that uses this vertex and don't do the merging if there is another face using it.

this is not optimal because you might reject a merge because of a face that later on might also be merged and then might not need this vertex... (i guess this is a very rare case...)

but this change should not harm the integrety of the mesh.

tested in bullet-2.79 -- my test-case program from above makes no problems with that modification.
svn diff attached and for easy reading i also added the complete changed file

coplanar_merging_fix.patch.cpp

[Erwin Coumans]

Some better check is required indeed.

Code: Select all

a simple fix to avoid the degeneration of the mesh is to check wether the GrahamScanConvexHull2D() rejected/did not use some of the vertices.

In that case, some cases would be rejected (the cap of a cylinder with a point in the middle is safe to merge).

We could strengten the condition so that it accepts the result of the 2D convex hull if

1) for any rejected vertex, there are no other faces that use this vertex

Thanks,
Erwin

[fastflo]

1) for any rejected vertex, there are no other faces that use this vertex

that is exactly what i've implemented in that patch. sorry if i was unclear about that.
the cap of a cylinder will be merged with my patch. (because no other faces outside the current coplanar-group uses the vertex in the middle) -- surely there is still the precondition that all the normals of all cap-faces need to be equal-enough.

added issue http://code.google.com/p/bullet/issues/detail?id=557

[Dirk Gregorius]

If you merge faces f1, f2 and f3 the resulting polygon is not convex anymore and the polygonal faces of a convex polyhedron must be convex as well. So another condition might be to walk the outline/horizon of the coplanar faces and only merge if the resulting polygon is convex as well. This would work for this example and the cylinder.

Another idea instead of comparing the face normals would be to use fat planes. You could e.g. check if the centroid of a neighboring face is inside of the fat region. Then for the merged faces you compute the Newell plane of the vertices of the new face. The Newell plane is basically a best fit plane through all vertices. You could use some relative thickness tolerance based on th AABB of the vertices.