Quadtrees for Embedded Surface Visualization: Constraints and Efficient Data Structures

In this paper, we study the properties of a triangulation class obtained by regular subdivision, called Embedded Regular Triangulation. In where we explored two simplification methods we pointed to the issue of constraints linked to such respresentations; in order to avoid cracks (or discontinuities) on the surface, all T-vertices have to be eliminated. The problem of T-vertices was also discussed in [7], as well as in [3,6]. When using a quadtree structure to store the triangulation, solving the constraints leads to computing the so-called restricted quadtree [6,7]. We present an efficient quadtree data structure with a particular indexing scheme allowing us to express a restricted quadtree in a closed form.