Bounding boxes: AABB and OBB
Wrap any element in a box that is quick to build and quick to test: the world-aligned AABB and the element’s own OBB, how each is built, and when the cheap one gives false alarms.
The AABB: six numbers
var beam = Aabb.Of(new V3(0, 0, 3), new V3(6, 0, 3), new V3(6, 0.3, 3.5), new V3(0, 0.3, 3.5));var duct = new Aabb(new V3(2, -1, 3.2), new V3(2.4, 2, 3.6));var pipe = new Aabb(new V3(2, -1, 3.6), new V3(2.2, 2, 3.8)); Console.WriteLine($"beam: {beam}, size {beam.Size}");Console.WriteLine($"beam and duct overlap: {beam.Overlaps(duct)}");Console.WriteLine($"beam and pipe overlap: {beam.Overlaps(pipe)}");Console.WriteLine($"beam and pipe within 0.15 m: {beam.Inflate(0.15).Overlaps(pipe)}");Console.WriteLine($"box around beam and duct: {Aabb.Union(beam, duct)}"); readonly record struct Aabb(V3 Min, V3 Max){ public static Aabb Of(params V3[] pts) { V3 lo = pts[0], hi = pts[0]; foreach (var p in pts) { lo = new(Math.Min(lo.X, p.X), Math.Min(lo.Y, p.Y), Math.Min(lo.Z, p.Z)); hi = new(Math.Max(hi.X, p.X), Math.Max(hi.Y, p.Y), Math.Max(hi.Z, p.Z)); } return new(lo, hi); } // Overlap on X, on Y and on Z. Boxes that only touch do not count. public bool Overlaps(Aabb o) => Min.X < o.Max.X && o.Min.X < Max.X && Min.Y < o.Max.Y && o.Min.Y < Max.Y && Min.Z < o.Max.Z && o.Min.Z < Max.Z; public Aabb Inflate(double d) => new(Min - new V3(d, d, d), Max + new V3(d, d, d)); public static Aabb Union(Aabb a, Aabb b) => Of(a.Min, a.Max, b.Min, b.Max); public V3 Size => Max - Min; public override string ToString() => $"{Min} .. {Max}";} 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)})";}beam: (0, 0, 3) .. (6, 0.3, 3.5), size (6, 0.3, 0.5) beam and duct overlap: True beam and pipe overlap: False beam and pipe within 0.15 m: True box around beam and duct: (0, -1, 3) .. (6, 2, 3.6)
< means boxes that only touch, like a beam sitting on a column, are not reported; the clash detection lesson comes back to that choice.
What turning does to an AABB
var half = new V3(3, 0.15, 0.25); // a 6 x 0.3 x 0.5 beam, centred on its origin foreach (double deg in new[] { 0.0, 30, 45, 90 }){ var r = RotZ(deg); // 1: turn all 8 corners and keep the largest |x|, |y| and |z| double hx = 0, hy = 0, hz = 0; for (int i = 0; i < 8; i++) { var c = new V3(i % 2 == 0 ? -half.X : half.X, i / 2 % 2 == 0 ? -half.Y : half.Y, i < 4 ? -half.Z : half.Z); var p = Apply(r, c); hx = Math.Max(hx, Math.Abs(p.X)); hy = Math.Max(hy, Math.Abs(p.Y)); hz = Math.Max(hz, Math.Abs(p.Z)); } // 2: the shortcut, |R| times the half sizes var h = new V3( Math.Abs(r[0, 0]) * half.X + Math.Abs(r[0, 1]) * half.Y + Math.Abs(r[0, 2]) * half.Z, Math.Abs(r[1, 0]) * half.X + Math.Abs(r[1, 1]) * half.Y + Math.Abs(r[1, 2]) * half.Z, Math.Abs(r[2, 0]) * half.X + Math.Abs(r[2, 1]) * half.Y + Math.Abs(r[2, 2]) * half.Z); double grow = h.X * h.Y * h.Z / (half.X * half.Y * half.Z); Console.WriteLine($"{deg,2} deg: corners {new V3(hx, hy, hz) * 2}, shortcut {h * 2}, volume x{grow:0.0}");} static double[,] RotZ(double d){ double t = d * Math.PI / 180, c = Math.Cos(t), s = Math.Sin(t); return new[,] { { c, -s, 0 }, { s, c, 0 }, { 0, 0, 1 } };} static V3 Apply(double[,] m, V3 v) => new( m[0, 0] * v.X + m[0, 1] * v.Y + m[0, 2] * v.Z, m[1, 0] * v.X + m[1, 1] * v.Y + m[1, 2] * v.Z, m[2, 0] * v.X + m[2, 1] * v.Y + m[2, 2] * v.Z); 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)})";}0 deg: corners (6, 0.3, 0.5), shortcut (6, 0.3, 0.5), volume x1.0 30 deg: corners (5.346, 3.26, 0.5), shortcut (5.346, 3.26, 0.5), volume x9.7 45 deg: corners (4.455, 4.455, 0.5), shortcut (4.455, 4.455, 0.5), volume x11.0 90 deg: corners (0.3, 6, 0.5), shortcut (0.3, 6, 0.5), volume x1.0
The OBB: a box that turns with the element
// A 6 m beam turned 30 deg in plan, centred at (10, 5, 3)double t = 30 * Math.PI / 180;var beam = new Obb(new V3(10, 5, 3), new V3(Math.Cos(t), Math.Sin(t), 0), new V3(-Math.Sin(t), Math.Cos(t), 0), new V3(0, 0, 1), new V3(3, 0.15, 0.25)); foreach (var p in new V3[] { new(12, 6, 3), new(12, 5, 3), new(10, 5, 3.3) }) Console.WriteLine($"{p}: local {beam.ToLocal(p)}, inside {beam.Contains(p)}"); readonly record struct Obb(V3 Centre, V3 U, V3 V, V3 W, V3 Half){ public V3 ToLocal(V3 p) { var d = p - Centre; return new(V3.Dot(d, U), V3.Dot(d, V), V3.Dot(d, W)); } public bool Contains(V3 p) { var l = ToLocal(p); return Math.Abs(l.X) <= Half.X && Math.Abs(l.Y) <= Half.Y && Math.Abs(l.Z) <= Half.Z; }} 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)})";}(12, 6, 3): local (2.232, -0.134, 0), inside True (12, 5, 3): local (1.732, -1, 0), inside False (10, 5, 3.3): local (0, 0, 0.3), inside False
Where does the OBB come from?
From the family: in BIM you usually have it for free. A family instance has a local bounding box in its own coordinates and a transform that places it. The local box’s centre and half sizes, turned and moved by that transform, give an exact OBB. From the geometry: for a bare mesh, a good OBB can be found from the directions in which its points spread most (principal component analysis), or by trying the directions of its edges and keeping the smallest box. That is more work, so it is done once and stored. From a convention: for linear elements like beams, ducts and pipes, the axis of the element is the obvious U, and the section gives V and W.
| AABB | OBB | |
|---|---|---|
Show a hint
Show the solution
double l = 6, w = 0.3;for (int deg = 0; deg <= 90; deg += 15){ double t = deg * Math.PI / 180, c = Math.Abs(Math.Cos(t)), s = Math.Abs(Math.Sin(t)); double width = l * c + w * s, depth = l * s + w * c; Console.WriteLine($"{deg,2} deg: {width:0.00} x {depth:0.00} m, {width * depth / (l * w):0.0} x the beam");}0 deg: 6.00 x 0.30 m, 1.0 x the beam 15 deg: 5.87 x 1.84 m, 6.0 x the beam 30 deg: 5.35 x 3.26 m, 9.7 x the beam 45 deg: 4.45 x 4.45 m, 11.0 x the beam 60 deg: 3.26 x 5.35 m, 9.7 x the beam 75 deg: 1.84 x 5.87 m, 6.0 x the beam 90 deg: 0.30 x 6.00 m, 1.0 x the beam
Remember
A bounding box answers “could this element be involved?” before any expensive test. An AABB is the min and max of every coordinate; two of them overlap only if they overlap on X, Y and Z. Turning an element makes its AABB grow: a thin beam at 45° has an AABB about eleven times its area. The AABB of a turned box has half sizes |R| · h; boxes of boxes keep growing, so recompute from the element. An OBB (centre, three axes, three half sizes) fits at any angle; in BIM it comes from the family’s local box and its transform.