Park, Son, Kim, and Elber (Computer-Aided Design, 2020) introduced a surface–surface intersection (SSI) algorithm that precomputes a bounding volume hierarchy (BVH) for each freeform surface and stores, in every leaf node, an osculating toroidal patch — a trimmed torus segment with second-order contact to the surface — so that candidate intersecting patch pairs are found by cheap bounding-volume overlap tests and locally resolved by torus–torus intersection. The method handles near-tangential intersections far better than conventional subdivision, but its authors explicitly leave its reliability open: (1) no precise, tight bounding of tangential intersection areas exists, so near-tangential regimes generate millions of overlap-pair checks; (2) the acceptance test for the computed intersection curves is a sampling-based heuristic augmented by a classical derivative-bound correction (Filip–Magedson–Markot), not a rigorous, locally certified error estimator for the curves induced by the toroidal surrogates; and (3) no provable mechanism guarantees at least one seed point on every branch or loop, so a whole intersection component can be missed. The problem posed here is to supply these three certification results for the osculating-toroidal-patch BVH pipeline. A February 2026 field overview confirms that topologically consistent, error-controlled SSI remains a central open reliability problem for CAD systems; strong 2023–2026 results on topology guarantees and precision control by other machinery (subdivision, interval algebraic topology, winding numbers) do not discharge the toroidal-surrogate-specific certification.

Background

Computing the intersection curve of two parametric surfaces (the SSI problem) is a fundamental operation in computer-aided design (CAD): Boolean operations on boundary-represented solids, mesh generation, and numerical engineering analysis all depend on it. Modern CAD represents freeform shapes as B-spline or NURBS surface patches (piecewise rational polynomial parametric surfaces S(u,v)S(u,v)), and decades of SSI algorithms fall largely into two families: marching/tracing methods, which start from one point on each intersection component and trace it, and subdivision methods, which recursively split both surfaces until candidate patch pairs are small enough to resolve. Both families struggle when the surfaces meet tangentially — that is, with (nearly) parallel surface normals along the contact region — because the intersection degenerates from a clean transversal curve into extended patches of near-contact; subdivision pruning then loses efficiency (huge numbers of patch pairs look potentially overlapping) and tracing can miss entire components. A standard stress test is Heo–Kim–Elber's pair of almost-coaxial cylinders: as the angle θ\theta between the cylinder axes shrinks, subdivision methods first slightly miss and then completely miss the X-junctions (the crossing points where two intersection branches meet). The source paper of this candidate (Park, Son, Kim, Elber, 2020) attacks this regime with a precomputed data structure: each surface is sampled on a (1+2H)×(1+2H)(1+2H)\times(1+2H) grid, a bounding volume hierarchy (BVH — a tree of ever-tighter enclosing volumes; the paper compares axis-aligned boxes, rectangle-swept spheres called RSS, and convex hulls) is built once and stored compactly, and each leaf node carries an osculating toroidal patch. An osculating toroidal patch is a segment of a torus having second-order contact with the surface at a grid point (matching position, tangent plane, and principal curvatures), trimmed to the leaf's parameter cell, so it encloses the surface subpatch and — via the Gauss map, the spherical image of the surface normals — also bounds its normal directions. At query time the two BVHs are traversed to find all overlapping leaf pairs; for each pair the two toroidal patches are intersected (torus–torus intersection is algebraically tractable), producing candidate intersection segments represented as G1G^1-biarc splines (tangent-continuous piecewise-circular-arc curves) in both parameter domains. The accuracy of each accepted segment is then checked by a sampling test: squared point-to-surface distances d2(θk)d^2(\theta_k) are sampled along matched biarc arcs and increased by an error term η\eta derived from the classical derivative-based surface-approximation bound of Filip, Magedson, and Markot (1986); the pair passes when max⁡kd2(θk)+η<ϵ2\max_k d^2(\theta_k)+\eta<\epsilon^2. The method was demonstrated on the Grandine–Klein benchmark suite and on the coaxial-cylinder test down to θ=0.00002∘\theta=0.00002^\circ, where the osculating tori still recover the branching structure — but at the cost of more than five million overlapping leaf pairs, because near-tangency makes the bounding volumes overlap almost everywhere. The ideal tangential output regions are the surface subpatches lying within a one-sided Hausdorff distance δ\delta (a worst-case nearest-neighbor distance) of the other surface; the authors note that computing them exactly requires intersecting a surface with the ±δ\pm\delta-offset surfaces of the other, a problem they judge harder than ordinary SSI, and they instead approximate these areas by uniform sampling. Three limitations are left open in the paper itself: the tangential areas are not tightly bounded, the acceptance test is heuristic rather than a certified error bound, and — as the authors state in their discussion of robustness — a whole intersection loop can be missed 'by bad luck' if torus–torus intersection produces no seed point (p∗,v∗)(p^*,v^*) for it; they explicitly defer incorporating the completeness apparatus of subdivision-based methods ('such as ensuring at least one point on each branch or loop'). Meanwhile, the broader field has advanced on neighboring fronts: topology-guaranteed B-spline SSI (Yang–Jia–Yan, ACM TOG 2023), interval-algebraic-topology analysis of rational SSI including tangent points and tiny loops (Cheng et al., ACM TOG 2023), a priori precision control of NURBS SSI via Lipschitz/convex-hull Hausdorff bounds (Li et al., ACM TOG 2026), and winding-number-based detection of starting points on all branches including small loops and tangent intersections (Yang–Jia, ACM TOG 2026) — none of which, however, provides certified tangential-area bounding or error certificates for the toroidal-surrogate pipeline itself.

