Spatial Partioning - Linear Octree Question
Author
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.
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
