a very basic kd-tree tutorial?

Do you need a static or dynamic kd-tree? The tree balancing algorithm is fairly annoying, as opposed to simply constructing a balanced kd-tree from a set of points, which is quite easy.

just a static one. I think I got the thory behind the contruction and the traversal, but honestly I don't feel like spending hours trying to fix code. If I can look to a working, basic kd-tree, I would be happier :-)
Thank you!

I was considering writing one (I actually have an article on a related subject). However, if I did it, it would be in OCaml. Do you think you could handle it?

cignox,

jacco bikker's tutorial about raytracing is probably what you are looking for... :)
http://www.devmaster.net/articles/raytracing_series/part7.php

cheers,

Well, the last time I did something with OCaml was several years ago, but I suppose that once I get used with its syntax again, it would be ok... I just hoped to be able to come up with something working this week because next week I will come back to work and I will have much less spare time :-)
Thank you anyway, in the meantime I will try to implement it alone, because for the other features I planned to add soon I can't really use my current brute force approach :-(

Quote:

Original post by ptitjulien cignox, jacco bikker's tutorial about raytracing is probably what you are looking for... :) http://www.devmaster.net/articles/raytracing_series/part7.php cheers,

Yes, I know that tutorial very well :-) It is very good, but it is not really what I was looking for.
Well, perhaps I should stop asking for the simple path, and instead trying to do the dirty job (It's just that I don't find kd-trees very interesting, I would prefer spending time with the 'visual' features) :-)

Thak you all!

Well, I personally suggest much more than KD-Trees so called Hierarchical Bounding Volumes (also reffered as Bounding volume hierarchy, or in short BVH). These are much easier to programme and applicable to dynamic objects in real time.

If you want to know more about BVH, try google - or feel free to ask ;)

IMO KD-Tree isn't the best way to go - too long build times, hardly applicable to dynamic objects. Well long build times - you can try NlogN builder, but that's little damned :D (Those who tried knows what I'm talking about).
Anyway if you do want an really easy spatial structure - try firstly some OcTree (or standard Grid, respectively better so called Nested Grid) - if you want to find out more about them - google, or feel free to ask ;-)

Thank you. Yep, I choosed kd-tree because they are the 'standard de facto' in offline raytracing and because there is a lot of documentation (not much useful when one is lazy like me).
I will give it a look, though as far as I know, making BVH traversal fast enough to be at least comparable to a kd-tree is most probably harder than building the kd-tree in the first place, and since I'm doing offline rendering I'm more interested in traversale speed.

Anyway, I will certainly give it a look, thank you again!

So what's the general consensus here on the best *dynamic* tree?

I have a lot of objects moving around in a very large space, with additions and deletions in real time, and no guarantee of any cohesive grouping, or predictable movement...

I read in a few places that a KD-tree was the way to go, but was not convinced.
I use Octrees at the moment for static groups, and was considering producing either an Octree with some special features, or falling back to a grid with nodes...

I am interested in people's opinions and feedback so that I can try to cut down some of the options / trial and error when I start programming this in anger..

Cheers.

IIRC Jacco Bikker in his Arauna real time raytracer uses BIH for dynamic geometry and kd-tree for static one. Kd-tree is considered to be the fastest available for raytracing, but building the tree can be a slow task, while BIH is a little slower (Once I've read that it should be possible to reach 80% of the performances of a kd-tree) but the building time is much lower, even suitable for real time.

#cignox1 - Anyway if you want suitable times for building kd trees you'll need sooner or later look onto Havran's work - building KD tree in NlogN ... it's maybe one of the hardest ways, but with NlogN KD tree builder your times of it's building will be much better ;)

#scratt - I personally don't recommend KD-trees, because you can't have dynamic geometry with them, ye BVH is slower (or you may try toxie's BIH), but if you'd like dynamic geometry you can add it whenever you want ;).

#cignox1 (2) - BIH building is even faster than BVH one, and both BIH and BVH are suitable for real time. I personally now use BVH, and I'm now about to implement new fast-spherical BVH (now colliding within maximum of 4 subtractions, 5 additions and 8 multiplications - no reciprocal and no square root ... which is IMNSHO damn low) - i got idea about it not so long ago (so still thinking about math though :D).
Hierarchy with bounding spheres (Ye, I know spheres aren't so good for some objects, but IMO it worths testing) can be builded too really fast - not so fast like BIH of course. I'm looking forward to getting some results from it :-)
About KD tree - it's nowadays the fastest available optimisation solution for ray tracing.