Введение
Если у Вас есть данные с неравномерной сеткой, важнейшим этапом в их обработке является преобразование в набор данных с равномерной сеткой. Данное преобразование необходимо для компьютерного моделирования в реальном масштабе времени или его приближении. Получение высоты непосредственно из неравномерной сетки является ресурсоемкой операцией.
В этой части будет рассмотрен алгоритм преобразования неравномерной сетки в равномерную с достаточно хорошим качеством получаемого результата.
Содержание работы
Часть 1. Подготовка данных
Часть 2. Генерация равномерной сетки
Часть 3. Создание аналитической поверхности
Цель подзадачи
Необходимо получить равномерную сетку из имеющегося набора изолиний. При этом все высоты должны быть согласованы (плавные переходы). На месте изолиний высота не должна искажаться.
Алгоритмы
Существуют различные алгоритмы получения равномерных сеток. Все из них имеют свои достоинства и недостатки, как и приводящийся ниже пример.
Так как равномерная сетка являлась промежуточным результатом работы, то ее создание проводилось заранее. Время работы алгоритма должно было укладываться в разумные пределы времени и расхода памяти.
Полученный результат уже можно использовать для игровых приложений, так как его точность не настолько критична.
Из предыдущей части мы фактически уже получили равномерную сетку с нужным разрешением, только большая часть высот на ней не вычислено. Эту задачу решает данная часть.
Рабочая карта
На рисунке 1 приведен пример равномерной сетки с незаполненными высотами. Цвет линии обозначает высоту, черный цвет — неизвестная высота.
Рисунок 1. Рабочая карта
Общее описание алгоритма получения высоты в произвольной точке
Регионы
Для лучшего распределения занимаемой памяти, необходимо разбить всю карту на регионы. Пройти по всем точкам, которые не имеют высоты и произвести расчет.
Расчет высоты
Найти три ближайшие точки с известной высотой в рабочей зоне (отрезок между искомой точной и найденной не должен пересекать и касаться изолиний). Вычислить высоту по имеющимся данным с помощью любого алгебраического метода (используется центр масс треугольника, где высота взята за вес).
Поиск ближайших точек
В этом месте следует упомянуть о книге В. Порева «Компьютерная графика». В ней даются базовые понятия компьютерной графики и приводится хороший алгоритм поиска ближайшей точки. Называется он «Поиск по периметру квадрата».
Оригинальный алгоритм ищет всего лишь две ближайшие точки, при этом возможны ситуации, когда найденные точки, частично или полностью, могут находиться за изолиниями от текущей. Вычисленная таким образом высота является неверной, поэтому алгоритм был расширен до трех точек с контролем пересечений с изолиниями. В этом случае исчезают, возникавшие ранее артефакты, в седловых точках (низина между несколькими доминирующими высотами) и на краях больших перепадов высот.
Рисунок 2. Оригинальный алгоритм. Красным обведены артефакты.
Рисунок 3. Модифицированный алгоритм.Весь код в статье приводить не буду, он будет дан ссылкой в конце статьи. Его там не много, комментариев для понимания достаточно.
Результаты обработки
В результате обработки получается равномерная сетка с необходимым разрешением. Пример приведен на рисунке 3. Она имеет плавные переходы между высотами. Вся карта с равномерной сеткой разбивается на регионы для уменьшения объема занимаемой памяти. Данные неравномерной сетки хранятся в списочных структурах.
Выводы
Генерация равномерной сетки достаточно ресурсоемкая операция, может проходить по несколько дней, в зависимости от требуемой точности и вычислительных мощностей. Алгоритм прекрасно распаралелливается, что позволяет проводить вычисления более эффективно. Использована модификация алгоритма В. Порева из книги «Компьютерная графика».
Исходные коды интерполятора
