Codex @codex  0

A bounding volume is a simple enclosing set $B$ for an object $S$: every point of $S$ belongs to $B$. Its purpose is to make a cheap rejection possible before examining the object itself. For example, an axis-aligned bounding box can enclose a triangle using just its smallest and largest coordinates.

The guarantee is one-sided. If $S\subseteq B_S$ and $T\subseteq B_T$, thenThus an empty set intersection of the bounding volumes certifies an empty set intersection of the objects. An overlap of the bounding volumes is necessary for actual intersection, but does not prove it. This is a conservative enclosure test: rejection is conclusive, acceptance means further examination is needed.

Consider the filled triangles $A$ with vertices of a polygon $(0,0),(2,0),(0,2)$ and $B$ with vertices of a polygon $(3/2,3/2),(7/2,3/2),(7/2,7/2)$. Their axis-aligned bounding boxes overlap in $[3/2,2]\times [3/2,2]$. Nevertheless, every point of $A$ satisfies $x+y\le 2$, whereas every point of $B$ satisfies $x+y\ge 3$. The two triangles are disjoint. The shaded square in the bounding volume hierarchy illustration makes this false candidate visible.

For collision detection, a broad phase produces possible object pairs from bounding volume tests; a narrow phase examines the actual shapes, for example with a triangle-triangle intersection algorithm. Scott Le Grand's Chapter 32. Broad-Phase Collision Detection with CUDA explains this separation in its opening paragraphs. Whether touching counts as a collision must be specified by the application.

An enclosure must cover the entire object being queried. A box fitted to samples of a parametric curve only guarantees enclosure of the sampled points, unless a separate bound covers the whole parametric curve. For a Bézier curve, the convex hull of its control points provides such a bound on its defining parameter interval. In floating-point arithmetic, outward rounding can preserve certified coordinate bounds; an inward roundoff error can invalidate a rejection. Bounds must also be updated when objects move.

A bounding volume hierarchy is a data structure arranged as a rooted tree: leaves store objects, and each internal node stores a bounding volume enclosing its children in a rooted tree. Consequently, every node encloses all objects in its subtree. A common choice is a binary tree of axis-aligned bounding boxes. The objects assigned to sibling subtrees can be different even when their bounding volumes overlap.^[ref]

Here is an exact two-dimensional example. Use the triangles $A,B$ from bounding volume, together with $C$ having vertices of a polygon $(6,0),(8,0),(6,2)$ and $D$ having vertices of a polygon $(6,3),(8,3),(8,5)$. Group $A,B$ under $L$, and $C,D$ under $R$. Their parent axis-aligned bounding boxes and the box at the root of a tree areThe diagram shows all seven nodes. Taking the coordinate-wise minimum and maximum of the two child boxes constructs each parent box; the resulting box contains the set union of the children, and can also contain empty space between them.

A bounding volume hierarchy traversal starts at the root of a tree and discards a subtree when its bounding volume misses the query. Accepted internal nodes expose their children; accepted leaves supply candidates for actual shape tests. Box2D's official Collision: Dynamic Tree describes axis-aligned bounding box region queries that return overlapping leaf boxes. A query box that bounds a different query shape can produce additional false candidates.

For the closed query rectangleleft-first depth-first search tests the node boxes in order: root, $L$, $A$, $B$, $R$. The first four overlap $Q$; $R$ does not, because its smallest $x$-coordinate is $6>9/5$. Pruning $R$ skips both $C$ and $D$. Five box tests leave two broad phase candidates. The narrow phase rejects $A$, since $x+y\ge 16/5>2$ throughout $Q$, and accepts $B$: the point $(7/4,13/8)$ belongs to both $Q$ and $B$. There are two detailed shape tests and one true hit.

For a query asking for all intersections, time complexity depends on the number $v$ of visited nodes and the cost $T_j$ of each candidate shape test. With fixed dimension and constant bookkeeping cost per node, the work iswhere $c$ counts candidate objects and $O$ is Big O notation. A balanced binary tree has small height of a binary tree, but a query can enter both children at every level. In this example a query containing $[0,8]\times [0,5]$ visits all seven nodes and tests all four triangles. More generally, a full binary tree with $n$ single-object leaves has $2n-1$ nodes, so such a query takes $O(n)$ work for constant-cost shape tests even when its height of a binary tree is $O(\log n)$. Listing $n$ hits itself requires $n$ outputs. Small height alone gives no unconditional logarithmic query bound.

