Piko3D

Introduction

Space partitioning is commonly used in 3D games and game engines. It is used to efficiently choose the objects to draw or collide, and so on. Many options are available, differing in both complexity and efficiency. Examples of space partitioning include: KD-Trees, Octrees, Grid cell partitioning, Icoseptrees and so on.

This tutorial is not a definitive guide to implementing the ultimate Octree, but it just describes our implementation of an Octree; we decided to share it with you because, well, we think it’s just awesome 😉
For those of you who already know what space partitioning is, and what octrees are: skip the following two paragraphs, move along people, nothing to see here 😉

Space partitioning

Space partitioning is, simply put, subdividing your game world into smaller parts, with the purpose of optimizing queries on your game world. For instance, say you want to render a scene, with e.g. a heightmap, trees, lots of bushes, some rocks, some houses full of furniture etcetera. Usually not the entire scene is in view, so all objects that are outside your view do not need to be drawn. This can greatly speed up the rendering process.

In order to be able to determine which objects are in view, we have to know whether or not they intersect with our view “Volume” – the space that is visible to us. For that we give our camera a bounding volume which describes this space. As it is mathematically rather expensive to test if an arbitrary object is inside this volume, we also define a bounding volume for our objects. This volume will be a rough approximation of the object, like a bounding sphere for instance. We can determine if the object is in view, by calculating if the bounding volume of this object intersects with the bounding volume of our camera.

In Piko3D, we get data from our scene using a simple query object. If we pass the bounding volume of the camera to this query object, we can do a simple for loop to decide which objects are in view:

1
2
3
4
5
6
void Scene::query(SceneQuery& query) {

    for (int i = 0; i < mObjects.count(); ++i){

        if(query.boundingVolume->intersects(mObjects[i]->boundingVolume))

            query.objects.add(mObjects[i]);

    }

}

This works well on smaller scenes (say, < 1000 objects), but the larger the world, the more checks need to be done. When talking about checking collisions, a problem arises with even a relatively small amount of objects. This is demonstrated with the following code snippet:

1
2
3
4
5
6
void Scene::collide() {

    for (int i = 0; i < mObjects.count() - 1; ++i)

        for (int j = i + 1; j < mObjects.count(); ++j)

            if(mObjects[i].boundingVolume->intersects(mObjects[j]->boundingVolume))

                // do physics collisions ....

}

This sums up to (n(n – 1)) / 2 checks, where n is the number of objects. With 1000 objects, this results in almost half a million checks! Great performance gains can be achieved by grouping objects that are close to each other into a separate volume (which we call partition) which is a bounding volume that completely contains the given objects. If two partitions do not collide, the separate objects inside one partition do not have to be tested against the objects inside the other; so if a partition contains 100 objects, and it does not collide with another partition with 100 objects, almost 5000 checks are saved. This shows that good space partitioning is essential to the performance of modern games.

Octrees

The structure we chose to use is called an Octree. An Octree works with splitting the world (or ‘root partition’) recursively in 8 partitions (or ‘children’ of a partition): one for each corner of the world (lower left front, lower left back, lower right front… etc, until upper right back). The partition containing the children is called the ‘parent’ partition for each child. Each corner can again be repeatedly subdivided into 8 children. Objects are placed as ‘deep as possible’: e.g. if an object fits in one of the children of a partition, it will be placed in the child (or even one of the child’s children). An example is shown below; for clarity a quadtree is shown, which is the 2D equivalent of an octree. To convert this example to an octree, simply add a third dimension and split it the same way.

So, if we want to take the collisions of one of the objects in the upper-right quadrant, we can completely
ignore the other three quadrants, ignoring all objects contained therein.

Whenever an object moves, its place in the octree needs to be recalculated, so that the tree is always up to date. Instead of checking the complete tree, we only check whether an object still fits in the current partition; if it does, check whether it fits in one of its children. If it doesn’t, check the current partition’s parent. Repeat until the object doesn’t fit in any child.

Splitting and merging

Okay, we now have an octree. But when do we split a partition? We could simply split the octree a predefined number of times, but determining the number of splits is hard. Too many splits means that there is lots of overhead, even when there are not many objects in a certain spot. Too little splits means that too many objects are checked for culling or for collision.

