CloudCompare octree

The octree structure is used throughout CloudCompare: in particular all processing methods involving spatial considerations use it. Note that the particular structure used in CloudCompare is very efficient for nearest neighbor extraction but not for display purposes (L.O.D. approaches, etc.).

Structure

An octree corresponds to the recursive partition of a cubical volume of space. From an initial box, octree cells are formed by dividing cubes into 8 equivalent sub-cubes. By default, the octree subdivision is initiated from the square bounding box of a cloud, but it can also be computed from an arbitrary cube is space (to optimize comparison algorithms such as distance computation for example).

• Recursive subdivision principle
• 

  Depth: 1

• 

  Depth: 3

• 

  Depth: 6

The octree structure used in CloudCompare (DgmOctree) is not as properly speaking a real 'tree'. It takes the form of a list of numerical values (one per point) that code the absolute position of a point for all level of subdivision. It is particularly suited for spatial indexing. Two points lying in the same cell at a given level of subdivision have the same (partial) associated code. The octree size in memory is also constant.

The code is formed by concatenating sets of 3 bits (0...7) which code the relative position of the cell for each level of subdivision. The cell at the first level of subdivision corresponds to the most significant bits, and the deepest level corresponds to the less significant bits. Codes are then sorted to allow fast binary search as well as spatial sweep of the cloud (adjacent cells are next to each other in the sorted list).

The maximum octree depth in the standard CloudCompare version is 10. In this version codes are coded on 32 bits, and are associated to a 32 bits index value (i.e. the octree weights 128 bits per point = 8 bytes --> 8 Mb / M. points). One can compile CloudCompare to use 64 bits codes, which allows to go up to 21 levels of subdivision (but memory consumption is 50% higher).

Computing the octree

You can force the computation of the octree on any point cloud in CloudCompare (to display it for example - see below): Edit > Octree > Compute.

Displaying the octree

Once computed (either manually - see above - or after a method has requested it), one can display it.

The octree 'object' (in database tree) must be activated and set to 'visible'. Three types of visualization are available:

• wire (default)
• points (one point per cell)
• plain cubes