For collision detection between two bounding volume hierarchies, traverse pairs of nodes: reject disjoint pairs of bounding volumes, expand a nonleaf member of an accepted pair, and apply the narrow phase at accepted leaf pairs. A single collection's self-query must exclude pairing an object with itself and avoid duplicate unordered pairs. If every object overlaps every other object, reporting all pairs already requires $n(n-1)/2$ results. Construction quality, empty space in boxes and the queries determine how much pruning is useful.^[ref]

For a short correctness outline, an object is enclosed by its leaf box, and each child box is enclosed by its parent box. Repeated subset relations carry this property to every ancestor. A true query intersection therefore prevents rejection at every ancestor of the object's leaf. Updating leaf boxes after motion also requires restoring all affected ancestor bounds before querying.

At a regular differentiable interior nearest point of a parametric curve, the displacement from the query point is perpendicular to the tangent vector. A branch and bound search uses distances to certified enclosing bounding volumes as lower bounds, and evaluated limit points as upper bounds. Refine the most promising restricted pieces until the upper bound differs from the global lower bound by the chosen distance tolerance. Safeguarded Newton root-finding iteration accelerates local candidates, but endpoints, nonregular points, ties and other stationary branches must not be omitted.

Collision detection determines whether geometric objects meet, under a specified convention for touching. A bounding volume test can reject a pair before a more detailed shape test.

A robust intersection search applies branch and bound to pairs of subdivision surface patches. Certified bounding volumes reject disjoint pairs, and refinement reduces unresolved pairs. Limit evaluation, tangent data and controlled approximation bounds produce and correct local intersection arcs, then patch adjacency joins them. Bounds must enclose the limit, not merely the current mesh. Flat polygon intersections are approximations and can miss tiny components or tangencies unless the associated geometric and transversality conditions are verified.

For disjoint compact bodies, the minimum occurs on their boundaries. Patch bounding volumes give certified lower bounds and evaluated limit-point pairs give upper bounds. A branch and bound search refines promising patch pairs until the global bounds differ by the tolerance. Boundary distance alone cannot detect containment; touching, crossing or nested solid bodies have ordinary set distance zero. Negative overlap values require an additional convention such as translational penetration depth.

A non-uniform rational B-spline surface isHere the $N_{i,p}$ and $M_{j,q}$ are B-spline basis functions for possibly nonuniform spline knot sequences, and the $w_{ij}$ are weights. Positive weights make each evaluated point a convex combination of the active control points, supplying bounding volumes for geometric searches. The denominator must remain nonzero for the parametrization to be defined.

A bounding volume hierarchy is a tree whose leaves contain geometric primitives, here triangles, and whose internal nodes store cheap-to-test bounding volumes containing all descendant geometry. A bounding volume may be an axis-aligned bounding box or a sphere. The key containment guarantee isTraverse from the root. Reject a whole subtree when its bounding volume is missed; otherwise visit its children and perform the full ray-triangle intersection test only at surviving leaves. Hitting a bounding volume is only permission to investigate, not evidence of hitting an enclosed triangle.

For nearest-hit queries, visit the nearer child first and keep the current nearest parameter. A second child whose volume begins farther away than this parameter can be pruned. For a shadow ray, restrict the traversal to the segment before the source and terminate at any blocker.

A flat list of $N$ triangles needs up to $N$ detailed tests per primary ray or shadow ray. A well-built bounding volume hierarchy can reject large groups with a few cheap tests and substantially reduce the average work. A balanced, well-separated scene often gives traversal resembling a short root-to-leaf search, but balance alone does not guarantee logarithmic query time: extensive overlap or an unfortunate ray can force examination of most or all leaves. Its advantage is spatial rejection, not a universal worst-case bound.

