Octree Class Reference

Collaboration diagram for Octree:

Detailed Description

A loose octree implementation.

The octree divides the populated space, in its entirety, into an hierarchy of axis-aligned bounding boxes (cubes), residing in world space coordinates. Each cube is represented by an OctreeNode.

It is implemented to be fast, but not extravagantly gluttonous for memory. In practice, it means that the octree is not fully expanded. Rather, it is subdivided and modified as needed, using only as much memory as it actually needs.

There is presently only one parameter that control subdivision depth. The minimum size of a node is set upon constructing the octree. It is then guaranteed that the tree will never produce nodes smaller than set by subdividing itself.

Size and half-size always refers to the bounding cubes' side length (or half side length), never the shortest distance to the cube from it's center point or anything such.

Remarks:: The octree is initially centered around the world origin, but is dynamically extended as needed and best suited.
The loose octree was invented and dubbed by Thatcher Ulrich, refer to his website for tidbits of good information.


Public Member Functions
	Octree (real32 initial_size, real32 min_node_size)
	Octree constructor.
	~Octree () throw ()
	Octree destructor.
bool	queue_need_update (Cullable *obj) throw ()
	Notify the octree that a contained object's bounding volume has been changed or moved.
void	process_updates () throw ()
	Make needed changes to the octree.
void	add_object (Cullable *obj) throw ()
	Add an object to the octree.
void	remove_object (Cullable *obj) throw ()
	Remove an object from the octree.
bool	contains (Cullable *obj) const throw ()
	Check whether a given object is in the octree or not.
void	traverse_pvs (primitives::Camera camera, OctreeTraverser traverser) throw ()
	Traverse the octree, in rough front to back order.
void	purge () throw ()
	Remove unnecessary nodes.
unsigned int	get_excess_node_count () const throw ()
	Get the number of excess, unnecessary nodes in the octree.
unsigned int	get_contained_count () const throw ()
	Get the number of objects in the octree.
Protected Member Functions
OctreeNode *	grow_to_accomodate (Cullable *obj) throw ()
void	remove_subtree_from_empty_nodes (OctreeNode *subtree) throw ()
Private Attributes
OctreeNode *	m_root
	The root node of the octree.
std::set< Cullable * >	m_update_set
	The set of all objects having been marked as needing their octree info to be updated.
std::map< Cullable , OctreeNode >	m_objects
	Auxillary lookup table used to perform octree updates.
real32	m_min_node_size
	The minimal size of nodes to be constructed in the octree.
std::set< OctreeNode * >	m_empty_nodes
	Contains nodes that are possibly empty.
Classes
struct	OctreeNode
	A node in the octree. More...

Constructor & Destructor Documentation

Octree	(	real32	initial_size,
		real32	min_node_size
	)

Octree constructor.

Parameters:

	initial_size	The initial "half" size of the octree. Objects who's center point isn't enclosed by this volume (centered in the world origin), and nodes larger than this parameter, cause the octree to grow as needed.
	min_node_size	The minimum node size allowed. The tree will never be subdivided in octants with "half size" smaller than this.

See also:: OctreeNode

~Octree ( ) throw ()

Octree destructor.

Frees all resources allocated by the octree, as well as any OctreeNodes used by it.

Member Function Documentation

bool queue_need_update ( Cullable * obj ) throw ()

Notify the octree that a contained object's bounding volume has been changed or moved.

Returns:: true if the node was already scheduled for updating, false otherwise.

Remarks:: Does not queue children of obj, the caller is responsible for queuing child nodes, need they be updated.
Since rotations never change the bounding volume, the octree doesn't need to be notified of them. Call this method when an objects has been scaled or moved. If you don't, you can expect erroneous behaviour.

void process_updates ( ) throw ()

Make needed changes to the octree.

Processes the changes indicated by previous calls to queue_need_update(Cullable *). If no calls to queue_need_update(Cullable *) have been made prior to calling the function, or since the last time it was called, it will do nothing and return immediately.

