Generation of analytical surfaces using maps as an example. Part 2

Introduction

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

In this part, we will consider an algorithm for converting an uneven grid to a uniform one with a fairly good quality of the result.

The content of the work

Part 1. Data preparation
Part 2. Generation of a uniform grid
Part 3. Creation of an analytical surface

Subtask Purpose

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

Algorithms

There are various algorithms for obtaining uniform grids. All of them have their advantages and disadvantages, as well as the example below.

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

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

From the previous part, we actually already received a uniform grid with the desired resolution, only most of the heights on it are not calculated. This problem is solved by this part.

Work card

Figure 1 shows an example of a uniform grid with unfilled heights. The color of the line indicates the height, black color - unknown height.


Figure 1. Work card

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

Regions

For a better distribution of the occupied memory, it is necessary to divide the entire map into regions. Go through all the points that have no height and make a calculation.

Height calculation

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

Find nearby points

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

The original algorithm searches for only two nearest points, while situations are possible when the found points, partially or completely, can be located behind the isolines from the current one. The height calculated in this way is incorrect, so the algorithm was expanded to three points with the control of intersections with contours. In this case, previously artefacts disappear at the saddle points (lowlands between several dominant heights) and at the edges of large elevations.


Figure 2. The original algorithm. Red circled 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. It is not much there, comments are enough for understanding.

Processing results

As a result of processing, a uniform grid with the necessary resolution is obtained. An example is shown in Figure 3. It has smooth transitions between heights. An entire map with a uniform grid is divided into regions to reduce the amount of occupied memory. Irregular grid data is stored in list structures.

conclusions

Generating a uniform grid is quite a resource-intensive operation, it can take several days, depending on the required accuracy and computing power. The algorithm is perfectly parallelized, which allows us to carry out calculations more efficiently. A modification of V. Porev’s algorithm from the book “Computer Graphics” was used .

Interpolator source codes