Thien Hoang and Dmitry Anisimov
INRIA Sophia Antipolis
Geometry processing pipelines often require detecting various shapes among user-defined items. The simplest examples are detecting planar shapes in an unstructured point cloud or on the surface of a polygon mesh. More specific use cases may show up in practice, too. For example, detecting lines in a 2D point cloud or detecting spheres in a 3D point cloud. CGAL already offers a shape detection algorithm based on the *Efficient RANSAC (RANdom SAmple Consensus)* method and a simple version of the *Region Growing (RG)* method for detecting planes in a 3D point cloud.
For the next CGAL release (5.0), we have completely reworked the RG-based shape detection algorithm such that it is now able to handle any user-defined items given the connectivity among them and a user-specified region type. In addition to the generic version of the algorithm, we have also added three particular instances: detecting lines in a 2D point cloud, detecting planes in a 3D point cloud, and detecting planes on a polygon mesh.
Detecting Lines in a 2D Point Cloud
Given a set of 2D points with the corresponding normals, the algorithm groups these points with respect to the quality of the local least squares 2D line fit. The connectivity among points is provided via a K-d tree.
A 2D point set depicted with one color per detected line.
Detecting Planes in a 3D Point Cloud
Given a set of 3D points with the corresponding normals, the algorithm groups these points with respect to the quality of the local least squares 3D plane fit. The connectivity among points is provided via a K-d tree.
A 3D point set depicted with one color per detected plane.
This type of detection can be used in conjunction with a new package added in the next version of CGAL, Polygonal Surface Reconstruction to reconstruct piecewise planar surfaces from point clouds. An example of both features working together is available here.
Detecting Planes on a Polygon Mesh
Given a triangle surface mesh, the algorithm groups its faces with respect to the quality of the local least squares plane fit. The connectivity and normals are obtained directly from the mesh.
A triangle surface mesh depicted with one color per detected plane.
This package is already available in CGAL's master branch on the CGAL GitHub repository, and will be officially released in the upcoming version of CGAL, 5.0, scheduled for Autumn 2019.
