⚙️AlgorithmAdvanced

3D Geometry Basics

Key Points

  • •
    3D geometry relies on a small toolkit: vectors, dot products, cross products, and planes; mastering these unlocks most 3D problem-solving.
  • •
    Dot product measures how aligned two vectors are, while cross product gives a perpendicular vector whose length equals the area of the parallelogram they span.
  • •
    Planes are defined by a normal vector and an offset, and many queries reduce to projecting onto or intersecting with planes and lines.
  • •
    Distances in 3D often come from projecting or using areas: point–plane via projection; point–line via cross product area divided by the line’s length.
  • •
    Robustness matters: always use doubles and an epsilon tolerance to guard against floating-point errors and degeneracies.
  • •
    The signed volume via scalar triple product lets you test orientation and compute volumes; it is the foundation of many mesh algorithms.
  • •
    Line–plane and plane–plane intersections can be expressed in closed form with vector algebra and solved in O(1) time.
  • •
    Full 3D convex hulls exist in O(n log n) time but are intricate to implement; many tasks only require primitives like orientation and intersection.

Prerequisites

  • →Vector algebra (2D/3D) — Understanding vector addition, scalar multiplication, and basic properties is essential for dot and cross products.
  • →Analytic geometry (lines and planes) — Knowing how equations represent geometric objects underpins the plane equation and parameterized lines.
  • →Trigonometry and angles — Dot and cross product interpretations involve cosine and sine relationships.
  • →Floating-point arithmetic — 3D computations require careful handling of precision, tolerances, and degeneracies.
  • →Basic linear algebra — Solving small linear systems and reasoning about spans, orthogonality, and determinants aids in derivations and implementations.

Detailed Explanation

Tap terms for definitions

01Overview

3D Geometry Basics provides the essential tools to represent and compute with points, vectors, lines, and planes in three-dimensional space. At the heart are vector operations: the dot product, which measures alignment and lengths, and the cross product, which produces a vector perpendicular to two inputs and whose magnitude encodes area. With these, we can construct planes from points, compute distances, and find intersections such as where a line hits a plane or where two planes cross. Many practical problems—ray casting in rendering, collision detection in physics, spatial queries in databases, and geometric modeling—reduce to combinations of these primitives. A plane is typically written as ax + by + cz + d = 0, with the normal vector (a, b, c) pointing perpendicularly to the surface. Distances to planes or lines can be derived through projections or area formulas. The triple scalar product a · (b × c) captures signed volume and orientation; it provides both robust orientation tests (coplanarity, handedness) and formulas for volume. While implementing these operations is conceptually straightforward, numerical stability is crucial. Using double precision and epsilon tolerances helps manage edge cases like near-parallel lines or nearly coplanar points. Advanced tasks like computing 3D convex hulls build on these basics but introduce algorithmic complexity and implementation pitfalls. Mastering these fundamentals enables you to confidently tackle a wide range of 3D computational problems.

02Intuition & Analogies

Imagine vectors as arrows in space. The dot product is like asking: “How much does one arrow point in the same direction as the other?” If two arrows point the same way, their dot product is large and positive; if they are at right angles, it’s zero; if they point opposite, it’s negative. This is similar to how, when pushing a door, only the component of your push perpendicular to the hinge (aligned with the door’s motion) actually opens it. The cross product is like using a wrench: you push at a right angle to generate torque. Given two arrows on a tabletop, their cross product is an arrow sticking straight up or down, perpendicular to both. The length of this new arrow is proportional to the area of the parallelogram formed by the original two—just like how a wider grip on a wrench (larger area) generates more torque. A plane is like an infinite sheet of paper floating in space. Its normal vector is a straw poking straight through the sheet, indicating which way is “up” relative to the sheet. The plane equation ax + by + cz + d = 0 tells you whether a point is above (positive), on (zero), or below (negative) the sheet by plugging in its coordinates. Distances often come from projections: the shortest path from a point to a plane is the perpendicular drop—imagine shining a flashlight straight down onto the plane; the shadow falls directly below. The shortest distance from a point to a line is like holding a stick (the line) and measuring the shortest piece of string connecting a nearby point to the stick; that length is tied to the area of the parallelogram formed by the stick and the connecting vector, divided by the stick’s length. Signed volume via a · (b × c) is like asking which way a screw turns: it encodes both size (volume) and handedness (orientation). Add these building blocks together, and you can find where a laser (ray) hits a wall (plane), whether two walls intersect in a seam (line), and how big a 3D shape is (volume).

