Voronoi Dataset

Our first step is to precompute a Centroidal Voronoi Tessellation with a moderately high density of 2048 cells for use within a 256x256 point map. The C++ source code can be found on John Burkardt's website. The choice of 2048 voronoi cells is based on how big the cells would be on a 256x256 point map. Ideally, they should not be too big or too small. We precompute basic information regarding each voronoi cell, such as their centroid location, neighbour indices, neighbour directions and the border condition.

After that, we clamp the facet points of each voronoi cell that are outside of the map region to its border. Additionally, we do polygonal scan-line rendering in order to get the point data for each voronoi cell. We store them in a compressed row format as opposed to individual points.

We chose to use Centroidal Voronoi Tessellation is because the prior method of generating a voronoi cell network using Fortune's algorithm can result in voronoi cells being stretched along the border of the map. This makes them difficult to use at the border and would result in weird stretching results with sharp points from subsequent algorithms.

Geometry Tile Sets

Next, we precompute a set of geometry tiles in the form of textured quads that are optimised for loading. We use a common tile set for the broad phase solution and several more specific tile sets for the narrow phase. We precompute the geometric data in the form of vertex and polygon counts, indices for position, texture coordinate and face normals, indices for polygon vertices and unique positions and texture coordinates.

This allows the solution to perform much faster updating to the geometry chunks when the user moves around the scene since the geometry assembly process is a slow process and the identical geometry tiles are being reused throughout the entire scene.

The images below show the full set of geometry tiles that the solution currently uses. The colours from the geometry tiles are only for sub-mesh grouping purposes.

The first set is made for inland water bodies and coastlines that have no beaches. So only lakes will use this tile set as all the coastlines are set to contain beaches in this current implementation. This tile set will also be revised for subsequent updates.

The second set is a simplified version of the first one and is more suitable for coastline with beaches and for jagged land boundaries. Shallow seawater also uses this second tile set. This tile set will also be revised for subsequent updates.

The third set is for seawater with sea waves. These tiles include 4x4,8x8,16x16 and 32x32 points. There are 16 variations for each group. This tile set only acts as a placeholder and seawater tiles will be revised for subsequent updates.

The offline mesh assembly system spilts the mesh into several sub-meshes each with a different material. Within each sub-mesh, it forms the quad geometry based on the colour indices the .vox file uses. The mesh assembler attempts to make the least quads required to form the geometry tile. The assembler exports position, normal and texture coordinates for each tile. After that, all the tiles are batched and each geometric component is exported as a batch. We do this because three.js uses a binary importer that is more suitable for importing mesh data with a common datatype.

Island Generation

We generate between two to four large-sized islands on a 256x256 point map, ensuring that the seed voronoi cells do not fall among the border. Next, we do a randomised deposition of neighbouring cells around the seed cell. Neighbouring cells that do not meet the randomisation criteria gets excluded. This allows the formation of small inlet and bay features for the island as the particular voronoi cells were permanently omitted from land formation.

After establishing the land portion for the islands, we propagate the elevation as a min-max value from the seed cell outwards to the neighbouring cells in several elevation layers. We start the seed cell with the highest suitable elevation range and taper off the values for each layer away from the center. Hence, we do not intend to use a Perlin noise generated height-map that are prevalent in other algorithms.

We repeat the same procedure for medium-sized and small-sized islands. Additionally, we need to ensure that the distance between an existing island cell and a potential seed cell is sufficiently wide. This avoid setting new seed cells to be too close to existing island cells.

After that, we determine the shore-water regions that surround the landmass of the islands. These regions are then expanded once more but randomly with a criteria threshold. Next, we resolve any missing voronoi cells that should be classified as shore-water, especially if they could be fully enclosed by other cells with the same classification.

From the shore-water regions, we classify any voronoi cells are mostly surrounded by land as shore-water bays and those that are fully surrounded by land as shore-water lakes. Next, we reclassify any shore-water bay clusters as lakes if they are fully enclosed by land.

After the shallow water regions have been classified, we expand the remaining water-related voronoi cells as seawater in layers. The elevation range of the seafloor is then established in layers, with the shallow water regions having the highest elevation below seawater level.

