article

Iteration and optimization scheme for the reconstruction of 3D surfaces based on non-uniform rational B-splines

Authors:

Jian-Dong Yang,

Jie-Bin YangAuthors Info & Claims

Computer-Aided Design, Volume 44, Issue 11

Pages 1127 - 1140

https://doi.org/10.1016/j.cad.2012.05.004

Published: 01 November 2012 Publication History

Abstract

Curve or surface reconstruction is a challenging problem in the fields of engineering design, virtual reality, film making and data visualization. Non-uniform rational B-spline (NURBS) fitting has been applied to curve and surface reconstruction for many years because it is a flexible method and can be used to build many complex mathematical models, unlike certain other methods. To apply NURBS fitting, there are two major difficult sub-problems that must be solved: (1) the determination of a knot vector and (2) the computation of weights and the parameterization of data points. These two problems are quite challenging and determine the effectiveness of the overall NURBS fit. In this study, we propose a new method, which is a combination of a hybrid optimization algorithm and an iterative scheme (with the acronym HOAAI), to address these difficulties. The novelties of our proposed method are the following: (1) it introduces a projected optimization algorithm for optimizing the weights and the parameterization of the data points, (2) it provides an iterative scheme to determine the knot vectors, which is based on the calculated point parameterization, and (3) it proposes the boundary-determined parameterization and the partition-based parameterization for unorganized points. We conduct numerical experiments to measure the performance of the proposed HOAAI with six test problems, including a complicated curve, twisted and singular surfaces, unorganized data points and, most importantly, real measured data points from the Mashan Pumped Storage Power Station in China. The simulation results show that the proposed HOAAI is very fast, effective and robust against noise. Furthermore, a comparison with other approaches indicates that the HOAAI is competitive in terms of both accuracy and runtime costs.

References

[1]

Floater, M.S., Parameterization and smooth approximation of surface triangulations. Computer Aided Geometric Design. v14 i3. 231-250.

[2]

Pan, R.J. and Skala, V., Continuous global optimization in surface reconstruction from an oriented point cloud. Computer-Aided Design. v43 i8. 896-901.

[3]

Hussain, M.Z. and Sarfraz, M., Monotone piecewise rational cubic interpolation. International Journal of Computer Mathematics. v86 i3. 423-430.

[4]

Eck M, Hoppe H. Automatic reconstruction of B-spline surfaces of arbitrary topological type. In: Proceedings of the 23rd annual conference on computer graphics and interactive techniques. 1996. p. 325-34.

Digital Library

[5]

Gregorski, B., Hamann, B. and Joy, K., Reconstruction of B-spline surfaces from scattered data points. Proceedings Computer Graphics International. 163-170.

[6]

Sarkar, B. and Menq, C.H., Parameter optimization in approximating curves and surfaces to measurement data. Computer Aided Geometric Design. v8. 267-290.

[7]

Yang, Z., Deng, J. and Chen, F.L., Fitting unorganized point clouds with active implicit B-spline curves. The Visual Computer. v21 i1. 831-839.

[8]

Borges, C.F. and Pastva, T., Total least squares fitting of Bezier and B-spline curves to ordered data. Computer Aided Geometric Design. v19 i4. 275-289.

[9]

Gálvez, A., Iglesias, A. and Puig-Pey, J., Iterative two-step genetic-algorithm-based method for efficient polynomial B-spline surface reconstruction. Information Science. v182 i1. 56-76.

[10]

Wang, W.P., Pottmann, H. and Liu, Y., Fitting B-spline curves to point clouds by curvature-based squared distance minimization. ACM Transactions on Graphics. v25 i2. 214-238.

[11]

Zhao, X.Y., Zhang, C.M., Yang, B. and Li, P.P., Adaptive knot placement using a GMM-based continuous optimization algorithm in B-spline curve approximation. Computer Aided Design. v43 i6. 598-604.

[12]

Riyazuddin M. Visualization with NURBS using simulated annealing optimization technique. Master thesis. Dept. ICS. King Fahd University of Petroleum and Minerals, Dhahran (Saudi Arabia); 2004.

[13]

Sarfraz, M., Raza, S.A. and Baig, M.H., Computing optimized curves with NURBS using evolutionary intelligence. Lecture Notes in Computer Science. v3483. 806-815.

[14]

Wagner T, Michelitsch T, Sacharow A. On the design of optimizers for surface reconstruction. In: Proceedings of the 2007 genetic and evolutionary computation conference-GECCO2007. London (England); 2007. p. 2195-202.