03Formal Definition

Let vectors be elements of \(\). For vectors \( = (,,)\) and \( = (,,)\): - Dot product: \( = + + = \\,\\), where \(\) is the angle between them. - Cross product: \( = ( - ,\; - ,\; - )\). It satisfies \(,\) and \(\ = \\,\\). A plane is the set \(\{ : + d = 0\}\) with normal \(=(a,b,c)\). Given non-collinear points \(,,\), the plane’s normal is \( = (-)(-)\). The distance from point \(\) to plane \( + d = 0\) is \(\). The distance from point \(\) to an infinite line defined by point \(\) and direction \(\) is \(\). A line can be parameterized as \((t) = + t\,\). Its intersection with plane \( + d=0\) occurs at \(t = -\), provided the denominator is nonzero. The intersection of two non-parallel planes with normals \(,\) is a line with direction \( = \). A point on that line can be written as \( = \), where \( = -\). The signed volume of a tetrahedron with vertices \(,,,\) is \(\, ()\).

04When to Use

Use 3D geometry primitives whenever you need to model or compute spatial relationships:

  • Rendering and ray tracing: ray–triangle intersections (Möller–Trumbore), shadow rays, and reflection directions rely on dot/cross products and plane intersections.
  • Physics and collision detection: closest distances (point–line/segment, point–plane) and contact normals determine collision responses and constraints.
  • CAD/3D modeling: building planes from points, computing face normals, and measuring angles/areas/volumes are core to mesh processing and solid modeling.
  • Robotics and navigation: projecting points onto planes (e.g., ground plane), computing angles between orientations, and intersecting sensor rays with environment geometry.
  • Computational geometry problems: detecting coplanarity, computing orientation via scalar triple product, and constructing convex hulls or half-space intersections. Choose these formulas when inputs are small fixed-size vectors and exactness isn’t mandatory (double precision is fine). When you need global structures (e.g., the convex hull of many points), use dedicated algorithms (incremental hull, Quickhull) but still rely on these primitives for orientation tests and plane construction. For highly degenerate or exact arithmetic needs, consider robust predicates (e.g., adaptive exact arithmetic).

⚠️Common Mistakes

  • Ignoring normalization: Using a non-unit normal with formulas that assume unit length leads to wrong distances or angles. Either normalize vectors when required or keep length factors explicit in formulas.
  • Swapping cross product order: (\mathbf{a}\times\mathbf{b} = -\mathbf{b}\times\mathbf{a}). Reversing order flips directions (normals, line directions), which can invert signs (e.g., volume, face orientation). Be consistent throughout.
  • Mishandling plane constants: For plane (\mathbf{n}\cdot\mathbf{x} + d = 0), the sign of (d) is not arbitrary. If the plane passes through point (\mathbf{p}), then (d = -\mathbf{n}\cdot\mathbf{p}). Mixing conventions produces incorrect distances and intersections.
  • Floating-point exactness assumptions: Comparing to zero without tolerance causes failures near parallel/coplanar cases. Always use an epsilon (e.g., 1e-9) to test for “near zero.”
  • Using integers for intermediate computations: Cross products and triple products can overflow 32-bit integers even for moderate coordinates. Use double (or long double) for safety unless you employ exact arithmetic libraries.
  • Forgetting direction domain: A line is infinite, but many problems involve segments or rays. After computing parameter (t), ensure it lies in the valid interval (segment: ([0,1]), ray: ([0,\infty)))).
  • Not guarding division by small numbers: In intersection formulas, denominators like (\mathbf{n}\cdot\mathbf{u}) or (|\mathbf{u}|) can be almost zero. Check and handle degeneracies (parallel, zero-length vectors) explicitly.
  • Inconsistent triangle winding: Mesh volume and normals depend on consistent vertex order (counterclockwise when viewed from outside). Inconsistent winding yields cancellation or negative volumes.

Key Formulas

Dot Product

Explanation: This computes alignment between vectors. The algebraic sum equals the product of lengths times the cosine of the angle, so you can extract angles or projections.

Cross Product

Explanation: Produces a vector perpendicular to both inputs. Its length equals the area of the parallelogram spanned by a and b, and its direction follows the right-hand rule.

