I wonder if there would be another way to do spatial partitioning.
SofieHerbeck
How do methods of spatial partitioning tend to be chosen? It seems to me that KD-Trees are intuitively the most effective, and BSP-Trees similarly so, but Oct-Trees seem too prescriptive to be really useful ... although maybe their use is in their simplicity, since you don't have to make any decisions about where the dividing plane will go/what its rotation will be? Please advise.
caokevinc
I think decisions still have to be made in constructing the oct-tree, but the decision becomes whether or not to split at a given level instead of how to split, which can greatly simplify the construction and traversal of the tree. To me it seems that it can be more effective as an academic tool, since it provides an order of magnitude optimization, but not necessarily effective in practice optimization.
shadaj
Is Oct-Tree still the term used when dealing with 2D space? I would think that the "Oct" part of this comes from the fact than in 3D space every node will have 8 children since there are two sides for every axis in the space.
SofieHerbeck
@shadaj I believe it was mentioned in lecture that the 2D version of an oct-tree is called a quad-tree
I wonder if there would be another way to do spatial partitioning.
How do methods of spatial partitioning tend to be chosen? It seems to me that KD-Trees are intuitively the most effective, and BSP-Trees similarly so, but Oct-Trees seem too prescriptive to be really useful ... although maybe their use is in their simplicity, since you don't have to make any decisions about where the dividing plane will go/what its rotation will be? Please advise.
I think decisions still have to be made in constructing the oct-tree, but the decision becomes whether or not to split at a given level instead of how to split, which can greatly simplify the construction and traversal of the tree. To me it seems that it can be more effective as an academic tool, since it provides an order of magnitude optimization, but not necessarily effective in practice optimization.
Is Oct-Tree still the term used when dealing with 2D space? I would think that the "Oct" part of this comes from the fact than in 3D space every node will have 8 children since there are two sides for every axis in the space.
@shadaj I believe it was mentioned in lecture that the 2D version of an oct-tree is called a quad-tree