When two regular parametric surfaces intersect along a closed loop, a marching tracer must decide when it has completed exactly one non-overlapping traversal and may stop. Wu and Aléssio (SIBGRAPI 2001) proposed stopping when three numerical conditions hold — proximity of the current point to the start point within a tolerance, and agreement of the tangent and normal frames within the same tolerance — combined with a stack-based estimator of the rotation index (turning number) accumulated during the march. The authors acknowledged that this procedure has no general correctness proof and posed as future work either a formal proof of validity for all intersection geometries or a precise characterization of the geometric cases and tolerance regimes where it is valid. Their own 2005 journal version proved the rotation-index theory for regular closed curves with removable tangential self-intersections and branch points, but explicitly left open the regimes where distinct intersection components cross one another, where singular points have contact order greater than four, and where cusps or higher-order singularities occur. The surviving open core is the prove-or-characterize program for rotation-index-based termination of closed-loop intersection tracing.

Background

Computing the intersection of two surfaces (the surface–surface intersection, or SSI, problem) is a basic operation in computer-aided geometric design (CAGD): trimming, Boolean operations, and meshing of solid models all depend on it. For parametric surfaces S1(u,v)S_1(u,v) and S2(s,t)S_2(s,t), the intersection is generically a curve given only implicitly, as the solution set of S1(u,v)=S2(s,t)S_1(u,v)=S_2(s,t) in four parameters. Two families of algorithms dominate: subdivision methods, which recursively bisect parameter domains and prune subpatches that provably cannot intersect, and marching (or tracing) methods, which start from one point of the curve and propagate it step by step by predicting a new point near the current one and projecting it back onto the intersection (for example by Newton iteration). Marching is efficient but inherently local: when the intersection curve is a closed loop, the tracer eventually returns to its starting point and must recognize that the loop is complete, having traversed it exactly once without gaps or overlaps. Kriezis, Patrikalakis, and Wolter (1992) survey the topological and differential-equation machinery for this problem, including early loop-detection criteria; Grandine and Klein (1997) instead determine the number of intersection loops a priori by algebraic-topological means before tracing, a route later made robust in singular ('critical') cases by Hur, Oh, and Kim (2009) via perturbation. These global strategies complement rather than replace marching.

A purely numerical stop rule — stop when the current point is within a tolerance ϵ\epsilon of the start point — is unreliable: a curve that crosses itself, passes near the start point on another branch, or contains singular points can trigger a spurious stop, while stopping too late overlaps already traced segments. Wu and Aléssio (2001) attacked this with differential geometry. The rotation index (turning number) of a closed plane curve is the integer mm such that the tangent direction turns through exactly 2πm2\pi m over one traversal; a simple loop has ∣m∣=1|m|=1, a figure-eight has m=0m=0, and an mm-looped curve has ∣m∣=m|m|=m. The idea is to accumulate the signed turning of the tangent during the march and stop only when the accumulated angle is consistent with the estimated index mm. Estimating mm on the fly requires bookkeeping at singular events: a branch point is a self-intersection where the curve crosses itself; a tangential contact point is a self-contact where two parameter values share a tangent direction; the contact order at a singular point (related to the singularity-theoretic type AkA_k of the contact) measures how many derivatives of the two surface parametrizations agree there and controls how many branches meet and in which directions. The 2001 procedure detects candidate singular points by finding where the two surface normals become nearly parallel, refines them by Newton iteration on the four-equation intersection/parallel-normal system, classifies them with the discriminant D=b122−b11b22D=b_{12}^2-b_{11}b_{22} of the local quadratic form that governs branch directions (the classification of Ye and Maekawa (1999)), and maintains stacks of branch generators — for each singular point encountered, one recorded generator per branch of the curve emanating from it, carrying the point and that branch's tangent direction, used to relaunch tracing along each outgoing branch and to pair up re-encounters — to update the index estimate. The stopping test combines three inequalities: ∥P0Pn∥<ϵ\|P_0P_n\|<\epsilon (the traced point PnP_n is near the start P0P_0), 1−t(P0)⋅t(Pn)<ϵ1-t(P_0)\cdot t(P_n)<\epsilon and 1−n(P0)⋅n(Pn)<ϵ1-n(P_0)\cdot n(P_n)<\epsilon (the tangent and normal frames at PnP_n agree with those at P0P_0 up to the tolerance, written as dot-product deviations from 11), with the binormal check 1−b(P0)⋅b(Pn)<ϵ1-b(P_0)\cdot b(P_n)<\epsilon optional. The authors verified the procedure on six examples but stated that the stack rules are operational heuristics without a general proof, and posed as future work either a formal proof or a precise delimitation of the cases and tolerance regimes where the method is valid. The question is sharpened by the authors' own journal follow-ups (Wu and Aléssio 2002; Wu, Aléssio, and Costa 2005), which prove the rotation-index formulas for regular closed curves — including the removal of tangential pairs by regular homotopy, the index m−nm-n for simple crossings, and exterior-angle corrections at branch points of higher multiplicity — while documenting failure and gap regimes: intersections made of several curves that cross each other (which can leave unmatched branch generators on the stack), singular points of contact order greater than four (where the circular-step approximation of the marcher and Newton refinement can converge to the wrong branch), and cusps and other higher-order singularities. Practitioners' experience confirms the difficulty: Skytt (2006) lists branch points, tangential intersections, and marching that jumps branches among the open challenges of real CAD intersection code, and recent work — the certified-topology framework of Cheng, Zhang, Xiao, and Li (2023) for rational surfaces, the structure-extraction method of Bo, Liu, and Zhang (2024), and the overview of Li, Yang, and Jia (2026) — addresses degenerate SSI topology by subdivision, interval algebraic topology, and point-cloud reconstruction rather than by proving a marching stop rule correct.