Cross Magnitude

Explanation: The magnitude relates to the sine of the angle between vectors. It is useful for computing areas and perpendicular distances.

Plane Equation

Explanation: Implicitly defines a plane: points satisfying this equation lie on the plane. The vector n is the plane’s normal and d is the offset.

Plane from 3 Points

Explanation: Three non-collinear points define a plane. The cross product of two edges yields the normal vector.

Point–Plane Distance

Explanation: Drop a perpendicular from the point to the plane. The numerator measures signed offset; dividing by the normal’s length yields perpendicular distance.

Line–Plane Intersection Parameter

Explanation: Substitute the line P(t) = P0 + t u into the plane equation and solve for t. If the denominator is near zero, the line is parallel to the plane.

Plane–Plane Intersection Line

Explanation: Two non-parallel planes intersect along a line with direction u. A point on that line can be written using cross products and the planes’ offsets.

Point–Line Distance

Explanation: The area of the parallelogram formed by (p–M) and u equals base times height; solving for the height gives the perpendicular distance.

Tetrahedron Volume

Explanation: The scalar triple product gives six times the signed volume of the tetrahedron with edges a, b, c from a common vertex. Absolute value gives geometric volume.

Angle Between Vectors

Explanation: Rearranges the dot product definition to compute the angle between two vectors. Useful for measuring orientations and checking perpendicularity.

Vector Projection

Explanation: Gives the component of v along direction u. Subtracting from v yields the rejection (perpendicular component).

Complexity Analysis

Most primitive operations in 3D geometry—dot product, cross product, normalization, projections, and distance computations—are constant-time O(1) in both time and space: they involve a fixed number of arithmetic operations on three coordinates. For example, a dot product uses three multiplications and two additions; a cross product uses six multiplications and three subtractions. Intersections such as line–plane and plane–plane also run in O(1), requiring a small fixed sequence of dot/cross products and divisions, plus checks for degeneracy (near-zero denominators). Memory usage for these primitives is O(1) because they store only a constant number of doubles. When applying these primitives to collections—e.g., computing distances from n points to a plane, or testing a ray against m triangles—the total cost scales linearly with the number of elements: O(n) or O(m). A typical ray–triangle intersection via Möller–Trumbore is O(1) per triangle, so intersecting a ray with a mesh of T triangles is O(T). If spatial acceleration structures (e.g., BVH, k-d tree) are used, query time can drop to O(log T) on average, but building the structure costs O(T log T) to O(T). Global structures like 3D convex hulls require asymptotically more work. State-of-the-art algorithms typically achieve O(n log n) expected time with O(n) space, though careful implementation is needed to handle degeneracies and produce robust output. Regardless, these algorithms rely heavily on constant-time primitives (orientation tests via scalar triple products, plane construction, and intersection checks). The dominant practical considerations are numerical robustness (using tolerances to avoid false negatives/positives) and avoiding expensive operations (like repeated normalizations) when not necessary.

Code Examples

