Sign in to follow this  
keathmilligan

Efficient ray-model intersect testing

Recommended Posts

Hi, my project targets mobile devices so I'm looking for ways to optimize it as much as possible. One area that I am particularly concerned about is ray-model intersection.


Here is the approach I am currently using:

Each model has a bounding box that is oriented with the model (OBB). The OBB is generated when the model is loaded and the points of the OBB are transformed when an intersect test needs to be performed (with logic to optimize not regenerating multiple times in a frame or not regenerating when the object position/transformation hasn't changed, etc.).

When it comes time to do the intersect test:[list]
[*]First, before transforming the OBB, I do a quick check to make sure the ray isn't headed in completely the opposite direction. If so, exit, no intersection.
[*]Next the OBB is transformed if necessary.
[*]An intersect test is performed on the sides of the OBB. If no intersection of the OBB, exit, no intersection.
[*]If the OBB is intersected, then I loop through each face of the model:
[*]Calculate a normal for the face.
[*]If the face is pointing away from the vector, proceed to the next face.
[*]If not, perform a Moller-Trumbore intersection test of the triangle - return TRUE if intersection found or proceed to next face if not.
[/list]
What could I do to optimize this, if anything, and still get similar results? Looping through each face is painful, but my models are fairly low polygon count so it's not [i]that[/i] bad. One capability I am adding is the ability to manually specify the OBB and have multiple OBBs for an object so they more closely follow its shape. Another thought is to simply return TRUE when the OBB is intersect when the object is far away without going through each face for a more precise detection. Edited by kmx

Share this post


Link to post
Share on other sites
[url="http://en.wikipedia.org/wiki/Spatial_database"]spacial database[/url] or spacial index may be useful

You can add an index to the mesh for faster checks against the mesh and you can also add an index for objects in your scene. Implementing something such as this can be tricky. So my advice, be sure you need to add this. You may find, and I would expect, that your game runs fine without it. If you had hundreds or even thousands of objects, if you had very complicated meshes, or if you are doing hundreds of ray intersection tests per from then it may be necessary but if you are only doing a handful of tests on a handful of objects I wouldn't worry about that right way.

EDIT: If you do choose this route, I would recommend looking into [url="http://en.wikipedia.org/wiki/Octree"]Octrees[/url]. They are easy to understand and efficient.

A simpler thing you could do would be to transform the ray from world space to the objects local space for collision detection instead of the other way around by transforming the objects bounding box or, even worse, the mesh data. Edited by HappyCoder

Share this post


Link to post
Share on other sites
There are a lot of factors when selecting the best approach. For example:[list]
[*]What shape are your objects?
[*]How important is accuracy?
[*]Are false positives better/worse than false negatives?
[*]How many are you talking about?
[*]Is your game world sparse or dense?
[*]Are objects clustered?
[*]Are most objects static or moving?
[*]Does your ray have a finite length?
[*]Are there significant occluders, e.g. walls/floors?
[/list]
To show why some of these are important, let's look at a few examples. Many games don't perform collisions with meshes. Often a collision with a sphere, cube, cylinder, cone or plane is enough, and much faster to do. In many arcade games (for example) the action is thick and fast and the player literally won't notice the imprecision. Now think about indoor vs outer space. In space you need to potentially consider every object, as there are very few occluders and they are relatively small. Indoor however most rays will hit a wall, floor or ceiling, so an approach like PVS is more appropriate for immediately cutting down the possibilities.

That aside, HappyCoder made some good suggestions. Have a look at the below for some discussion of octree ray testing.
[url="http://stackoverflow.com/questions/10228690/ray-octree-intersection-algorithms"]http://stackoverflow.com/questions/10228690/ray-octree-intersection-algorithms[/url]

Share this post


Link to post
Share on other sites
Here's what I do in my ray tracer (2 million rays/s on a single thread on a 3.4 GHz core i7)

Build an axis-aligned bounding box tree for the model's triangles. Make sure that you use some sort of surface area heuristic to determine the splitting plane, this is essential to getting good performance in all cases. I use a binned-SAH approximation which is much faster to build and gets good results.

Store the (static) tree in an array of nodes, this improves cache performance. Try to keep your nodes sized so that they are 2^n bytes in size for some n so that whole nodes fit into cache lines. Nodes store an AABB (min and max points), leaf node flag, data offset (either the offset to the first child in the node array or the triangle index if it is a leaf).

This will get you pretty good performance (say ~800,000 rays/s). You can take this a step further by taking advantage of SSE code. The easiest way I've found to get a 2-3x performance boost is to use a [url="http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.100/institut/Papers/QBVH.pdf"]QBVH[/url] (4-ary AABB tree stored in an SSE-friendly format). Using this structure, you can do 4 ray vs AABB tests at once for a huge performance boost. The construction of the tree is a little more involved and the ray traversal code needs to be really well written to see the benefits, but the approach works really well!

As for the actual ray tracing algorithm, you want to transform the ray into object space to avoid having to transform any BVH nodes, then just transform the intersection point back to world space at the end.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this