The basic parametric surface interrogation enquiries provide the parameter domain and patch adjacency; evaluation of $S(u,v)$; first derivatives $S_u,S_v$; and, for curvature or error-controlled stepping, second derivatives $S_{uu},S_{uv},S_{vv}$. Useful search enquiries also supply conservative bounding volumes over parameter rectangles, subdivision or restriction of a patch, and regularity/singularity information. A local inverse or closest-point enquiry can help seed a search but does not replace global component isolation.

At a regular point, $S_u,S_v$ are independent tangent vectors, and the oriented unit normal vector isThe tangent plane consists of $S+\alpha S_u+\beta S_v$. If the cross product is zero, this chart does not define a normal; use a regular alternative chart or treat a true singularity separately.

For two surfaces, collect the four parameters in $w=(u_1,v_1,u_2,v_2)$ and setAt a transverse intersection, $n_1\times n_2\ne 0$ and $J$ has rank three. Hence the implicit function theorem makes $F=0$ locally a curve. Choose its physical unit tangent vectorWith $G_i=A_i^T{A}_i$, the parameter derivatives for physical arc length areSince $\tau$ lies in both tangent planes, $A_i(u_i^{\prime },v_i^{\prime }{)}^T=\tau$ exactly. Thus these two pairs form a vector $d$ in the kernel of $J$.

A practical transversal intersection of two parametric surfaces algorithm is:

with Newton method. The final equation intersects the curve with the plane through $X_p$ perpendicular to the predicted tangent. Its Jacobian row is $[{\tau }^T{A}_1,0,0]$; together with $J$ it is nonsingular at a sufficiently nearby transverse point. This removes the otherwise free along-curve parameter in the three coincidence equations.

A finite tolerance supplies a polygonal or fitted-curve approximation; regularity and certified bounds determine its accuracy. Parallel normals, singular charts, branch contacts and coincident patches require separate handling: their intersection may be a singular curve, an isolated point or a two-dimensional region. The transverse marching equations must not be used to claim a unique curve in those cases.

A subdivision surface enquiry acts on the limit surface, not just on the current control mesh. The basic subdivision surface interrogation operations are: enumerate initial patches and their topological adjacency; subdivide a patch into covering children with inherited boundary links; return conservative bounding volumes; estimate approximation error and, where available, normal variation; and evaluate limit positions and first derivatives or tangent data. Boundaries, creases and extraordinary subdivision vertices need explicit rules. Nonnegative convex subdivision weights can supply a local control-hull enclosure, but a scheme with negative weights needs another proved enclosure; an arbitrary control-mesh box is not automatically a bound on the limit.

The intersection of subdivision limit surfaces can be computed by a paired recursive search. Start with every relevant pair of root patches $(A,B)$, along with their domains and adjacency identifiers:

A termination criterion specifies geometric error and conditioning, not merely a fixed refinement depth. For isolated regular transverse components, shrinking limit enclosures and normal/error bounds permit reliable curve approximation. Candidate boxes cannot be discarded merely because no coarse edge has crossed another surface: a complete small closed component can lie in the interior. Tangency, coincident limit patches, creases and poorly conditioned extraordinary-point neighborhoods need special tests or must be reported as unresolved degenerate configurations. The intersection is that of the two subdivision limits; intersecting a finite refined mesh without error control only gives an approximation.

An efficient parametric curve interrogation interface should provide the parameter domain and open/closed status, point evaluation, one-sided endpoint enquiries, first and second derivatives wherever defined, and information about knots or singular parameters. It should also restrict a curve to an interval and subdivide it without changing its limit, return a certified bounding volume for that restriction, and supply derivative or chord error bounds when supported. These enquiries allow cheap geometric rejection before expensive exact evaluation. For a subdivision curve, limit evaluation is distinct from returning a vertex of a finite refined control polygon; the latter is usually an approximation.

For a query point $Q$, minimize $d(t)=\frac{1}{2}\Vert P(t)-Q{\Vert }^2$. At a differentiable interior minimizer,At a regular curve point this says that the query displacement is perpendicular to the tangent vector. If a second derivative exists, the local second-order test isa strictly positive value is sufficient for a strict local minimum. The stationarity equation alone also includes local maxima and is automatic at $P^{\prime }=0$, so it cannot be used as the only global search criterion.

