Optimal Linear Spline Approximation of Digitized Models

In this paper we present a new technique for surface reconstruction of digitized models in three dimensions. Concerning this problem, we are given a data set in three-dimensional space, represented as a set of points without connectivity information, and the goal is to find, for a fixed number of vertices, a set of approxiamating triangles whic minimize the error measured by the displacement from the given points. Our method creates near-optimal linear spline approximations, using an iterative optimization scheme based on simulated annealing. The algorithm adapts the mesh to the data set and moves the triangles to enhance feature lines. At the end, we can use the approach to create a hierarchy of different resolutions for the model.