Improved algorithms for determining the injectivity of 2D and 3D rational Bézier curves

Xuanyi Zhao; Jinggai Li; Ying Wang; Chungang Zhu; Xuanyi Zhao; Jinggai Li; Ying Wang; Chungang Zhu

doi:10.3934/era.2022091

Electronic Research Archive

2022, Volume 30, Issue 5: 1799-1812. doi: 10.3934/era.2022091

Previous Article Next Article

Research article

Improved algorithms for determining the injectivity of 2D and 3D rational Bézier curves

1.
School of Science, Dalian Maritime University, Dalian 116026, China
2.
College of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, China
3.
School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China

Academic Editor: Predrag Stanimirovic

Received: 28 December 2021 Revised: 19 March 2022 Accepted: 24 March 2022 Published: 30 March 2022

Bézier curves and surfaces are important to computer-aided design applications. This paper presents algorithms for checking the injectivity of 2D and 3D Bézier curves. An injective Bézier curve or surface is one that has no self-intersections. The proposed algorithms use recently proposed sufficient and necessary conditions under which Bézier curves are guaranteed to be non-self-intersecting. As well as a rigorous derivation of the proposed algorithms, we present a series of examples and derive the complexity and computation times of the proposed algorithms. We find that the complexity our algorithms is approximately $ O(m) $, representing an improvement over previous injectivity-checking algorithms.
- injectivity,
- Bézier curve,
- monotone chain,
- algorithm analysis
Citation: Xuanyi Zhao, Jinggai Li, Ying Wang, Chungang Zhu. Improved algorithms for determining the injectivity of 2D and 3D rational Bézier curves[J]. Electronic Research Archive, 2022, 30(5): 1799-1812. doi: 10.3934/era.2022091

Related Papers:

Abstract

Bézier curves and surfaces are important to computer-aided design applications. This paper presents algorithms for checking the injectivity of 2D and 3D Bézier curves. An injective Bézier curve or surface is one that has no self-intersections. The proposed algorithms use recently proposed sufficient and necessary conditions under which Bézier curves are guaranteed to be non-self-intersecting. As well as a rigorous derivation of the proposed algorithms, we present a series of examples and derive the complexity and computation times of the proposed algorithms. We find that the complexity our algorithms is approximately $ O(m) $, representing an improvement over previous injectivity-checking algorithms.

References

