# Spatial Partioning - Linear Octree Question

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

## 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 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

1. 1
2. 2
Rutin
21
3. 3
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633736
• Total Posts
3013603
×