10 replies to this topic

[Juliean]

Hello,

 

I've implemented a basic Octree, which should for now only store primitive collision shapes like boxes and spheres to raypick for my level editor. For now I've two methods to stop child creation:

 

- Eighter if the node only contains one children

- or if it goes beyond a certain depth.

 

Works pretty well, except for one corner case. Consider this picture (its a quad-tree, but since octree and quadtrees are conceptually similar its easier for me to draw):

 

 

See how the green and blue rectangle take up nearly the same space. Obviously now none of the above condition is triggered, so the lower left tree-child gets subdevided (I only marked this one, but same would applie to the other too). Now the red marked child is where things get really ugly. Since each of those childs would contain both rectangles, they would subdevide further and further and so on until the maximum depth is reached.

 

This doesn't make any sense, from a performance viewpoint. Since each of those children contain exactly the same bounding volumes, they shouldn't exist. It should look like this:

 

 

The middle child as well as the two yellow marked childs, since all containing the same two bounding volumes, don't get subdevided further - I subdevided those where it would make sense.

 

Now, my question: what is the common approch for that case? It wasn't talked about in any tutorial about oct/quadtrees I've read. The only way I can think about is to first create all eight child-nodes, and then check if they contain exactly the same volumes (or the data they are connected too). But since this is a performance critical task, I wouldn't want to do this if there is a way around it. First of all with this approach I'd have to first create all eight children, then check their content (consider if more then two shapes overlap that way), then destroy them - on top of that I'd need to give away the convinient recursive nature of the octree, sinse I'd have to split the node creation and node subdivision in two methods, in order for the nodes not to subdevide until max depth before I can destroy them.

 

Is there any fast algorythm for this problem?

[sgt_barnes]

Wouldn't it make sense in that case to only consider the presence of bounding volume edges (line segments for the quad tree, or faces for the octree) for subdivision? You would then get nicely subdiveded cubes around the edges, and not within the volume, I think...

 

For picking, it might even be enough if you consider the faces of the bounding volumes, but this depends on the exact usage scenario.

[Juliean]

Hm, you are right, this would indeed make sense. I think I could even use the faces for picking, but again, from a performance viewport, what would make more sense? Having one AABB or six cube faces for raycasting? And do you have any link for non-oriented bounding box vs. cube face collision detection?

[sgt_barnes]

Octrees are pretty efficient, so I don't think that the performance hit of face picking vs. volume picking would be noticeable. And considered you should easily be able to search through hundreds of faces in under 5ms, that should be o.k. for picking objects in a level editor.

 

Note that you can discard lots of faces early, by rejecting everything with a normal pointed away from the camera. Then, project every vertex of all the remaining faces into screen space and pick in 2D. If you sort the hit list for distance to camera, you can even exit early as soon as one of the faces hits.

 

As for the links: Sorry, I don't have any...

[Juliean]

So you would suggest me to do the following:

 

- Cast a view ray against the octree

- For every leaf the ray hits, store the faces in a list/array , if it doesn't point away from it

- Sort the list for distance to camera

- Project the vertices to screen space

- check if the mouse points over any of those faces

 

Correct? I thought more about testing the faces against the view ray in 3d space, but this approach appears much better to me... in case I got it right.

[kauna]

There are several different logic for deciding when to subdivide or not and in which node you insert the object.

 

You could for example choose the node by the midpoint of the axis aligned bound box of the primitive / mesh. This way each object is located only in one node.

Also you could have a rule that the nodes bound must be bigger than the primitives bound. This results that bigger objects stay at top of the tree and smaller objects at the bottom. Typically this isn't a problem. Only challenge with this approach is that it requires "loose bounds" for each node. Ie. each nodes loose bound must contain all the objects inside it + the child nodes loose bounds.

 

Cheers!

[sgt_barnes]

@The King2:

 

Yeah, that's exactly what I meant.

Try it, and tell us about the results! 

 

