The framework of Ko and Ahn (2010) approximates a surface-to-surface intersection (SSI) curve by combining a validated ordinary differential equation (ODE) solver that traces the intersection with mathematically proved existence and uniqueness, explicit box-cover conditions (C1–C4) certifying that the approximate curve is topologically consistent with the exact one, and constrained optimization that refines the approximation inside validated enclosures. The authors themselves left the decisive extensions open: the pipeline was demonstrated only for transversal intersections of two Bézier surface pairs, recombines traced monotonic segments with only C0C^0 continuity, provides no systematic step-size policy for the interval-mapping stage, and its optimization stage is untested at scale. This problem asks for the coherent completion of that program: adapt and validate the tracing, certification, and refinement machinery for tangential intersections (where the standard marching direction vanishes and the governing ODEs change), achieve CnC^n (n≥1n\ge 1) continuity across segment joins inside the validated framework, and supply step-size bounds or automatic step control that provably maintain the topological cover conditions without repeated recomputation. No existing validated-ODE method certifies tangential contact of order two or higher.

Background

In computer-aided design (CAD) and solid modeling, the surface-to-surface intersection (SSI) curve is the curve along which two parametric surfaces (surfaces given by maps such as r(u,v)\mathbf{r}(u,v) from a parameter rectangle into 3D space, typically in B-spline or Bézier form — the standard piecewise-polynomial representations of CAD geometry) meet; it is the basic entity for trimming surfaces and producing watertight solid models. Computing it exactly is impractical: implicitizing the problem by function composition explodes the algebraic degree (a bicubic-vs-bicubic intersection already leads to very high-degree pre-image equations), so practical systems approximate the curve by a low-degree parametric spline. Two difficulties must be handled together. Numerically, a marching method can trace the curve by formulating it as an initial-value problem for a system of ODEs — an approach going back to Grandine and Klein (1997) — where the marching direction is the cross product of the two surface normals; but a conventional floating-point integrator offers no guarantee that the computed curve stays on the true branch or has the correct connectivity. Topologically, the approximate curve must be equivalent to the exact one (same endpoints, same knot type under an ambient homeomorphism, that is, a continuous invertible deformation of the surrounding space), otherwise trimming produces gaps or spurious components. Ko and Patrikalakis (2008) initiated a validated line: using interval arithmetic (arithmetic on ranges that rigorously enclose floating-point results) to obtain proved error bounds for SSI tracing. Ko and Ahn (2010) completed this into an end-to-end method: a validated ODE solver (the two-phase solver VNODE, whose first phase proves existence and uniqueness of a solution branch via a Picard–Lindelöf/Banach fixed-point argument and encloses it in a priori boxes), a theorem giving locally checkable conditions C1–C4 on a finite box cover of the curve that guarantee the approximate curve is ambiently homeomorphic to the exact one (via comparison with a pipe surface, the tube of fixed radius around the curve), and a final constrained optimization (L-BFGS-B, the bound-constrained variant of the low-memory BFGS quasi-Newton method) that moves the control points of the approximating spline to minimize its distance to the true intersection while keeping the points inside the validated enclosures. In this pipeline, a pre-processing step decomposes the intersection into monotonic segments — pieces between characteristic points (border, turning, and singular points) on which the curve is monotone with respect to a chosen parameter direction, so that a single marching pass traces each piece — and the traced segments are then recombined into the complete intersection curve with only C0C^0 (positional) continuity at the joins. A further interval-mapping step carries the a priori parameter-domain enclosures into 3D boxes by interval arithmetic; enclosure growth from derivative propagation and floating-point rounding can make boxes that are not consecutive along the curve overlap, violating the cover conditions, and the authors' remedy — reducing the step size and recomputing — carries no systematic guarantee. Tangential intersections — where the surfaces touch with parallel normals, so the normal cross product vanishes — were studied long before (Markot and Magedson 1989; Luo, Ma and McAllister 1995) and are a documented industrial bottleneck (Skytt 2005); there the marching direction must be derived from higher-order derivatives and the governing ODE system differs from the transversal case. A validated interval-ODE formulation for first-order tangential marching already exists in the source lineage (Mukundan et al. 2004), but that method could not evaluate contact of order two or higher and left the topological configuration of tangential contact curves out of scope. Concurrency is significant: Hur, Oh and Kim (2009) approximated SSI curves within a prescribed error bound satisfying continuity requirements by a non-validated method and likewise excluded tangential contact of order two or higher. The whole SSI area remains active precisely because guaranteed handling of tangential, near-tangential, and degenerate configurations is still not solved: recent systems either combine subdivision with interval algebraic topology analysis — configuring the local intersection topology inside four-dimensional interval boxes (Cheng et al. 2023, which handles tangent points and curves only up to singularity multiplicity two) — give topology guarantees for B-spline intersections without validated ODE certificates (Yang, Jia and Yan 2023), detect all branches including small loops and tangent intersections via winding numbers (Yang and Jia 2026), or improve watertightness of the two parametric-domain image curves through constrained optimization with gap control (Wang et al. 2025). None of these provides the validated existence/uniqueness tracing plus ambient-topology certification of the source framework, and higher-order tangential contact is open in all of them.

