Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / 3D Theory & Graphics / polygons in an octree Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
takis

April 12, 2005, 09:25 AM

Hello, i want to speed up my ray tracer.
I heard you can use octrees and kdtrees to speed up.

How can you efficiently do this and how many polygons is the maximum to store in a cell of an octree?

 
Scali

April 12, 2005, 09:54 AM

kD-trees are better than octrees for raytracers, because they split the actual dataset rather than the space that the dataset is in. This means that the tree is always balanced, even if you would put a golfball in a football-stadium, or something like that.

It can be implemented reasonably simply... Basically you put a bounding box around your object, and then you use the kD-tree or octree to subdivide the triangles in the object. Then you trace your ray through the bounding box, walking down the hierarchy of the tree... at the leaf you find the nearest bounding box, and you test the ray against the triangles contained in that node. The nearest triangle will give the intersection point you're interested in. Something like that. Perhaps someone can offer other variations on the theme.

 
Marmakoide

April 12, 2005, 12:14 PM

Maybe you have already seen the excellent article from the raytracing series, by "The Phantom" ? It's on flipcode...

 
Christer Ericson

April 13, 2005, 04:02 AM

Scali wrote: kD-trees are better than octrees for raytracers, because they split the actual dataset rather than the space that the dataset is in.


I'm afraid that's not correct. k-d trees and octrees are both spatial partitioning schemes, recursively dividing space into smaller subspaces at deeper levels of the tree. k-d trees split space in two (not necessarily equal) parts; octrees split space into 8 equal size parts.

However, what data you store in a k-d tree or an octree and whether you split that data to the dividing planes of a node or not is entirely orthogonal to the definition of k-d trees and octrees.

For raytracing k-d trees are generally seen as being better than octrees, but that's for other reasons than you mention; for both data structures you'd typically split polygons on insertion to have them (their parts) end up in multiple leaves of the tree.

To answer the OP, though: the basic idea behind any spatial partitioning scheme is that if you can split your data in two (or more) parts such that a ray hits the space of the one partition but not the other, you can clearly discard the second partition of data from further processing.

By recursively partitioning data into parts, you can proceed in the same manner until you have just a few polygons left. At this point you test the ray against all of the polygons.

Usually you repeat this recursive subdivision until there's only some small number of polygons left in a node. Depending on your code and your input geometry this can be, say, 5-20 polygons. There's no one number that works for all applications, so you have to experiment a bit and see what works best for you.

There's plenty of articles on the web describing the construction of spatial partitioning structures like k-d trees and octrees for ray tracing. Search and you'll find them.

Christer Ericson
http://realtimecollisiondetection.net/

 
Scali

April 13, 2005, 06:17 AM

I'm afraid that's not correct. k-d trees and octrees are both spatial partitioning schemes, recursively dividing space into smaller subspaces at deeper levels of the tree. k-d trees split space in two (not necessarily equal) parts; octrees split space into 8 equal size parts.


Yes, that's what I meant, I missed the word 'equally' in my sentence.
"kD-trees are better than octrees for raytracers, because they split the actual dataset equally rather than the space that the dataset is in."
Something like that.

For raytracing k-d trees are generally seen as being better than octrees, but that's for other reasons than you mention; for both data structures you'd typically split polygons on insertion to have them (their parts) end up in multiple leaves of the tree.


I disagree, the reason I mentioned (tree being balanced), is also important for performance. It guarantees O(log N) performance on everything, while octrees may get much worse performance on certain parts of the scene, depending on how evenly your polygons are distributed across space (usually not that equally... picture a room... the structure of the room may be only a handful polys, but objects on a desk or such, may be very highpoly)... which is not good when your camera happens to be zoomed in on such parts.

 
Christer Ericson

April 13, 2005, 11:43 AM

Scali wrote: I disagree, the reason I mentioned (tree being balanced), is also important for performance.

I think we are in agreement here. Without the missing word "equally" I parsed your sentence differently from what you intended to say. k-d trees do indeed adapt to the data in a way an octree cannot in that the splitting planes of an octree are fixed (relative the octree root position and octree size) whereas the k-d tree splitting planes are not.

Of course, there are many additional reasons why k-d trees generally are better than octrees, including that they are much more cache friendly.

Note, however, that balancing the number of primitives equally on either side isn't necessarily (or indeed typically) what you want to do either, because you also want to pick your planes such that they prune off large (possibly empty) regions of space quickly too.


Christer Ericson
http://realtimecollisiondetection.net/

 
Marmakoide

April 13, 2005, 01:06 PM

After all this interesting posts, I have some questions. I need to find intersections in a really HUGE soup of animated geometries : spheres, cylinders, boxes (Mechanical simulation of complex robots in a 3D environnement). Spatial partionning is the key... Because all my geometries move all the time, I must update my space partionning. I must find the good balance between the time to make the partion, and the time to use it for collision. In this case, the regular grid could be better than KD-trees ?

 
Scali

April 13, 2005, 02:40 PM

I would suggest using kD-trees for all static meshes, then move these kD-trees around (well, actually their bounding boxes) in a regular grid or octree or such... not a kD-tree anyway, because it's rather expensive to have dynamic kD-trees.

 
This thread contains 8 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.