Performance: Let $m$ and $n$ be the number of scheduled updates and octree nodes respectively. Expected running time (under "normal", non-degenerate conditions) is then $O(m)$ , worst case is $O(mn)$ .

Remarks:: This functionality cannot (easily) be put in OctreeNode, since it needs write access to the root node.

void add_object ( Cullable * obj ) throw ()

Add an object to the octree.

If the object already exists in the octree this operation will do nothing.

Parameters:

obj

The object to be inserted.

Remarks:: Worst case running time of this operation can be expected to be linear.

void remove_object ( Cullable * obj ) throw ()

Remove an object from the octree.

If the object isn't in the octree this operation will do nothing.

Parameters:

obj

The object to be removed.

Todo:: This code is sub-optimal in terms of performance, clean up scheduled!

bool contains ( Cullable * obj ) const throw ()

Check whether a given object is in the octree or not.

Returns:: true if obj is contained in the octree, false otherwise.

void traverse_pvs	(	primitives::Camera *	camera,
		OctreeTraverser *	traverser
	)			throw ()

Traverse the octree, in rough front to back order.

Depending on the cull tests specified it will also perform frustum culling against both the octree and object bounding volumes.

Parameters:

	frustum	The frustum (in world coordinates) used for culling.
	traverser	A pointer to the object called for each node in the octree, as it's being traversed - its traverse() method is called for each cullable in the PVS.

Note:: This interface is volatile and subject to change!

void purge ( ) throw ()

Remove unnecessary nodes.

Will remove any redundant octree nodes, i.e. empty leaf nodes or paths beginning in empty nodes, and thus necessarily end in empty nodes.

Running time: Linear in the number of excess nodes. Giving a pathological worst case performance of $O(n)$ in the total number of contained objects. The number of excess nodes can be retrieved using get_excess_node_count().

Remarks:: You may purge the octree periodically to keep memory usage down. However, refrain from calling it each frame is this could cause a performance hit - especially since some empty nodes are likely to be re-populated in the next frame. If you have a very dynamic scene it is recommended that you purge the octree once every few frames. If your particular scene changes little, you needn't purge it often.

unsigned int get_excess_node_count ( ) const throw ()

Get the number of excess, unnecessary nodes in the octree.

Returns the number of nodes that would be removed by a call to purge().

Returns:: The number of unnecessary nodes that can safely be removed.

Member Data Documentation

OctreeNode* m_root [private]

The root node of the octree.

Invariant:: Always non-null (except in the constructor).

Remarks:: May change over time (if the tree is enlarged).

std::set<Cullable *> m_update_set [private]

The set of all objects having been marked as needing their octree info to be updated.

Objects are added to the set by queue_need_update(Cullable *) and processed (and subsequently removed from the set) by process_updates().

std::map<Cullable *, OctreeNode *> m_objects [private]

Auxillary lookup table used to perform octree updates.

Maps a scene object to the octree node it is contained in. This structure must be updated as objects are inserted, moved in and deleted from the octree.

real32 m_min_node_size [private]

The minimal size of nodes to be constructed in the octree.

Remarks:: Note that while it is guaranteed that no nodes of size smaller than m_min_node_size are constructed, it is not guaranteed that they do not (already) exist (should you change the minimum size after they have been constructed).

std::set<OctreeNode *> m_empty_nodes [private]

Contains nodes that are possibly empty.

Nodes are put in this set when they are empty, however, they might remain in here even if they become repopulated before purge() is called. Note that not all empty nodes are guaranteed to be in the set, but it is guaranteed that at least one (that node being a leaf) node of every empty subtree can be found herein. It is used by purge() to remove unnecessary nodes.

Remarks:: add_object(Cullable *) removes re-populated nodes from the set.

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

src/renderer/Octree.hh
src/renderer/Octree.cc

peekabot

User manual

Octree Class Reference

Detailed Description

Public Member Functions

Protected Member Functions

Private Attributes

Classes

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation