Basically, I made 3 points, one for location, one for location + facing, or for location + up vector, for each keyframe, then did Catmull-Rom interpolation on each point to regenerate the camera position & orientation. It worked well for my older camera paths, but the new ones I just made didn't work great, so I switched to Quaternion interpolation of rotation, and use the Catmull-Rom as before for position.
I've been working on a new spatial hierarchy - man, I've written so many of these, both for use in Ancient Galaxy, and other projects. Ancient Galaxy uses a BVH for world tiles, each of which contains a per-material AABB triangle tree. Dynamic objects also live inside BVH trees. To move objects, I delete them from the BVH, then re-insert. No rebalancing happens during these steps, that is instead done per-frame.
The new hierarchy I've been developing is something I call a BoxTree. It is a binary tree of AABox Nodes, each of which can have zero or two children. Nodes with zero children can have up to 8 Items in them, each with a AABox from the user, and a void* user data pointer. Items do not live higher in the tree than the leaf nodes.
Each non-leaf node also stores an Axis value ( 0,1 or 2 representing x,y or z ), a Partition value, which is a float that measures along this axis, and the UserData pointer last used to partition the node.
In some ways it is like a KD tree in the sense that you are sort of storing a split plane, but in other ways it is a balanced binary tree in the sense that when you are splitting nodes with 8 items, you do a median split, so that 4 items always go down the left child and 4 go down the right.
One bug with it I fixed today was with the case where 2 items were exactly on the partition value ( the axis-aligned split plane ), with one being the 4th item and the other the 5th. These two items would go down the left & right sides respectively, but later on when searching for one of these items, I didn't want to have to search both left & right subtrees.
The solution was to also store the last user data pointer used in the partition. This way, an item always goes down a particular way, left or right, never both, because you can use the user data pointer to break ties when the partition values are the same. This pointer only has to be remembered when a split happens - it doesn't even need to be changed if that item gets deleted, the pointer value itself is the tiebreaker, so it remains valid even if it doesn't point to anything.
With that change, my unit tests are passing despite adding & removing several hundred boxes at random.
Just realized that the tree doesn't handle duplicate items nicely - if you add > 1 item with the same userdata pointer, you will find one of them, but maybe not the one you expected. I suppose I will add two new methods, one that adds an item but checks for dupes and replaces the dupe with the new value and another one that fails on adding a dupe.
Next is to test the cases where I have many duplicate boxes, and ensure the splitting logic is robust.
Download Ancient Galaxy Here
