Hello,

the past few days I've been improving my octree implementation. I've read about "loose octrees" and really got hooked by the concept, so I rebuilt my octree using this concept. It works like a charm, so I thought I'd share my code with you in case someone wants to use those as well. Plus, I got two more questions, but I'll post them at the end. Here is the code:

BoundingVolume.h

#pragma once
//todo: implement own vector class
#include <d3dx9.h>
class Ray
{
public:
Ray(const D3DXVECTOR3& vOrigin, const D3DXVECTOR3 vDirection): m_vOrigin(vOrigin), m_vDirection(vDirection)
{
m_vDirFrac.x = 1.0f / m_vDirection.x;
m_vDirFrac.y = 1.0f / m_vDirection.y;
m_vDirFrac.z = 1.0f / m_vDirection.z;
};
D3DXVECTOR3 m_vOrigin, m_vDirection;
D3DXVECTOR3 m_vDirFrac;
};
class BoundingBox;
class BoundingVolume
{
public:
virtual bool IsInside(const BoundingVolume* pVolume) const = 0;
virtual bool WithBox(const BoundingBox& box) const = 0;
virtual bool Intersect(const Ray& ray) const = 0;
virtual float MaxExtents(void) const = 0;
D3DXVECTOR3 m_vCenter, m_vOrigin;
};
class BoundingBox : public BoundingVolume
{
public:
//todo: allow for non-cubic bounding boxes
BoundingBox(void) : m_size(0.0f) { m_vCenter = D3DXVECTOR3(0.0f, 0.0f, 0.0f); m_vOrigin = m_vCenter; }
BoundingBox(float x, float y, float z, float size) : m_size(size) { m_vCenter = D3DXVECTOR3(x, y, z); m_vOrigin = m_vCenter; }
BoundingBox(const D3DXVECTOR3& vCenter, float size) : m_size(size) { m_vCenter = vCenter; m_vOrigin = m_vCenter;}
bool IsInside(const BoundingVolume* pVolume) const
{
return pVolume->WithBox(*this);
}
bool WithBox(const BoundingBox& box) const
{
D3DXVECTOR3 vDistance = m_vCenter;
vDistance -= box.m_vCenter;
float maxDistance = m_size + box.m_size;
return (abs(vDistance.x) <= maxDistance && abs(vDistance.y) <= maxDistance && abs(vDistance.z) <= maxDistance);
}
bool Intersect(const Ray& ray) const
{
D3DXVECTOR3 dirfrac;
D3DXVECTOR3 vMin(m_vCenter.x - m_size, m_vCenter.y - m_size, m_vCenter.z - m_size), vMax(m_vCenter.x + m_size, m_vCenter.y + m_size, m_vCenter.z + m_size);
// r.dir is unit direction vector of ray
// lb is the corner of AABB with minimal coordinates - left bottom, rt is maximal corner
// ray.m_vOrigin is origin of ray
float t1 = (vMin.x - ray.m_vOrigin.x)*ray.m_vDirFrac.x;
float t2 = (vMax.x - ray.m_vOrigin.x)*ray.m_vDirFrac.x;
float t3 = (vMin.y - ray.m_vOrigin.y)*ray.m_vDirFrac.y;
float t4 = (vMax.y - ray.m_vOrigin.y)*ray.m_vDirFrac.y;
float t5 = (vMin.z - ray.m_vOrigin.z)*ray.m_vDirFrac.z;
float t6 = (vMax.z - ray.m_vOrigin.z)*ray.m_vDirFrac.z;
float tmin = max(max(min(t1, t2), min(t3, t4)), min(t5, t6));
float tmax = min(min(max(t1, t2), max(t3, t4)), max(t5, t6));
// if tmax < 0, ray (line) is intersecting AABB, but whole AABB is behing us
if (tmax < 0)
{
//t = tmax;
return false;
}
// if tmin > tmax, ray doesn't intersect AABB
if (tmin > tmax)
{
//t = tmax;
return false;
}
//t = tmin;
return true;
}
float MaxExtents(void) const
{
return D3DXVec3Length(&D3DXVECTOR3(m_size, m_size, m_size));
}
float m_size;
};

Octree.h

