I wrote a breakdown on Twitter that explains how Windshake accomplished this, and documented my whole process of how I got to my final efficient algorithm.
https://x.com/BoatbomberRBLX/status/1666597175407828994
In case y’all don’t have Twitter, I’ll copy paste it all here.
WindShake should animate only the objects in view. Here’s an illustrated breakdown on how I implemented sub-millisecond frustum culling in Roblox!
Before we start, we have to spatially partition our objects. To keep things fast, we don’t use any dynamic tree algos (like Octrees). We just chop the world into voxel cells and put objects in the box they occupy (which I’ve called a VectorMap, since it’s just a dictionary of vectors to object lists).
First, we get our camera’s view. We find the far plane using a configurable render distance, then we create a voxel-aligned bounding box around it. This gives us the cells that could possibly be in view, which we’ll narrow down next.
Narrowing it down can be expensive, so we try to use cheap methods first when we can.
We’ll start with a simple distance check. If a cell is farther than the far plane corners, we know it must be outside our frustum and we can discard it and move on.
Now we want to do a little better. We’ll check if the cell is beyond the far plane by converting it to the plane’s local space and seeing if there’s a negative Z component. This gives us the proper render distance we asked for.
Then we do the same thing on the other side. We check if the cell is behind the plane of the camera.
We can use trig to determine the vertical and horizontal angles of our view. We convert the direction to the cell into camera space, flatten one axis, convert it back to world, and check if the angle is outside the view angle of that axis. These two are the main checks!
At this point, we know all the cells that are in the camera’s view!
I didn’t show it because it makes it harder to understand the shapes, but we actually immediately discard cells that are empty so that by the end all we have are the cells with items in them!
We can now animate the objects in these cells.
Future plans: We’re currently checking each cell individually. It’s fast enough for now, but we could likely improve this by checking cells in big groups to discard bunches of cells at a time.
We’re back with more! I had new ideas and threw out basically everything.
Now, we calculate the oriented bounding box of the frustum to do cheap checks if cells intersect with it. This allows us to drop the distance check, the far plane check, and the near plane check!
Next we calculate the normal of the frustum’s top, bottom, left, and right (shown in those green lines) and discard if the cell is on the outside of any of the planes. We don’t need to check front or back since the OBB takes care of those!
By narrowing it down to just two techniques, it is both faster (yay) and easier to maintain (super yay!)
In the example from those images, the grid aligned bounding box had 240 cells to check. 117 of them were discarded by OBB, then another 46 by frustum normals. We are left with the 77 cells you see in blue! In practice, more are dropped for being empty.
~120 microseconds!
Thanks to MrChickenRocket for an idea! We know the frustum is convex, so there can’t be a gap in the cells. Therefore, when checking along the line we can skip the rest once we hit a cell that’s no longer inside! In this demo, we skipped 26% of the cells!
It occurred to me that once you find the first filled voxel, the subsequent voxels are sorted (filled on the left and empty on the right).
Instead of linearly searching for the last filled voxel, I wrote a binary search from that first point onward!