2
\$\begingroup\$

I'm studying about Octrees since I've read they're used to organize my elements in space, but I couldn't find any practical example so I'm kinda lost as to their use.

From what I could understand, I'll divide my "space" in 8 cubes, and each cube will divide it's own space in another 8 cubes and so on until my defined "depth" is reached. This is what I could understand from octrees, so now about their uses:

  1. Are they done so the check of each cube's with the camera frustum is easier to compute?
  2. If I have a open world scenario, do I put all the vertexes in it? And related:
  3. How often do they get updated? Everytime I insert a new game element, don't I have to re-do all the calculations for the current node and it's subnodes?

If you can share any resource on BSPs/Octrees and their practical usages (not just the concept, which I've been reading a lot), please share!

\$\endgroup\$
3
\$\begingroup\$
  1. The point is that once you cull one octree node, you can stop culling and discard all of its children therein. Consider a binary search for example. Once you know that your key isn't in one part of the array, you can stop searching that part completely. The check itself isn't easier to compute, it just decreases the number of calls you may have to make (as long as you don't use silly depths or in other words use too many nodes for too few objects)

  2. I'm not sure what you mean by vertexes. I'm assuming you mean models/entities, in which case, the answer is maybe. In the end you might have multiple systems of subdividing space and multiple culling systems in order to maximise performance. Generally though, if we're talking about say plain scene objects (e.g renderable vehicle, player characters), the answer is yes. It must be stressed though, you won't be adding individual vertexes, you'll be adding the bounding box belonging to the entity that contains the vertexes. You will still end up ultimately culling the specific entity you add to the tree if it ends up in the visible candidate list, it just allows you to say, if you are at one end of the map, eliminate dozens or even hundreds of entities with a single cull check.

  3. It depends on what you mean by 'update'. If you mean 'cull', thereby updating the list of visible candidates (objects that may be visible) then yes, otherwise you might run into a situation where an object that should be on the screen isn't rendered.

    When you refer to calculations, what are you referring to? The insertion of a new element will generally involve recursion, beginning with your root node, adding it to nodes that contain it. (strictly speaking this can be a bit more complex depending on how you produce your visible list - you don't want duplicates) The only calculations you will have to perform (not may) will be the bounding box intersection test with each node you recurse for.

Here is some basic pseudo-code (just to give you an idea, not necessarily accurate)

void RecurseAddBoundsToOctree(TBoundingBox boundsToAdd, TOctreeNode node)
{
    if node == NULL
        return

    for each child
        RecurseOctree(currentChild); 

    //Note: Above we may want to prevent multiple children from containing the
    //same bounding box (you could return a boolean to indicate whether it was added)

    if BoundingBoxIntersect(boundsToAdd, node.BoundingBox)
        node.AddBoundingBox(boundsToAdd)
} 
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The examples I found used to separate by vertexes, so I'd sent pointers to array of vertexes that will be contained in the Cube. I thought you had to get the max XYZ values from each cube to get it's "center" position and boundaries for easier collision checking. But if it's just about entities then it's not as small as I thought I had to go, and means I can divide the area of my world in sections. I'm still unsure about #2 though, using Skyrim or WoW as example, does that means the entire game is in memory during play, but only a portion of it is shown? \$\endgroup\$ – Danicco Aug 8 '13 at 0:22
  • \$\begingroup\$ No. You don't have to have all the portions of your octree split to leaf nodes all the time, that's part of why they're useful in the first place. Based on both distance AND the number of entities within a node, nodes will be split, ergo the tree will usually not be static. Let's say you have a huge world but coincidentally the player never leaves one particular child node of the root. The other children could be completely empty and loading (and entity insertion) might only occur when you get within x distance of a particular node. \$\endgroup\$ – parar Aug 8 '13 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.