• Advertisement
Sign in to follow this  

Triangle-AABB intersection test

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement