<style> .reveal-up, .reveal-left, .reveal-right, .reveal-stagger > * { opacity: 1 !important; transform: none !important; } </style>
  1. Learn
  2. BIM Math
  3. 3D geometry and solids
All lessons in this course

Foundations

Vectors

Lines and curves

Planes and polygons

Matrices and transforms

Rotations in depth

3D geometry and solids

Master level

Lesson 35 of 44 15 minAdvanced

Ray–triangle intersection

Find where a ray meets a triangle with the Möller–Trumbore method, read the answer as barycentric weights, and use it for picking, terrain heights and inside/outside tests.

Click on a wall in a 3D view and the program has to work out which element is under the mouse. It does that by shooting a ray (a start point O and a direction d, from the lines lesson: P(t) = O + t·d with t ≥ 0) from the eye through the cursor, and finding the first triangle it hits. The same test drops a point onto a terrain surface, checks whether a sight line from a window is blocked, and decides whether a point is inside a solid.

Interactive

Does the ray hit the triangle?

ABCO
det = e₁ · (d × e₂)48.240
t1.000
plane point(0, 0.2, 1)
resulthit
Hit at t = 1.00. The point is w·A + u·B + v·C with all three weights between 0 and 1 and adding up to 1, so it lies inside the triangle.

Two questions in one

Hitting a triangle means two things: the ray meets the triangle’s plane in front of its origin (t > 0), and the meeting point lies inside the triangle. You could solve them separately (line–plane intersection from the planes module, then a point-in-triangle test), but there is a neater way that answers both at once.

Barycentric coordinates

Every point P in the plane of a triangle ABC can be written as P = w·A + u·B + v·C with w + u + v = 1. The three weights are its barycentric coordinates. At A they are (1, 0, 0), at the middle of edge BC (0, ½, ½), at the centroid (⅓, ⅓, ⅓). P is inside the triangle exactly when all three are between 0 and 1. A negative weight says which edge P is beyond: the one opposite that corner. The bars in the widget show this as you aim.

Since w = 1 − u − v, P = A + u·(B − A) + v·(C − A). Setting that equal to the ray, O + t·d = A + u·e₁ + v·e₂ with e₁ = B − A and e₂ = C − A, gives three equations (x, y and z) for three unknowns t, u and v.

Möller–Trumbore

Solving those equations with Cramer’s rule, and reusing cross products, gives the method Tomas Möller and Ben Trumbore published in 1997. It is still the standard. Its determinant det = e₁ · (d × e₂) is zero when the ray is parallel to the plane, and its sign says whether the ray hits the front or the back of the triangle.

RayTriangle.cs
V3 a = new(0, -2, 0), b = new(0, 2, 0.3), c = new(0, -0.4, 2.8);   // a panel in the plane x = 0var o = new V3(4.5, -1.2, 2.4); var rays = new (string Name, V3 O, V3 D)[]{    ("aimed at (0, 0.2, 1)", o, new V3(0, 0.2, 1) - o),    ("aimed at (0, 1.6, 2)", o, new V3(0, 1.6, 2) - o),    ("pointing away", o, o - new V3(0, 0.2, 1)),    ("parallel to the panel", new V3(1.2, -3.2, 1.2), new V3(0, 1, 0.15))};foreach (var (name, ro, d) in rays)    Console.WriteLine(Intersect(ro, d, a, b, c) is double t ? $"{name}: hit at t = {t:0.###}, point {ro + d * t}" : $"{name}: miss"); static double? Intersect(V3 o, V3 d, V3 a, V3 b, V3 c){    const double Eps = 1e-12;    V3 e1 = b - a, e2 = c - a;    V3 p = V3.Cross(d, e2);    double det = V3.Dot(e1, p);    if (Math.Abs(det) < Eps) return null;          // parallel to the plane     double inv = 1 / det;    V3 s = o - a;    double u = V3.Dot(s, p) * inv;                  // weight of B    if (u < 0 || u > 1) return null;     V3 q = V3.Cross(s, e1);    double v = V3.Dot(d, q) * inv;                  // weight of C    if (v < 0 || u + v > 1) return null;     double t = V3.Dot(e2, q) * inv;                 // distance along the ray, in units of d    return t > Eps ? t : null;                      // only in front of the origin} readonly record struct V3(double X, double Y, double Z){    public static V3 operator +(V3 a, V3 b) => new(a.X + b.X, a.Y + b.Y, a.Z + b.Z);    public static V3 operator -(V3 a, V3 b) => new(a.X - b.X, a.Y - b.Y, a.Z - b.Z);    public static V3 operator *(V3 v, double k) => new(v.X * k, v.Y * k, v.Z * k);    public static double Dot(V3 a, V3 b) => a.X * b.X + a.Y * b.Y + a.Z * b.Z;    public static V3 Cross(V3 a, V3 b) =>        new(a.Y * b.Z - a.Z * b.Y, a.Z * b.X - a.X * b.Z, a.X * b.Y - a.Y * b.X);    public double Length => Math.Sqrt(Dot(this, this));    public V3 Normalized() => this * (1 / Length);    static string F(double v) => Math.Abs(v) < 5e-4 ? "0" : v.ToString("0.###");    public override string ToString() => $"({F(X)}, {F(Y)}, {F(Z)})";}
Output
aimed at (0, 0.2, 1): hit at t = 1, point (0, 0.2, 1)
aimed at (0, 1.6, 2): miss
pointing away: miss
parallel to the panel: miss

Notice the early exits: most triangles a ray is tested against are misses, and the method gives up as soon as u or v is out of range, before computing t. The ray “pointing away” passes through the same panel point but at t = −1, behind its origin, so it is a miss.

The nearest hit, and weights as an interpolator

Against a whole mesh, test every triangle and keep the smallest positive t: that is the surface the eye sees first. The barycentric weights are useful beyond the inside test: any value stored at the three corners (a height, a colour, a normal, a temperature) can be blended at the hit point as w·value_A + u·value_B + v·value_C. A terrain surface (a TIN, triangulated irregular network) uses exactly this to find the ground level under a point:

TerrainHeight.cs
// Two triangles of a surveyed terrain surfacevar pts = new V3[] { new(0, 0, 10.2), new(20, 0, 11.0), new(20, 20, 12.6), new(0, 20, 10.8) };var tris = new[] { (0, 1, 2), (0, 2, 3) }; foreach (var (x, y) in new[] { (5.0, 2.0), (12.0, 15.0), (25.0, 5.0) }){    var o = new V3(x, y, 1000);                       // drop a ray straight down    var d = new V3(0, 0, -1);    double? best = null;    foreach (var (i, j, k) in tris)        if (Intersect(o, d, pts[i], pts[j], pts[k]) is double t && (best is null || t < best)) best = t;    Console.WriteLine(best is double tb ? $"({x}, {y}): ground at z = {1000 - tb:0.###}" : $"({x}, {y}): outside the survey");} static double? Intersect(V3 o, V3 d, V3 a, V3 b, V3 c){    V3 e1 = b - a, e2 = c - a, p = V3.Cross(d, e2);    double det = V3.Dot(e1, p);    if (Math.Abs(det) < 1e-12) return null;    double inv = 1 / det;    V3 s = o - a;    double u = V3.Dot(s, p) * inv;    if (u < 0 || u > 1) return null;    V3 q = V3.Cross(s, e1);    double v = V3.Dot(d, q) * inv;    if (v < 0 || u + v > 1) return null;    double t = V3.Dot(e2, q) * inv;    return t > 1e-12 ? t : null;} readonly record struct V3(double X, double Y, double Z){    public static V3 operator +(V3 a, V3 b) => new(a.X + b.X, a.Y + b.Y, a.Z + b.Z);    public static V3 operator -(V3 a, V3 b) => new(a.X - b.X, a.Y - b.Y, a.Z - b.Z);    public static V3 operator *(V3 v, double k) => new(v.X * k, v.Y * k, v.Z * k);    public static double Dot(V3 a, V3 b) => a.X * b.X + a.Y * b.Y + a.Z * b.Z;    public static V3 Cross(V3 a, V3 b) =>        new(a.Y * b.Z - a.Z * b.Y, a.Z * b.X - a.X * b.Z, a.X * b.Y - a.Y * b.X);    public double Length => Math.Sqrt(Dot(this, this));    public V3 Normalized() => this * (1 / Length);    static string F(double v) => Math.Abs(v) < 5e-4 ? "0" : v.ToString("0.###");    public override string ToString() => $"({F(X)}, {F(Y)}, {F(Z)})";}
Output
(5, 2): ground at z = 10.56
(12, 15): ground at z = 11.73
(25, 5): outside the survey

Speed: not every triangle

A model with ten million triangles cannot test every one for every mouse move. Real picking first tests the ray against bounding boxes, using a bounding volume hierarchy (BVH) or another spatial index from the DSA course’s spatial indexes lesson, and only runs Möller–Trumbore on the few triangles inside the boxes the ray passes through.

Quick check

Möller–Trumbore returns u = 0.6 and v = 0.5 for a hit with t = 3. What does that mean?

Quick check

Why does a pick ray keep the smallest positive t rather than any hit?

Practice

Decide whether a point is inside a closed mesh by casting a ray from it and counting how many triangles it crosses: an odd count means inside. Use Mesh.Box(4, 3, 2.5) and test (2, 1.5, 1), (5, 1, 1), (1, 1, 2.4) and (2, 1.5, −0.5). Use the direction (1, 0.123, 0.0371) so the ray does not run exactly along an edge.

Show a hint