Problem Statement

Provide the certification results that Park–Son–Kim–Elber (2020) explicitly left open for their precomputed-BVH surface–surface-intersection scheme with osculating toroidal patches in the leaf nodes, so that the pipeline becomes certified in near-tangential and degenerate regimes. Concretely, take the admissible class to be the surface pairs (that is, ordered pairs of freeform parametric surface patches — B-spline/NURBS patches, with bicubic Bézier/B-spline as the representative case — intersected via the precomputed hierarchies of trimmed osculating toroidal patches) that exhibit the near-tangential and degenerate behavior the pipeline targets; the class covers both curve-like configurations (one-dimensional local intersections, from transversal contacts to tangential ones) and non-curve-like degenerate contacts (two-dimensional tangential contact patches and isolated point tangencies). For such a pair of surfaces SA(u,v)S_A(u,v) and SB(s,t)S_B(s,t), deliver: (1) a technique that bounds the tangential intersection areas precisely and tightly — i.e., for every user-prescribed one-sided Hausdorff tolerance δ>0\delta>0, a certified enclosure of the near-tangential contact region, understood as the surface subpatches within one-sided Hausdorff distance δ\delta of the other surface, such that the enclosure provably contains the true δ\delta-contact region and its excess over that region (measured in area or in one-sided Hausdorff distance) is bounded by an explicit quantity whose dependence on δ\delta, on the leaf resolution, and on the local curvature data is fully stated, and which is required to vanish in the refinement limit — that is, the excess must tend to zero as the leaf resolution is refined and δ→0\delta\to 0 jointly, so that the enclosure converges to the true δ\delta-contact region in that excess measure and a containment whose excess stays bounded away from zero in that limit (for instance the whole surface) does not satisfy this deliverable; (2) a rigorous, locally certified error estimator replacing the current sampling-based acceptance test: a computable bound, valid for the G1G^1-biarc intersection-curve segments induced by the toroidal surrogates of each overlapping leaf pair whose local intersection is curve-like (one-dimensional), on the deviation of those curves from the exact intersection curve of the original surfaces (the present test only samples d2(θk)d^2(\theta_k) along matched biarcs and adds a Filip-type correction η\eta, which bounds the distance of the computed curve to the other surface, without a certified local bound for the surrogate-induced curve against the exact intersection curve); configurations in which the intersection contains two-dimensional contact patches — the highly tangential regime in which, as the source paper's own experiments show, the output is given as surface subpatches or even as a whole surface — are to be detected and certified as tangential contact regions under deliverable (1), not as curves; and (3) a provable mechanism guaranteeing at least one seed (start) point on every branch and every loop of the intersection for every curve-like configuration in the admissible class just described. The three deliverables jointly certify reliability of this specific acceleration scheme: for every configuration in the admissible class defined above, each stated guarantee must hold. The acknowledged memory-footprint limit on maximum BVH resolution is a hardware engineering constraint and is not part of the problem.

