基于仿射算术和区间运算的直线与NURBS曲线/曲面求交

中国机械工程

基于仿射算术和区间运算的直线与NURBS曲线/曲面求交

池宝涛1,2;张见明1,2;鞠传明1,2

1.湖南大学机械与运载工程学院，长沙，410082
2.湖南大学汽车车身先进设计制造国家重点实验室，长沙，410082

出版日期:2019-05-10 发布日期:2019-05-14
基金资助:
国家自然科学基金资助项目(11472102，11772125)

An Improved Fast Algorithm for Solving Intersections of Lines and NURBS Curves and Surfaces Using Interval Analysis with Affine Transform

CHI Baotao1,2;ZHANG Jianming1,2;JU Chuanming1,2

1.College of Mechanical and Vehicle Engineering,Hunan University,Changsha，410082
2.State Key Laboratory of Advanced Design and Manufacturing for Vehicle Body,Hunan University,Changsha,410082

Online:2019-05-10 Published:2019-05-14

摘要/Abstract

摘要： 针对直线与参数空间NURBS曲线、直线与NURBS曲面求交问题，提出了一种改进的基于仿射算术和区间运算的直线与NURBS曲线/曲面求交的有效方法。该方法将基于边曲率或面曲率的子域分解方法应用到求交算法中，快速定位预迭代区间，减少不必要的迭代求交判断。与传统区间迭代算法相比，该求交算法为超线性收敛的快速迭代算法，在一定程度上解决了传统区间运算的“保守性”。另外，该方法放宽了对初始区间的要求，减少迭代次数，提高了迭代算法效率。通过计算区间算子判断给定直线与NURBS曲线/曲面有无交点和存在交点时的交点数目，保证了求解交点精度，为解决直线与曲线/曲面多交点判断及内外环或内外域判断等问题提供了有利条件。数值算例验证了该方法的有效性、计算精度和效率。

关键词: NURBS曲线/曲面, 仿射算术, 区间分析, 快速求交

Abstract: An improved geometric method was presented for efficiently computing intersections between a line and a NURBS curve in parametric space or a line and a NURBS surface using interval arithmetic with affine transform. Combined with the subdomain decomposition algorithm based on the curve or surface curvatures, the appropriate preliminary iterative intervals could be determined quickly. In comparison with conventional interval iterative algorithms, the proposed method was superlinearly convergent which could overcome the conservatism of conventional interval arithmetic to some extents. In addition, the method prossessed the ability to relax requirements for initial iterative intervals, greatly to reduce numbers of unnecessary iterations and to promote the performance and efficiency of interval arithmetic. Based on the numbers of intersection points and the computational accuracy, this method could be applicable to the intersection problems of the inner and outer loop or domain. Numerical examples demonstrate the validity, accuracy and efficiency of the proposed method.

Key words: NURBS curve and surface, affine transform, interval analysis, rapid calculation of intersections

中图分类号:

TP391

池宝涛1,2;张见明1,2;鞠传明1,2. 基于仿射算术和区间运算的直线与NURBS曲线/曲面求交[J]. 中国机械工程.

CHI Baotao1,2;ZHANG Jianming1,2;JU Chuanming1,2. An Improved Fast Algorithm for Solving Intersections of Lines and NURBS Curves and Surfaces Using Interval Analysis with Affine Transform[J]. China Mechanical Engineering.

参考文献

[1]MOORE R E. Interval Analysis[M]. Englewood Clifs: Prentice Hall, 1966.
[2]PIEGL L, TILLER W. The NURBS Book[M]. Berlin: Springer Science & Business Media, 2012.
[3]NELLES O. Nonlinear System Identification: from Classical Approaches to Neural Networks and Fuzzy Models[M]. Berlin: Springer Science & Business Media, 2013.
[4]OWEN S J. An Introduction to Automatic Mesh Generation Algorithms—Part Ⅱ[R].Albuquerque: Sandia National Lab, 2016.
[5]CHEN J , XIAO Z , ZHENG Y, et al. Automatic Sizing Functions for Unstructured Surface Mesh Generation[J]. International Journal for Numerical Methods in Engineering, 2017, 109(4):577-608.
[6]DEVENDRA K E A . Guaranteed Ray Intersections with Implicit Surfaces[J]. ACM Siggraph Computer Graphics, 1989, 23(23):297-306.
[7]GOLDBERG P W, PAPADIMITRIOU C H, SAVANI R. The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions[J]. ACM Transactions on Economics and Computation, 2013, 1(2):9.
[8]PIRNIA M, CANIZARES C A, BHATTACHARYA K, et al. A Novel Affine Arithmetic Method to Solve Optimal Power Flow Problems with Uncertainties[J]. IEEE Transactions on Power Systems, 2014, 29(6):2775-2783.
[9]李庆扬, 莫孜中, 祁力群. 非线性方程组的数值解法[M] .北京:科学出版社, 1987.
LI Qingyang, MO Zizhong, QI Liqun. Numerical Methods for No-linear Systems of Equations[M]. Beijing: Science Press, 1987.
[10]KRAWCZYK R. A Class of Interval-newton-operators[J]. Computing, 1986, 37(2):179-183.
[11]NEUMAIER A, ZUHE S. The Krawczyk Operator and Kantorovich's Theorem[J]. Journal of Mathematical Analysis and Applications, 1990, 149(2):437-443.
[12]寿华好, 王国瑾, 沈杰. 区间算术和仿射算术的研究与应用[J].中国图象图形学报, 2006, 11(10): 1351-1358.
SHOU Huahao, WANG Guojin, SHEN Jie. A Survey on Research and Applications of Interval Arithmetic and Affine Arithmetic[J]. Journal of Image and Graphics Image Graph, 2006, 11(10): 1351-1358.
[13]王保庆, 张俐, 李东升. 逆向工程中 NURBS 曲面与直线交点快速计算[J]. 工程图学学报, 2010, 31(2): 149-152.
WANG Baoqing, ZHANG Li, LI Dongsheng. Rapid Calculation of Intersection Points between NURBS Surface and Line in Reverse Engineering [J]. Journal of Engineering Graphics, 2010, 31(2): 149-152.
[14]朱建宁, 王敏杰, 魏兆成,等. 直线与高精度细分曲面交点快速计算方法[J]. 大连理工大学学报, 2013(3):376-381.
ZHU Jianning, WANG Minjie, WEI Zhaocheng. Rapid Calculation of Intersection of Line and Catmull-Clark Surface[J]. Journal of Dalian University of Technology, 2013(3):376-381.
[15]官火梁, 吴强, 席平. RCS计算中NURBS曲面和射线求交的快速计算[J]. 工程图学学报, 2006, 27(1):87-91.
GUAN Huoliang, WU Qiang, XI Ping. A Fast Algorithm for Intersection Calculation of Ray and NURBS Surface in Predicting Radar Cross Section Calculation[J]. Journal of Engineering Graphics,2006, 27(1):87-91.