Ask for resource about fast ray-tracing algorithm

Question

First, I am sorry for this rough question, but I don't want to introduce too much details, so I just ask for related resource like articles, libraries or tips.

My program need to do intensive computation of ray-triangle intersection (there are millions of rays and triangles), and my goal is to make it as fast as I can.

What I have done is:

1. Use the fastest ray-triangle algorithm that I know.

2. Use Octree.(From Game Programming Gem 1, 4.10. 4.11)

3. Use An Efficient and Robust Ray–Box Intersection Algorithm which is used in octree algorithm.

It is faster than before I applied those better algorithms, but I believe it could be faster, Could you please shed lights on any possible places that could make it faster?

Thanks.

Answer 1

The place to ask these questions is ompf2.com. A forum with topics about realtime (although also non-realtime) raytracing

Answer 2

OMPF forum is the right place for this question, but since I'm here today...

Don't use a ray/box intersection for OctTree traversal. You may use it for the root node of the tree, but that's it. Once you know the distance to the entry and exit of the root box, you can calculate the distances to the x,y, and z partition planes - the planes that subdivide the box. If the distance to front and back are f and b respectively then you can determine which child nodes of the box are hit by analyzing f,b,x,y,z distances. You can also determine the order to traverse the child nodes and completely reject many of them.

At most 4 of the children can be hit since the ray starts in one octant and only changes octants when it crosses one of the 3 partition planes.

Also, since it becomes recursive you'll be needing the entry and exit distances for the child nodes. These distances are chosen from the set (f,b,x,y,z) which you've already computed.

I have been optimizing this for a very long time, and can safely say you have about an order of magnitude performance still on the table for trees many levels deep. I started right where you are now.

Answer 3

There are several optimizations you can do, but all of them depend on the exact domain of your problem. As far as general algorithms go, you are on the right track. Depending on the domain, you could:

1. Introduce a portal system
2. Move the calculations to a GPU and take advantage of parallel computation
3. A quite popular trend in raytracing recently is Bounding Volume Hierarchies

Answer 4

You've already gotten a good start using a spatial sort coupled with fast intersection algorithms. For tracing single rays at a time, one of the best structures out there (for static scenes) is a K-d tree built using the Surface Area Heuristic.

However, for truly high-speed ray tracing you need to take advantage of:

• Coherent packets of rays
• Frusta
• SIMD

I would suggest you start with "Ray Tracing Animated Scenes using Coherent Grid Traversal". It gives an easy-to-follow example of such a modern approach. You can also follow the references to see how these ideas are applied to K-d trees and BVHs.

On the same page, also check out "State of the Art in Ray Tracing Animated Scenes".

Another great set of resources are all the SIGGRAPH publications over the years. This is a very competitive conference, so these papers tend to be top-notch.

Finally, if you're willing to use existing code, check out the project page for OpenRT.

Answer 5

A useful resource I've seen is the journal of graphics tools. Depending on your scenes, another BVH might be more appropriate than an octree.

Also, if you haven't looked at your performance with a profiler then you should. Shark is great on OSX, and I've gotten good results with Very Sleepy on windows.