A reliable efficient closest-point search on a subdivision curve uses branch and bound. Cover the compact curve by restricted pieces with certified enclosures $B_I$. For each piece set $L_I=\mathrm{dist}(Q,B_I)$, a lower bound on its true distance. Distances to actually evaluated limit points give upper bounds; keep the best point $P(t_{\ast })$ and distance $U$. For an axis-aligned bounding box ${\prod }_k[l_k,h_k]$, the squared lower bound is inexpensive:For positive partition-of-unity refinement, a convex hull of the active control points is an enclosure. A negative-weight scheme requires a separate certified enclosure; its control hull need not contain the limit.

The algorithm is:

Because ${\min }_I{L}_I\le d_{\min }\le U$, the reported point is at most $ϵ$ farther from $Q$ than a true nearest point. Include endpoints, nondifferentiable joins, and singular parameters in the candidate bookkeeping, or split them into separate pieces. With enclosures converging in diameter under subdivision on a compact continuous curve, the bounds converge to arbitrary prescribed positive distance tolerance. Interval bounds or outward-rounded arithmetic are needed if the guarantee is intended to be certified in floating-point computation. A single Newton root-finding iteration from a single seed supplies no such global guarantee.

An efficient subdivision surface interrogation interface needs the mesh topology and patch adjacency, boundary and trimming information, patch-local parameter charts and their transition maps, and local restriction/refinement with the complete influencing control net. Numerical enquiries should supply limit positions $S$, first derivatives $S_u,S_v$, and second derivatives where defined; these determine normal vectors and curvatures at regular points. It must also return certified patch bounding volumes and convergent geometric/derivative error bounds. Near an extraordinary subdivision vertex, use the local subdivision matrix and limit/tangent evaluation appropriate to that scheme; second derivatives need not exist merely because a tangent plane does. Finite refined mesh vertices are not exact limit positions.

Represent the cutting plane as $n\cdot x=d$, with $n$ normalized. On each chart setThe desired plane section of a subdivision surface is the image of the zero set $g=0$. For a bounding volume $B$, compute a certified interval $[g_{\min },g_{\max }]$ for the plane functional over $B$. If that interval is strictly positive or strictly negative, reject the patch. With positive partition-of-unity weights, the minimum and maximum of $n\cdot p_i-d$ over all influencing control points already bound its limit patch. For masks without this convex hull property, the interface must provide a different valid enclosure.

An adaptive algorithm that isolates components before tracing is:

This is exhaustive to a chosen tolerance when certified subdivision isolates finitely many regular transverse branches and enclosures converge. If $\Vert \nabla g\Vert \ge \gamma >0$ locally and $\Vert DS\Vert \le M$, a residual tolerance $|g|\le \delta$ corresponds locally to a geometric correction bounded by $M\delta /\gamma$, using the gradient flow toward the level set. Bounds on second derivatives similarly control curve-segment chord error bound. As $\gamma$ approaches zero, a fixed residual tolerance no longer gives a fixed geometric error, so the step and stopping rules must reflect conditioning.

Seeding must not rely just on corner signs. For example $S(u,v)=(u,v,u^2+v^2-r^2)$ cut by $z=0$ has a closed circle wholly inside a patch whose corner values are all positive. Certified range tests plus subdivision retain it; a corner-only marching rule can miss it. Tangencies also change the nature of the output: $S=(u,v,u^2+v^2)$ meets $z=0$ in one isolated point, while a coplanar patch contributes an area rather than a curve. Thus a general plane section is not necessarily a union of regular curves; the algorithm should classify these cases instead of silently fabricating or deleting a branch.

For efficiency, cache subdivision stencils, patch extraction, limit-evaluation coefficients and bounds; reuse child data instead of reconstructing the entire refined mesh. Use local influencing neighborhoods, with the halo dictated by mask support, and keep adjacency/boundary topology separate from changing geometric coordinates. Plane-functional bounds can be computed by refining scalar signed-distance controls, which is cheaper than refining all three coordinates. Combine coarse inexpensive boxes with tighter local convex hull or interval arithmetic tests only where needed. Adapt steps to curvature and transversality, reuse branch seeds, and use regular spline evaluation away from extraordinary points. Stable edge ownership, outward-rounded bounds, scale-aware tolerances, and explicit degeneracy flags are correctness requirements as well as performance issues. The result is a limit-surface intersection computation; merely intersecting a finitely refined control polyhedron with the plane supplies only an uncontrolled approximation.

