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

Introduction

Exact physical modeling requires high poly maps. The higher the accuracy of the map, the more memory it takes and the more data you have to process to get the height. Spline interpolation allows you to get a grid of any resolution, with any convenient at the moment, step in latitude and longitude.

The content of the work

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

Subtask target

Get a spline surface from a uniform grid containing all the original points. Implement the calculation of the height in two coordinates with an arbitrary step.

Algorithms

The biggest problem, when searching for an algorithm, was to find a competent description of creating a surface from connected splines (boundary conditions) that would contain all the desired points on the height map (interpolation).
')
It should also be borne in mind that the number of parts on the surface can only decrease, relative to the initial data. It suffices to recall the Shannon-Kotelnikov theorem

An excellent description of the algorithm for creating a spline surface from a height map is given in the book “Computer geometry and computer graphics algorithms” by E. A. Nikulin . There is a lot of theoretical material and mathematics in this area (there is also a description of the approaches to the generation of surfaces by fractal algorithms, which makes it possible to create bulk surfaces).

I will not give here the mathematical calculations and code examples, because mathematics can be found in the book, and the implementation will be attached at the end of the article.

Processing results

As a result of processing a uniform grid, we get a fairly large file with spline coefficients:

1 33
3.30000000000000E+0001 1.00000000000000E+0000 -1.51788304147970E-0018 -1.95156391047391E-0018
0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000

1.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
1.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
2.16840434497101E-0019 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
2.16840434497101E-0019 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000

1.50000000000000E+0002 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000

1 34
3.40000000000000E+0001 1.00000000000000E+0000 8.67361737988404E-0019 2.38524477946811E-0018
0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000

1.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
1.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
2.16840434497101E-0019 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
2.16840434497101E-0019 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000

1.50000000000000E+0002 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000

1 35
3.50000000000000E+0001 1.00000000000000E+0000 -2.60208521396521E-0018 -3.03576608295941E-0018
0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000

1.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
1.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
2.16840434497101E-0019 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
2.16840434497101E-0019 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000

1.50000000000000E+0002 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000 0.00000000000000E+0000
…


That is, for every four points of the uniform grid we created our own spline, which is inseparable in the second derivative with all the neighboring ones. Now it is possible to determine the height at any point of the spline, and hence the entire map.

As you can see, the matrix of spline coefficients are quite sparse, so they are well compressed. You can perfectly save on the volume occupied by the card, without losing the speed of data processing.

Examples of the resulting surfaces:

findings

The ability to navigate the map with any step opens up great prospects for the development of application software. Algorithms for dynamic change of landscape detailing begin to work in full force ( LOD , MegaTexture ). The height is calculated with constant complexity (matrix multiplication).

Further, it is possible to create maps not in projections, but directly on the geoid, thereby simulating with precision the region of the earth or the entire surface of the earth. And all that enough imagination.

There are other algorithms to achieve this result. It all depends on the tasks. The proposed approach gives only a reason for reflection and a small impetus to the solution of the problem.

Generator sources on Delphi7