Octree Encoding- used in Computational Methods

Description of Octrees, Quadtrees, along with examples and representation with applications in various industries
This will be great start for learning Octree and Quadtree.

1. Presentation on
Octree Encoding
Presented By:
Aditya Deshpande
Guided By:
Prof. G. D. Korwar
VISHWAKARMA INSTITUTE OF TECHNOLOGY, PUNE

2. Introduction
Octreesarehierarchicaltreestructuresthatdescribeeachregionof3D
spaceasnodes.Whencomparedwiththebasicvoxelrepresentation,
octreesreducestoragerequirementsfor3Dobjects.Italsoprovidesa
convenientrepresentationforstoringinformationaboutobject
interiors.Octreeencodingprocedureisanextensionofthequadtree
encodingof2Dimages

3. •Anoctreeisatreedatastructureinwhicheachinternalnodehas
exactlyeightchildren.
•Octreesaremostoftenusedtopartitionathreedimensional
spacebyrecursivelysubdividingitintoeightoctants.
•Octreesarethethree-dimensionalanalogueofquadtrees.
•Thenameisformedfromoct+tree,butnotethatitisnormally
written"octree"withonlyone"t".
•Octreesareoftenusedin3Dgraphicsand3Dgameengines.
•Theuseofoctreesfor3Dcomputergraphicswaspioneeredby
DonaldMeagheratRensselaerPolytechnicInstitute,ina1980
Octrees -Intro

4. Octrees are hierarchical tree structures
used to represent solid objects
Octrees are particularly useful in
applications that require cross sectional
views
for example medical applications
Octrees are typically used when the
interior of objects is important
Octrees

5. •Octrees are based on a two-dimensional representation scheme
called quadtreeencoding
•Quadtree encoding divides a square region of space into four equal
areas until homogeneous regionsare found
•These regions can then be arranged in a tree
Octrees & Quadtrees

6. QuadtreeExamples 1

7. QuadtreeExamples 2

8. •Quadtree encodings provide considerable savings in storage when
large colour areas exist in a region of space
•An octree takes the same approach as quadtrees, but divides a cube
region of 3D space into octants
•Each region within an octree is referred to as a volume elementor
voxel
•Division is continued until homogeneous regions are discovered
Octree

9. Octree (cont…)

10. •In 3 dimensions regions can be considered to be homogeneous in
terms of colour, material type, density or any other physical
characteristics
•Voxels also have the unique possibility of being empty
Octree (cont…)

11. Octree Examples

14. Octree Representation of 3D Data
(a) Example 3-dimensional object; (b) its octree block decomposition; and (c) its tree representation.

15. 1.3D computer graphics
2.Spatial indexing
3.Nearest neighbour search
4.Efficientcollision detectionin three dimensions
5.View frustum culling
6.Fast Multipole Method
7.Unstructured grid
8.Finite element analysis
9.Sparse voxel octree
10.State estimation
11.Set estimation
Applications