The quadric error is an estimator based on a quadric representation of a local surface. It works great for removing near coplanar triangles, but it quickly comes tricky when dealing with vertex normals, which may designate an edge as hard or smooth independently from its fold angle. In case of edge collapse, the idea is to sort edges by their angle when the edge connects two faces. Angle-basedĪnother somewhat simple estimator. Yet, none of these is guaranteed to be optimal, it’s just a guessing game.

Let me show you an example: let’s say we want to collapse edge BC, what solution do you choose?Īs you can see, there are many ways to collapse an edge based on distance. The idea is to compute the maximum distance between local shapes before and after collapsing. Let me share with you the common ones: Distance-based Over the last four decades (since 3D games emerged), some people thought about it and came up with different ideas to create such an estimator. If you spend some time thinking about this, you’ll probably realize that it is complex and that a heuristical approach is inevitable: unlike b-rep / nurbs 3D models, triangles models are already a geometrical approximation of what the artist had in mind (unless we talk about cubes or tesselation by design, but for such cases decimating doesn’t really make sense). The hard part is: how do we quantify the contribution of an edge to the shape and color of an object? The general idea is to sort edges from lower to highest contribution to the general object shape and color. Let’s say we use edge collapse to remove triangles: the edge collapse method takes an edge (obviously). But now that we have a way to remove triangles, which triangles shall we remove? Also, this method goes well with a half-edge mesh data structure, which is a way of organizing meshes in memory to allow easy traversal and connectivity queries. When collapsing an edge, we actually merge two vertices into one single vertex, allowing the placement of that new vertex at a location that could compensate for the change in topology. I listed it because it could work in theory, but it would be very destructive a provide little control over polygon count since the removal of a single triangle could potentially imply many other topological changes.Ĭollapsing edges (also known as the “Edge Collapse method”) is the most used for today’s best mesh decimation algorithm. A solution would be to alter vertices adjacents to the removed vertex, but it would come at the cost of much greater complexity.Ĭollapsing entire triangles is a solution that I’ve never been implemented. It is rather easy to implement, but comes with a major downside: As a vertex is removed, we do not compensate for the change in topology. Removing vertices consists of progressively untesselating the mesh. By removing vertices (points that connect triangles together) one by one.First, we need a way to actually reduce the number of triangles. Such algorithms can be implemented in various ways.

Meshlab polygon reduction