Symmetric Cluster Set Level of Detail for Real-Time Terrain Rendering

In this paper, we present an improvement for batch-based quad tree terrain rendering that drastically reduces the number of draw calls to the graphics processing unit. As a result, more fine-grained triangular optimization is possible without sacrificing triangle throughput. No extra preprocessing is required. In general, quad tree terrain algorithms recursively subdivide mesh geometry to meet visual error constraints. Batch-based techniques use buffered grid blocks as the subdivision primitive for better triangle throughput. We base our algorithm on structural observations of such terrain quad trees. First, we show that the four sub-nodes of any non-leaf can be categorized into sixteen distinct states of drawing behavior. These states are symmetric in such a way that allows just five unique geometries to represent all of them. With the additional observation that leaf nodes appear in groups of four across regions of homogeneous grid resolution, we develop a technique employing 23 unique geometric batches from which any terrain can be rendered. The resulting algorithm reliably reduces draw calls by a factor of 6 on average, and achieves render performance 30 to 50 percent faster than comparable techniques.