Grid Decimation

By default GenSurf will produce a surface using triangular brushes that fit a rectangular grid. For many surfaces, however, it would be much more economical to use more brushes in detailed areas where the slope changes frequently and fewer brushes in relatively planar areas. This is the purpose of the grid decimation feature of GenSurf. The algorithm used by GenSurf is very similar to one described in the article Fast Polygonal Approximation of Terrains and Height Fields by Michael Garland and Paul Heckbert. You can download this article and/or read up on other decimation algorithms at their Terrain Simplification web site. In short, GenSurf uses only those vertices which, if omitted, would result in large errors in the shape of the surface. Other vertices are discarded. The final output mesh is a triangulation of those vertices not discarded. A rather extreme example of this algorithm at work is illustrated by the screenshots below:

Undecimated 32x32 grid

Surface resulting from using 90% decimation

GenSurf starts the decimation routine by ignoring all but the 4 corner points, then triangulates that grid. For each of the 2 resulting triangles, GenSurf finds the vertex enclosed by that triangle that has the largest error for the current triangulated mesh. If the error for this vertex is equal to or greater than 1/2 the maximum error for all vertices, then this vertex is added to the mix. After adding vertices the mesh is triangulated again. The process is repeated until the specified decimation level is reached. In addition, GenSurf checks for edge triangles with small angles at the surface edge. (Edge values frequently have small or zero error, and so would never be included in the above calculations. However, if precautions aren't taken to add sufficient edge vertices, the resulting mesh will sometimes have very long, slender triangles that don't accurately mimic the original surface). After producing the decimated grid, GenSurf checks to ensure that all fixed points have 0 error. If not, these vertices are also added.

Shown below are contour plots (with elevation represented by color) of ground surface meshes produced by GenSurf with different decimation values. The original surface is a 32x32 grid. Note that I'm not suggesting this is a good grid size to use... the large size was selected to push the decimation routine and produce visible differences in the results.

Decimation=0
1089 vertices
2048 brushes
Peak poly count

Decimation=50
546 vertices
1021 brushes
Peak poly count

with hint brushes:
w/o hint brushes:

1385
3973

with hint brushes:
w/o hint brushes:

930
2215

Decimation=75
275 vertices
501 brushes
Peak poly count

Decimation=90
112 vertices
192 brushes
Peak poly count

with hint brushes:
w/o hint brushes:

722
1118

with hint brushes:
w/o hint brushes:

392
413

For maps using detail hint brushes, you'll probably be disappointed with the results achieved using a decimated grid. Though you can certainly reduce the polygon count using a large decimation value, the hint brushes produced by GenSurf are much less effective than they are with a normal rectangular grid. On many test surfaces that I've produced, surrounding all surface brushes with hint planes results in bizarre visual errors in the game - typically infinitely tall surface brushes that aren't solid. It turns out that the detail hint brushes cause problems for the compilers if the planes of the hint brushes aren't parallel to one of the orthogonal axes. For this reason, GenSurf will only add hint brushes that bound a rectangular collection of surface brushes. The higher the decimation value is, the less likely it is that brushes can be grouped into a rectangle... so the difference in polygon counts for large decimation values is not as significant as the difference for little or no decimation.

Ground surface: 16x16 grid, 1024x1024 units, Fractal method with roughness=32.

Cliff walls: 16x6 grid, 1024x384h units, Fractal method with roughness=64.

All surfaces use GenSurf's detail hint brushes.

You'll notice that the differences between 0 and 75% decimation are more apparent if Phong shading isn't used. The overall shape is roughly the same. No value judgements are made here - if you want to keep small details in your surfaces then grid decimation obviously isn't the way to go. In this case, though, I personally think the decimated surfaces look as good as or better than the original, if only because the surface isn't quite so regular.

No decimation
wpoly=922

75% decimation
wpoly=498