Octree: a tree data structure in which each node has either 0 or exactly 8 children nodes which partition the parent node into equal size cubic volumes. More...

Detailed Description

Octree: a tree data structure in which each node has either 0 or exactly 8 children nodes which partition the parent node into equal size cubic volumes.

This is a spatial hierarchy structure, to accelerate some of the spatial find operations, such as finding the closest object to each other in a scene. The root node is the spatially biggest node, with the size enough to cover the entire scene (e.g. map size). Scene objects are inserted into the octree one by one, by finding an empty node for them based on their position, starting from the root node. If a tree node suitable for the object being inserted doesn't have any object yet, we store the object in that node. If a tree node suitable for the object being inserted already has 1 object, and we have not yet reached the maximum tree depth, we further subdivide that node into 8 children nodes, and reinsert the object already inside the tree, and insert the new object. In case we already reached the maximum tree depth, we do not further subdivide but just insert the new object to the most suitable node, in this case a node can has multiple objects stored in it.

This is just my own simply octree implementation. Note that although the octree divides the space perfectly, the objects being put inside this tree are allowed to overlap multiple tree nodes. Their position decides which tree node they will be put into, overlapping across different nodes is not considered.

There are a lot of example implementations on the internet: A few simple:

Note this is not a Loose Octree implementation, but might become in the future. Info about loose octree:

Definition at line 51 of file PureOctree.h.

#include <PureOctree.h>

Inheritance diagram for PureOctree:

Public Types
enum	NodeType { Parent , LeafEmpty , LeafContainer }
	NodeType tells if the given node has children nodes or Objects. More...

typedef TPureUInt	ChildIndex
	ChildIndex indexes a child node within a vector of children nodes.

Public Member Functions
	PureOctree (const PureVector &pos, TPureFloat size, TPureUInt maxDepthLevel, TPureUInt currentDepthLevel)
	Creates an octree node.

virtual	~PureOctree ()

ChildIndex	calculateIndex (const PureVector &pos) const
	Calculates child node index for the given position in the current node.

virtual PureOctree *	insertObject (const PureObject3D &obj)
	Inserts the given object in the octree.

virtual const PureOctree *	findObject (const PureObject3D &obj) const
	Finds the given object in the octree.

TPureUInt	getDepthLevel () const
	Gets the current depth level of the octree node.

TPureUInt	getMaxDepthLevel () const
	Gets the maximum depth level of the octree node as it was specified in the constructor of the octree.

NodeType	getNodeType () const
	Gets the type of the octree node which depends on if the node has any objects or children nodes.

const PureVector &	getPos () const
	Gets the world-space position of the node as specified in the constructor.

TPureFloat	getSize () const
	Gets the length of the side of the cube represented by this node as it was specified in the constructor.

const std::vector< PureOctree * > &	getChildren () const
	Gets the children nodes of this node.

const PureOctree *	getParent () const
	Gets the parent node of this node.

const std::set< const PureObject3D * > &	getObjects () const
	Gets the stored objects of this node.

Static Public Attributes
static const ChildIndex	BIT_AXIS_Y = 0
	Bit to set to TOP or BOTTOM.

static const ChildIndex	BIT_AXIS_X = 1
	Bit to set to LEFT or RIGHT.

static const ChildIndex	BIT_AXIS_Z = 2
	Bit to set to FRONT or BACK.

static const ChildIndex	TOP = 0
	Child is above or in same as parent's position on Y-axis.

static const ChildIndex	BOTTOM = BIT(PureOctree::BIT_AXIS_Y)
	Child is under parent's position on Y-axis.

static const ChildIndex	LEFT = 0
	Child is left to parent's position on X-axis.

static const ChildIndex	RIGHT = BIT(PureOctree::BIT_AXIS_X)
	Child is right to or in same as parent's position on X-axis.

static const ChildIndex	FRONT = 0
	Child is closer to camera than parent's position on Z-axis.

static const ChildIndex	BACK = BIT(PureOctree::BIT_AXIS_Z)
	Child is farther or same distance from camera than parent's position on Z-axis.

Protected Member Functions
	PureOctree ()

	PureOctree (const PureOctree &)

PureOctree &	operator= (const PureOctree &)

virtual TPureBool	subdivide ()

void	DeleteChildren ()

Protected Attributes
std::vector< PureOctree * >	vChildren

PureOctree *	parent

Private Attributes
PureVector	vPos

TPureFloat	fSize

TPureUInt	nCurrentDepth

TPureUInt	nMaxDepth

NodeType	nodeType

std::set< const PureObject3D * >	vObjects

Member Typedef Documentation

◆ ChildIndex

TPureUInt PureOctree::ChildIndex

ChildIndex indexes a child node within a vector of children nodes.

It is basically a number between 0 and 7, but it is easier to read and write code if we set named bits depending on where the child node is placed on each axis compared to its parent. Front means facing to camera, back means looking away from camera view.

Definition at line 78 of file PureOctree.h.

Member Enumeration Documentation

◆ NodeType

enum PureOctree::NodeType

NodeType tells if the given node has children nodes or Objects.

The default type is LeafEmpty. This changes to LeafContainer after adding 1 object to the node. LeafContainer can later change to Parent after adding further objects to the same node.

Enumerator
Parent	This non-leaf node does not have objects but 8 children nodes that might store objects.
LeafEmpty	This leaf node has neither children nodes nor objects stored inside.
LeafContainer	This leaf node has at least 1 object stored inside.

Definition at line 64 of file PureOctree.h.

Constructor & Destructor Documentation

◆ PureOctree() [1/3]

PureOctree::PureOctree	(	const PureVector &	pos,
		TPureFloat	size,
		TPureUInt	maxDepthLevel,
		TPureUInt	currentDepthLevel )

Creates an octree node.

Initially the type of this node will be LeafEmpty.

Parameters

pos	The world-space position of this node. For global use, you can specify just (0;0;0).
size	The length of the side of the cube represented by this node. Recommend this to be big enough to contain any scene objects.
maxDepthLevel	The maximum node depth level supported by this octree. 0 means there is no depth limit.
currentDepthLevel	The depth level of this specific node being created. For global use, just specify 0 so this will be the root node of the octree.

Definition at line 48 of file PureOctree.cpp.

◆ ~PureOctree()

PureOctree::~PureOctree ( )

virtual

Definition at line 60 of file PureOctree.cpp.

◆ PureOctree() [2/3]

PureOctree::PureOctree ( )

protected

Definition at line 308 of file PureOctree.cpp.

◆ PureOctree() [3/3]

PureOctree::PureOctree ( const PureOctree & )

protected

Definition at line 319 of file PureOctree.cpp.

Member Function Documentation

◆ calculateIndex()

PureOctree::ChildIndex PureOctree::calculateIndex ( const PureVector & pos ) const

Calculates child node index for the given position in the current node.

Calculates child node index for the given world-space position in the current node.

Bounds checking is NOT done, so giving a position which is outside the bounds of this Octree Node will not be detected.

Parameters

pos	The world-space position for which child index should be selected in the current node.

Returns: Calculated child index. If given position is same as Octree Node position, index will be TopRightBack.

Definition at line 73 of file PureOctree.cpp.

◆ DeleteChildren()

void PureOctree::DeleteChildren ( )

protected

Definition at line 356 of file PureOctree.cpp.

◆ findObject()

const PureOctree * PureOctree::findObject ( const PureObject3D & obj ) const

virtual

Finds the given object in the octree.

Note that the search will NOT involve the whole tree. The current position of the given object will be used to select the nodes to be searched in the tree. This means that if the position of the given object has changed since it was put in the tree, the search might fail.

Parameters

obj	The object to be found.

Returns: The octree node containing the object. If the object is not found, PGENULL is returned.

Reimplemented in PureBoundingVolumeHierarchy.

Definition at line 177 of file PureOctree.cpp.

◆ getChildren()

