Jump to content

  • Log In with Google      Sign In   
  • Create Account

#ActualThe King2

Posted 23 March 2013 - 11:33 AM

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!


#1The King2

Posted 23 March 2013 - 11:26 AM

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;
};

...

 

Any suggestions would be highly appreciated!


PARTNERS