Home Journal of Computer Science and Technology Article
Article Link
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Show Outline
Outline
Abstract
Keywords
Electronic Supplementary Material
References
Show full outline
Hide outline
Regular Paper

A Geometric Strategy Algorithm for Orthogonal Projection onto a Parametric Surface

College of Data Science and Information Engineering, Guizhou Minzu University, Guiyang 550025, China
School of Mathematics and Computer Science, Yichun University, Yichun 336000, China
School of Software Engineering, South China University of Technology, Guangzhou 510006, China
Department of Science, Taiyuan Institute of Technology, Taiyuan 030008, China
Center for Economic Research, Shandong University, Jinan 250100, China
Show Author Information

Abstract

In this paper, we investigate how to compute the minimum distance between a point and a parametric surface, and then to return the nearest point (foot point) on the surface as well as its corresponding parameter, which is also called the point projection problem of a parametric surface. The geometric strategy algorithm (hereafter GSA) presented consists of two parts as follows. The normal curvature to a given parametric surface is used to find the corresponding foot point firstly, and then the Taylor’s expansion of the parametric surface is employed to compute parameter increments and to get the iteration formula to calculate the orthogonal projection point of test point to the parametric surface. Our geometric strategy algorithm is essentially dependent on the geometric property of the normal curvature, and performs better than existing methods in two ways. Firstly, GSA converges faster than existing methods, such as the method to turn the problem into a root-finding of nonlinear system, subdividing methods, clipping methods, geometric methods (tangent vector and geometric curvature) and hybrid second-order method, etc. Specially, it converges faster than the classical Newton’s iterative method. Secondly, GSA is independent of the initial iterative value, which we prove in Theorem 1. Many numerical examples confirm GSA’s robustness and efficiency.

Keywords

point projection problempoint inversion problemnormal curvaturenormal curvature sphereconvergence analysis

Electronic Supplementary Material

Download File(s)
jcst-34-6-1279-Highlights.pdf (103.3 KB)

References

[1]

Ma Y L, Hewitt W T. Point inversion and projection for NURBS curve and surface: Control polygon approach. Computer Aided Geometric Design, 2003, 20(2): 79-99.

Crossref Google Scholar
[2]

Yang H P, Wang W P, Sun J G. Control point adjustment for B-spline curve approximation. Computer-Aided Design, 2004, 36(7): 639-652.

Crossref Google Scholar
[3]
Johnson D E, Cohen E. A framework for efficient minimum distance computations. In Proc. the 1998 IEEE International Conference on Robotics & Automation, May 1998, pp.3678-3684.
[4]

Piegl L, Tiller W. Parametrization for surface fitting in reverse engineering. Computer-Aided Design, 2001, 33(8): 593-603.

Crossref Google Scholar
[5]

Pegna J, Wolter F E. Surface curve design by orthogonal projection of space curves onto free-form surfaces. Journal of Mechanical Design, 1996, 118: 45-52.

Crossref Google Scholar
[6]

Besl P J, McKay N D. A method for registration of 3-D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256.

Crossref Google Scholar
[7]

Mortenson M E. Geometric Modeling (1st edition). Wiley, 1985.

[8]

Zhou J M, Sherbrooke E C, Patrikalakis N. Computation of stationary points of distance functions. Engineering with Computers, 1993, 9(4): 231-246.

Crossref Google Scholar
[9]

Limaien A, Trochu F. Geometric algorithms for the intersection of curves and surfaces. Computers & Graphics, 1995, 19(3): 391-403.

Crossref Google Scholar
[10]

Polak E, Royset J O. Algorithms with adaptive smoothing for finite minimax problems. Journal of Optimization: Theory and Applications, 2003, 119(3): 459-484.

Crossref Google Scholar
[11]

Patrikalakis N, Maekawa T. Shape Interrogation for Computer Aided Design and Manufacturing (1st edition). Springer, 2002.

Crossref
[12]
Johnson D E, Cohen E. Distance extrema for spline models using tangent cones. In Proc. the 2005 Conference on Graphics Interface, May 2005, pp.169-175.
[13]

Selimovic I. Improved algorithms for the projection of points on NURBS curves and surfaces. Computer Aided Geometric Design, 2006, 23(5): 439-445.

Crossref Google Scholar
[14]

Cohen E, Lyche T, Riesebfeld R. Discrete B-splines and subdivision techniques in computer-aided geometric design and computer graphics. Computer Graphics and Image Processing, 1980, 14(2): 87-111.

Crossref Google Scholar
[15]

Piegl L, Tiller W. The NURBS Book. Springer, 1995.

Crossref
[16]
Elber G, Kim M S. Geometric constraint solver using multivariate rational spline functions. In Proc. the 6th ACM Symposiumon Solid Modeling and Applications, June 2001, pp.1-10.
Crossref
[17]

