## Space partitioning with Octrees

Torpedo
Unregistered

Post: #1
I've read some articles about octrees, and they seem to be a solution good for object culling.
There is something I haven't yet understanded, and maybe someone can explain, or give me a link to a more detailed explanation.
Suppose there is an object on the scene that is far to big to fit on a smaller leaf of the octree.
How should this kind of objects be treated? Should they be divided in 2 or more objects, and then put each object on diferent leafs?
Sage
Posts: 1,482
Joined: 2002.09
Post: #2
Unless my understanding of octrees is off, you don't necessarily put an object in the leaves. Instead you place it in the smallest node that completely contains the object. A tree is hierarchal, and if you are only using the leaves, then you might as well be using an array. Also, that means that you have the tree structure to begin with, the tree should be built from the objects that you add to it.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Sage
Posts: 1,403
Joined: 2005.07
Post: #3
Put a reference to the object in both leaves.

Sir, e^iÏ€ + 1 = 0, hence God exists; reply!
Torpedo
Unregistered

Post: #4
If the leafs only contain intire objects then the objects shouldn't be too big. Is this correct?
Let's suppose I've created my set, that represents a landscape with moutains, etc. In the set, there are smaller objects like trees, rocks, etc.
When creating the octree, the root will have a reference to the set (because the octree root is the same size as the set) and the smaller objects (like trees) will be in some leaf childs. Is this correct?
If this is correct, then the set will be entirely sent to the pipeline for rendering. Wouldn't this impact performance?
Sage
Posts: 1,482
Joined: 2002.09
Post: #5
Torpedo Wrote:If the leafs only contain intire objects then the objects shouldn't be too big. Is this correct?

The point is that when an object overlaps a leaf's boundary you want to put up farther in the tree so that it's in the smallest single node that can contain the object. If you always have a full tree that is 5 levels deep, and always put object references in the leaves, you aren't effectively using the tree.

Torpedo Wrote:When creating the octree, the root will have a reference to the set (because the octree root is the same size as the set) and the smaller objects (like trees) will be in some leaf childs. Is this correct?
If this is correct, then the set will be entirely sent to the pipeline for rendering. Wouldn't this impact performance?

No, You determine the visibility of an entire node at once. If it isn't visible, all of it's subnodes also aren't visible.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Torpedo
Unregistered

Post: #6
Skorche Wrote:No, You determine the visibility of an entire node at once. If it isn't visible, all of it's subnodes also aren't visible.

Remember that the main set is placed on the Root node of the tree. The root node is always in the viewing frustum, so the main set is always entirely sent to the render pipeline. Correct?
Example:
(I'll put it in 2D for simplicity)

ROOT ->Main set
Child1 ->Some trees
Child2 ->Some rocks
Child3 & Child 4 ->No objects

Suppose the viewing frustum intersects only Child1. So I have to render the ROOT and CHILD 1 (ignoring Child 2).
If I don't break the main set in smaller pieces, I will always have to send it entirely to the pipeline for render.
Luminary
Posts: 5,139
Joined: 2002.04
Post: #7
so break the "set".
Sage
Posts: 1,482
Joined: 2002.09
Post: #8
Torpedo Wrote:Suppose the viewing frustum intersects only Child1. So I have to render the ROOT and CHILD 1 (ignoring Child 2).
If I don't break the main set in smaller pieces, I will always have to send it entirely to the pipeline for render.

I don't think you entirely grasp the point of space trees. The root node should only directly contain the objects that don't fit into it's children, it indirectly contains the objects in it's children.

So you draw the objects directly stored in the root node (not all the objects in all of its children!), determine which of it's children are visible and repeat.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.