View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Ray-AABB collision detection

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

9 replies to this topic

### #1sheep19  Members

Posted 05 January 2013 - 02:46 PM

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

### #2jeffkingdev  Members

Posted 06 January 2013 - 12:15 PM

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)

### #3kauna  Members

Posted 07 January 2013 - 08:23 AM

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

Edited by kauna, 07 January 2013 - 08:25 AM.

### #4Glass_Knife  Moderators

Posted 07 January 2013 - 10:18 AM

http://www.cs.utah.edu/~awilliam/box/box.pdf

Give this a try.

I think, therefore I am. I think? - "George Carlin"
My Website: Indie Game Programming

My Book: http://amzn.com/1305076532

### #5JohnnyCode  Members

Posted 07 January 2013 - 10:18 AM

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.

### #6sheep19  Members

Posted 07 January 2013 - 02:18 PM

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)

### #7mast4as  Members

Posted 07 January 2013 - 02:23 PM

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.

### #8Vilem Otte  GDNet+

Posted 08 January 2013 - 07:31 PM

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

My current blog on programming, linux and stuff - http://gameprogrammerdiary.blogspot.com

### #9Bacterius  Members

Posted 08 January 2013 - 09:07 PM

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.

“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”

### #10sheep19  Members

Posted 09 January 2013 - 04:43 AM

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

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.