Generation of analytical surfaces on the example of maps. Part 2

Introduction

If you have data with an uneven grid, the most important step in processing it is converting to a data set with a uniform grid. This transformation is necessary for computer simulation in real time or approximation. Obtaining height directly from a non-uniform grid is a resource-intensive operation.

In this part, we will consider the algorithm for converting a non-uniform grid into a uniform one with a fairly good quality of the result.

The content of the work

Part 1. Data preparation
Part 2. Generating a uniform grid.
Part 3. Creating an analytical surface

Subtask target

It is necessary to obtain a uniform grid from the existing set of isolines. In this case, all heights must be consistent (smooth transitions). In place of the isoline height should not be distorted.
')

Algorithms

There are various algorithms for obtaining uniform grids. All of them have their strengths and weaknesses, as is the example below.

Since the uniform grid was an intermediate result of the work, its creation was carried out in advance. The running time of the algorithm should have been within the reasonable limits of time and memory consumption.

The obtained result can already be used for gaming applications, since its accuracy is not so critical.

From the previous part, we have actually already received a uniform grid with the required resolution, only the majority of the heights on it have not been calculated. This task is solved by this part.

Work card

Figure 1 shows an example of a uniform grid with unfilled heights. Line color indicates height, black color means unknown height.


Figure 1. Work Card

General description of the algorithm for obtaining height at an arbitrary point

Regions

For a better allocation of occupied memory, it is necessary to split the entire map into regions. Go through all points that do not have height and calculate.

Height calculation

Find the three nearest points with a known height in the working area (the segment between the exact and the desired one should not intersect and touch the isolines). Calculate the height of the available data using any algebraic method (using the center of mass of the triangle , where the height is taken as weight).

Find nearby points

At this point, mention should be made of the book V. Porev "Computer Graphics" . It provides basic concepts of computer graphics and provides a good algorithm for finding the nearest point. It is called "Search around the perimeter of the square."

The original algorithm searches for only two nearest points, and there may be situations when the found points, partially or completely, can be located behind isolines from the current one. The height calculated in this way is incorrect, therefore the algorithm was extended to three points with control of intersections with contour lines. In this case, artifacts arising earlier disappear in saddle points (lowlands between several dominant heights) and at the edges of large height differences.


Figure 2. The original algorithm. Red outlined artifacts.

Figure 3. Modified algorithm.

I will not give all the code in the article; it will be given by reference at the end of the article. There is not much of it, comments are enough for understanding.

Processing results

The processing results in a uniform grid with the required resolution. An example is shown in Figure 3. It has smooth transitions between heights. The whole map with a uniform grid is divided into regions to reduce the amount of memory used. Uneven grid data is stored in list structures.

findings

The uniform grid generation is a fairly resource-intensive operation, it can take several days, depending on the required accuracy and computing power. The algorithm is perfectly parallelized, which allows you to perform calculations more efficiently. A modification of the B. Porev algorithm from the book “Computer Graphics” was used .

Interpolator source codes