Some notes about oct tree. This is the online video
Basic ideas about oct tree
The structure of the tree
The idea of the oct tree or quad tree is a spatial decomposition structure. We can decompose the spatial by a bisection manner and refine it as needed.
What does the node represent
The node of the structure represents the current bounding box. The coordinates of the bounding box is the basic element of the node.
Common operations
There are two set of refine principles, one is to refine based on space coordinates. Another is to refine it based on the actual variable value.
With this structures, we can refine the data in an adaptive manner. For example, the mesh can be dense for the region we are interested. We can further refine the region if the specific condition is not satisfied.
This condition can come from two aspects, one is the property of the physical space, for example, each node contains less than n points then stop the refinement.
Another one is the property of the actual physical value. For example, we may only stop the refinement when the data variance is less than a specific value or threshold
The basic use scenarios of the oct tree
Refer to common uses sections of wiki page:
Render more details in specific area
Search the closest points
Detect the relationship with the closest points (such as the collision detection)
Example of using the oct tree in VTK
current example
https://kitware.github.io/vtk-examples/site/Cxx/#octree
input a data set and output the octtree
The associated code is at
Particular nodes:
VTK/Common/DataModel/vtkOctreePointLocatorNode.cxx
The associated tree structure:
VTK/Common/DataModel/vtkOctreePointLocator.cxx
5MCST example, input a polydata and then output oct tree locator
There are two kinds of boundry, the firs one is the spatial boundry (coordinates bounudry) for each dimentsion, the second one is the data boundry for each dimension.
Understanding VTK oct tree implementation
core structure of the oct tree
DivideRegion is a high level function, and there is recursive call based on this function. The main refinement operation is implemented based on this function.
node structure and the tree structure
condition to determin when to complete the refine operation is based on the level information or the number of points in the node or the MaximumPointsPerRegion (the default one is 100) DivideTest contains the condition to decide if to do the further refinement operation.
Be careful about the index part, use three digit to represent it. The index start from 000 to the 111 For each dimention, it can either be 0 or 1, the number of digits equals to the numbers of the dimention. If is larger than middle position value, the index is 1 for that position, otherwise, the index is 0.
In DivideRegion function, order array is a little bit tricky to understand.
Originally, we set it by natural order, then during the index computation, we select out the points belonging to each sub space, these index are stored into a points list, then we reuse that order array, for each sub division, we try to assign it to corsponding segment of the ordering array. Then setting the start position of the order at different position based on the counter. Without this array, we can not know how many points belongs to the next level after the subdivision. We do not know the virtual nody contains how many points.
Difference between the OCTree and HyperGridTree
The octtree is like a kind of index based on the specific dataset. We can use the octtree as the locator to find the specific points. The original data is in a different structure and we build the oct tree overit. The HyberGridTree is different, its original data is stored in the tree format direactly.
(TODO) amr data in the hdf5 format
