Hi. To improve the performance of my raytracer, I decided to use Uniform Space Partitioning. Basically, I divide the world into 3D boxes, and put objects (Surfaces) inside them. When tracing a ray, I check first with the boxes and if there is a hit, I check with the Surfaces it contains.

The problem is, from 11 seconds I dropped to only 8 seconds. Another thing I noticed is that when the world is divided into more boxes, it takes more time to render. So this means there is a problem with my AABB-Ray collision function.

bool intersects(const ref Ray r) const
	{
		Vector3 n = void,						// normal
				v = void, u = void;				// vectors
		
		float t = void;
		
		// plane 0 (front)
		v = Vector3(max.x, min.y, min.z) - min;
		u = Vector3(min.x, max.y, min.z) - min;
		n = cross(v, u);
		n.normalize();
		t = dot(r.d, n);
		
		/++writeln("t0 = ", t);
		if( t > 0 )
			writeln("plane 0 intersected");
		else
			writeln("plane 0 not intersected");++/
		
		Vector3 temp = min - r.e;
		Vector3 p = r.e + r.d * dot(temp, n) / t;
		//writeln("p0 = ", p);
		if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z )
		{
			//writeln("YES 0\n");
			return true;
		}
		/++else
			writeln("NO 0\n");++/
		
		
		// plane 1 (right)
		v = Vector3(max.x, max.y, min.z) - Vector3(max.x, min.y, min.z);
		u = Vector3(max.x, min.y, max.z) - Vector3(max.x, min.y, min.z);
		n = cross(v, u);
		n.normalize();
		
		t = dot(r.d, n);
		/++writeln("t1 = ", t);
		
		if( t > 0 )
			writeln("plane 1 intersected");
		else
			writeln("plane 1 not intersected");++/
		
		temp = Vector3(max.x, min.y, min.z) - r.e;
		p = r.e + r.d * dot(temp, n) / t;
		//writeln("p1 = ", p);
		if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z )
		{
			//writeln("YES 1\n");
			return true;
		}
		/++else
			writeln("NO 1\n");++/
		
		// plane 2 (left)
		v = Vector3(min.x, min.y, max.z) - Vector3(min.x, min.y, min.z);
		u = Vector3(min.x, max.y, min.z) - Vector3(min.x, min.y, min.z);
		n = cross(v, u);
		n.normalize();
		
		t = dot(r.d, n);
		/++writeln("t2 = ", t);
		
		if( t > 0 )
			writeln("plane 2 intersected");
		else
			writeln("plane 2 not intersected");++/
		
		temp = Vector3(min.x, min.y, min.z) - r.e;
		p = r.e + r.d * dot(temp, n) / t;
		//writeln("p2 = ", p);
		if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z )
		{
			//writeln("YES 2\n");
			return true;
		}
		/++else
			writeln("NO 2\n");++/
		
		// plane 3 (back)
		v = Vector3(max.x, min.y, max.z) - Vector3(min.x, min.y, max.z);
		u = Vector3(min.x, max.y, max.z) - Vector3(min.x, min.y, max.z);
		n = cross(v, u);
		n.normalize();
		
		t = dot(r.d, n);
		/++writeln("t3 = ", t);
		
		if( t > 0 )
			writeln("plane 3 intersected");
		else
			writeln("plane 3 not intersected");++/
		
		temp = Vector3(min.x, min.y, max.z) - r.e;
		p = r.e + r.d * dot(temp, n) / t;
		//writeln("p3 = ", p);
		if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z )
		{
			//writeln("YES 3\n");
			return true;
		}
		/++else
			writeln("NO 3\n");++/
		
		// plane 4 (top)
		v = Vector3(min.x, max.y, max.z) - Vector3(min.x, max.y, min.z);
		u = Vector3(max.x, max.y, min.z) - Vector3(min.x, max.y, min.z);
		n = cross(v, u);
		n.normalize();
		
		t = dot(r.d, n);
		/++writeln("t4 = ", t);
		
		if( t > 0 )
			writeln("plane 4 intersected");
		else
			writeln("plane 4 not intersected");++/
		
		temp = Vector3(min.x, max.y, min.z) - r.e;
		p = r.e + r.d * dot(temp, n) / t;
		//writeln("p4 = ", p);
		if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z )
		{
			//writeln("YES 4\n");
			return true;
		}
		else
			/++writeln("NO 4\n");++/
		
		// plane 5 (bottom)
		v = Vector3(max.x, min.y, min.z) - Vector3(min.x, min.y, min.z);
		u = Vector3(min.x, min.y, max.z) - Vector3(min.x, min.y, min.z);
		n = cross(v, u);
		n.normalize();
		
		t = dot(r.d, n);
		/++writeln("t5 = ", t);
		
		if( t > 0 )
			writeln("plane 5 intersected");
		else
			writeln("plane 5 not intersected");++/
		
		temp = Vector3(min.x, min.y, min.z) - r.e;
		p = r.e + r.d * dot(temp, n) / t;
		//writeln("p5 = ", p);
		if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z )
		{
			//writeln("YES 5\n");
			return true;
		}
		/++else
			writeln("NO 5\n");++/
		
		return false;
	}

What I do is check all six planes and then if the hit point is inside the boundaries. I know this is the worst method. What's a better way to do this?

Please, if you suggest something, provide an explanation why it works, as that's the important thing here - I want to learn this stuff.

Thank you :)

Thank you for your replies! The writelns were commented out.

I have found a better solution if my graphics book (the one that calculates tmin, tmax)

Just a little note - I can link you to my pseudo-log (it's not actually log because I hardly find time to update or write something useful there) - http://gameprogrammerdiary.blogspot.cz/2012/09/tutorial-intersecting-ray-and-aabb.html

Here you can find some ray-aabb, with SSE version. Notice how intrinsic version's assembly is a lot better and smaller than compiler generated from

Just so you know, uniform space partitioning is not efficient. If you want to really see some speedup, you'll want to implement a generalized version of space partitioning, namely an octree, kd-tree, or bounding volume hierarchy. For an introduction to bounding volume hierarchies, I suggest you take a look at this code:

https://github.com/brandonpelfrey/Fast-BVH

It's very readable, and quite efficient. Somewhat of a life saver, if, like me, you had trouble grasping the implementation of these kinds of data structures. You might not notice a speedup immediately, but you'll see when you start increasing your polygon count

PS: that code has a small bug, you need to fix the ray-surface intersection code for leaf nodes because it's not doing it right, but nothing too serious, it works great otherwise.

Just so you know, uniform space partitioning is not efficient. If you want to really see some speedup, you'll want to implement a generalized version of space partitioning, namely an octree, kd-tree, or bounding volume hierarchy. For an introduction to bounding volume hierarchies, I suggest you take a look at this code:

https://github.com/brandonpelfrey/Fast-BVH

It's very readable, and quite efficient. Somewhat of a life saver, if, like me, you had trouble grasping the implementation of these kinds of data structures. You might not notice a speedup immediately, but you'll see when you start increasing your polygon count

PS: that code has a small bug, you need to fix the ray-surface intersection code for leaf nodes because it's not doing it right, but nothing too serious, it works great otherwise.

Yeah, I noticed that it's not very efficient. It also depends on the size of each AABB the space is divided -- but you cannot know the best size for each scene.

Thank you for the link, I'm going to read BVH through my book first :)