#### Archived

This topic is now archived and is closed to further replies.

# Octree questions

This topic is 6907 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I think there is an article on www.gamasutra.com that has something about octrees in them. I cant remember the name of the article though, i think it is to do with culling or occlusion.

##### Share on other sites
The whole point of any tree structure is to throw out a large amount of irrelevant data.

For example, depending on your camera position and orientation, a BSP Tree could concievably throw out HALF of your entire world on the top level and do nothing with it, because it's off screen. It could then concievably throw out half of the remaining half, and continues until it's left with the stuff that is onscreen and needs processing.

An Octree can concievably throw out 7/8 of a world at a time. The best way to envision an Octree is to take 8 building blocks and arrange them into a bigger cube. You have four blocks sitting on the ground and another four sitting on top. Now imagine each of these blocks is devided into eights the same way, and each of those divisions is broken up until you reach some finite minimum oct size.

You can use the tree(or any tree structure) to do alot of stuff. As already mentioned above, only draw the Octs that are in front of the camera and not too far away. You can put objects in the octs and only do collision detection with objects in the same oct instead of doing a distance test against every single item against every other one.

Octrees are only really practical if you're working in a truely 3-D environment. If your level is 500 feet wide by 500 feet long by only eight feet high, an octree is not going to be effective. You're basically going to have all kinds of nodes from eight feet high to 500 feet that contain absolutely nothing but still need to be eliminated when you traverse the tree. If you've got a game set in space, you can go in any direction so an Octree makes sense.

There are also quadtrees, which just devide a two-dimentional area into quadrants. These work pretty good if jumping onto a box is the only height-type issue you have to deal with. I prefer them to BSP trees. In C++, they're alot less abstract.

I think the reason BSP trees took such a hold was because they were based on Binary Trees(which already had all kinds of sorting/searching algos worked out) and were probably easier to deal with in straight C (where any one of the above options can get to look pretty abstract and ugly.) You can still find alot more pre-tested algo's for a BSP tree, though.

##### Share on other sites
Check out "Harmless Algorithms" on http://www.flipcode.com. There's a document called "Scene Traversal Algorithms". It covers octrees and compares them with BSP trees / Portals / KD-trees ...

Kevin

##### Share on other sites
It seems there is very little information online about implementing Octrees in a 3d engine.

So, what exactly are Octrees used for?

Just as a data structure for your worlds?

Can they be used for culling? Polygon sorting? Collision detection? Anything?

Would it be possible/practical to have a combination of octrees and BSP trees?

Are there any articles online about octrees?
(I tried flipcode, I only found about one article, and a short one at that)

1. 1
2. 2
Rutin
22
3. 3
4. 4
5. 5

• 16
• 14
• 9
• 9
• 9
• ### Forum Statistics

• Total Topics
632928
• Total Posts
3009264
• ### Who's Online (See full list)

There are no registered users currently online

×