Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


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.

  • You cannot reply to this topic
9 replies to this topic

#1 sheep19   Members   -  Reputation: 412

Like
1Likes
Like

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



Sponsor:

#2 jeffkingdev   Members   -  Reputation: 778

Like
1Likes
Like

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)

#3 kauna   Crossbones+   -  Reputation: 2741

Like
0Likes
Like

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.


#4 Glass_Knife   Moderators   -  Reputation: 4748

Like
0Likes
Like

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"
Indie Game Programming

#5 JohnnyCode   Members   -  Reputation: 259

Like
0Likes
Like

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.



#6 sheep19   Members   -  Reputation: 412

Like
0Likes
Like

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)



#7 mast4as   Members   -  Reputation: 124

Like
0Likes
Like

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.



#8 Vilem Otte   Crossbones+   -  Reputation: 1462

Like
0Likes
Like

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


#9 Bacterius   Crossbones+   -  Reputation: 9043

Like
2Likes
Like

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 wink.png

 

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.


The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#10 sheep19   Members   -  Reputation: 412

Like
0Likes
Like

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 wink.png

 

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.



PARTNERS