Octrees

http://www.google.co.uk/search?hl=en&q=octree&btnG=Google+Search&meta=
http://en.wikipedia.org/wiki/Octree

Not too terribly useful, but it's better than nothing :p
Thanks (more is all ways appreciated). :)

Ok, I seem to have a little better understanding of Octrees. It seems they are the same exact things as Quadtrees and k-d trees, except quadtrees divide each node into four new nodes and k-d trees divide each node into two new nodes, while octrees divide into eight. Is there any advantage to each other, and would I be correct in thinking that k-d trees and quadtrees would be easier to implement compared to octrees?

Think of a cube bounding your entire scene. Cut the cube into eight smaller cubes, each containing now 1/8th of that scene...then cut each of those cubes up further. This is really what an Octree is, a hierarchical spacial subdivision of a polygon soup into cubic regions.

Starting from the first cube that might bound the entire scene, it has eight nodes below it for the initial subdivision. Each node has eight nodes below it (unless it is a leaf node), hence why it is called an Oct-tree.

The scene can be progressively subdivided in a number of ways. Possibilities can be to subdivide until a given node contains a specific amount of polygons, or to subdivide uniformly so that each cube is a similar size to the other sibling nodes at any given point in the tree. There is also the idea of 'loose octrees' where cubes are allowed to overlap in order to conveniently share data in an optimal way.

A common use of an Octree is as a visibility test. Any node of the octree can be determined to be completely on screen or not. It it is, then all child nodes are on screen, thus all their geometry is visible too. Likewise, a node that is offscreen guarantees child nodes are also offscreen. No need to draw anything in this case, the geometry is culled through trivial rejection. A node that is partially on/off screen is processed further...tests now progress onto its children.

Similarly, Octrees can assist in a ray-casting situation. The ray is compared with the octree nodes such that a simple ray vs box intersection test takes place. If the ray intersects, the test continues against the child nodes. When the leave node is found, the contained polygons can be processed...nothing else.

Does that help?

Quote:

Original post by bronxbomber92 Ok, I seem to have a little better understanding of Octrees. It seems they are the same exact things as Quadtrees and k-d trees, except quadtrees divide each node into four new nodes and k-d trees divide each node into two new nodes, while octrees divide into eight. Is there any advantage to each other, and would I be correct in thinking that k-d trees and quadtrees would be easier to implement compared to octrees?

It looks to me that you've made comparisons against things that would suggest you have indeed figured it out.

To be honest, all of the above are fairly straightforward to work with.

Advantages of one vs another...well quadtrees of course can be more appropriate to a terrain engine whereas octrees might be better off with geometry that is distributed more arbitrarily.

Thanks freakchild, that does help :)

One last question, hoq do you actually divide the geometry into node? Is it basically like a simple collision test where you think of the node as a "solid" cube, and check to see if your array of vertices intersect it, and if so, you further sub-divide that node into 8 more nodes, and do the collision test again? If so, does that mean each node with have an array of vertices, and some child nodes with store a copy of part of the parents vertices (thus, extra, possibly wasteful memory?).


edit - Also, if you further sub-divide, should you even keep the parent node afterwards since you can just test against the smaller nodes??
Thanks!

Quote:

Original post by bronxbomber92 Thanks freakchild, that does help :) One last question, hoq do you actually divide the geometry into node? Is it basically like a simple collision test where you think of the node as a "solid" cube, and check to see if your array of vertices intersect it, and if so, you further sub-divide that node into 8 more nodes, and do the collision test again? If so, does that mean each node with have an array of vertices, and some child nodes with store a copy of part of the parents vertices (thus, extra, possibly wasteful memory?). edit - Also, if you further sub-divide, should you even keep the parent node afterwards since you can just test against the smaller nodes?? Thanks!

More or less yes, you think of the node as a cube. If any piece of geometry is within it then it boils down to vertex in cube (or poly in cube) checks. If a vertex straddles the edge of the cube you can either have it be a member of both cubes (which may be faster in a given case) or clip the geometry into two pieces and have each of the resulting pieces in the adjacent cubes.

If you subdivide a node, then the node only contains 8 more nodes...no geometry. You only put geometry in the leaf nodes of the tree (where there are no further nodes).

I thought each node contained geometry... So, only the "bottom" nodes contain the actual geometry?

Usually, any node can hold content. You store something inside the smallest node that it still fits in completely. Something that lies on the border of two nodes, doesn't fit into either of them, and is therefor stored in their parent node. This means that you'll have to deal with the content of all nodes that you touch, not just the smallest ones.
If you decide that only leaf nodes can hold content, then multiple nodes can (and likely, will) hold, or better, reference the same content - in that case, you'll have to deal with the duplication.

Of course, there are various variants of this structure, such as loose octrees (nodes overlap each other a bit, so objects can be placed in lower nodes more often), adaptive octrees (nodes are subdivided when their content reaches a certain maximum), etc. It's totally up to you which one you pick - perhaps you want to customize your octree some more, depending on what exactly you need.


Either way, I don't think it's wise to divide your scene up into vertices. I haven't done much with 3D graphics, but from what I know, sending a few vertices less to the hardware isn't going to give you much performance gain. Sending them all in one bunch, or storing them on the 3D card, gives better gains. I think it's therefor much better to store models, objects, in your octree, rather than splitting them up into vertices and polygons.
Besides... what if you're animating a model? You'd constantly be updating vertex positions in your octree... which is something to consider: updating positions within your data structure.

That's more or less my method. My models are stuffed into the octree based on their AABB (whose XZ plane is made into a square) and translation. If there is a collision based on this, then I do an on-the-fly sort for the two models based on their relative positions and orientations and test again until I have the information I need. This works nicely since all of my rotations come from joints, and so that information is already calculated.

Makes sense. I was thinking that Octrees were more of a restrictive, set division. I guess I'll mess around with them, and see what I can come up with :p

Thanks for all your guys/gals help and input!
-Jedd