Structured graph representation of a hierarchical triangulation


The problem of representing a 212-dimensional surface at variable degrees of accuracy is considered. A hierarchical model, called a hierarchical triangulation, is described which approximates a surface by a network of triangular, planar facets whose projections in the plane are nested. In the paper, a dual representation of such a triangulation in the form of a structured graph is defined and the fundamental properties of this representation are discussed. An algorithm for converting a hierarchical triangulation into its dual form is given. As an example of application, an algorithm is described for the conversion of the dual graph into the standard triangle-oriented structure used for encoding triangulated irregular networks.

Computer vision, graphics, and image processing