Abstract
We present a genetic algorithm for approximating densely sampled curves with uniform cubic B-Splines suitable for Combined B-reps. A feature of this representation is altering the continuity property of the B-Spline at any knot, allowing to combine freeform curves and polygonal parts within one representation. Naturally there is a trade-off between different approximation properties like accuracy and the number of control points needed. Our algorithm creates very accurate B-Splines with few control points, as shown in Fig. 1. Since the approximation problem is highly nonlinear, we approach it with genetic methods, leading to better results compared to classical gradient based methods. Parallelization and adapted evolution strategies are used to create results very fast.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Renner, A. Markus G., Vancza, J.: Genetic algorithms in free form curve design. In: Mathematical Methods for Curves and Surfaces, pp. 343–354 (1995)
Renner, A. Markus G., Vancza, J.: Spline interpolation with genetic algorithms. In: Proceedings of the 1997 International Conference on Shape Modelling and Applications, pp. 47–54 (1997)
de Boor, C.: A Practical Guide to Splines (Applied Mathematical Sciences) (1978)
Catmull, E., Clark, J.: Recursively generated b-spline surfaces on arbitrary topological meshes. Comput. Aided Des. 10, 350–355 (1978)
Cohen, E., Riesenfeld, R.F., Elber, G.: Geometric Modeling with Splines: An Introduction (2001)
Farin, G.: Curves and Surfaces for CAGD: A Practical Guide (1993)
Goldenthal, R., Bercovier, M.: Spline curve approximation and design by optimal control over the knots using genetic algorithms. In: International Congress on Evolutionary Methods for Design, EUROGEN 2003 (2003)
Golub, G.H., van Loan, C.F.: Matrix Computations, 2nd edn. The John Hopkins University Press, Baltimore (1989)
Havemann, S.: Generative mesh modeling. PhD thesis, Braunschweig Technical University, Germany (2005)
Havemann, S., Fellner, D.: Progressive combined b-reps—multi-resolution meshes for interactive real-time shape design. J. WSCG 16(1–3), 121–135 (2008)
Hoschek, J.: Intrinsic parametrization for approximation. Comput. Aided Geom. Des. 5, 27–31 (1988)
Juhasz, I., Hoffmann, M.: The effect of knot modifications on the shape of b-spline curves. J. Geom. Graph. 5, 111–119 (2001)
Laurent-Gengoux, P., Mekhilef, M.: Optimization of a nurbs representation. Comput. Aided Des. 25(11), 699–710 (1993)
Renner, G., Ekart, A.: Genetic algorithms in computer aided design. Comput. Aided Des. 35(8), 709–726 (2003). Genetic Algorithms
Sapidis, N., Farin, G.: Automatic fairing algorithm for b-spline curves. Comput. Aided Des. 22, 121–129 (1990)
Shene, D.C.K.: CS3621 Introduction to computing with geometry notes. Department of Computer Science, Michigan Technological University, http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/. Last visited 10.02.2011 (2008)
Speer, T., Kuppe, M., Hoschek, J.: Global reparametrization for curve approximation. Comput. Aided Geom. Des. 15(9), 869–877 (1998)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bein, M., Fellner, D.W. & Stork, A. Genetic B-Spline approximation on combined B-reps. Vis Comput 27, 485–494 (2011). https://doi.org/10.1007/s00371-011-0592-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00371-011-0592-9