a very basic kd-tree tutorial?
Author
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 :-)
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.
Author
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!
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,
jacco bikker's tutorial about raytracing is probably what you are looking for... :)
http://www.devmaster.net/articles/raytracing_series/part7.php
cheers,
Author
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 :-(
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 :-(
Author
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 ;-)
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 ;-)
Author
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!
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
