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:

• 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.
  
  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 that 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.

spacial database 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 Octrees. 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.

There are a lot of factors when selecting the best approach. For example:

• 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?
  
  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.
  http://stackoverflow.com/questions/10228690/ray-octree-intersection-algorithms

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 QBVH (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.