linear octree презентация

Linear Octree Ref: Tu and O’Hallaron 2004 Simple and Efficient Traversal Methods for Quadtrees and Octrees, Frisken and Perry 2002

Pointer-based Representation

Linear Octree Assign a unique key (locational code) to each node Represent an octree as a collection of lear nodes comprising it Extremely useful in practice when main memory cannot accommodate a pointer-based octree

Locational code The code for each node is of the same length (zero-padded) Level of the node is also attached

Octree and Linear Octree

Observation When we sort the leaf nodes according to their locational codes (as binary scalars), the order is the same as the preorder traversal of the octree In octree, we may use octal number for coding

Simple and Efficient Traversal Methods for Quadtrees and Octrees Frisken and Perry 2002 (MERL) Usually locational code is for linear octrees (for more compact representation); here it is used in tree-based representations to facilitate a simpler and more efficient query for point location, region location and neighbor finding

Representation

Point Location

Region Location (1)

Region Location (2)

Neighbor Search