Sign in to follow this  
Quat

octrees for ray tracing

Recommended Posts

Hi, I have a triangle based ray tracer which just traces each triangle one by one. It is very slow for all but simple meshes, so I want to add an octree to eleminate lots of wasteful tests. I just wanted to know if my algorithm is correct before I start working on the code. Here it is: Build one AABB that contains the whole scene. Subdivide box into 8 octants, and sort triangles amongst them. Repeat recursively until a leaf box contains no more than some some fixed number of triangles. So I guess this would be a "leafy" octree, where internal nodes just store an AABB, but the leaf nodes store a collection of triangles. Then once the data structure is built, I shoot a ray at the root box. It interesects it, so I test against each of its children boxes. Then continue recursively down each child box the ray intersects until I hit the leaf boxes--then do ray-triangle intersection tests. So as I recurse, I will miss entire boxes and therefore eleminate many tests with one AABB/ray test.

Share this post


Link to post
Share on other sites
That looks correct for the most part, but I should mention that there are a great deal of pitfalls and optimizations that you may not consider.

Here's one such example: Suppose a triangle (Tri1) is contained in two cells of the octree, cell A and cell B (this will be the case for a great deal of triangles). You shoot a ray that intersects cell A and cell B, and is supposed to hit a second triangle (Tri2) in cell B that lies in front of Tri1.

Suppose the ray enters cell A, and tests against Tri1. It returns a positive hit because it would have eventually hit Tri1 if it continued on through cell B and past Tri2. If you had stopped here, you would have found the wrong intersection! (Tri1 instead of Tri2). You instead need to halt if the last intersection is closer than the back edge of the cell.

This further means that you may need to test against the same triangle multiple times. A technique called "mailboxing" avoids this.

I should also mention that a similar structure often called a KD tree is usually even more efficient than an octree.

If you're really interested, then I HIGHLY recommend you pick up a copy of "Physically Based Rendering" (Pharr and Humphreys). It's pretty expensive, but is a phenomenal resource for any personal raytracer. It includes full code for everything, including an octree and KD tree implementation, with great explanations.

Share this post


Link to post
Share on other sites
http://chiranjivi.tripod.com/octrav.html

Although it's written on the basis of generating a list of nodes crossed by the ray (presorted in ray order), you can use it all the same for immediate processing.

Quote:
I should also mention that a similar structure often called a KD tree is usually even more efficient than an octree.

If it's balanced... Where I work, we use kd-trees for searches on the X360/PS3, but only for stuff that's static and specifically for data where points are loose enough that the recursion depth for a kd-tree is about the same as any other spatial subdivision hierarchy. The cost of balancing becomes totally offline. For a separate problem, we've got a little higher point density, and so an octree is preferable and a kd-tree is out of the question because recursion depth is pure evil on these architectures. In either case, we never use either for raycasts -- more for locality searches.

Quote:
use kd-tree, it's much simplier and faster.

I can think of plenty of cases where it's much faster, and plenty of cases where it's much slower. But there has never been, nor can I even think there ever could be, a case where I'd call it simpler in any way whatsoever.

Share this post


Link to post
Share on other sites
A proper SAH kd-tree is definitely much faster in more situations than an octree. However, it's a nightmare to implement correctly. A much simpler solution is a BIH . You can add full or partial SAH to the building of this to speed it up to. It's not as fast as a kd-tree, but it's not that much slower.

Check out the forums at http://ompf.org/forum for more info and links to papers on building good kd-trees and BIH for raytracing.

Share this post


Link to post
Share on other sites
One thing that needs to be noted is that you really want a maximum depth for your octree. Otherwise, its very easy to run out of memory in pathological scenes.

Quote:
Original post by cpiasminc
http://chiranjivi.tripod.com/octrav.html

Although it's written on the basis of generating a list of nodes crossed by the ray (presorted in ray order), you can use it all the same for immediate processing.

Quote:
I should also mention that a similar structure often called a KD tree is usually even more efficient than an octree.

If it's balanced... Where I work, we use kd-trees for searches on the X360/PS3, but only for stuff that's static and specifically for data where points are loose enough that the recursion depth for a kd-tree is about the same as any other spatial subdivision hierarchy. The cost of balancing becomes totally offline. For a separate problem, we've got a little higher point density, and so an octree is preferable and a kd-tree is out of the question because recursion depth is pure evil on these architectures. In either case, we never use either for raycasts -- more for locality searches.


Actually, If surface area heuristics are used for tree building, the trees tend to be extremely unbalanced. You want to have lots of empty nodes in the tree so that intersection tests are avoided, so this tends to lead to long, stringy trees. Using balanced trees for ray casting is actually easier and faster for building the tree (you can just repeatedly split near the median of the primitive list), but its slower for ray casting, because the tree doesn't create as much empty space.




Share this post


Link to post
Share on other sites
well.. BIH is very slow. it will give you a lot of overlaping spaces. maybe building it is fast but raytracing is nightmare. quite impractical idea.
i think the top method today is still KD-trees.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
www.ompf.org has some forums you need to check out.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by biki_
well.. BIH is very slow. it will give you a lot of overlaping spaces. maybe building it is fast but raytracing is nightmare. quite impractical idea.
i think the top method today is still KD-trees.


No. Pop some animations in your ray traces and try to render them with a dynamically compiled kd-tree. Have some fun with it.

To say it again: Check out ompf's forum (ompf.org)

my site

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