Week 6 - Pruning the Octree — Guilain Huyghues-Despointes

Last week I was able to set up the basics for an octree. However its currently very bare-bones an not fully integrated with the IK System. Right now the only thing the octree does is store the nodes inside of itself and then spawn new child octrees if it's capacity is reached. Now we need to be able to traverse the octree and get the closest node to any specified location. In theory this is fairly simple. You just need to get the octree that that location would be located inside and then iterate to find the closest node inside that octree. This gets tricky, however, when you consider that nodes and the target location can be close to the edges of the octree. It's entirely possible that a node in a neighboring octree is closer to the target location than any node within the octree that holds the target point. So to search for the nearest node, octrees need to know their neighbors. By knowing the neighbors we can iterate through all the nodes among these octrees and get the true closest node.

Calculating an octree's neighbors is a surprisingly difficult challenge and a potentially tedious one, especially in 3D. Depending on where the leaf octree and its parents are (as in NE, NE) affects which directions of the neighbors we want. There are basically 8 x 8 = 64 possible permutations with unique behavior to potentially code, but I'll explain later how I figured out a way to avoid rewriting similar code. The whole process is done in two rough phases. The first gets all the neighbors of the same size/depth and any larger ones and the second is refining the larger neighbors to only grab the smaller parts.

For this week I'm focusing on getting the neighbors of the same size and larger, since developing a more general way to do the standard algorithm is quite taxing. First I should explain how the algorithm works. To start it takes the direction of the neighbors as input, you pass in North and get all the northern neighbors and you need to call the method multiple times to get the whole list. To makes things simpler to explain I'm going to go over the algorithm for getting the northern parents only.

If I'm a SW or SE child return the respective NW or NE sibling, otherwise it means I'm a northern child and need to go up the tree
Call the same method on the parent to get it's northern neighbor
- This gives us a neighbor that is larger than ourselves
If the parents northern neighbor has no children we can just return it, otherwise we want to go deeper and get neighbors of a smaller size
- The depth only goes to the same depth as the starting octree
If the parent has northern neighbors then depending on if I'm a NW or NE child, we get the SW or SE child of the parents northern neighbor
With this we have the the northern neighbor of equal of greater size

The above algorithm has many problems. For one, it requires rewriting very similar code 8 times in 2 dimensions and 24 times int 3 dimensions. Yeah I'm not going to do that. In a similar vein to the first, I want to be get all the neighbors and not just those in a single direction. The general algorithm is basically unchanged but there are some improvements to stop it from being one huge switch. My first goal is to get just the larger neighbors and then I can worry about refining them into equal size octree later.. My version goes as follows:

Get all your parents equal or larger neighbors (recursive call)
Filter your siblings and add any legal ones
- Siblings are legal if they are in the same direction as the starting octrees location.
- So if the original octree is in the NE corner then any recursive calls will only grab the siblings in that direction (I'll explain how I did that a little later)
That gives us all all of the largest possible neighbors we have

I think I've come up with a pretty clever way to get siblings in a certain direction. This hypothetically could be a large switch statement, but that's 64 permutations and again would be terrible, but I can use math in order to figure this out. Luckily, from before I have a hashmap of Direction to FVector directional offsets. So I can easily get the vector form of any direction. By making a second hashmap of FIntVector (vectors of ints) to Directions, I can easily swap between the two. Finally, for each combination of current location in the octree and direction I want the neighbors of I want a list of legal directions to grab and add as my neighbors. I'm doing this with a third hashmap of Pairs of direction to an array of direction. For example, a NE octree wanting NE neighbors, will only allow the NW, NE, and SE siblings as legal. With this hashmap we can easily decide if a sibling makes a legal neighbor for the original octree.

The difficulty is now populating this huge hashmap of pairs of directions to directions. Like I said above that's 64 different combinations of directions and there's no good way of filling those in by hand. Luckily, there's a way to populate this hashmap mathematically using the ability to swap back and forth between directions and their vectors. By knowing the location offset of the current octree I can add the offset of the direction I want to go and get a possible neighbor. For example, SW is represented by (-1, -1) and NE by (1, 1). If my starting octree is in the NR corner my direction is now (1, 1). If eventually my parent is in the SW corner, I know I want to move in the NE direction. So by adding the location and the direction * 2 (this is done to skip the 0s) I get the NE family member at (1, 1) which is a legal neighbor to the original octree. But this only gives one possible neighbor, however, if we deconstruct the direction vector into each possible permutation then we get all the legal neighbors. So in out above example, we deconstruct NE, or (1, 1), into (0, 1), (1, 0), and (1, 1). Adding each of these to the locations and converting it back into directions gives us NW, NE, and SE, which are all legal neighbors. I can initialize the legal neighbor hashmap with all these calculations and get legal neighbors.

Now we are able to get all of our starting octree largest possible neighbors, but we still want to be able to thin these out and get at least neighbors of the same size. We already call the main neighbor function recursively. Right now once we have the largest neighbors we just pass them down and store them, but what if we refined them with each step down. Whenever we go down a level we take our current large neighbors and try to break them up into the smaller legal neighbors. Lets take a look at our updated algorithm:

Get all your parents equal or larger neighbors (recursive call)
Refine the parents larger neighbors
- If they have no children don't do anything
- If they have children add the legal ones (explained further down)
Filter your siblings and add any legal ones
- Siblings are legal if they are in the same direction as the starting octrees location.
- So if the original octree is in the NE corner then any recursive calls will only grab the siblings in that direction (I'll explain how I did that a little later)
That gives us all all of the largest possible neighbors we have

The main difference from the earlier algorithm is the step where we refine the parents neighbors. This process is similar to the part where we determine legal siblings based on the direction we're trying to grab. First we want the location parent of the octree we're currently in and the location of the parent's neighbor we are currently looking at. To make things easier, our parent will be SW and the neighbor is NW in this example. We convert that to a coordinate so (-1, -1) and (-1, 1). We calculate the vector from the neighbor to the parent (0, -2). Then we use this direction to calculate the neighbors children we think are legal. The 0 means that we want both children along the X axis, and the -2 means we only want the southern children. So whenever I see a zero I replace the possibilities with -1, and 1 and I clamp everything between -1, 1. So we end up with the offsets of (-1, -1) and (1, -1) which we convert into SW and SE. So now we have neighbors the same size as the starting octree. This works for the most part, but I still need to make sure it works properly with multiple refining stages.

4 - Corner with neighbors of different elevation

5 - Upper corner with neighbors, currently doesn't get octrees smaller than itself

With each octree knowing their neighbors, we can finally accurately find the nearest node. Now to find the nearest node to a target location we find the octree that would contain the target location and then iterate through each of that octree's nodes and the nodes of each of it's neighbors. This is great because instead of iterating through all the nodes in the scene we limit it to a very hard cap.