Particle swarm optimization for non-uniform rational B-spline surface reconstruction from clouds of 3D data points

This work investigates the use of particle swarm optimization (PSO) to recover the shape of a surface from clouds of (either organized or scattered) noisy 3D data points, a challenging problem that appears recurrently in a wide range of applications such as CAD design, data visualization, virtual reality, medical imaging and movie industries. In this paper, we apply a PSO approach in order to reconstruct a non-uniform rational B-spline (NURBS) surface of a certain order from a given set of 3D data points. In this case, surface reconstruction consists of two main tasks: (1) surface parameterization and (2) surface fitting. Both tasks are critical but also troublesome, leading to a high-dimensional non-linear optimization problem. Our method allows us to obtain all relevant surface data (i.e., parametric values of data points, knot vectors, control points and their weights) in a shot and no pre-/post-processing is required. Furthermore, it yields very good results even in presence of problematic features, such as multi-branches, high-genus or self-intersections. Seven examples including open, semiclosed, closed, zero-genus, high-genus surfaces and real-world scanned objects, described in free-form, parametric and implicit forms illustrate the good performance of our approach and its superiority over previous approaches in terms of accuracy and generality. (C) 2010 Elsevier Inc. All rights reserved.