Park C H, Elber G, Kim K J, Kim G Y, Seong J K. A hybrid parallel solver for systems of multivariate polynomials using CPUs and GPUs. Computer-Aided Design, 2011, 43(11): 1360-1369.

Crossref Google Scholar
[18]

Bartoň M. Solving polynomial systems using no-root elimination blending schemes. Computer-Aided Design, 2011, 43(12): 1870-1878.

Crossref Google Scholar
[19]

van Sosin B, Elber G. Solving piecewise polynomial constraint systems with decomposition and a subdivision-based solver. Computer-Aided Design, 2017, 90: 37-47.

Crossref Google Scholar
[20]

Bartoň M, Elber G, Hanniel I. Topologically guaranteed univariate solutions of underconstrained polynomial systems via no-loop and single-component tests. Computer-Aided Design, 2011, 43(8): 1035-1044.

Crossref Google Scholar
[21]

Chen X D, Yong J H, Wang G Z, Paul J C, Xu G. Computing the minimum distance between a point and a NURBS curve. Computer-Aided Design, 2008, 40(10/11): 1051-1054.

Crossref Google Scholar
[22]

Chen X D, Xu G, Yong J H, Wang G Z, Paul J C. Computing the minimum distance between a point and a clamped B-spline surface. Graphical Models, 2009, 71(3): 107-112.

Crossref Google Scholar
[23]

Oh Y T, Kim Y J, Lee J, Kim M S, Elber G. Efficient point-projection to freeform curves and surfaces. Computer Aided Geometric Design, 2012, 29(5): 242-254.

Crossref Google Scholar
[24]

Liu X M, Yang L, Yong J H, Gu H J, Sun J G. A torus patch approximation approach for point projection on surfaces. Computer Aided Geometric Design, 2009, 26(5): 593-598.

Crossref Google Scholar
[25]

Hu S M, Wallner J. A second-order algorithm for orthogonal projection onto curves and surfaces. Computer Aided Geometric Design, 2005, 22: 251-260.

Crossref Google Scholar
[26]

Li X, Wu Z, Hou L, Wang L, Yue C, Xin Q. A geometric orthogonal projection strategy for computing the minimum distance between a point and a spatial parametric curve. Algorithms, 2016, 9(1): Article No. 15.

Crossref Google Scholar
[27]

Li X, Wang L, Wu Z, Hou L, Liang J, Li Q. Convergence analysis on a second-order algorithm for orthogonal projection onto curves. Symmetry, 2017, 9(10): Article No. 210.

Crossref Google Scholar
[28]

Hartmann E. On the curvature of curves and surfaces defined by normalforms. Computer Aided Geometric Design, 1999, 16(5): 355-376.

Crossref Google Scholar
[29]

Hoschek J, Lasser D. Fundamentals of Computer Aided Geometric Design (1st edition). A K Peters/CRC Press, 1996.

[30]

Hu S M, Sun J G, Jin T G, Wang G Z. Computing the parameter of points on Nurbs curves and surfaces via moving affine frame method. J. Software, 2000, 11(1): 49-53. (in Chinese).

Google Scholar
[31]

Liang J, Hou L, Li X, Pan F, Cheng T, Wang L. Hybrid second-order method for orthogonal projection onto parametric curve in n-dimensional Euclidean space. Mathematics, 2018, 6(12): Article No. 306.

Crossref Google Scholar
[32]

Li X, Wang L, Wu Z, Hou L, Liang J, Li Q. Hybrid second-order iterative algorithm for orthogonal projection onto a parametric surface. Symmetry, 2017, 9(8): Article No. 146.

Crossref Google Scholar
[33]

Li X, Pan F, Cheng T, Wu Z, Liang J, Hou L. Integrated hybrid second order algorithm for orthogonal projection onto a planar implicit curve. Symmetry, 2018, 10(5): Article No. 164.

Crossref Google Scholar
[34]

Ko K H, Sakkalis T. Orthogonal projection of points in CAD/CAM applications: An overview. Journal of Computational Design and Engineering, 2014, 1(2): 116-127.

Crossref Google Scholar
[35]

Wang X P, Zhang W Z, Huang X. Computation of point in-version and ray-surface intersection through tracing along the base surface. The Visual Computer, 2015, 31(11): 1487-1500.

Crossref Google Scholar
[36]

Piegl L A. Ten challenges in computer-aided design. Computer-Aided Design, 2005, 37(4): 461-470.

Crossref Google Scholar
Journal of Computer Science and Technology
Volume 34 Issue 6,
November 2019
Pages 1279-1293
DOI: 10.1007/s11390-019-1967-z
Cite this article:
Li X, Wu Z, Pan F, et al. A Geometric Strategy Algorithm for Orthogonal Projection onto a Parametric Surface. Journal of Computer Science and Technology, 2019, 34(6): 1279-1293. https://doi.org/10.1007/s11390-019-1967-z
Metrics & Citations  
Article History
Copyright
Return