For my thesis work, I needed a way of determining collisions between an axis-aligned bounding box (AABB) and a triangle. I was working in C#, and discovered that there isn’t a whole lot of code examples out there. I ended up adapting some C++ code into C#, but it seems to work quite well. Here’s a dump of the code. It does involve some bits used in other parts of my work, but it should still work.

My triangle class:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using Microsoft.Xna.Framework;

namespace Voxelizer5Common

{

public class Triangle

{

private Vector3 a;

private Vector3 b;

private Vector3 c;

private Vector3 normal;

#region Properties

///

/// A

///

public Vector3 A

{

get { return a; }

set { a = value; }

}

///

/// B

///

public Vector3 B

{

get { return b; }

set { b = value; }

}

///

/// C

///

public Vector3 C

{

get { return c; }

set { c = value; }

}

///

/// Normal

///

public Vector3 Normal

{

get { return normal; }

set { normal = value; }

}

#endregion

///

/// Returns true if all points are non-zero;

///

///

public bool AllPointsNonZero()

{

bool result = true;

if (a.X == 0.0f && a.Y == 0.0f && a.Z == 0.0f)

{

result = false;

}

else if (b.X == 0.0f && b.Y == 0.0f && b.Z == 0.0f)

{

result = false;

}

else if (c.X == 0.0f && c.Y == 0.0f && c.Z == 0.0f)

{

result = false;

}

return result;

}

///

/// Returns true if any of the points are zero.

///

///

public bool AnyPointsZero()

{

bool result = false;

if (a.X == 0.0f && a.Y == 0.0f && a.Z == 0.0f)

{

result = true;

}

else if (b.X == 0.0f && b.Y == 0.0f && b.Z == 0.0f)

{

result = true;

}

else if (c.X == 0.0f && c.Y == 0.0f && c.Z == 0.0f)

{

result = true;

}

return result;

}

///

/// Gets the minimum point of the AABB of this triangle.

///

///

public Vector3 GetMinPoint()

{

Vector3 min = new Vector3(a.X, a.Y, a.Z);

//X

if (b.X < min.X)

{

min.X = b.X;

}

if (c.X < min.X)

{

min.X = c.X;

}

//Y

if (b.Y < min.Y)

{

min.Y = b.Y;

}

if (c.Y < min.Y)

{

min.Y = c.Y;

}

//Z

if (b.Z < min.Z)

{

min.Z = b.X;

}

if (c.Z < min.Z)

{

min.Z = c.Z;

}

return min;

}

///

/// Gets the maximum point in the AABB that would surround the triangle.

///

///

public Vector3 GetMaxPoint()

{

Vector3 max = new Vector3(a.X, a.Y, a.Z);

//X

if (b.X > max.X)

{

max.X = b.X;

}

if (c.X > max.X)

{

max.X = c.X;

}

//Y

if (b.Y > max.Y)

{

max.Y = b.Y;

}

if (c.Y > max.Y)

{

max.Y = c.Y;

}

//Z

if (b.Z > max.Z)

{

max.Z = b.Z;

}

if (c.Z > max.Z)

{

max.Z = c.Z;

}

return max;

}

///

/// Gets the center of the triangle. (Essentially the average of all 3 points).

///

///

public Vector3 GetCenter()

{

Vector3 center = new Vector3();

center.X += A.X;

center.Y += A.Y;

center.Z += A.Z;

center.X += B.X;

center.Y += B.Y;

center.Z += B.Z;

center.X += C.X;

center.Y += C.Y;

center.Z += C.Z;

center.X = center.X / 3.0f;

center.Y = center.Y / 3.0f;

center.Z = center.Z / 3.0f;

return center;

}

///

/// Gets the hash code of the triangle.

///

///

public override int GetHashCode()

{

return a.GetHashCode() + b.GetHashCode() + c.GetHashCode();

}

///

/// Determines if obj is equal to this triangle

///

//////

public override bool Equals(object obj)

{

bool result = false;

if (obj.GetType() == typeof(Triangle))

{

Triangle t = (Triangle)obj;

if (t.A == A && t.B == B && t.C == C)

{

result = true;

}

}

return result;

}

}

}

The TriangleBoxIntersect method is on my Node class – where each node is a node in an octree. It has a min and max Vector3 representing the minimum and maximum points of the axis aligned bounding box:

///

/// Uses the separating axis theorem to determine if there is overlap between the box and triangle.

///

