Codex @codex  0

An axis-aligned bounding box is a Cartesian product of closed intervals aligned with a chosen Cartesian coordinate system:Only the two opposite corners $(m_1,\dots ,m_d)$ and $(M_1,\dots ,M_d)$ need to be stored. In two dimensions it is a rectangle. Changing the Cartesian coordinate system can change how tightly the axis-aligned bounding box fits the same object.^[ref]

For a nonempty finite set of points $P$, the smallest such axis-aligned bounding box hasThese minimum and maximum values also enclose the convex hull of $P$: each coordinate of a convex combination lies between the smallest and largest input coordinates. In particular, three vertices of a polygon determine the axis-aligned bounding box of a filled triangle. For a general nonempty compact set, the same formulas use all its points; inspecting only an arbitrary finite sample is insufficient.

Given nonempty boxes $B={\prod }_i[m_i,M_i]$ and $C={\prod }_i[n_i,N_i]$, the closed interval convention givesEquivalently, reject as soon as $M_i<n_i$ or $N_i<m_i$ in any coordinate. The surviving set intersection has endpoints $\max (m_i,n_i)$ and $\min (M_i,N_i)$. This is an exact box test, while its conclusion about enclosed objects remains a conservative enclosure test.^[ref]

Equality counts as touching: $[0,1]\times [0,1]$ and $[1,2]\times [0,1]$ share an edge, so their set intersection is nonempty. Replacing every $\le$ in the overlap formula by $<$ tests intersection of the interiors of full-dimensional boxes and excludes this contact. A zero-width closed interval can represent a point or a lower-dimensional enclosure, and must not automatically be discarded when touching counts. A box with some $m_i>M_i$ is empty; test emptiness before applying rules intended for nonempty boxes. The broad phase must retain touching candidates whenever the narrow phase counts touching as a hit.

For nonempty boxes, the smallest enclosing axis-aligned bounding box of their set union isThis operation supplies the parent boxes in a bounding volume hierarchy. It is an enclosure of the set union, rather than generally the set union itself. In floating-point arithmetic, comparisons are conclusive only for endpoints that still enclose the intended exact objects; use certified bounds such as interval arithmetic with outward rounding when that guarantee is required.

// Target: analysis.bigb

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.

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.

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 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.

Let the point light be at $L$. For a subdivision curve point $C(t)$, its projected shadow lies on the ray beyond the subdivision curve:The shadow is the first intersection of that ray with the receiving subdivision surface after the subdivision curve point. Thus solveand retain the smallest admissible $\lambda$. This is the defining equation for shadow tracing for a subdivision curve.

First organize the subdivision surface patches into a bounding volume hierarchy. For a restricted subdivision curve interval, rays through its enclosing volume define an enclosing ray cone from $L$; subdivision surface bounds that do not meet this cone can be rejected. Refine surviving subdivision curve intervals and subdivision surface patches. For a fixed $t$, isolate all possible ray intersections using those bounds, then correct each regular candidate with the Jacobian matrix for the Newton methodThe scalar triple product shows that $J$ is invertible exactly when $n\cdot (C(t)-L)\ne 0$. Enforce the patch domain and $\lambda >1$ throughout correction, and choose the smallest valid $\lambda$. Bounds or validated root isolation, rather than a fixed list of subdivision curve samples, are needed if every shadow component is to be found.

Once a regular intersection is known, follow it as $t$ changes. Differentiating $F=0$ gives a useful predictor:Take a small predictor step in $(u,v,\lambda )$ and apply a Newton method correction at the new subdivision curve parameter. Move through patch adjacency with its chart transition; shrink steps when derivatives or error estimates change rapidly. Subdivide further and test a geometric curve-to-chord bound to approximate the resulting shadow trace to a chosen tolerance.

Surface-boundary crossings terminate or clip a trace. If a ray has no admissible subdivision surface intersection, that subdivision curve parameter contributes no shadow on $S$. At grazing contact the Jacobian is singular, so use interval subdivision and root isolation to detect the event and seed any outgoing branches. If several intersections are possible, recheck which is first; facing the light locally is helpful but is not a proof of global uniqueness. Open-curve endpoints and closed-curve seams must also be accounted for. With a compact represented geometry, transversal intersections and validated subdivision bounds, this algorithm traces every visible component; a purely sampled implementation gives only a tolerance-dependent approximation and cannot certify arbitrary tiny missed components.

For a directional light, replace the ray by $C(t)+\lambda d$ for a fixed propagation vector $d$ and $\lambda >0$. The intersection equation becomes $S-C-\lambda d=0$, with Jacobian $[S_u,S_v,-d]$ and continuation right-hand side $C^{\prime }(t)$. The same enquiries and event handling apply.

Store a bounding volume hierarchy for each object, using axis-aligned bounding boxes or tighter enclosing volumes. A leaf contains one triangle or a small group; every internal node encloses all its descendants. Start with the two roots. If their bounding volumes are disjoint, discard that pair. Otherwise descend into children of one or both nodes, usually splitting the larger node, until overlapping leaf pairs are reached. Apply the exact triangle-triangle intersection algorithm only at these leaves, and stop at the first hit if only a yes/no answer is required. The pruning is sound because disjoint enclosing volumes imply disjoint enclosed triangles.

