Optimizing terrain culling.

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.

Arbitrary polygon displayed with red lines. Terrain chunks that do not intersect this polygon are culled.

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:

The camera frustum projected onto the terrain grid forms a trapezoid.

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.

On the left, a top down view of the camera frustum (projected onto the terrain). On the right, the convex hull resulting from the edges of this projection.

The red lines display the shape of the culling polygon produced from projecting the camera frustum onto the sea plane.

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.

This entry was posted in Coding, DBP2011, XNA and tagged , , . Bookmark the permalink.

6 Responses to Optimizing terrain culling.

  1. GeorgeR says:

    Good God – 200 tests? Use a quad tree!

  2. olhovsky says:

    200 tests is with a quadtree.

  3. check it out says:

    %image_title% is the greatest.|
    check it out http://www.geckogo.com/Blogs/?user=145618788

  4. Richie says:

    Hey Admin do you want unlimited content for your wordpress blog?

    100% unique and human readable. Serarch in google:
    Ryordel’s rewriter

  5. Hannelore says:

    If you are interested in topic: earn online money by
    typing pal – you should read about Bucksflooder first

  6. 83Tanja says:

    Hi admin, i must say you have high quality articles
    here. Your blog should go viral. You need initial traffic boost only.
    How to get it? Search for: Mertiso’s tips go viral

Leave a Reply

Your email address will not be published. Required fields are marked *


You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>