Simplification could reduce flipped triangles via collinearity check

[desaic]

I find that adding this criterion to hasTriangleFlip significantly reduces the number of flipped or self-intersecting triangles in flat or smooth regions. The idea is taken from another mesh simplification repository https://github.com/sp4cerat/Fast-Quadric-Mesh-Simplification. See src.cmd/Simplify.h function bool flipped(...).
In a triangle ABC, where C is going to be replaced by point D, this check looks for cases where AD and BD are in almost the same direction.

The following is code I added to my local clone of meshoptimizer:

// check for abcd nearly coplanar case
 // da * db too close to 1?
 Vector3 bd = {d.x - b.x, d.y - b.y, d.z - b.z};
 float normSquared = ed.x * ed.x + ed.y * ed.y + ed.z * ed.z;
 normSquared *= bd.x * bd.x + bd.y * bd.y + bd.z * bd.z;
 float daDotDb = ed.x * bd.x + ed.y * bd.y + ed.z * bd.z;
 float len = sqrtf(normSquared);
 if (len > 1e-7f) {
   daDotDb /= len;
   if (daDotDb > 0.999f) {
     return true;
   }
 }

Here is a simple comparison for a mesh output by marching cubes.

[zeux]

Thanks, this is interesting. Would you be able to attach the file above as .obj (before simplification)?

[desaic]

Sure. this zip file contains a .obj file. Thanks for the quick response!
track_pre_simp.zip

[desaic]

Well, this is more complicated than I thought. I had to add another check to skip the linearity check for bad triangles due to numerical issues. The linearity check suffers from numerical precision issue for skinny triangles such as in a finely divided cylinder mesh.
This is the code I use now, it's very messy.

// check for abcd nearly coplanar case
// da * db too close to 1?
Vector3 bd = {d.x - b.x, d.y - b.y, d.z - b.z};
float normSquared = ed.x * ed.x + ed.y * ed.y + ed.z * ed.z;
normSquared *= bd.x * bd.x + bd.y * bd.y + bd.z * bd.z;
float daDotDb = ed.x * bd.x + ed.y * bd.y + ed.z * bd.z;
float len = sqrtf(normSquared);
Vector3 cb = {c.x - b.x, c.y - b.y, c.z - b.z};
float caDotCb = ec.x * cb.x + ec.y * cb.y + ec.z * cb.z;
float oldLen =
(ec.x * ec.x + ec.y * ec.y + ec.z * ec.z) * (cb.x * cb.x + cb.y * cb.y + cb.z * cb.z);
oldLen = sqrtf(oldLen);
//don't check linearity for super skinny triangles.
if (caDotCb < 0.999f * oldLen) {
if (len > 1e-7 && daDotDb > 0.999f * len) {
return true;
}
}

[zeux]

Yeah there's a set of complications here; in addition to numerical issues, in some cases this seems to overly constrain the simplification process without improving the visual output. The check could be implemented as a separate option, but I'd need to look into various issues around precision. It's also not fully clear which edges to compare - AD vs BD or AB vs AD? And if the source triangle is already skinny it might be worth allowing collapses to extend these; so some questions to work through.

[desaic]

Thanks again for the response! I looked into a few more cases and realized that it's really about having an edge collapsing preference for near planar edges as shown in the following poor drawing. Basically we don't like the top vertex to be collapsed to the bottom. Instead we want to promote the bottom vertices to collapse into each other