# Triangle-AABB intersection test

This topic is 1228 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I want to implement octrees where I store a (limited) number of triangles in each octree node. One triangle can exist in multiple nodes.

Before i can add it I need to figure out if the triangle intersects/overlays with the sub cube of the node. It is only necessary that a part of the triangle is inside that cube. Here are my querys I already implemented:

A triangle is (partly) inside an AABB if

• at least one of the three corner points is inside AABB
• at least one of the three edges intersects with at least one of six AABB planes

Now there is a third possibilty where a triangle intersects with the AABB, and that is if only the surface goes through one of the six planes. I know that 2 intersecting planes can form a line, but then I don't know how this might help me.

Do you have any ideas how to estimate the third possibility?

lg Chris

PS: follow me on my blog where I explain computer graphics in pure C++ (no OpenGL or DirectX)

http://computergraphicsguide.blogspot.co.at/

##### Share on other sites

You colud use the "separate axis algorithm". Depending on the case I think that it is possible to get away only with "is every vertex from the triangle in the box" test... not sure

Edited by imoogiBG

##### Share on other sites

You can find Triangle-AABB intersection test in MathGeoLib, with references to sources. See

##### Share on other sites
Untested C# snipet:

public class AabbTriTest
{
// CONSTANTS //////////////////////////////////////////////////////////////////////////////////////////////////////

private   static readonly Vector3 []   BOX_DIR = new Vector3 [3] { new Vector3( 1.0f, 0.0f, 0.0f ),
new Vector3( 0.0f, 1.0f, 0.0f ),
new Vector3( 0.0f, 0.0f, 1.0f ) };

// FIELDS /////////////////////////////////////////////////////////////////////////////////////////////////////////

private   Vector3             m_Center;
private   Vector3             m_Extent;
private   readonly float []   m_MinMax = new float [6];

// METHODS ////////////////////////////////////////////////////////////////////////////////////////////////////////

//-----------------------------------------------------------------------------------------------------------------
public void Setup( Vector3 boxCenter, Vector3 boxExtents )
{
m_Center = boxCenter;
m_Extent = boxExtents;

Vector3  min = boxCenter - boxExtents;
Vector3  max = boxCenter + boxExtents;

m_MinMax[0] = min.x;
m_MinMax[1] = max.x;
m_MinMax[2] = min.y;
m_MinMax[3] = max.y;
m_MinMax[4] = min.z;
m_MinMax[5] = max.z;
}

//-----------------------------------------------------------------------------------------------------------------
public bool Test( Vector3 [/*3*/] tri, Vector3 triPlaneN, float triPlaneD )
{
Vector3  dir;
float    tMin, tMax, bMin, bMax;

// tri's normal...

tMin = tMax = -triPlaneD;

ProjectBox( triPlaneN, out bMin, out bMax );

if ( tMax < tMin || bMax < tMin )
return false;

// normals of box faces...

ProjectTri( BOX_DIR[0], tri, out tMin, out tMax );   // tMin = min( tri[0].x, ... , tri[2].x )
// tMax = max( tri[0].x, ... , tri[2].x )
if ( tMax < m_MinMax[0] || m_MinMax[1] < tMin )
return false;

ProjectTri( BOX_DIR[1], tri, out tMin, out tMax );   // tMin = min( tri[0].y, ... , tri[2].y )
// tMax = max( tri[0].y, ... , tri[2].y )
if ( tMax < m_MinMax[2] || m_MinMax[3] < tMin )
return false;

ProjectTri( BOX_DIR[2], tri, out tMin, out tMax );   // tMin = min( tri[0].z, ... , tri[2].z )
// tMax = max( tri[0].z, ... , tri[2].z )
if ( tMax < m_MinMax[4] || m_MinMax[5] < tMin )
return false;

// cross-products of tri edges and box axis...

for ( int i = 0, j = 3; i < 3; j = i++ )
{
Vector3 edge = tri[i] - tri[j];

for ( int k = 0; k < 3; ++k )
{
dir = Vector3.Cross( edge, BOX_DIR[k] );

ProjectBox( dir,      out bMin, out bMax );
ProjectTri( dir, tri, out tMin, out tMax );

if ( tMax < bMin || bMax < tMin )
return false;
}
}

return true;
}

//-----------------------------------------------------------------------------------------------------------------
private void ProjectBox( Vector3 dir, out float projMin, out float projMax )
{
float  c =          ( dir.x * m_Center.x ) +          ( dir.y * m_Center.y ) +          ( dir.z * m_Center.z );
float  e = Mathf.Abs( dir.x * m_Extent.x ) + Mathf.Abs( dir.y * m_Extent.y ) + Mathf.Abs( dir.z * m_Extent.z );

projMin = c - e;
projMax = c + e;
}

//-----------------------------------------------------------------------------------------------------------------
private static void ProjectTri( Vector3 dir, Vector3 [] tri, out float projMin, out float projMax )
{
projMin =
projMax = Vector3.Dot( dir, tri[0] );

float p = Vector3.Dot( dir, tri[1] );

if ( p < projMin ) projMin = p; else
if ( p > projMax ) projMax = p;

p = Vector3.Dot( dir, tri[2] );

if ( p < projMin ) projMin = p; else
if ( p > projMax ) projMax = p;
}
}


Edited by MCapousek

##### Share on other sites

You colud use the "separate axis algorithm". Depending on the case I think that it is possible to get away only with "is every vertex from the triangle in the box" test... not sure

I can't just depend on assumptions, a polygon's triangle might miss that way and then I have a big hole in my rendered object. I'd also like like to avoid transformations needed for SAA.

You can find Triangle-AABB intersection test in MathGeoLib, with references to sources. See

Thx, I can use that as inspiration, but I intend to avoid extern libraries in my framework. It's an educational purpose and it won't help my readers if I use something else.

@MCapousek

Your algorithm seems compact and not as complicated as MathGeoLib's version where they consider existing defines. I'll also use that as inspritation. But when you use 3 points for a triangle, there is no need to add normal and constant as parameters, you can calculate them from these 3 points.

-------------------------

With so many supports I speak my thanks. I can finally accelerate raycasting/raytracing algorithm in my framework

Edited by rumpfi88

##### Share on other sites
SAT test is generally the best you can get, and in this case you need to test all 4 face normals and 9 cross products. Both implementations you were linked to do the same thing, with MathGeoLib being highly optimized with unrolled loops and SIMD arithmetic, but less readable as a result.

##### Share on other sites

it seems the whole algorithm is easier to understand when transforming the triangle so that AABB's center is at zero-point. I go with SAT.

##### Share on other sites

I'm done with implementation: I have the following informations and comparisions:

# Objects: 4

# Triangles: 34,378

Render method: Raycasting

Render size: 640x480

Time without Octree: ca. 8  minutes

Time with Octree: 35 seconds (15s for loading and building, 20s for rendering).

And of course, the results look the same ^^. Thx a lot for your advices.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 13
• 9
• 15
• 14
• 46
• ### Forum Statistics

• Total Topics
634060
• Total Posts
3015300
×