logo back up home forward   further reading more topics »

3D Theory - Octtree

An octtree is a data structure which can define a shape in 3 dimensions.

The 3D space is divided into 8 cubes:

Then where more structure is needed, within a cube, it can be further divided into 8 smaller cubes and so on, recursively. This can be represented by a tree where each node has either 8 or no children.

A three dimensional volume could be modelled by dividing the world into small cubes (see voxel), the position of each cube could be represented by 3 Cartesian coordinates (x,y and z) and if each cube were small enough then it could be considered to contain only one type of matter coded in some way. However this would require an enormous array of data to hold a reasonable representation of a scene. This might be an inefficient way to model the world because a large mass of homogenous matter would require just as much data as the very intricate parts of its outer structure. Therefore it might be more efficient to hold this information in a BSP tree or an octtree, then we can have lots of detail in the parts that need it, without wasting data where it is not needed.

Octrees could be used to represent a shape for rendering for example or we might use some other method, such as polygons, for rendering but use octrees for collision detection or hidden object removal.


next:

up:
see also:

metadata block
see also:

 

Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

cover 3d Games:Volume 1: Real-time Rendering - Written around engine 'fly3d'. Includes Bezier + B-spline curves, kinematics, using quaternions to represent rotation, collision detection (not response) so physics needs to be pre-scripted.

Commercial Software Shop

Where I can, I have put links to Amazon for commercial software, not directly related to this site, but related to the subject being discussed, click on the appropriate country flag to get more details of the software or to buy it from them.

cover Adobe Dimensions 3.0 Win

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2012 Martin John Baker - All rights reserved - privacy policy.