Clash detection and the separating-axis theorem
Find elements that run into each other: a cheap broad phase with boxes, then an exact test for convex shapes based on the separating-axis theorem, with tolerances for touching and clearance.
Broad phase: compare cheap bounding boxes, using sorting or a spatial index, to find the few pairs that might touch. Narrow phase: run an exact test on those candidate pairs only.
Broad phase: sweep and prune
var items = new (string Name, double X0, double X1, double Y0, double Y1, double Z0, double Z1)[]{ ("beam B1", 0, 6, 0, 0.3, 3.0, 3.5), ("duct D1", 2, 2.4, -1, 2, 3.2, 3.6), ("pipe P1", 2, 2.2, -1, 2, 3.6, 3.8), ("column C1", 5.8, 6.2, -0.1, 0.3, 0, 3.0), ("beam B2", 7, 13, 0, 0.3, 3.0, 3.5), ("duct D2", 12, 12.4, -1, 2, 3.3, 3.7)}; var order = items.OrderBy(i => i.X0).ToArray();int tests = 0;for (int i = 0; i < order.Length; i++) for (int j = i + 1; j < order.Length && order[j].X0 < order[i].X1; j++) { tests++; var (a, b) = (order[i], order[j]); if (a.Y0 < b.Y1 && b.Y0 < a.Y1 && a.Z0 < b.Z1 && b.Z0 < a.Z1) Console.WriteLine($"candidate: {a.Name} and {b.Name}"); }Console.WriteLine($"{tests} box tests instead of {items.Length * (items.Length - 1) / 2}");candidate: beam B1 and duct D1 candidate: beam B2 and duct D2 5 box tests instead of 15
The separating-axis theorem
var duct = new Rect(new P2(3.4, 3.2), 2.2, 0.8, 20); foreach (var (x, y, deg) in new[] { (6.0, 4.0, 60.0), (7.0, 4.6, 60.0), (6.4, 5.4, 30.0) }) Console.WriteLine($"B at ({x}, {y}), {deg} deg: {Sat(duct, new Rect(new P2(x, y), 1.3, 0.6, deg))}"); static string Sat(Rect a, Rect b){ var axes = new[] { ("A1", a.U), ("A2", a.V), ("B1", b.U), ("B2", b.V) }; double least = double.MaxValue; string leastName = ""; foreach (var (name, ax) in axes) { var (a0, a1) = a.Project(ax); var (b0, b1) = b.Project(ax); double overlap = Math.Min(a1, b1) - Math.Max(a0, b0); if (overlap <= 0) return $"apart (gap {-overlap:0.00} on {name})"; if (overlap < least) (least, leastName) = (overlap, name); } return $"clash (smallest overlap {least:0.00} on {leastName})";} readonly record struct P2(double X, double Y); readonly record struct Rect(P2 C, double Hx, double Hy, double Deg){ double T => Deg * Math.PI / 180; public P2 U => new(Math.Cos(T), Math.Sin(T)); public P2 V => new(-Math.Sin(T), Math.Cos(T)); public (double, double) Project(P2 ax) { double c = C.X * ax.X + C.Y * ax.Y; double r = Hx * Math.Abs(U.X * ax.X + U.Y * ax.Y) + Hy * Math.Abs(V.X * ax.X + V.Y * ax.Y); return (c - r, c + r); }}B at (6, 4), 60 deg: clash (smallest overlap 0.78 on B2) B at (7, 4.6), 60 deg: apart (gap 0.28 on A1) B at (6.4, 5.4), 30 deg: apart (gap 0.09 on B1)
Boxes in 3D: fifteen axes
var beam = new Obb(new V3(0, 0, 0), Rot(0, 0), new V3(2, 0.15, 0.3)); // 4 m beam along X var cases = new (string Name, V3 Centre)[]{ ("duct through the beam", new(0, 0, 0.3)), ("duct just past the beam edge", new(0, -1, 0.3)), ("duct well above", new(0, 0, 1.6))};foreach (var (name, c) in cases){ var duct = new Obb(c, Rot(30, 45), new V3(0.1, 1.5, 0.1)); // a sloping duct Console.WriteLine($"{name}: {Separating(beam, duct) ?? "clash"}");} static string? Separating(Obb a, Obb b){ var axes = new List<(string, V3)>(); for (int i = 0; i < 3; i++) axes.Add(($"A{"xyz"[i]}", a.Axes[i])); for (int i = 0; i < 3; i++) axes.Add(($"B{"xyz"[i]}", b.Axes[i])); for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) { var c = V3.Cross(a.Axes[i], b.Axes[j]); if (c.Length > 1e-9) axes.Add(($"A{"xyz"[i]} x B{"xyz"[j]}", c)); // skip parallel edges } var d = b.Centre - a.Centre; foreach (var (name, l) in axes) if (Math.Abs(V3.Dot(d, l)) > a.Radius(l) + b.Radius(l)) return $"apart, separated on {name}"; return null;} // Rz(z) * Rx(x), returned as the three turned axesstatic V3[] Rot(double z, double x){ double cz = Math.Cos(z * Math.PI / 180), sz = Math.Sin(z * Math.PI / 180); double cx = Math.Cos(x * Math.PI / 180), sx = Math.Sin(x * Math.PI / 180); return new V3[] { new(cz, sz, 0), new(-sz * cx, cz * cx, sx), new(sz * sx, -cz * sx, cx) };} readonly record struct Obb(V3 Centre, V3[] Axes, V3 Half){ // Half the length of the box's shadow on the direction l public double Radius(V3 l) => Half.X * Math.Abs(V3.Dot(Axes[0], l)) + Half.Y * Math.Abs(V3.Dot(Axes[1], l)) + Half.Z * Math.Abs(V3.Dot(Axes[2], l));} 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)})";}duct through the beam: clash duct just past the beam edge: apart, separated on Ax x By duct well above: apart, separated on Az
Touching, tolerances and clearance
Touching is not clashing. A beam sitting on a column, or a duct resting on a hanger, shares a face. Exact zero overlaps are rare in floating point, so checkers treat an overlap smaller than a tolerance (for example 1 mm) as touching. Clearance (soft) clashes. Some elements must keep a distance: insulation around a pipe, access space in front of a panel. Inflate one shape by the clearance and test again, or compute the actual distance between the shapes and compare it with the requirement. Duplicates. Two identical elements on top of each other overlap completely. Reporting them separately (same type, same geometry) keeps the clash list readable.
Show a hint
Show the solution
var beam = (Min: new V3(0, 0, 3), Max: new V3(6, 0.3, 3.5));var others = new (V3 Min, V3 Max)[]{ (new V3(2, -1, 3.53), new V3(2.2, 2, 3.73)), (new V3(2, -1, 3.6), new V3(2.2, 2, 3.8)), (new V3(6.04, 0.32, 0), new V3(6.4, 0.6, 3.5))};const double Clearance = 0.05;foreach (var o in others){ var gap = new V3(Gap(beam.Min.X, beam.Max.X, o.Min.X, o.Max.X), Gap(beam.Min.Y, beam.Max.Y, o.Min.Y, o.Max.Y), Gap(beam.Min.Z, beam.Max.Z, o.Min.Z, o.Max.Z)); double dist = gap.Length; Console.WriteLine($"{o.Min} .. {o.Max}: {dist:0.000} m apart -> {(dist < Clearance ? "soft clash" : "ok")}");} static double Gap(double a0, double a1, double b0, double b1) => Math.Max(0, Math.Max(b0 - a1, a0 - b1)); 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)})";}(2, -1, 3.53) .. (2.2, 2, 3.73): 0.030 m apart -> soft clash (2, -1, 3.6) .. (2.2, 2, 3.8): 0.100 m apart -> ok (6.04, 0.32, 0) .. (6.4, 0.6, 3.5): 0.045 m apart -> soft clash
Remember
Clash detection runs a cheap broad phase on bounding boxes, then an exact narrow phase on the few candidates. Sweep and prune sorts boxes by min X so each box is only compared with boxes that start before it ends. Separating-axis theorem: two convex shapes are apart if and only if their shadows are apart on some axis. Rectangles need their 4 edge normals; boxes in 3D need 6 face normals plus 9 edge × edge cross products. Use a tolerance so touching elements are not clashes, and clearance distances for soft clashes.