References

  1. Youngjin Park, Sang-Hyun Son, Myung-Soo Kim, Gershon Elber, “Surface–Surface-Intersection Computation Using a Bounding Volume Hierarchy with Osculating Toroidal Patches in the Leaf Nodes”, Computer-Aided Design 127:102866 (2020). DOI 10.1016/j.cad.2020.102866, https://doi.org/10.1016/j.cad.2020.102866
  2. Daniel Filip, Robert Magedson, Robert Markot, “Surface algorithms using bounds on derivatives”, Computer Aided Geometric Design 3(4):295–311 (1986). DOI 10.1016/0167-8396(86)90005-1, https://doi.org/10.1016/0167-8396(86)90005-1
  3. Hee-Seok Heo, Myung-Soo Kim, Gershon Elber, “The intersection of two ruled surfaces”, Computer-Aided Design 31(1):33–50 (1999). DOI 10.1016/s0010-4485(98)00078-5, https://doi.org/10.1016/S0010-4485(98)00078-5
  4. Thomas A. Grandine, Frederick W. Klein, “A new approach to the surface intersection problem”, Computer Aided Geometric Design 14(2):111–134 (1997). DOI 10.1016/s0167-8396(96)00024-6, https://doi.org/10.1016/S0167-8396(96)00024-6
  5. Sang-Hyun Son, Myung-Soo Kim, Gershon Elber, “Precise Hausdorff distance computation for freeform surfaces based on computations with osculating toroidal patches”, Computer Aided Geometric Design 86:101967 (2021). DOI 10.1016/j.cagd.2021.101967, https://doi.org/10.1016/j.cagd.2021.101967
  6. Youngjin Park, Q Youn Hong, Myung-Soo Kim, Gershon Elber, “Self-intersection computation for freeform surfaces based on a regional representation scheme for miter points”, Computer Aided Geometric Design 86:101979 (2021). DOI 10.1016/j.cagd.2021.101979, https://doi.org/10.1016/j.cagd.2021.101979
  7. Kangmin Kim, Jinyoung Choi, Youngjin Park, “A new spatial data structure for triangular mesh with toroidal patches”, Journal of King Saud University – Computer and Information Sciences 36:101891 (2024). DOI 10.1016/j.jksuci.2023.101891, https://doi.org/10.1016/j.jksuci.2023.101891
  8. Minseok Kim, Youngjin Park, “Minimum distance computation for toroidal patch via topological classification”, Computer Aided Geometric Design 128:102570 (2026). DOI 10.1016/j.cagd.2026.102570, https://doi.org/10.1016/j.cagd.2026.102570
  9. Jieyin Yang, Xiaohong Jia, Dong-Ming Yan, “Topology Guaranteed B-Spline Surface/Surface Intersection”, ACM Transactions on Graphics 42(6):1–16 (2023). DOI 10.1145/3618349, https://doi.org/10.1145/3618349
  10. Jin-San Cheng, Bingwei Zhang, Yikun Xiao, Ming Li, “Topology driven approximation to rational surface-surface intersection via interval algebraic topology analysis”, ACM Transactions on Graphics 42(4):1–16 (2023). DOI 10.1145/3592452, https://doi.org/10.1145/3592452
  11. Pengbo Bo, Qingxiang Liu, Caiming Zhang, “Topological structure extraction for computing surface–surface intersection curves”, The Visual Computer 41(5):3503–3518 (2024). DOI 10.1007/s00371-024-03616-8, https://doi.org/10.1007/s00371-024-03616-8
  12. Bingwei Zhang, Jin-San Cheng, Yu-Shen Liu, Zhaoqi Zhang, “Topology guaranteed and error controlled curve tracing for parametric surface-surface intersection”, Computer Aided Geometric Design 118:102432 (2025). DOI 10.1016/j.cagd.2025.102432, https://doi.org/10.1016/j.cagd.2025.102432
  13. Yuqing Wang, Xiaohong Jia, Jieyin Yang, Bolun Wang, Pengbo Bo, Yang Liu, “Improving the Watertightness of Parametric Surface/Surface Intersection”, Computer Graphics Forum, article e70298 (2025). DOI 10.1111/cgf.70298, https://doi.org/10.1111/cgf.70298
  14. Xiao Chu, Kai Li, Xiaohong Jia, Jieyin Yang, Jiarui Kang, “Computing the intersection of two ellipsoids based on a fast algebraic topology determination strategy”, Computer Aided Geometric Design 119:102442 (2025). DOI 10.1016/j.cagd.2025.102442, https://doi.org/10.1016/j.cagd.2025.102442
  15. Gangyi Li, Xi Wu, Zhongxuan Luo, Lei Na, Jin-San Cheng, “A Precision Controlled Surface-Surface Intersection Algorithm for NURBS”, ACM Transactions on Graphics 45(5):1–14 (2026). DOI 10.1145/3806045, https://doi.org/10.1145/3806045
  16. Jieyin Yang, Xiaohong Jia, “A Robust and Efficient Intersection Algorithm for NURBS Surfaces: Handling Small Loops and Tangent Intersections”, ACM Transactions on Graphics 45(5):1–19 (2026). DOI 10.1145/3807948, https://doi.org/10.1145/3807948
  17. Chenming Gao, Hongwei Lin, Gengchen Li, “Topology Understanding of B-Spline Surface/Surface Intersection with Mapper”, arXiv:2604.12631 (2026). https://arxiv.org/abs/2604.12631
  18. Kai Li, Jieyin Yang, Xiaohong Jia, “Advances and challenges in surface–surface intersection computation — An overview”, Computer-Aided Design 193:104039 (2026). DOI 10.1016/j.cad.2026.104039, https://doi.org/10.1016/j.cad.2026.104039