Octrees?

News & General Discussion
1

I understand the nature of the octree in that you have a trunk and branches and the way it is searched there are less queries needed to get the result you need. Or something along those lines:) How do you make one in Unity? I am thinking that it is similar to a series of embedded if and else if statements. However, running that through my head I get some glitches in the performance and search abilities.

So the question is, how do you build octree type structures in Unity?

This isn’t really a scripting question but more a curiosity I have been wondering about for a while as I was thinking of building a voxel terrain editor.

Best
BTH

2

It should be more or less the same in Unity as it would be elsewhere (the basic data structure is essentially the same regardless of context).

As for the if-else statements, operations using an octree are generally recursive (in spirit, at least - they can be implemented iteratively as well).

Depending on your needs though, there might be other data structures that would be more appropriate.

3

OK… But how would you set up an octree without if/else if statements or case and break statements? Would it be done with nested arrays? Such as the first array points to the arrays of the first branches off the trunk. The second set of arrays is those branches pointing at the first fork off of the branches from the trunk, the third set of arrays being the branches coming off the trunk branches. If so then how would you know which branch off the trunk to take to eventually reach the leaf at the end of branching branches you are seeking?

TIA
BTH

4

There are many ways to store an octree. You can store it ‘flat’ in a single array, with nodes storing indices or references pointing to their children. Or you can have each node create and store its children directly.

Here’s an example of the latter method (untested C#):

class OctreeNode
{
    OctreeNode[] children
}

If the node has children, you’d create an array of 8 OctreeNode references, and assign it to ‘children’, i.e.:

children = new OctreeNode[8];

You’d then need to create and assign each child node individually.

As for queries, consider the simple query of finding the leaf node in which a given point lies. For any node, determining which child node the point falls in reduces to classifying the point with respect to the node’s three splitting planes. (Typically these planes are axis-aligned and bisect the node along each dimension.)

One method that’s often used is to use bitmasking to efficiently identify the child node corresponding to a query point, e.g.:

int index = 0;
if (p.x > splitX) {
    index |= 1;
}
if (p.y > splitY) {
    index |= 2;
}
if (p.z > splitZ) {
    index |= 4;
}

You then have to make sure the order of the child nodes in the array corresponds to the way in which the index is built. (In the above code sample, ‘index’ is the index of the child node in which ‘p’ lies.)

Finding the leaf node that contains the point is then a recursive process (although it can be implemented iteratively). A recursive version might look like this (all untested):

public OctreeNode FindLeaf(Vector3 p)
{
    if (children == null) {
        return this;
    }
    // ...bitmasking code shown above goes here...
    return children[index].FindLeaf(p);
}
5

Thanks Jesse. Took me a few reads to follow it but I get the gist now. If I was building a voxel terrain following similar practices I have read of I would be creating 16x16x16 blocks, which may incorporate a subscheme such as a further 16x16x16 inside each block. Each block would be a 0 = empty/air, 1 = solid/earth, and other containing both empty and solid another designation, perhaps -1. All nodes that are either 0 or 1 are ignored and the remaining nodes get shuffled to the renderer. These nodes would contain the polygons defining the surface of the terrain. I would store the blocks in an octree with each block having a Vector3 position coordinate and zip right by any blocks equal to 0 or 1. I imagine I could even avoid alot of iteration by having any parent block store an integer total for all children blocks and if this equals 0 then the entire block is discarded and the next block checked. If non-zero then its children are checked via the same scheme. Is my thinking correct here and is this an optimal way of processing such data?

Thx
BTH

6

That sounds like the right idea, generally speaking.

For a voxel environment like what it sounds like you’re talking about, any sort of ‘naive’ representation (e.g. a regular grid or a uniform-depth octree) will likely be unsuitable due to memory constraints. In order to make it work, various tricks of the type you describe will likely be needed (e.g. compression, hashing, hierarchical storage, etc.).

I know this has been discussed quite a bit, both here and on Unity Answers, and also at gamedev.net, so if you dig around a bit you might be able to find some references that go into a bit more detail on how it can be done.

7

I would probably store each detail depth as a 3-dimensional array?

8

I was thinking of storing it within the original blocks but just using an 8x8 and then a 4x4 to get 1/2 and 1/4 LOD. Since vertices would be on an edge or face these could be interpolated by skipping blocks and connecting the vertices in the unskipped blocks. What would your reason be for a 3 dimensional array? I understand hashtables and Builtin arrays are fast but you cannot make a 3 dimensional array from the Builtin array.(can you?) The primary goal of storing and accessing the data at acceptable realtime framerates is why octrees are used. It would seem that a 3 dimensional array would slow things down a bit. Correct me if my assumptions are off base here. I am assuming I have to iterate through the 3D array whilst with octree structures I can forego alot of iterating and just seek the data I need.

Best Regards
BTH

9

That’s the point of the octree… you don’t HAVE to create a 3-dimensional array to store every single cell.

The idea behind it is that you have a single master node (or voxel), which has the ability to subdivide itself into 8 children. Once it does, the master node basically becomes a relay for it’s children, passing new data onto them, and doing no work itself, since it’s visual space is now being taken care of by it’s 8 children.

Each child then, also has the potential to subdivide itself, so it works just like the top node, relaying information to it’s children.

So, each cell can be accessed by the master node, which will call it’s appropriate child, which in turn will call it’s own, and so on, until you reach the desired subdivision level.

Cheers

10

The point of octree is what this 8 child split actually causes. The depth of the tree storing the “path” to your cell in the world (leaf to which it is related in the end) is reduced by log_8 (a binary tree is log_2 in comparision) as each level in the tree stores 8 times more objects than the one above it so where a bin tree with height 4 stores 2^(4-1) elements at max, an octree can hold up to 8^(4-1) while still finding the relevant leaf in 3 steps at max.

This allows you to organize the world in a structured form while still being able to query for objects in a range extremely easy as you just find the topmost nodes whichs “area they span” is completely in the volume or crosses it for example. all that are completely in are within the area, for those nodes where their volume crossed you need to check the child(s) but thats a matter of a handfull of checks not X checks for each game object in the world and its even more performant because if you know that node X is fully in the volume, then all childs are automatically too so you do not need to process this subtree any further