Direct Segmentation of Algebraic Models for Reverse Engineering

In Reverse Engineering a physical object is digitally reconstructed from a set of boundary points. In the segmentation phase these points are grouped into subsets to facilitate consecutive steps as surface fitting. In this paper we present a segmentation method with subsequent classification of simple algebraic surfaces. Our method is direct in the sense that it operates directly on the point set in contrast to other approaches that are based on a triangulation of the data set. The segmentation process involves a fast algorithm for k-nearest neighbors search and an estimation of first and second order surface properties. The first order segmentation, that is based on normal vectors, provides an initial subdivision of the surface and detects sharp edges as well as flat or highly curved areas. One of the main features of our method is to proceed by alternating the steps of segmentation and normal vector estimation. The second order segmentation subdivides the surface according to principal curvatures and provides a sufficient foundation for the classification of simple algebraic surfaces. If the boundary of the original object contains such surfaces the segmentation is optimized based on the result of a surface fitting procedure.