基于圆环面片逼近的点投影与圆环面求交算法研究
|
摘要
圆环面是机械零件设计中常见的一种曲面，数控机床刀具的有效工作面有时也设计成圆环面，CAD/CAM系统中经常面临着圆环面和曲面的求交与距离计算问题。本文研究了两个圆环面的求交和距离计算以及基于圆环面片逼近的点投影算法，论文的主要工作如下：
提出了一种两圆环面的求交检测和距离计算的方法。首先证明了空间两圆的Hausdorf距离可以通过计算共线法向点获得。通过解一个一元八次方程，求出两圆的共线法向点，然后对共线法向点进行分类比较，得到两圆之间的最近距离和Hausdorf距离。接着，给出了两圆环相交、分离和包含三种位置关系的充分必要条件，证明了两个圆环面间的位置关系不仅与其大圆的最近距离有关，还与其大圆的单向Hausdorf距离有关，进而解决了两圆环面之间的最近距离计算问题，所有的计算过程都可实时完成。和已有的算法相比，本文算法的优点在于能够正确判断出一圆环完全被另一圆环包含的情形，并计算出它们的最近距离。
提出了一种两圆环面求交的算法。首先用隐式方程表示交线在一个圆环面参数空间的原像曲线，然后用特征点将原像曲线分割成多段单值函数曲线。接着对特征点进行拓扑分析，求得原像曲线的拓扑结构，最后用自适应的剖分方法求得满足给定精度要求的交线。和传统的跟踪法求交相比较，本文算法可以克服跟踪法的分支跳跃和小环遗漏的问题；生成的交线上的交点是解析法求得，精度高于跟踪法的数值迭代求精方法；传统的跟踪法只能用步长粗略控制交线的精度，而本文的自适应算法可以较准确地控制交线精度。
提出了一种用圆环面片逼近法求点到曲面投影的算法。研究了用圆环面片在局部逼近曲面的方法，在此基础上设计了一个二阶几何迭代算法求点到曲面的投影，每次迭代时，在曲面上的投影初值点处构建一个与原曲面二阶密切的圆环面片，将测试点投影到该圆环面片上，以求得下一次迭代初值。该方法既适用于参数曲面，也适用于隐式曲面，稳定性和效率都优于现有方法。
A torus is often used in the design of mechanical parts and the cutter heads ofnumerically controlled machine tools. It is needed to compute the intersection curvesor the minimum distance of a torus and a surface in CAD/CAM systems. This dis-sertation focuses on the computation of intersection and the minimum distance of twotori and point projection on surfaces based on torus patch approximation. The maincontributions are summarized as follows.
A method for the collision detection and the minimum distance computation be-tween two tori is presented. This dissertation proves that the Hausdorf distance be-tween two circles in three-dimensional space can be obtained by computing theircollinear normal points, which can be calculated by solving an equation of degreeeight. With classification and comparison of the collinear normal points, the minimumdistance and the Hausdorf distance between these two circles are obtained. This dis-sertation gives the sufcient and necessary conditions of the three types of positionrelationship (i.e. inclusion, disjunction and intersection) between two tori and provesthat position relationship between two tori relates to not only the minimum distancebut also the two directed Hausdorf distances between their major circles. And then theminimum distance between two tori is calculated. The method can be carried out inreal time. Compared with existing methods, the method has the advantage that it canmake correct judgement in the case of that a torus completely includes another torusand compute the distance between them.
An algorithm for torus/torus intersection is presented. The pre-image of the inter-section in the parametric space of one torus is represented by an implicit equation. Thepre-image is divided into one-valued function curve segments by characteristic points.The topological feature of these characteristic points is analyzed and the structure of thepre-image is obtained. Intersection curves satisfying required precision are generatedby a self-adaptive refinement method. Compared with the tracing method, the algo- rithm can overcome the drawbacks of straying and loop missing of the tracing method.Additionally, the points on the intersection curves obtained by the algorithm are com-puted by the analytic method, whose precision is higher than the points obtained byiteration when using the tracing method. The tracing method can only control theprecision roughly by estimating the advance step, while the algorithm can control theprecision accurately.
An algorithm for point projection on surfaces is presented. This dissertation pro-poses a local surface approximation method with a torus patch. Based on it, a secondorder geometric iteration algorithm for point projection on surfaces is proposed. Ineach iteration, a second order osculating torus patch to the surface at the previous pro-jection is constructed. Then the test point is projected onto the torus patch to computethe next projection. The algorithm can apply to not only parametric surfaces but alsoimplicit surfaces, and its stability and efciency are better than the existing methods.
提出了一种两圆环面的求交检测和距离计算的方法。首先证明了空间两圆的Hausdorf距离可以通过计算共线法向点获得。通过解一个一元八次方程，求出两圆的共线法向点，然后对共线法向点进行分类比较，得到两圆之间的最近距离和Hausdorf距离。接着，给出了两圆环相交、分离和包含三种位置关系的充分必要条件，证明了两个圆环面间的位置关系不仅与其大圆的最近距离有关，还与其大圆的单向Hausdorf距离有关，进而解决了两圆环面之间的最近距离计算问题，所有的计算过程都可实时完成。和已有的算法相比，本文算法的优点在于能够正确判断出一圆环完全被另一圆环包含的情形，并计算出它们的最近距离。
提出了一种两圆环面求交的算法。首先用隐式方程表示交线在一个圆环面参数空间的原像曲线，然后用特征点将原像曲线分割成多段单值函数曲线。接着对特征点进行拓扑分析，求得原像曲线的拓扑结构，最后用自适应的剖分方法求得满足给定精度要求的交线。和传统的跟踪法求交相比较，本文算法可以克服跟踪法的分支跳跃和小环遗漏的问题；生成的交线上的交点是解析法求得，精度高于跟踪法的数值迭代求精方法；传统的跟踪法只能用步长粗略控制交线的精度，而本文的自适应算法可以较准确地控制交线精度。
提出了一种用圆环面片逼近法求点到曲面投影的算法。研究了用圆环面片在局部逼近曲面的方法，在此基础上设计了一个二阶几何迭代算法求点到曲面的投影，每次迭代时，在曲面上的投影初值点处构建一个与原曲面二阶密切的圆环面片，将测试点投影到该圆环面片上，以求得下一次迭代初值。该方法既适用于参数曲面，也适用于隐式曲面，稳定性和效率都优于现有方法。
A torus is often used in the design of mechanical parts and the cutter heads ofnumerically controlled machine tools. It is needed to compute the intersection curvesor the minimum distance of a torus and a surface in CAD/CAM systems. This dis-sertation focuses on the computation of intersection and the minimum distance of twotori and point projection on surfaces based on torus patch approximation. The maincontributions are summarized as follows.
A method for the collision detection and the minimum distance computation be-tween two tori is presented. This dissertation proves that the Hausdorf distance be-tween two circles in three-dimensional space can be obtained by computing theircollinear normal points, which can be calculated by solving an equation of degreeeight. With classification and comparison of the collinear normal points, the minimumdistance and the Hausdorf distance between these two circles are obtained. This dis-sertation gives the sufcient and necessary conditions of the three types of positionrelationship (i.e. inclusion, disjunction and intersection) between two tori and provesthat position relationship between two tori relates to not only the minimum distancebut also the two directed Hausdorf distances between their major circles. And then theminimum distance between two tori is calculated. The method can be carried out inreal time. Compared with existing methods, the method has the advantage that it canmake correct judgement in the case of that a torus completely includes another torusand compute the distance between them.
An algorithm for torus/torus intersection is presented. The pre-image of the inter-section in the parametric space of one torus is represented by an implicit equation. Thepre-image is divided into one-valued function curve segments by characteristic points.The topological feature of these characteristic points is analyzed and the structure of thepre-image is obtained. Intersection curves satisfying required precision are generatedby a self-adaptive refinement method. Compared with the tracing method, the algo- rithm can overcome the drawbacks of straying and loop missing of the tracing method.Additionally, the points on the intersection curves obtained by the algorithm are com-puted by the analytic method, whose precision is higher than the points obtained byiteration when using the tracing method. The tracing method can only control theprecision roughly by estimating the advance step, while the algorithm can control theprecision accurately.
An algorithm for point projection on surfaces is presented. This dissertation pro-poses a local surface approximation method with a torus patch. Based on it, a secondorder geometric iteration algorithm for point projection on surfaces is proposed. Ineach iteration, a second order osculating torus patch to the surface at the previous pro-jection is constructed. Then the test point is projected onto the torus patch to computethe next projection. The algorithm can apply to not only parametric surfaces but alsoimplicit surfaces, and its stability and efciency are better than the existing methods.
引文
[1] de Boor C. A practical guide to splines. Berlin: Springer,1978.
[2] Farin G. Curves and surfaces for CAGD.5ed., San Francisco: Morgan Kaufmann,2002.
[3] Piegl L, Tiller W. The NURBS Book.2nd ed., Berlin, Heidelberg, New York: Springer-Verlag,1997.
[4]孙家广.计算机图形学（第3版）.北京:清华大学出版社,1998.
[5]唐荣锡. CAD/CAM技术.北京:北京航空航天大学出版社,1994.
[6]朱心雄.自由曲线曲面造型技术.北京:科学出版社,2000.
[7]施法中.计算机辅助几何设计与非均匀有理B样条.北京:高等教育出版社,2001.
[8] Patrikalakis N, Maekawa T. Shape Interrogation for Computer Aided Design and Manufac-turing. Berlin Heidelberg: Springer-Verlag,2002.
[9] Kim K J, Kim M S. Torus/sphere intersection based on a configuration space approach.Graphical Models and Image Processing,1998,60(1):77–92.
[10]陈小雕,雍俊海,郑国勤,等.圆环面/球面求交算法.计算机辅助设计与图形学学报,2005,17(6):1202–1206.
[11] Nef C. Finding the distance between two circles in three-dimensional space. IBM Journalof Research and Development,1990,34(5):770–775.
[12]倪炎榕,马登哲,张洪,等.圆环面刀具五坐标数控加工复杂曲面优化刀位算法.机械工程学报,2001,37(2):87–91.
[13] Aras E. Generating cutter swept envelopes in five-axis milling by two-parameter families ofspheres. Computer-Aided Design,2009,41(2):95–105.
[14] Hur S, Oh M, Kim T. Approximation of surface-to-surface intersection curves within aprescribed error bound satisfying G2continuity. Computer-Aided Design,2009,41(4):37–46.
[15] Kim S H, Ahn Y J. An approximation of circular arcs by quartic Bezier curves. Computer-Aided Design,2007,39(6):490–493.
[16] Huttenlocher D P, Klanderman G A, Rucklidge W J. Comparing images using the Haus-dorf distance. IEEE Transactions on Pattern Analysis and Machine Intelligence,1993,15(9):850–863.
[17] Son H J, Kim S H, Kim J S. Text image matching without language model using a Hausdorfdistance. Information Processing&Management,2008,44(3):1189–1200.
[18] Tan H C, Zhang Y J. Computing eigenface from edge images for face recognition based onHausdorf distance. Proceedings of the4th International Conference on Image and Graphics,2007.639–644.
[19] Lee Y H, Shim J C. Curvature based human face recognition using depth weighted Hausdorfdistance. Proceedings of International Conference of Image Processing, volume3,2004.1429–1432.
[20] Du C, Su G D. Improved line Segment Hausdorf distance for face recognition. Journal ofOptoelectronics Laser,2005,16(1):89–93.
[21] Gao Y S, Leung M K. Face recognition using line edge map. IEEE Transactions on PatternAnalysis and Machine Intelligence,2002,24(6):764–779.
[22] Natarajan S, Wong Y. Hausdorf distance for iris recognition. Proceedings of IEEE22ndInternational Symposium on Intelligent Control,2007.614–619.
[23] Li F, Leung M K. Palmprint identification using Hausdorf distance. Proceedings of IEEEInternational Workshop on Biomedical Circuits and Systems,2004. S3.3.5–S3.3.8.
[24] Alt H, Behrends B, Blomer J. Approximate matching of polygonal shapes. Annals ofMathematics and Articial Intelligence,1995,13(2):251–265.
[25] Scharf L. Computing the Hausdorf distance between sets of curves[M]. Berlin: FachbereichMathematik und Informatik, Freie Universita¨t, December,2003.
[26] Alt H, Scharf L. Computing the Hausdorf distance between sets of curves. Proceedings ofthe20th European Workshop on Computational Geometry (EWCG),2004.233–236.
[27] Elber G, Grandine T. Hausdorf and minimal distances between parametric freeforms inR2and R3. Proceedings of Lecture Notes In Computer Science, Hangzhou, China,2008.191–204.
[28] Belogay E, Cabrelli C, Molter U, et al. Calculating the Hausdorf distance between curves.Information Processing Letters,1997,64(1):17–22.
[29] Ju¨ttler B. Bounding the Hausdorf distance of implicitly defined and/or parametric curves.in: Mathematical Methods for Curves and Surfaces. Publisher Vanderbilt UniversityNashville, TN, USA,2000:223–232.
[30] Kim Y J, Oh Y T, Yoon S H, et al. Precise Hausdorf distance computation for pla-nar freeform curves using biarcs and depth bufer. The Visual Computer,2010,26(6-8):1007–1016.
[31] Bai Y B, Yong J H, Liu C Y, et al. Polyline approach for approximating Hausdorf distancebetween planar free-form curves. Computer-Aided Design,2011,43(6):687–698.
[32] Chen X D, Ma W Y, Xu G, et al. Computing the Hausdorf distance between two B-splinecurves. Computer Aided Design,2010,42(12):1197–1206.
[33]王日昀,宁涛,席平,等.圆环与圆环求交算法中初始点的计算.工程图学学报,2004,25(1):47–51.
[34] Almohamad H, Selim S Z. An algorithm for computing the distance between two circulardisks. Applied Mathematical Modelling,2003,27(2):115–124.
[35] Kim I S. An algorithm for finding the distance between two ellipses. CommunicationsKorean Mathematical Society,2006,21(3):559–567.
[36] Mantyla M. Introduction to Solid Modeling. Rockville, Maryland: Computer Science Press,1988.
[37] Chiyokura H. Solid modelling with designbase theory and implementation. Singapore:Addison-Wesley,1988.
[38] Hofman C. Geometric and Solid Modeling: An Introduction. San Mateo, California: MoranKaufmann Publishers, Inc.,1989.
[39] Requicha A A G. Representations for rigid solids: Therory, methods, and systems. ACMComputing Surveys,1980,12(4):437–464.
[40] Requicha A A G, Rossignac J R. Solid modeling and beyond. IEEE Computer Graphicsand Applications,1992,12(5):31–44.
[41] Levin J. Mathematical models for determining the intersections of quadric surfaces. Com-puter Graphics and Image Processing,1979,11(1):73–87.
[42] Sarraga R. Algebraic methods for intersections of quadric surfaces in GMSOLID. ComputerVision, Graphics, and Image Processing,1983,22(2):222–238.
[43] Sarraga R, Nef C, O’Conner M A. Automatic parsing of degenerate quadric-surface inter-sections. ACM Transactions on Graphics,1989,8(3):174–203.
[44] Wilf I, Manor Y. Quadric-surface intersection curves: shape and structure. Computer-AidedDesign,1993,25(10):633–643.
[45]陈小雕.二次曲线曲面间的位置关系[博士学位论文].北京:清华大学,2006.
[46] Tu C, Wang W, Wang J. Classifying the morphology of the nonsingular intersection curvesof two quadric surfaces. Proceedings of Geometric Modeling and Processing,2002.23–32.
[47] Dupont L, Lazard S, Lazard D, et al. Near-optimal parameterization of the intersection ofquadrics. Proceedings of ACM Symposium on Computational Geometry,2003.246–255.
[48] Tu C, Wang W, Mourrain B. Signature sequence of intersection curveof two quadrics for exact morphological classification. Technical re-port, Department of Computer Science, Hong Kong University,2005.http://www.csis.hku.hk/research/techreps/document/TR-2005-09.pdf.
[49] Tu C, Wang W, Mourrain B, et al. Using signature sequences to classify intersection curvesof two quadrics. Computer Aided Geometric Design,2009,26(3):317–335.
[50] Levin J. A parametric algorithm for drawing pictures of solid objects composed of quadrics.Communications of the ACM,1976,19(10):555–563.
[51] Geismann N, Hemmer M, Schoemer E. Computing a3-dimensional cell in an arrangementof quadrics: Exactly and Actually. Proceedings of ACM Symposium on ComputationalGeometry,2001.264–273.
[52] Wang W, Goldman R, Tu C. Enhancing Levin’s method for computing quadric-surfaceintersections. Computer Aided Geometric Design,2003,20(7):401–422.
[53] Johnstone J K, Shene C K. Computing the intersection of a plane and a natural quadric.Computers&Graphics,1992,16(2):179–186.
[54] Johnstone J K. A new intersection algorithm for cyclides and swept surfaces using circledecomposition. Computer Aided Geometric Design,1993,10(1):1–24.
[55] Heo H S, Hong S J, Seong J K, et al. The intersection of two ringed surfaces and somerelated problems. Graphical Models,2001,63(4):228–244.
[56] Miller J. Geometric approaches to non-planar quadric surface intersection curves. ACMTransactions on Graphics,1987,6(4):274–307.
[57] Miller J, Goldman R. Using tangent balls to find plane section of natural quadrics. IEEEComputer Graphics&Applications,1992,12(2):68–82.
[58] Miller J, Goldman R. Geometric algorithms for detecting and calculating all conic sec-tions in the intersection of any two natural quadric surfaces. Graphical Models and ImageProcessing,1995,57(1):55–66.
[59] Piegl L. Constructive method of intersecting natural quadrics represented in trimmed surfaceform. Computer-Aided Design,1989,21(4):79–82.
[60] Shene C, Johnstone J. On the lower degree intersections of two natural quadrics. ACMTransaction on Graphics,1994,13(4):400–424.
[61] Aziz N, Bata R, Bhat S. Bezier surface/surface intersection. IEEE Computer Graphics&Applications,1990,10(1):50–58.
[62] Bajaj C, Hofmann C. Tracing surface intersections. Computer Aided Geometric Design,1988,5(4):285–307.
[63] Barnhill R, Farin G, Jordan G, et al. Surface/surface intersection. Computer Aided Geomet-ric Design,1987,4(1-2):3–16.
[64] Barnhill R, Kersey S. A marching method for parametric surface/surface intersection. Com-puter Aided Geometric Design,1990,7(1-4):257–280.
[65] Kriezis G, Patrikalakis N, Wolter F E. Topological and diferential-equation methods forsurface intersections. Computer-Aided Design,1992,24(1):41–55.
[66] Wu S, Andrade L. Marching along a regular surface/surface intersection with circular steps.Computer Aided Geometric Design,1999,16(4):249–268.
[67] Wu S, Osmar A, Costa S. A complete and non-overlapping tracing algorithm for closedloops. Computer Aided Geometric Design,2005,22(6):491–514.
[68] Ma Y, Luo R. Topological method for loop detection of surface intersection problems.Computer-Aided Design,1995,27(11):811–820.
[69] Ma Y, Lee Y S. Detection of loops and singularities of surface intersections. Computer-Aided Design,1988,30(14):1059–1067.
[70] Sederberg T, Meyers R. Loop detection in surface patch intersections. Computer AidedGeometric Design,1988,5(2):161–171.
[71] Rossignac J R, Requicha A A G. Piecewise-circular curves for geometric modeling. IBMJournal of Research and Development,1987,31(3):296–313.
[72] Limaiem A, Trochu F. Geometric algorithms for the intersection of curves and surfaces.Computers and Graphics,1995,19(3):391–403.
[73] Patrikalakis N M. Surface-to-surface intersections. IEEE Computer Graphics and Applica-tions,1993,13(1):89–95.
[74]贺安辉.圆环求交双向跟踪法和交线点的均匀化[硕士学位论文].北京:清华大学,2009.
[75] Grandine T, Klein F. A new approach to the surface intersection problem. Computer AidedGeometric Design,1997,14(2):111–134.
[76] Hur S, Oh M, Kim T. Classification and resolution of critical cases in Grandine and Klein’stopology determination using a perturbation method. Computer Aided Geometric Design,2009,26(2):243–258.
[77]刘晓明,刘长远,胡强,等.计算两圆环面之间的最近距离.计算机辅助设计与图形学学报,2011,23(2):240–246.
[78]谌炎辉,徐武彬.采用“结式法”的圆环面和球面求交算法.工程图学学报,2007,28(3):61–66.
[79]庞新维,谌炎辉.基于坐标变换的圆环面/球面相交分析.广西工学院学报,2008,19(2):23–27.
[80] Pegna J, Wolter F E. Surface curve design by orthogonal projection of space curves ontofree-form surfaces. Journal of mechanical design,1996,118(1):45–52.
[81] Song H C, Yong J H, Yang Y J, et al. Algorithm for orthogonal projection of parametriccurves onto B-spline surfaces. Computer-Aided Design,2011,43(4):381–393.
[82] Besl P, McKay N. A method for registration of3-D shapes. IEEE Transactions on PatternAnalysis and Machine Intelligence,1992,14(2):239–256.
[83] Tucker T, Kurfess T. Newton methods for parametric surface registration. Part II. Experi-mental validation. Computer-Aided Design,2003,35(1):115–120.
[84] Pottmann H, Leopoldseder S, Hofer M. Registration without ICP. Computer Vision andImage Understanding,2004,95(1):54–71.
[85] Hu S M, Wallner J. A second order algorithm for orthogonal projection onto curves andsurfaces. Computer Aided Geometric Design,2005,22(3):251–260.
[86] Mortenson M. Geometric Modeling. New York: John Wiley&Sons,1985.
[87] Zhou J, Sherbrooke E, Patrikalakis N. Computation of stationary points of distance func-tions. Engineering with Computers,1993,9(4):231–246.
[88] Dyllong E, Luther W. Distance calculation between a point and a NURBS surface. Proceed-ings of Curve and Surface Design, Saint-Malo, France,1999.55–62.
[89] Piegl L, Tiller W. Parameterization for surface fitting in reverse engineering. Computer-Aided Design,2001,33(8):593–603.
[90] Johnson D, Cohen E. A framework for efcient minimum distance computation. Pro-ceedings of the1998IEEE Intemational Conference on Robotics&Automation, Leuven,Belgium,1998.
[91] Ma Y, Hewitt W. Point inversion and projection for NURBS curve and surface: Controlpolygon approach. Computer Aided Geometric Design,2003,20(2):79–99.
[92] Chen X D, Su H, Yong J H, et al. A counterexample on point inversion and projection forNURBS curve. Computer Aided Geometric Design,2007,24(5):302.
[93] Selimovic I. Improved algorithms for the projection of points on NURBS curves and sur-faces. Computer Aided Geometric Design,2006,23(5):439–445.
[94] Chen X D, Xu G, Yong J H, et al. Computing the minimum distance between a point and aclamped B-spline surface. Graphical Models,2009,71(3):107–112.
[95] Oh Y T, Kim Y J, Lee, et al. Efcient point projection to freeform curves and surfaces. Pro-ceedings of Advances in Geometric Modeling and Processing, Lecture Notes in ComputerScience, Castro Urdiales, Spain,2010.192–205.
[96] Xu J, Liu W, Wu J, et al. Geometric algorithm for point projection and inversion onto Be′ziersurfaces. Frontiers of Computer Science in China,2010,3(4):472–476.
[97] Hoschek J, Lasser D. Fundamentals of Computer Aided Geometric Design. Wellesley: A.K.Peters,1993.
[98] Hartmann E. On the curvature of curves and surfaces defined by normalforms. ComputerAided Geometric Design,1999,16(5):355–376.
[99] Forrest A R. Computational geometry. Proceedings of the Royal Society of London A,1971,321:187–195.
[100] Faux I, Pratt M. Computational geometry for design and manufacture. Chichester, England:Ellis Horwood,1981.
[101]徐国良. CAGD中的隐式曲线与曲面.数值计算与计算机应用,1997,(2):114–124.
[102] Sederberg T. Piecewise algebraic surface patches. Computer Aided Geometric Design,2(1):53–59.
[103] Patrikalakis N M, Kriezis G A. Representation of piecewise continuous algebraic surfacesin terms of B-splines. The Visual Computer,1993,5(6):360–373.
[104] Bajaj C, Chen J, Xu G. Modeling with cubic A-patches. ACM Transaction on Graphics,1995,14(2):103–133.
[105] Bajaj C, Xu G L. Piecewise rational approximations of real algebraic curves. Journal ofComputational Mathematics,1997,15(1):55–71.
[106] Gao X S, Li M. Rational quadratic approximation to real algebraic curves. Computer AidedGeometric Design,2004,21(8):805–828.
[107] Arau′jo B R, Jorge J A P. Adaptive polygonization of implicit surfaces. Computers&Graphics,2005,29(5):686–696.
[108] Tong W h, Kim T w. High-order approximation of implicit surfaces by G1triangular splinesurfaces. Computer-Aided Design,2009,41(6):441–455.
[109] Hartmann E. Numerical parameterization of curves and surfaces. Computer Aided Geomet-ric Design,2000,17(3):251–266.
[110] Alexa M, Adamson A. On normals and projection operators for surfaces defined by pointsets. Proceedings of Eurographics Symp. on Point-Based Graphics,2004.149–155.
[111]余正生,樊丰涛,王毅刚.点到隐式曲线曲面的最小距离.工程图学学报,2005,(5):74–79.
[112]徐海银,方雄兵,胡利安.点到隐式曲面的正交投影计算.计算机辅助设计与图形学学报,2008,20(12):1641–1647.
[113]方雄兵.点到隐式曲线、曲面的正交投影算法研究[硕士学位论文].武汉:华中科技大学,2008.
[114] Madsen K. A root-finding algorithm based on Newton’s method. BIT Numerical Mathe-matics,1973,13(1):71–75.
[115] Jenkins M A, Traub J F. A three-stage algorithm for real polynomials using quadratic it-eration. Society for Industrial and Applied Mathematics Journal (SIAM) on NumericalAnalysis,1970,7(4):545–566.
[116] Zidna A, Michel D. A two-steps algorithm for approximating real roots of a polynomial inBernstein basis. Mathematics and Computers in Simulation,2008,77(2-3):313–323.
[117] Ostrowski A M. Solution of equations and systems of equations. London: Academic Press.,1960.
[118] Lee K, Seong J K, Kim K J, et al. Minimum distance between two sphere-swept surfaces.Computer-Aided Design,2007,39(6):452–459.
[119] Peters T J, Stewart N, Ferguson D, et al. Algorithmic tolerances and semantics in dataexchange. Proceedings of the thirteenth annual symposium on Computational geometry,Nice, France,1997.403–405.
[120] Elber G, Kim M S. Geometric constraint solver using multivariate rational spline functions.Proceedings of the Sixth ACM Symposium on Solid Modeling and Applications, New York,United States,2001.
[121] Mourrain B, Pavone J. Subdivision methods for solving polynomial equations. Journal ofSymbolic Computation,2009,44(3):292–306.
[122] Walker R. Algebraic Curves. Princeton: Princeton University Press,1950.
[123] Goldman R. Curvature formulae for implicit curves and surfaces. Computer Aided Geo-metric Design,2005,22(7):632–658.
[124] Che W, Paul J C, Zhang X. Lines of curvature and umbilical points for implicit surfaces.Computer Aided Geometric Design,2007,24(7):395–409.
[2] Farin G. Curves and surfaces for CAGD.5ed., San Francisco: Morgan Kaufmann,2002.
[3] Piegl L, Tiller W. The NURBS Book.2nd ed., Berlin, Heidelberg, New York: Springer-Verlag,1997.
[4]孙家广.计算机图形学（第3版）.北京:清华大学出版社,1998.
[5]唐荣锡. CAD/CAM技术.北京:北京航空航天大学出版社,1994.
[6]朱心雄.自由曲线曲面造型技术.北京:科学出版社,2000.
[7]施法中.计算机辅助几何设计与非均匀有理B样条.北京:高等教育出版社,2001.
[8] Patrikalakis N, Maekawa T. Shape Interrogation for Computer Aided Design and Manufac-turing. Berlin Heidelberg: Springer-Verlag,2002.
[9] Kim K J, Kim M S. Torus/sphere intersection based on a configuration space approach.Graphical Models and Image Processing,1998,60(1):77–92.
[10]陈小雕,雍俊海,郑国勤,等.圆环面/球面求交算法.计算机辅助设计与图形学学报,2005,17(6):1202–1206.
[11] Nef C. Finding the distance between two circles in three-dimensional space. IBM Journalof Research and Development,1990,34(5):770–775.
[12]倪炎榕,马登哲,张洪,等.圆环面刀具五坐标数控加工复杂曲面优化刀位算法.机械工程学报,2001,37(2):87–91.
[13] Aras E. Generating cutter swept envelopes in five-axis milling by two-parameter families ofspheres. Computer-Aided Design,2009,41(2):95–105.
[14] Hur S, Oh M, Kim T. Approximation of surface-to-surface intersection curves within aprescribed error bound satisfying G2continuity. Computer-Aided Design,2009,41(4):37–46.
[15] Kim S H, Ahn Y J. An approximation of circular arcs by quartic Bezier curves. Computer-Aided Design,2007,39(6):490–493.
[16] Huttenlocher D P, Klanderman G A, Rucklidge W J. Comparing images using the Haus-dorf distance. IEEE Transactions on Pattern Analysis and Machine Intelligence,1993,15(9):850–863.
[17] Son H J, Kim S H, Kim J S. Text image matching without language model using a Hausdorfdistance. Information Processing&Management,2008,44(3):1189–1200.
[18] Tan H C, Zhang Y J. Computing eigenface from edge images for face recognition based onHausdorf distance. Proceedings of the4th International Conference on Image and Graphics,2007.639–644.
[19] Lee Y H, Shim J C. Curvature based human face recognition using depth weighted Hausdorfdistance. Proceedings of International Conference of Image Processing, volume3,2004.1429–1432.
[20] Du C, Su G D. Improved line Segment Hausdorf distance for face recognition. Journal ofOptoelectronics Laser,2005,16(1):89–93.
[21] Gao Y S, Leung M K. Face recognition using line edge map. IEEE Transactions on PatternAnalysis and Machine Intelligence,2002,24(6):764–779.
[22] Natarajan S, Wong Y. Hausdorf distance for iris recognition. Proceedings of IEEE22ndInternational Symposium on Intelligent Control,2007.614–619.
[23] Li F, Leung M K. Palmprint identification using Hausdorf distance. Proceedings of IEEEInternational Workshop on Biomedical Circuits and Systems,2004. S3.3.5–S3.3.8.
[24] Alt H, Behrends B, Blomer J. Approximate matching of polygonal shapes. Annals ofMathematics and Articial Intelligence,1995,13(2):251–265.
[25] Scharf L. Computing the Hausdorf distance between sets of curves[M]. Berlin: FachbereichMathematik und Informatik, Freie Universita¨t, December,2003.
[26] Alt H, Scharf L. Computing the Hausdorf distance between sets of curves. Proceedings ofthe20th European Workshop on Computational Geometry (EWCG),2004.233–236.
[27] Elber G, Grandine T. Hausdorf and minimal distances between parametric freeforms inR2and R3. Proceedings of Lecture Notes In Computer Science, Hangzhou, China,2008.191–204.
[28] Belogay E, Cabrelli C, Molter U, et al. Calculating the Hausdorf distance between curves.Information Processing Letters,1997,64(1):17–22.
[29] Ju¨ttler B. Bounding the Hausdorf distance of implicitly defined and/or parametric curves.in: Mathematical Methods for Curves and Surfaces. Publisher Vanderbilt UniversityNashville, TN, USA,2000:223–232.
[30] Kim Y J, Oh Y T, Yoon S H, et al. Precise Hausdorf distance computation for pla-nar freeform curves using biarcs and depth bufer. The Visual Computer,2010,26(6-8):1007–1016.
[31] Bai Y B, Yong J H, Liu C Y, et al. Polyline approach for approximating Hausdorf distancebetween planar free-form curves. Computer-Aided Design,2011,43(6):687–698.
[32] Chen X D, Ma W Y, Xu G, et al. Computing the Hausdorf distance between two B-splinecurves. Computer Aided Design,2010,42(12):1197–1206.
[33]王日昀,宁涛,席平,等.圆环与圆环求交算法中初始点的计算.工程图学学报,2004,25(1):47–51.
[34] Almohamad H, Selim S Z. An algorithm for computing the distance between two circulardisks. Applied Mathematical Modelling,2003,27(2):115–124.
[35] Kim I S. An algorithm for finding the distance between two ellipses. CommunicationsKorean Mathematical Society,2006,21(3):559–567.
[36] Mantyla M. Introduction to Solid Modeling. Rockville, Maryland: Computer Science Press,1988.
[37] Chiyokura H. Solid modelling with designbase theory and implementation. Singapore:Addison-Wesley,1988.
[38] Hofman C. Geometric and Solid Modeling: An Introduction. San Mateo, California: MoranKaufmann Publishers, Inc.,1989.
[39] Requicha A A G. Representations for rigid solids: Therory, methods, and systems. ACMComputing Surveys,1980,12(4):437–464.
[40] Requicha A A G, Rossignac J R. Solid modeling and beyond. IEEE Computer Graphicsand Applications,1992,12(5):31–44.
[41] Levin J. Mathematical models for determining the intersections of quadric surfaces. Com-puter Graphics and Image Processing,1979,11(1):73–87.
[42] Sarraga R. Algebraic methods for intersections of quadric surfaces in GMSOLID. ComputerVision, Graphics, and Image Processing,1983,22(2):222–238.
[43] Sarraga R, Nef C, O’Conner M A. Automatic parsing of degenerate quadric-surface inter-sections. ACM Transactions on Graphics,1989,8(3):174–203.
[44] Wilf I, Manor Y. Quadric-surface intersection curves: shape and structure. Computer-AidedDesign,1993,25(10):633–643.
[45]陈小雕.二次曲线曲面间的位置关系[博士学位论文].北京:清华大学,2006.
[46] Tu C, Wang W, Wang J. Classifying the morphology of the nonsingular intersection curvesof two quadric surfaces. Proceedings of Geometric Modeling and Processing,2002.23–32.
[47] Dupont L, Lazard S, Lazard D, et al. Near-optimal parameterization of the intersection ofquadrics. Proceedings of ACM Symposium on Computational Geometry,2003.246–255.
[48] Tu C, Wang W, Mourrain B. Signature sequence of intersection curveof two quadrics for exact morphological classification. Technical re-port, Department of Computer Science, Hong Kong University,2005.http://www.csis.hku.hk/research/techreps/document/TR-2005-09.pdf.
[49] Tu C, Wang W, Mourrain B, et al. Using signature sequences to classify intersection curvesof two quadrics. Computer Aided Geometric Design,2009,26(3):317–335.
[50] Levin J. A parametric algorithm for drawing pictures of solid objects composed of quadrics.Communications of the ACM,1976,19(10):555–563.
[51] Geismann N, Hemmer M, Schoemer E. Computing a3-dimensional cell in an arrangementof quadrics: Exactly and Actually. Proceedings of ACM Symposium on ComputationalGeometry,2001.264–273.
[52] Wang W, Goldman R, Tu C. Enhancing Levin’s method for computing quadric-surfaceintersections. Computer Aided Geometric Design,2003,20(7):401–422.
[53] Johnstone J K, Shene C K. Computing the intersection of a plane and a natural quadric.Computers&Graphics,1992,16(2):179–186.
[54] Johnstone J K. A new intersection algorithm for cyclides and swept surfaces using circledecomposition. Computer Aided Geometric Design,1993,10(1):1–24.
[55] Heo H S, Hong S J, Seong J K, et al. The intersection of two ringed surfaces and somerelated problems. Graphical Models,2001,63(4):228–244.
[56] Miller J. Geometric approaches to non-planar quadric surface intersection curves. ACMTransactions on Graphics,1987,6(4):274–307.
[57] Miller J, Goldman R. Using tangent balls to find plane section of natural quadrics. IEEEComputer Graphics&Applications,1992,12(2):68–82.
[58] Miller J, Goldman R. Geometric algorithms for detecting and calculating all conic sec-tions in the intersection of any two natural quadric surfaces. Graphical Models and ImageProcessing,1995,57(1):55–66.
[59] Piegl L. Constructive method of intersecting natural quadrics represented in trimmed surfaceform. Computer-Aided Design,1989,21(4):79–82.
[60] Shene C, Johnstone J. On the lower degree intersections of two natural quadrics. ACMTransaction on Graphics,1994,13(4):400–424.
[61] Aziz N, Bata R, Bhat S. Bezier surface/surface intersection. IEEE Computer Graphics&Applications,1990,10(1):50–58.
[62] Bajaj C, Hofmann C. Tracing surface intersections. Computer Aided Geometric Design,1988,5(4):285–307.
[63] Barnhill R, Farin G, Jordan G, et al. Surface/surface intersection. Computer Aided Geomet-ric Design,1987,4(1-2):3–16.
[64] Barnhill R, Kersey S. A marching method for parametric surface/surface intersection. Com-puter Aided Geometric Design,1990,7(1-4):257–280.
[65] Kriezis G, Patrikalakis N, Wolter F E. Topological and diferential-equation methods forsurface intersections. Computer-Aided Design,1992,24(1):41–55.
[66] Wu S, Andrade L. Marching along a regular surface/surface intersection with circular steps.Computer Aided Geometric Design,1999,16(4):249–268.
[67] Wu S, Osmar A, Costa S. A complete and non-overlapping tracing algorithm for closedloops. Computer Aided Geometric Design,2005,22(6):491–514.
[68] Ma Y, Luo R. Topological method for loop detection of surface intersection problems.Computer-Aided Design,1995,27(11):811–820.
[69] Ma Y, Lee Y S. Detection of loops and singularities of surface intersections. Computer-Aided Design,1988,30(14):1059–1067.
[70] Sederberg T, Meyers R. Loop detection in surface patch intersections. Computer AidedGeometric Design,1988,5(2):161–171.
[71] Rossignac J R, Requicha A A G. Piecewise-circular curves for geometric modeling. IBMJournal of Research and Development,1987,31(3):296–313.
[72] Limaiem A, Trochu F. Geometric algorithms for the intersection of curves and surfaces.Computers and Graphics,1995,19(3):391–403.
[73] Patrikalakis N M. Surface-to-surface intersections. IEEE Computer Graphics and Applica-tions,1993,13(1):89–95.
[74]贺安辉.圆环求交双向跟踪法和交线点的均匀化[硕士学位论文].北京:清华大学,2009.
[75] Grandine T, Klein F. A new approach to the surface intersection problem. Computer AidedGeometric Design,1997,14(2):111–134.
[76] Hur S, Oh M, Kim T. Classification and resolution of critical cases in Grandine and Klein’stopology determination using a perturbation method. Computer Aided Geometric Design,2009,26(2):243–258.
[77]刘晓明,刘长远,胡强,等.计算两圆环面之间的最近距离.计算机辅助设计与图形学学报,2011,23(2):240–246.
[78]谌炎辉,徐武彬.采用“结式法”的圆环面和球面求交算法.工程图学学报,2007,28(3):61–66.
[79]庞新维,谌炎辉.基于坐标变换的圆环面/球面相交分析.广西工学院学报,2008,19(2):23–27.
[80] Pegna J, Wolter F E. Surface curve design by orthogonal projection of space curves ontofree-form surfaces. Journal of mechanical design,1996,118(1):45–52.
[81] Song H C, Yong J H, Yang Y J, et al. Algorithm for orthogonal projection of parametriccurves onto B-spline surfaces. Computer-Aided Design,2011,43(4):381–393.
[82] Besl P, McKay N. A method for registration of3-D shapes. IEEE Transactions on PatternAnalysis and Machine Intelligence,1992,14(2):239–256.
[83] Tucker T, Kurfess T. Newton methods for parametric surface registration. Part II. Experi-mental validation. Computer-Aided Design,2003,35(1):115–120.
[84] Pottmann H, Leopoldseder S, Hofer M. Registration without ICP. Computer Vision andImage Understanding,2004,95(1):54–71.
[85] Hu S M, Wallner J. A second order algorithm for orthogonal projection onto curves andsurfaces. Computer Aided Geometric Design,2005,22(3):251–260.
[86] Mortenson M. Geometric Modeling. New York: John Wiley&Sons,1985.
[87] Zhou J, Sherbrooke E, Patrikalakis N. Computation of stationary points of distance func-tions. Engineering with Computers,1993,9(4):231–246.
[88] Dyllong E, Luther W. Distance calculation between a point and a NURBS surface. Proceed-ings of Curve and Surface Design, Saint-Malo, France,1999.55–62.
[89] Piegl L, Tiller W. Parameterization for surface fitting in reverse engineering. Computer-Aided Design,2001,33(8):593–603.
[90] Johnson D, Cohen E. A framework for efcient minimum distance computation. Pro-ceedings of the1998IEEE Intemational Conference on Robotics&Automation, Leuven,Belgium,1998.
[91] Ma Y, Hewitt W. Point inversion and projection for NURBS curve and surface: Controlpolygon approach. Computer Aided Geometric Design,2003,20(2):79–99.
[92] Chen X D, Su H, Yong J H, et al. A counterexample on point inversion and projection forNURBS curve. Computer Aided Geometric Design,2007,24(5):302.
[93] Selimovic I. Improved algorithms for the projection of points on NURBS curves and sur-faces. Computer Aided Geometric Design,2006,23(5):439–445.
[94] Chen X D, Xu G, Yong J H, et al. Computing the minimum distance between a point and aclamped B-spline surface. Graphical Models,2009,71(3):107–112.
[95] Oh Y T, Kim Y J, Lee, et al. Efcient point projection to freeform curves and surfaces. Pro-ceedings of Advances in Geometric Modeling and Processing, Lecture Notes in ComputerScience, Castro Urdiales, Spain,2010.192–205.
[96] Xu J, Liu W, Wu J, et al. Geometric algorithm for point projection and inversion onto Be′ziersurfaces. Frontiers of Computer Science in China,2010,3(4):472–476.
[97] Hoschek J, Lasser D. Fundamentals of Computer Aided Geometric Design. Wellesley: A.K.Peters,1993.
[98] Hartmann E. On the curvature of curves and surfaces defined by normalforms. ComputerAided Geometric Design,1999,16(5):355–376.
[99] Forrest A R. Computational geometry. Proceedings of the Royal Society of London A,1971,321:187–195.
[100] Faux I, Pratt M. Computational geometry for design and manufacture. Chichester, England:Ellis Horwood,1981.
[101]徐国良. CAGD中的隐式曲线与曲面.数值计算与计算机应用,1997,(2):114–124.
[102] Sederberg T. Piecewise algebraic surface patches. Computer Aided Geometric Design,2(1):53–59.
[103] Patrikalakis N M, Kriezis G A. Representation of piecewise continuous algebraic surfacesin terms of B-splines. The Visual Computer,1993,5(6):360–373.
[104] Bajaj C, Chen J, Xu G. Modeling with cubic A-patches. ACM Transaction on Graphics,1995,14(2):103–133.
[105] Bajaj C, Xu G L. Piecewise rational approximations of real algebraic curves. Journal ofComputational Mathematics,1997,15(1):55–71.
[106] Gao X S, Li M. Rational quadratic approximation to real algebraic curves. Computer AidedGeometric Design,2004,21(8):805–828.
[107] Arau′jo B R, Jorge J A P. Adaptive polygonization of implicit surfaces. Computers&Graphics,2005,29(5):686–696.
[108] Tong W h, Kim T w. High-order approximation of implicit surfaces by G1triangular splinesurfaces. Computer-Aided Design,2009,41(6):441–455.
[109] Hartmann E. Numerical parameterization of curves and surfaces. Computer Aided Geomet-ric Design,2000,17(3):251–266.
[110] Alexa M, Adamson A. On normals and projection operators for surfaces defined by pointsets. Proceedings of Eurographics Symp. on Point-Based Graphics,2004.149–155.
[111]余正生,樊丰涛,王毅刚.点到隐式曲线曲面的最小距离.工程图学学报,2005,(5):74–79.
[112]徐海银,方雄兵,胡利安.点到隐式曲面的正交投影计算.计算机辅助设计与图形学学报,2008,20(12):1641–1647.
[113]方雄兵.点到隐式曲线、曲面的正交投影算法研究[硕士学位论文].武汉:华中科技大学,2008.
[114] Madsen K. A root-finding algorithm based on Newton’s method. BIT Numerical Mathe-matics,1973,13(1):71–75.
[115] Jenkins M A, Traub J F. A three-stage algorithm for real polynomials using quadratic it-eration. Society for Industrial and Applied Mathematics Journal (SIAM) on NumericalAnalysis,1970,7(4):545–566.
[116] Zidna A, Michel D. A two-steps algorithm for approximating real roots of a polynomial inBernstein basis. Mathematics and Computers in Simulation,2008,77(2-3):313–323.
[117] Ostrowski A M. Solution of equations and systems of equations. London: Academic Press.,1960.
[118] Lee K, Seong J K, Kim K J, et al. Minimum distance between two sphere-swept surfaces.Computer-Aided Design,2007,39(6):452–459.
[119] Peters T J, Stewart N, Ferguson D, et al. Algorithmic tolerances and semantics in dataexchange. Proceedings of the thirteenth annual symposium on Computational geometry,Nice, France,1997.403–405.
[120] Elber G, Kim M S. Geometric constraint solver using multivariate rational spline functions.Proceedings of the Sixth ACM Symposium on Solid Modeling and Applications, New York,United States,2001.
[121] Mourrain B, Pavone J. Subdivision methods for solving polynomial equations. Journal ofSymbolic Computation,2009,44(3):292–306.
[122] Walker R. Algebraic Curves. Princeton: Princeton University Press,1950.
[123] Goldman R. Curvature formulae for implicit curves and surfaces. Computer Aided Geo-metric Design,2005,22(7):632–658.
[124] Che W, Paul J C, Zhang X. Lines of curvature and umbilical points for implicit surfaces.Computer Aided Geometric Design,2007,24(7):395–409.