ToyMaker::Octree Class Reference

A data structure used for speeding up spatial queries about 3-dimensional objects in the scene. More...

#include <spatial_query_octree.hpp>

Public Types
using	EntityAddressPair = std::pair<EntityID, OctreeNode::Address>
	An entity-id node-address pair indicating the address at which some entity known by the entity is present.

Public Member Functions
	Octree (uint8_t subdivisionThreshold, const AxisAlignedBounds &totalWorldBounds)
	Constructs a new octree which encapsulates the bounds specified in the argument.
std::vector< std::pair< EntityID, AxisAlignedBounds > >	findAllMemberEntities () const
	Retrieves all entities in this octant and its descendants.
std::vector< std::pair< EntityID, AxisAlignedBounds > >	findEntitiesOverlapping (const AxisAlignedBounds &searchBounds) const
	Retrieve all entities that intersect with the region described by searchBounds.
std::vector< std::pair< EntityID, AxisAlignedBounds > >	findEntitiesOverlapping (const Ray &searchRay) const
	Retrieves all entities that intersect with the ray described by searchRay.
void	insertEntity (EntityID entityID, const AxisAlignedBounds &entityWorldBounds)
	Inserts an entity into the octree.
void	removeEntity (EntityID entityID)
	Removes an entity from the octree, based on its cached node address.

Static Public Attributes
static constexpr float	kMaxDimensionRatio { 20.f }
	The maximum possible ratio between two dimensions of the region enclosed by the octree.

Private Attributes
std::shared_ptr< OctreeNode >	mRootNode
	The root node of the octree.
std::map< EntityID, OctreeNode::Address >	mEntityAddresses {}
	A mapping of entity IDs to their addresses computed at entity insertion (and recomputed when the octree grew or shrank).

Detailed Description

A data structure used for speeding up spatial queries about 3-dimensional objects in the scene.

The octree is essentially a node representing a cuboidal region that can be subdivided into equally-proportioned smaller cuboidal regions recursively. Each node of the octree maintains a list entities contained by its region.

When given a query in the form of some geometry (currently only AABBs and Rays), where entities overlapping or contained by that geometry are desired, the octree speeds up the query by limiting its search to only those entities whose nodes overlap the query geometry.

Octrees presume the finiteness of geometry contained by them. An octree can grow in size or shrink so long as the region it encloses does not become infinite, nor fall below some threshold granularity.

See also

OctreeNode

Constructor & Destructor Documentation

Octree()

ToyMaker::Octree::Octree ( uint8_t subdivisionThreshold, const AxisAlignedBounds & totalWorldBounds )

inline

Constructs a new octree which encapsulates the bounds specified in the argument.

Parameters

subdivisionThreshold	The number of member entities for a single node beyond which that node's subdivision should be attempted.
totalWorldBounds	The region containing all of the objects in the world, which this octree will be defined to encompass.

Member Function Documentation

findAllMemberEntities()

std::vector< std::pair< EntityID, AxisAlignedBounds > > ToyMaker::Octree::findAllMemberEntities ( ) const

inline

Retrieves all entities in this octant and its descendants.

Available query methods

Returns

std::vector<std::pair<EntityID, AxisAlignedBounds>> A list of entities (their IDs and AABBs) known by the octree.

findEntitiesOverlapping() [1/2]

std::vector< std::pair< EntityID, AxisAlignedBounds > > ToyMaker::Octree::findEntitiesOverlapping ( const AxisAlignedBounds & searchBounds ) const

inline

Retrieve all entities that intersect with the region described by searchBounds.

Parameters

searchBounds

The AABB intersecting or within which entities should be retrieved.

Returns

std::vector<std::pair<EntityID, AxisAlignedBounds>> The entities found to match the query.

findEntitiesOverlapping() [2/2]

std::vector< std::pair< EntityID, AxisAlignedBounds > > Octree::findEntitiesOverlapping

(

const Ray &

searchRay

)

const

Retrieves all entities that intersect with the ray described by searchRay.

Parameters

searchRay

The ray intersecting which entities need to be retrieved.

Returns

std::vector<std::pair<EntityID, AxisAlignedBounds>> The entities found to match the query.

insertEntity()

void Octree::insertEntity	(	EntityID	entityID,
		const AxisAlignedBounds &	entityWorldBounds )

Inserts an entity into the octree.

Parameters

entityID	The ID of the entity being inserted.
entityWorldBounds	The bounds of the entity's AABB.

removeEntity()

void Octree::removeEntity

(

EntityID

entityID

)

Removes an entity from the octree, based on its cached node address.

Parameters

entityID

The ID of the entity being removed.

Member Data Documentation

kMaxDimensionRatio

float ToyMaker::Octree::kMaxDimensionRatio { 20.f }

staticconstexpr

The maximum possible ratio between two dimensions of the region enclosed by the octree.

Specified in order to keep nodes more-or-less cuboidal, and preventing them from being too flat or line-like (and thereby causing the octree to have to expand or shrink too often).

---

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

• src/engine/spatial_query_octree.hpp
• src/engine/spatial_query_octree.cpp