Содержание к диссертации
Введение
1 Математические методы классификации трехмерных данных и генерации моделей земного рельефа 11
1.1. Лазерное и радарное сканирование: LIDAR и IFSAR (InSAR) 11
1.2. Существующие методы классификации пространственных данных 16
1.3. Матричное описание обработки данных (МООД) 21
1.3.1. Метод и критерии выделения связных множеств матричных элементов 22
1.3.2. Накопление ошибок 26
1.4. Метод виртуальной поверхности (МВП) 27
1.5. Точность методов МООД и МВП и сравнение с другими подходами 35
1.5.1. Сравнение МООД и МВП с методом SB-фильтра 36
1.5.2. Точность МООД как растрового приближения 38
1.5.3. Сравнение МООД и МВП с растровым методом 41
1.6. Экспериментальная проверка эффективности методов МООД и МВП для обработки трехмерных данных лазерного авиасканирования 44
2 Методика создания автоматизированных программных средств для обработки трехмерных данных 51
2.1. Главные особенности и проблемы обработки трехмерных данных 51
2.1.1. Неполнота 3D данных, сильная зависимость их качества от многих факторов 53
2.1.2. Специфичность методов классификации данных в трехмерном пространстве 60
2.1.3. Сложность визуализации трехмерных данных и методов их активной коррекции 60
2.1.4. Возможность эффективного трехмерного моделирования объектов. 61
2.2. Принципиальные компоненты комплекса по обработке 3D данных 61
2.3. Анализ требований к комплексам по обработке 3D данных 65
2.4. Базовая архитектура комплексов обработки 3D данных 67
2.4.1. Компоненты системного ядра 69
2.4.2. Компоненты функционального ядра 71
2.4.3. Компоненты интерактивного ядра 73
2.5. Схема представления трехмерных лидарных данных 75
3 Автоматизированный комплекс программных средств обработки данных LIDAR для компенсирования неполноты данных и получения изображений высокого разрешения (АКС-ЛИДАР) 78
3.1. Лазерное сканирование и измерение отражающей способности поверхностей 78
3.2. Архитектура комплекса АКС-ЛИДАР 82
3.2.1. Калибровка интенсивности 83
3.2.2. Сегментирование и преобразование координат 85
3.2.3. Растеризация изображений и обработка дефектов 87
3.2.4. Интерполяция и нормализация 88
3.3. Экспериментальные исследования комплекса АКС-ЛИДАР для получения ИК-изображений высокого качества 90
4 Автоматизированный комплекс программных средств для классификации данных лазерного сканирования и моделирования трехмерных поверхностей (АКС-ЛИДАР-ЗБ) 93
4.1. Лазерное измерение трехмерных координат точек отражения 93
4.2. Архитектура и программные компоненты комплекса АКС-ЛИДАР-ЗО . 94
4.2.1. Сортировка 95
4.2.2. Преобразование координат 95
4.2.3. Растеризация и интерполяция 96
4.2.4. Классификация 98
4.2.5. Просеивание 101
4.2.6. Интерфейс 101
4.3. Экспериментальные исследования комплекса АКС-ЛИДАР-ЗО для получения высокоточной трехмерной модели земного рельефа 104
5 Программные средства для визуализации и активной коррекции лидарных данных в процессе их обработки 108
5.1. Разработка эффективного средства визуализации трехмерных данных 108
5.2. Методы активной коррекции трехмерных данных 116
5.3. Совмещение трехмерных рельефов с двумерными изображениями 121
Заключение 123
Литература
- Существующие методы классификации пространственных данных
- Специфичность методов классификации данных в трехмерном пространстве
- Калибровка интенсивности
- Архитектура и программные компоненты комплекса АКС-ЛИДАР-ЗО
Введение к работе
Актуальность темы. Авиационные лидары позволяют получать трёхмерные координаты сотен миллионов точек земной поверхности. Нетривиальной задачей обработки лидарных данных для генерации высокоточных цифровых моделей рельефа (ЦМР, Digital Terrain Model) является автоматическая классификация отражений лазерного луча на отражения от земли и от зданий и растительности. Эта математическая и алгоритмическая проблема до сих пор не решена с нужной точностью. Отсюда следует практическая и тоже нерешенная оптимальным образом задача: результат автоматический обработки нужно быстро визуализировать и, при обнаружении ошибок классификации, исправить.
Производители лидарных систем (Leica, Optech) предоставляют программы для обработки данных, но эти программы несовершенны по результативности; они созданы не в России, а за рубежом, и их математическое и алгоритмическое наполнение обычно не раскрывается. Такие программные пакеты не позволяют гибко подходить к решению новых задач, например, организации обработки лидарных данных вместе с многоспектральными изображениями, или перенастройки алгоритмов на классификацию радарных отражений.
Для решения описанных проблем автором предложен более эффективный математический метод классификации лидарных данных, а также гибкая архитектура программного комплекса. Предложенный метод, основанный на адаптивном анализе наклонов поверхности, позволяет избежать наиболее серьезных проблем предшествующих методов и повышает точность классификации, при этом его производительность позволяет обрабатывать данные в потоковом режиме. В работе детально описаны математические методы и алгоритмы, которые лежат в основе созданных программ, что позволяет самостоятельно реализовать аналогичный комплекс, максимально адаптированный под решаемые задачи.
При автоматизации решения задач обработки используются схожие алгоритмы распознавания и классификации объектов, фильтрации дефектов, интерполяции и триангуляции поверхностей, преобразования координатных систем. Автор предлагает вариант создания базовой архитектуры комплексов по обработке 3D данных, которая позволяет оперативно составлять новую комбинацию из имеющихся программных модулей, необходимых для решения широкого спектра задач обработки.
В России существуют хорошо известные школы фотограмметрии (например, в МИИГАиК), которые используют высокоэффективные методы построения трёхмерных моделей земной поверхности по аэрофотосъёмке. Математические методы обработки лидарных данных, которые представляют собой неравномерное трёхмерное облако точек, еще не достигли совершенства методов, развитых в фотограмметрии.
Важной особенностью предложенного автором решения для обработки лидарных данных является то, что в процессе обработки трёхмерное облако точек лидарных отражений редуцируется до трех наиболее информативных двумерных матриц, к которым могут применяться эффективные алгоритмы и решения, накопленные в фотограмметрии.
Цель и задачи. Разработка и исследование методики обработки и классификации трехмерных данных лазерного сканирования. Для достижения этой цели в работе решались следующие задачи:
-
Анализ требований к методикам обработки лидарных данных; создание новых математических методов и алгоритмов обработки и классификации трехмерных данных лазерного сканирования.
-
Разработка и построение эффективной модели представления данных.
-
Создание принципиальной схемы обработки данных.
-
Создание программ для обработки лидарных данных, включая визуализацию результата и средства интерактивной коррекции, исследование их эффективности.
-
Внедрение в практику разработанной методики обработки и анализ результатов её использования.
Научная новизна работы. Автором создана и реализована новая методика обработки и классификации трехмерных геодезических данных лазерного сканирования, при этом:
-
Предложен новый математический метод классификации данных лазерного сканирования, основанный на адаптивном анализе наклонов поверхности, а также алгоритм его реализации. Метод позволяет выделять точки, не принадлежащие земному рельефу, и отличается высокой производительностью и эффективностью.
-
Построена новая модель представления трехмерных топографических данных, позволяющая преобразовать их в набор плоских матриц и, тем самым, использовать для обработки 3D данных математические методы и алгоритмы, ранее разработанные для 2D изображений.
-
Предложен технологичный подход к созданию программных комплексов на основе использования базовой архитектуры из трех компонент – универсального системного ядра, функционального (алгоритмического) ядра и интерактивного ядра, а также разработана детальная спецификация этих компонент.
-
Разработан ряд эффективных алгоритмических решений, обеспечивающих функциональную полноту созданного автором комплекса программ, включая трёхмерную визуализацию и коррекцию результатов.
-
Создан автоматизированный комплекс (программных) средств АКС-ЛИДАР для получения инфракрасных изображений высокого разрешения и комплекс АКС-ЛИДАР-3D для генерации точной цифровой модели рельефа (ЦМР). Тестирование показало значительные преимущества разработанных методики и программ по сравнению с другими средствами обработки.
Практическая ценность работы. Разработка и реализация методов для обработки данных лидарной топографической съемки – новой и бурно развивающейся технологии трехмерных изображений – является весьма актуальной задачей. Улучшение точности цифровой трехмерной модели рельефа имеет большое практическое значение для топографии, гравиметрии, геоморфологии, моделирования наводнений, оползней и других физических процессов на рельефе.
Методика и программы, разработанные автором, прошли тестирование при получении инфракрасных изображений и трехмерных моделей рельефа с точностью высот 9-14 сантиметров для 20 тысяч кв. километров земной поверхности, сканированной самолетным лидаром с высоты около километра (акт внедрения ФГУП «Уралгеоинформ» от 10.08.2011).
Методы исследования. В диссертации применялись методы математического и численного моделирования, а также методы статистического анализа для определения точности полученных трехмерных моделей.
Апробация работы. Работа была доложена и обсуждена на:
1-й международ. научно-практ. конф. «Современные информационные технологии и ИТ-образование» (МГУ, 19-23 сентября 2005);
2-й международ. научно-практ. конф. «Современные информационные технологии и ИТ-образование» (МГУ, 18-21 декабря 2006);
научном семинаре в МИИГАиК (21 декабря 2006, Москва);
3-й международ. научно-практ. конф. «Современные информационные технологии и ИТ-образование» (МГУ, 8-11 декабря 2008);
научном семинаре в НИВЦ МГУ (19 февраля 2009);
научном семинаре кафедры АСВК ВМиК МГУ (17 сентября 2009);
научном семинаре в МИИГАиК (8 декабря 2010, Москва).
Cодержание и результаты диссертационной работы освещены в 7 публикациях [1-7], включая 3 статьи в изданиях, рекомендованных ВАК по специальности диссертации [1,2,3], 1 статья (в соавторстве) в журнале из списка ВАК по вычислительной технике и информатике [4] и 3 статьи в сборниках международных конференций [5,6,7].
Объем и структура диссертации. Общий объём диссертации, состоящей из введения, пяти глав, заключения и списка литературы – 133 страницы, в том числе 48 иллюстраций и 3 таблицы. Список литературы содержит 93 наименования.
Существующие методы классификации пространственных данных
Объем и структура диссертации. Общий объём диссертации, состоящей из введения, пяти глав, заключения, списка литературы и акта о внедрении разработки - 136 страниц, в том числе 48 иллюстраций и 3 таблицы. Список литературы содержит 93 наименования. Основные результаты работы. Результаты диссертации, выносимые на защиту: Разработан математический метод классификации данных лазерного топографического сканирования, основанный на адаптивном анализе наклонов поверхности, а также алгоритм его реализации. Метод позволяет выделять точки, не принадлежащие земному рельефу, и отличается высокой производительностью. Сделан анализ результатов применения метода к тестовому набору данных и сравнение его с существующими методами классификации. 2. Построена новая модель представления трехмерных топографических данных, позволяющая преобразовать их в набор плоских матриц. Понижение размерности позволяет применить математические методы и алгоритмы, разработанные для двумерных изображений, упростить анализ идентификационных признаков объектов в данных, значительно сокращает временные затраты на обработку и снижает требования к оборудованию. Проведено исследование погрешности такого представления и доказана обоснованность его применения.
Предложен новый подход к построению программных комплексов для обработки трехмерных топографических данных лазерного сканирования. В рамках подхода разработана спецификация универсальных компонент, реализующих часто используемые алгоритмы и подзадачи обработки, такие как интерполяция, классификация, растеризация, визуализация данных. Это позволяет интегрировать реализованные компоненты в необходимой последовательности, в зависимости от поставленных задач обработки данных. При разработке новых программ такая технология значительно сокращает этапы анализа, проектирования и тестирования.
На основе предложенного подхода и разработанных моделях и методах были реализованы программные комплексы АКС-ЛИДАР и АКС-ЛИДАР-ЗБ для обработки топографических данных лазерного сканирования, получения инфракрасных изображений высокого разрешения и моделирования трехмерных поверхностей. Эффективность предложенных решений и точность полученных моделей была экспериментально проверена автором при использовании его программ для обработки свыше 20 000 км2 земной поверхности. Глава 1
Математические методы классификации трехмерных данных и генерации моделей земного рельефа
Данная глава посвящена эффективным методам, классификации множества трехмерных точек, полученных с помощью лазерного топографического сканирования. Описанные методы позволяют отфильтровать данные, соответствующие земной поверхности, и даже интерполировать промежутки между ними.
Лазерное и радарное сканирование: LIDAR и IFSAR (InSAR) Программные средства и математические методы обработки двумерных изображений или цифровых фотографий составляют обширную область вычислительной математики и программирования, активно развивающуюся уже несколько десятилетий [25,28,41,60,73,86].
В последние годы распространились трехмерные данные нового типа — лидарные [14,22,23]. Первый коммерческий лидар (Light Detection And Ranging, http://www.csc.noaa.gov/crs/rs_apps/sensors/lidar.htm) авиационного базирования появился в 1993 году. Лидарные авиасистемы совершили переворот в генерации трехмерных моделей земной поверхности, позволив получать большие объемы геодезических измерений с горизонтальным шагом 1-2 метра и точностью по высоте 10 см при уровне достоверности 95% (таб. 1).
Точность различных методов сбора 3D данных [75, 85] Авиационный LIDAR позволяет сканировать земную поверхность лазерными инфракрасными лучами с частотой 100-150 тысяч лазерных импульсов в секунду. Самолет, летящий на высоте около километра, сканирует полосу шириной около 0.5 км. Плотность распределения сканируемых точек обычно близка к 1 выстрелу на кв. метр земли. Абсолютная точность определения высоты 10-15 см, относительная (по отношению к соседней точке) — около 5 см. Точность определения плановых координат задается диаметром лазерного луча и близка к 1 метру при сканировании с высоты около 1 км. Требования к точности итоговых результатов (трехмерной модели земли), используемых, например, для моделирования наводнений, очень высоки: по наиболее распространенным стандартам, среднеквадратичная ошибка результатов по высоте должна быть меньше 18.5 см [32,45,47,49].
Лидары используются как для практических задач (например, проектирование нефтепроводов [17]), так и для научных проблем, например, изучения геологических сдвигов [50]. Запускаются спутники для лазерного сканирования Земли, Луны и Марса. Лидары используются для построения трехмерных моделей городов, стыковки космических аппаратов и автономной навигации роботов [35,53,82]. Многочисленные примеры применения трехмерных лидарных данных включают топографическое моделирование земной поверхности [17,22,26]; проектирование новых зданий и документирование памятников [3,23]); контроль за изготовлением судов и самолетов; ликвидация последствий катастроф; геология и геоморфология [57,89,63].
Лазерный сканер генерирует для объекта набор трехмерных координат -обычно с атрибутом интенсивности отражения в каждой точке [7-12,22]. Чувствительность приемного устройства лидара такова, что оно может ловить не одно, а два и более отражений одного луча: например, не только отражение В от вершины дерева («first return» в англоязычной литературе), но и отражение луча от земной поверхности в точке А, к которой лазерный луч проник сквозь
Специфичность методов классификации данных в трехмерном пространстве
Матричное представление позволяет не только лучше традиционных методов классифицировать лидарные отражения, но и отслеживать все преобразования, которые совершаются над данными и оценивать накопление сопутствующих ошибок.
Количество последовательных процедур обработки матрицы 3D данных может исчисляться десятками. Каждая процедура меняет значение элемента и, строго говоря, вносит ошибку в это значение. В конечном варианте матрицы часть элементов окажется пришедшей непосредственно из лидарных измерений, а часть - претерпевшей множественные процедуры обработки и интерполяции, и им можно доверять лишь в некоторой степени. Как отследить историю преобразования каждого пиксела и как оценить накапливающуюся ошибку обработки в любом пикселе?
Хотя трехмерная матрица кажется неудобным для работы объектом, но на практике её можно свести к достаточно удобной двумерной матрице упакованной побитно. Значение каждого элемента будет содержать в разных битах информацию об использованных процедурах обработки данного пиксела.
Введём вектор ошибки Sj , каждая компонента которого соответствует средней ошибке, вносимой j-операцией обработки. В рамках развитого формализма мы легко можем описать процесс накопления ошибок в ходе обработки матрицы данных. Зная матрицу операций и вектор ошибки, для каждого і,к-пиксела можно записать уравнение суммарной ошибки
В реальности всегда можно найти объекты (дома сложной формы, пологие кусты или кластеры деревьев), для которых не выполняются критерии структуры или связного множества. Для убирания таких неструктурированных объектов в комплексе АКС-ЛИДАР-ЗБ разработан и применяется новый математический метод классификации лазерных отражений, соответствующих земной поверхности - метод виртуальных поверхностей [7].
В статье [7] рассмотрен метод виртуальной поверхности для фильтрации лидарных данных. Этот метод обладает положительными качествами двух известных методов: SB-фильтра [88] и его адаптивной версии [83], а также IPF-метода [61]. При этом метод виртуальной поверхности избегает наиболее серьезных недостатков этих алгоритмов.
Метод виртуальной поверхности совмещает фильтрацию и интерполирование, как и IPF-метод, получая в результате виртуальную поверхность, близкую к реальной земной поверхности. Как и в SB-фильтре, важным элементом описываемого метода является фильтрующий элемент в виде поверхности шара, или, в более общем варианте, поверхности двухосного эллипсоида. В отличие от SB-фильтра и IPF-метода, метод виртуальной поверхности применяется не к исходным лидарным точкам, а к уже растеризованным данным (лидарным точкам, рассортированным по пикселам). Метод виртуальной поверхности обладает рядом заметных преимуществ по сравнению с SB-фильтром и IPF-методом, и, в сочетании с другими фильтрами, был с успехом применен для сортировки большого объема лидарных данных.
Рассмотрим в качестве образца исходный файл лидарных отражений, полученных на участке 1200 х 1800 метров. Каждая строчка файла содержит данные о трехмерных координатах первого и последнего отражений. Для эффективного применения метода виртуальной поверхности к данному файлу нужно предварительно применить процедуры растеризации и интерполяции.
Отсортируем начальный файл лидарных точек в пикселы размером 2 метра, что дает растеризованную картину 600 х 900 пикселов. Высота каждого пиксела принимается равной минимальной величине из высот лидарных точек, расположенных в данном пикселе.
Вышеописанная процедура применяется отдельно к первому и последнему лидарным отражениям. Таким образом, мы получаем две поверхности, представленные в виде массивов. Каждый массив эквивалентен черно-белому изображению, где яркость пиксела соответствует высоте трехмерной поверхности. Таким образом, описанный метод применим и к обычным оптическим или любым другим черно-белым изображениям.
Первой процедурой классификации точек лидарных отражений является определение и извлечение зданий. Для таких объектов эффективен градиентный метод. В нем здание определяется как достаточно большой объект с замкнутой границей, при этом граница здания определяется как набор пикселов, где высота последнего отражения испытывает значительный скачок ( 1 метра). После извлечения зданий образовавшиеся пустоты затягиваются с использованием информации о высоте краевых пикселов. Итоговый файл лидарных отражений содержит информацию о земной поверхности, растительности и о небольших зданиях, для которых не выполняется градиентный критерий. Тем самым, непростая для многих фильтров проблема удаления больших зданий решается отдельно от МВП.
Калибровка интенсивности
Собранные лидарные данные могут представлять собой набор файлов большого размера, каждый из которых содержит результаты авиасканирования за день. Такой файл может состоять из многих миллионов точек отражений, распределенных в пространстве на десятки километров. Это облако точек дается в стандартной для данной аппаратуры географической координатной системе, а результат нужно получить, возможно, в совсем другой системе координат. Поэтому на первом этапе данные преобразуются в нужную координатную систему, калибруются и нормируются, очищаются от очевидных дефектов и сегментируются в участки или области заданного размера, с которыми уже могут работать блоки интерполяции, классификации и моделирования. Под участком заданного размера понимается облако лидарных точек, которое расположено в пространственном параллелепипеде, размеры которого задаются с учетом цели обработки и возможностей применяемых компьютеров. Рассматриваемые ниже программы испытывались обычно на участках 1.2 х 1.8 км в горизонтальной плоскости и с интервалом по вертикали от минимальной до максимальной высоты рельефа (с учетом зданий) на данном участке. В каждом таком файле содержится около миллиона точек первого отражения и столько же - последнего.
Что можно извлечь из облака «сырых» данных? Учтем, что воспринимать трехмерное облако точек без привычных ориентиров и референтных объектов для человеческого глаза неудобно. Если мы захотим рассмотреть такое трехмерное облако в деталях, то нам для этого потребуется соответствующее программное обеспечение. Оптимальным для многих случаев является проектирование трехмерного облака в набор двумерных изображений, хорошо передающих информацию об объекте. Для лидарных отражений от здания потребуется много проекций с разных ракурсов; для земной поверхности плоскость проекции задается естественной горизонтальной плоскостью.
Спроектируем трехмерный набор точек на горизонтальную растеризованную плоскость. В обработке данных авиасканирования типичен пиксел в 2 метра для рельефа и 1 метр для интенсивности отражений, хотя разработанные программы использовались и для обработки лидарных данных с размером пиксела для рельефа в 1 метр и 0.3 метра. Каждый пиксел содержит в среднем 1-2 отражения, из которых мы будем определять всего три величины: максимальная высота отражения в пикселе, минимальная высота отражения, средняя величина интенсивности отражения.
На первый взгляд кажется, что трехмерное облако точек после проекции на плоскость так упростилось, что с формальной точки зрения ничем не отличается от двумерного изображения, где яркость вполне аналогична параметру высоты, тем самым все методы обработки двумерных изображений могут переноситься без изменений на трехмерные проецированные данные. Где-то это верно, где-то нет.
Опыт работы с лидарными данными позволяет нам сформулировать главные особенности 3D данных LIDAR (даже спроецированных на двумерную плоскость), отличающие их от классических 2D изображений:
1. Неполнота 3D данных; сильная зависимость их качества от многих факторов. Разреженность трехмерных изображений, вызванная их векторным представлением и наличием пробелов в данных из-за сложностей в функционировании лидаров, тогда как растровые изображения, как правило, полны; неоднородность трехмерных изображений, связанная со сбоями в работе оборудования или лидарной аэросъемкой, проведенной в разные времена года.
2. Специфичность методов классификации данных в трехмерном пространстве. Принципиальное отличие значимости высоты объекта от значимости его цвета и разной сферы их применения в практических задачах; наличие множества значений высот для каждой точки поверхности, обусловленных последовательными отражениями луча от частично проницаемых поверхностных объектов, тогда как на двумерных изображениях цвет имеет один слой.
3. Сложность визуализации 3D данных и методов их активной коррекции.
4. Возможность эффективного трехмерного моделирования объектов.
Эти особенности одновременно характеризуют специфические проблемы, которые возникают при обработке лидарных данных. Имеющиеся решения для потоковой обработки и распознавания двумерных изображений малоприменимы к трехмерным из-за обсуждаемых особенностей 3D данных [12]. Рассмотрим детальнее эти особенности.
Неполнота 3D данных, сильная зависимость их качества от многих факторов Принципиальная неполнота трехмерных данных связана с геометрией сканирования и потерей части отражений. При сканировании из одной точки или сверху, как в авиасканировании, неполнота бывает четырёх типов:
1. Неполнота представления невидимых частей объекта: у дома, сканируемого сверху, большинство отражений приходится на крышу, и лишь малая часть — на вертикальные стены.
2. Измерение координат точки отражения луча возможно только при хотя бы частичном отражении луча назад - к приёмнику, что происходит при квазидиффузном отражении от объекта. Но в случае падения на поверхность воды или стекла, луч может отразиться полностью в сторону зеркальным образом, и приемник не зарегистрирует обратного сигнала.
Архитектура и программные компоненты комплекса АКС-ЛИДАР-ЗО
Даже лучшие автоматизированные программные средства могут ошибаться и для исправления их ошибок требуется вмешательство человека.
Отметим на рис. 35 два углубления в правом верхнему углу, которые соответствуют дефектам «подземных отражений», связанных с отражением лазерного луча от стекол домов, расположенных в густом лесу, что обусловило недостаточную эффективность работы фильтров таких дефектов. Именно для таких случаев в комплексе АКС-ЛИДАР-ЗБ разработан удобный интерфейс активного вмешательства, который позволяет в течение 1-2 минут пересчитать модель данного участка с уточнёнными параметрами и избавиться от этих углублений.
При этом, для обнаружения ошибки, необходима визуализация трехмерных поверхностей в процессе их обработки и генерации. Разработка эффективного средства визуализации трехмерных данных
Визуализация цифровых моделей рельефа, полученных при помощи лазерного топографического сканирования, является важным элементом комплекса по обработке данных. Она позволяет оценить промежуточные и конечные результаты работы, чтобы скорректировать обработку, если есть необходимость. Кроме того, визуализация может быть полезна не только в рамках комплекса по обработке, но и как отдельный сервис предоставляемый заказчику (в том числе, для построения анимационных моделей с использованием цифрового рельефа). Регулярная структура ЦМР, полученной на этапе классификации, позволяет воспользоваться при рендеринге иерархической структурой данных.
Для эффективной реализации необходимо, кроме стандартных алгоритмов оптимизации на CPU, использовать, по возможности, ресурсы современных графических адаптеров (GPU), которые в последнее время стали значительно превосходить CPU по вычислительной мощности. Так как один из важнейших принципов современной машинной графики гласит «Batch, batch, batch» [91], то обрабатываемая ЦМР разбивается на участки фиксированного размера 2п+1, например 33x33 точек (1089 вершин), имеющие совмещенные краевые вершины. Каждый такой участок содержит до 2048 треугольников и рисуется одним вызовом графического API минимизируя расходы, связанные с обращениями к АРІ. Все 1089 вершин должны умещаться в предварительном кэше трансформаций GPU, что также ускоряет рендеринг. В модуле GUI используется отсечение по усеченной пирамиде видимости, которое позволяет уменьшить трафик к адаптеру за счет участков находящихся заведомо вне поля зрения. Причем, статус видимости для участков пересчитывается, только если положение камеры изменилось (минимизация вычислений CPU при анимации). Еще одним важным этапом является уменьшение количества рисуемых треугольников на участках при увеличении расстояния до камеры; угол между осью зрения и поверхностью участка в текущей реализации не учитывается. Уровень детализации (level of detail) выбирается сразу для всего участка 33x33 и может быть равен 0, 1, 2, 3 для, соответственно, 2048, 512, 128, 32 треугольников (каждый раз пропускается половина вершин по каждой оси).
Цвет вершины зависит от ее относительной высоты [8]. Нормаль в вершине вычисляется как нормализованная сумма единичных нормалей, прилегающих к вершине треугольников; вес суммируемой нормали пропорционален углу, который образован этой вершиной. Все эти вычисления делаются при предварительной обработке, после которой вершинные данные рельефа загружаются в память видеокарты в виде статических VBO (расширение GL_ARB_yertex_buffer object), если такая возможность поддерживается.
Для достижения хорошей производительности 3D движка, необходимо обеспечить высокий процент попадания в кэш трансформированных вершин (post T&L cache), так как на регулярном рельефе каждая вершина принадлежит в среднем шести треугольникам, и трансформировать ее шесть раз не слишком выгодно. Видеоадаптер будет использовать кэш только в случае обращения к вершинным данным по индексам. Кэш устроен по принципу FIFO, и его размер может быть от 6 вершин (ATI Radeon серии 7000) до 45 вершин (NVIDIA GF7). Чтобы обеспечить хорошее попадание и на небольших кэшах, каждый участок 33x33 разбивается на смежные полосы шириной 5 вершин (рис. 39).
Сначала в кэш помещаются вершины первой линии 0-4, это делается заданием трех фиктивных треугольников (0-1-1), (2-3-3), (3-4-4). Затем задаются сами треугольники в порядке (0-5-6), (6-1-0), (1-6-2), (7-2-6), и т.д. При таком алгоритме, в кэше всегда находятся нужные нам вершины предыдущей линии и каждый треугольник будет обходиться в среднем меньше, чем в одну трансформированную вершину; в данном примере коэффициент составит 1.55 треугольников за вершину на всем участке. При использовании полос шириной 33 на более крупном кэше можно добиться 1.88 тр/вершину, что близко к теоретическому максимуму.
По такому принципу для каждого уровня детализации создается свой массив индексов (всего 4 массива для 33x33), каждый из которых тоже помещается в память видеокарты. Используются списки треугольников, а не полосы (strips), чтобы избежать лишних фиктивных полигонов. В итоге, время, затраченное на предварительную подготовку вершинных данных, для ЦМР объемом 4 миллиона точек, на машине Р4 2.8GHz, составило 1.4 секунды. Готовые данные выводятся командой glDrawElements.
В случае использования этого кода для анимации, например, движения каких-то объектов над рельефом, может возникнуть ситуация, когда камера, а, следовательно, и рельеф, не меняли своего положения между последовательными фреймами. Чтобы не перерисовывать рельеф с нуля, логично было бы сохранять буферы цвета и глубины для отрендеренного рельефа и использовать их повторно. Возможность быстрой работы с буфером появилась с расширением GL_ARB_pixel_buffer_object (входит в OpenGL 2.0), которое позволяет использовать память видеоадаптера при работе с растровыми операциями glReadPixels/glDrawPixels. Для примера, выигрыш в fps, при использовании этого приема на GeForce 6200, составил 73%. Движок замеряет производительность glDrawElements и glDrawPixels в миллисекундах, а затем выбирает более быстрый метод, так как далеко не всегда растровые операции реализованы в GPU достаточно эффективно. Несмотря на то, что внутренний формат буфера глубины является форматом с плавающей точкой (как правило 24-битным), заполнение его из пиксельного буфера формата GLFLOAT происходит очень медленно, видимо, происходят какие-то дорогие преобразования типа данных, хотя ни в MSDN, ни в литературе описания этого явления найти не удалось [21]. Использование буфера формата GL_UNSIGNED_INT ведет к незначительной потере точности, но зато он работает в шесть раз быстрее.
