Octree< T, AS > Class Template Reference

Generic octree template. More...

List of all members.

Public Member Functions

 Octree (int size, const T &emptyValue=T(0))
 Octree (const Octree< T, AS > &o)
 ~Octree ()
int size () const
const T & emptyValue () const
unsigned long bytes () const
int nodes () const
int nodesAtSize (int size) const
void setEmptyValue (const T &emptyValue)
void swap (Octree< T, AS > &o)
Octree< T, AS > & operator= (Octree< T, AS > o)
T & operator() (int x, int y, int z)
const T & operator() (int x, int y, int z) const
const T & at (int x, int y, int z) const
void set (int x, int y, int z, const T &value)
void erase (int x, int y, int z)
Array2D< T > zSlice (int z) const
void writeBinary (std::ostream &out) const
void readBinary (std::istream &in)

Static Public Member Functions

unsigned long branchBytes ()
unsigned long aggregateBytes ()
unsigned long leafBytes ()

Protected Member Functions

Node *& root ()
const Node * root () const

Static Protected Member Functions

void deleteNode (Node **node)

Detailed Description

template<typename T, int AS = 1>
class Octree< T, AS >

Author:
Simon Perreault <nomis80@nomis80.org>
Date:
April 2007
This class template represents an octree, often used for manipulating 3-D scattered data efficiently. The type of the contained data is supplied as a template parameter.

Parameters:
T Type of the contained data. Requirements on type: must be copyable and default-constructible.
AS Short for "aggregate size." As an optimization, leaves can be aggregated so that the relative size of pointers is diminished. This is 1 by default, but should be set higher when the size of T is small. Must be a power of two.

Constructor & Destructor Documentation

template<typename T, int AS>
Octree< T, AS >::Octree (  int  size,
const T &  emptyValue = T(0)
) 
 

Parameters:
size Size of octree, in nodes. Should be a power of two. For example, an octree with size = 256 will represent a cube divided into 256x256x256 nodes. Must be a power of two.
emptyValue This is the value that will be returned when accessing regions of the 3-D volume where no node has been allocated. In other words, instead of following a null node pointer, this value is returned. Since the octree root is initially a null pointer, the whole volume is initialized to this value.

template<typename T, int AS>
Octree< T, AS >::Octree (  const Octree< T, AS > &  o  ) 
 

Performs a deep copy of an octree. All branch pointers will be followed recursively and new nodes will be allocated.

Parameters:
o Octree to be copied.

template<typename T, int AS>
Octree< T, AS >::~Octree (   ) 
 

Recursively deletes all nodes by following branch pointers.

Member Function Documentation

template<typename T, int AS>
unsigned long Octree< T, AS >::aggregateBytes (   )  [static]
 

Returns:
Number of bytes an aggregate node occupies.

template<typename T, int AS>
const T & Octree< T, AS >::at (  int  x,
int  y,
int  z
)  const
 

Returns:
Value at index (x,y,z). If no node exists at this index, the value returned by emptyValue() is returned.
Remarks:
Memory access is faster when x varies the quickest, followed by y and then by z. Therefore you should write nested loops in this order for faster access:
 for ( int z = 0; z < ...; ++z ) {
     for ( int y = 0; y < ...; ++y ) {
         for ( int x = 0; x < ...; ++x ) {
             ... = octree.at(x,y,z);
         }
     }
 }

However, zSlice() provides an even faster way.

template<typename T, int AS>
unsigned long Octree< T, AS >::branchBytes (   )  [static]
 

Returns:
Number of bytes a branch node occupies.

template<typename T, int AS>
unsigned long Octree< T, AS >::bytes (   )  const
 

Returns:
Total number of bytes the octree occupies.
Remarks:
Memory fragmentation may make the actual memory usage significantly higher.

template<typename T, int AS>
void Octree< T, AS >::deleteNode (  Node **  node  )  [static, protected]
 

Deletes a node polymorphically. If the node is a branch node, it will delete all its subtree recursively.

template<typename T, int AS>
const T & Octree< T, AS >::emptyValue (   )  const
 

Returns:
Value of empty nodes, as specified in the constructor.
See also:
setEmptyValue()

