Bad news on my end. It turns out that my ideas for finding the neighbors of the octree is not entirely accurate. Last week I also solely focused on finding the neighbors that are of equal or larger sizes of the current octree and I didn't get the chance to trim those into their smaller children. So this week is about fixing the problems with my algorithm and getting the smallest possible neighbor.
Let's start with what was wrong. My idea worked great at the size of octree that I was testing with, but it quickly broke down with more recursive calls. So in getting the larger neighbors I would get extra neighbors, such as my parent's neighbors, and it's parent's neighbors as so on. So I need a way to know when the neighbor I'm looking at is a neighbor to the original octree and not a neighbor to it's ancestor. The simplest way to do this without spending too much time changing everything I've already done is by checking the distance between the octrees. Each octree knows it's exact size and position, so we know that if the distance between the base octree and it's potential neighbor is less than their added sizes then they are adjacent. By adding this small distance math we can cull any excess neighbors. Luckily, the work I've already done makes this distance check not as costly as it would normally be since I'm not comparing each octree with each other one. Instead I have a fairly small list of neighbors and only some of them are incorrect and this distance check fixes that.
1 - (a) Blue is octree to octree and purple shows the bound radius, (b) Purple shows the bounds added together, (c) The purple bounds forms a box, (d) The absolute value of the blue vector fits inside the box meaning they are neighbors
I'm going to get more into detail about checking the distance since there are some small quirks that I want to mention. If we just added the bounds of the octrees together to form a max distance we would get a potentially incorrect size. This is because the bounds effectively point to the corner of the octree box, which is the largest possible distance. If we add them together we get the largest possible distance that the octree could be from each other, but this might give us false positives when the octree are actually along the same axis. Instead we can do something similar to a box collision. We compare each individual component with the corresponding one to make sure that the maximal distance encapsulates totally encapsulates the distance between octree. To summarize, adding the bounds of each octree gives us a theoretical box that represents legal neighbor distances. Then we get the distance between the two octrees. This in turn forms a point in space which we want to make sure is within inside of the theoretical bounds box. This takes gives us an accurate idea of if the two octree are actually adjacent or not.
Now we still need to turn the large neighbors into their children. This is actually a fairly simple process. If the large neighbor has children we do the same distance check I described before and cull the children that fail. Then we keep doing this on those children and it's children, until we're left with the smallest possible adjacent children. The final product works really well. No bugs this time.
1 - Octree that's in the ground with it's neighbors. Notice the smaller cubes to the left and right
2 - Much larger octree with multiple neighbors of varying sizes
Now that the octree has neighbors we can actually prune the tree looking for the nearest node. This is a fairly simple act of finding which octree the the target point would be contained by, getting all of it's neighbors, and then finding the nearest node within those neighbors and the octree. There is one problem that I'm currently running into however; what happens when the octree with the target point and all of it's neighbors contain no nodes. This would mean that there is no nearest node, which isn't exactly true. I do have a possible workaround though. I can get an answer if I then iterate through all the neighbors of the parent octree's parent. Then I repeat the process until hopefully I find a valid node.
With that my feature detection/ octree side-quest comes to a close. I went down this path because I needed to know for certain where the limbs could place their end effectors. So I implemented a custom navigation mesh which generates nodes at areas that can be walked on. Now the rig is able to find and move the limbs to the nearest node. However this has performance penalties which is why I had to use an octree. The octree stops me from having to iterate through each node to find the nearest one which is much faster. In fact, I have run some tests to see the kind's of saving I get with the octree compared to iterating through each node and it's pretty substantial. With 954 nodes in the scene I iterated through an average of 27 nodes and with 2435 nodes the average was 221. The octree is pretty worth it already and the saving can only get better the larger the NavMesh is. Hopefully I won't need to revisit this code in the future, since the navmesh and octree are both functional and optimized to the level I need.
Finally, in regards to implementation this week I want to add something to the walk cycle code to make it look cleaner and smoother. I want to mimic a walk cycle by forcing limbs to rise and fall on their way to they destination. I can do this by changing how my limbs decide and move to their target points. Right now the limb is told to move to it's destination and the IK system slowly moves itself to it. Instead I propose that I have the IK system follow a specific path and have that be the motion I want the legs to follow. This way, I can control how a step looks and the IK handles how to orient the limbs.
To get this done I just need to interpolate between the the last known step location and the new step location I want to move to. Then, over a set time, the limbs target can be update to move along this interpolated path. This has the added benefit of prevent limbs from taking weird paths to the target that look strange. More importantly, I can force the limbs to rise and fall to mimic how actual walking works. Cosine is very useful here. I can get the arc I want by converting my interpolation percentage into radians in order to sync up the arc with the interpolation. This leaves me with a much more natural looking walk.
3 - Example of the character walking. Limbs actually lift this their legs instead of sliding towards their destination. The red lines show the interpolation path.
This week I'm also spending some time thinking about a huge problem that I'll need to tackle; how does the limb react to collisions? So far, the research I've found all implement their own specific IK algorithms which means that I won't be able to simple use their techniques. I'll have to spend more time testing out implementations to see what works.