Problem Statement

The object under study is the termination procedure of Wu and Aléssio (2001), as consolidated in the authors' 2005 journal version: a marching tracer for the intersection curve of two regular parametric surfaces S1S_1 and S2S_2 that (i) propagates points along the curve with a higher-order step and Newton projection; (ii) detects candidate singular points by near-parallel surface normals and refines them by Newton iteration on the four-equation intersection/parallel-normal system; (iii) classifies each singular point with the discriminant D=b122−b11b22D=b_{12}^2-b_{11}b_{22} of the local quadratic form governing branch directions; (iv) maintains stacks of branch generators (for each singular point encountered, one recorded generator per branch of the curve emanating from it, carrying the point and that branch's tangent direction, so that tracing can be relaunched along each outgoing branch and re-encounters paired) to incrementally estimate the rotation index mm of the traced loop; and (v) stops when the proximity and frame-agreement inequalities

∥P0Pn∥<ϵ,1−t(P0)⋅t(Pn)<ϵ,1−n(P0)⋅n(Pn)<ϵ\|P_0P_n\|<\epsilon,\qquad 1-t(P_0)\cdot t(P_n)<\epsilon,\qquad 1-n(P_0)\cdot n(P_n)<\epsilon

hold together with consistency of the accumulated tangent-angle sum with 2πm2\pi m (the binormal check 1−b(P0)⋅b(Pn)<ϵ1-b(P_0)\cdot b(P_n)<\epsilon optional), where ϵ\epsilon is a numerical tolerance and tt, nn, bb are the unit tangent, normal, and binormal of the intersection curve. The exact accumulated-angle consistency test (its threshold, sign convention, and 2π2\pi-branch bookkeeping) and the push/pop and pairing rules that maintain the estimate of mm on the branch-generator stacks are those defined in the cited papers; items (i)–(v) summarize the procedure whose correctness is at issue.

The problem is: either (a) prove that for every pair of regular parametric surfaces whose intersection contains closed loops, this procedure terminates after exactly one complete non-overlapping traversal of each traced loop with the correct topological count; or (b) precisely characterize the class of intersection geometries (component structure, self-crossings, inter-curve crossings, contact orders, singularity types) and tolerance regimes in which the procedure is guaranteed correct. The regimes that the authors' own journal follow-ups documented as unsettled — intersections where distinct component curves cross one another, leaving unmatched branch generators on the stack; singular points of contact order greater than four, where the circular-step approximation of the marcher and Newton refinement can converge to the wrong branch; and cusps and higher-order singularities outside the regular-curve rotation-index framework — together with the behavior of the tolerance ϵ\epsilon and of the discretization error of the accumulated turning angle, identify where a trust guarantee is currently missing and mark the territory any proof or characterization must confront; they are background to the question rather than a prescribed checklist of separately accepted components. The single scientific objective is a trust guarantee for closed-loop intersection tracing: a domain expert holding the submission must be able to decide, without redefining the question, for which geometries and tolerances the rotation-index stopping rule is provably reliable.

