Sign in to follow this  

Octree implementation

This topic is 3103 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
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 this post


Link to post
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]

Share this post


Link to post
Share on other sites

This topic is 3103 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this