A Robust Algorithm for Computing the Intersection Curve of Two Algebraic Surfaces

Abstract

Computing the intersection curve of two surfaces is fundamental in CAD and geometric modeling but remains challenging because of degeneracy such as tangential intersection and the difficulty of recovering correct topology. Robustness is therefore essential for a reliable surface–surface intersection module. In this paper, we present a robust algorithm for intersecting two low-degree (less than or equal to four) algebraic surfaces common in geometric modeling (e.g., quadrics, toric surfaces, swept surfaces, and surfaces of revolution). The method projects the spatial intersection onto a plane and computes singular and critical points of the resulting planar algebraic curve using volume functions associated with the curve. Crucially, the exact number of singular and critical points is determined a priori, which guarantees correct planar topology in the subsequent tracing stage. The planar curve is traced starting from singular, boundary, and critical points until all components are recovered, and the traced components are lifted back to 3D using subresultant techniques to produce the spatial intersection. We verify our method using several examples, which contain degenerate cases such as tangency, and the results demonstrate the robustness of our algorithm. The proposed algorithm has the potential to solve the stability problem in low-degree algebraic surface intersection in geometric kernel.

Keywords

Algebraic surfaces / Surface/surfaces intersection / Volume function / Resultant / Singular point / Critical point / 65D17 / 68U07

References

[1] Bajaj CL, Hoffmann CM, Lynch RE, Hopcroft JEH. Tracing surface intersections. Comput. Aided Geom. Des., 1988, 54285307.

[2] Barnhill RE, Kersey SN. A marching method for parametric surface/surface intersection. Comput. Aided Geom. Des., 1990, 71257280.

[3] Berberich E, Emeliyanenko P, Kobel A, Sagraloff M. Exact symbolic–numeric computation of planar algebraic curves. Theoret. Comput. Sci., 2013, 491: 1-32.

[4] Briand, E., Rosas, M.: Milne’s volume function and vector symmetric polynomials. J. Symb. Comput. 44(5), 583–590 (2009). Spanish National Conference on Computer Algebra

[5] Busé L, Ba TL. The surface/surface intersection problem by means of matrix based representations. Comput. Aided Geom. Des., 2012, 298579598.

[6] Busé L, Elkadi M, Galligo A. Intersection and self-intersection of surfaces by means of Bezoutian matrices. Comput. Aided Geom. Des., 2008, 2525368.

[7] Chan, K.: A simple mathematical approach for determining intersection of quadratic surfaces, pp. 271–298 (06 2021)

[8] Changhe T, Wang W, Mourrain B, Wang J. Using signature sequences to classify intersection curves of two quadrics. Comput. Aided Geom. Des., 2009, 263317335.

[9] Chen F, Feng Y, Kozak J. Tracing a planar algebraic curve. Appl. Math. J. Chin. Univ., 1997, 12B: 15-24

[10] Cheng, Jin-San., Zhang, Bingwei, Xiao, Yikun, Li, Ming: Topology driven approximation to rational surface-surface intersection via interval algebraic topology analysis. ACM Trans. Graph. 42(4) (July 2023)

[11] Chu X, Li K, Jia X, Yang J, Kang J. Computing the intersection of two ellipsoids based on a fast algebraic topology determination strategy. Comput. Aided Geom. Des., 2025, 119. 102442

[12] Dokken T. Finding intersections of b-spline represented geometries using recursive subdivision techniques. Comput. Aided Geom. Des., 1985, 21189195.

[13] Dupont L, Lazard D, Lazard S, Petitjean S. Near-optimal parameterization of the intersection of quadrics: I. The generic algorithm. J. Symb. Comput., 2008, 433168191.

[14] Farouki RT, Neff C, O’Conner MA. Automatic parsing of degenerate quadric-surface intersections. ACM Trans. Graph., 1989, 83174203.

[15] Gao, Xiao-Shan., Li, Ming: Rational quadratic approximation to real algebraic curves. Comput. Aided Geom. Des. 21(8), 805–828 (2004). Geometric Modeling and Processing 2004