#pragma once
#include "Node.h"
#include <algorithm>
template<typename T>
class Octree
{
typedef std::map<BoundingVolume*, Node<T>*> nodeMap;
public:
Octree(float size): m_size(size), m_node(BoundingBox(0.0f, 0.0f, 0.0f, m_size), 0, NULL) {};
~Octree(void) {
};
void InsertNode(BoundingVolume& volume, T data){
//acccess volume and octree max size
float volumeSize = volume.MaxExtents(), treeSize = m_size;
int depth = 0;
//until node box is smaller than the volume
while(treeSize > volumeSize)
{
treeSize /= 2;
depth += 1;
//break on max depth
if(depth > Node<T>::MAX_DEPTH)
break;
}
//adjust depth and size
depth -= 1;
treeSize *= 2;
//find node
Node<T>* pNode = FindFittingNode(volume, treeSize, depth);
//insert data into node
pNode->InsertData(volume, data);
//link volume and node for update
m_mNodeData[&volume] = pNode;
};
void RemoveData(BoundingVolume& volume)
{
m_mNodeData[&volume]->RemoveData(volume);
m_mNodeData.erase(&volume);
}
void UpdateData(BoundingVolume& volume, T data)
{
m_mNodeData[&volume]->RemoveData(volume);
InsertNode(volume, data);
}
void Intersect(const Ray& ray, std::map<BoundingVolume*, T>& mData)
{
//intersection with parent box
m_node.Intersect(ray, mData);
}
const Node<T>& GetRoot(void) const
{
return m_node;
}
private:
Node<T>* FindFittingNode(const BoundingVolume& volume, float treeSize, unsigned int depth)
{
D3DXVECTOR3 vCenter(volume.m_vCenter.x + m_size, volume.m_vCenter.y + m_size, volume.m_vCenter.z + m_size);
//calculate absolut position
unsigned int x = (unsigned int)(vCenter.x / treeSize);
unsigned int y = (unsigned int)(vCenter.y / treeSize);
unsigned int z = (unsigned int)(vCenter.z / treeSize);
Node<T>* pNode = &m_node;
//iteratively choose next child node
for(unsigned int i = 0; i != depth; i++)
{
//pick node if it isn't split
if(!pNode->IsSplit())
break;
unsigned int currentDepth = depth - i;
//calculate position at current depth
//todo: check for invalid positions
unsigned int currentDepthX = x >> currentDepth;
unsigned int currentDepthY = y >> currentDepth;
unsigned int currentDepthZ = z >> currentDepth;
//calculate childs index
unsigned int childIndex = currentDepthX + (currentDepthZ << 1) + (currentDepthY << 2);
//get new node
pNode = pNode->Children()[childIndex];
//modify absolut positions to new child
x -= currentDepthX << currentDepth;
y -= currentDepthY << currentDepth;
z -= currentDepthZ << currentDepth;
}
return pNode;
}
float m_size;
Node<T> m_node;
nodeMap m_mNodeData;
};

Node.h

