   Octree implementation
  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?   
  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.   ;  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 templatesee reference to class template instantiation 'math::basic_octree_traits<elem_t,float_t,vector3_t>' being compiledtemplate<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 typetypedef typename octree_traits<elem_t,float_t,vector3_t>octree_traits_t;};And finally the octree class that contains the public interfacetemplate<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]