Zelimir Fedoran
email zelimir.fedoran@gmail.com

Reducing Triangle Count

Posted on
April 30th, 2010
Tags
, ,

After creating the initial voxel renderer I noticed several inefficiencies. One of them is that I draw a lot of unnecessary triangles. For instance, if there are 4 quads, next to each other, why not draw one quad instead of 4? Another is that I draw a lot of triangles which are not even visible.

Merging Adjacent Faces

I can reduce the number of drawn triangles by merging them with adjacent triangles to create larger rectangles. However, none of the algorithms I came up with were fast enough to be used in a game. Thus, i settled on merging quads into one dimensional strips rather than rectangles. This allows me to create quad strips by only checking the current and next voxel while looping through all voxels. I repeat this once for each of the 3 axis to merge quads along the X-axis, Y-axis, and the Z-axis.

It is a simple algorithm and produces acceptable results. On a random 16x16x16 region, where 90% of the voxels are empty, the triangle count goes from 11,612 to 8,060. That’s 30% less triangles! With a more realistic terrain I expect the number of triangles to be much less.

No merging at allMerged on X-axis onlyMerged on X-axis and Y-axisMerged on all 3 axis

Backface Culling

When you look at a cube you can only ever see three sides directly. Therefore, it does not make sense to draw the sides which are not visible. When viewing a distant region of voxels, the voxels will all show the same faces. Therefore, I can selectively render only the faces which are visible to the camera by maintaining 6 index buffers per region, one for each face. However, this method requires 3 or more draw calls per region, but it reduces the final triangle count from 8,060 to 4,022 or by 50%. Ultimately, I have decided to leave this optimization out since these triangles wont be shaded anyways and the larger number of draw calls is likely more expensive on the Xbox.

Backface Culling (Far)Backface Culling (Near)