Regular and non-regular point sets: Properties and reconstruction

In this paper, we address the problem of curve and surface reconstruction f rom sets of points. We introduce regular interpolants, which are polygonal approximations of curves and surfaces satisfying a new regularity condition . This new condition, which is an extension of the popular notion of r-samp ling to the practical case of discrete shapes, seems much more realistic th an previously proposed conditions based on properties of the underlying con tinuous shapes. Indeed, contrary to previous sampling criteria, our regular ity condition can be checked on the basis of the samples alone and can be t urned into a provably correct curve and surface reconstruction algorithm. O ur reconstruction methods can also be applied to non-regular and unorganize d point sets, revealing a larger part of the inner structure of such point sets than past approaches. Several real-size reconstruction examples valida te the new method. (C) 2001 Elsevier Science B.V All rights reserved.