Edge Collapse
The reduction code uses an edge-collapse algorithm to simplify the skeletal mesh. It can help to have some understanding of what an edge collapse actually does. The images below show the the three steps in collapsing an edge. The actual reduction tool can be thought of as a loop that collapses edges in a mesh until only a desired number of triangles (or alternately vertices) remains in the mesh.
-
The edge to collapse is chosen
a. Edge to collapse
-
A replacement location is computed. (this might not lie on the edge)
a. Replacement vertex
-
The edge is collapsed, eliminating two triangles.
How is the Edge Chosen?
For the mesh, each edge has a “cost” that represents how much the mesh will change if that edge is collapsed. The simplification algorithm chooses the edge with the lowest cost (i.e. that will change the mesh the least). Now we can be a little more detailed about the simplification. If we order the edges from cheapest to most expensive: The algorithm will eat its way through this list of edges until a specified number of triangles (or specified number of vertices) is left. The idea being that the cheapest (least important edges) have been collapsed, leaving the most expensive (important) edges. There is a subtlety, when an edge collapses, that act changes nearby edges and their “cost” has to be updated as does the position of those edges in list ordered by cost.
-
The edge to collapse is chosen
a. Edge to collapse
So, Where Does the Cost Come From?
The actual cost of collapse is computed based on how much the local shape of the mesh will change (when using the best possible replacement vertex location) , along with additional penalties based on how poorly the attributes for the new vertex (for example, normals, color and others) will work. In the actual skeletal simplifier, we have the ability to make certain edges cost more. In particular we have exposed the ability to add additional penalties to edges that are associated with skeletal bones indicated by the user as important. Now, this doesn’t mean that the edge will never be collapsed - it just means the edge will be much later the stack of edges that feeds the simplifier.