Jump to content
  • Advertisement
Sign in to follow this  
kbundy

How does the octree be implemented?

This topic is 4524 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

Hi I am currently reading an algortihm of an octree. I know how it actually work. It's starts off one large space and subdivide it into 4 subspace and keep subdivide until there is no object in the space or only left with one object in it. I am wondering how does this structures can be implemented in code and how does it usually be traversed.

Share this post


Link to post
Share on other sites
Advertisement
Depends on the programming language. In C/C++, it's usually a structure with 9 pointers in it, one for each child node and one for the parent node, or NULL for the child nodes if it's a leaf.
As for traversing it, you just loop through each node, and check it's extents. If the object is in this node, then you check each of the 8 child nodes, and continue until you reach a leaf node.

Share this post


Link to post
Share on other sites

Quote:

and subdivide it into 4 subspace


You probably meant 8 subspaces here. Quadtree uses 4 subspaces.



class OctTreeNode
{
protected:
OctTreeNode *pChild[8];
OctTreeNode *pParent;
...
some data
....

OctTreeNode *GetNode(Vector3d &point);
public:

void InsertObject(GameObject *pObj);
};




Depending on the needs you'll probably have different member functions. But basically as explained, octrees are used for queries such as "render objects in frustum" or "get nearest object" or perhaps ray tracing.

For example, to get a octree node with a position, you'd start with the top node and then check each children's bound if the point is located in their space and continue the search with that subtree. (Of course, this is rather slow and you could optimize it by checking the relation of the point to the center of the bound. With 3 tests you are able to find the correct subspace where to continue the search.)

There are lots of things related to octrees, quadtrees, binary trees - but all of them tend to work more and less in the same way.



Share this post


Link to post
Share on other sites

Hehe yea 2D Octree is subdivided 4 and 3D is 8 ....

Do I need to define the width, depth and height cube space for the octree algorithm?

Share this post


Link to post
Share on other sites
Quote:
Original post by kbundy

Hehe yea 2D Octree is subdivided 4 and 3D is 8 ....

Do I need to define the width, depth and height cube space for the octree algorithm?
It's up to you, it depends if you need it. I'd recommend storing the size (or width, height, depth if your nodes aren't cubes) and position of the node to make it faster and easier to test if points are in the node, but I don't think you really need anything else apart from a list of objects in the node - unless you do it the other way around and have objects reference nodes instead of nodes reference objects.

Share this post


Link to post
Share on other sites
Quote:
Original post by kbundy

Hehe yea 2D Octree is subdivided 4 and 3D is 8 ....

Do I need to define the width, depth and height cube space for the octree algorithm?


Erm, if it's subdivided by 4 then it's a quadtree not an octree.

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!