[15]

Weinert K, Surmann T, Mehnen J. Evolutionary surface reconstruction using CSG-NURBS-hybrids. In: Proceedings of the 2001 genetic and evolutionary computation conference-GECCO2001. San Francisco (USA); 2001. p. 1456-463.

[16]

Gálvez, A. and Iglesias, A., Particle swarm optimization for non-uniform rational B-spline surface reconstruction from clouds of 3D data points. Information Science.

[17]

Laurent-Gengoux, P. and Mekhilef, M., Optimization of a NURBS representation. Computer Aided Design. v25 i11. 699-710.

[18]

De Boor, C., A practical guide to splines. 1978. Springer-Verlag.

[19]

Lee, E.T., Choosing nodes in parametric curve interpolation. Computer-Aided Design. v21 i6. 363-370.

[20]

Hendrix, E.M.T. and Toth, B.G., Introduction to nonlinear and global optimization. 2010. Springer, Cambridge.

[21]

Schwartz, A. and Polak, E., Family of projected descent methods for optimization problems with simple bounds. Journal of Optimization Theory and Applications. v92 i1. 1-31.

[22]

Lin, C.J. and Moré, J.J., Newton's method for large bound-constrained optimization problems. SIAM Journal on Optimization. v9 i4. 1100-1127.

[23]

Li, W., Xu, S., Zhao, G. and Goh, L.P., Adaptive knot placement in B-spline curve approximation. Computer-Aided Design. v37 i7. 791-797.

[24]

í***lker, E. and Arslan, A., Automatic knot adjustment using an artificial immune system for B-spline curve approximation. Information Sciences. v179 i10. 1483-1494.

[25]

Weiss, V., Andor, L., Renner, G. and Varady, T., Advanced surface fitting techniques. Computer Aided Geometric Design. v19 i1. 19-42.

[26]

Ma, W.Y. and Kruth, J.P., Parameterization of randomly measured points for least squares fitting of B-spline curves and surfaces. Computer-Aided Design. v27 i9. 663-675.

[27]

Moré, J.J., The Levenberg-Marquardt algorithm: implementation and theory. In: Watson, G.A. (Ed.), Numerical analysis, Springer-Verlag, Berlin.

[28]

Krause, F.L., Fischer, A., Gross, N. and Barhak, J., Reconstruction of freeform objects with arbitrary topology using neural networks and subdivision techniques. CIRP Annals-Manufacturing Technology. v52 i1. 125-128.

[29]

