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

CNA snapshot 009d40f5  ·  Deep Dives › Framework core  ·  source links pinned to 009d40f5

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, tolerances and, in a few places, answers that differ from the genuine XNA 4.0 implementation. This page gives the exact semantics per type — half-space conventions, corner order, what "touching" means, which tolerance applies — and marks every place where CNA and XNA 4.0 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.

PlaneIntersectionType::Front means the whole volume lies on the positive side (the side the normal points to), Back the negative side and Intersecting both. Plane::IntersectsPoint returns Front for a positive distance, Back for a negative one and Intersecting for exactly zero; 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. All four agree with XNA 4.0. The Doxygen comments in PlaneIntersectionType.hpp state the opposite meanings (Front "in the negative half-space"); trust the behaviour, not those two comments (recorded on Known Issues).

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. XNA 4.0 inverts M and then reads the rows of the inverse directly, which amounts to the same thing without an explicit transpose. CNA's Plane::Transform(plane, matrix) inverts and then calls Matrix::Transpose(transformedMatrix, transformedMatrix) with one object as both source and destination. That overload is not safe to alias (see output-reference overloads): it symmetrises the inverse from its lower triangle instead of transposing it. The two agree only when the inverse is symmetric — the identity and pure axis-aligned scales — which is exactly what the two existing tests use (PlaneTest.TransformByIdentityMatrixUnchanged and its output-reference twin). Worked cases, derived by hand from the assignment order:

• The plane y = 1 moved by CreateTranslation(1, 0, 0) should be unchanged. The inverse has M41 = −1; after the aliased call M14 is −1 as well, and the result is Normal (1, 1, 0), D = −1: a translation tilts the plane by 45 degrees and leaves it unnormalised.
• The plane y = 2 rotated by CreateRotationZ(PiOver2) should have normal (−1, 0, 0); the aliased call gives (1, 0, 0), the wrong side.

Plane::Transform(plane, quaternion) is not affected: it rotates the normal with Vector3::Transform and keeps D, which is correct for a normalised plane. Nothing else in CNA calls the matrix overload (the frustum derives its planes from the matrix directly, and the effects compute their world inverse-transpose into separate objects), so the damage lands only in games and bindings that transform planes themselves. Until the implementation changes, transpose into a separate object:

Plane TransformPlane(const Plane& plane, const Matrix& transform)
{
    const Matrix inverseTranspose = Matrix::Transpose(Matrix::Invert(transform)); // distinct objects
    return Plane(Vector4::Transform(Vector4(plane.Normal, plane.D), inverseTranspose));
}

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 and plane 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 compared with XNA 4.0:

The frustum row is the important one: a ray from a camera or light outside a frustum that points straight into it is reported as a miss. For the frustum built from CreateLookAt((0, 0, 10), Zero, Up) * CreatePerspectiveFieldOfView(PiOver4, 1, 1, 100), a ray from (0, 0, 20) along −Z enters at the near plane (z = 9), so XNA answers 11 and CNA answers "no hit". Intersect such rays with a proxy BoundingBox or BoundingSphere, or clip against the six planes yourself (getNearProperty() … getBottomProperty()). These limitations are recorded on Known Issues. A nearest-hit picking loop over boxes, syntax-checked against the TARGET headers:

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.

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. Contains(BoundingFrustum) classifies the frustum by testing its corners against the box and never returns Disjoint: a frustum entirely separate from the box is reported as Intersects, and one whose corner 0 alone lies outside the box is reported as Contains. XNA first asks frustum.Intersects(box). The source comment calls the code "legacy behavior"; FNA's original carries a "TODO". Ask the frustum first, as in the sphere workaround below.
• Construction. CreateFromPoints takes a std::vector<Vector3> and throws System::ArgumentException for an empty one; CreateFromSphere and CreateMerged are exact min/max operations.

BoundingSphere

• 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 std::invalid_argument (the box throws a different family). 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 strictly inside, Disjoint strictly outside and Intersects for a point exactly on the surface. XNA never answers Intersects for a point: on the surface it answers Disjoint.
• Contains(BoundingSphere) compares squared distances with (R + r)² and (R − r)². Because the second square loses the sign of R − r, a larger sphere around the same centre is reported as Contains: BoundingSphere(Vector3::Zero, 1).Contains(BoundingSphere(Vector3::Zero, 5)) is Contains in CNA and Intersects in XNA, which tests R − r ≥ d. The same happens whenever the argument is the larger sphere and encloses this one (distance ≤ r − R): CNA answers Contains, XNA Intersects. The code is FNA's.
• Contains(BoundingFrustum) returns Contains when all eight corners are inside and otherwise always Intersects: its distance accumulator is declared as 0 and never computed, so Disjoint is unreachable. XNA asks frustum.Intersects(sphere) first.

The first-ask-the-frustum workaround for both containment defects, syntax-checked:

ContainmentType SphereContainsFrustum(const BoundingSphere& sphere, const BoundingFrustum& frustum)
{
    if (!frustum.Intersects(sphere))
        return ContainmentType::Disjoint;
    for (const Vector3& corner : frustum.GetCorners())
        if (Vector3::DistanceSquared(corner, sphere.Center) > sphere.Radius * sphere.Radius)
            return ContainmentType::Intersects;
    return ContainmentType::Contains;
}

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) returns Disjoint as soon as a plane distance is positive, and when a distance is exactly 0 it answers Intersects and stops, without testing the remaining planes. A point on one plane's extension but outside a later plane is therefore Intersects, and a point on the boundary is Intersects. XNA answers Disjoint only for a distance above 1e-5 and otherwise Contains: points on or within 1e-5 of the boundary are inside, and a point is never Intersects.
• Contains(BoundingBox), Contains(BoundingSphere) classify the volume against each plane: any Front means Disjoint, any Intersecting means Intersects, otherwise Contains. 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) are defined as Contains(…) != Disjoint, so they inherit that conservatism. XNA runs an exact GJK distance query for these two, so in the edge and corner cases above XNA answers false where CNA answers true. For culling the difference only draws a few extra objects; for collision it is a false positive. BoundingBox::Intersects(frustum) and BoundingSphere::Intersects(frustum) delegate here, and so do the frustum-culling helpers of the engine layer.
• 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.
• Contains(BoundingFrustum) classifies the other frustum's corners against this frustum's planes and returns Contains for the same object (this == &frustum).
• GetCorners(std::vector<Vector3>&) throws std::out_of_range below eight elements; PlaneCount is private. Equality and GetHashCode use only the matrix.

Containment and intersection answers at a glance

None of the unfinished functions carries a TODO marker in CNA (FNA's own markers were replaced by neutral comments such as "Legacy behavior"), so a marker search of the math module reports no gaps. Semantic tests, not marker searches, find these. The mismatches are recorded on Known Issues; the argument-exception families are listed on Math value types: argument errors.

Evidence

Checked by reading the TARGET sources and tests at 009d40f5; nothing was built or run, and the worked values 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); FNA was read at b355124 to locate the origin of the ported code. Test coverage: BoundingBoxTests, BoundingSphereTests, BoundingFrustumTests, PlaneTests and RayTests are analytic unit tests; the only oracle in this area is the CreateFromPoints corpus. The disjoint-frustum tests assert only "not Contains", the ray–frustum tests cover inside and behind origins, and RayTests.cpp notes that its frustum case is omitted. The maintainer failure map is on Math internals: failure map.