Do you occasionally struggle with slow performance of collision detection routines?
Do you sometimes wish there were a magical function you could call that would just… suddenly make everything fast, with no extra work needed?
Well, no longer! I have written a function that will optimize any node graph containing “into” collision nodes in such a way that collision detection will become orders of magnitude more efficient.
As an extra feature, it can also convert visible geometry into collision geometry for you, in case you were too lazy to figure out the pipeline for getting optimized collision geometry out of your modelling program.
Where to get it
How to use it
Import it, and then:
optimize_collisions(render, track_progress=True)
That’s it! It will automatically take all CollisionNodes with an “into” node, extract the solids, and reforge them into a massive new tree that you think has far too many nodes, but contains a secret kind of magic that actually makes it really really fast, for typical scenes.
The track_progress option shows a nice progress bar on the console in case it takes a while, but you can take it out if you don’t want it (or pass a custom function to integrate with your own loading bar). If it really takes long, you can of course just write_bam_file() the result as a kind of offline cache.
By default, it does not convert visible geometry into CollisionPolygons, but if you really want to do this, then you can use convert_geometry=True.
If you don’t care about preserving the names of CollisionNodes or their tags (like, if you don’t use this information in your collision handlers), then you can pass preserve_name=False or preserve_tags=False to strip this information for extra efficiency.
Also, if your game is strictly top-down with no verticality, use ignore_z=True for a possibly slightly more improved layout (quadtree instead of octree).
Limitations
This method works well if you have a large, static collision scene with many relatively small colliders. If you have huge colliders that span the entire scene, or a lot of overlapping colliders, that will make this method less efficient. If you have a ground plane or something like that, exclude it from the computation, or split it up into smaller polygons.
The method also assumes your “from” nodes are reasonably-sized and don’t encompass the entire scene. Don’t use this method if you have a massive “from” node that can collide with all solids at once.
If you wish to move the “into” CollisionNodes individually, this doesn’t work. Instead, organize all your static collision geometry under the same node, then call optimize_collisions on that node.
Currently, it uses 60-bit Morton codes, which limits the depth of the graph to 20 levels, but that’s enough for a quintillion “into” nodes to all have their own cells, so that should be quite enough for now!
How it works
If you just want to use it, you can stop reading now. But if you want to understand how it works, read on…
The general idea is to build an octree, so that instead of going through all the collision solids one by one, Panda’s hierarchical collision detection system can progressively narrow down on the parts of the scene that may intersect with a model, and only perform collision detection on the “into” solids that are actually close to the “from” collider in question. For a scene with 50k spread-out collision solids, this can reduce the number of actual tests done from (roughly) 50k to about 16. That’s a 3000x speed-up!
We build the tree by gathering all the collision solids, taking their center points, turning them into a Morton code, and sorting all the solids by this code, which ensures that the solids in any branch of the octree are in a contiguous range. Then we can just walk through the tree with some clever bit-shifting with the Morton codes and build up the collision node hierarchy, with some extra cleverness to not construct empty parts of the tree.
Technically, the result is not an octree, but an AABB tree. This is because the solids aren’t actually points, so in on octree they would have to be put in more than one cell. But since Panda’s node hierarchy already automatically calculates the AABB for everything, I still just assign the CollisionNode to one cell and have Panda make the AABB large enough to account for any overlap. (This is why it’s bad if you include huge solids that encompass the entire scene; the AABB will grow to very large proportions, negating the advantage of hierarchical testing.)
But my node count is massive now, how could this possibly be faster?
The resulting node count can be huge, such that calling render.ls() actually takes a while! But the renderer will skip them, because the root nodes are marked hidden. And the collision traverser only visits the nodes that have a chance of actually colliding with the “from” node based on the AABB test. Unless your “from” node is so huge that it will collide with a majority of the solids at once, only a few nodes will ever be visited at a time.
How is this different from what subdivideCollisions(8) does?
Well, it’s far more aggressive. This rips apart all your “into” CollisionNodes and rebuilds them in the most optimal manner, whereas subdivideCollisions only subdivides already existing CollisionNodes. That’s not useful if you have many individual CollisionNodes, only if you have single CollisionNodes containing many individual.
Can we add this to Panda?
Maybe! We could do something like this as part of the egg/gltf loader. I am also considering adding a similar feature directly to CollisionNode, so that CollisionNodes with many solids will automatically be optimized into an internal octree.