@kauna:

 

If I understand you correctly, you suggest some kind of "overlapping" bounding volumes, ordered in a strict hierarchy of their own?

[kauna]

Yes, the each node has a strict bound and a loose bound that may overlap the bound of a neighbour. Each time you insert an object, you'll need to recalculate the loose bound (ie. the strict bound + the bounds of all objects inside the node) and then update the parent nodes loose bounds too.

 

The loose bounds are part of the octree hierarchy, nothing strange there. They are required because by the definition in this case, each object may stay only inside one node and the nodes bound must contain all the objects.

 

For picking or frustum culling, you'll be using the loose bound.

 

Cheers!

[Yrjö P.]

I have not used octrees, but bounding volume hierarchies, which do not suffer from this sort of problem.

Does it actually save any performance when you allow the octree to divide into smaller nodes than the size of the primitives (boxes) you are storing? It would seem like you then have to re-test the same primitive as a ray travels through nodes that contain some of the primitive, whereas not dividing would lead to the primitive tested just once. In your example scenario we'd certainly want to avoid even the first division and just make one leaf with two boxes.

[Juliean]

Does it actually save any performance when you allow the octree to divide into smaller nodes than the size of the primitives (boxes) you are storing? It would seem like you then have to re-test the same primitive as a ray travels through nodes that contain some of the primitive, whereas not dividing would lead to the primitive tested just once. In your example scenario we'd certainly want to avoid even the first division and just make one leaf with two boxes.

 

Well I think you are right that it does not save that much performance if you let the tree devide further when inserting bounding volumes that are larger than the actual octree boxes. This is true as long as you use non-oriented (don't know how else to call them, square boxes without rotation) boxes, but just think about what happens if the boxes become AABBs, with different sizes for all axis. Or if I wanted to insert spheres, faces, and so on too... how would I determine if I should further devide or not? Thats the real problem I have.

 

I think the face-approach will do much, but there still is room to improvement. But I think I should be able to do so while developing my engine. I got everything working, maybe you have got some suggestions how I could improve that code?

 

 

#pragma once
#include "Node.h"
#include <algorithm>

template<typename T>
class Octree
{
public:
    Octree(float size): m_node(BoundingBox(0.0f, 0.0f, 0.0f, size), NULL) {};
    ~Octree(void) {
    };

    void InsertNode(BoundingVolume& volume, T& data){
        m_node.InsertNode(volume, data);
    };

    void Intersect(const Ray& ray, std::map<BoundingVolume*, T>& mData)
    {
        //intersection with parent box
        m_node.Intersect(ray, mData);
    };

private:

    Node<T> m_node;
    
};
 

 

#pragma once
#include <map>
#include "BoundingVolume.h"

template<typename T>
class Node
{
	typedef std::map<BoundingVolume*, T> dataMap;

	static const int MAX_DEPTH = 3;

public:

	Node(const BoundingBox& box, int depth) : m_box(box), m_depth(depth), m_pNodes(NULL) {};
	virtual ~Node(void) {
		if(m_pNodes)
		{
			//free memory
			for(int i = 0; i<8; i++)
			{
				delete m_pNodes[i];
			}
			delete[] m_pNodes;
			m_pNodes = NULL;
		}
	};

	void InsertNode(BoundingVolume& volume, T data){

		//check collision with volume
		if(!m_box.IsInside(&volume))
			return;

		//insert data if max depth was reached
		//todo: improve condition for data insertion
		if(m_depth >= MAX_DEPTH)
		{
			m_mData[&volume] = data;
			return;
		}

		if(!m_pNodes)
		{
			//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(int i = 0; i<8; i++)
			{
				m_pNodes[i] = new Node<T>(GetOct(octBox, i, halfsize*2), m_depth+1);
				//recursively insert data
				m_pNodes[i]->InsertNode(volume, data);
			}
		}
		else 
		{
			//insert into nodes
			for(int i = 0; i<8; i++)
			{
				m_pNodes[i]->InsertNode(volume, data);
			}
		}
	}

	void Intersect(const Ray& ray, dataMap& mData)
	{
		bool bIntersect = m_box.Intersect(ray);

		//skip if no intersection with box
		if(!bIntersect)
			return;

		if(!m_pNodes)
		{
			//store data if node has any
			if(m_mData.size() != 0)
			{
				mData.insert(m_mData.begin(), m_mData.end());
			}
		}
		else
		{
			//test for child node intersection
			for(int i = 0; i<8; i++)
			{
				m_pNodes[i]->Intersect(ray, mData);
			}
		}
	}

private:

	//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.y += size;
			break;
		case 3:
			targetBox.m_vCenter.z += size;
			break;
		case 4:
			targetBox.m_vCenter.y -= size;
			break;
		case 5:
			targetBox.m_vCenter.x -= size;
			break;
		case 6:
			targetBox.m_vCenter.y += size;
			break;
		case 7:
			targetBox.m_vCenter.z -= size;
			break;
		}

		return targetBox;

	}

	int m_depth;

	BoundingBox m_box;
	dataMap m_mData;
	Node** m_pNodes;

};