Problem Statement

Complete the validated, topologically certified framework of Ko and Ahn (2010) for approximating surface-to-surface intersection curves so that it covers the configurations and smoothness guarantees it currently excludes. Concretely, construct and validate an algorithm that: (1) traces tangential intersections — where the two surface normals are parallel, the standard marching direction (the normal cross product) vanishes, and the direction must be obtained from higher-order derivatives under a different ODE system — while retaining the validated existence/uniqueness phase wherever its hypotheses hold and extending that validated formulation to tangential contact of order two and higher, and extending the box-cover conditions C1–C4 of the source paper (locally checkable sufficient conditions on a finite box cover of the curve, proved there for regular transversal curves, that guarantee the approximate curve is ambiently homeomorphic to the exact one) so that the topological consistency of the approximation is still certified for tangential branches; at branch creation, branch annihilation, and isolated tangent points — configurations in which the exact intersection may cease to be a regular curve and the hypotheses of the original pipe-surface certificate may fail — the extended certification must still determine the correct topological behavior; (2) recombines the traced monotonic segments into a complete intersection-curve approximation whose joins attain parametric CnC^n continuity of the approximating spline for a proved order n≥1n\ge 1 — not merely C0C^0 — while control points remain inside the validated enclosures; and (3) provides systematic step-size bounds or an automatic step-control policy for the interval-mapping stage — computed a priori from certified interval data of the given surface pair (a per-instance guarantee), rather than by trial-and-error retries — that provably guarantees the cover conditions hold without repeated step-size reduction and recomputation, eliminating the spurious intersections among non-consecutive boxes caused by floating-point interval growth. Scalability of the constrained optimization refinement to very large control-point counts and intersection patterns with many segments and branches remains an auxiliary open aspect of the same pipeline, but it does not define the completion boundary of this problem, which is carried by items (1)–(3). The common objective uniting these deliverables is an end-to-end SSI approximation method that certifies both topological consistency and numerical accuracy over the full range of intersection configurations arising in CAD for which the exact intersection is a curve or an isolated tangent point — including tangential contact and isolated tangent points, and excluding coincident or partially coincident patches, where the exact intersection is two-dimensional and the framework's curve approximation and its ambient-homeomorphism certificate have no defined meaning — rather than only transversal intersections of simple Bézier pairs.

