The One Man MMO Project
The story of a lone developer's quest to build an online world :: MMO programming, design, and industry commentary
Terrain Mesh Level of Detail
By Robert Basler on 2013-09-25 19:53:09
Homepage: www.onemanmmo.com email:one at onemanmmo dot com

In my quest to increase draw distance, I needed to find a way to reduce the number of triangles in my terrain block meshes from 7938 to something much smaller but that still retained the overall shape of the original block. I found lots of algorithms for decimating (reducing the number of triangles in) meshes but nothing specific to terrain meshes.

I had a couple of considerations I used to create the algorithm. I wanted to keep all the edge vertices so that blocks mesh perfectly. (There are lots of algorithms for perfectly matching terrain blocks of different detail levels, but I just didn't want to put in the effort to use them.) The mesh will only be viewed from one direction (I'm building an RTS, and these blocks are far from the camera.)

The original algorithm used the distance to line function and iterated twice over the grid of vertices, removing ones where the middle vertex was less than 2.5m from the ones on either side. The problem was that this algorithm completely flattened the terrain in some cases. Oops.

After an afternoon of thought while driving in Vancouver traffic, I came up with a better algorithm:

1. Find the contour lines perpendicular to the view direction. By treating the high and low points of each contour line specially, I'm able to retain high and low points on the terrain with no risk of flattening them. These are key to maintaining the overall shape of the terrain in the distance. To do this, I search across the vertices (either higher or lower ones) until I find the first point where the slope of the line changes direction. These two points are a contour segment.
2. Use the distance to line function to remove any vertices between the high and low points of that contour segment that are less than 2.5m from the line.
3. Once the grid has been reduced to contour lines, iterate over all the points, removing ones where the centre one is more than 2.5m from the line. There's a slight danger of flattening a peak here, but looking at the results, this doesn't seem to be a problem.

This code removes the unneeded vertices:

`        static const float32 SMOOTHING_FACTOR = 2.5f;        // Pass 1, Find high and low spots to generate a contour line.          // Remove any points between them that are outside of smoothing factor range.        for ( unsigned int row = 1; row < TILE_Y_DATA_SIZE - 1; ++ row )        {            unsigned int leftCol = 0;            while ( leftCol < TILE_X_DATA_SIZE - 1 )            {                unsigned int rightCol = leftCol + 1;                if ( vertices[ row ][ leftCol ][ 1 ] <= vertices[ row ][ rightCol ][ 1 ] )                {                    while ( ( vertices[ row ][ rightCol - 1 ][ 1 ] <= vertices[ row ][ rightCol ][ 1 ] ) &&                             ( rightCol < TILE_X_DATA_SIZE - 1 ) )                    {                        ++rightCol;                    }                }                else                {                    while ( ( vertices[ row ][ rightCol - 1 ][ 1 ] > vertices[ row ][ rightCol ][ 1 ] ) &&                             ( rightCol < TILE_X_DATA_SIZE - 1 ) )                    {                        ++rightCol;                    }                }                for ( unsigned int column = leftCol + 1; column <= rightCol - 1; ++column )                {                    float32 distance;                    Geometry::DistancePointLine( vertices[ row ][ column ],                         vertices[ row ][ leftCol ],                         vertices[ row ][ rightCol ],                         &distance );                    if ( distance < SMOOTHING_FACTOR )                     {                        included[ row ][ column ] = false;                    }                }                leftCol = rightCol;            }        }        // Pass 2, Now that we have a contour, smooth it out.        for ( unsigned int row = 1; row < TILE_Y_DATA_SIZE - 1; ++ row )        {            for ( unsigned int column = 1; column < TILE_X_DATA_SIZE - 1; ++column )            {                if ( included[ row ][ column ] )                {                    unsigned int leftCol = column - 1;                    while ( !included[ row ][ leftCol ] ) --leftCol;                    unsigned int rightCol = column + 1;                    while ( !included[ row ][ rightCol ] ) ++rightCol;                    float32 distance;                    Geometry::DistancePointLine( vertices[ row ][ column ],                         vertices[ row ][ leftCol ],                         vertices[ row ][ rightCol ],                         &distance );                    if ( distance < SMOOTHING_FACTOR )                     {                        included[ row ][ column ] = false;                    }                }            }        }`

