Planes, rays and bounding volumes: exact containment and intersection semantics

CNA snapshot 3b43bd86  ·  Deep Dives › Framework core  ·  source links pinned to 3b43bd86

Plane, Ray, BoundingBox, BoundingSphere and BoundingFrustum answer the geometric questions of culling, picking and collision. Their XNA names suggest one uniform quality level; at TARGET each function has its own boundary rules and tolerances, and nearly all of them reproduce the genuine XNA 4.0 implementation, including its convex frustum intersection and its ray clipping. This page gives the exact semantics per type — half-space conventions, corner order, what "touching" means, which tolerance applies — and marks the two places where CNA and XNA 4.0 still disagree, with a workaround. It is for gameplay programmers writing collision and picking code and for porters whose results must match XNA. Short member tables are on Math types: bounding types; Tutorial 44 and Tutorial 74 are the hands-on introductions.

Planes and half-spaces

A Plane stores a Normal and a scalar D and describes the set N·x + D = 0, so D is the negated distance of the plane from the origin along its normal: the plane y = 1 is Plane(Vector3(0, 1, 0), -1). Plane.cpp provides four constructors. Only the three-point constructor normalises: it takes N = normalize(Cross(b − a, c − a)) and D = −N·a, so the normal points to the side from which a, b, c appear counter-clockwise in a right-handed frame. Plane(normal, d), Plane(a, b, c, d) and Plane(Vector4) store what they are given; call Normalize() before using DotCoordinate as a distance.

• DotCoordinate(p) = N·p + D is the signed distance of a point (for a unit normal) and is the classification primitive: positive means on the side the normal points to.
• DotNormal(v) = N·v ignores D and tests a direction, for example whether a ray is heading towards the plane.
• Dot(Vector4) = N·(x, y, z) + D·w covers both: w = 1 for points, w = 0 for directions.
• Normalize follows XNA's arithmetic: the squared length of the normal is accumulated wider than float, its square root is rounded to float before the reciprocal is taken, and a plane whose squared normal length lies within 2⁻²³ (about 1.19e-7) of 1 is returned unchanged. Matrix::CreateReflection and Matrix::CreateShadow normalise their plane argument the same way (PlaneNormalizationCompatibilityTests.cpp).

PlaneIntersectionType::Front means the whole volume lies on the positive side (the side the normal points to), Back the negative side and Intersecting both. BoundingSphere::Intersects(Plane) answers Front when the centre's distance exceeds the radius; BoundingBox::Intersects(Plane) tests the box's most negative and most positive vertex against the normal; both agree with XNA 4.0. The private helper Plane::IntersectsPoint, which only BoundingFrustum uses, returns Front for a positive distance, Back for a negative one and Intersecting for exactly zero; XNA has no such helper, and that zero case is what makes BoundingFrustum::Intersects(Plane) differ (below). The Doxygen comments in PlaneIntersectionType.hpp state the opposite meanings (Front "in the negative half-space"); trust the behaviour, not those two comments (CNA-BUG-025).

Transforming a plane

Planes transform with the inverse transpose of the point transform: if points move by M, the plane (N, D) as a row vector is multiplied by (M⁻¹)^T. CNA's Plane::Transform(plane, matrix) inverts M and transposes the inverse in place with Matrix::Transpose(transformedMatrix, transformedMatrix). That output-reference overload reads all sixteen source fields before it writes (see output-reference overloads), so the call yields the true inverse transpose and the result matches XNA 4.0, which inverts M and reads the rows of the inverse directly. The plane y = 2, Plane(Vector3::Up, -2), moved by CreateTranslation(0, 5, 0) becomes y = 7, Plane(Vector3::Up, -7), through the value form, the output-reference form and an output that aliases the input: MatrixTransposeCompatibilityTest.PlaneTransformRetainsTranslatedNonzeroOffset pins exactly that case, and AliasedOutputPreservesBitsAndIsAnInvolution pins the aliased transpose bit for bit.

Since the 0.1.0 release this overload is correct. The release's aliased transpose symmetrised the inverse instead of transposing it, so a translated plane came out tilted and a rotated one could end up facing the wrong way; code that worked around it by transposing into a separate object computes the same result and can stay as it is. The matrix overload does not renormalise: under a transform that scales, the resulting normal is no longer unit length, so call Normalize() before reading distances. Plane::Transform(plane, quaternion) rotates the normal with Vector3::Transform and keeps D, which is correct for a normalised plane rotated about the origin.

