The code that culls terrain chunks was using a 3D bounding box vs camera frustum test for each terrain chunk, which was incredibly slow. On the XBOX 360 this was taking about 4ms for ~200 intersection tests. At 60FPS you only get 16ms per frame to do everything, so terrain culling was taking up 25% of the CPU time.
I’ve refined the culling method to test blocks against an arbitrary polygon in 2D space.
This method takes 0.5ms using a 6 vertex culling polygon — 8x faster than testing the camera frustum against terrain chunk bounding boxes. This in turn gives me enough room on the CPU to potentially quadruple the number of terrain chunks, and increase the number of lights, and the terrain detail.
This allows me to use the trapezoid of the camera frustum projected onto the ground plane to cull the terrain, like so:
Image courtesy of this forum post.
This trapezoid however, is not enough. The shape needed is a projection of the entire frustum onto the terrain. I thought that wouldn’t be too hard, but it took ~12 hours to complete.
My method for finding the culling polygon desired, is to find the trapezoid above by intersecting the frustum rays against the terrain. Then project the near plane onto the terrain plane (good enough for our purposes).
Then take the resulting projected points and find the convex hull that surrounds them.
Although this took much longer than expected to implement, along the way I’ve implemented ray-terrain intersection testing, convex hull from point cloud creation, simple polygon point list winding (i.e. take a convex hull and produce the list of vertices in clockwise winding order), and point in polygon testing.
These tools will come in handy very soon, as monsters and more physics are introduced into the game. For example, I can now compute a bounding polygon for a monster, instead of just using a bounding sphere/box.
Now that things are being drawn reasonably efficiently, I can finally start to implement some interesting game mechanics. Stay tuned for that.