Reuse Intersect from RayTriangle.cs and count every triangle it returns a value for, not just the nearest.

Show the solution
Solution.cs
var box = Mesh.Box(4, 3, 2.5);var dir = new V3(1, 0.123, 0.0371); foreach (var p in new V3[] { new(2, 1.5, 1), new(5, 1, 1), new(1, 1, 2.4), new(2, 1.5, -0.5) }){    int hits = box.F.Count(t => Intersect(p, dir, box.V[t.A], box.V[t.B], box.V[t.C]) is not null);    Console.WriteLine($"{p}: {hits} crossing{(hits == 1 ? "" : "s")} -> {(hits % 2 == 1 ? "inside" : "outside")}");} static double? Intersect(V3 o, V3 d, V3 a, V3 b, V3 c){    V3 e1 = b - a, e2 = c - a, p = V3.Cross(d, e2);    double det = V3.Dot(e1, p);    if (Math.Abs(det) < 1e-12) return null;    double inv = 1 / det;    V3 s = o - a;    double u = V3.Dot(s, p) * inv;    if (u < 0 || u > 1) return null;    V3 q = V3.Cross(s, e1);    double v = V3.Dot(d, q) * inv;    if (v < 0 || u + v > 1) return null;    double t = V3.Dot(e2, q) * inv;    return t > 1e-12 ? t : null;} sealed class Mesh{    public readonly List<V3> V = new();    public readonly List<(int A, int B, int C)> F = new();   // counter-clockwise seen from outside     public static Mesh Box(double lx, double ly, double lz) =>        Prism(new[] { (0.0, 0.0), (lx, 0.0), (lx, ly), (0.0, ly) }, lz);     // A counter-clockwise footprint extruded up by h (floor and roof fanned from corner 0)    public static Mesh Prism((double X, double Y)[] poly, double h)    {        var m = new Mesh();        int n = poly.Length;        foreach (var (x, y) in poly) m.V.Add(new V3(x, y, 0));        foreach (var (x, y) in poly) m.V.Add(new V3(x, y, h));        for (int k = 1; k < n - 1; k++)        {            m.F.Add((0, k + 1, k));                 // floor, facing down            m.F.Add((n, n + k, n + k + 1));         // roof, facing up        }        for (int i = 0; i < n; i++)        {            int j = (i + 1) % n;            m.F.Add((i, j, j + n));                 // each wall as two triangles            m.F.Add((i, j + n, i + n));        }        return m;    }     public static Mesh Pyramid(double b, double h)    {        var m = new Mesh();        m.V.AddRange(new V3[] { new(0, 0, 0), new(b, 0, 0), new(b, b, 0), new(0, b, 0), new(b / 2, b / 2, h) });        m.F.AddRange(new[] { (0, 1, 4), (1, 2, 4), (2, 3, 4), (3, 0, 4), (0, 2, 1), (0, 3, 2) });        return m;    }     // (b - a) x (c - a): points out of the solid, and its length is twice the triangle's area    public V3 Normal((int A, int B, int C) t) => V3.Cross(V[t.B] - V[t.A], V[t.C] - V[t.A]);} readonly record struct V3(double X, double Y, double Z){    public static V3 operator +(V3 a, V3 b) => new(a.X + b.X, a.Y + b.Y, a.Z + b.Z);    public static V3 operator -(V3 a, V3 b) => new(a.X - b.X, a.Y - b.Y, a.Z - b.Z);    public static V3 operator *(V3 v, double k) => new(v.X * k, v.Y * k, v.Z * k);    public static double Dot(V3 a, V3 b) => a.X * b.X + a.Y * b.Y + a.Z * b.Z;    public static V3 Cross(V3 a, V3 b) =>        new(a.Y * b.Z - a.Z * b.Y, a.Z * b.X - a.X * b.Z, a.X * b.Y - a.Y * b.X);    public double Length => Math.Sqrt(Dot(this, this));    public V3 Normalized() => this * (1 / Length);    static string F(double v) => Math.Abs(v) < 5e-4 ? "0" : v.ToString("0.###");    public override string ToString() => $"({F(X)}, {F(Y)}, {F(Z)})";}
Output
(2, 1.5, 1): 1 crossing -> inside
(5, 1, 1): 0 crossings -> outside
(1, 1, 2.4): 1 crossing -> inside
(2, 1.5, -0.5): 0 crossings -> outside

Remember

  • A ray O + t·d hits a triangle when t > 0 and the plane point is inside the triangle.
  • Barycentric weights (w, u, v) add up to 1; the point is inside when all three are between 0 and 1.
  • Möller–Trumbore finds t, u and v together; det = e₁ · (d × e₂) is zero for a parallel ray.
  • For picking keep the smallest positive t; the weights also interpolate values such as terrain heights.
  • Counting crossings tells inside from outside; edge hits need care, and big models need a BVH first.
0 of 44 lessons completed