#### Archived

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

# Octree

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

## Recommended Posts

Hi Can someone plz explain to me whats an Octree? Thanks

##### Share on other sites

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

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 on other sites
I see.
So its a way to show Geomatry?
Or what he is usualy used for?

##### 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 on other sites
Ok i got it..thanks

##### Share on other sites
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).