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?

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.

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?

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...

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.

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!

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

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!

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