3D Vector and Plane Utilities: distances and intersections
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Vec3 {
5    double x, y, z;
6    Vec3() : x(0), y(0), z(0) {}
7    Vec3(double x_, double y_, double z_) : x(x_), y(y_), z(z_) {}
8    // Vector addition and subtraction
9    Vec3 operator+(const Vec3& o) const { return Vec3(x + o.x, y + o.y, z + o.z); }
10    Vec3 operator-(const Vec3& o) const { return Vec3(x - o.x, y - o.y, z - o.z); }
11    // Scalar multiplication and division
12    Vec3 operator*(double k) const { return Vec3(x * k, y * k, z * k); }
13    Vec3 operator/(double k) const { return Vec3(x / k, y / k, z / k); }
14    // Dot and cross
15    double dot(const Vec3& o) const { return x * o.x + y * o.y + z * o.z; }
16    Vec3 cross(const Vec3& o) const {
17        return Vec3(y * o.z - z * o.y, z * o.x - x * o.z, x * o.y - y * o.x);
18    }
19    // Norms
20    double norm2() const { return this->dot(*this); }
21    double norm()  const { return sqrt(norm2()); }
22    // Unit vector (safe)
23    Vec3 unit() const {
24        double n = norm();
25        if (n == 0) return *this; // or return some convention
26        return *this / n;
27    }
28};
29
30static const double EPS = 1e-9;
31
32struct Plane {
33    // Plane in form n·x + d = 0
34    Vec3 n; // normal
35    double d; // offset
36};
37
38// Build plane from 3 non-collinear points
39Plane plane_from_points(const Vec3& A, const Vec3& B, const Vec3& C) {
40    Vec3 n = (B - A).cross(C - A);
41    // It is okay if n is not unit; formulas below handle general length
42    double d = -n.dot(A);
43    return {n, d};
44}
45
46// Signed distance from point P to plane (positive on the side of n)
47double signed_distance_point_plane(const Vec3& P, const Plane& pl) {
48    return (pl.n.dot(P) + pl.d) / max(EPS, pl.n.norm());
49}
50
51// Absolute (geometric) distance from point to plane
52double distance_point_plane(const Vec3& P, const Plane& pl) {
53    return fabs(pl.n.dot(P) + pl.d) / max(EPS, pl.n.norm());
54}
55
56// Point-line distance: line defined by point M and direction dir
57double distance_point_line(const Vec3& P, const Vec3& M, const Vec3& dir) {
58    double denom = max(EPS, dir.norm());
59    return (P - M).cross(dir).norm() / denom;
60}
61
62// Line-plane intersection: line P(t) = P0 + t*dir. Returns (has_intersection, t, point)
63struct LinePlaneHit { bool ok; double t; Vec3 point; };
64LinePlaneHit intersect_line_plane(const Vec3& P0, const Vec3& dir, const Plane& pl) {
65    double denom = pl.n.dot(dir);
66    if (fabs(denom) < EPS) {
67        // Parallel: either no intersection or the line lies in plane
68        // Check if P0 lies in plane
69        double val = pl.n.dot(P0) + pl.d;
70        if (fabs(val) < 1e-8) return {true, numeric_limits<double>::infinity(), P0};
71        return {false, 0.0, Vec3()};
72    }
73    double t = -(pl.n.dot(P0) + pl.d) / denom;
74    Vec3 P = P0 + dir * t;
75    return {true, t, P};
76}
77
78// Plane-plane intersection: returns whether they intersect in a line and, if so, a point and direction
79struct PlanePlaneLine { bool ok; Vec3 point; Vec3 dir; };
80PlanePlaneLine intersect_plane_plane(const Plane& p1, const Plane& p2) {
81    Vec3 u = p1.n.cross(p2.n); // direction of intersection line
82    double u2 = u.norm2();
83    if (u2 < EPS*EPS) {
84        // Parallel or coincident
85        // If normals are parallel, check offsets for coincidence
86        Vec3 n1 = p1.n, n2 = p2.n;
87        // If they are parallel and d matches proportionally, treat as coincident (many solutions)
88        // For simplicity, report no unique line
89        return {false, Vec3(), Vec3()};
90    }
91    // Solve for a point on the line using formula with c_i = -d_i
92    double c1 = -p1.d, c2 = -p2.d;
93    Vec3 p0 = ( (p2.n.cross(u)) * c1 + (u.cross(p1.n)) * c2 ) / u2;
94    return {true, p0, u};
95}
96
97int main() {
98    // Example usage
99    Vec3 A(0,0,0), B(1,0,0), C(0,1,0); // xy-plane triangle
100    Plane pl = plane_from_points(A,B,C); // plane z=0 with some scaling of normal
101
102    Vec3 P(0.2, 0.3, 5.0);
103    cout.setf(std::ios::fixed); cout<<setprecision(6);
104    cout << "Distance point-plane: " << distance_point_plane(P, pl) << "\n";
105
106    // Line: passes through (0,0,10) going toward negative z-axis
107    Vec3 P0(0,0,10), dir(0,0,-1);
108    auto hit = intersect_line_plane(P0, dir, pl);
109    if (hit.ok && isfinite(hit.t)) {
110        cout << "Line-plane intersection at t=" << hit.t << ": ("
111             << hit.point.x << ", " << hit.point.y << ", " << hit.point.z << ")\n";
112    }
113
114    // Plane-plane intersection: z=0 and x=0 -> y-axis line
115    Plane p1 = pl; // z=0
116    Plane p2{Vec3(1,0,0), 0}; // x=0
117    auto line = intersect_plane_plane(p1, p2);
118    if (line.ok) {
119        cout << "Plane-plane dir: (" << line.dir.x << ", " << line.dir.y << ", " << line.dir.z << ")\n";
120        cout << "A point on the line: (" << line.point.x << ", " << line.point.y << ", " << line.point.z << ")\n";
121    }
122
123    // Point-line distance: distance from (1,1,1) to z-axis line through origin
124    Vec3 M(0,0,0), zdir(0,0,1), Q(1,1,1);
125    cout << "Distance point-line: " << distance_point_line(Q, M, zdir) << "\n";
126
127    return 0;
128}
129