#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) {};

	D3DXVECTOR3 m_vOrigin, m_vDirection;
};

class BoundingBox;
class BoundingSphere;
class BoundingVolume
{
public:
	virtual bool IsInside(const BoundingVolume* pVolume) const = 0;
	
	virtual bool WithBox(const BoundingBox& box) const = 0;

	virtual bool WithSphere(const BoundingSphere& sphere) const = 0;

	virtual bool Intersect(const Ray& ray) const = 0;
};

class BoundingBox : public BoundingVolume
{
public:

	//todo: allow for non-cubic bounding boxes
	BoundingBox(void) : m_vCenter(0.0f, 0.0f, 0.0f), m_size(0.0f) {};
	BoundingBox(float x, float y, float z, float size) : m_vCenter(x, y, z), m_size(size) {};
	BoundingBox(const D3DXVECTOR3& vCenter, float size) : m_vCenter(vCenter), m_size(size) {};

	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 WithSphere(const BoundingSphere& sphere) const
	{
		return true;
	}

	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
		dirfrac.x = 1.0f / ray.m_vDirection.x;
		dirfrac.y = 1.0f / ray.m_vDirection.y;
		dirfrac.z = 1.0f / ray.m_vDirection.z;
		// 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)*dirfrac.x;
		float t2 = (vMax.x - ray.m_vOrigin.x)*dirfrac.x;
		float t3 = (vMin.y - ray.m_vOrigin.y)*dirfrac.y;
		float t4 = (vMax.y - ray.m_vOrigin.y)*dirfrac.y;
		float t5 = (vMin.z - ray.m_vOrigin.z)*dirfrac.z;
		float t6 = (vMax.z - ray.m_vOrigin.z)*dirfrac.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;
	}


	D3DXVECTOR3 m_vCenter;
	float m_size;
};

...

Usage like this:

 

 

    //insert entities to octree
    EntityManager::entityVector* pEntities = m_pEntityManager->EntitiesWithComponents<Position, Bounding>();
    if(pEntities == NULL)
        return;

    for(auto entity : *pEntities)
    {
        BoundingBox* pBox = &entity->GetComponent<Bounding>()->m_box;
        m_octree.InsertNode(*pBox, entity);
    }

...

    //pick object
    std::map<BoundingVolume*, Entity*> m_mEntities;
    m_octree.Intersect(mouseRay, m_mEntities);

    for(auto data: m_mEntities)
    {
        if(data.first->Intersect(mouseRay))
            SigSelectGameObject(data.second);
    }
 

 

Any suggestions would be highly appreciated!

Edited by The King2, 23 March 2013 - 11:33 AM.

[Juliean]

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?)

Attached Thumbnails

•