Rays: one type, four intersection rules

A Ray is a Position and a Direction; every intersection returns std::optional<float> (XNA's float?), empty for no hit. The box, plane and frustum tests return the ray parameter t, measured in multiples of Direction; the sphere test computes the distance along the ray as Dot(Direction, centre − origin), which is a distance only for a unit direction. XNA documents Direction as a unit vector, and CNA does not normalise it, so normalise picking directions before querying several shapes. The four rules, read in Ray.cpp and BoundingFrustum.cpp and compared with XNA 4.0:

The frustum row is the one that changed most since the 0.1.0 release, which classified only the ray origin: a ray from outside that pointed into the frustum was reported as a miss, and an origin exactly on a plane threw System::NotImplementedException. At TARGET BoundingFrustum::Intersects(Ray) and Ray::Intersects(BoundingFrustum) clip the ray. For the camera frustum CreateLookAt((0, 0, 5), Zero, Up) * CreateOrthographic(2, 2, 1, 5), whose near plane lies at z = 4, a ray from (0, 0, 7) along −Z enters at t = 3; BoundingFrustumTest.IntersectsRayUsesTransformedAndCameraFrustumPlanes asserts that answer through both frustum overloads and through Ray::Intersects, and IntersectsRayClipsEveryPlaneWithXnaBoundaryRules covers 22 cases (entry through each of the six planes, boundary and stationary origins, the containment tolerance and the parallel threshold) that CNA records as passing against the genuine XNA 4.0 assembly as well. A nearest-hit picking loop over boxes (syntax-checked against the headers at c1c316b9; the declarations it uses are unchanged at TARGET):

const SceneObject* nearest = nullptr;
float nearestDistance = std::numeric_limits<float>::max();
for (const SceneObject& candidate : candidates)
{
    if (const std::optional<float> hit = pickRay.Intersects(candidate.bounds);
        hit && *hit < nearestDistance)
    {
        nearestDistance = *hit;
        nearest = &candidate;
    }
}

Build pickRay from two Viewport::Unproject calls at depth 0 and 1 and a normalised difference, as in Math types: code examples. Where a ray may start exactly on a sphere's surface and the XNA answer 0 matters, test Vector3::DistanceSquared(origin, centre) <= r * r first and treat it as a hit at 0.

BoundingBox

BoundingBox.cpp stores Min and Max and trusts them: nothing checks that Min ≤ Max.

• Corner order. GetCorners() returns XNA's fixed order, the Max.Z face first, each face wound top-left, top-right, bottom-right, bottom-left: 0 = (Min.X, Max.Y, Max.Z), 1 = (Max.X, Max.Y, Max.Z), 2 = (Max.X, Min.Y, Max.Z), 3 = (Min.X, Min.Y, Max.Z), 4 = (Min.X, Max.Y, Min.Z), 5 = (Max.X, Max.Y, Min.Z), 6 = (Max.X, Min.Y, Min.Z), 7 = (Min.X, Min.Y, Min.Z). So Max is corner 1 and Min corner 7, not 0 and 7. No test asserts this order (GetCornersContainsMinAndMax only checks that both appear). GetCorners(std::vector<Vector3>&) fills an existing vector and throws System::ArgumentOutOfRangeException below eight elements; BoundingBox::CornerCount is 8.
• Touching counts. Contains(point) is inclusive on every face, and Intersects(BoundingBox) uses inclusive comparisons, so two boxes that share only a face intersect. That is the opposite of Rectangle (see Rectangle edge ownership). Both match XNA.
• Box and sphere. Contains(BoundingSphere) returns Contains when the sphere fits inside every face with its radius, otherwise accumulates the squared distance from the centre to the box (in double) and answers Intersects or Disjoint; Intersects(BoundingSphere) is the same distance test. The answers agree with XNA's clamp-and-distance formulation for ordinary inputs.
• Box and frustum. Intersects(BoundingFrustum) delegates to the frustum's convex test (below). Contains(BoundingFrustum) follows XNA: Disjoint when the frustum does not intersect the box, Intersects as soon as one of the eight frustum corners lies outside the box, Contains otherwise.
• Construction. CreateFromPoints takes a std::vector<Vector3> and throws System::ArgumentException for an empty one; CreateFromSphere and CreateMerged are exact min/max operations.

BoundingSphere

• The constructor BoundingSphere(center, radius) refuses a negative radius with System::ArgumentException, as XNA's does; zero, negative zero, NaN and infinity are stored as given (GeometryValuesCompatibilityTest.SphereRejectsNegativeRadiusAndPreservesOtherValues). The default constructor gives radius 0, and the public Radius field can still be assigned anything.
• CreateFromPoints reproduces XNA's own two-pass algorithm: the extreme points on each axis, the widest axis chosen by the distance between its extremes (the later axis wins a tie), a seed sphere of half that distance around their midpoint, and one growth pass in which each outside point moves the radius to the mean of the old radius and its distance. It is not the minimal enclosing sphere and depends on point order. Every intermediate is evaluated wider than float and stored as float, and BoundingSphereOracleTests compares the result bit for bit with 445 recorded point sets from the genuine XNA runtime; details on Math internals: BoundingSphere::CreateFromPoints. An empty list throws System::ArgumentException, the same type as the box's. CreateFromFrustum runs it over the eight frustum corners.
• CreateFromBoundingBox gives the circumscribed sphere: centre (Min + Max)/2 and radius the distance from that centre to Max. XNA computes the same sphere as Lerp(Min, Max, 0.5) and Distance(Min, Max) · 0.5, so the two can differ in the last bit; no oracle covers it.
• Transform(matrix) transforms the centre with Vector3::Transform and multiplies the radius by the square root of the largest squared length of the matrix's first three rows — XNA's formula. Under CreateScale(2, 3, 4) a sphere of radius 2 gets radius 8. The result encloses the transformed ellipsoid, which is safe for broad-phase culling but loose; for a tight bound transform the source points and rebuild, or use an oriented box of your own.
• Contains(Vector3) returns Contains only for a point strictly inside and Disjoint otherwise, a point exactly on the surface included; it never answers Intersects, as in XNA. The value form compares a squared distance accumulated wider than float with r² computed in double; the output-reference form first stores the squared distance as a float, as XNA's does, so for a point within one rounding step of the surface the two overloads can disagree exactly as XNA's do (GeometryContainmentCompatibilityTest.SpherePointOverloadsRetainTheirMeasuredStorageBoundary). A NaN distance is Disjoint.
• Contains(BoundingSphere) compares the distance between the centres (not its square) with the signed radii, in double: Disjoint unless R + r ≥ d, Contains when R − r ≥ d, otherwise Intersects. A larger sphere around the same centre is therefore Intersects: BoundingSphere(Vector3::Zero, 1).Contains(BoundingSphere(Vector3::Zero, 5)) gives Intersects, as XNA does (SphereContainmentUsesSignedRadiusDifference).
• Intersects(BoundingSphere) is true only when (R + r)² > d², a strict comparison evaluated wider than float: two spheres that only touch from outside do not intersect, and a NaN radius never intersects (SphereIntersectionExcludesExternalTangency). Intersects(BoundingBox) delegates to the box.
• Contains(BoundingBox), Contains(BoundingFrustum) answer Disjoint when the volume does not intersect the sphere, Intersects when any of its eight corners lies farther from the centre than the radius, and Contains otherwise. A corner exactly on the surface counts as inside here, unlike Contains(Vector3) (VolumeCornersRemainInclusiveDespiteStrictPointApi); XNA draws the same distinction.

BoundingFrustum

BoundingFrustum.cpp derives six normalised, outward-facing planes from its matrix in the order Near, Far, Left, Right, Top, Bottom (XNA's extraction; the derivation and the [0, 1] depth volume it implies are on Coordinate conventions: depth), and eight corners by intersecting three planes at a time. The corner order matches XNA's: the near face first — near-left-top, near-right-top, near-right-bottom, near-left-bottom — then the far face in the same winding, topologically the same order as the box's. CNA computes each corner with the three-plane formula; XNA intersects a plane with the line where two others meet, so the corners can differ in the last bit. Because the planes point outward, a Front classification against any one plane means outside.

• Contains(Vector3) evaluates all six planes, accumulating each distance wider than float, and answers Disjoint only when a distance exceeds XNA's tolerance of 1e-5; otherwise it answers Contains. Points on the boundary or up to 1e-5 outside it are inside, and a point is never Intersects (GeometryContainmentCompatibilityTest.FrustumPointChecksAllPlanesAndXnaTolerance, BoundingFrustumTest.OrthographicPointContainmentMatchesXnaFarPlaneTolerance).
• Contains(BoundingBox), Contains(BoundingSphere) classify the volume against each plane: any Front means Disjoint, any Intersecting means Intersects, otherwise Contains (the sphere form evaluates each plane distance in double, as XNA's inlined expression does). This is XNA's rule and it is conservative: a volume beside an edge or corner of the frustum can straddle two side planes' extensions without touching the frustum and is then reported as Intersects.
• Intersects(BoundingBox), Intersects(BoundingSphere), Intersects(BoundingFrustum) run XNA's GJK convex-separation query (ported into the internal Gjk.hpp, with XNA's progress and termination thresholds), not the plane rule, so in the edge and corner cases above Contains answers Intersects while Intersects answers false, exactly as in XNA. GeometryContainmentCompatibilityTest.FrustumIntersectionRequiresActualConvexSeparation shows the split for a sphere of radius 1 at (1.8, 1.8, 0.5) beside the identity-matrix frustum, and FrustumSeparationOracleTests compares spheres, boxes and frustums with a corpus CNA recorded from the genuine XNA runtime (tests/reference/xna40/framework/frustum-separation-oracle.txt). BoundingBox::Intersects(frustum) and BoundingSphere::Intersects(frustum) delegate here.
• Intersects(Plane) classifies the eight corners with Plane::IntersectsPoint; a corner exactly on the plane counts as Intersecting, so a frustum touching a plane from behind is Intersecting where XNA, which counts a zero distance as Back, answers Back (CNA-BUG-071). Where that boundary matters, classify the corners yourself with DotCoordinate and treat a zero distance as Back.
• Contains(BoundingFrustum) answers Disjoint when the two frustums do not intersect, Intersects when any corner of the other frustum lies outside this one (by more than the point tolerance), and Contains otherwise. A frustum contains itself and every frustum built from the same matrix; there is no pointer-identity shortcut (BoundingFrustumTest.ContainsSameFrustumReturnContains).
• GetCorners(std::vector<Vector3>&) throws System::ArgumentOutOfRangeException below eight elements; PlaneCount is private. Equality and GetHashCode use only the matrix.

Containment and intersection answers at a glance

The two remaining differences are recorded on Known Issues (CNA-BUG-069, CNA-BUG-071), as is the swapped Doxygen of PlaneIntersectionType. The argument exceptions are listed on Math value types: argument errors.

Evidence

Checked by reading Plane.cpp, Ray.cpp, BoundingBox.cpp, BoundingSphere.cpp, BoundingFrustum.cpp, Gjk.hpp, Vector3Arithmetic.hpp and their tests at 3b43bd86; nothing was built or run, and the worked values are CNA's own test expectations or were derived by hand from the code. The XNA 4.0 behaviour was read in the decompiled genuine Microsoft.Xna.Framework assembly (BoundingBox, BoundingSphere, BoundingFrustum, Plane, Ray). Test coverage: BoundingBoxTests, BoundingSphereTests, BoundingFrustumTests, PlaneTests and RayTests are mostly analytic unit tests; GeometryContainmentCompatibilityTests, GeometryValuesCompatibilityTests, PlaneNormalizationCompatibilityTests and MatrixTransposeCompatibilityTests carry expectations CNA measured on the genuine runtime; the oracle suites are BoundingSphereOracleTests and FrustumSeparationOracleTests. The disjoint-frustum cases in BoundingBoxTests and BoundingSphereTests still assert only "not Contains"; the Disjoint answers are pinned by GeometryContainmentCompatibilityTest.FrustumContainmentIsGeometricNotPointerIdentity. RayTests.cpp still carries a stale comment saying its frustum case is omitted because the function is unimplemented; the ray–frustum cases live in BoundingFrustumTests.cpp. The maintainer failure map is on Math internals: failure map.