Ocular Engine
Ocular::Core::BVHSceneTree Class Reference

#include <BVHSceneTree.hpp>

Inheritance diagram for Ocular::Core::BVHSceneTree:
Ocular::Core::ISceneTree

Public Member Functions

virtual void restructure () override
 
virtual void destroy () override
 
virtual void addObject (SceneObject *object) override
 
virtual void addObjects (std::vector< SceneObject * > const &objects) override
 
virtual bool removeObject (SceneObject *object) override
 
virtual void removeObjects (std::vector< SceneObject * > const &objects) override
 
virtual void getAllObjects (std::vector< SceneObject * > &objects) const override
 
virtual void getAllVisibleObjects (Math::Frustum const &frustum, std::vector< SceneObject * > &objects) const override
 
virtual void getIntersections (Math::Ray const &ray, std::vector< SceneObject * > &objects) const override
 
virtual void getIntersections (Math::BoundsSphere const &bounds, std::vector< SceneObject * > &objects) const override
 
virtual void getIntersections (Math::BoundsAABB const &bounds, std::vector< SceneObject * > &objects) const override
 
virtual void getIntersections (Math::BoundsOBB const &bounds, std::vector< SceneObject * > &objects) const override
 
virtual void setDirty (UUID const &uuid) override
 
virtual SceneTreeType getType () const override
 

Protected Member Functions

void rebuild ()
 
void insertNewObjects ()
 
void updateDirtyNodes ()
 
bool rebuildNeeded () const
 
void destroyNode (BVHSceneNode *node) const
 
void insertObject (SceneObject *object)
 
BVHSceneNodefindParent (BVHSceneNode *node, SceneObject *object) const
 
BVHSceneNodefindNearest (BVHSceneNode *node, uint64_t const &morton) const
 
void findVisible (BVHSceneNode *node, Math::Frustum const &frustum, std::vector< SceneObject * > &objects) const
 
void findIntersections (BVHSceneNode *node, Math::Ray const &ray, std::vector< std::pair< SceneObject *, float >> &objects) const
 
void findIntersections (BVHSceneNode *node, Math::BoundsSphere const &bounds, std::vector< SceneObject * > &objects) const
 
void findIntersections (BVHSceneNode *node, Math::BoundsAABB const &bounds, std::vector< SceneObject * > &objects) const
 
void findIntersections (BVHSceneNode *node, Math::BoundsOBB const &bounds, std::vector< SceneObject * > &objects) const
 
void build ()
 
void createMortonPairs (std::vector< MortonPair > &pairs) const
 
BVHSceneNodegenerateTree (BVHSceneNode *parent, std::vector< MortonPair > const &pairs, uint32_t first, uint32_t last) const
 
uint32_t findSplit (std::vector< MortonPair > const &pairs, uint32_t first, uint32_t last) const
 
void fitNodeBounds (BVHSceneNode *node) const
 

Additional Inherited Members

- Protected Attributes inherited from Ocular::Core::ISceneTree
std::vector< SceneObject * > m_NewObjects
 Newly added objects that are waiting to be added to the tree.
 

Detailed Description

Linear implementation of a Bounding Volume Hierarchy (BVH) Scene Tree.
For a parallel implementation (GPU) please see ... (does not exist yet).

The BVH Tree is implemented as a binary tree where each leaf node contains exactly one child SceneObject. This SceneObject may itself have child objects attached to it of course, but each node is limited to a single object.

Internal nodes have exactly two child nodes. In the event of an odd amount of leaf nodes, the root node can have direct child leaf nodes.

Enforcing these rules allows for the following to be expected:

A tree has N leaf nodes
A tree has N-1 internal nodes (including root)

Each node has a corresponding bounding box that encompasses all of it's children. Thus, the bounds of a leaf node are equal to that of it's attached object. The bounds of a internal node contains both of it's children. The bounds of the root then must encompass all objects within the entire scene.

The implementation of this tree is based on several sources:

Tero Karras, NVIDIA Research
Thinking Parallel, Parts I-III
http://devblogs.nvidia.com/parallelforall/thinking-parallel-part-i-collision-detection-gpu/

Real-Time Rendering, 3rd Edition
...

Daniel Kopta, et al. 
Fast, Effective BVH Updates for Animated Scenes
http://www.cs.utah.edu/~thiago/papers/rotations.pdf

Member Function Documentation

void Ocular::Core::BVHSceneTree::addObject ( SceneObject object)
overridevirtual

Adds the object to the scene tree.

Note
The object will not be instantly added to the tree proper. Instead, they will be added next time the restructure method is invoked. The restructure method is automatically called by the engine periodically. If one needs the object to be immediately available in the tree, then they must manually call the restructure method themselves.
Parameters
[in]object

Implements Ocular::Core::ISceneTree.

void Ocular::Core::BVHSceneTree::addObjects ( std::vector< SceneObject * > const &  objects)
overridevirtual

Adds a collection of objects to the scene tree.

