Monday, March 16, 2009

Out with the Octree in with KD tree

The original plan of using octree data structures for getting basic primitives to work on for the physics implementation was flawed. The size of the initial object would have to be a cube and the object smallest destroyable part would have to be in equal powers of 2 in each dimension.
This is best thought of in terms of a wall that's dimensions are 10*5*1. If the smallest component part, a brick, is 2*1*1 one subdivision of the of the initial root volume would immediately exceed the smallest part on the z-axis. This was therefore no use for modelling destroyable objects that have set smallest parts.
I had to research and find a new solution to this problem. I continued with the idea of using a tree based data structure and look into using a BSP tree. This was more suited as you could choose the split point on the object. However a BSP is limited to two dimensions. This leads onto the KD tree. The KD tree is a special Circumstance of the BSP. It allows for multiple dimensions in the data structure and the split can be down any of those dimensions. This the allows for smallest destroyable parts of any size to be made for the objects without any issues.
The original octree will still be useful in some respects for the project although i cant see any real need to use it now as the KD tree is far more efficient for what im trying to do.

No comments: