Implicit reconstruction of solids from cloud point sets
Chek T. Lim, George M. Turkiyyah, Mark A. Ganter, Duane Storti · 1995
This paper describes a new technique that combines numerical optimization methods with triangulation methods for generating mathematical representations of solids from 3D point data.The solid representation obtained takes the form of an algebraic function whose level surface closely approximates the surface described by the data, The algebraic function is obtained via Implicit Solid Modeling, a constructive scheme for approximating Boolean volume set operations on implicitly defined primitive volumes, and is comprised of a blended union of spherical primitives.The parameters of the algebraic function are the spatial locations and radii of the spheres as well as the parameters that describe the blending of these primitives, Fitting an implicit solid model to a data set is formulated as a sequence of non-linear optimization problems of an increasing number of variables.The cost function we employ in these optimizations is a weighted combination of discrepancies in location (distance from points to boundary of reconstructed object), discrepancies in surface normals, and desired curvature characteristics of the reconstructed solid.Since a set of trivariate data points without any connectivity information is ambiguous, an infinite number of solids, in principle, can be constructed to fit them.Different characteristics of the solid can be specified through the cost function to create the most desirable interpretation of the data.The starting point of the optimization-corresponding to the starting configuration of the primitives-is determined by performing a 3D Delaunay triangulation on the data set, and is based on the locations and sizes of the resulting tetrahedral.The effectiveness of the algorithm is demonstrated through the reconstruction of several sample data sets, including a molar and a femur.Tradeoffs between accuracy and compactness of the representations are also examined.