A new segmentation method for point cloud data

In the process of generating a surface model from point cloud data, a segmentation that extracts the edges and partitions the three-dimensional (3D) point data is necessary and plays an important role in fitting surface patches and applying the scan data to the manufacturing process. Many researchers have tried to develop segmentation methods by fitting curves or surfaces in order to extract geometric information, such as edges and smooth regions, from the scan data. However, the surface- or curve-fitting tasks take a long time and it is also difficult to extract the exact edge points because the scan data consist of discrete points and the edge points are not always included in these data. In this research, a new method for segmenting the point cloud data is proposed. The proposed algorithm uses the octree-based 3D-grid method to handle a large amount of unordered sets of point data, The final 3D-grids are constructed through a refinement process and iterative subdivisioning of cells using the normal values of points. This 3D-grid method enables us to extract edge-neighborhood points while considering the geometric shape of a part. The proposed method is applied to two quadric models and the results are discussed. (C) 2001 Elsevier Science Ltd. All rights reserved.