Could you please explain more about the difference between octree and K-D tree? I think both of them split the whole space into non-uniform subspace, but I didn't quite know the difference between them.
merc
If K-D trees have better intersection performance than quadtrees/octrees, then in what situations would we reasonably prefer this over K-D trees? Just construction costs?
ljelenak
@yongchi1 I think the difference is that the octree splits it among the grid, as you can see how it is all squares here (basically split into 4 even squares every time), but a KD tree has non uniform splitting, and that the cuts don't exactly line up.
mdsavage
@merc I think another upside of the quadtree/octree over the K-D tree is that it supports random access at every level: given a point and a level of the tree, you can always compute which tree node (i.e., space partition) it corresponds to at that level. This isn't true of the K-D tree since its partition points are determined by its contents, so you would have to traverse the K-D tree top-down each time to do the same operation.
I have no idea if this is a common operation in practice, however. It seems like it could reasonably be useful if the scene is large and most collision tests would happen in a very small area (perhaps triangle-triangle collisions where each triangle is much smaller than the scene), since you could then feasibly skip multiple layers of the tree and jump to the region of interest. (I wonder if you could make a hybrid tree that starts as a quadtree/octree and switches to a K-D tree at a certain depth for such a situation?)
Leslie
In my perspective, K-D tree and Octree are kind of similar, but I assume there should be some conditions that one algorithm always outperforms the other. What are the factors that help us to decide which one we should choose?
acpatel
Here we express that one of the advantages of the octree over a kd-tree is that it is easier to build, since we only have to split along grid planes. Is the easiness to build actually ever a factor when we are determining what data structure to use? This operation will only perform once for the mesh so how much does the time building the data structure takes factor in to which spacial data structure we choose? Shouldn't we always choose the data structure that allows us to perform the fastest queries, not build the representation of the mesh the fastest?
Could you please explain more about the difference between octree and K-D tree? I think both of them split the whole space into non-uniform subspace, but I didn't quite know the difference between them.
If K-D trees have better intersection performance than quadtrees/octrees, then in what situations would we reasonably prefer this over K-D trees? Just construction costs?
@yongchi1 I think the difference is that the octree splits it among the grid, as you can see how it is all squares here (basically split into 4 even squares every time), but a KD tree has non uniform splitting, and that the cuts don't exactly line up.
@merc I think another upside of the quadtree/octree over the K-D tree is that it supports random access at every level: given a point and a level of the tree, you can always compute which tree node (i.e., space partition) it corresponds to at that level. This isn't true of the K-D tree since its partition points are determined by its contents, so you would have to traverse the K-D tree top-down each time to do the same operation.
I have no idea if this is a common operation in practice, however. It seems like it could reasonably be useful if the scene is large and most collision tests would happen in a very small area (perhaps triangle-triangle collisions where each triangle is much smaller than the scene), since you could then feasibly skip multiple layers of the tree and jump to the region of interest. (I wonder if you could make a hybrid tree that starts as a quadtree/octree and switches to a K-D tree at a certain depth for such a situation?)
In my perspective, K-D tree and Octree are kind of similar, but I assume there should be some conditions that one algorithm always outperforms the other. What are the factors that help us to decide which one we should choose?
Here we express that one of the advantages of the octree over a kd-tree is that it is easier to build, since we only have to split along grid planes. Is the easiness to build actually ever a factor when we are determining what data structure to use? This operation will only perform once for the mesh so how much does the time building the data structure takes factor in to which spacial data structure we choose? Shouldn't we always choose the data structure that allows us to perform the fastest queries, not build the representation of the mesh the fastest?