Skip to content

Instantly share code, notes, and snippets.

@StagPoint
Last active July 18, 2024 09:31
Show Gist options
  • Save StagPoint/76ae48f5d7ca2f9820748d08e55c9806 to your computer and use it in GitHub Desktop.
Save StagPoint/76ae48f5d7ca2f9820748d08e55c9806 to your computer and use it in GitHub Desktop.
Triangle/AABB Intersection Test in C#
public static bool IntersectsBox( Vector3 a, Vector3 b, Vector3 c, Vector3 boxCenter, Vector3 boxExtents )
{
// From the book "Real-Time Collision Detection" by Christer Ericson, page 169
// See also the published Errata at http://realtimecollisiondetection.net/books/rtcd/errata/
// Translate triangle as conceptually moving AABB to origin
var v0 = ( a - boxCenter );
var v1 = ( b - boxCenter );
var v2 = ( c - boxCenter );
// Compute edge vectors for triangle
var f0 = ( v1 - v0 );
var f1 = ( v2 - v1 );
var f2 = ( v0 - v2 );
#region Test axes a00..a22 (category 3)
// Test axis a00
var a00 = new Vector3( 0, -f0.z, f0.y );
var p0 = Vector3.Dot( v0, a00 );
var p1 = Vector3.Dot( v1, a00 );
var p2 = Vector3.Dot( v2, a00 );
var r = boxExtents.y * Math.Abs( f0.z ) + boxExtents.z * Math.Abs( f0.y );
if( Math.Max( -fmax( p0, p1, p2 ), fmin( p0, p1, p2 ) ) > r )
{
return false;
}
// Test axis a01
var a01 = new Vector3( 0, -f1.z, f1.y );
p0 = Vector3.Dot( v0, a01 );
p1 = Vector3.Dot( v1, a01 );
p2 = Vector3.Dot( v2, a01 );
r = boxExtents.y * Math.Abs( f1.z ) + boxExtents.z * Math.Abs( f1.y );
if( Math.Max( -fmax( p0, p1, p2 ), fmin( p0, p1, p2 ) ) > r )
{
return false;
}
// Test axis a02
var a02 = new Vector3( 0, -f2.z, f2.y );
p0 = Vector3.Dot( v0, a02 );
p1 = Vector3.Dot( v1, a02 );
p2 = Vector3.Dot( v2, a02 );
r = boxExtents.y * Math.Abs( f2.z ) + boxExtents.z * Math.Abs( f2.y );
if( Math.Max( -fmax( p0, p1, p2 ), fmin( p0, p1, p2 ) ) > r )
{
return false;
}
// Test axis a10
var a10 = new Vector3( f0.z, 0, -f0.x );
p0 = Vector3.Dot( v0, a10 );
p1 = Vector3.Dot( v1, a10 );
p2 = Vector3.Dot( v2, a10 );
r = boxExtents.x * Math.Abs( f0.z ) + boxExtents.z * Math.Abs( f0.x );
if( Math.Max( -fmax( p0, p1, p2 ), fmin( p0, p1, p2 ) ) > r )
{
return false;
}
// Test axis a11
var a11 = new Vector3( f1.z, 0, -f1.x );
p0 = Vector3.Dot( v0, a11 );
p1 = Vector3.Dot( v1, a11 );
p2 = Vector3.Dot( v2, a11 );
r = boxExtents.x * Math.Abs( f1.z ) + boxExtents.z * Math.Abs( f1.x );
if( Math.Max( -fmax( p0, p1, p2 ), fmin( p0, p1, p2 ) ) > r )
{
return false;
}
// Test axis a12
var a12 = new Vector3( f2.z, 0, -f2.x );
p0 = Vector3.Dot( v0, a12 );
p1 = Vector3.Dot( v1, a12 );
p2 = Vector3.Dot( v2, a12 );
r = boxExtents.x * Math.Abs( f2.z ) + boxExtents.z * Math.Abs( f2.x );
if( Math.Max( -fmax( p0, p1, p2 ), fmin( p0, p1, p2 ) ) > r )
{
return false;
}
// Test axis a20
var a20 = new Vector3( -f0.y, f0.x, 0 );
p0 = Vector3.Dot( v0, a20 );
p1 = Vector3.Dot( v1, a20 );
p2 = Vector3.Dot( v2, a20 );
r = boxExtents.x * Math.Abs( f0.y ) + boxExtents.y * Math.Abs( f0.x );
if( Math.Max( -fmax( p0, p1, p2 ), fmin( p0, p1, p2 ) ) > r )
{
return false;
}
// Test axis a21
var a21 = new Vector3( -f1.y, f1.x, 0 );
p0 = Vector3.Dot( v0, a21 );
p1 = Vector3.Dot( v1, a21 );
p2 = Vector3.Dot( v2, a21 );
r = boxExtents.x * Math.Abs( f1.y ) + boxExtents.y * Math.Abs( f1.x );
if( Math.Max( -fmax( p0, p1, p2 ), fmin( p0, p1, p2 ) ) > r )
{
return false;
}
// Test axis a22
var a22 = new Vector3( -f2.y, f2.x, 0 );
p0 = Vector3.Dot( v0, a22 );
p1 = Vector3.Dot( v1, a22 );
p2 = Vector3.Dot( v2, a22 );
r = boxExtents.x * Math.Abs( f2.y ) + boxExtents.y * Math.Abs( f2.x );
if( Math.Max( -fmax( p0, p1, p2 ), fmin( p0, p1, p2 ) ) > r )
{
return false;
}
#endregion
#region Test the three axes corresponding to the face normals of AABB b (category 1)
// Exit if...
// ... [-extents.x, extents.x] and [min(v0.x,v1.x,v2.x), max(v0.x,v1.x,v2.x)] do not overlap
if( fmax( v0.x, v1.x, v2.x ) < -boxExtents.x || fmin( v0.x, v1.x, v2.x ) > boxExtents.x )
{
return false;
}
// ... [-extents.y, extents.y] and [min(v0.y,v1.y,v2.y), max(v0.y,v1.y,v2.y)] do not overlap
if( fmax( v0.y, v1.y, v2.y ) < -boxExtents.y || fmin( v0.y, v1.y, v2.y ) > boxExtents.y )
{
return false;
}
// ... [-extents.z, extents.z] and [min(v0.z,v1.z,v2.z), max(v0.z,v1.z,v2.z)] do not overlap
if( fmax( v0.z, v1.z, v2.z ) < -boxExtents.z || fmin( v0.z, v1.z, v2.z ) > boxExtents.z )
{
return false;
}
#endregion
#region Test separating axis corresponding to triangle face normal (category 2)
var planeNormal = Vector3.Cross( f0, f1 );
var planeDistance = Vector3.Dot( planeNormal, v0 );
// Compute the projection interval radius of b onto L(t) = b.c + t * p.n
r = boxExtents.x * Math.Abs( planeNormal.x )
+ boxExtents.y * Math.Abs( planeNormal.y )
+ boxExtents.z * Math.Abs( planeNormal.z );
// Intersection occurs when plane distance falls within [-r,+r] interval
if( planeDistance > r )
{
return false;
}
#endregion
return true;
}
private static float fmin( float a, float b, float c )
{
return Math.Min( a, Math.Min( b, c ) );
}
private static float fmax( float a, float b, float c )
{
return Math.Max( a, Math.Max( b, c ) );
}
@StagPoint
Copy link
Author

StagPoint commented Feb 21, 2021

Yup, straight out of his book Real-Time Collision Detection. I highly recommend that book, it's a fantastic resource. The code above is just my attempt to port it to C# for my own use. I've not made any claim to ownership or invention, nor any other representation at all. I'm pretty sure he didn't invent it either, for whatever that's worth.

I'll review and test your suggested changes if I ever need to use code like this again. It's doubtful that I will, so the code will likely remain unchanged here, and people will have to investigate any potential issues themselves.

Here's the notes published on the Errata page for the book:
image

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment