# Ray-AABB collision detection

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

## Recommended Posts

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 :)

##### Share on other sites
I'm not sure why your code doesn't work, but check this book out:
http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323

It's the best book I've found with regards to collision detection, great code samples and great explanations.

Jeff.
(I'm not affiliated with the book at all, except that I have it)

##### Share on other sites

Comment out the "writeln"s ? Otherwise, I have seen much much shorter ray / AABB tests, without vector normalization. Cheers!

Edited by kauna

##### Share on other sites

AABS would be better than AABB. In case of AABS you just check distance of AABS center from line/ray. Also checking center distance from plane are just very few linear operations as well.

##### Share on other sites

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)

##### Share on other sites

You can find some information about the ray-box algorithm at this location:

http://scratchapixel.com/lessons/3d-basic-lessons/lesson-7-intersecting-simple-shapes/ray-box-intersection/

As mentioned by other people, don't print stuff out from your program. It will significantly slow things down (printf, std::cout <<, etc.).

To accelerate your code if you really need speed up you can use SSE instructions.

##### Share on other sites

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

##### Share on other sites

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.

##### Share on other sites
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 :)

• 9
• 9
• 12
• 10
• 12