点到Bézier曲面最近距离高效稳定的计算方法
|
摘要
针对现有点投影算法不能同时快速收敛和保持计算稳定性等问题,提出结合二次曲面逼近的Bézier曲面点投影算法。首先,通过距离函数对应的控制网格信息得到若干个局部极小控制点;其次,在极小控制点对应的局部区域内,采用二次曲面逼近估算出对应的最小值及其参数,更好地筛选和优化对应的初始值;最后,根据获得的初始值,使用Newton法进行迭代解得最近距离。新算法不仅可获得全局最优解,同时能做到快速收敛。数值实例表明:与已有的细分剪枝算法相比,新算法的计算效率可提高至5～15倍。
Prevailing point projection algorithms can not eithor quickly converge or maintain the computational stability. This paper proposes a Bézier surface point projection algorithm combined with quadratic surface approximation technique. Firstly, the new method obtains several local minimum control points of the control net corresponding to the distance function; secondly, quadratic surface approximation is used to refine the corresponding minimum value and its parameters for each local region, which leads to much better initial values; finally, the Newton's method is applied for solving accurate solutions. The new algorithm not only obtains the global optimal solution, but also achieves fast convergence. Numerical examples show that the new algorithm can improve the computational efficiency by 5～15 times by comparing with prevailing pruning algorithms.
Prevailing point projection algorithms can not eithor quickly converge or maintain the computational stability. This paper proposes a Bézier surface point projection algorithm combined with quadratic surface approximation technique. Firstly, the new method obtains several local minimum control points of the control net corresponding to the distance function; secondly, quadratic surface approximation is used to refine the corresponding minimum value and its parameters for each local region, which leads to much better initial values; finally, the Newton's method is applied for solving accurate solutions. The new algorithm not only obtains the global optimal solution, but also achieves fast convergence. Numerical examples show that the new algorithm can improve the computational efficiency by 5～15 times by comparing with prevailing pruning algorithms.
引文
[1] CHEN X D,YONG J H,WANG G,et al.Computing the minimum distance between a point and a NURBS curve[J].Computer-Aided Design,2008,40(10):1051-1054.
[2] ZHU F,LIU B.Computing the minimum distance between a point and a curve on mesh[J].Journal of Computational Methods in Sciences and Engineering,2015,15(1):13-22.
[3] JIMENEZ P,THOMAS F,TORRAS C,et al.3D collision detection:a survey[J].Computers & Graphics,2001,25(2):269-285.
[4] ZHANG L,BIAN Y,CHEN H,et al.Implementation of a CNC NURBS curve interpolator based on control of speed and precision[J].International Journal of Production Research,2009,47(6):1505-1519.
[5] LI X,WANG L,WU Z,et al.Convergence analysis on a second order algorithm for orthogonal projection onto curves[J].Symmetry,2017,9(10):210.
[6] LI X,PAN F,CHENG T,et al.Integrated hybrid second order algorithm for orthogonal projection onto a planar implicit curve[J].Symmetry,2018,10(5):164.
[7] UPRETI K,SUBBARAYAN G.Signed algebraic level sets on NURBS surfaces and implicit Boolean compositions for isogeometric CAD-CAE integration[J].Computer-Aided Design,2017,82:112-126.
[8] LI X,HOU L,LIANG J,et al.The analytical expressions for computing the minimum distance between a point and a torus[J].Journal of Computer and Communications,2016,4(4):125.
[9] WU J,ZHOU H,TANG X,et al.Implementation of CL points preprocessing methodology with NURBS curve fitting technique for high-speed machining[J].Computers & Industrial Engineering,2015,81:58-64.
[10] 陆洋,施侃乐,雍俊海.细分法求解点投影问题时的剪枝算法[J].计算机辅助设计与图形学学报,2014,26(4):617-622.
[11] 宋海川.点到自由曲线和曲面上法向投影问题的研究[D].北京:清华大学,2015.
[12] OH Y T,KIM Y J,LEE J,et al.Efficient point-projection to freeform curves and surfaces[J].Computer Aided Geometric Design,2012,29(5):242-254.
[13] PIEGLA L A,TILLERB W.Parametrization for surface fitting in reverse engineering[J].Computer-Aided Design,2001,33(8):593-603.
[14] QI J D,SHOU H H.A subdivision algorithm for computing the minimum distance between a point and an algebraic curve[J].Journal of Zhejiang University (Science Edition),2016,43:286-291.
[2] ZHU F,LIU B.Computing the minimum distance between a point and a curve on mesh[J].Journal of Computational Methods in Sciences and Engineering,2015,15(1):13-22.
[3] JIMENEZ P,THOMAS F,TORRAS C,et al.3D collision detection:a survey[J].Computers & Graphics,2001,25(2):269-285.
[4] ZHANG L,BIAN Y,CHEN H,et al.Implementation of a CNC NURBS curve interpolator based on control of speed and precision[J].International Journal of Production Research,2009,47(6):1505-1519.
[5] LI X,WANG L,WU Z,et al.Convergence analysis on a second order algorithm for orthogonal projection onto curves[J].Symmetry,2017,9(10):210.
[6] LI X,PAN F,CHENG T,et al.Integrated hybrid second order algorithm for orthogonal projection onto a planar implicit curve[J].Symmetry,2018,10(5):164.
[7] UPRETI K,SUBBARAYAN G.Signed algebraic level sets on NURBS surfaces and implicit Boolean compositions for isogeometric CAD-CAE integration[J].Computer-Aided Design,2017,82:112-126.
[8] LI X,HOU L,LIANG J,et al.The analytical expressions for computing the minimum distance between a point and a torus[J].Journal of Computer and Communications,2016,4(4):125.
[9] WU J,ZHOU H,TANG X,et al.Implementation of CL points preprocessing methodology with NURBS curve fitting technique for high-speed machining[J].Computers & Industrial Engineering,2015,81:58-64.
[10] 陆洋,施侃乐,雍俊海.细分法求解点投影问题时的剪枝算法[J].计算机辅助设计与图形学学报,2014,26(4):617-622.
[11] 宋海川.点到自由曲线和曲面上法向投影问题的研究[D].北京:清华大学,2015.
[12] OH Y T,KIM Y J,LEE J,et al.Efficient point-projection to freeform curves and surfaces[J].Computer Aided Geometric Design,2012,29(5):242-254.
[13] PIEGLA L A,TILLERB W.Parametrization for surface fitting in reverse engineering[J].Computer-Aided Design,2001,33(8):593-603.
[14] QI J D,SHOU H H.A subdivision algorithm for computing the minimum distance between a point and an algebraic curve[J].Journal of Zhejiang University (Science Edition),2016,43:286-291.