References

  1. Shin-Ting Wu and Osmar Aléssio, "Tracing along an intersection closed loop, when should one stop?", Proceedings XIV Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI 2001), IEEE, 2001, pp. 2–9. DOI 10.1109/SIBGRAPI.2001.963031, https://doi.org/10.1109/SIBGRAPI.2001.963031 (source of the open question)
  2. Shin-Ting Wu and Osmar Aléssio, "Complete and non-overlapping marching along a closed regular intersection curve", Computers & Graphics 26(6), 2002, pp. 853–864. DOI 10.1016/S0097-8493(02)00174-7, https://doi.org/10.1016/S0097-8493(02)00174-7
  3. Shin-Ting Wu, Osmar Aléssio, and Sueli I. R. Costa, "A complete and non-overlapping tracing algorithm for closed loops", Computer Aided Geometric Design 22(6), 2005, pp. 491–514. DOI 10.1016/j.cagd.2005.01.005, https://doi.org/10.1016/j.cagd.2005.01.005
  4. Xiuzi Ye and Takashi Maekawa, "Differential geometry of intersection curves of two surfaces", Computer Aided Geometric Design 16(8), 1999, pp. 767–788. DOI 10.1016/S0167-8396(99)00018-7, https://doi.org/10.1016/S0167-8396(99)00018-7
  5. Thomas A. Grandine and Frederick W. Klein, "A new approach to the surface intersection problem", Computer Aided Geometric Design 14(2), 1997, pp. 111–134. DOI 10.1016/S0167-8396(96)00024-6, https://doi.org/10.1016/S0167-8396(96)00024-6
  6. G. A. Kriezis, N. M. Patrikalakis, and F.-E. Wolter, "Topological and differential-equation methods for surface intersections", Computer-Aided Design 24(1), 1992, pp. 41–55. DOI 10.1016/0010-4485(92)90090-W, https://doi.org/10.1016/0010-4485(92)90090-W
  7. Seok Hur, Min-jae Oh, and Tae-wan Kim, "Classification and resolution of critical cases in Grandine and Klein's topology determination using a perturbation method", Computer Aided Geometric Design 26(2), 2009, pp. 243–258. DOI 10.1016/j.cagd.2008.03.003, https://doi.org/10.1016/j.cagd.2008.03.003
  8. Vibeke Skytt, "Challenges in Surface-Surface Intersections", in Computational Methods for Algebraic Spline Surfaces, Springer, 2006, pp. 11–26. DOI 10.1007/3-540-27157-0_2, https://doi.org/10.1007/3-540-27157-0_2
  9. Jin-San Cheng, Bingwei Zhang, Yikun Xiao, and Ming Li, "Topology driven approximation to rational surface-surface intersection via interval algebraic topology analysis", ACM Transactions on Graphics 42(4), 2023, pp. 1–16. DOI 10.1145/3592452, https://doi.org/10.1145/3592452
  10. Pengbo Bo, Qingxiang Liu, and Caiming Zhang, "Topological structure extraction for computing surface–surface intersection curves", The Visual Computer 41(5), 2025, pp. 3503–3518 (published online 2024). DOI 10.1007/s00371-024-03616-8, https://doi.org/10.1007/s00371-024-03616-8
  11. Kai Li, Jieyin Yang, and Xiaohong Jia, "Advances and challenges in surface–surface intersection computation — An overview", Computer-Aided Design 193, 2026, article 104039. DOI 10.1016/j.cad.2026.104039, https://doi.org/10.1016/j.cad.2026.104039
  12. Xiao-Ming Liu, Chang-Yuan Liu, Jun-Hai Yong, and Jean-Claude Paul, "Torus/Torus Intersection", Computer-Aided Design and Applications 8(3), 2011, pp. 465–477. DOI 10.3722/CADAPS.2011.465-477, https://doi.org/10.3722/CADAPS.2011.465-477
  13. Jing Zhu, Houjun Hang, Yongjian Cheng, Ping Guo, Yaling Wu, and Yongyan Sun, "Biparted Hyperboloid and Sphere Intersection Algorithm", 2022 4th International Conference on Pattern Recognition and Intelligent Systems (PRIS), 2022, pp. 32–35. DOI 10.1145/3549179.3549185, https://doi.org/10.1145/3549179.3549185