Printable View
does anyone know if there is an significant difference in using these structures for scene management? (so the objects stored in the nodes have bounding boxes, and the nodes of the trees have also boxes (cuboids)
the thing is, when moving to a child in the oct-tree - it relates to moving to 3 children in the kd-tree.
but in the kd-tree the nodes can be fitted better to the objects contained in them.
edit: kd-tree is basically a dual-tree - simlar to quad-tree and oct-tree
If you look at moving to a node in a kd-tree as if you're moving to that node and all its children, then moving to a node in an oct tree would be, at minium, like moving to 8 children, no?Quote:
the thing is, when moving to a child in the oct-tree - it relates to moving to 3 children in the kd-tree.
They are both solving the same problem, just handling the data in a different way. So with proper abstraction, you should be able to use both systems the same way.
>> like moving to 8 children,
no, its 3 children.
an octree-node has 8 children.
a binary tree has, when moving from some node 3 steps down, a total of 2^3=8 children in that level (relative to the node started from).
>> So with proper abstraction, you should be able to use both systems the same way.
yes, thats what im doing anyway. i just don't want to have to implement the interface twice though ;)
(eventually ill do it i guess - but currently i want to continue with the project instead of getting stuck in trying to get like 5% more speed out of it)
i just wondered if anyone has already messed around with that stuff.
well, ive now decided to go along with the kd tree.
(when i used it for my raytracer it worked out pretty well - it could render a 5000 poly object in less than a second (on a 3ghz comp, 512x512)
I see what you mean now. With a kd-tree, you'll have more traversal steps. That's not that bad though.Quote:
when moving from some node 3 steps down, a total of 2^3=8 children in that level (relative to the node started from).
I hope you come up with a good interface so you can interchange the data structures. I've never actually tried to do that, but the API's I've written were easily adaptable. As long as you hide anything to do with the traversal, you should be ok.
At times, I've needed to use the traversal path to my advantage. Createing a traversal object that lets you override callback methods works out pretty well, that way you can process the data in anyway you want, and the traversal still happens automagically.