/// Original C++ source code from: http://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/tribox3.txt

///

/// Does the following tests:

/// 1) The x, y, z directions

/// 2) Normal of the triangle

/// 3) Crossproduct (edge from triangle)

///

////////////

public bool TriangleBoxIntersect(Triangle triangle)

{

Vector3 center = new Vector3(this.min.X + (size / 2.0f), this.min.Y + (size / 2.0f), this.min.Z + (size / 2.0f));

Vector3 boxHalfSize = new Vector3(this.size, this.size, this.size);

Vector3 v0 = triangle.A – center;

Vector3 v1 = triangle.B – center;

Vector3 v2 = triangle.C – center;

Vector3 e0 = v1 – v0;

Vector3 e1 = v2 – v1;

Vector3 e2 = v0 – v2;

//Point 1 in original paper: minimal AABB of triangle against AABB. Involves 3 tests against normals.

float min, max;

FindMinMax(v0.X, v1.X, v2.X, out min, out max);

if (min > boxHalfSize.X || max < -boxHalfSize.X) { return false; } FindMinMax(v0.Y, v1.Y, v2.Y, out min, out max); if (min > boxHalfSize.Y || max < -boxHalfSize.Y) { return false; } FindMinMax(v0.Z, v1.Z, v2.Z, out min, out max); if (min > boxHalfSize.Z || max < -boxHalfSize.Z)

{

return false;

}

//Point 2 in original paper: Normal of triangle – uses plane/AABB overlap test.

Vector3 normal = Vector3.Cross(e0, e1);

if (!PlaneBoxOverlap(normal, v0, boxHalfSize))

{

return false;

}

//Point 3 in the original paper: 9 tests for edges.

float fex = Math.Abs(e0.X);

float fey = Math.Abs(e0.Y);

float fez = Math.Abs(e0.Z);

if (!AXISTEST_X01(e0.Z, e0.Y, fez, fey, v0, v1, v2, min, max, boxHalfSize)) { return false; }

if (!AXISTEST_Y02(e0.Z, e0.X, fez, fex, v0, v1, v2, min, max, boxHalfSize)) { return false; }

if (!AXISTEST_Z12(e0.Y, e0.X, fey, fex, v0, v1, v2, min, max, boxHalfSize)) { return false; }

fex = Math.Abs(e1.X);

fey = Math.Abs(e1.Y);

fez = Math.Abs(e1.Z);

if (!AXISTEST_X01(e1.Z, e1.Y, fez, fey, v0, v1, v2, min, max, boxHalfSize)) { return false; }

if (!AXISTEST_Y02(e1.Z, e1.X, fez, fex, v0, v1, v2, min, max, boxHalfSize)) { return false; }

if (!AXISTEST_Z0(e1.Y, e1.X, fey, fex, v0, v1, v2, min, max, boxHalfSize)) { return false; }

fex = Math.Abs(e2.X);

fey = Math.Abs(e2.Y);

fez = Math.Abs(e2.Z);

if (!AXISTEST_X2(e2.Z, e2.Y, fez, fey, v0, v1, v2, min, max, boxHalfSize)) { return false; }

if (!AXISTEST_Y1(e2.Z, e2.X, fez, fex, v0, v1, v2, min, max, boxHalfSize)) { return false; }

if (!AXISTEST_Z12(e2.Y, e2.X, fey, fex, v0, v1, v2, min, max, boxHalfSize)) { return false; }

//If everything has passed up to this point, we are intersecting.

return true;

}

And here are the AXISTEST methods, PlaneBoxOverlap method, and FindMinMax methods:

///

/// AXISTEST_X01

///

/////////////////////////////////

private bool AXISTEST_X01(float a, float b, float fa, float fb, Vector3 v0, Vector3 v1, Vector3 v2, float min, float max, Vector3 boxHalfSize)

{

float p0 = a * v0.Y – b * v0.Z;

float p2 = a * v2.Y – b * v2.Z;

if (p0 < p2) { min = p0; max = p2; } else { min = p2; max = p0; } float rad = fa * boxHalfSize.Y + fb * boxHalfSize.Z; if (min > rad || max < -rad)

{

return false;

}

else

{

return true;

}

}

///

/// AXISTEST_X2

///

/////////////////////////////////

private bool AXISTEST_X2(float a, float b, float fa, float fb, Vector3 v0, Vector3 v1, Vector3 v2, float min, float max, Vector3 boxHalfSize)

