×

Computing the minimum distance between two Bézier curves. (English) Zbl 1166.65006

Summary: A sweeping sphere clipping method is presented for computing the minimum distance between two Bézier curves. The sweeping sphere is constructed by rolling a sphere with its center point along a curve. The initial radius of the sweeping sphere can be set as the minimum distance between an end point and the other curve. The nearest point on a curve must be contained in the sweeping sphere along the other curve, and all of the parts outside the sweeping sphere can be eliminated. A simple sufficient condition when the nearest point is one of the two end points of a curve is provided, which turns the curve/curve case into a point/curve case and leads to higher efficiency. Examples are shown to illustrate efficiency and robustness of the new method.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chen, X. D.; Su, H.; Yong, J. H.; Paul, J. C.; Sun, J. G., A counterexample on point inversion and projection for NURBS curve, Computer Aided Geometric Design, 24, 302 (2007) · Zbl 1171.65328
[2] Chen, X. D.; Zhou, Y.; Shu, Z.; Su, H.; Paul, J. C., Improved algebraic algorithm on point projection for Bézier curves, International Multi-Symposiums on Computer and Computational Sciences, 17, 158-163 (2007)
[3] G. Elber, M. Kim, Geometric constraint solver using multivariate rational spline functions, in: Proceedings of the Sixth ACM Symposium on Solid Modeling and Applications, 2001 pp. 1-10; G. Elber, M. Kim, Geometric constraint solver using multivariate rational spline functions, in: Proceedings of the Sixth ACM Symposium on Solid Modeling and Applications, 2001 pp. 1-10
[4] Hu, S.; Wallner, J., A second order algorithm for orthogonal projection onto curves and surfaces, Computer Aided Geometric Design, 22, 251-260 (2005) · Zbl 1205.65086
[5] D. Johnson, E. Cohen, A framework for efficient minimum distance computations, in: Proceedings of IEEE International Conference on Robotics & Automation, 1998, pp. 3678-3684; D. Johnson, E. Cohen, A framework for efficient minimum distance computations, in: Proceedings of IEEE International Conference on Robotics & Automation, 1998, pp. 3678-3684
[6] Limaiem, A.; Trochu, F., Geometric algorithms for the intersection of curves and surfaces, Computer & Graphics, 19, 391-403 (1995)
[7] Lin, M.; Manocha, D., Fast interference detection between geometric models, The Visual Computer, 11, 542-561 (1995)
[8] Ma, Y.; Hewitt, W., Point inversion and projection for NURBS curve and surface: Control polygon approach, Computer Aided Geometric Design, 20, 79-99 (2003) · Zbl 1069.65558
[9] Mortenson, M., Geometric Modeling (1985), Wiley: Wiley New York
[10] Patrikalakis, N.; Maekawa, T., Shape Interrogation for Computer Aided Design and Manufacturing (2001), Springer-Verlag: Springer-Verlag New York
[11] Piegl, L.; Tiller, W., Parametrization for surface fitting in reverse engineering, Computer-Aided Design, 33, 593-603 (2001)
[12] Piegl, L.; Tiller, W., The NURBS Book (1997), Springer-Verlag: Springer-Verlag New York · Zbl 0868.68106
[13] Pegna, J.; Wolter, F., Surface curve design by orthogonal projection of space curves onto free-form surfaces, Journal of Mechanical Design, 118, 42-52 (1996)
[14] Selimovic, I., Improved algorithms for the projection of points on NURBS curves and surfaces, Computer Aided Geometric Design, 23, 439-445 (2006) · Zbl 1098.65019
[15] Zhou, J. M.; Sherbrooke, E. C.; Patrikalakis, N., Computation of stationary points of distance functions, Engineering with Computers, 9, 231-246 (1993)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.