I''ve been doing some reading recently in to linked lists and found them really easy to implement\understand. With collision detection looming on the horizon I read up on binary tree''s which see really cool. Now I find references to things like Octtree''s or something. I was wondering if anyone could point me to a good description on what they are \ how they are used \ why you would used them rather than other tree''s. (The don''t appear in the index of my "Data Structures, Algorithms & Software Principles" book Thanks gimp

Hi Gimp,

I''m pretty sure, you will not see the DataStructure ''Octree'' in any Book for now, still too young.

But, anyway, Octree are used to subdivide world in a way that, you can eliminate a lot of wasted CPU cycle by eliminating polygon that you cannot see. The trick here its to have a big Head-Node (a box) around your world. So all the polygons are a part of this head-node. But this come to nothing. But, if you subdivide you Head-Node cube in 8 cadran (Octree''s name came from that), making 8 new box and sort polygons in those box, you can eliminating 1/2 of the polygon. Resubdivide each box in 8 new boxes, sort polygon in those boxes, and so on.

So when you render, you travel the world by parsing those cube, when a cube is invisible, dont go farter. So, you will get a list of polygons that [bold]may be visible[/bold] (they are in you FOV - field of view). Do anything you want after, because Octree are just there to get this smaller list of polygons.

As can you see, instead of doing all complex calculation to known, if yes or no, a polygon is in you FOV, you discard alot of polygon by selecting cube that are in your FOV. So, you will have save a lot of CPU Cycle.

And, DONT FALL IN BOTTLENECKS. I mean, dont subdivide too much, but dont have a lot of polygon in each Octan Cube.

Happy Coding,

LowRad

cadran? you mean octant?

Octrees are actually a tree with 8 nodes, the same way that a binary tree has two. nothing more than that. it is used for dividing the world though.

Thanks guys (and thanks for the desciption of how to do efficient culling though thats not what I expected I really enjoyed it.

In essencene then an octree would be as you said like a binary tree but each junction branches 8 times. From what I''ve read I would summise that this kind of ADT is useful for sorting large amounts of data in fewer steps that a binary tree as each junction reduces the search by (gulp) about 87.5%(?).

This seems similar to a way I once say radix sorting being performed, though if I recall correctly they used a tree that branched 256 times per junction (once for each ascii char).

Keeping in mind that I never went to uni and only started learning c++ at easter I think that to working out when to use certain data structures would require some algorithmic analysis to determine at what point(size wise) different ADT''s come in to their own. I bet a pretty graph would help too...