1.3. Генерация рельефа для виртуальных глобусов
В основе визуализации рельефа для виртуальных глобусов лежат те же алгоритмы, что и для «плоского» рельефа, но с некоторыми модификациями.
При визуализации рельефа можно выделить две основные фазы: (1) генерация геометрии рельефа и (2) текстурирование и освещение этой геометрии.
Рассмотрим подробнее первую фазу. Вторая будет освещена во второй главе.
1.3.1. Генерация трехмерного рельефа
Существует множество разных методов создания трехмерного рельефа. Рассмотрим основные из них.
Полигональные поверхности. Трехмерный рельеф аппроксимируется полигональной поверхностью. Высота точек поверхности берется из карты высот. Есть несколько вариантов построения полигональной поверхности:
регулярная сетка — вершины расположены через равные интервалы. Каждому пикселю карты высот соответствует своя вершина сетки. Это наиболее простой метод;
нерегулярная сетка (TIN, Triangular Irregular Network) — в местах быстрого перепада высот плотность вершин делается выше, в более ровных местах — ниже. Это позволяет уменьшить количество полигонов, но требует большего времени на построение.
Генерация, использование и текстурирование нерегулярных сеток – довольно сложная задача. Они могут дать выигрыш, если большая часть рельефа плоская и сам рельеф небольшого размера.
Поэтому на практике для больших территорий применяются регулярные сетки, которые удобнее в работе и проще строятся. А уменьшение количества полигонов можно достичь с помощью уровней детализации. К тому же развитие производительности видеокарт сводит на нет преимущества нерегулярных сеток [62].
Уровни детализации (LOD, Level of Detail). Но для больших территорий использование одной большой полигональной поверхности не выгодно. Большая 3D-модель рельефа занимает видеопамять и процессорное время. В каждый момент времени видна лишь небольшая часть большой территории. А если отдалиться и посмотреть на всю территорию целиком, то детализация поверхности будет слишком избыточной.
Поэтому применяются уровни детализации рельефа. Издалека виден грубый рельеф, а при приближении детализация полигональной поверхности увеличивается.
Существуют алгоритмы для непрерывных уровней детализации. Например, ROAM (Real-Time Optimally Adapting Meshes) [63]. Заранее строится двоичное дерево, каждый узел которого содержит один треугольник, а два дочерних узла – половинки этого треугольника.
Во время работы приложения происходит динамическая подстройка сетки –рядом с наблюдателем число треугольников делается выше, а чем дальше, тем ниже. Это происходит в реальном времени при перемещении наблюдателя. Вычисляются ошибки отклонения вершин, и при необходимости треугольник разбивается на две половины.
При этом расчет сетки полностью ложится на центральный процессор. Поэтому этот метод проигрывает по быстродействию другим алгоритмам, хотя и обеспечивает большую точность.
Наиболее часто применяются дискретные уровни детализации. Формируется пирамида уровней детализации. Каждый следующий уровень имеет разрешение в 2 раза выше. Каждый уровень детализации разбивается на тайлы равного размера. Издалека виден грубый рельеф с низким разрешением. При приближении он заменяется на 4 тайла с более высоким разрешением и т.д. Каждый тайл имеет свою карту высот и свою текстуру.
В этой ситуации возникает проблема сшивки тайлов. Если два находящихся рядом тайла имеют разные уровни детализации, то между ними могут возникать щели. Это решается добавлением «юбок» к тайлам. Юбка — вертикальная полоска треугольников по периметру тайла (рис. 1 .7).
В работе Livny Y., Kogan Z., El-Sana J. предложен алгоритм бесшовного стыка тайлов [64].
В случае дискретных уровней детализации может возникать эффект скачков (popping), когда при смене тайлов разных уровней детализации виден резкий скачок некоторых частей рельефа. Этот эффект проявляется при медленной подгрузке новых тайлов с диска или из интернета. Одно из возможных решений: плавная интерполяция между тайлам. Она, конечно, будет замета, но не будет сильно резать глаза.
|
Рис. 1.7. Слева - щель между тайлами, справа - закрытие щели с помощью юбки
|
|
Geometry Clipmaps. Особняком стоит алгоритм Geometry Clipmaps [65]. Он не использует разбиение геометрии на тайлы. Вокруг наблюдателя генерируется набор плоских вложенных регулярных полигональных сеток. Чем дальше от наблюдателя, чем ниже разрешение сетки. Параметры подбираются так, чтобы размер треугольников на экране был примерно одинаковым. При движении наблюдателя сетки движутся вместе с ним (рис. 1 .8).
Высота вершин сетки вычисляется в вершинном шейдере на основе карт высот. Используется пирамида карт высот разного разрешения для разных сеток.
|
Рис. 1.8. Вложенные сетки в алгоритме Geometry Clipmapping
|
|
При движении наблюдателя сетки движутся вместе с ним. При этом текстура рельефа и карта высот динамически обновляются: часть текстуры удаляется, и на ее место подгружается кусок с диска. Используется тороидальный доступ. Это позволяет использовать текстуры и карты высот теоретически неограниченного размера.
1.3.2. Разбиение поверхности глобуса на тайлы
В методе дискретных уровней детализации необходимо разбивать каждый уровень на прямоугольные кусочки — тайлы. В случае «плоского» рельефа естественным является рекурсивное разбиение пространства на квадраты. В случае глобуса можно придумать много разных вариантов разбиения [48]. Вот некоторые из них:
разбиение правильного многогранника. За основу берется, например, тетраэдр. Далее каждая грань рекурсивно разбивается на треугольники. При добавлении новых вершин они сдвигаются к поверхности эллипсоида;
«надутый куб». За основу берется куб. Для каждой грани куба формируется регулярная сетка нужного разрешения. Затем каждая вершина сдвигается к поверхности эллипсоида (рис. 1 .9);
разбиение HEALPix (Hierarchical Equal Area isoLatitude Pixelization), при котором все пиксели занимают одинаковую площадь (рис. 1 .10) [66];
географическая сетка. Разбиение на тайлы происходит вдоль меридианов и параллелей (рис. 1 .11).
1.3.3. Географическая система координат Эллипсоид и геоид
Для задания положения точек на глобусе обычно используется географическая система координат: тройка чисел (долгота, широта, высота). Но на видеокарте все расчеты происходят в прямоугольной декартовой системе координат. Поэтому необходимо задать связь между этими системами координат.
Земля имеет сложную пространственную форму. Для упрощения математических вычислений необходимо уметь описывать форму Земли с разной степенью точности. Самое простое приближение — сфера — подходит только для самых мелких масштабов. Часто используется следующее приближение — эллипсоид (рис. 1 .12). Эта геометрическая фигура образована вращением эллипса вокруг малой полуоси.
|
Рис. 1.9. Разбиение «надутый куб»
|
|
|
Рис. 1.10. Разбиение HEALPix
|
|
Рис. 1.11. Разбиение по географической сетке
|
Ещё одно приближение – геоид, эквипотенциальная поверхность гравитационного поля, совпадающая с морями и океанами и условно продолженная вглубь материков. Поверхность геоида в каждой точке перпендикулярна линии отвеса.
Т.к. эллипсоид по форме не совпадает с геоидом, то один и тот же эллипсоид можно двигать относительно геоида, компенсируя погрешности в одном месте и увеличивая в другом месте. Датум — это набор параметров, которые задают смещение эллипсоида относительно геоида [67]. Датумы могут быть локальными, т.е. обеспечивать наилучшую аппроксимацию геоида в данном месте (например, Североамериканский датум NAD83). Также датумы могут быть глобальными — минимизировать погрешность для всей Земли. В настоящее время наиболее часто используется датум 1984 года World Geodetic System (WGS84). Например, он используется в системе позиционирования GPS.
|
Рис. 1.12. Геоид и эллипсоид
|
|
В системе WGS84 используется эллипсоид с параметрами: экваториальный радиус — 6378137м, полярный радиус — 6356752.3142м. Географические координаты задаются относительно этого эллипсоида [68].
Мировая декартова система координат (МСК) задается следующим образом. Ось Z проходит через северный полюс, плоскость XY — через экватор, плоскость XY — через нулевой меридиан.
Для перехода от эллипсоида к геоиду необходимо в каждой точке задать высоту геоида над эллипсоидом. Это отклонение невелико и составляет ± 200 м. Существуют модели для расчета этого отклонения. Часто используется модель EGM96. Например, она применяется для корректировки высот в системе позиционирования GPS. Также сейчас существует усовершенствованная модель EGM2008.
Учет формы Земли при построении виртуального глобуса
Форма полигональной поверхности глобуса зависит от цифровой модели рельефа (ЦМР), которая используется при его построении. Если ЦМР не задана, то поверхность принимает форму эллипсоида. Если используется ЦМР, то вершины полигональной сетки сдвигаются по нормали на заданную высоту.
Современные ЦМР, такие как SRTM и ASTER GDEM (приложение А), содержат высоту рельефа над геоидом EGM96. Поэтому для сдвига вершин полигональной сетки нужно делать поправку на высоту геоида над эллипсоидом. Существуют программные библиотеки для проведения расчетов.
При визуализации 3D-данных на глобусе нужно учитывать, как задана высота точек. Есть три альтернативы (рис. 1 .13):
высота задана относительно эллипсоида;
высота задана относительно геоида (относительно уровня моря);
высота задана относительно рельефа.
Имея ЦМР и геоид EGM96, можно корректно показать расположение геопространственных 3D-данных.
Таким образом, точность представления данных зависит в первую очередь от самих данных.
|
Рис. 1.13. Высота точки относительно разных поверхностей
| Вычисление нормали
Во многих задачах связанных с визуализацией часто нужно вычислять нормаль к поверхности эллипсоида в точке. Нужно различать геоцентрическую нормаль и геодезическую нормаль (рис. 1 .14). Геоцентрическая нормаль лежит на линии, соединяющей центр эллипсоида и данную точку на поверхности. Геодезическая нормаль — честный перпендикуляр к поверхности.
Геодезическая нормаль вычисляется по формуле:
 ,
