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.

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.

Quote:
and subdivide it into 4 subspace

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



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.

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?

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.

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.