References

  1. Ko, K. H.; Ahn, H. S. (2010). Approximation of 3D surface-to-surface intersection curves. Engineering with Computers 26(1):49–60. DOI 10.1007/s00366-009-0133-6. https://doi.org/10.1007/s00366-009-0133-6 (source paper)
  2. Ko, K. H.; Patrikalakis, N. M. (2008). Analysis of validated error bounds of surface-to-surface intersection. Computer-Aided Design 40(3):273–280. DOI 10.1016/j.cad.2007.09.005. https://doi.org/10.1016/j.cad.2007.09.005
  3. Grandine, T. A.; Klein, F. W. (1997). A new approach to the surface intersection problem. Computer Aided Geometric Design 14(2):111–134. DOI 10.1016/S0167-8396(96)00024-6. https://doi.org/10.1016/S0167-8396(96)00024-6
  4. Markot, R. P.; Magedson, R. L. (1989). Solutions of tangential surface and curve intersections. Computer-Aided Design 21(7):421–427. DOI 10.1016/0010-4485(89)90126-7. https://doi.org/10.1016/0010-4485(89)90126-7
  5. Luo, R. C.; Ma, Y.; McAllister, D. F. (1995). Tracing tangential surface-surface intersections. In: Proceedings of the Third ACM Symposium on Solid Modeling and Applications, pp. 255–262. DOI 10.1145/218013.218070. https://doi.org/10.1145/218013.218070
  6. Huber, E.; Barth, W. (1999). Surface-to-surface intersection with complete and guaranteed results. In: Developments in Reliable Computing, pp. 189–202. DOI 10.1007/978-94-017-1247-7_15. https://doi.org/10.1007/978-94-017-1247-7_15
  7. Hur, S.; Oh, M.-jae; Kim, T.-wan (2009). Approximation of surface-to-surface intersection curves within a prescribed error bound satisfying continuity. Computer-Aided Design 41(1):37–46. DOI 10.1016/j.cad.2008.11.008. https://doi.org/10.1016/j.cad.2008.11.008
  8. Skytt, V. (2005). Challenges in Surface-Surface Intersections. In: Computational Methods for Algebraic Spline Surfaces, Springer, pp. 11–26. DOI 10.1007/3-540-27157-0_2. https://doi.org/10.1007/3-540-27157-0_2
  9. Park, Y.; Son, S.-H.; Kim, M.-S.; Elber, G. (2020). Surface–Surface-Intersection Computation Using a Bounding Volume Hierarchy with Osculating Toroidal Patches in the Leaf Nodes. Computer-Aided Design 127:102866. DOI 10.1016/j.cad.2020.102866. https://doi.org/10.1016/j.cad.2020.102866
  10. Cheng, J.-S.; Zhang, B.; Xiao, Y.; Li, M. (2023). Topology driven approximation to rational surface-surface intersection via interval algebraic topology analysis. ACM Transactions on Graphics 42(4):1–16. DOI 10.1145/3592452. https://doi.org/10.1145/3592452
  11. Yang, J.; Jia, X.; Yan, D.-M. (2023). Topology Guaranteed B-Spline Surface/Surface Intersection. ACM Transactions on Graphics 42(6):1–16. DOI 10.1145/3618349. https://doi.org/10.1145/3618349
  12. Wang, Y.; Jia, X.; Yang, J.; Wang, B.; Bo, P.; Liu, Y. (2025). Improving the Watertightness of Parametric Surface/Surface Intersection. Computer Graphics Forum, article e70298. DOI 10.1111/cgf.70298. https://doi.org/10.1111/cgf.70298
  13. Yang, J.; Jia, X. (2026). A Robust and Efficient Intersection Algorithm for NURBS Surfaces: Handling Small Loops and Tangent Intersections. ACM Transactions on Graphics 45(5):1–19. DOI 10.1145/3807948. https://doi.org/10.1145/3807948
  14. Mukundan, H.; Ko, K. H.; Maekawa, T.; Sakkalis, T.; Patrikalakis, N. M. (2004). Tracing surface intersections with a validated ODE system solver. In: Proceedings of the ACM Symposium on Solid Modeling and Applications (SPM 2004), pp. 249–254 (reference 12 of the source paper). Full text: https://diglib.eg.org/server/api/core/bitstreams/760c6104-646e-40c8-be52-f6e7437e5952/content