i just learned about kd-tree (and i've read a lot), i am trying to implement it on frustum culling for my games, but something make me confuse: 1.during the construction of kd-tree, each iteration is splitting the space using plane on some axis, then for next iteration (on its child) on next axis, and so on, how do i know the box (AABB) of the space (each tree node) if each node is only have information where its space is splitted on one axis? 2.most kd-tree implementation and example are for points in 3D space, how to implement on AABB of entities? should i treat those entities as 8 points per AABB? 3.how to handle moving object, do i really need to reconstruct the kd-tree each frame?, reconstruct the node where the object has leave each frame?, and do i need to update (and check) the tree when entity is moving, or every rendering step (each frame)? thanks

First, let me say that I haven't actually used kd-trees myself, so these answers will be speculative (based on my understanding of them). If I have anything wrong though, I'm sure someone who's worked directly with kd-trees will be able to clarify.

Quote:1.during the construction of kd-tree, each iteration is splitting the space using plane on some axis, then for next iteration (on its child) on next axis, and so on, how do i know the box (AABB) of the space (each tree node) if each node is only have information where its space is splitted on one axis?

Presumably you begin the process with an AABB that encompasses all the geometry of interest. Splitting an AABB along a cardinal hyperplane yields two AABBs; therefore, each time you split a node, you should end up with two AABBs. As such, you should know the full bounds (AABB) for any node or leaf in the tree.

Does that make sense?

Quote:2.most kd-tree implementation and example are for points in 3D space, how to implement on AABB of entities? should i treat those entities as 8 points per AABB?

No, don't use the 8 corners of the AABB. Instead, treat the AABB as a solid, and determine which leaves of the tree the AABB overlaps (it may overlap more than one).

This is touched on briefly in the Wikipedia article on kd-trees.

Quote:3.how to handle moving object, do i really need to reconstruct the kd-tree each frame?, reconstruct the node where the object has leave each frame?, and do i need to update (and check) the tree when entity is moving, or every rendering step (each frame)?

I don't know that this question has a single 'right answer', per se - it depends on a number of factors, such as the data structures being used, the ratio of static objects to dynamic objects, and the total number of objects in the simulation.

Quote:Presumably you begin the process with an AABB that encompasses all the geometry of interest. Splitting an AABB along a cardinal hyperplane yields two AABBs; therefore, each time you split a node, you should end up with two AABBs. As such, you should know the full bounds (AABB) for any node or leaf in the tree.

Does that make sense?

ok, so i just need to store AABB information of node space on each node on kd-tree. thanks, that made sense.

Quote:No, don't use the 8 corners of the AABB. Instead, treat the AABB as a solid, and determine which leaves of the tree the AABB overlaps (it may overlap more than one).

should AABB only reside on exactly one leaf (using some decision) or i should put the pointer to more than one node if it intersect with more than one nodes?

Quote:I don't know that this question has a single 'right answer', per se - it depends on a number of factors, such as the data structures being used, the ratio of static objects to dynamic objects, and the total number of objects in the simulation.

how does another spatial partitioning do with it? lets say octree/quadtree?

The first 2 questions are answered nicely by the above posters. For the 3rd one, it does depend on your scene itself.

If your scene is small, you can get away with rebuilding the entire tree no problem. For frustum culling, you aren't likely going to the triangle level in your tree, so the tree probably isn't that expensive to rebuild anyways.

If your scene is larger, consider having 2 acceleration trees, one for static objects and one for dynamic objects. The static one can be built for optimal traversal speed, and the dynamic one can be something like a bvh tree or a kd-tree built in a fast manner (not necessarily optimal for traversal).

And if this is just for frustum culling and not collision/ray-tracing as well, then you might consider just not putting the dynamic objects into a tree at all and just doing a simple bounding-box test with the camera's frustum. If there aren't thousands upon thousands of dynamic objects, this should still be fine.

Or once a dynamic object comes to rest for a time, then you could add it to the tree, and remove it again when it moves, and do the naive simple test on the moving objects. Then you only have to rebuild the tree when an object starts/stops. In any event, you can keep track of when dynamic objects move and only rebuild the tree on those frames, but, that might be every frame anyways.

rvx, for your #3:

I use kd-trees for collision detection (they are actually heuristic based kd-trees, I guess more like ABT, to allow faster construction/rebuilding). Each node in this tree keeps a counter - number of objects contained in its sub-trees. Whenever objects are removed / inserted / moved, these counters are updated (for node and all its ancestors).

Now after all objects are moved, I check if kd-tree needs to be re-balanced. Every kd-tree node has two children. Starting at root node I check if ratio of objects in left sub-tree / right sub-tree passes "acceptance" threshold. For my purposes I found 40-60 % ratio to be ok (that is if one of sub-trees contains less than 40% or more than 60% i re-balance). If node passes this test, then it does not require rebuilding: you can recursively descend into children and check if they require rebuilding. If it does not pass the test, you rebuild the node.

In my experience this system works rather well (I use highly dynamic 3d particles).

ttvd