Defines a 3D vector type with dot, cross, and norm operations; constructs planes from three points; computes distances from a point to a plane and to a line; finds line–plane and plane–plane intersections. The main function demonstrates usage with the xy-plane, a vertical ray, and intersecting coordinate planes.

Time: O(1) per query (each function does a constant number of arithmetic operations).Space: O(1) auxiliary memory (a handful of Vec3 temporaries).
Ray–Triangle Intersection (Möller–Trumbore)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Vec3 { double x,y,z; Vec3() : x(0),y(0),z(0){} Vec3(double X,double Y,double Z):x(X),y(Y),z(Z){}
5    Vec3 operator+(const Vec3& o) const { return Vec3(x+o.x,y+o.y,z+o.z);} 
6    Vec3 operator-(const Vec3& o) const { return Vec3(x-o.x,y-o.y,z-o.z);} 
7    Vec3 operator*(double k) const { return Vec3(x*k,y*k,z*k);} 
8    double dot(const Vec3& o) const { return x*o.x + y*o.y + z*o.z; }
9    Vec3 cross(const Vec3& o) const { return Vec3(y*o.z - z*o.y, z*o.x - x*o.z, x*o.y - y*o.x); }
10};
11
12static const double EPS = 1e-9;
13
14// Returns (hit, t, u, v, intersection_point). If cull_backfaces=true, ignores intersections from the back side.
15struct RayTriHit { bool hit; double t,u,v; Vec3 P; };
16RayTriHit ray_triangle_mt(const Vec3& orig, const Vec3& dir, const Vec3& v0, const Vec3& v1, const Vec3& v2, bool cull_backfaces=false) {
17    Vec3 e1 = v1 - v0;
18    Vec3 e2 = v2 - v0;
19    Vec3 pvec = dir.cross(e2);
20    double det = e1.dot(pvec);
21
22    if (cull_backfaces) {
23        if (det < EPS) return {false,0,0,0,Vec3()};
24    } else {
25        if (fabs(det) < EPS) return {false,0,0,0,Vec3()};
26    }
27
28    double invDet = 1.0 / det;
29    Vec3 tvec = orig - v0;
30    double u = tvec.dot(pvec) * invDet;
31    if (u < 0.0 - 1e-12 || u > 1.0 + 1e-12) return {false,0,0,0,Vec3()};
32
33    Vec3 qvec = tvec.cross(e1);
34    double v = dir.dot(qvec) * invDet;
35    if (v < 0.0 - 1e-12 || u + v > 1.0 + 1e-12) return {false,0,0,0,Vec3()};
36
37    double t = e2.dot(qvec) * invDet;
38    if (t < 0.0) return {false,0,0,0,Vec3()}; // ray only (t >= 0)
39
40    Vec3 P = orig + dir * t;
41    return {true, t, u, v, P};
42}
43
44int main(){
45    // Define a triangle in the plane z=0
46    Vec3 v0(0,0,0), v1(1,0,0), v2(0,1,0);
47    // Define a ray from (0.2,0.2, 1) pointing downward
48    Vec3 O(0.2, 0.2, 1.0), D(0,0,-1);
49
50    auto hit = ray_triangle_mt(O, D, v0, v1, v2, false);
51    if (hit.hit) {
52        cout.setf(std::ios::fixed); cout<<setprecision(6);
53        cout << "Hit at t=" << hit.t << " point=("
54             << hit.P.x << ", " << hit.P.y << ", " << hit.P.z << ")\n";
55        cout << "Barycentric (u,v,w) = (" << hit.u << ", " << hit.v << ", " << (1-hit.u-hit.v) << ")\n";
56    } else {
57        cout << "No intersection\n";
58    }
59    return 0;
60}
61

Implements the Möller–Trumbore algorithm to intersect a ray with a triangle without explicitly building the plane. It computes edge vectors, uses cross/dot products to solve for barycentric coordinates, and returns the hit time t and location. The optional backface culling flag filters hits from the back side of the triangle.

