Axis-Aligned Bounding Box (AABB) to Triangle Collision Detection in C#

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s