Jump to content
  • Advertisement
Sign in to follow this  

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.

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

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

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
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!