Time: O(1) per intersection query.Space: O(1) auxiliary memory.
Signed Volume via Scalar Triple Product and Mesh Volume
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Vec3 { double x,y,z; Vec3() : x(0),y(0),z(0){} Vec3(double X,double Y,double Z):x(X),y(Y),z(Z){}
5    Vec3 operator+(const Vec3& o) const { return Vec3(x+o.x,y+o.y,z+o.z);} 
6    Vec3 operator-(const Vec3& o) const { return Vec3(x-o.x,y-o.y,z-o.z);} 
7    Vec3 operator*(double k) const { return Vec3(x*k,y*k,z*k);} 
8    double dot(const Vec3& o) const { return x*o.x + y*o.y + z*o.z; }
9    Vec3 cross(const Vec3& o) const { return Vec3(y*o.z - z*o.y, z*o.x - x*o.z, x*o.y - y*o.x); }
10};
11
12// Signed volume of tetrahedron (O as origin)
13double signed_tet_volume(const Vec3& A, const Vec3& B, const Vec3& C) {
14    // V = (1/6) * A · (B × C)
15    return (1.0/6.0) * A.dot(B.cross(C));
16}
17
18// Volume of a closed triangle mesh (assuming outward-facing consistent winding)
19double mesh_volume(const vector<array<Vec3,3>>& tris) {
20    // Sum signed volumes of tetrahedra (O, v0, v1, v2)
21    long double acc = 0.0L;
22    for (const auto& t : tris) {
23        const Vec3 &v0 = t[0], &v1 = t[1], &v2 = t[2];
24        long double vol6 = (long double)v0.x * ( (long double)v1.y * v2.z - (long double)v1.z * v2.y )
25                         - (long double)v0.y * ( (long double)v1.x * v2.z - (long double)v1.z * v2.x )
26                         + (long double)v0.z * ( (long double)v1.x * v2.y - (long double)v1.y * v2.x );
27        acc += vol6; // equals 6 * signed_tet_volume(v0,v1,v2)
28    }
29    return (double)(acc / 6.0L);
30}
31
32int main(){
33    // Build a unit cube [0,1]^3 using 12 triangles (each face split in 2)
34    vector<Vec3> V = {
35        {0,0,0},{1,0,0},{1,1,0},{0,1,0}, // bottom z=0
36        {0,0,1},{1,0,1},{1,1,1},{0,1,1}  // top z=1
37    };
38    auto tri = [&](int a,int b,int c){ return array<Vec3,3>{V[a],V[b],V[c]}; };
39    vector<array<Vec3,3>> tris;
40    // bottom (CCW seen from below? We want outward normals; bottom faces point downwards)
41    tris.push_back(tri(0,2,1)); tris.push_back(tri(0,3,2));
42    // top (z=1), outward normal +z
43    tris.push_back(tri(4,5,6)); tris.push_back(tri(4,6,7));
44    // front (y=0)
45    tris.push_back(tri(0,1,5)); tris.push_back(tri(0,5,4));
46    // back (y=1)
47    tris.push_back(tri(3,7,6)); tris.push_back(tri(3,6,2));
48    // left (x=0)
49    tris.push_back(tri(0,4,7)); tris.push_back(tri(0,7,3));
50    // right (x=1)
51    tris.push_back(tri(1,2,6)); tris.push_back(tri(1,6,5));
52
53    double Vcube = mesh_volume(tris);
54    cout.setf(std::ios::fixed); cout<<setprecision(6);
55    cout << "Computed cube volume: " << Vcube << " (expected 1.0)\n";
56
57    // Demonstrate single tetrahedron volume (O, A, B, C)
58    Vec3 A(1,0,0), B(0,1,0), C(0,0,1);
59    cout << "Signed volume of tetrahedron OABC: " << signed_tet_volume(A,B,C) << " (expected 1/6)\n";
60
61    return 0;
62}
63

Uses the scalar triple product to compute signed volumes. The mesh volume function sums the signed volumes of tetrahedra formed by the origin and each triangle; for a closed, consistently oriented surface, the sum equals the enclosed volume. A cube test verifies correctness; a simple tetrahedron check shows the 1/6 relation.

Time: O(T) for a mesh with T triangles.Space: O(1) auxiliary memory beyond the triangle list.