[1]	W. Boehm, H. Prautzsch, Geometric Foundations of Geometric Design, AK Peter, Boston, 1992.
[2]	G. Farin, Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide, Academic Press, 1993.
[3]	G. E. Farin, D. Hansford, The Essentials of CAGD, A K Peters/CRC Press, 2000. http://doi.org/10.2307/3621635
[4]	J. Hoschek, D. Lasser, Grundlagen der geometrischen Datenverarbeitung, B. G. Teubner Stuttgart, 1992.
[5]	M. Duncan, Applied Geometry for Computer Graphics and CAD, Springer-Verlag, 2005.
[6]	M. Mortenson, Geometric modeling, New York: Wiley Computer Publishing, 2006.
[7]	L. A. Piegl, W. Tiller, The NURBS book, Springer-Verlag, 1997.
[8]	A. Rockwood, P. Chambers, Interactive curves and surfaces, in Technology-Based Re-Engineering Engineering Education Proceedings of Frontiers in Education FIE'96 26th Annual Conference, 1996,471–474.
[9]	F. P. Preparata, M. I. Shamos, Computational Geometry, Springer-Verlag, 1985.
[10]	P. E. Bézier, Example of an existing system in the motor industry: The Unisurf system, Proc. Roy. Soc. A, 321 (1971), 207–218. http://doi.org/10.1098/rspa.1971.0027 doi: 10.1098/rspa.1971.0027
[11]	P. Casteljau, De Casteljau's autobiography: My time at Citroën, Comput. Aided Geom. Design, 16 (1999), 583–586. http://doi.org/10.1016/S0167-8396(99)00024-2 doi: 10.1016/S0167-8396(99)00024-2
[12]	G. Farin, Some aspects of car body design at Daimler-Benz, in North-Holland Publ Co, (1983), 93–97.
[13]	H. J. Hochfeld, M. Ahlers, Role of Bézier curves and surfaces in the Volkswagen CAD approach from 1967 to today, Comput. Aided Design, 22 (1990), 598–608. http://doi.org/10.1016/0010-4485(90)90045-E doi: 10.1016/0010-4485(90)90045-E
[14]	P. Bézier, Numerical control: mathematics and applications, Jhon Wiley & Sons Ltd., Bristol, 1972.
[15]	P. Bézier, The Mathematical Basis of the UNISURF CAD System, Butterworth-Heinemann, 1986.
[16]	A. R. Forrest, Interactive interpolation and approximation by Bézier polynomials, Comput. Aided Design, 22 (1990), 527–537. http://doi.org/10.1016/0010-4485(90)90038-e doi: 10.1016/0010-4485(90)90038-e
[17]	W. J. Gordon, R. F. Riesenfeld, Bernstein-Bézier methods for the computer-aided design of free-form curves and surfaces, J. ACM, 21 (1974), 293–310. http://doi.org/10.1145/321812.321824 doi: 10.1145/321812.321824
[18]	G. Farin, Algorithms for rational Bézier curves, Comput. Aided Design, 15 (1983), 73–77.
[19]	G. Farin, J. Hoschek, M. S. Kim, Handbook of Computer Aided Geometric Design, Elsevier, 2002.
[20]	P. J. Barry, R. N. Goldman, Three examples of dual properties of Bézier curves, Math. Methods Comput. Aided Geom. Design, (1989), 61–69.
[21]	W. Boehm, On cubics: A survey, Comput. Graph. Image Process., 19 (1982), 201–226. http://doi.org/10.1016/0146-664X(82)90009-0 doi: 10.1016/0146-664X(82)90009-0
[22]	D. Nairn, J. Peters, D. Lutterkort, Sharp, quantitative bounds on the distance between a Bézier curve and its control polygon, Comput. Aided Geom. Design, 16 (1999), 613–631. http://doi.org/10.1016/S0167-8396(99)00026-6 doi: 10.1016/S0167-8396(99)00026-6
[23]	H. Lin, Geometric iterative methods and their applications, Zhejiang University, 2021.
[24]	H. Lin, T. Maekawa, C. Deng, Survey on geometric iterative methods and their applications, Comput. Aided Design, 95 (2018), 40–51. http://doi.org/10.1016/j.cad.2017.10.002 doi: 10.1016/j.cad.2017.10.002
[25]	J. Hoschek, Offset curves in the plane, Comput. Aided Design, 17 (1985), 77–82. http://doi.org/10.1016/0010-4485(85)90249-0 doi: 10.1016/0010-4485(85)90249-0
[26]	Y. S. Chua, Bézier brushstrokes, Comput. Aided Design, 22 (1990), 550–555. http://doi.org/10.1016/0010-4485(90)90040-J doi: 10.1016/0010-4485(90)90040-J
[27]	H. N. Phien, N. D. Ejdumrong, Efficient algorithms for Bézier curves, Comput. Aided Geom. Design, 17 (2000), 247–250. http://doi.org/10.1016/S0167-8396(99)00048-5 doi: 10.1016/S0167-8396(99)00048-5
[28]	C. M. Hoffmann, Geometric and solid modeling : An introduction, Morgan Kaufmann, 1989.
[29]	D. Lasser, Calculating the self-intersections of Bézier curves, Comput. Ind., 12 (1988), 259–268.
[30]	W. Tiller, E. G. Hanson, Offsets of two-dimensional profiles, IEEE Comput. Graph. Appl., 4 (1984), 36–46. http://doi.org/10.1109/MCG.1984.275995 doi: 10.1109/MCG.1984.275995
[31]	G. Craciun, L. Garcia-Puente, F. Sottile, Some geometrical aspects of control points for toric patches, Lect. Notes Comput. Sci., 5862 (2010), 111–135.
[32]	F. Sottile, C. G. Zhu, Injectivity of 2D toric Bézier patches, in International Conference on Computer-aided, (2011), 235–238.
[33]	C. Zhu, X. Zhao, Self-intersections of rational Bézier curves, Graph. Models, 76 (2014), 312–320. http://doi.org/10.1016/j.gmod.2014.04.001 doi: 10.1016/j.gmod.2014.04.001
[34]	Y. Yu, Y. Ji, C. Zhu, An improved algorithm for checking the injectivity of 2D toric surface patches, Comput. Math. Appl., 79 (2020), 2973–2986. http://doi.org/10.1016/j.camwa.2020.01.001 doi: 10.1016/j.camwa.2020.01.001
[35]	Y. Yu, Y. Ji, C. Zhu, Conditions for injectivity of toric volumes with arbitrary positive weights, Comput. Graph., 97 (2021), 88–98. http://doi.org/10.1016/j.cag.2021.04.026 doi: 10.1016/j.cag.2021.04.026
[36]	X. Zhao, J. Li, S. He, C. Zhu, Geometric conditions for injectivity of 3D Bézier volumes, AIMS Math., 6 (2021), 11974–11988. http://doi.org/10.3934/math.2021694 doi: 10.3934/math.2021694
[37]	F. P. Preparata, K. J. Supowit, Testing a simple polygon for monotonicity, Inf. Process. Lett., 12 (1981), 161–164. http://doi.org/10.1016/0020-0190(81)90091-0 doi: 10.1016/0020-0190(81)90091-0
[38]	R. Krasauskas, Toric surface patches, Adv. Comput. Math., 17 (2002), 89–113. http://doi.org/10.1023/A:1015289823859 doi: 10.1023/A:1015289823859
[39]	Y. Zhou, A new algorithm for polygon intersection operation, in International Conference on Computer & Electrical Engineering, 2009. http://doi.org/10.1109/ICCEE.2009.19
[40]	S. Park, H. Shin, Polygonal chain intersection, Comput. Graph-UK, 26 (2002), 341–350. http://doi.org/10.1016/S0097-8493(02)00060-2 doi: 10.1016/S0097-8493(02)00060-2
[41]	X. Zhao, C. Zhu, Injectivity of NURBS curves, J. Comput. Appl. Math., 302 (2016), 129–138. http://doi.org/10.1016/j.cam.2016.01.046 doi: 10.1016/j.cam.2016.01.046
[42]	X. Zhao, C. Zhu, H. Wang, Geometric conditions of non-self-intersecting NURBS surfaces, Appl. Math. Comput., 310 (2017), 89–96. http://doi.org/10.1016/j.amc.2017.04.016 doi: 10.1016/j.amc.2017.04.016

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)