[go: up one dir, main page]
Scribd
Upload
2K views2 pages

Octrees

Octrees are hierarchical tree structures used to represent 3D objects by recursively subdividing 3D space into octants. Each node corresponds to a region of 3D space, with up to 8 child nodes representing the octants. If an octant is homogeneous (all voxels the same type), its type is stored at the node, otherwise it is subdivided further. Octrees extend the 2D quadtree encoding scheme, where a region is subdivided into quadrants and each node stores 4 data elements for the quadrants. Quadtrees and octrees provide data compression by representing homogeneous regions with a single node.

Uploaded by

mail.sushilk8403
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
2K views2 pages

Octrees

Octrees are hierarchical tree structures used to represent 3D objects by recursively subdividing 3D space into octants. Each node corresponds to a region of 3D space, with up to 8 child nodes representing the octants. If an octant is homogeneous (all voxels the same type), its type is stored at the node, otherwise it is subdivided further. Octrees extend the 2D quadtree encoding scheme, where a region is subdivided into quadrants and each node stores 4 data elements for the quadrants. Quadtrees and octrees provide data compression by representing homogeneous regions with a single node.

Uploaded by

mail.sushilk8403
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
You are on page 1/ 2

Octrees

Hierarchical tree structures, called octrees, are used to represent solid objects in some graphics
systems. Medical imaging and other applications that require displays of object cross sections
commonly use octree representations. The tree structure is organized so that each node corresponds to
a region of three-dimensional space.

The octree encoding procedure for a three-dimensional space is an extension of an encoding scheme
for two-dimensional space, called quadtree encoding. Quadtrees are generated by successively
dividing a two-dimensional region (usually a square) into quadrants. Each node in the quadtree has
four data elements, one for each of the quadrants in the region as shown.

Region of a two-dimensional space divided intu numbered


quadrants and the associated quadtree node with four data elements

If all pixels within a quadrant have the same color (a homogeneous quadrant), the corresponding data
element in the node stores that color. In addition, a flag is set in the data element to indicate that the
quadrant is homogeneous. Suppose all pixels in quadrant 2 of fig are found to be red The color code
for red is then placed in data element 2 of the node. Otherwise, the quadrant is said to be
heterogeneous, and that quadrant is itself divided into quadrants The corresponding data element in
the node now flags the quadrant as heterogeneous and stores the pointer to the next node in the
quadtree.
If each quadrant in the original space has a single color specification, the quadtree has only one node.
For a heterogeneous region of space, the successive subdivisions into quadrants continues until all
quadrants are homogeneous.
Fig shows a quadtree representation for a region containing one area with a solid color that is different
from the uniform color specified for all other areas in the region.

Quadtree encodings prowde considerable savings in storage when large color areas exist in a region of
space, since each single-color area can be represented with one node. For an area containing 2'' by 2"
pixels, a quadtree representation contains at most n levels. Each node in the quadtree has at most four
immediate descendants.

An octree encoding scheme divides regions of three-dimensional space (usually cubes) into octants
and stores eight data elements in each node of the tree Individual elements of a three-dimensional
space are called volume elements, or voxels. When all voxels in an octant are of the same type, this
type value is stored in the corresponding data element of the node. Empty regions of space are
represented by voxel type "void." Any heterogeneous octant is subdivided into octants, and the
corresponding data element in the node points to the next node in the octree. Procedures for
generating octrees are similar to those for quadtrees: Voxels in each octant are tested, and octant
subdivisions continue until the region of space contains only homogeneous octants. Each node in the
octree can now have from zero to eight immediate descendants.

Region of a three-dimensional space divided into numbered


octants and the associated octree node with eight data elements

You might also like