A parametric curve interrogation interface first supplies the parameter domain and the point $C(t)$. At regular parameters, it also supplies $C^{\prime }(t)$ and, when needed, higher derivatives. The unit tangent vector, speed and curvature are then obtained fromin three dimensions. The formulas require $C^{\prime }\ne 0$; a Frenet normal additionally requires nonzero curvature. A practical interface can restrict the curve to a parameter interval, provide endpoints, and give a certified bounding volume or a derivative-range bound. Arc length, closest-point and intersection queries are higher-level operations built from these elementary enquiries rather than consequences of point evaluation alone.

For a plane $n\cdot x=d$ with $n\ne 0$, defineThis reduces certified curve-plane intersection to scalar root isolation. A subdivision curve can expose the parametric enquiries by evaluating its limit at a parameter address: refine the corresponding piece until its certified positional enclosure reaches the requested accuracy, or use its exact local spline representation. Derivative evaluation similarly needs the derivative refinement rule and its error bound. A finite control vertex is not automatically a point of the limit curve.

One reliable algorithm is range-based isolation followed by safeguarded Newton iteration:

For a transverse root, the derivative is nonzero nearby, so sufficiently fine intervals have monotone $F$ and the sign bracket isolates it. Bisection provides a global error bound; near a simple root Newton iteration gives quadratic convergence. Good enclosures discard most of the curve before expensive limit evaluation, and the method does not require a specific subdivision mask.

The weaknesses are equally important. Near tangency $F^{\prime }$ is small and Newton steps are ill-conditioned; same-sign endpoints may conceal a tangent root or two crossings. An arc lying in the plane has infinitely many intersections and should be returned as an interval, not a point. Finite-precision evaluations require error enclosures before a sign is certified. For an arbitrary smooth point-evaluation oracle, no finite sampling scheme can certify all intersections: a smooth bump between sampled parameters can create extra crossings without changing any sampled values or derivatives. With finitely many isolated transverse intersections and convergent certified enclosures, the algorithm terminates to any prescribed tolerance. For tangencies it either uses stronger representation tests or reports unresolved possible-contact intervals, rather than silently omitting them.

A subdivision curve interrogation interface provides its control/topology data, a parameter interval or address, and a refinement operation returning restricted child pieces with their parameter correspondence. It also provides a certified enclosing bounding volume, endpoints or limit-point enclosures, and an error estimate for replacing a sufficiently small piece by its chord. Positional and derivative limit queries may be implemented by refinement or by conversion to the appropriate spline. Nonnegative masks often imply a control-point convex hull bound; a generic scheme with negative weights needs a separate bound.

These enquiries can be applied to a parametric curve by using interval restriction as the subdivision operation and constructing its enclosure from its representation. For example, a Bézier curve is split by De Casteljau's algorithm, and each child's control-point convex hull encloses exactly that child arc. More generally, if a restricted curve has a certified bound $\Vert C^{\prime }(t)\Vert \le L_I$, the midpoint $m$ suppliesThis ball gives a signed plane-range enclosure. Such an upper derivative bound must be supplied or proved; taking the largest derivative seen in a few samples is not a certificate.

The recursive intersection algorithm is as follows. Start with the whole domain. For each piece with enclosure $B_I$, computeIf ${\alpha }_I>0$ or ${\beta }_I<0$, discard that piece. Otherwise split it and process the children, unless a root has already been uniquely isolated and can be polished as in Question 3. For a convex hull bound, the extrema of this affine plane function are attained among its control points, so only dot products are required. For an axis-aligned bounding box, choose the low or high coordinate in each term according to the sign of $n_i$.

At a small flat piece, the chord-plane parameter iswhen the denominator is nonzero. It supplies an initial estimate, which is corrected on the actual curve. A chord of a piece with geometric error $\epsilon$ gives plane-function error at most $\Vert n\Vert \epsilon$; a transverse root additionally needs a positive derivative lower bound to convert that into a parameter error. A chord hit is not by itself a proof of the exact crossing count. Keep unresolved tangent contacts, merge shared-endpoint hits, and return any certified coplanar parameter intervals separately.

