Progressive forest split compression

In this paper we introduce the Progressive Forest Split (PFS) repre- sentation, a new adaptive refinement scheme for storing and trans- mitting manifold triangular meshes in progressive and highly com- pressed form. As in the Progressive Mesh (PM) method of Hoppe, a triangular mesh is represented as a low resolution polygonal model followed by a sequence of refinement operations, each one spec- ifying how to add triangles and vertices to the previous level of detail to obtain a new level. The PFS format shares with PM and other refinement schemes the ability to smoothly interpolate between consecutive levels of detail. However, it achieves much higher compression ratios than PM by using a more complex refine- ment operation which can, at the expense of reduced granularity, be encoded more efficiently. Aforest split operation doubling the number of triangles of a mesh requires a maximum of approxi- mately bits to represent the connectivity changes, as opposed to approximately bits in PM. We describe algorithms to efficiently encode and decode the PFS format. We also show how any surface simplification algo- rithm based on edge collapses can be modified to convert single resolution triangular meshes to the PFS format. The modifications are simple and only require two additional topological tests on each candidate edge collapse. We show results obtained by applying these modifications to the Variable Tolerance method of Gueziec.