Mesh generation

In the implementation of terrain mesh generation, a flexible and extensible approach was taken by defining a base class, TerrainGenerator, from which specific terrain generation methods could be derived. This base class, defined in terrain_generator.hpp, serves as a common interface for generating meshes. It includes a pure virtual method generate(), which must be implemented by any derived class to produce a mesh.


class TerrainGenerator
    {
    public:
        using mesh_type = Mesh;
        virtual std::unique_ptr<mesh_type> generate() = 0;
        virtual ~TerrainGenerator() {};
    };

Two primary subclasses were developed to handle different sources of elevation data: LambdaGenerator and GpsGenerator. Both classes inherit from TerrainGenerator and share a common goal—creating a 3D mesh by initializing its points and triangles. However, they differ in how they assign the z values (elevation) to the mesh points.

1. LambdaGenerator

The LambdaGenerator class, defined in lambda_generator.hpp and implemented in lambda_generator.cpp, allows for the creation of a mesh where the z values are derived from a user-defined lambda function. This function is passed to the constructor and is used to compute the elevation for each point in the mesh grid.


class LambdaGenerator : public TerrainGenerator
{
public:
    using fn_type = std::function<double(double, double)>;
    LambdaGenerator(int meshSize, fn_type const &fn);
    virtual ~LambdaGenerator();

    std::unique_ptr<mesh_type> generate() override;

private:
    int M_meshSize;
    fn_type M_fn;
};

The mesh is generated on a regular grid, where each grid point’s elevation is computed by applying the lambda function to its x and y coordinates. After computing the elevations, the grid points are connected to form triangles, resulting in a triangulated mesh.

Key steps in the LambdaGenerator::generate() method include:

  • Grid points creation: The mesh grid is initialized, and each point is assigned a z value based on the provided lambda function.

  • Triangle formation: Right triangles are created from adjacent grid points, ensuring a complete triangulated mesh.

  • Edges creation: Border edges are added to the mesh to define its boundary.


1.1. Surface of a sphere

The following lambda function:

\[z(x, y) = \sqrt{r^2 - (x - x_0)^2 - (y - y_0)^2}\]

where r is the radius of the sphere and \((x_0, y_0)\) are the coordinates of the center and z is the z-coordinate of the point on the sphere corresponding to the input coordinates x and y.

This function translates in C++ like this:


auto fn = [=](double x, double y)
{
    return std::sqrt(radius * radius - (x - centerX) * (x - centerX)
    - (y - centerY) * (y - centerY));
};

and it results in the following mesh:


generated lambda 1
Figure 1. 3D mesh surface of a sphere

1.2. Wave-like terrain surface

This other lambda function:


\[z(x, y) = sin(x) + cos(y)\]

wich translates in C++ like this:


auto fn = [=](double x, double y)
{
    return std::sin(x) + std::cos(y);
};

results in the following mesh:


generated lambda 2
Figure 2. 3D mesh wave-like surface

2. GpsGenerator

The GpsGenerator class, defined in gps_generator.hpp and implemented in gps_generator.cpp, generates a mesh where the z values are obtained from real-world elevation data. This data is fetched from a specified tile using the Mapbox Terrain-RGB v1 API.


class GpsGenerator : public TerrainGenerator
    {
    public:
        GpsGenerator(int meshSize, double latitude, double longitude, unsigned zoomLevel, std::string const &apiKey);
        virtual ~GpsGenerator();

        std::unique_ptr<mesh_type> generate() override;

    private:
        int M_meshSize;
        double M_latitude;
        double M_longitude;
        unsigned M_zoomLevel;
        std::string M_apiKey;
    };

The process involves the following steps:

  • Tile downloading: The latitude, longitude, and zoom level specified in the configuration are used to determine the corresponding tile. The tile data is then downloaded using the downloadTile() function.

  • Elevation data processing: The downloaded tile is decoded to extract elevation values. These values are used to initialize the z coordinates of the mesh points.

  • Mesh construction: Similar to LambdaGenerator, the grid points are connected to form triangles, and border edges are added to define the mesh boundary.

Here is the resulting mesh, corresponding to the tile with coordinates (x, y) = (33809, 23527) at zoom level 16, which includes the location at longitude 5.7232 and latitude 45.1835, located in Grenoble, France:


generated grenoble 16
Figure 3. 3D mesh surface at zoom level 16 for the tile (33809, 23527)

All the meshes visualized here were exported in the MSH format, using the ExporterMeshGmsh class, and were visualized using the Gmsh software.

3. Common functionalities

Both LambdaGenerator and GpsGenerator share a common workflow for mesh construction, with the primary difference being the source of the z values:

  • Lambda function: In LambdaGenerator, the z values are computed using a lambda function, providing flexibility in defining custom terrain shapes.

  • GPS data: In GpsGenerator, the z values are sourced from actual elevation data, enabling accurate representation of real-world terrains.

This modular approach, where the z values are derived from either a lambda function or real elevation data, allows the system to be extended easily for different types of terrain generation methods while maintaining a consistent structure for mesh construction.


Next: Contour lines generation


References