I always used to laugh inside my head when people around me would talk about edge and corner cases on a daily basis. Usually they’re referring to a solution to a problem that works for the majority of inputs except for rare cases. Now that I’ve spent the last few days trying to implement a triangle-reduction/mesh-simplification algorithm, I can talk about real edge and corner cases without it being a metaphor.
Why do I want to do this? Originally, I wanted to implement a software-based, visual, occlusion culling system. I built a cheap software rasterizer in a day but throwing complex geometry at it ran incredibly slow. I did some optimizations and removed some sanity checks to improve performance but it obviously wasn’t good enough for runtime. Then again, I was testing it with the highest level of detail models. I knew that wasn’t going to work but it was a good test.
All of the articles and papers that I have read on the subject use voxel-based data or a low LOD for occluders, and bounding boxes for occludable models. So I started writing this thinking it wouldn’t be an excessively long task for my needs.
The basic algorithm requires building a graph of connectivity data for every edge on every triangle in s mesh. For every triangle, there are three vertices, and an edge from one vertex to the next. That’s three edges. However, for this algorithm, which employs the edge-collapse technique, six edges must be stored to account for each direction. The edge collapse technique moves one vertex on an edge to another, in either direction, potentially removing one edge, one vertex, and two triangles.
Before a collapse can occur, we must pick which edge to collapse. This is done by scoring every possible move based on the impact it will have to the overall shape or deformation of the geometry. There are several approaches to do this depending on your metric, whether you are concerned with the final number of triangles in the geometry or maintaining the overall structure. In my case, I wanted to preserve the exact outline of the original geometry that for certain edges to be immovable.
Rather than using heuristics, I used hard rules and thresholds, disallowing any movement if a moving vertex was connected to a face whose normal was parallel or within some threshold of the direction of movement. This prevented any vertex connected to a corner from being displaced but didn’t prevent corners with complicated, concave vertex patterns from being dragged out or inverted.
The final solution was to manually compare the normals of all connected faces before and after the move. If any of those normals exceeded some threshold the move was rejected. It was more expensive but work perfectly. Only the neighboring faces and edges needed this course to be re-computed.