Sign in to follow this  
Hrethric

Spatial Partioning - Linear Octree Question

Recommended Posts

When reviewing the different forms of spatial partioning for an outdoor environment, I ran across linear octrees. Ok, so setting up an octree is a fairly simple process, it's basically AABB. Linear octrees add a somewhat unknown element to me though. Since the children are no longer stored in the nodes for a linear octree, how do you build the octree itself? Any information on linear octrees you could provide would be great; at the moment I am kind of at a stand still in my research on them.

Share this post


Link to post
Share on other sites
Basically your tree is a linear array of N octree nodes, octree nodes do not have information for the indices as you said.
You can compute the index of the child nodes by using the following formula:
N = index of your node
8N+1
8N+2
8N+3
8N+4
8N+5
8N+6
8N+7
8N+8

You can build the tree in several ways, some people use a standard tree with links to the nodes, and then linearize it by writing out all the data except the child node data:

struct myOctNode
{
struct myOctData
{} data;
myOctNode *childX; // 8 of these
}

when storing this as a linear array you can store only myOctData:
std::vector<myOctData> linearOctree;


More efficient is to use the array itself while building the tree, and using indices as "handles" to the individual nodes.

Hope this helps

Share this post


Link to post
Share on other sites

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