[16] Garrity T, Warren J. On computing the intersection of a pair of algebraic surfaces. Comput. Aided Geom. Des., 1989, 62137153.

[17] González-Vega, L., Recio, T., Lombardi, H., Roy, M.-F.: Sturm—habicht sequences, determinants and real roots of univariate polynomials. Quantifier Elimination and Cylindrical Algebraic Decomposition (1998)

[18] Gonzalez-Vega L, Necula I. Efficient topology determination of implicitly defined algebraic plane curves. Comput. Aided Geom. Des., 2002, 199719743.

[19] Gonzalez-Vega L, Trocado A. Tools for analyzing the intersection curve between two quadrics through projection and lifting. J. Comput. Appl. Math., 2021, 393. 113522

[20] Houghton EG, Emnett RF, Factor JD, Sabharwal CL. Implementation of a divide-and-conquer method for intersection of parametric surfaces. Comput. Aided Geom. Des., 1985, 21173183.

[21] Huang Y, Wang D. Computing intersection and self-intersection loci of parametrized surfaces using regular systems and Gröbner bases. Comput. Aided Geom. Des., 2011, 289566581.

[22] Jia X, Changhe T, Wang W. Topological classification of non-degenerate intersections of two ring tori. Comput. Aided Geom. Des., 2013, 302181198.

[23] Jin K, Cheng J. On the topology and isotopic meshing of plane algebraic curves. J. Syst. Sci. Complex., 2020, 331230260.

[24] Levin JZ. Mathematical models for determining the intersections of quadric surfaces. Comput. Graph. Image Process., 1979, 1117387.

[25] Manocha D, Canny J. A new approach for surface intersection. Int. J. Comput. Geom. Appl., 1991, 1: 209-219.

[26] Miller JR, Goldman RN. Geometric algorithms for detecting and calculating all conic sections in the intersection of any 2 natural quadric surfaces. Graph. Models Image Process., 1995, 5715566.

[27] Milne, P.S.: On the solutions of a set of polynomial equations

[28] Mukundan, H., Ko, K., Maekawa, T., Sakkalis, T., Patrikalakis, N.: Tracing surface intersections with validated ode system solver. ACM Symposium on Solid Modeling and Applications, SM, pp. 249–254 (2004)

[29] Sarraga RF. Algebraic methods for intersections of quadric surfaces in gmsolid. Comput. Vis. Graph. Image Process., 1983, 222222238.

[30] Sederberg, T.W., Chen, F.: Implicitization using moving curves and surfaces, pp. 301–308 (1995)

[31] Shao W, Chen F. Topological classification of the intersection curves of two quadrics using a set of discriminants. Comput. Aided Geom. Des., 2023, 107. 102244

[32] Shene C-K, Johnstone JK. On the lower degree intersections of two natural quadrics. ACM Trans. Graph., 1994, 134400424.

[33] Wang W, Joe B, Goldman R. Computing quadric surface intersections based on an analysis of plane cubic curves. Graph. Models, 2002, 646335367.

[34] Wang W, Goldman R, Changhe T. Enhancing levin’s method for computing quadric-surface intersections. Comput. Aided Geom. Des., 2003, 207401422.

[35] Wang X-Y, Shen L-Y, Yuan C-M, Pérez-Díaz S. Globally certified g1 approximation of planar algebraic curves. J. Comput. Appl. Math., 2024, 436. 115399

[36] Wilf I, Manor Y. Quadric-surface intersection curves: shape and structure. Comput. Aided Des., 1993, 2510633643.

[37] Yang, J., Jia, X., Yan, D.-M.: Topology guaranteed b-spline surface/surface intersection. ACM Trans. Graph. 42(6) (2023)

[38] Yao S, Jia X. Topological classification and determination of non-degenerate intersections of two dupin cyclides. Comput. Aided Des., 2022, 153. 103406

Rights & permissions

School of Mathematical Sciences, University of Science and Technology of China and Springer-Verlag GmbH Germany, part of Springer Nature