And this code triangulates the resulting vertices:

`        unsigned int faceIndex = 0;        unsigned int topRightCol;        unsigned int bottomLeftCol;         unsigned int bottomRightCol;        for ( unsigned int topRow = 0; topRow < TILE_Y_DATA_SIZE - 1; ++topRow )        {            unsigned int bottomRow = topRow + 1;            unsigned int topLeftCol = 0;            while ( !included[ topRow ][ topLeftCol ] ) ++topLeftCol;            topRightCol = topLeftCol + 1;            while ( !included[ topRow ][ topRightCol ] ) ++topRightCol;            bottomLeftCol = topLeftCol;            while ( !included[ topRow + 1 ][ bottomLeftCol ] ) --bottomLeftCol;            bottomRightCol = bottomLeftCol + 1;            while ( !included[ topRow + 1 ][ bottomRightCol ] ) ++bottomRightCol;            bool topTriangle = topRightCol - topLeftCol >= bottomRightCol - bottomLeftCol;            while ( ( topRightCol < TILE_X_DATA_SIZE ) || ( bottomRightCol < TILE_X_DATA_SIZE ) )            {                if ( topTriangle )                {                    {                        terrainGridFaces[ faceIndex ].v1 = topRow * TILE_X_DATA_SIZE + topLeftCol;                         terrainGridFaces[ faceIndex ].v2 = bottomRow * TILE_X_DATA_SIZE + bottomLeftCol;                         terrainGridFaces[ faceIndex ].v3 = topRow * TILE_X_DATA_SIZE + topRightCol;                         ++faceIndex;                    }                    topLeftCol = topRightCol;                    topRightCol = topLeftCol + 1;                    while ( ( topRightCol < TILE_X_DATA_SIZE ) &&                             !included[ topRow ][ topRightCol ] ) ++topRightCol;                    if ( ( ( topLeftCol >= bottomLeftCol ) || ( topRightCol == TILE_X_DATA_SIZE ) ) &&                          ( bottomRightCol != TILE_X_DATA_SIZE ) )                    {                        topTriangle = false;                    }                }                else                {                    {                        terrainGridFaces[ faceIndex ].v1 = topRow * TILE_X_DATA_SIZE + topLeftCol;                         terrainGridFaces[ faceIndex ].v2 = bottomRow * TILE_X_DATA_SIZE + bottomLeftCol;                         terrainGridFaces[ faceIndex ].v3 = bottomRow * TILE_X_DATA_SIZE + bottomRightCol;                         ++faceIndex;                    }                    bottomLeftCol = bottomRightCol;                    bottomRightCol = bottomLeftCol + 1;                    while ( ( bottomRightCol < TILE_X_DATA_SIZE ) &&                             !included[ bottomRow ][ bottomRightCol ] ) ++bottomRightCol;                    if ( ( ( bottomLeftCol >= topLeftCol ) || ( bottomRightCol == TILE_X_DATA_SIZE ) ) &&                          ( topRightCol != TILE_X_DATA_SIZE ) )                    {                        topTriangle = true;                    }                }            }        }`

Another improvement I tried was to remove faces that faced away from the viewer. I ended up removing this because when the camera is on the top of a mountain and the terrain block is quite far below, those faces sometimes show as holes in the terrain. I would have to remove only faces that faced almost directly away from the camera to prevent holes, and that doesn't seem worth the effort.

On my terrain, this algorithm removes 90-96% of the triangles from the original mesh and the horizon line is indistinguishable from the high-resolution meshes.

New Comment

You will not be able to post until you resolve this problem.

 Comment (You can use HTML, but please double-check web link URLs and HTML tags!) Your Name Homepage (optional, don't include http://) Email (optional, but automatically spam protected so please do) What is four plus three? (What's this?)

[The Imperial Realm :: Miranda] [Blog] [Gallery] [About]