Jump to content
  • Advertisement
Sign in to follow this  
cignox1

a very basic kd-tree tutorial?

This topic is 3629 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
Advertisement
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
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
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?

Share this post


Link to post
Share on other sites
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
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
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
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
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
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!