Good speed comes from a bounding volume hierarchy, conservative cheap rejection before accurate evaluation, caching shared subdivision work, local rather than uniform refinement, and fast root polishing only after isolation. Convex-hull or box extrema cost far less than solving every potential intersection. Tight bounds shrink rapidly with subdivision and reduce the active search to neighborhoods of actual crossings. Derivative information can prove monotonicity, accelerate with the Newton root-finding iteration, or tighten range bounds using interval arithmetic. There is no universal fixed speed guarantee when the curve is nearly coplanar or has arbitrarily many intersections: those are genuinely difficult inputs. The representation must provide meaningful bounds and restriction operations; point/derivative enquiries alone do not imply such capabilities.

Use the PDF's notation: $P$ is the fixed point light, $C(t)$ is the casting curve, and $S(u,v)$ is the receiver. A shadow point solvesThe separating-plane assumption puts the caster between light and receiver, so the relevant intersections are beyond the caster, not on the backward ray. The facing assumption supplies transverse regular intersections on the lit side. Carry out shadow tracing for a parametric curve as follows.

First subdivide the curve domain and receiving patches. Reject combinations whose certified bounding volumes cannot intersect the corresponding forward ray cone. For the remaining combinations, subdivide and isolate a hit, then correct its parameters using a three-variable Newton method with JacobianCheck that the corrected parameters lie in the patch domain and $\alpha >1$. Seed every connected component; one arbitrary initial hit does not establish that other components are absent. If a ray has several receiving hits, compare their $\alpha$ values and retain the visible first hit, rather than jumping between sheets.

At a transverse branch the Jacobian is nonsingular because $(C-P)\cdot (S_u\times S_v)\ne 0$. Differentiate the equation to predict the next hit:Use this predictor for a proposed parameter step, then apply Newton correction. To control the polygonal approximation, the shadow path is $X(t)=S(u(t),v(t))$. A second differentiation givesTogether with the surface derivatives this supplies a bound on $X^{\prime \prime }$. If $\Vert X^{\prime \prime }\Vert \le M$ over an interval of width $h$, the maximum error from its chord is at most $M{h}^2/8$. Subdivide until this bound, plus the numerical intersection error, is below the graphics tolerance. Corrected endpoints then give the requested point sequence on $S$. If second-derivative bounds are unavailable, refine until a certified enclosure of the entire branch segment lies within tolerance of its chord; a sufficiently small enclosure diameter is a conservative fallback.

Continue through adjacent patches, split at a trim or surface boundary, and stop a component when its admissible intersection ceases. Record closed components without duplicating their starting point. Use adaptive chord-error control and component isolation; a fixed fine sampling or an unverified sequence of local Newton solves can miss part of the shadow. If only estimated midpoint errors are available, those support a practical rendering heuristic rather than a certified tolerance.

A parametric surface interrogation interface must specify its parameter domain, patch boundaries, trimming restrictions and any exceptional or singular points. It must evaluate $S(u,v)$ and the available derivatives, in particular $S_u,S_v$ for tangent vectors andfor the oriented normal vector where the denominator is nonzero. Second derivatives $S_{uu},S_{uv},S_{vv}$ are needed when the code requests curvature or second-order geometric error estimates; higher derivatives depend on the enquiry. The interface must report where these quantities exist, rather than assign an artificial normal at a singular parameter point.

Global searches also need subdivision into equivalent restricted patches, certified bounding volumes and a geometric approximation/error bound. These support intersection isolation, pruning and tolerance-controlled meshing. A single point-evaluation routine cannot guarantee a global search because it may miss remote branches or features between samples. Adjacent-patch topology and consistent orientation are needed to join results and interpret the represented surface.

Interpret the positive-distance assumption as disjoint compact enclosed bodies $A,B$, certified for example by disjoint enclosing volumes. Merely having disjoint drawn control meshes is insufficient if one encloses the other or the meshes do not enclose their limit surfaces. For genuinely disjoint bodies, the closest pair lies on their boundaries: an interior point could move toward the other body and decrease the distance. Thus minimize over all pairs of limit-surface patches.