Note
The objects will not be instantly added to the tree proper. Instead, they will be added next time the restructure method is invoked. The restructure method is automatically called by the engine periodically. If one needs the object to be immediately available in the tree, then they must manually call the restructure method themselves.
Parameters
[in]objects

Implements Ocular::Core::ISceneTree.

void Ocular::Core::BVHSceneTree::build ( )
protected

Builds the tree from the collection of objects stored in m_AllObjects.

void Ocular::Core::BVHSceneTree::createMortonPairs ( std::vector< MortonPair > &  pairs) const
protected

Calculates and sorts the Morton Codes for all objects in the tree.

Parameters
[out]pairsContainer to be filled with the sorted Morton Codes and their associated SceneObject
void Ocular::Core::BVHSceneTree::destroy ( )
overridevirtual

Destroys the SceneTree and all nodes contained within. Does not destroy any SceneObjects.

Implements Ocular::Core::ISceneTree.

void Ocular::Core::BVHSceneTree::destroyNode ( BVHSceneNode node) const
protected

Safely destroys the specified node and all children.

void Ocular::Core::BVHSceneTree::findIntersections ( BVHSceneNode node,
Math::Ray const &  ray,
std::vector< std::pair< SceneObject *, float >> &  objects 
) const
protected

Recursively finds all SceneObjects that intersect with the specified ray. The results are unordered.

Parameters
[in]nodeCurrent node.
[in]rayRay to test against.
[out]objectsAll discovered SceneObjects that intersect and their intersection points.
void Ocular::Core::BVHSceneTree::findIntersections ( BVHSceneNode node,
Math::BoundsSphere const &  bounds,
std::vector< SceneObject * > &  objects 
) const
protected

Recursively finds all SceneObjects that intersect with the specified bounds.

Parameters
[in]nodeCurrent node.
[in]boundsBounds to test against.
[out]objectsAll discovered SceneObjects that intersect.
void Ocular::Core::BVHSceneTree::findIntersections ( BVHSceneNode node,
Math::BoundsAABB const &  bounds,
std::vector< SceneObject * > &  objects 
) const
protected

Recursively finds all SceneObjects that intersect with the specified bounds.

Parameters
[in]nodeCurrent node.
[in]boundsBounds to test against.
[out]objectsAll discovered SceneObjects that intersect.
void Ocular::Core::BVHSceneTree::findIntersections ( BVHSceneNode node,
Math::BoundsOBB const &  bounds,
std::vector< SceneObject * > &  objects 
) const
protected

Recursively finds all SceneObjects that intersect with the specified bounds.

Parameters
[in]nodeCurrent node.
[in]boundsBounds to test against.
[out]objectsAll discovered SceneObjects that intersect.
BVHSceneNode * Ocular::Core::BVHSceneTree::findNearest ( BVHSceneNode node,
uint64_t const &  morton 
) const
protected

Finds the node with the nearest morton code to the one specified.

Parameters
[in]nodeCurrent node.
[in]mortonMorton code to compare against
Returns
The nearest node.
BVHSceneNode * Ocular::Core::BVHSceneTree::findParent ( BVHSceneNode node,
SceneObject object 
) const
protected

Finds the leaf node that owns the specified object in the tree.

Parameters
[in]nodeCurrent node.
[in]objectThe object to find.
Returns
The parent node.
uint32_t Ocular::Core::BVHSceneTree::findSplit ( std::vector< MortonPair > const &  pairs,
uint32_t  first,
uint32_t  last 
) const
protected

Finds the index to split the remaining objects to fit the tree.

Parameters
[in]pairsSorted list of morton code/scene object pairings.
[in]firstIndex of first object remaining to be added to the tree
[in]lastIndex of the last object remaining to be added to the tree
Returns
Best index to split the remaining objects.
void Ocular::Core::BVHSceneTree::findVisible ( BVHSceneNode node,
Math::Frustum const &  frustum,
std::vector< SceneObject * > &  objects 
) const
protected
Parameters
[in]nodeCurrent node.
[in]frustumFrustum to test against.
[out]objectsAll discovered SceneObjects that intersect.
void Ocular::Core::BVHSceneTree::fitNodeBounds ( BVHSceneNode node) const
protected

Adjusts the bounds of the specified node to fit over it's children.

Parameters
[in]nodeNode to adjust the bounds of.
BVHSceneNode * Ocular::Core::BVHSceneTree::generateTree ( BVHSceneNode parent,
std::vector< MortonPair > const &  pairs,
uint32_t  first,
uint32_t  last 
) const
protected

Recursively generates the tree in a top-down manner beginning at the root.

Parameters
[in]parentThe node calling this recursive sequence.
[in]pairsSorted list of morton code/scene object pairings.
[in]firstFirst node in the current split
[in]lastLast node in the current split (inclusive)
Returns
Pointer to the root node of the newly generated tree.
void Ocular::Core::BVHSceneTree::getAllObjects ( std::vector< SceneObject * > &  objects) const
overridevirtual

