# Octree algorithms

All coordinates stored in a Coordinate3 node will be stored into an octree with adaptive depth. As the name implies, each node can have a maximum of eight successors. The nodes in this tree are representing cubic fractions of space. An intermediate node divides his cube into eight subcubes with the same size by halving the sides. This means the (max 8) successors of the intermediate node are representing subcubes of the cube of this node. The cube parameters are not stored explicit in the nodes, they are definitly defined by the parameters of the superior cube and the index of the successor pointer to this cube. A cube defined by a leaf node contains exactly one coordinate. The insert algorithm creates automatically intermediate nodes if two coordinates would fall into the same cube.

Each node has an array of pointers to it's successors. As shown in the picture above an intermediate node divides his cube into eight subcubes. A subnode of this node with index i represents a subcube with this index as shown in the left half of the picture. Each leaf node contains exactly one coordinate. So if two coordinates would fall into the same cube, this cube must be divided into subcubes using an intermediate node. In the example in the picture above such an intermediate is shown. The node has two subnodes (in this case leaf nodes) defining two subcubes 0 and 3 which are containing a coordinate.

## Inserting Coordinates into an Octree

Before any coordinate can be inserted into an octree, the bounds of all coordinates which are intended to be inserted must be known. These bounds specify the cube represented by the root-node. In the example below these bounds are the intervals [0-8], [0-8], [0-8] for x, y and z.

The insert algorithm is realized by a recursive function.
Beginning with the root of the tree the function walks through the tree.
While the current node is an intermediate node the function calculates the subcubes and finds out in which subcube the new coordinate is inside. This determines the right successor for searching again. This is made until a leaf node is reached or the pointer to the successor is NULL.

Then there are three cases:

• case 1: the current node is NULL (successor pointer is NULL)
• This means the algorithm has found a place to insert. The successor pointer will be set to the new node. An example for this case you can see in the picture above.

• case 2: a leaf node is reached containing a coordinate equal to the coordinate to be inserted
• This means an equal coordinate already exists. The new coordinate will not be inserted into the tree. An example for this case you can see in the picture above.

• case 3: a leaf node is reached containing a coordinate different to the coordinate to be inserted
• Two coordinates would fall into the same cube this means the octree is not deep enough. The leaf node will be replaced by a new intermediate node. The old leaf node and the new node will be inserted into the new intermediate node using recursive calls to the function. It can happen that the two coordinates would fall again into the same cube. In this case this algorithm would be applied again.
In the picture above the algorithm reaches the leaf node containing the coordinate (3,1,2). The new coordinate is (3,1,1) so it is different to (3,1,2). The old leaf node will be replaced by a new intermediate node and the nodes (3,1,1) and (3,1,2) will be inserted into the new intermediate node.

## Getting the Representative of Coordinates

For generating LODs it is neccessary to select representatives of clusters of coordinates. The program uses octree quantization this means the leaves of the tree will be combined into parent nodes. Each node has an pointer (called represent) to it's parent node. But if anyone wants to get the representative of a specified coordinate it's not sufficient to get simply the node where the pointer represent points to. This is because within a LOD the parent node can also be combined with other nodes into another parent node. If you want to known the representative in LOD x of a coordinate you must follow the represent pointers until the lod number of the node is greater than x (or the lod number is -1 - this means this lod is not generated yet).

Consider you want to know the representative in LOD 1 of the coordinate B of LOD 0.

In this case you must follow the represent pointer to D and than to G. At G you have to stop because the lod number of H is 2. The representative in LOD 1 of the coordinate B of LOD 0 is G. The representative in LOD 1 of A, C, E, F is also G.

Sometimes it is neccessary to known which coordinate in LOD y was selected as the representative. For this reason a selected pointer points from each parent node to the selected subnode. In this case you must follow the selected pointer until the lod number of the node is lesser than y or there no more subnodes. In the example above the selected coordinate in LOD 0 of the coordinate G is C.