Hierarchyless Simplification, Stripification and Compression of Triangulated Two‐Manifolds

In this paper we explore the algorithmic space in which stripification, simplification and geometric compression of\udtriangulated 2-manifolds overlap. Edge-collapse/uncollapse based geometric simplification algorithms develop a\udhierarchy of collapses such that during uncollapse the reverse order has to be maintained. We show that restricting\udthe simplification and refinement operations only to, what we call, the collapsible edges creates hierarchyless\udsimplification in which the operations on one edge can be performed independent of those on another. Although\udonly a restricted set of edges is used for simplification operations, we prove topological results to show that, with\udminor retriangulation, any triangulated 2-manifold can be reduced to either a single vertex or a single edge using\udthe hierarchyless simplification, resulting in extreme simplification.\udThe set of collapsible edges helps us analyze and relate the similarities between simplification, stripification and\udgeometric compression algorithms. We show that the maximal set of collapsible edges implicitly describes a triangle\udstrip representation of the original model. Further, these strips can be effortlessly maintained on multiresolution\udmodels obtained through any sequence of hierarchyless simplifications on these collapsible edges. Due\udto natural relationship between stripification and geometric compression, these multi-resolution models can also be efficiently compressed using traditional compression algorithms.\udWe present algorithms to find the maximal set of collapsible edges and to reorganize these edges to get the minimum number of connected components of these edges. An order-independent simplification and refinement of these\udedges is achieved by our novel data structure and we show the results of our implementation of view-dependent,\uddynamic, hierarchyless simplification. We maintain a single triangle strip across all multi-resolution models created\udby the view-dependent simplification process. We present a new algorithm to compress the models using the\udtriangle strips implicitly defined by the collapsible edges