Введение

Точное физическое моделирование требует высокополигональных карт. Чем выше точность карты, тем больший объем памяти она занимает и тем больше приходится обрабатывать данных, чтобы получить высоту. Сплайновая интерполяция позволяет получить сетку любого разрешения, с любым, удобным в данный момент, шагом по широте и долготе.

Содержание работы

Часть 1. Подготовка данных
Часть 2. Генерация равномерной сетки
Часть 3. Создание аналитической поверхности

Цель подзадачи

Получить из равномерной сетки сплайновую поверхность, содержащую все исходные точки. Реализовать вычисление высоты по двум координатам с произвольным шагом.

Алгоритмы

Самой большой проблемой, при поиске алгоритма, было найти грамотное описание создания поверхности из связанных сплайнов (граничные условия), которые бы содержали все искомые точки карты высот (интерполяция).

Также следует учитывать, что количество деталей на поверхности может только уменьшаться, относительно начальных данных. Достаточно вспомнить теорему Шеннона-Котельникова

Отличное описание алгоритма создания сплайновой поверхности из карты высот приведено в книге Е. А. Никулина “Компьютерная геометрия и алгоритмы машинной графики”. В ней очень много теоретического материала и математики по данному направлению (есть и описание подходов к генерации поверхностей фрактальными алгоритмами, что дает возможность создавать объемные поверхности).

Не буду приводить здесь математические выкладки и примеры кода, потому что математику можно найти в книге, а реализация будет приложена в конце статьи.

Результаты обработки

В результате обработки равномерной сетки мы получим достаточно большой файл с коэффициентами сплайнов:

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 

…

То есть, для каждых четырех точек равномерной сетки мы создали свой сплайн, который неразрывен по второй производной со всеми соседними. Теперь есть возможность определить высоту в любой точке сплайна, а значит и всей карты.

Как видно, матрицы коэффициентов сплайна достаточно разрежены, поэтому хорошо поддаются сжатию. Можно отлично сэкономить на объеме, занимаемым картой, без потери скорости обработки данных.

Примеры получившихся поверхностей:

Выводы

Возможность перемещаться по карте с любым шагом открывает большие перспективы по разработке прикладного программного обеспечения. Алгоритмы динамического изменения детализации ландшафта начинают работать в полную силу (L.O.D, MegaTexture). Высота вычисляется с постоянной сложностью (перемножение матриц).

Далее можно создавать карты не в проекциях, а прямо на геоиде, тем самым моделировать с высокой точностью регион земли или всю поверхность земли. И все, на что хватит фантазии.

Существуют и другие алгоритмы, позволяющие добиться такого результата. Все зависит от поставленных задач. Предложенный подход дает лишь повод для размышлений и небольшой толчек к решению поставленной задачи.

Исходники генератора на Delphi7

Генерация аналитических поверхностей на примере карт. Часть 3