How can I efficiently detect intersection detection of a ray and a mesh?

Question

I have several 3d models in an OpenGL ES application for iPhone and at some point i want the user to touch the screen and act on them. The problem is to recognize which, among the ones rendered on the screen, has been touched. In order to achieve this I calculated the picking ray as suggested by the OpenGL FAQ, and I now want to detect if it intersects to any model.

I've looked up at the irrlicht source code and found that I can calculate the intersection between the ray and each single model triangle (they do this by calculating if the ray intersects the triangle plane first and then by seeing whether the intersection point falls into the triangle, but there is a more efficient way to do so as stated here).

My question is: do I really need to do all this computation for each single triangle of every model? Isn't there a better way (maybe not so precise) to achieve a similar result?

Answer 1

You are quite right there ARE better ways to go through the tree. One method is to build an octtree around the object. Then if the ray intersects one of the 8 segments you can check which of its 8 children it intersects and so on until you are left with a few triangles to do an intersection test against. Another method is to build a K-d tree.

There are many many ways to efficiently handle this problem. Look up info on ray tracing acceleration structures.