Our solution was as follows: we define a maximum number of objects per partition (definable by the user, ofcourse). Whenever more objects than this are in one single partition that has not yet been split (we check this whenever an object is added to a partition, either by an add or a move), we decide to split the partition in eight partitions. This way, the overhead is distributed where it is needed: when lots of objects are close together, there will be more partitions there to distribute the objects. At other locations where the objects are less dense, there will be less partitions.

Then the next problem arises (when is it ever going to stop ?!), namely what if we have a group of objects that are moving through space? Partitions that used to have a lot of objects may unnecessarily be left split. For this, we define a minimum number of objects per partition. Whenever an object is removed from a partition, we check whether this partition including its children contain less than that threshold. If this is true, this same check is recursively done for the partition’s parent. The uppermost partition that is below the threshold is merged; which means that all objects from its entire subtree are added, and all its children are removed from the tree. Yay, problem solved! 😀

Growing and shrinking

We now have a octree which dynamically splits and merges whenever the need arises. All is well! But … what if we have lots of objects that are outside the root space (for instance, if we have a large fleet of spaceships that move at high speed outside the solar system)? All objects outside the root partition are not grouped, and are therefore are checked against each other and all objects contained by the root partition. For a small amount of objects outside the root space, this is not a big deal; however this can get ugly (and by ugly, I mean slow) quickly.

We could simply recalculate the bounding volume of all objects, create a root partition (and possibly children) accordingly, and move all objects from the old root partition to the new partition, so we have a new root. But, to keep in the spirit of Piko, where all objects are themselves responsible for actions that affect them (in stead of ‘God’ objects that coordinate the whole thing), we wanted a different approach where only local changes were needed to grow the tree.

We solved this case by checking the number of objects outside of the root partition whenever an object is added to it. If this is larger than a certain threshold, we determine in which quadrant (or actually octant 😉 ) outside the root space are the most objects. Second, we create a partition, where its space is exactly at the position as the parent of the original root space would be, if it had a parent. We then split this parent in eight, and replace the child that exactly overlaps the original root, with this original root. This parent is now our new root!

Of course, we don’t want our root space to grow indefinitely. So, it should be possible to shrink the root. We do this by determining the child partition of the root with the largest number of objects. If the number of objects outside this partition is lower than a certain threshold, we remove all partitions except this one. And presto: we have a shrinking octree!

Overlapping spaces

The previous sections describe how our dynamic octree works. But what happens with the two objects on the right in between two spaces? They do not fit in any of the children, so they are placed in the parent space. This means that partitions and their containing objects can not be quickly discarded for these objects. This can be a big problem if we e.g. have a dense forest with a lot of trees, where lots of trees reside in between the spaces. If a character is walking through the forest (and ofcourse we don’t want to walk through trees 😉 ), all trees in the root partition will be checked for collision.

A solution to this problem is to use an Icoseptree, that subdivides each partition in 27(!) children (o_O). It is basically the same as an octree, but for every two adjacent children there is a partition in between them for objects that intersect them both, plus one partition in the center for objects that intersect more than two spaces. Well, we made an implementation of it in a different project a while back, and it works perfectly. However, us Pikoders really like simplicity, and the idea and implementation is way too complex for us 😉

So, we used a different approach: what if we just enlarged all children to overlap just a little bit, so an object that used to intersect two adjacent children now probably fit in one of them (unless they are relatively big; which means that they should be put in the root partition anyway). We chose to enlarge partitions with a user-defined percentage. This approach kept the implementation simple, while addressing most – if not all – of the problems.

The final result

What better way to show what we’ve got than with a movie! (You may have already seen this movie in the newspost) If you pay attention, you will notice the growing of the partitions, the root, and the overlapping of spaces. You may also notice that there is a lot of splitting and merging going on; this is mainly due to the unique case of having only moving space ships as objects, and the fact that we set the minimum and maximum number of objects close to eachother for testing the worst-case scenario. It also adds to the demo-effect. 😉

Octree Scene Graph Demo

Cheers!

Paramike