Honest, I don't get it. Yeah, its a cool idea to think about: cubes made of cubes, made of cubes, ... The code isn't faster over other data types and I can't see where memory space would be conserved in practical use.

I get to this quandry by way of trying to implement an efficient algorithm. The only way to avoid the eight way branch is to use a binary octree.

and ebx, 111y
jmp

...this would require greater depth for the same spatial refinement. If we are going to use an eight-way branch then binary trees provide far greater flexiblity.
Posted on 2004-11-10 18:54:18 by bitRAKE
You miss the point I guess - binary trees divide things into half, and half again.. ie, each node represents a single splitting plane.

Imagine the initial space as a 3d cube, please.
If you applied three splitting planes to the cube (split the cube in half along the x, y and z axes), you have eight subcubes.

Octree nodes represent these subcubes.

If you can picture all this so far, now comes the cool part, and why OSP has been revisited and in its new form is preferred over BSP..
The Octree inherently encodes A HIERARCHY OF BOUNDING CUBES.
Why is this cool? Because we can use it to perform wholesale hierarchical culling at any level in the tree we require :) It's inherently hierarchical, and inherently cubic. The cubes are all axially-aligned and the math for them is VERY cheap. The fact that they are in a hierarchy is something that has only recently been taken advantage of.
Posted on 2004-11-10 23:30:07 by Homer
A better designed octree node keeps a list of children rather than keeping up to eight null pointers... it's up to the oop coder to write a nice dynamic octree node object class.
Posted on 2004-11-10 23:32:06 by Homer
I do understand the 3D aspect. You are speaking conceptually, but I am speaking in terms of actual code - a linear running process. How in code can you divide something eight ways - three branches - same for a binary tree.

I'm just saying at the code level it breaks down to binary partitioning with three levels processed per octree node. So, it can be seen also as a condensed binary tree.
Posted on 2004-11-11 01:44:23 by bitRAKE
Then again the code can be used to do binary tree or quadtree or octtree or anything as long as they are power of 2. Quite a good idea, bitRAKE. :-D
Posted on 2004-11-11 05:40:31 by roticv
i think that you can see an octree as a special bsp tree, where the positions of the planes are always fixed :)

on www.cbloom.com you can find some ideas about the implementation of octrees. talking about octrees, do you know "loose octrees"? i prefer them.
Posted on 2004-11-11 07:27:55 by lifewire
lifewire is correct.

If the structure of the tree is stored as a bitpattern (like it is in some bsp file formats) then it is possible both with bsp and osp to calculate the address of node data stored in a static array - there doesn't need to be ANY LINKS IN THE NODES :)

Due to the cubic nature of the osp tree and the premise above, it is possible to "walk the tree nodes" in any axial direction, again without using any links to do so.

It is possible to load an osp datafile into memory and walk its data directly, without any need to create a true linked tree of nodes, just like you can with a bsp datafile, but with more flexibility when walking the tree.
Posted on 2004-11-11 21:55:32 by Homer