The land-based voronoi cells are classified into the types of land they are occupying. The upper bound of the elevation range determines the scope of the land types that can be used for randomisation, so there can be a bit of overlapping land types across dominant regions.

World Attributes

The world attributes can now be generated and these are similar to existing games that make use of world map generation solutions (eg Dwarf Fortress).

Each voronoi cell computes the latitude zone in which it is located. For this project alone, only a common latitude zone is used. For larger world maps, the latitude range can span different zones.

After that, we determine the natural drainage for voronoi cells that have land or enclosed water regions. Enclosed water bodies such as lakes and rivers have poor drainage since water retention is the highest. Since there are no rivers in this project, only lakes have the poorest drainage.

For land-based voronoi cells, the type of land determines the scope of drainage it can have. For example, hilly regions aid in the velocity runoff of rainwater and can have moderate drainage, while flat regions tend to have imperfect drainage and coastal land regions always have imperfect drainage. A suitable drainage type is randomly determined based on the given scope.

The type of wind-force is determined next and the algorithm only uses logic determination with no numerical computations. This allows the results to remain stable throughout the wind propagation, as our past work in using numerical computations had shown that it could result in some overtly accumulated wind force values.

Since the overall scene is heavy in seawater, we set initial wind-force type to be of strong breeze. Next, the initial wind direction is determined by the latitude zone. The wind propagation begins with voronoi cells at the border. For each iteration, the voronoi cells distributing the wind force will check for the least obstructed land and water types to flow to.

The algorithm determines the next wind force type from its current residue, depending on the current and least obstructed land and water types. The next wind force type could increase to a stronger one if the next region to flow to has lower resistance. Likewise, it could decrease to a weaker one if the next region to flow to has greater resistance. The neighbouring wind force type and residue is updated only if the wind flow becomes stronger.

After that, the temperature type for each voronoi cell is determined by the latitude and the type of land or water. A suitable temperature type is randomly chosen from a span of possibilities. Temperatures on land tend to be warmer than those for water.

Next, the moisture type is determined for each voronoi cell based on the wind force and temperature types. After that, the rainfall type is determined for each voronoi cell based on the moisture and type of land or water.

Next, we prepare the type of water-biome for each voronoi cell that has a water-type. Additional criteria include the latitude, temperature and salinity. After that, the shore-water lakes are updated to reflect a common water-biome type if any neighbouring cell of the lake has a different water-biome type.

After that, we prepare the type of land-biome for each voronoi cell that has a land-type. Additional criteria include the latitude, temperature and rainfall.

Next, we prepare the type of wetland-biome for the closest voronoi cell that is affected by a neighbouring lake. Additional criteria include the land type, latitude, rainfall, drainage and salinity.

The coastlines with clear-water beaches are identified by checking the prevalence of fine sandy beaches along the outermost voronoi cells of each island. This condition allows for a brighter colour for the shallow seawater surrounding the island.

After that, we prepare a similar scope of world attributes but only for the seawater that exists on the surrounding border maps.

Broad Phase Solution

We move onto preparing the scene as part of the broad phase solution. The solution uses a hierarchy of voxels in order to provide the spatial partitioning required to segregate parts of the scene into smaller manageable components.

A voxel in our implementation has space for 4x4x4 points, in which the textured geometry quads within it will match its coloured grids from the texture onto the sub-mesh geometry. We do this in our pre-computation step on assembling the geometry tile sets.

We scale the hierarchy to voxel-cells, in which each has space for 8x8x8 voxels. Then a voxel-chunk has space for 4x4x4 voxel-cells.

Since the map is flat in the current implementation, only one layer of voxel-chunks is required and within it, only one layer of voxel-cells is required. But within each voxel-cell, only two layers of voxels are required, one for the broad phase and the layer on top of it for the narrow phase.

A voxel also can reference to a point on the low resolution 2D map. It extracts the world attributes from the map from which had been determined earlier and use them to determine the material type that the voxel would have. The geometry chunk processes these voxels and assembles the geometric mesh using the precomputed geometry tile set into vertex and index buffers.

