Archived

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

Octree

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Simple answer:

It''s a tree where each node has 8 children.

Slightly longer answer:

An octree is often used to divide up space, to be used for hierarchical culling or querying for 3D graphics.

Each node in the tree is given a (axis-aligned) bounding box. The children for the box are arranged like this:


-----------
| a | b |
| | |
-----------
| c | d |
| | |
-----------

/----/----/
/ e / f /|
/----/----/ |
/ g / h /| /
/----/----/ |/|
| | | /b|
| | |/| /
----------/ |/
| c | d | /
| | |/
----------/


(imagine the bottom figure is a cube, but it doesn''t really have to be a cube, the top figure shows the layout of the bottom four children)

The children are here labelled a,b,c,d,e,f,g,h and each can either contain 8 more nodes (arranged in the same way), or be a leaf.

Depending on how the tree is used, geometry could be stored in all the nodes, or just the leafs or whatever.

Share this post


Link to post
Share on other sites
An octree is usually used in a large 3D world. This way, you can cull parts of the world and not draw them. Instead of drawing every single poly in the world, you can draw only the ones that the player sees. This is done by checking which nodes in the octree are in the frustum and which are not.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I''m using an octree to speed the calculation of the gravitational forces between hundreds of ''stars'' that are all mutually interacting. The simple method of doing this is to loop through each star and add the gravitational force due to all other stars. This is O(n^2).

Using the Octree, one can group stars that are far away from the current start together. Their combined forces are approximated as the force of a single star located at their combined centre of mass, with mass equal to the sum of the masses of the far away stars. This is O(n log n).

Share this post


Link to post
Share on other sites