#pragma once
#include <map>
#include "BoundingVolume.h"
template<typename T>
class Node
{
typedef std::map<BoundingVolume*, T> dataMap;
public:
static const int MAX_DEPTH = 5;
Node(const BoundingBox& box, int depth, Node* pParent) : m_box(box), m_looseBox(box.m_vCenter, box.m_size), m_depth(depth), m_pParent(pParent), m_pNodes(NULL), m_bSplit(false), m_numActiveNodes(0)
{
if(m_depth < MAX_DEPTH)
CreateChildren();
}
virtual ~Node(void) {
if(m_pNodes)
{
//free memory
for(unsigned int i = 0; i<8; i++)
{
delete m_pNodes[i];
}
delete[] m_pNodes;
m_pNodes = NULL;
}
}
void InsertData(BoundingVolume& volume, T data)
{
m_mData[&volume] = data;
//check if node needs to be split
if(m_mData.size() > 1 && m_depth < MAX_DEPTH)
{
//set status to split
m_bSplit = true;
//todo: make existing data be checked for needing to get inserted deeper once a node is split
}
//check if node has become active
else if(m_mData.size() == 1)
{
//expand border
m_looseBox.m_size = m_box.m_size*2;
//tell parent node is active
if(m_pParent != NULL)
m_pParent->AddActiveNode();
}
}
void RemoveData(BoundingVolume& volume)
{
m_mData.erase(m_mData.find(&volume));
CheckNodeStatus();
}
void Intersect(const Ray& ray, dataMap& mData)
{
bool bIntersect = m_looseBox.Intersect(ray);
//skip if no intersection with box
if(!bIntersect)
return;
//store data if node has any
if(m_mData.size() != 0)
{
mData.insert(m_mData.begin(), m_mData.end());
}
if(IsSplit())
{
//test for child node intersection
for(unsigned int i = 0; i<8; i++)
{
m_pNodes[i]->Intersect(ray, mData);
}
}
}
bool IsSplit(void) const
{
return m_bSplit;
}
Node** Children(void) const
{
return m_pNodes;
}
const BoundingBox& GetBox(void) const
{
return m_box;
}
private:
void CreateChildren(void)
{
//create child Node array
m_pNodes = new Node*[8];
//child bounding box size
float halfsize = m_box.m_size / 2;
//center of the first new bounding box
D3DXVECTOR3 vNewCenter(m_box.m_vCenter.x - halfsize, m_box.m_vCenter.y - halfsize, m_box.m_vCenter.z - halfsize);
//create first bounding box
BoundingBox octBox(vNewCenter, halfsize);
//create 8 child nodes
for(unsigned int i = 0; i<8; i++)
{
m_pNodes[i] = new Node<T>(GetOct(octBox, i, halfsize*2), m_depth+1, this);
}
}
void AddActiveNode(void)
{
m_numActiveNodes += 1;
}
void RemoveActiveNode(void)
{
m_numActiveNodes -= 1;
CheckNodeStatus();
}
void CheckNodeStatus(void)
{
//check if node still needs to be split
if(m_mData.size() <= 1 && m_numActiveNodes == 0)
{
//check if node still contains any data
if(m_mData.size() == 0)
{
//reset loose borders
m_looseBox.m_size = m_box.m_size;
//tell parent node becomes inactive
if(m_pParent != NULL)
m_pParent->RemoveActiveNode();
}
m_bSplit = false;
}
}
//recursively constructs the num child leaves bounding box
const BoundingBox& GetOct(BoundingBox& targetBox, int num, float size) const
{
switch(num)
{
case 1:
targetBox.m_vCenter.x += size;
break;
case 2:
targetBox.m_vCenter.x -= size;
targetBox.m_vCenter.z += size;
break;
case 3:
targetBox.m_vCenter.x += size;
break;
case 4:
targetBox.m_vCenter.x -= size;
targetBox.m_vCenter.z -= size;
targetBox.m_vCenter.y += size;
break;
case 5:
targetBox.m_vCenter.x += size;
break;
case 6:
targetBox.m_vCenter.x -= size;
targetBox.m_vCenter.z += size;
break;
case 7:
targetBox.m_vCenter.x += size;
break;
}
return targetBox;
}
int m_depth, m_numActiveNodes;
bool m_bSplit;
BoundingBox m_box;
BoundingBox m_looseBox;
Node* m_pParent;
dataMap m_mData;
Node** m_pNodes;
};

Stats look really promising. Insertion of 1.000.000 objects takes 30 ms (i7 X980), with a linear increase/decrease of time (twice the objects takes twice the time). Notice that the function BoundingBox::MaxExtents is not nearly optimized out, "caching" that value decreases insertion time by ~10 ms. Notice also that insertion time is not depending on bounding volume complexity. Any bounding volume that correctly implements the BoundingVolume-interface can be used and will perform equally well. See the attachment for a visualisation of the octree with 1000 randomly placed cubes. The octree currently lacks a proper check for objects that are completely outside of the tree, so you need to check this manually.

Now I'm still concerned on two things which I don't know how to improve (but there is probably lots of space for improvement):

- First of all, the loose borders of the tree. As soon as an object is inserted into a node, the nodes loose border needs to be extented to safely fit the object in. Right now my implementation will simply extent the loose borders to the maximum as soon as one object is inserted and, when there is no object left + no active child node, then the borders are reset to normal size. Size ranges from node_size -> node_size*2, if you are not familiar with loose octrees. My question, is there any better way to calculate the loose borders of a node? Obviously it would be optimal to have the loose borders be as big as the biggest object that is inside the node, and, if there is any child node, at least node_size * 1.5 . But how would you implement that? Only thing I can think about is storing the objects size in a vector for each node, but that would mean I'd have to iterate through the whole vector on removal of any object (which can become quite big, so updating objects could take quite long), so I'm sure there is a better approach?

- Speaking of which, how is updating objects normally handled in an octree? Right now I've got my entities a OctreeComponent, which will check their position, size etc.. for changes that would require to switch a node. If that happens, I remove and insert the object again to the tree. Its not bad from a performance standport, because of the low insertion time, but I'm still not sure if this a good approach. Can someone tell me how this is handled normally? Is it ok to handling object updating outside of the tree or is there some algorythm for having the octree/nodes handling their objects themselfs (without looping over all of them every frame?)