Ask for resource about fast ray-tracing algorithm

Question

Hi, All,

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 ompf.org. A forum with topics about realtime (although also non-realtime) raytracing

Answer 2

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 3

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 4

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.