Time is coming to an end with GNodeFactory and I have had an immense pleasure being a part of it. As I am writing this a fair few additions have been made to the project. In order to organize this into a succinct post, listing out each item will help:
GNodeFactoryF Allocation Strategy being updated (again..)
The update to the allocation strategy this time went from having pools of data that could theoretically be endless to having a fixed maximum size pool. This would mean that when the user allocates nodes, they are either filling up existing pools, or if needed having more pools being made at a fixed size and having the handles returned. Handles still work with cross-pool relationships which was exciting to not have to go track and fix more bugs.
Currently the node count per allocated pool is 4096 which should be modified as testing happens finding out the best "bang for buck" allocation size for the system. While users typically shouldn't need to allocate a "large" number of nodes (i.e. one million nodes), GNodeFactory should still be able to maintain performance at those large node counts, within reason.
FindSphereNodes being implemented, then multithreaded
Lari and I discussed that at least one spatial query method would be implemented before my time with Gateware was up. Looking at the workload amongst my program requirements I initially wanted to leave spatial query methods to a future developer. Since Lari wouldn't consider GnodeFactory "completed" until at least one was implemented, FindSphereNodes is now here.
Initially I had waited to do multithreading until the entire library was created, then I would go back and multithread where reasonable. In this case since we need to look down all the pools we can tell GConcurrent to run some work for each pool to find the node in parallel. The idea is that if multiple threads are working to find the node within their pool, the time spent overall would be less if it was linear. Functionality was tested using a separate solar systems simulation. Below is that simulation where I would press `1` to toggle FindSphereNodes within 100m of the camera.
ResolveHierarchy being multithreaded
One of the largest features within GNodeFactory is the ability to resolve the hierarchies transforms. In order to do this, every pool will be tested to find out which nodes are dirty. Then based on those nodes, run work in parallel to recompute them. Since node roots don't overlap, every node has exactly one parent. This means you can follow a parent from anywhere resulting in a single root. Two roots can never share a node, letting each root get its own thread with no locking between them.
The write lock is taken once at the top and the workers run under it without ever locking again, which also fixed an earlier version that deadlocked itself by re-locking on every level of the recursion. ResolveSubHierarchy stays single threaded since the handles a user passes in can overlap, and two threads resolving overlapping subtrees would trip over each other.
FindAll Child, Sibling, and Parent Nodes being multithreaded
These three take a list of nodes to search from, so instead of splitting the work up by pool, I split it up by search. Each search is on its own anyway, so each one gets its own task and its own list to write results into.
Once they all finish, those lists get copied into the real output array in order. That order matters because the output is one flat array with a count for each search, and a thread has no way to know where its results go until the searches before it are done. Copying them in afterwards means everything ends up exactly where it did before.
That said, this one probably wasn't worth it. It only helps if you're searching from a lot of nodes at once, and most of the time you're only searching from one, so you get a single task and pay for the threading without getting anything back. It does keep the Find methods consistent with each other, at least.
Find Capsule, Frustrum, AABB, and OBB Nodes
Once FindSphereNodes was done, the rest were easy. Every node already has a sphere around it, which is just the collider radius sitting wherever the node resolved to. So all four of these are really asking the same thing, does this sphere touch that shape? GCollision already had those tests written, so each method ended up being the same scan as the sphere one with a single line swapped out in the middle.
AABB needed its min and max corners turned into a center and extent first, since that's the form the test wants. The frustum is the odd one out, because it isn't one shape, it's six planes. A node is outside if its sphere sits fully behind any one of them, so it checks all six and stops at the first miss. That assumes the planes point inward, which is normal, but worth knowing if a frustum ever comes from somewhere unexpected.
As for everything else, I don't really have any major updates towards GNodeFactoryF. GNodeFactoryD however will be getting made soon since it will be mostly a copy and paste from the float implementation. Since that covers most of the past two weeks, I hope everyone who gets the chance to use GNodeFactory can create some awesome projects with it!
