Fitting scattered data points with ball B-Spline curves using particle swarm optimization

• Published in: Computers & graphics 2018-05, Vol.72, p.1-11
• Main Authors: Wu, Zhongke, Wang, Xingce, Fu, Yan, Shen, Junchen, Jiang, Qianqian, Zhu, Yuanshuai, Zhou, Mingquan
• Format: Article
• Language: English
• Subjects: Algorithms; Animation; Ball B-spline curves (BBSCs); CAD; Computer aided design; Computer animation; Data points; Model accuracy; Optimization; Parameter estimation; Particle swarm optimization; Particle swarm optimization (PSO); Scattered data fitting; Scattered data points; Skeleton; Three dimensional models
• ISSN: 0097-8493; 1873-7684
• DOI: 10.1016/j.cag.2018.01.006

•An efficient and robust scattered data points fitting algorithm of BBSCs based on particle swarm optimization.•We use the BBSCs to represent the 3D tubular shape by one parametric equation, i.e. B-spline form.•We use PSO algorithm three times to finish the surface reconstruction. [Display omitted] Scattered data fitting has always been a challenging problem in the fields of geometric modeling and computer-aided design. As the skeleton-based three-dimensional solid model representation, the ball B-Spline curve is suitable to fit scattered data points on the surface of a tubular shape. We study the problem of fitting scattered data points with ball B-spline curves (BBSCs) and propose a corresponding fitting algorithm based on the particle swarm optimization (PSO) algorithm. In this process, we encounter three critical and difficult sub-problems: (1) parameterizing data points, (2) determining the knot vector, and (3) calculating the control radii. All of these problems are multidimensional and nonlinear. The parallelism of the PSO algorithm provides high optimization, which is suitable for solving nonlinear, non-differentiable, and multi-modal optimization problems. Therefore, we use it to solve the scattered data fitting problem. The PSO is applied in three steps to solve this problem. First, we determine the parametric values of the data points using PSO. Then, we compute the knot vector based on the parametric values of the data points. Finally, we obtain the radius function. The experiments on the shell surface, crescent surface, and real vessel models verify the accuracy and flexibility of the method. The research can be widely used in computer-aided design, animation, and model analysis.