Abstract
Surface reconstruction from range data acquired using a variety of sources has been a very active area of research in computational vision over the past decade. Generalized splines have emerged as the single most popular approximation tool to this end. In this paper we present a new and fast algorithm for solving the surface reconstruction problem using the membrane spline which yields a C 0 surface. Our algorithm for dense data constraints takes O(N) computational time, where N is the number of nodes in the discretization. For sparse data constraints, the algorithm requires O(log N/π 2 ) iterations with each iteration taking O(N) time. The number of iterations in this case depends on a prespecified error tolerance. We demonstrate the algorithm performance on synthesized sparse range data.