I have worked on implementing Taubin et al. paper Geometric Compression through Topological Surgery.
The goal of the paper is to create a compression scheme to efficiently store and transfer complex 3D meshes.
The basic approach is to take an arbitrary manifold mesh and partition it into triangle strips. Triangle strips are an efficient way to represent connectivity information between triangle faces in a mesh. Standard triangulated meshes contain redundancy in that each face references three vertices
and thus their common edges reference the same vertex multiple times.
Triangle strips operate by defining a base triangle then building off of that triangle by only keeping track of a bit to indicate which of two possible edges to build off of and the index of the next vertex to add. Each triangle strip has a small amount of overhead so the goal of any partitioning scheme is to create long triangle strips.
Their approach to partitioning a mesh into triangle strips is to create a vertex spanning tree and a triangle spanning tree for the mesh. The vertex spanning defines the borders of the triangle strips and the triangle tree defines the strips themselves and the connections between the strips. The ends of triangles trips are known as leaf nodes and the triangles that connect triangle strips are known as branching nodes.
They presented two primary ways to construct the two spanning trees:
- 1. Pick a root vertex. Sort the edges of the mesh according to the distance from their midpoints to the root vertex. Pick the edge with the minimum distance and put that in the vertex spanning tree if it does not create a cycle in the tree. Repeat this until every vertex in the mesh is connected via this tree.
- 2. Pick a root vertex and make it the first boundary. Find all of the faces incident on that vertex and make that the first layer. Find all of the edges in the first layer that are not incident on the first boundary and make them the second boundary. Find all of the triangles incident on the second boundary and not in the first layer, this becomes the second layer. Continue this process until the entire mesh has been covered. Merge the layers by adding edges connecting the boundaries and removing any cycles from the boundaries.
The first method produces reasonable results but the second method is much better.
The paper outlines many more objetives to compress a triangulated mesh such as vertex position prediction, entropy encoding position corrections, and compact representations of the vertex spanning tree, triangle spanning tree, and boundary formed by cutting the mesh along the vertex tree. My primary focus was on generating the triangle strips.
