Evolution Visualization

(Note: GIFs may need few seconds to load)

Forward Evolution

Backward Evolution

Execution

make mapgen
./mapgen -n [nVoxels] -m [nMountains], -t [nThreads]

External Libraries & APIs

• Generating Fantasy Maps (inspiration)
• FortuneSweep Voronoi Generation
• Graphics.py
• Raylib
• EarCut Tesselation
• OpenMP

Algorithm Design

The block diagram gives an overview of the map generation and rendering pipeline. Arrows are used to indicate a linear set of dependencies between different stages of the pipeline. CPU-executed components are indicated in yellow, and GPU components are indicated in green.

• Voronoi - Compute a randomized Voronoi map with a prespecified number of voxels using the Fortune Sweep algorithm.
• Parsing - Iterate over the centroids and edges of the returned Voronoi map and store them in the custom map data structure. Allocate a zeroed out heightmap of the same size as the number of voxels.
• Slope - Generate a random 2D vector representation of a line and compute the dot product of each voxel centroid to the line. Store this distance in the voxel's heightmap.
• Mountain - Generate 2D mountain locations. For each voxel, compute the distance between the voxel and mountain center. As an effect of this computation, heightmap values of voxels nearer to the mountain will be influenced more.
• Normalize - Retrieve the min and max height values across the global heightmap. Subtract the min height from each value in the heightmap, and divide by the difference between the max and min (i.e. heightmap normalization).
• Mean - Retrieve the mean of the heightmap list.
• Render - Compute the color for each voxel as a function of its height through a threshold and affine transformation based coloring scheme. Before rendering each voxel, tessellate the polygon using the EarCut algorithm, and render each polygon with the computed colors.

Performance

Results of Fig 1-3 computed on an 8-core Linux machine.
Results of Fig 4 computed on an 4-core Linux machine.

Fig 1. Generation time in μsec as voxels increase, m=25.

Fig 2. Generation time in μsec with n=320000, m=25.

Fig 3. Generation time in μsec as mountains increase, n=32000.

Fig 4. Generation time in μsec with n=320000, m=32000.

Gallery

(Click on the image to reveal a high-res version with the number of voxels and mountains listed.)

Contributors

(equal contribution. sorted in alphabetical order).

• Oscar Dadfar
• Shuby Deshpande