For optimisation purposes, the solution does not store individual voxels but instead as a group. So some voxels can be bigger with a size of up to 4x4x4. And the geometric mesh does not always have uniform sized quads being batched into its buffers, it can contain quads of different sizes.

The solution renders the broad phase geometry data as a hidden layer to cover up holes indirectly produced by floating point errors from the narrow phase geometry. So the broad phase voxel data tends to be rather clunky.

A voxel of size 1x1x1 can allow the geometric sub-mesh to have quads that are textured with a 4x4 pattern. A chunk can contain different sized voxels and more than one quad is usually required to complete assembling the sub-mesh for each voxel, since there is also the reuse of texture space within the generic coloured texture.

Narrow Phase Solution

We move onto preparing the scene as part of the narrow phase solution. For each group of land or water biome-type in the narrow phase, the solution prepares a list of voronoi cells that would be affected. After that, the pixel locations occupied by each voronoi cell within the list are extracted. Each pixel location is checked for its land or water biome-type suitability before expanding the same query to its neighbouring locations. Next, we gather a list of conditions from the neighbouring pixel locations before establishing the type of connectivity of the current pixel.

The type of connectivity for a pixel corresponds to the specific geometry tile in the tile set. It can also be varied by the number of unique connecting materials from its adjacent neighbours. Materials for wetland biomes will also take precedence over land biomes.

During the geometry chunk update process, the specific geometry tile is obtained from the reference tile set and added to the geometry buffers in order to assemble the sub-mesh of the voxel. The routine is scaled across all valid voxels within each voxel-cell and for all voxel-cells within the voxel-chunk. Rendering of the scene geometry is only done at the voxel-chunk level so as to keep the number of draw calls to a minimum.

A reusable object system is also implemented in order to allow hidden chunks of the scene to be recycled and only those that are visible to the frustum to be cached and rendered. So hidden voxel-chunks will eventually be recycled and memory reclaimed by the garbage collector and new voxel-chunks will undergo the same geometry update process.

We start off with establishing the border of the lakes in conjunction with the neighbouring materials. After that, the lake water is filled up.

The beach shore with the inland neighbouring materials is then established. After that, we add in the beach wet sand and immediate seawater.

The coastal shallow water is next and this region is closer to the beach. After that, the turquoise seawater transitions to light-blue.

The first layer of non-shallow seawater is established next. After that, nearshore sea waves are added in.

Both seawater and sea-waves could overlap over to the border maps if there is an island close to the boundary of the center map. But this is less likely to happen at this stage.

The next layer to be established is deep seawater. After that, deep sea-waves are added in.

Both deep seawater and deep sea-waves could overlap over to the border maps if there have been sufficient propagation towards the border of the center map. And this is more likely to happen at this stage.

We also expand the deep sea-waves by an additional iteration in order to widen its coverage.

The next layer to be established is the ocean. After that, ocean waves are added in.

Both ocean and ocean-waves could overlap over to the border maps if there have been sufficient propagation towards the border of the center map. And this still can happen because the overlapping of seawater onto the border maps had not been completed.

We also expand the ocean-waves by two additional iterations in order to widen its coverage.

The last layer to be established is the deep ocean. After that, deep ocean-waves are added in. We also expand the deep ocean-waves by two additional iterations in order to widen its coverage.

Next, we establish the borders of wetland regions on the islands. These borders include different wetland boundaries or adjacent land boundaries to the wetland. The solution addresses the issue of having multiple neighbouring materials by subdividing the sub-mesh in the voxel to use different materials.

After that, the borders of differing land regions are then established. For both wetland and land borders, the solution iterates through the individual biome types in order to establish consistent jagged borders from one biome to its neighbour.

Next, the wetland regions are filled using a flood-filling solution. Lastly, the land regions are filled similarly.

After that, we switch the hidden coarse layer of voxel geometry back on to cover the many tiny holes caused by imperfect precision.

Conclusion

In summary, we have discussed the development techniques for the first version of Littlecube Island Maps. In the next article, we will discuss some changes to the solution as we work towards the second version of the project.

References

Littlecube Island Maps: Development Overview

Dragons Abound (by Scott Turner)

John Burkardt's website