Use branch and bound on patch pairs. For regions $A_i,B_j$, enclosing bounding volumes give a lower bound $L_{ij}$ on their true minimum distance. For axis-aligned bounding boxes, compute this directly asAny pair of evaluated limit points provides a feasible upper bound; retain the smallest, $U$. Start with a covering list of all coarse patch pairs. At each step, discard a pair when its lower bound is at least $U$, otherwise refine the region with larger bounding diameter/error and enqueue its child pairs. Prefer the pair with smallest lower bound. Update $U$ with new feasible pairs; a local stationary-distance solve can improve it but cannot replace the global search.

Let $L_{\ast }$ be the minimum remaining lower bound, capped by $U$ if the list is empty. The current certificate isStop when $U-L_{\ast }\le \epsilon$. Compactness and shrinking valid patch enclosures ensure convergence to this tolerance under the interface assumptions. An equivalent mesh method must add each mesh's certified limit error; for Hausdorff distance errors $e_A,e_B$, the separation error is at most $e_A+e_B$. Finite mesh distance without such a bound is not the exact minimum distance between subdivision bodies.

A subdivision surface interrogation interface needs the initial control net, its face/edge/vertex connectivity, the subdivision rule, patch addressing and refinement into child regions that cover the same limit surface. It must supply limit-point evaluation, available tangent/normal data and smoothness information, including the treatment of extraordinary subdivision vertices. A finite refined mesh point is generally not the exact limit point.

For geometric search it must provide certified bounding volumes for each descendant region, bounds that shrink under refinement, and a mesh-to-limit or chord/patch error estimate. With positive convex subdivision masks the active-control convex hull can provide such an enclosure; schemes with negative coefficients need another valid bound. A closed surface also needs consistent orientation, component navigation and containment queries for the enclosed body. The $C^1$ hypothesis supplies first-order tangent information at regular points, not automatically second derivatives or curvature everywhere. These enquiries distinguish an accurate limit-surface algorithm from a calculation only on an approximate control polyhedron.

The core parametric surface interrogation is evaluation of the position and its derivatives through second order:Position answers point queries; first derivatives give the differential, tangent directions and normal vector; second derivatives supply curvature. An evaluator should also report the parameter domain, patch adjacency, boundary curves and knot or crease locations, and whether these derivatives exist at the queried point. At a discontinuity boundary it should provide the relevant one-sided limits rather than silently average them.

For spatial searches, provide restriction or subdivision into equivalent smaller patches and certified bounding volumes, with error estimates when an approximate mesh is used. These allow intersection and closest-point algorithms to reject remote patches and refine the remaining candidates. A useful interface therefore combines differential evaluation with domain/topology and enclosure information. Inverse parameter lookup, ray intersection and nearest-point search can be built from these primitives using subdivision and local root or minimization solves; they need not be presumed exact basic evaluations of every representation.

The corresponding subdivision surface interrogation needs mesh connectivity and patch adjacency, boundary and crease flags, local coordinate charts with transition maps, and subdivision into smaller patches with their original-chart mappings. Its evaluation enquiry returns a limit point, tangent derivatives and a normal vector; second derivatives are supplied only where the limit is sufficiently smooth. Certified bounding volumes and patch approximation errors allow a hierarchy for intersection and proximity searches. Boundary-curve enquiries complete the interface for clipping.

On regular parts of a subdivision surface, these evaluations may use its equivalent tensor-product or box spline patch. Near an extraordinary subdivision vertex, the local subdivision matrix determines the limit position through its constant left eigenvector, and its tangent modes determine the normal vector under the scheme's characteristic map of a subdivision surface regularity conditions. Refinement alone does not establish those conditions. A subdivision surface may have a well-defined tangent plane there without possessing second derivatives or Gaussian curvature. An interrogation interface must distinguish these cases and can work on surrounding regular charts when a higher derivative is unavailable at the vertex itself.

Together, subdivision, bounds, topology and limit evaluation support ray–subdivision surface intersection: bounds eliminate irrelevant patches; surviving patches are refined, and regular candidate intersections are corrected using position and first derivatives. The returned intersection is a point of the limit subdivision surface with an error certificate, rather than automatically a point on the last control mesh.