octrees vs kd-trees

I've been working very hard on a kd-tree implementation over the weekend, so let me answer your questions. :)

The kd-tree is very superior to the octree. It doesn't take that long to build; my current code takes about a second for a scene consisting of 3000 triangles (a torus knot floating in empty space). I'm using a quite expensive algorithm to determine the split plane orientation and position, so your results could even be better if you keep it simpler.

But even if the sum of building the tree and tracing a scene using it is more expensive for the kd-tree than for the octree, it might be worth it: First, you could save the constructed tree. It can be loaded in milliseconds. Second, you may wish to render multiple frames. I let the knot spin on the screen, so I use the tree several times. And, lights don't end up in the tree, so you can have a dynamic viewpoint and light sources, without recalculating the tree.

I have implemented the SAH (surface area heuristic) that Wald describes in his thesis on the OpenRT renderer. He points to several other authors; the most relevant one is probably Havran, who wrote a thesis on spatial subdivision schemes for accelerating ray tracing. Chapter 4 of his thesis deals with the construction of efficient kd-trees, you could have a look at that. The thesis is available online.

Other algorithms: I have been working closely together with Thierry Berger-Perrin (sse superman), he used to use a BVH (bounding volume hierarchy). This is only good if you view your model from outside, and even then it can't keep up with a kd-tree. The kd-tree is by far the best solution. Wald states in his thesis that a properly built kd-tree is about twice as fast as an octree.

Shameless plug: My sse packet ray tracer now shoots 1.3M rays through a 3k triangle scene, resulting in slightly more than 3fps @ 512x512 resolution, on a 1700Mhz laptop. :) Closing in on Wald. ;)

Quote:

Original post by phantomus Shameless plug: My sse packet ray tracer now shoots 1.3M rays through a 3k triangle scene, resulting in slightly more than 3fps @ 512x512 resolution, on a 1700Mhz laptop. :) Closing in on Wald. ;)

very nice work there mate :)

one day i should get around to making a kd-tree: they are indeed far superior to an octree, and not all that more complex. actually, the only more complex thing is the construction, but you can choosebetween varying degrees of complexity, and even this surfacearea heuristic is quite doable if i remember correctly. on sparse scenes it can be orders of magnitude better than an octree.

i was pondering dynamic scenes for a bit, and the fact that you dont want to recalculate them every time. would it be efficient to use a hierarchy of non-axis aligned kd-trees? each rigid and non-axis aligned body has a precalculated kd-tree, placed inside a global and every frame recalculated kd-tree. once a ray, started tracing in the global tree hits the aabb of a subtree, just transform the ray into the coordinate system of the subtree and continue tracing.

that way youd only have to recalculate a quite shallow tree for all dynamic objects, would be very realtimish i suppose. but would the speedhit of transforming the ray be very big compared to traversing the tree? i think not. another problem is: a lot of the global tree contains static geometry, which doesnt need rebuilding. but you cant really partly rebuild a tree, can you? maybe a seperate static tree would be better, which is calculated using the best heuristics there are. but that would be kind of doubling your casting time though...

well ive gone far enough OT already.

Constructing kd-trees is not very hard indeed; you could even start with alternating orientations and split plane positions in the middle; this would basically give you an octree. From thereon you could improve things.

SAH is not very difficult, but it can be quite slow. The funny thing is, it gets faster as you progress through the more complex things, like primitive clipping (which improves the accuracy of the SAH scores).

About dynamic scenes: I have no experience with this yet, but Wald has dedicated quite a large chunk of his thesis to this topic. It's a good read, I suggest you check it out.

BTW I will release the code for the ray tracer, but right now it's not in a very nice shape (actually at this very moment it isn't even working ;) ). I'm still in doubt wether or not I should write another tutorial for Flipcode on ray tracing; I have a feeling that the latest articles from my series where already a bit too much for most readers. :)

i dont check flipcode so i havnt seen your articles, but ill read them when i have the time. wald also sounds interesting, thanks for the tip.

Hey Phantomus,

Here's one Flipcoder that has really enjoyed them :). I've actually used an octree for everything I've done in the past (mostly general ray casting around a scene for things like ambient occlusion, and for swept sphere tests against triangle soups). However, since tutorial 7 of your series I thought I'd give kd-trees a go. I'm currently at the stage where I need to use some decent heuristics to build it, but its currently about as fast as the octree version at runtime due to your lovely packing of the nodes!
I think the octree was reasonably well optimized as well, since I built it bottom up removing empty nodes, and then did another pass to shrink the nodes down to the triangles within (implicitly clipping to get a tight fit). However, I think keeping the nodes small is a really big win since its the traversal that seemed to take up quite a large portion of whatever it was I was doing.

I'll have to build the kd-tree to create a similar partitioning to the octree and time them both to see which is best. Glad i've got xmas hols coming up :).

T

If you Jacco B., then I've read them all. I even wrote you an e-mail about a month ago (sender:Honza). Anyway, it takes over 2 minutes on my 700mhz Athlon to build the tree for your scene from the seventh tutorial (+40 secs for the raytracing itself). That's why I though it's so slow.

I've already started reading Walds work.

Nice work on the tutorials, really *thumbs up*

yeah excellent tutorials! you made me miss my meeting :P

im sure there are a lot of people on gamedev you could help with it, try pimping it here a little, im sure dave would like to host such a good series.

btw, you visit the blitzbasic codearchives/forum? or did you just stumble across them? in case of the former we might know eachother.

Quote:

Original post by Caesar Anyway, it takes over 2 minutes on my 700mhz Athlon to build the tree for your scene from the seventh tutorial (+40 secs for the raytracing itself). That's why I though it's so slow.

I've been thinking lately to find a way to speed up the building process but haven't really come up with a solution (yet). Building gets a lot slower as more complex models are in the scene:
ex.
I tried it with a 50000 poly model and it took +- 15 minutes just to find the first splitposition. Even after 4 hours the tree still wasn't build.
(2 GHz processor)

Most of the time is spend in determining the number of objects in each child node for each splitposition. Are there any good ways to solve this?

Quote:

Original post by Lotuspec Most of the time is spend in determining the number of objects in each child node for each splitposition. Are there any good ways to solve this?

well, id say discard the mayority of splitpositions on a much cheaper condition. dont know what those conditions would be, but its obvious a lot of splitpositions dont makeany sense.

the buildtimes you mention do sound very extreme indeed, it must be possible to do better, otherwise building a multi-million tree would be impossible.

Over the weekend I added primitive clipping to the kd-tree construction code: As I switched to pure triangle meshes, this is not too hard. The result is a set of vertices that fits in the node that is being split. This seriously speeds up the rest of the operations: Split plane position candidates are the sides of the bounding box of these vertices, so there are only two per triangle for each plane orientation. The same happens when assigning the primitives to both subvoxels: First a simple test of the same extrema tells you if all vertices are to the left of the plane, or all to the right (or spanning otherwise).

In practise: I got more precision from the clipping, *and* I added evaluation for all three axii, instead of just the major axis, as I did in article 7. That's three times more work, yet it runs now in 1 or 2 seconds, and that's for a much more complex scene than the one in article 7.

I can post the kd-tree code here, if someone desperately needs to take a look at it. It will be a while anyway before I write the next article (coding is too much fun atm).

On top of what has been said i'd like to stress that even if a full SAH implementation has to dodge lots of quadratic behaviours, it's not doomed to be irremediably slow (with proper sortings etc).

Case in point, i could compile a bvh for the xyz_dragon (7M triangles) under 5 minutes.

My kdtree compiler is a bit slower right now for a given number of nodes but it doesn't have to, it's just because of sloppy code. And bugs ;)

tbp.

PS: Phantomus, yes i'm sure you're gonna lose whatever readers you had past episode 7 :p

Quote:

Original post by tbp PS: Phantomus, yes i'm sure you're gonna lose whatever readers you had past episode 7 :p

i think it just starts to get interesting :)

triangular bezier patches in a slick KD-tree... should be pretty impressive. i wont be bored during the holidays, thats for sure :)

Phantomus we need to synchronize :)

That's exactly how i do it.
As split positions can only be at extremums (and voxel/tri intersections, but that's another issue), you only need to carry bounding boxes thru the SAH evaluation.
Sort them on each axis, compute a list of potential splits, and then you always know how many primitives you have left and right of any split position (for bvh you can also precompute the area of shrunken left/right voxels).

A side effect is that compilation time now depends mostly on how "structured" your triangle soup is, that is how many potential splits have to be inspected.

Quote:

Original post by phantomus I can post the kd-tree code here, if someone desperately needs to take a look at it. It will be a while anyway before I write the next article (coding is too much fun atm).

i might ask you later.

i dont want any of the fun spoiled: ill first try myself. then ill see what i will continue to use.

omg!

i though i had found wald's paper (but unsurprisingly he has authored more than one)

anyway i just found the link to his real paper at the bottom of your tut.

my god. it has tripeled the size of my reseachpapers directory. i guess i will also triple my nerd-factor when i work myself completely trough that beast! :P

Yeah it's a beast, size-wise. But don't worry, it's an easy read, for the most part. And you can simply pick your area of interest and skip the rest.

Beware though; Wald is not just writing this to share his knowledge, apparently: The pseudo-code contains bugs (lots), the text is missing crucial details and he keeps saying how fast and wonderfull OpenRT is. :) I mean, he has the right to be proud of course, but it feels a bit commercial.

If you need more details on kd-trees, you may wish to turn to Vlastimil Havran, also linked to from my articles on flipcode. His thesis is far more scientific (and harder to read), but his info is exhaustive and accurate. The man can tell you everything you didn't want to know about kd-trees. :)

... clicky linky...
http://www.cgg.cvut.cz/~havran/phdthesis.html
http://www.graphicon.ru/2002/pdf/Hurley_Kapustin_Reshetov_Soupikov_Re.pdf
http://www.mpi-sb.mpg.de/~guenther/vvh.pdf
etc..

Hmm, lost references for fast tree/hierarchy updates.