Octree - Kd Tree hybrid

29b20ebf71a918e4d2cafe506f67fdb3
0
mutantleg 101 Apr 12, 2010 at 14:00

10-04-11.jpg

Description
It’s a common practice to use octrees and/or kd-trees to speed up rendering/collision detection in games. On my thesis on environmental effects i wanted to use a 3D model for the game level, and used a hybrid version of the trees.

Every node is an axis aligned box. Instead of 8 children per node, there are only 2, which are created based on the dimensions of the node. The tree was also used for detecting collisions between actors, and creates children nodes if a node has more actors in it than the limit allows.

The advantage of this tree was the ease of implementation, the disadvantage was that speed wise it was not the best solution. The speed problems come from that the results of the queries were stored in a stl vector array and used the push_back() method to put pointers to triangles in it, and this was a mistake as it turns out push_back is way slower than i expected. This mistake prevented the tree from being fast enough to have lot of collisions per frame that i wanted to use on particles. I think in this case using a simple array (and an integer to keep track of the last element added) would’ve been a better solution, as only one array is needed and it only needs to store pointers the memory requirements wouldn’t be high either. Wish i thought of this sooner, anyway:

Download link for my thesis game: http://www.multiupload.com/17D4O0A79K
(also it would be a great help if anyone who played with it could fill this survey for me: http://surveys.polldaddy.com/s/C7852DDBE0E5A5AD/ )

6 Replies

Please log in or register to post a reply.

886c9946a5dd9887a33d237ddcc9b7e7
0
phresnel 101 Apr 13, 2010 at 14:18

Instead of 8 children per node, there are only 2, which are created based on the dimensions of the node.

Me wonders about the difference to a regular Kd-Tree, where you are also allowed to put a Bounding Box in.

29b20ebf71a918e4d2cafe506f67fdb3
0
mutantleg 101 Apr 13, 2010 at 16:17

@phresnel

Me wonders about the difference to a regular Kd-Tree, where you are also allowed to put a Bounding Box in.

Not much, in the end it’s but an unbalanced Kd-tree, that uses AABBs for nodes; it’s just that even though a Kd-tree covers quite a lot of type of trees (as it means K dimensional tree as far as i know) people still tend to associate it with the balanced kind that uses splitting planes.

6aa952514ff4e5439df1e9e6d337b864
0
roel 101 Apr 13, 2010 at 21:41

Maybe I’m missing something, but isn’t this just a (binary) BVH?

29b20ebf71a918e4d2cafe506f67fdb3
0
mutantleg 101 Apr 13, 2010 at 22:45

@roel

Maybe I’m missing something, but isn’t this just a (binary) BVH?

It is, with the difference that in a BVH the bounding box would be resized to fit close to it’s contents.

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Apr 15, 2010 at 04:06

Your content’s nice. :)
You need to texture the ground tho. (or add real grass, that would be nice) :)

Oh yeh, and a question… Does it support animatable insides, this kd tree?

Whenever it comes to animation id probably prefer an octree (with erase triangle and add triangle) cause its divisions always stay in the same place, but even if you havent supported animation, could you support it if you tweaked it in?

Id say most the time a game wouldnt bother with “dynamic?” space partitioning, and just leave the majority of the content static, but maybe for a game with tonnes of moving platforms like a 3d mario type game it could pay to implement it, but only if it was worth the trouble.

Its not like its not useful just static, its probably more useful… looks like I talked myself out of my own question. hehe

29b20ebf71a918e4d2cafe506f67fdb3
0
mutantleg 101 Apr 15, 2010 at 11:32

@rouncer

Whenever it comes to animation id probably prefer an octree (with erase triangle and add triangle) cause its divisions always stay in the same place, but even if you havent supported animation, could you support it if you tweaked it in?

Im not exactly sure what you mean by animation, you mean like rebuilding the tree for a vertex animated mesh every frame it changes?

If you just mean adding and removing objects in runtime, it does that with actors (maybe having a different tree for static and dynamic objects would made more sense though)

(btw the windmill the house and the well are just free to use game models)