const std::vector< PureOctree * > & PureOctree::getChildren ( ) const

Gets the children nodes of this node.

An octree node has either 0 or exactly 8 children nodes.

Returns: The children nodes of this node.

Definition at line 276 of file PureOctree.cpp.

◆ getDepthLevel()

TPureUInt PureOctree::getDepthLevel ( ) const

Gets the current depth level of the octree node.

Returns: Depth level of the octree node. 0 means this is the root of the octree.

Definition at line 206 of file PureOctree.cpp.

◆ getMaxDepthLevel()

TPureUInt PureOctree::getMaxDepthLevel ( ) const

Gets the maximum depth level of the octree node as it was specified in the constructor of the octree.

This value will be the same for all nodes within the same octree.

Returns: Maximum depth level of the octree node. 0 means there is no depth limit.

Definition at line 217 of file PureOctree.cpp.

◆ getNodeType()

PureOctree::NodeType PureOctree::getNodeType ( ) const

Gets the type of the octree node which depends on if the node has any objects or children nodes.

Returns: The type of the octree node. See explanation of values at PureOctree::NodeType.

Definition at line 227 of file PureOctree.cpp.

◆ getObjects()

const std::set< const PureObject3D * > & PureOctree::getObjects ( ) const

Gets the stored objects of this node.

Returns: The stored objects of this node.

Definition at line 299 of file PureOctree.cpp.

◆ getParent()

const PureOctree * PureOctree::getParent ( ) const

Gets the parent node of this node.

The root node does not have parent.

Returns: The parent node of this node.

Definition at line 288 of file PureOctree.cpp.

◆ getPos()

const PureVector & PureOctree::getPos ( ) const

Gets the world-space position of the node as specified in the constructor.

This value will be the same for all nodes at the same depth level of the same octree. Since children nodes partition the parent node into equal size cubic volumes, the biggest node is the root node. The deeper we go in the tree i.e. the higher the depth level, the smaller the nodes are.

Returns: The position of the node in world-space.

Definition at line 250 of file PureOctree.cpp.

◆ getSize()

TPureFloat PureOctree::getSize ( ) const

Gets the length of the side of the cube represented by this node as it was specified in the constructor.

This value will be the same for all nodes at the same depth level of the same octree. Since children nodes partition the parent node into equal size cubic volumes, the biggest node is the root node. The deeper we go in the tree i.e. the higher the depth level, the smaller the nodes are.

Returns: The length of the side of the cube represented by this node.

Definition at line 264 of file PureOctree.cpp.

◆ insertObject()

PureOctree * PureOctree::insertObject ( const PureObject3D & obj )

virtual

Inserts the given object in the octree.

The tree doesn't make copy of the objects, it just saves pointers to them. Note that if you insert the same object multiple times with same position, it will be still contained only once in the tree, within the same node. If you insert the same object multiple times with differens positions, it might be contained by multiple nodes, which will lead to invalid containments. However, since this Octree implementation is for inserting static objects once, it should not be a problem.

Parameters

obj	The object to be inserted in the octree.

Returns: The node where the object ends up after insertion. In case of error, PGENULL is returned. If the given object is outside the bounds of this Octree Node, it is considered as an error.

Reimplemented in PureBoundingVolumeHierarchy.

Definition at line 105 of file PureOctree.cpp.

◆ operator=()

PureOctree & PureOctree::operator= ( const PureOctree & )

protected

Definition at line 324 of file PureOctree.cpp.

◆ subdivide()

TPureBool PureOctree::subdivide ( )

protectedvirtual

Reimplemented in PureBoundingVolumeHierarchy.

Definition at line 330 of file PureOctree.cpp.

Member Data Documentation

◆ BACK

const PureOctree::ChildIndex PureOctree::BACK = BIT(PureOctree::BIT_AXIS_Z)

static

Child is farther or same distance from camera than parent's position on Z-axis.

Definition at line 89 of file PureOctree.h.

◆ BIT_AXIS_X

const PureOctree::ChildIndex PureOctree::BIT_AXIS_X = 1