|
(1.1)
|
 ,
|
(1.2)
|
где  – вектор нормали, m – вспомогательный вектор, (a, b, c) – радиусы эллипсоида, (xs, ys, zs) – точка на поверхности эллипсоида.
|
Рис. 1.14. Геоцентрическая и геодезическая нормали
|
|
Преобразование географических координат в декартовы довольно просто. Иногда бывает нужно и обратное преобразование. Но оно значительно сложнее и может приводить к неоднозначностям.
1.3.4. Особенности виртуальных глобусов
В случае рендеринга виртуального глобуса и данных на глобусе нужно учитывать ряд нюансов и особенностей, которых нет в плоском варианте [48].
Точность координат. В настоящее время видеокарты в основном используют при расчетах тип данных с плавающей точкой одинарной точности (float), который имеет примерно 7 значащих десятичных цифр. Радиус Земли также имеет 7 значащих цифр. Это приводит к ошибкам округления при проведении матричных преобразований. Визуально это проявления в «дрожании» (jittering) объектов рядом с камерой.
Проблема частично решается использованием операций с двойной точностью на CPU. Результаты операций далее переводятся в одинарную точность перед отправкой на GPU.
Точность буфера глубины. Буфер глубины (z-buffer) хранит глубину отрисованных пикселей экрана. В случае виртуального глобуса наблюдатель может смотреть на глобус целиком из космоса, а может подлетать к поверхности глобуса. Это приводит к необходимости иметь очень близко ближнюю плоскость отсечения и очень далеко дальнюю плоскость отсечения. Глубина пикселя зависит от этих расстояний. При вычислении глубины она округляется из-за ограниченной точности буфера глубины. Чем больше расстояние от ближней до дальней плоскости отсечения, тем больше ошибка. И может оказаться так, что дальние объекты будут закрывать ближние.
Проблема частично решается введением логарифмического буфера глубины, что, однако, влияет на производительность приложения [69].
Аккуратность расчетов. Нужно помнить, что Земля — это эллипсоид, а не сфера. И при осуществлении расчетов учитывать разницу между экваториальным и полярным радиусами, разницу между геоцентрической и геодезической нормалями. Например, при движении космических аппаратов вокруг Земли или при позиционировании объектов на поверхности глобуса.
Кривизна. Нужно помнить, что Земля — круглая. Если соединить 2 точки на поверхности прямой линий в декартовых координатах, то эта линия окажется под поверхностью глобуса. Необходимо применять различные методы, чтобы все линии и полигоны оказались на поверхности, а не под поверхностью. Нужно помнить про линию перемены дат, и что на полюсах имеется сингулярность.
Большие объёмы данных. Виртуальный глобус строится на основе спутниковых снимков и карт высот. Если мы заходим представить рельеф всей Земли с разрешением 1 м на пиксель, то нам понадобится текстура 40 млн на 20 млн пикселей размером примерно в 11 петабайт. При этом возникает проблема — ограничение видеопамяти. На современных видеокартах имеется порядка 1 гигабайта памяти. При этом существуют ограничения на размер текстур в памяти — примерно 8192х8192 пикселей. Также существует предел обработки количества вершин модели в секунду.
Поэтому основная проблема заключается в том, как использовать большой объем (гигабайты и петабайты) исходных данных на жестком диске, чтобы показать на экране рельеф с небольшим числом вершин и небольшим размером текстур, который мог бы обновляться с частотой 30 кадров в секунду.
Использование многопоточности. Динамическая загрузка и выгрузка данных из памяти сильно влияет на производительность. Эти операции лучше все выполнять в отдельном потоке.
Алгоритмы рендеринга различных эффектов обычно используют упрощения и предположения, которые не применимы в случае виртуальных глобусов. Например, в обычных приложениях направление «вверх» всегда совпадает с осью Z. В случае глобуса в каждой точке будет своё собственное направление «вверх».
Современные компьютерные игры достигли больших успехов в реалистичном рендеринге природы. Рельеф, деревья, трава, облака, вода — всё генерируется программно с большой детализацией. Но в случае глобусов приходится использовать реальные данные о рельефе, реальную текстуру земной поверхности, которые зачастую имеют низкое разрешение. Если пытаться эти данные улучшать и добавлять детализацию, то не в ущерб достоверности.
1.3.5. Алгоритм Chunked LOD
В итоге с учётом всех особенностей глобуса авторы книги [48] рекомендуют использовать алгоритм Chunked Level of Detail (CLOD), как наиболее сбалансированный по всем характеристикам. Этот же алгоритм используется в инструментарии osgEarth. Изначально он был предложен в 2002 году [70].
Этот метод не требует предварительной обработки геопривязанных изображений, удобно ложится на эллипсоид, обеспечивает приемлемую точность в рамках чисел с одинарной точностью, и работает даже на самых старых видеокартах. Рассмотрим его подробнее.
Рельеф состоит из тайлов (chunk), выстроенных вдоль меридианов и параллелей. Каждый тайл имеет свою геометрию на основе регулярной сетки и текстуру. Каждый тайл относится к некоторому уровню детализации. Все тайлы образуют квадродерево. При приближении к тайлу он заменяется на 4 тайла большей детализации. Для каждого тайла хранится ограничивающий объём, который используется для проверки видимости тайла.
Каждый тайл должен храниться в отдельном файле. При необходимости тайлы подгружаются в память с диска или выгружаются из памяти. Каждый тайл содержит ссылки на файлы с 4 дочерними тайлами.
Структура получаемого квадродерева изображена на рисунке 1 .15.
|
Рис. 1.15. Структура квадродерева
|
|
TerrainTile — содержит сам тайл (геометрию и текстуру). Group — просто группирует подузлы графа. PagedLOD — переключает тайлы с разными уровнями детализации.
|
