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/

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

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

• http://clb.demon.fi/MathGeoLib/nightly/docs/Triangle_Intersects.php
• https://github.com/juj/MathGeoLib/blob/master/src/Geometry/Triangle.cpp#L697

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;
	}
}

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

• http://clb.demon.fi/MathGeoLib/nightly/docs/Triangle_Intersects.php
• https://github.com/juj/MathGeoLib/blob/master/src/Geometry/Triangle.cpp#L697

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

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.

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.

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.