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.

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.

Count scalar additions, subtractions, multiplications and divisions for the specific triangle-triangle intersection algorithm above; comparisons and index selection are separate. Computing one plane normal vector uses two vector differences, costing six subtractions, and one cross product, costing six multiplications and three subtractions. The three vertex-to-plane evaluations use nine further coordinate subtractions and three dot products, each with three multiplications and two additions. The first rejection test therefore costsFor randomly located triangles of characteristic size $a$ in a box of size $H\gg a$, a second triangle straddles the first triangle's plane only when its position is in a slab of relative thickness $O(a/H)$. Consequently the first plane test rejects almost every pair: the expected arithmetic count for this implementation is $39+O(a/H)$, with the constant in the remainder determined by the subsequent branches. This is an average count, rather than the assertion that every input needs 39 operations.

For a generic surviving noncoplanar pair, the symmetric plane test costs another 39 operations, the cross product $N_A\times N_B$ costs nine, and each of the four slice endpoints needs five scalar operations in the selected coordinate: one subtraction and division for the interpolation fraction, then one subtraction, multiplication and addition for the coordinate. Thus this branch usesA fully executed coplanar test can use six planar edge directions. Each needs two subtractions to form its perpendicular and six two-dimensional dot products, costing $2+6(3)=20$ operations. Including both plane tests and the parallelism cross product gives an upper count $78+9+120=207$ before any early exit. Contact and degeneracy can shorten or change these counts. Precomputed normal vectors or a preliminary axis-aligned bounding box test also change the answer: the latter uses only comparisons after its coordinate extrema are available. The relevant small-triangle average is 39 operations for the specified plane-first implementation; a generic complete test uses 107.

Let the triangles have vertices $A_0,A_1,A_2$ and $B_0,B_1,B_2$. Work initially with nonzero-area triangles. A triangle-triangle intersection algorithm begins with the unnormalized normal vector $N_A=(A_1-A_0)\times (A_2-A_0)$ and the three signed plane evaluations $d_j=N_A\cdot (B_j-A_0)$. If all $d_j$ are strictly positive, or all strictly negative, the second triangle lies strictly on one side of the first one's plane, so the triangles are disjoint. Otherwise compute $N_B$ and $e_i=N_B\cdot (A_i-B_0)$ and apply the symmetric rejection test. Strict inequalities are important: contact on a vertex or edge counts as intersection.

If the planes are not parallel, put $L=N_A\times N_B$. Each triangle meets the other one's plane in an empty set, a point or a line segment. Its endpoints are obtained from zero-valued vertices and the edges whose endpoint plane evaluations have opposite signs. For example, an edge $B_j{B}_k$ contributesAll these points lie on the common line of the two planes. Choose a coordinate $r$ for which $L_r\ne 0$ and form the coordinate intervals $I_A=[a_{-},a_{+}]$, $I_B=[b_{-},b_{+}]$ of the two slices. This coordinate is one-to-one along the common line, so the exact final test isOnly that coordinate of each slice endpoint needs to be evaluated; no full three-dimensional line parameterization is necessary.

Parallel planes which have survived the strict plane tests are coplanar. Drop the coordinate corresponding to the largest component of $N_A$ and test the two projected planar triangles. For each edge of either projected triangle, project both vertex sets onto the perpendicular direction. A strictly disjoint pair of projection intervals certifies separation. If none of the six edge directions separates them, the planar convex sets overlap: a separating line for two disjoint convex polygons can be chosen parallel to an edge of one of them. This includes containment and boundary contact.

A zero normal vector signifies a degenerate triangle; reduce its convex hull to a point or its extreme line segment and use point containment or segment intersection instead. For floating-point input, reliable sign predicates and scale-aware error bounds are preferable to treating a tiny signed distance as an arbitrary exact zero. Plane rejection followed by interval overlap, with a planar test for coplanar input, determines all nondegenerate cases.