static

Bit to set to LEFT or RIGHT.

Definition at line 81 of file PureOctree.h.

◆ BIT_AXIS_Y

const PureOctree::ChildIndex PureOctree::BIT_AXIS_Y = 0

static

Bit to set to TOP or BOTTOM.

Definition at line 80 of file PureOctree.h.

◆ BIT_AXIS_Z

const PureOctree::ChildIndex PureOctree::BIT_AXIS_Z = 2

static

Bit to set to FRONT or BACK.

Definition at line 82 of file PureOctree.h.

◆ BOTTOM

const PureOctree::ChildIndex PureOctree::BOTTOM = BIT(PureOctree::BIT_AXIS_Y)

static

Child is under parent's position on Y-axis.

Definition at line 85 of file PureOctree.h.

◆ FRONT

const PureOctree::ChildIndex PureOctree::FRONT = 0

static

Child is closer to camera than parent's position on Z-axis.

Definition at line 88 of file PureOctree.h.

◆ fSize

TPureFloat PureOctree::fSize

private

Definition at line 131 of file PureOctree.h.

◆ LEFT

const PureOctree::ChildIndex PureOctree::LEFT = 0

static

Child is left to parent's position on X-axis.

Definition at line 86 of file PureOctree.h.

◆ nCurrentDepth

TPureUInt PureOctree::nCurrentDepth

private

Definition at line 132 of file PureOctree.h.

◆ nMaxDepth

TPureUInt PureOctree::nMaxDepth

private

Definition at line 133 of file PureOctree.h.

◆ nodeType

NodeType PureOctree::nodeType

private

Definition at line 134 of file PureOctree.h.

◆ parent

PureOctree* PureOctree::parent

protected

Definition at line 117 of file PureOctree.h.

◆ RIGHT

const PureOctree::ChildIndex PureOctree::RIGHT = BIT(PureOctree::BIT_AXIS_X)

static

Child is right to or in same as parent's position on X-axis.

Definition at line 87 of file PureOctree.h.

◆ TOP

const PureOctree::ChildIndex PureOctree::TOP = 0

static

Child is above or in same as parent's position on Y-axis.

Definition at line 84 of file PureOctree.h.

◆ vChildren

std::vector<PureOctree*> PureOctree::vChildren

protected

Definition at line 116 of file PureOctree.h.

◆ vObjects

std::set<const PureObject3D*> PureOctree::vObjects

private

Definition at line 135 of file PureOctree.h.

◆ vPos

PureVector PureOctree::vPos

private

Definition at line 130 of file PureOctree.h.

The documentation for this class was generated from the following files:

C:/__PR00F__/___developing___/projects/PGE/PGE/PURE/include/internal/SpatialStructures/PureOctree.h
C:/__PR00F__/___developing___/projects/PGE/PGE/PURE/source/SpatialStructures/PureOctree.cpp

Detailed Description

Public Types

Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Private Attributes

Member Typedef Documentation

◆ ChildIndex

Member Enumeration Documentation

◆ NodeType

Constructor & Destructor Documentation

◆ PureOctree() [1/3]

◆ ~PureOctree()

◆ PureOctree() [2/3]

◆ PureOctree() [3/3]

Member Function Documentation

◆ calculateIndex()

◆ DeleteChildren()

◆ findObject()

◆ getChildren()

◆ getDepthLevel()

◆ getMaxDepthLevel()

◆ getNodeType()

◆ getObjects()

◆ getParent()

◆ getPos()

◆ getSize()

◆ insertObject()

◆ operator=()

◆ subdivide()

Member Data Documentation

◆ BACK

◆ BIT_AXIS_X

◆ BIT_AXIS_Y

◆ BIT_AXIS_Z

◆ BOTTOM

◆ FRONT

◆ fSize

◆ LEFT

◆ nCurrentDepth

◆ nMaxDepth

◆ nodeType

◆ parent

◆ RIGHT

◆ TOP

◆ vChildren

◆ vObjects

◆ vPos