{

float p0 = a * v0.Y – b * v0.Z;

float p1 = a * v1.Y – b * v1.Z;

if (p0 < p1) { min = p0; max = p1; } else { min = p1; max = p0; } float rad = fa * boxHalfSize.Y + fb * boxHalfSize.Z; if (min > rad || max < -rad)

{

return false;

}

else

{

return true;

}

}

///

/// AXISTEST_Y02

///

/////////////////////////////////

private bool AXISTEST_Y02(float a, float b, float fa, float fb, Vector3 v0, Vector3 v1, Vector3 v2, float min, float max, Vector3 boxHalfSize)

{

float p0 = -a * v0.X + b * v0.Z;

float p2 = -a * v2.X + b * v2.Z;

if (p0 < p2) { min = p0; max = p2; } else { min = p2; max = p0; } float rad = fa * boxHalfSize.X + fb * boxHalfSize.Z; if (min > rad || max < -rad)

{

return false;

}

else

{

return true;

}

}

///

/// AXISTEST_Y1

///

/////////////////////////////////

private bool AXISTEST_Y1(float a, float b, float fa, float fb, Vector3 v0, Vector3 v1, Vector3 v2, float min, float max, Vector3 boxHalfSize)

{

float p0 = -a * v0.X + b * v0.Z;

float p1 = -a * v1.X + b * v1.Z;

if (p0 < p1) { min = p0; max = p1; } else { min = p1; max = p0; } float rad = fa * boxHalfSize.X + fb * boxHalfSize.Z; if (min > rad || max < -rad)

{

return false;

}

else

{

return true;

}

}

///

/// AXISTEST_Z12

///

/////////////////////////////////

private bool AXISTEST_Z12(float a, float b, float fa, float fb, Vector3 v0, Vector3 v1, Vector3 v2, float min, float max, Vector3 boxHalfSize)

{

float p1 = a * v1.X – b * v1.Y;

float p2 = a * v2.X – b * v2.Y;

if (p2 < p1) { min = p2; max = p1; } else { min = p1; max = p2; } float rad = fa * boxHalfSize.X + fb * boxHalfSize.Y; if (min > rad || max < -rad)

{

return false;

}

else

{

return true;

}

}

///

/// AXISTEST_Z0

///

/////////////////////////////////

private bool AXISTEST_Z0(float a, float b, float fa, float fb, Vector3 v0, Vector3 v1, Vector3 v2, float min, float max, Vector3 boxHalfSize)

{

float p0 = a * v0.X – b * v0.Y;

float p1 = a * v1.X – b * v1.Y;

if (p0 < p1) { min = p0; max = p1; } else { min = p1; max = p0; } float rad = fa * boxHalfSize.X + fb * boxHalfSize.Y; if (min > rad || max < -rad)

{

return false;

}

else

{

return true;

}

}

///

/// PlaneBoxOverlap test

///

////////////

private bool PlaneBoxOverlap(Vector3 normal, Vector3 vert, Vector3 maxBox)

{

Vector3 vMin, vMax;

float v;

//X

v = vert.X;

if (normal.X > 0.0f)

{

vMin.X = -maxBox.X – v;

vMax.X = maxBox.X – v;

}

else

{

vMin.X = maxBox.X – v;

vMax.X = -maxBox.X – v;

}

//Y

v = vert.Y;

if (normal.Y > 0.0f)

{

vMin.Y = -maxBox.Y – v;

vMax.Y = maxBox.Y – v;

}

else

{

vMin.Y = maxBox.Y – v;

vMax.Y = -maxBox.Y – v;

}

//Z

v = vert.Z;

if (normal.Z > 0.0f)

{

vMin.Z = -maxBox.Z – v;

vMax.Z = maxBox.Z – v;

}

else

{

vMin.Z = maxBox.Z – v;

vMax.Z = -maxBox.Z – v;

}

if (Vector3.Dot(normal, vMin) > 0.0f)

{

return false;

}

if (Vector3.Dot(normal, vMax) >= 0.0f)

{

return true;

}

return false;

}

///

/// Used to find the maximum AABB of a triangle

///

///////////////private void FindMinMax(float v0, float v1, float v2, out float min, out float max)

{

min = max = v0;

if (v1 < min) { min = v1; } if (v1 > max)

{

max = v1;

}

if (v2 < min) { min = v2; } if (v2 > max)

{

max = v2;

}

}

It probably isn’t optimal, but it does work.

## Reply