Building and traversing a surface at variable resolution

The authors consider the multi-triangulation, a general model for representing surfaces at variable resolution based on triangle meshes. They analyse characteristics of the model that make it effective for supporting basic operations such as extraction of a surface approximation, and point location. An interruptible algorithm for extracting a representation at a resolution variable over the surface is presented. Different heuristics for building the model are considered and compared. Results on both the construction and the extraction algorithm are presented.