template<typename T, int AS>
void Octree< T, AS >::erase (  int  x,
int  y,
int  z
) 
 

Erases the node at index (x,y,z). After the call, at(x,y,z) will return the value returned by emptyValue().

This function will free as much memory as possible. For example, when erasing the single child of a branch node, the branch node itself will be erased and replaced by a null pointer in its parent. This will percolate to the top of the tree if necessary.

template<typename T, int AS>
unsigned long Octree< T, AS >::leafBytes (   )  [static]
 

Returns:
Number of bytes a leaf node occupies.

template<typename T, int AS>
int Octree< T, AS >::nodes (   )  const
 

Returns:
Total number of nodes in the octree.

template<typename T, int AS>
int Octree< T, AS >::nodesAtSize (  int  size  )  const
 

Returns:
Number of nodes of at size size. For example, the root (if allocated) is the single node of size 1. At size n there may be a maximum of 2n nodes.
For sizes lower than the aggregate size, this function will always return zero.

template<typename T, int AS>
const T & Octree< T, AS >::operator() (  int  x,
int  y,
int  z
)  const
 

Synonym of at().

template<typename T, int AS>
T & Octree< T, AS >::operator() (  int  x,
int  y,
int  z
) 
 

Returns:
Reference to value at index (x,y,z). If no node exists at this index, a new one is created (along with the necessary ancestry), initialized to the value returned by emptyValue(), and returned.
Remarks:
Be careful when calling this function. If you do not want to inadvertently create new nodes, use the at() function.
See also:
at()

template<typename T, int AS>
Octree< T, AS > & Octree< T, AS >::operator= (  Octree< T, AS >  o  ) 
 

Assigns to this octree the contents of octree o.

template<typename T, int AS>
void Octree< T, AS >::readBinary (  std::istream &  in  ) 
 

Reads the octree from in. It must previously have been written using writeBinary().

template<typename T, int AS>
const Octree< T, AS >::Node * Octree< T, AS >::root (   )  const [protected]
 

Const version of above.

template<typename T, int AS>
Octree< T, AS >::Node *& Octree< T, AS >::root (   )  [protected]
 

Returns:
Pointer to octree's root node.

template<typename T, int AS>
void Octree< T, AS >::set (  int  x,
int  y,
int  z,
const T &  value
) 
 

Sets the value of the node at (x, y, z) to value. If value is the empty value, the node is erased. Otherwise, the node is created if it did not already exist and its value is set to value.

template<typename T, int AS>
void Octree< T, AS >::setEmptyValue (  const T &  emptyValue  ) 
 

Sets the value of empty nodes to emptyValue.

See also:
setEmptyValue()

template<typename T, int AS>
int Octree< T, AS >::size (   )  const
 

Returns:
Size of octree, in nodes, as specified in the constructor.

template<typename T, int AS>
void Octree< T, AS >::swap (  Octree< T, AS > &  o  ) 
 

Swaps the octree's contents with another's. This is a cheap operation as only the root pointers are swapped, not the whole structure.

template<typename T, int AS>
void Octree< T, AS >::writeBinary (  std::ostream &  out  )  const
 

Writes the octree in binary form to the output stream out. This should be fast, but note that the type T will be written as it appears in memory. That is, if it is a complex type containing pointers, the pointer addresses will be written instead of the data pointed at. For complex types, you should roll your own function.

template<typename T, int AS>
Array2D< T > Octree< T, AS >::zSlice (  int  z  )  const
 

Returns:
A slice of the octree, perpendicular to the Z axis. The content of all nodes for which the Z index is z will be copied into the returned array. If no node exists for a given index, the value returned by emptyValue() will be written instead.
Remarks:
This method ought to be relatively fast as long the the time required to copy values does not dwarf the time for indexing into the octree (this should be the case for built-in C++ types such as int and double). As a result, using this function is an easy way to accelerate the infamous three-level nested loops. For example:
 for ( int z = 0; z < ...; ++z ) {
     tmp = octree.zSlice(z);
     for ( int y = 0; y < ...; ++y ) {
         for ( int x = 0; x < ...; ++x ) {
             ... = tmp(y,x);
         }
     }
 }