Returns a flat list of all objects in the scene tree. No order is guaranteed for the returned objects.

Parameters
[out]objectsList of all objects in the scene tree.

Implements Ocular::Core::ISceneTree.

void Ocular::Core::BVHSceneTree::getAllVisibleObjects ( Math::Frustum const &  frustum,
std::vector< SceneObject * > &  objects 
) const
overridevirtual

Returns a flat list of all visbile objects in the scene tree. No order is guaranteed for the returned objects.

Parameters
[in]frustumViewing frustum to check visibility against.
[out]objectsList of all visible objects in the scene tree.

Implements Ocular::Core::ISceneTree.

void Ocular::Core::BVHSceneTree::getIntersections ( Math::Ray const &  ray,
std::vector< SceneObject * > &  objects 
) const
overridevirtual

Returns a list of all scene objects that intersect with the specified ray. The objects are given in the order they are encountered along the ray.

For example, if a ray is created with the origin at the camera and extends along the view direction, then objects[0] will be the object closest to the camera and objects[size-1] will be the object farthest away from the camera.

Parameters
[in]ray
[out]objectsList of objects intersected by the specified ray.

Implements Ocular::Core::ISceneTree.

void Ocular::Core::BVHSceneTree::getIntersections ( Math::BoundsSphere const &  bounds,
std::vector< SceneObject * > &  objects 
) const
overridevirtual

Returns a list of all scene objects that intersect with the sphere. An intersection occurs if a SceneObject either partially intersects or is entirely contained within the bounds.

Parameters
[in]bounds
[out]objectsList of objects intersected by the specified bounds.

Implements Ocular::Core::ISceneTree.

void Ocular::Core::BVHSceneTree::getIntersections ( Math::BoundsAABB const &  bounds,
std::vector< SceneObject * > &  objects 
) const
overridevirtual

Returns a list of all scene objects that intersect with the specified AABB. An intersection occurs if a SceneObject either partially intersects or is entirely contained within the bounds.

Parameters
[in]bounds
[out]objectsList of objects intersected by the specified bounds.

Implements Ocular::Core::ISceneTree.

void Ocular::Core::BVHSceneTree::getIntersections ( Math::BoundsOBB const &  bounds,
std::vector< SceneObject * > &  objects 
) const
overridevirtual

Returns a list of all scene objects that intersect with the specified OBB. An intersection occurs if a SceneObject either partially intersects or is entirely contained within the bounds.

Parameters
[in]bounds
[out]objectsList of objects intersected by the specified bounds.

Implements Ocular::Core::ISceneTree.

SceneTreeType Ocular::Core::BVHSceneTree::getType ( ) const
overridevirtual

Returns the type of SceneTree this implementation is.

Implements Ocular::Core::ISceneTree.

void Ocular::Core::BVHSceneTree::insertNewObjects ( )
protected

Individually inserts new objects into the tree.

If the number of new objects that need to be added is significant, then a complete tree rebuild will often be faster and more accurate.

void Ocular::Core::BVHSceneTree::insertObject ( SceneObject object)
protected

Inserts a single new object into the tree.

Parameters
[in]object
void Ocular::Core::BVHSceneTree::rebuild ( )
protected

Performs a complete rebuild of the tree.

This is a potentially costly operation and should only be called when absolutely necessary (either on initial tree construction or when a significant number of new objects have been added).

bool Ocular::Core::BVHSceneTree::rebuildNeeded ( ) const
protected

Checks to see if the tree needs to be rebuilt.

bool Ocular::Core::BVHSceneTree::removeObject ( SceneObject object)
overridevirtual

Removes the object from the scene tree.

Note that this simply removes the reference to the object and does not actually delete/deallocate the object as that should be handled by the scene manager.

Parameters
[in]object

Implements Ocular::Core::ISceneTree.

void Ocular::Core::BVHSceneTree::removeObjects ( std::vector< SceneObject * > const &  objects)
overridevirtual

Removes all objects from the scene tree.

Note that this simply removes the reference to the object and does not actually delete/deallocate the object as that should be handled by the scene manager.

Parameters
[in]object

Implements Ocular::Core::ISceneTree.

void Ocular::Core::BVHSceneTree::restructure ( )
overridevirtual

Periodically called (typically once per frame), this method behaves differently based on the SceneTree implementation. Generally though, it will update interal nodes based on any movement and/or rotation that has happened since the last call.

Implements Ocular::Core::ISceneTree.

void Ocular::Core::BVHSceneTree::setDirty ( UUID const &  uuid)
overridevirtual

Indicates that the tree is dirty, and that the object with the given UUID was explicitly changed.

Implements Ocular::Core::ISceneTree.

void Ocular::Core::BVHSceneTree::updateDirtyNodes ( )
protected

Updates all dirty nodes (leafs) whose objects have either moved or rotated.

Todo:
Update dirty nodes

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