Difference between KD-tree and a AABB BV tree
Author
I just wrote a Bounding Volume tree that uses AABB's to split up the triangle soup. The algorithm essentially works like this, find the longest axis and then find the mean of all the triangle's centroids along that axis and split the AABB at that point. I just researched kd-tree's and it essentially looks like its doing the same thing.
Provided you world is finite in size, the AABB-tree is binary and the bounding volumes never overlap then you have a kd-tree. Excepth with larger memory footprint. But a AAB-tree is not necesarily binary and doesn't need to partition space (the union of two children can be smaller than the parent in general, although that might not be the case in your tree), so not all AABB-trees are equivalent to kd-trees.
You'll probably get better results by using the surface area heuristic when building the tree btw. Esentially you choose a split point such that num_of_tris_in_child*child_surface_area is minimised. Google for more info.
You'll probably get better results by using the surface area heuristic when building the tree btw. Esentially you choose a split point such that num_of_tris_in_child*child_surface_area is minimised. Google for more info.
I agree w/ GameCat. I use a surface area heuristic in my bvh and my aabb tree classes, and it is MUCH faster when using it at runtime for raycasts & collision.
My aabb tree uses both split methods, however. Usually, you want to use the Surface Area Heuristic to decide where to split, but if you don't clip polygons, you may not make progress.
For instance, if you have too many tris for a leaf node, and you want to split, you may decide on a certain split axis, and then try to split the two children, but then find that all of the tris end up in the same child. This can lead to a stack overflow, or a hang, depending on how you code it.
For my AABB tree what I do is to try the SAH on every polygon vertex, for all 3 axes, and choose the best one. If that fails for some reason, I just use the median method, where you choose the longest axis, and force half of the tris on one side, and half on the other. So the median method is a good fallback, because it always makes progress in terms of reducing the # of items in a node. Even if all tris have the exact same distance from the split plane, half will go on one side, and half on the other.
For the BVH tree, I just do the SAH method on all 3 axes, at a fixed # of positions along each node, like 7 positions, each one 1/9 along the axis. I skip positions 0.0 and 1.0 for obvious reasons.
Some other tips when coding this sort of thing :
1) You can store > 1 triangle in a leaf node. This has the advantage of keeping your memory footprint from exploding, without having to compress your nodes or leafs. I store ~6 triangles per node, use floats for my bounding boxes, and average ~6 bytes per triangle of storage for the whole tree. This seemed easier to me compared to using byte[3] for bounding boxes, etc.
2) Your splitting code is crucial to get right - I had a bug last night that caused my game to run 50% slower, due to a screwy split function, which I fixed, and got my perf back.
3) Get your tree working in the simplest way possible, and if you later find that it's too slow to build the tree, one speedup is not to allocate anything in your build functions. My old version passed const refs to std::vectors created on the stack full of items for each child node. My new version creates 3 vectors up front, one each for sorting by x, y & z, and passes index ranges down to each new child. Each child then sorts just its range in order to find its best split axis, rather than allocating a new vector. This sped up the build process by ~80%.
[Edited by - SimmerD on May 27, 2005 11:40:21 PM]
My aabb tree uses both split methods, however. Usually, you want to use the Surface Area Heuristic to decide where to split, but if you don't clip polygons, you may not make progress.
For instance, if you have too many tris for a leaf node, and you want to split, you may decide on a certain split axis, and then try to split the two children, but then find that all of the tris end up in the same child. This can lead to a stack overflow, or a hang, depending on how you code it.
For my AABB tree what I do is to try the SAH on every polygon vertex, for all 3 axes, and choose the best one. If that fails for some reason, I just use the median method, where you choose the longest axis, and force half of the tris on one side, and half on the other. So the median method is a good fallback, because it always makes progress in terms of reducing the # of items in a node. Even if all tris have the exact same distance from the split plane, half will go on one side, and half on the other.
For the BVH tree, I just do the SAH method on all 3 axes, at a fixed # of positions along each node, like 7 positions, each one 1/9 along the axis. I skip positions 0.0 and 1.0 for obvious reasons.
Some other tips when coding this sort of thing :
1) You can store > 1 triangle in a leaf node. This has the advantage of keeping your memory footprint from exploding, without having to compress your nodes or leafs. I store ~6 triangles per node, use floats for my bounding boxes, and average ~6 bytes per triangle of storage for the whole tree. This seemed easier to me compared to using byte[3] for bounding boxes, etc.
2) Your splitting code is crucial to get right - I had a bug last night that caused my game to run 50% slower, due to a screwy split function, which I fixed, and got my perf back.
3) Get your tree working in the simplest way possible, and if you later find that it's too slow to build the tree, one speedup is not to allocate anything in your build functions. My old version passed const refs to std::vectors created on the stack full of items for each child node. My new version creates 3 vectors up front, one each for sorting by x, y & z, and passes index ranges down to each new child. Each child then sorts just its range in order to find its best split axis, rather than allocating a new vector. This sped up the build process by ~80%.
[Edited by - SimmerD on May 27, 2005 11:40:21 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
