Journal of Computer Science and Technology ›› 2019, Vol. 34 ›› Issue (6): 1279-1293.doi: 10.1007/s11390-019-1967-z

Special Issue: Artificial Intelligence and Pattern Recognition; Computer Graphics and Multimedia

• Computer Graphics and Multimedia • Previous Articles     Next Articles

A Geometric Strategy Algorithm for Orthogonal Projection onto a Parametric Surface

Xiaowu Li1, Zhinan Wu2, Feng Pan3, Senior Member, CCF, Juan Liang4, Jiafeng Zhang1, Linke Hou5,*   

  1. 1 College of Data Science and Information Engineering, Guizhou Minzu University, Guiyang 550025, China;
    2 School of Mathematics and Computer Science, Yichun University, Yichun 336000, China;
    3 School of Software Engineering, South China University of Technology, Guangzhou 510006, China;
    4 Department of Science, Taiyuan Institute of Technology, Taiyuan 030008, China;
    5 Center for Economic Research, Shandong University, Jinan 250100, China
  • Received:2019-01-13 Revised:2019-09-04 Online:2019-11-16 Published:2019-11-16
  • Contact: Linke Hou
  • About author:Xiaowu Li received his M.S. degree in computer science from Chongqing University, Chongqing, in 2006, and Ph.D. degree in mathematics science from Chongqing University, Chongqing, in 2011. He is currently a professor of College of Data Science and Information Engineering in Guizhou Minzu University, Guiyang. His research interests include numerical solution of partial differential equation, pattern recognition, computation geometry and computer aided geometric design.
  • Supported by:
    This work is supported by the National Natural Science Foundation of China under Grant No. 61263034, the Feature Key Laboratory for Regular Institutions of Higher Education of Guizhou Province of China under Grant No.[2016]003, the Key Laboratory of Advanced Manufacturing Technology of Ministry of Education of China with Guizhou University under Grant No. KY[2018]479, the Training Center for Network Security and Big Data Application of Guizhou Minzu University under Grant No. 20161113006, the Shandong Provincial Natural Science Foundation of China under Grant No. ZR2016GM24, the Progress Project for Young Science and Technology Scholars of Guizhou Provincial Department of Education under Grant No. KY[2016]164.

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.

Key words: point projection problem; point inversion problem; normal curvature; normal curvature sphere; convergence analysis;

[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.
[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.
[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.
[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.
[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.
[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.
[9] Limaien A, Trochu F. Geometric algorithms for the intersection of curves and surfaces. Computers & Graphics, 1995, 19(3):391-403.
[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.
[11] Patrikalakis N, Maekawa T. Shape Interrogation for Computer Aided Design and Manufacturing (1st edition). Springer, 2002.
[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.
[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.
[15] Piegl L, Tiller W. The NURBS Book. Springer, 1995.
[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.
[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.
[18] Bartoň M. Solving polynomial systems using no-root elimination blending schemes. Computer-Aided Design, 2011, 43(12):1870-1878.
[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.
[20] Bartoň M, Elber G, Hanniel I. Topologically guaranteed univariate solutions of underconstrained polynomial systems via no-loop and single-component tests. ComputerAided Design, 2011, 43(8):1035-1044.
[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.
[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.
[23] Oh Y T, Kim Y J, Lee J, Kim M S, Elber G. Efficient pointprojection to freeform curves and surfaces. Computer Aided Geometric Design, 2012, 29(5):242-254.
[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.
[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.
[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.
[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.
[28] Hartmann E. On the curvature of curves and surfaces defined by normalforms. Computer Aided Geometric Design, 1999, 16(5):355-376.
[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).
[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.
[32] Li X, Wang L, Wu Z, Hou L, Liang J, Li Q. Hybrid secondorder iterative algorithm for orthogonal projection onto a parametric surface. Symmetry, 2017, 9(8):Article No. 146.
[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.
[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.
[35] Wang X P, Zhang W Z, Huang X. Computation of point inversion and ray-surface intersection through tracing along the base surface. The Visual Computer, 2015, 31(11):1487-1500.
[36] Piegl L A. Ten challenges in computer-aided design. Computer-Aided Design, 2005, 37(4):461-470.
No related articles found!
Full text



[1] Zhang Yongyue; Peng Zhenyun; You Suya; Xu Guangyou;. A Multi-View Face Recognition System[J]. , 1997, 12(5): 400 -407 .
[2] WEI Xiaohui; JU Jiubin;. SFT: A Consistent Checkpointing Algorithm with Short Freezing Time[J]. , 2000, 15(2): 169 -175 .
[3] Jian-Wen Chen, Guo-Ping Li, and Yun He. A Novel MBAFF Scheme of AVS[J]. , 2006, 21(3): 323 -331 .
[4] Hao-Jun Ai, Shui-Xian Chen, and Rui-Min Hu. Introduction to AVS Audio[J]. , 2006, 21(3): 360 -365 .
[5] Gang Xu, Guo-Zhao Wang, and Xiao-Diao Chen. Free-Form Deformation with Rational DMS-Spline Volumes[J]. , 2008, 23(5 ): 862 -873 .
[6] R Raghavendra, Rao Ashok, and G Hemantha Kumar. Multimodal Biometric Score Fusion Using Gaussian Mixture Model and Monte Carlo Method[J]. , 2010, 25(4): 771 -782 .
[7] Yi-Hong Wu (吴毅红), Tian Lan (兰 添), and Zhan-Yi Hu (胡占义). Degeneracy from Twisted Cubic Under Two Views[J]. , 2010, 25(5): 916 -924 .
[8] Jung-Been Lee, Taek Lee, Hoh Peter In. Topic Modeling Based Warning Prioritization from Change Sets of Software Repository[J]. Journal of Computer Science and Technology, 2020, 35(6): 1461 -1479 .
[9] Xi-Bei Yang(杨习贝), Yu-Hua Qian(钱宇华), Member, CCF, IEEE, and Jing-Yu Yang(杨静宇), Member, CCF, IEEE. Hierarchical Structures on Multigranulation Spaces[J]. , 2012, 27(6): 1169 -1183 .
[10] Lun-Yao Wang, Zhu-Fei Chu, and Yin-Shui Xia. Low Power State Assignment Algorithm for FSMs Considering Peak Current Optimization[J]. , 2013, 28(6): 1054 -1062 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
  Copyright ©2015 JCST, All Rights Reserved