# Octree implementation

## Recommended Posts

I started to implement my own octree, however there are things I don't fully understand the concept yet. My current tree subdivides an axis aligned box (all available space) into 8 child boxes, of half the bounds of the parent box. I think this is the same for all octrees (except loose ones). I then dealt with insertion of elements. Every node in my tree can store up to 8 elements. When a 9th elements is being inserted, they are split among child nodes (which are created on-demand, so a node can have anything between 0 and 8 child nodes). Thus Considering every branch, only the deepest nodes actually stores elements, all other simply subdivide space. I've been reading a lot of posts on forums about the subject, and I got the impression, that there are implementations that somehow store an arbitrary list of elements in a node. But I wonder how to determine if a node should create new branches or not. For example, Yann L talks about his galaxy generator: "At the root level, there are 50 million stars. At the deepest level ( #12 ) there are 200 stars. [...] When the node gets recursively split into 8 children, all stars from the parent node gets distributed into the correct child ( selected based on their coordinates )." Does anyone have an example what kind of functions can be used to determine if a node should create new branches?

##### Share on other sites
phresnel    953
One possible measure of cost are Havran's Surface Area Heuristics, which are commonly applied to Kd-trees in Ray Tracing, but they are not limited to Kd-trees or Ray Tracing. His heuristics give a rough probability with which a ray hits the geometry inside a node. As a result of SAH, you would also get large, empty spaces, which are useful for an early return upon tree-traversal.

Of course SAH is mostly useful in ray tracing or when you want a fast collision detector, for raw rasterizing, I think it's more important to reduce the number of polygons.

##### Share on other sites
Thanks for the info. It helped me to think of more reasons on how an octree can be subdivided (especially about the criterias met). However I have some template issues with my implementation. I wanted my octree to accept another template argument: a traits class that defines the behaviour of the octree. In order to be flexible, this class is required to offer a function bool subdivide( const node & ) that is invoked to test if subdivision of a node is required or not. However this causes a C3200 error:

This is the traits class, that defines the octree's subdivision behaviour. The error points to the "typedef typename..." line:

error C3200: 'math::basic_octree_traits<elem_t,float_t,vector3_t>' : invalid template argument for template parameter 'octree_traits', expected a class template
see reference to class template instantiation 'math::basic_octree_traits<elem_t,float_t,vector3_t>' being compiled
template<	typename elem_t,	typename float_t,	typename vector3_t>class basic_octree_traits{public:	typedef typename octree_node<elem_t,float_t,vector3_t,basic_octree_traits>   octree_node_t;};

This is the node class that contains a std::map with the possible child nodes.
template<	typename elem_t,	typename float_t,	typename vector3_t,	template	<		typename T1,		typename T2,		typename T3	>	class octree_traits>class octree_node{	/// Typedef for the octree traits type	typedef typename octree_traits<elem_t,float_t,vector3_t>               octree_traits_t;};

And finally the octree class that contains the public interface
template<	typename elem_t,	typename float_t,	typename vector3_t = vector3<float_t>,	template	<		typename T1,		typename T2,		typename T3	>	class octree_traits = basic_octree_traits>class octree{};

Can anybody explain why this error appears? I am passing a class template to the last parameter of octree_node, as basic_octree_traits is not a complete instantiation.

*Edit* Well, I could somewhat solve my problem: I replaced the template template stuff with a simple typename octree_traits and passed an instantiated basic_octree_class into the parameter. Seems that VS 2008 isn't able to do this otherwise.

[Edited by - SiS-Shadowman on June 19, 2009 12:50:39 AM]

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account