Hoppe H, DeRose T, Duchamp T, Halstead M, Jin H, McDonald J, Schweitzer J, Stuetzle W. Piecewise smooth surface reconstruction. In: Proceedings of the 21st annual conference on computer graphics and interactive techniques (SIGGRAPH'94). New York (USA); 1994. p. 295-302.

Digital Library

[30]

Krishnamurthy, V. and Levoy, M., Fitting smooth surfaces to dense polygon meshes. In: Proceedings of the 23rd annual conference on computer graphics and interactive techniques (SIGGRAPH '96), ACM, New York (NY, USA). pp. 313-324.

[31]

Praun, E. and Hoppe, H., Spherical parametrization and remeshing. ACM Transaction on Graphics (SIGGRAPH). v22 i3. 340-349.

[32]

Losasso F, Hoppe H, Schaefer S, Warren JD. Smooth geometry images. In: Proceedings of symposium on geometry processing. 2003. p. 138-45.

[33]

Barhak, J. and Fischer, A., Adaptive parameterization for reconstruction of 3D freeform objects from laser-scanned data based on a PDE approach. The Visual Computer. v17 i6. 351-369.

[34]

Parameterization and reconstruction from 3D scattered points based on neural network and PDE techniques. IEEE Transactions on Visualization and Computer Graphics. v7 i1. 1-16.

[35]

Floater, M.S., Meshless parameterization and B-spline surface approximation. Proceedings of IMA Conference on the Mathematics of Surfaces. 1-18.

[36]

Azariadis, P.N., Parameterization of clouds of unorganized points using dynamic base surfaces. Computer Aided Design. v36 i7. 607-623.

[37]

Storn, R. and Price, K., Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization. v11 i4. 341-359.

[38]

Jolliffe, I.T., Principal component analysis. 2002. 2nd edition. Springer.

[39]

Hoppe, H., DeRose, T., Duchamp, T., McDonald, J. and Stuetzle, W., Surface reconstruction from unorganized points. SIGGRAPH Computer Graphics. v26 i2. 71-78.

Cited By

Zhu HCao JXiao YChen ZZhong ZZhang Y(2022)TCB-spline-based Image VectorizationACM Transactions on Graphics10.1145/351313241:3(1-17)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3513132
Jahanshahloo AEbrahimi A(2022)Reconstruction of 3D shapes with B-spline surface using diagonal approximation BFGS methodsMultimedia Tools and Applications10.1007/s11042-022-13024-681:26(38091-38111)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s11042-022-13024-6
Leth NPetersen H(2021)A New Method for Generating Work Piece Surface Representations for Robotic Machining2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS51168.2021.9636774(7607-7614)Online publication date: 27-Sep-2021
https://dl.acm.org/doi/10.1109/IROS51168.2021.9636774
Show More Cited By

Iteration and optimization scheme for the reconstruction of 3D surfaces based on non-uniform rational B-splines
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling

Recommendations

Matrix weighted rational curves and surfaces

Rational curves and surfaces are powerful tools for shape representation and geometric modeling. However, the real weights are generally difficult to choose except for a few special cases such as representing conics. This paper presents an extension of ...
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 ...
Rational C 1 cubic Powell–Sabin B-splines with application to representation of ruled surfaces
Abstract
This paper defines rational C 1 cubic Powell–Sabin splines and analyses their basic properties. A rational B-spline basis is established and an algorithm for determining the corresponding control points and weights by using the blossoming ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computer-Aided Design

Computer-Aided Design Volume 44, Issue 11

November, 2012

105 pages

ISSN:0010-4485

Issue’s Table of Contents

Copyright © Elsevier Ltd © 2012.

Publisher

Butterworth-Heinemann

United States

Publication History

Published: 01 November 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhu HCao JXiao YChen ZZhong ZZhang Y(2022)TCB-spline-based Image VectorizationACM Transactions on Graphics10.1145/351313241:3(1-17)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3513132
Jahanshahloo AEbrahimi A(2022)Reconstruction of 3D shapes with B-spline surface using diagonal approximation BFGS methodsMultimedia Tools and Applications10.1007/s11042-022-13024-681:26(38091-38111)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s11042-022-13024-6
Leth NPetersen H(2021)A New Method for Generating Work Piece Surface Representations for Robotic Machining2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS51168.2021.9636774(7607-7614)Online publication date: 27-Sep-2021
https://dl.acm.org/doi/10.1109/IROS51168.2021.9636774
Bhattarai SDahal KVichare PChen W(2020)Adapted Delaunay triangulation method for free-form surface generation from random point clouds for stochastic optimization applicationsStructural and Multidisciplinary Optimization10.1007/s00158-019-02385-661:2(649-660)Online publication date: 1-Feb-2020
https://dl.acm.org/doi/10.1007/s00158-019-02385-6
Nashed YPeterka TMahadevan VGrindeanu I(2019)Rational Approximation of Scientific DataComputational Science – ICCS 201910.1007/978-3-030-22734-0_2(18-31)Online publication date: 12-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-22734-0_2
Zhang YCao JChen ZZeng X(2017)Surface reconstruction using simplex splines on feature-sensitive configurationsComputer Aided Geometric Design10.1016/j.cagd.2017.01.00150:C(14-28)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1016/j.cagd.2017.01.001
Dimitrov AGu RGolparvar-Fard M(2016)Non-Uniform B-Spline Surface Fitting from Unordered 3D Point Clouds for As-Built ModelingComputer-Aided Civil and Infrastructure Engineering10.1111/mice.1219231:7(483-498)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1111/mice.12192
Yang X(2016)Matrix weighted rational curves and surfacesComputer Aided Geometric Design10.1016/j.cagd.2015.11.00542:C(40-53)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1016/j.cagd.2015.11.005
Zhang YCao JChen ZLi XZeng X(2016)B-spline surface fitting with knot position optimizationComputers and Graphics10.1016/j.cag.2016.05.01058:C(73-83)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.cag.2016.05.010
Norouzzadeh Ravari AD. Taghirad H(2016)Reconstruction of B-spline curves and surfaces by adaptive group testingComputer-Aided Design10.1016/j.cad.2016.01.00274:C(32-44)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1016/j.cad.2016.01.002
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents