Sign in to follow this  
cignox1

a very basic kd-tree tutorial?

Recommended Posts

cignox1    735
Hi all, I'm trying to implement a kd-tree for my raytracer, but I cannot find a simple tutorial to follow. The ones I've found (included the PBRT book) aim to build a highly performant tree, while I just need a very simple, easy to implement and working one, before thinking how to speed it up. My problem is that I find it hard to figure out wich the basic steps are inside all that optimization code... I could build one for myself from scratch, but this is the first time I implement a spatial structure, and a help would be great :-)

Share this post


Link to post
Share on other sites
ToohrVyk    1595
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.

Share this post


Link to post
Share on other sites
cignox1    735
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!

Share this post


Link to post
Share on other sites
ptitjulien    150
cignox,

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

cheers,

Share this post


Link to post
Share on other sites
cignox1    735
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 :-(

Share this post


Link to post
Share on other sites
cignox1    735
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!

Share this post


Link to post
Share on other sites
Vilem Otte    2938
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 ;-)

Share this post


Link to post
Share on other sites
cignox1    735
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!

Share this post


Link to post
Share on other sites
scratt    102
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.

Share this post


Link to post
Share on other sites
cignox1    735
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.

Share this post


Link to post
Share on other sites
Vilem Otte    2938
#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.

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