Triangle-based surface models


The problem of reconstructing a digital model of a surface from a finite set of sampled points is fundamental in many different application domains, including computer graphics, geographic data processing, computer vision and computer aided design. A triangulated surface model is often used, because of the possibility of including surface features, and of the simplicity of the topological structure. The definition of a triangle-based surface model relies on the concept of triangulation. In this paper, we discuss the basic properties of triangulations, Delaunay triangulations, constrained and conforming triangulations. We present a survey of algorithms for building these kinds of triangulations, which represent the first step in the construction of a surface model. A special attention is given to the surface reconstruction problem in 2 12 dimensions, which is connected to digital terrain modeling in geographic information systems. The more general problem of reconstructing the bounding surface of a solid object from three dimensional scattered data is also considered, and a brief survey of the main approaches proposed in the literature is presented.

Intelligent Systems and Robotics