1
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.polld...852DDBE0E5A5AD/ )
