Tree balancing for mesh simplification

Abstract

In this paper, a tree balancing technique is presented that reduces the number of hierarchy levels in typical paircontraction based mesh simplification methods. A well-balanced hierarchy is essential for data structures that explicitly represent vertices as the corresponding paths through the simplification hierarchy. The quality of the generated meshes is evaluated by three methods. The deviation between the simplified and the original mesh is measured by the Hausdorff distance. The shape of the individual triangles is evaluated by Guéziec’s compactness value. Finally, a plot showing the shape distribution of all triangles in the mesh is given. The experiments show that tree balancing has no significant impact on triangle quality.