A simple algorithm for homeomorphic surface reconstruction
Nina Amenta, Sunghee Choi, Tamal K. Dey, Naveen Leekha · 2000
The problem of computing a piecewise linear approximation to a surface from a set of sample points is important in solid modeling, computer graphics and computer vision. A recent algorithm [1] using the Voronoi diagram of the sample points gave a guarantee on the distance of the output surface from the original sampled surface assuming the sample was `suciently dense'. We give a similar algorithm, simplifying the computation and the proof of the geometric guarantee. In addition, we guarantee that our output surface is homeomorphic to the original surface; to our knowledge this is the rst such topological guarantee for this problem. 1 Introduction A number of applications in CAD, computer graphics, computer vision and mathematical modeling involve the computation of a piecewise lin- Dept. of Computer Science, U. of Texas, Austin TX 78712. e-mail: [email protected], supported by NSF grant CCR-9731977 y Dept. of Computer Science, U. of Texas, Austin, TX 78712. e-mail: sunghe...