Separating Axis test for triangle - aabb

Quote:

Original post by Rajveer Hi guys, in the process of building an octree I am currently testing whether a triangle (strictly a triangle, no quads or other polygons) intersects an aabb (i.e. the node) the following way: -1) check if any vertices lie within the aabb, if so return intersect -2) check if all vertices lie outside of either of the 6 planes of the aabb, if so return no intersect -3) check if the edges of the polygons intersect the planes of the box, if yes return intersect -4) check if the diagonals of the aabb intersect the triangle and if so, return intersect I've been reading about the separating axis/plane theorem and many of the threads on this forum (it seems to be jyk's favorite method as he always mentions it ;) )

Quote:

so I was thinking would using this algorithm mean I can get rid of all of the above tests? I'm looking for the most efficient algorithm, as I'm programming this for the Nintendo DS which isn't exactly powerful, so time is an issue. Just to be sure, would I: -1) perform 3 tests to check if the vertices lie in the box (1 for each direction) -2) perform 1 test for the closest diagonal to the triangle's normal against the triangle's plane and see where it intersects (would this not be long, as you'd first have to check where it intersects the triangle's plane, then test if this point lies "within" all of the 3 edge's planes?) -3) 9 cross product tests (3 for each direction of the aabb against each edge of the triangle)

Quote:

Original post by Rajveer Cheers for the quick reply jyk! I think after reading another paper on it I understand it better now. I think at the moment I'll leave the aabb and triangle (i.e. not transform into the cube's space). The way I see to go about it is: -1) Check for the elementary planes i.e. the aabb's sides, so you'd project the triangle's points onto the x, y and z-axes and test for each using simple if-statements if they're within the aabb's region -2) Check the triangle's plane (defined by a point on the triangle and the normal). So for this would you project the aabb's points onto this plane (i.e. using the triangle's normal and the aabb's vertices), and compare the triangle's vertices with the projected aabb's vertices? How would one go about checking this? -3) Test for the cross products of the triangle's edges and the box's axes (i.e. normals) and project the triangle onto this plane, then project the aabb by computing a radius r and test if the triangle's projected points lie within this radius. Is this right?

radius = dot(box.extents,v.absolute());

Quote:

Original post by jyk Yes, you have the right idea. Note however that projecting an AABB onto an axis does not require projecting each of the eight corners onto that axis. A search on 'AABB frustum culling' might turn up the correct algorithm for you, but meanwhile here's a hint. The projected radius of an AABB relative to a vector v is: radius = dot(box.extents,v.absolute());

Quote:

Original post by Rajveer r = hy|ay| + hz|az| where h = halfwidth (and hy = halfwidth of y-component) which is essentially the same as the dot-product you hinted at (except without hx|ax| as ax = 0 in this case). I was a bit confused when trying to figure it out, so I'll ask here: is the half-width like a radius but for a box? For an aabb which is a cube, hx hy and hz would all be the same right? Also, on their own they're scalars not vectors right?

//Second of 3 sets of tests: test in triangle's plane with triangle normal		f32 aabbCentre[3], testAxis[3], h[3], triEdge[3], a[3], p[3], minp, maxp, r, temp[3];		//Calculate and move aabb to origin, get halfwidths/extents of box		aabbCentre[0] = (maxx + minx)/2;	aabbCentre[1] = (maxy + miny)/2;	aabbCentre[2] = (maxz + minz)/2;		maxx = maxx - aabbCentre[0];	maxy = maxy - aabbCentre[1];	maxz = maxz - aabbCentre[2];	minx = minx - aabbCentre[0];	miny = miny - aabbCentre[1];	minz = minz - aabbCentre[2];		h[0] = (maxx + minx)/2;		h[1] = (maxy + miny)/2;	h[2] = (maxz + minz)/2;		//Get axis to project onto		testAxis[0] = Level1Poly[n].normal[0]; testAxis[1] = Level1Poly[n].normal[1]; testAxis[2] = Level1Poly[n].normal[2];		//Project aabb onto axis		r = mulf32(h[0], abs(testAxis[0])) + mulf32(h[1], abs(testAxis[1])) + mulf32(h[2], abs(testAxis[2]));		//Get triangle's points and work out min/max		temp[0] = Level1Poly[n].vertex0[0] * LevelScale;	temp[1] = Level1Poly[n].vertex1[0] * LevelScale;	temp[2] = Level1Poly[n].vertex2[0] * LevelScale;	p[0] = dotf32(&testAxis[0], &temp[0]);	p[1] = dotf32(&testAxis[1], &temp[1]);	p[2] = dotf32(&testAxis[2], &temp[2]);		maxp = p[0];	if(p[1] > maxp)	{maxp = p[1];}	if(p[2] > maxp)	{maxp = p[2];}		minp = p[0];	if(p[1] < minp)	{minp = p[1];}	if(p[2] < minp)	{minp = p[2];}		//Test if triangle overlaps aabb in this axis		if((minp > r) | (maxp < -r))	{return false;}	

	//Get axis to project onto	testAxis[0] = 4096; testAxis[1] = 0; testAxis[2] = 0;	triEdge[0] = ((Level1Poly[n].vertex1[0] * LevelScale) - aabbCentre[0]) - ((Level1Poly[n].vertex0[0] * LevelScale) - aabbCentre[0]);	triEdge[1] = ((Level1Poly[n].vertex1[1] * LevelScale) - aabbCentre[1]) - ((Level1Poly[n].vertex0[1] * LevelScale) - aabbCentre[1]);	triEdge[2] = ((Level1Poly[n].vertex1[2] * LevelScale) - aabbCentre[2]) - ((Level1Poly[n].vertex0[2] * LevelScale) - aabbCentre[2]);		crossf32(&testAxis[0], &triEdge[0], &a[0]);	//Project aabb onto axis	r = mulf32(h[1], abs(a[1])) + mulf32(h[2], abs(a[2]));	//Project triangle onto axis and work out min/max		temp[0] = Level1Poly[n].vertex0[0] * LevelScale;	temp[1] = Level1Poly[n].vertex2[0] * LevelScale;	p[0] = dotf32(&a[0], &temp[0]);	p[2] = dotf32(&a[0], &temp[1]);		maxp = p[0];	if(p[2] > maxp)	{maxp = p[2];}		minp = p[0];	if(p[2] < minp)	{minp = p[2];}		//Test if triangle overlaps aabb in this axis		if((minp > r) | (maxp < -r))	{return false;}