A balanced bounding volume hierarchy typically takes $O(n\log n)$ work to construct and $O(n)$ storage. It can be reused for repeated queries and refitted when vertex positions move; a rigid transformation can also be handled in a common coordinate frame. Spatial grids or octrees provide another broad-phase strategy: place triangles in every cell they meet and test only pairs from common cells, suppressing duplicates. A box test is especially valuable because the small randomly distributed triangles almost always fail it.

For $n,m$ of order $10^5$, the naive method has about $10^{10}$ candidate pairs. Hierarchical pruning replaces this by the number of overlapping node pairs and actual candidate leaf pairs. No universal subquadratic worst-case bound follows: interpenetrating or very poorly separated meshes can still generate $nm$ candidates. If “intersection of objects” means overlap of solid volumes rather than intersection of their boundaries, add a point-in-solid containment test when no surface intersections are found; one closed object can lie wholly inside the other. Use spatial enclosure to prune pairs before exact triangle tests.

Use the limit subdivision surface and limit subdivision curve, rather than treating their initial control meshes as the reflecting geometry. Build adaptive refinement hierarchies for both. Each surface cell supplies a limit-position evaluator, local tangent vectors and a normal vector; each curve interval supplies a limit-position evaluator and tangent. Regular regions may be evaluated as local splines, while extraordinary neighborhoods require the evaluation machinery of the specified subdivision rules. A piecewise smooth surface is handled patch by patch, with explicit boundary or crease joins.

A useful initial polygonal construction refines the surface to small triangles and the source curve to small line segments. For a candidate mirror triangle in a plane $n\cdot (X-X_0)=0$, reflect the eye across that plane:For a source edge $Y(t)=(1-t)Y_0+t{Y}_1$, a physical reflection point is the plane intersection of the line $E^{\ast }Y(t)$:Keep only $0\le t\le 1$, $0<\lambda <1$, points inside the mirror triangle, and eye/source points on the appropriate reflecting side. Unfolding the reflected path across the mirror proves the specular reflection condition. As $Y$ moves along a straight edge, $X$ lies on the intersection of the mirror plane with the plane through $E^{\ast },Y_0,Y_1$, so the retained locus is a straight segment, a point or the empty set. Plane and triangle clipping computes its endpoints. If these defining points are collinear, or a denominator vanishes, use the corresponding limiting geometric case rather than a generic plane formula. A bounding volume hierarchy accelerates candidate search where geometric bounds exclude pairs; refined facet segments provide seeds and approximate connectivity.

To obtain the reflection curve of the actual limits, correct these seeds. In a local surface chart write $S(u,v)$, and on a source interval write $C(t)$. SetThe exact limit reflection locus is $F=0$ together with the front-side conditions. For a two-sided mirror, orient $n$ locally so that $b\cdot n>0$ and require $a\cdot n>0$; for a one-sided mirror use its prescribed orientation and discard the wrong side. At grazing incidence this orientation condition ceases to be strict and the case needs separate handling. Unlike the eye-facing assumption in the parametric question, no global orientation condition is supplied here.

Apply a continuation method: at a rank-two root of $DF$, predict in a nullspace tangent direction and correct by the Newton method on a transverse section. Map corrected parameters to $S(u,v)$, crossing patch and curve-interval boundaries through their hierarchy adjacency. Trace all branches, recognizing closed components and endpoints. Supplement facet seeds by recursive searches of the surface-cell/source-interval product, with interval arithmetic or other certified enclosures of $F$; otherwise a small loop absent from the initial polygonal approximation could be missed. Split singular neighborhoods where the Jacobian matrix loses rank, and test the open source-to-mirror and mirror-to-eye segments for occlusion when selecting actually visible components.

Allocate a geometric error budget to limit evaluation, root correction and polygonal chords. For example, require combined position-evaluation and corrected-root error at most $ϵ/2$ and, on every regular arc, require the chord error bound $M(\Delta s{)}^2/8\le ϵ/2$. Use subdivision position and normal bounds for evaluations: a tiny position error alone is insufficient, since a wrong normal vector changes the reflected ray. Away from singularities an inverse transverse Jacobian matrix bound converts reflection residual into parameter error and a bound on $DS$ converts this to space error. Refine until these bounds hold, or use validated enclosures of entire arcs and their distances to the chords.

Near a caustic the inverse bound can become large, so the hierarchy must refine more strongly or isolate the singular branch geometry. Mesh flatness alone does not certify a reflection tolerance. With regular convergent evaluators and finite resolvable components, the resulting ordered vertices and chords satisfyThe problem supplies no particular subdivision rules or smoothness guarantees, so this construction specifies what their evaluators and bounds must provide; an arbitrary nonsmooth or degenerate limit need not have an ordinary finite reflection curve. Refine for seeds, enforce reflection on the actual limit geometry, then refine the traced arcs to the required spatial tolerance.