Визуализация данных на виртуальном глобусе 3.1. Облака точек 3.1.1. Обзор современного состояния дел
Облака точек — один из самых простых типов данных. Необходимость визуализации таких данных на виртуальном глобусе возникает в разных областях, однако при этом возникает ряд технических сложностей.
Один из примеров точек на глобусе — это гипоцентры землетрясений, которые хранятся в виде каталогов. Гипоцентр — это центральная точка очага землетрясения, которая находится в глубине земли. Проекция гипоцентра на поверхность Земли называется эпицентром. Каталоги гипоцентров свободно доступны на специализированных сайтах, например, на сайте Геологической службы США (USGS) [87], на сайте Камчатского филиала Геофизической службы РАН [88], и др. Каталог землетрясений для всей Земли с 1900 года включает около 1 млн. событий.
Точки из каталогов могут покрывать большие территории, возможно даже всю поверхность глобуса, и могут иметь разные высоты и глубины. Такие точки изначально хранятся в географической системе координат, и перед визуализацией их необходимо переводиться в мировую декартову систему координат.
Другой пример источника облаков точек — лазерное сканирование. Лазерное сканирование — это современный способ для быстрого создания высокоточных 3D-моделей зданий и любых объектов в виде облаков точек [89]. Точность может достигать 1 мм. Сначала производится сканирование объекта с разных позицией, затем — обработка полученых исходных облаков точек. Процесс обработки состоит из 2х этапов: сначала все облака для одного объекта сшиваются в единое облако точек (рис. 3 .33), затем по этому облаку точек восстанавливается полигональная 3D-модель. Первый этап проходит быстро и может быть автоматизирован. Однаков второй этап довольно трудоёмкий, требует ручной работы и может затянуться на месяцы.
Рис. 3.33. Облако точек Шуховской башни
Поэтому вместо того, чтобы создавать полигональную 3D-модель объекта, можно работать с точечной 3D-моделью. Облако точек для одного здания может содержать 50-100 миллионов точек и занимать в памяти несколько гигабайт. Это делает невозможным интерактивный рендеринг полного облака точек. Необходимо использовать уровни детализации.
Исследования в области обработки и визуализации облаков точек ведутся много лет. Значительные усилия тратятся на развитие методов и разработку библиотек для реконструкции полигональных поверхностей по облакам точек [90].
Кроме того, существуют методы визуализации непосредственно самих облаков точек. Обзор таких методов дан в статье [91]. Они различаются как разбиением облака точек на уровни детализации, так и способами рендеринга самих точек. Существуют три основных способа:
визуализация облаков точек в виде простого точечного примитива OpenGL (GL_POINT). Они изображаются на экране в виде либо квадрата, либо окружности заданного размера. В вершинном шейдере можно задавать размер индивидуально для каждой вершины;
визуализация облаков точек в виде спрайта — четырехугольника, который всегда повернут к камере. Это более медленный, но более гибкий вариант, т.к. позволяет использовать текстуру с прозрачностью;
визуализация в виде одного или нескольких треугольников фиксировано расположенных в пространстве, перпендикулярно вектору нормали. Они называются splats («нашлепки»). Это самый медленный, но наиболее гибкий вариант, который обеспечивает лучшее визуальное качество.
Спрайты и треугольники — это попытка скрыть промежутки между точками, чтобы 3D-модель визуально выглядела целостной, без дыр [92, 93]. Есть и другие подходы к этой проблеме, основанные на постпроцессинге [94].
Поскольку размеры облаков точек растут, то появляются методы по их сжатому хранению и распаковке на видеокарте [95, 96].
Для более качественно рендеринга с освещением необходимо знать нормаль в каждой точке. Если нормали изначально не заданы, то их можно вычислить. Существуют методы для этого [97].
В работе [46] предлагается отказаться от построения полигональных моделей зданий и использовать облака точек для создания 3D-моделей целых городов.
В моно-режиме облака точек сложно воспринимать на экране из-за отсутствия ощущения глубины точек. Все точки кажутся расположенными на одном расстоянии и сливаются в «кашу», особенно если используются не реальные, а условные цвета. Но ситуация меняется в случае использования стереоскопической визуализации. Визуально можно легко отделить точки, расположенные ближе, от точек, расположенных дальше. Это превращает стереовизуализацию в мощный инструмент для визуального анализа научных данных. Именно поэтому в данной работе делается акцент на точечных данных.
Точки удобны тем, что они рендерятся очень быстро, т.к. это базовый геометрический примитив. Современные видеокарты позволяют рендерить около 10 миллионов точек каждый кадр с интерактивной частотой кадров. Поэтому нет необходимости проверять индивидуальные точки на попадание в объем видимости.
На вызов каждой операции отрисовки тратится небольшой время (накладные расходы). Чтобы минимизировать суммарное время, рекомендуется объединять точки из разных облаков в единый массив, для отрисовки одной командой.
С другой стороны, если точки распределны по большой территории, то имеет смысл разбить все точки на несколько частей по пространственному признаку и проверять каждый кусок на попадание в область видимости.
Необходимо динамически определять, какие точки показывать в зависимости от положения виртуальной камеры. При приближении камеры необходимо показывать дополнительные точки в той части модели, которая попадает в область видимости камеры. А при отдалении снова скрывать их.
3.1.2. Алгоритм визуализации облаков точек
Была поставлена задача разработать алгоритм для интерактивного рендеринга больших облаков точек (размером больше 100 млн. точек) на виртуальном глобусе и динамической фильтрации их по заданным параметрам.
Можно заметить, что при разрешении 1920х1080 максимальное число видимых точек на экране составляет около 2 млн. Поэтому при просмотре облака с большого расстояния нет необходимости отображать все 100 млн. точек целиком.
В основе предложенного алгоритма лежит подход с дискретными уровнями детализации, при котором облако разбивается на фрагменты — мини-облака. Когда камера находится далеко, то показывается один фрагмент, который содержит точки случайным образом выбранные из полного облака точек. По мере приближения камеры должны показываться фрагменты более высоких уровней детализации. Все фрагменты должны содержать примерно одинаковое количество точек, но на более высоких уровнях детализации пространственный размер фрагмента должен быть меньше и фрагментов должно быть больше.
Идеологически эта схема напоминает подход с тайлами рельефа, описанный в параграфе 1.3.4. Однако природа точечных данных позволяет сделать одно существенное усовершенствование. В случае рельефа при приближении тайлы более высоких уровней детализации заменяют тайлы низких уровней детализации. Но точечные данные разных уровней детализации могут не мешать друг другу. Точки нескольких уровней детализации можно показывать одновременно. При приближении камеры фрагменты низкого уровня детализации не должны скрываться, а фрагменты более высоких уровней детализации должны добавляться к существующим.
Такой подход позволяет не дублировать точки между уровнями детализации. В памяти облако точек, разбитое на уровни детализации, будет заниматься столько же места, сколько и целое.
Генерация дерева фрагментов
В начале необходимо сгенерировать дерево фрагментов: разбить всё облако точек на фрагменты и расчитать расстояние видимости для каждого фрагмента.
Алгоритм основан на рекурсивном разбиении пространства и хранении данных в древовидной структуре данных. Древовидная структура данных включает квадро- и октодеревья. В случае квадродерева вся область рекурсивно разбивается на 4 ячейки. В случае октодерева — на 8 ячеек (рис. 3 .34).
|
Рис. 3.34. Схема октодерева
|
|
Далее перечислены шаги алгоритма.
0. Предварительный этап. Если облаков точек несколько, то их всех необходимо объединить в единое облако, и преобразовать координаты из локальных систем координат в географическую систему координат.
1. Построение корневого ограничивающего бокса. На этом шаге перебираются все точки полного облака точек для определения минимальных и максимальных значений координат по 3м осям. Далее вычисляются координаты вершин ограничивающего бокса, который плотно содержит в себе полное облако точек.
2. Начальное построение дерева. Каждый узел дерева имеет следующие атрибуты: соответствующий этому узлу ограничивающий бокс, массив вершин этого узла, массив цветов (и возможно массивы интенсивностей и других вершинных атрибутов) и ссылки на дочерние узлы.
Построенный на первом шаге бокс используется для создания корневого узла дерева.
На этом шаге происходит последовательное чтение точек (из файла или другого источника данных для облака точек) и помещение их в корневой узел дерева с помощью метода добавитьТочку() (рис. 3 .35).
В методе добавитьТочку() происходит помещение точки в локальный массив вершин этого узла до тех пор, пока их количество не превысит значение параметра  .
Если количество точек превысило  то происходит разбиение ограничивающего бокса и построение соответствующих дочерних подузлов. Все имеющиеся в данном узле точки распределяются по дочерним узлам, вызывая метод добавитьТочку() у каждого из дочерних подузлов.
При последующих вызовах добавитьТочку() происходит рекурсивный вызов добавитьТочку() у дочерних узлов. Когда количество точек в некотором узле достигнет значения , то процедура разбиения повторяется.
Вначале разбиение прозводится на 4 подбокса путем разрезания исходного по середине по долготе и широте. Далее квадродерево переходит в октодерево — дополнительно производится разрезание по средней высоте.
В конце этого этапа, когда все точки из полного облака будут обработаны, получится древовидная структура. Точки будут распределены по листовым узлам этого дерева.
|
Рис. 3.35. Распределение вершин по узлам
|
|
3. Перераспределение точек в дереве. В начале этого этапа все точки распределены по узлам максимального уровня детализации M. Теперь нужно заполнить точками другие уровни детализации. При этом точки не должны дублироваться, т.е. точки будут браться из дочерних узлов и подниматься вверх в иерархии.
Рекурсивно для всех промежуточных узлов, начиная с узлов уровня детализации М-1 и вверх по дереву должна быть выполнена следующая операция. Случайным образом из всех дочерних узлов нужно отобрать  точек и поместить в массив вершин данного узла.  , поэтому эта операция всегда возможна. Далее перебираются все дочерние узлы. Если в каком-то из них осталось меньше  точек, то они все переходят в массив вершин данного узла.
В результате этого этапа корневой узел будет содержать точек, каждый промежуточный узел будет содержать не меньше  и не больше  точек, а листовые узлы не меньше и не больше  .
4. Генерация геометрии. На основе каждого узла дерева создается объект, который будет отвечать за визуализацию данного фрагмента облака точек.
При визуализации глобального облака точек возможна следующая ситуация: при попытке приблизиться к точке или к группе рядом стоящих точек возникает дрожание (jittering). Как упоминалось в параграфе 1.3.4, это связано с использованием типа данных с одинарной точностью (float). Числа с плавающей точкой имеют фиксированную относительную точность, но изменяющуюся абсолютную точность. Точность обратно пропорциональная расстоянию от начала координат (центра глобуса). На поверхности глобуса абсолютная точность составляет около 1м. Чем выше от поверхности, тем ниже точность.
Поэтому координаты всех точек узла преобразуются из географической в локальную декартову систему координат данного узла.
Разработка приложения велась на основе фреймворка OpenSceneGraph, поэтому удобно представить результирующую структуру данных с использованием классов OpenSceneGraph наподобие схемы для тайлов рельефа на рисункеРис. 1 .15.
Конечная геометрия хранится в объектах класса Geode. Класс Group отвечает за группировку элементов графа сцены, а класс PagedLOD за переключение видимости в зависимости от расстояния и за подгрузку объектов с диска.
На рисунке 3 .36 представлена часть графа сцены, которая относится к одному фрагменту облака точек и хранится в одном файле. Этот файл прикреплен к экземпляру класса PagedLOD. Когда камера приблизится к заданному расстоянию, то файл будет подгружен с диска в память. На экране отобразится геометрия данного фрагмента (Geode) и будут задействованы еще 8 экземпляров PagedLOD, который в нужный момент подгрузят дочерние узлы следующего уровня детализации.
Алгоритм имеет несколько степеней свободы: значение параметров , , и расстояние, с которого нужно подгружать данный фрагмент.
|
Рис. 3.36. Граф сцены
|
|
Если параметры , , будут слишком маленькие, то возрастут затраты времени на накладные расходы видеокарты и на проверку видимости каждого фрагмента. Если эти параметры будут слишком большие, то новые фрагменты будут долго подгружаться с диска или интернета, и станут заметны скачки частоты кадров. Предлагается использоваться следующие значения:  ,  ,  .
5. Вычисление расстояний видимости фрагментов
Необходимо также настроить переключение видимости фрагментов. Расстояние, с которого нужно подгружать фрагмент, должно определяться, исходя из визуальной плотности точек на экране в момент подгрузки.
Угловой размер каждого пикселя экрана определяется по следующей формуле:
|
(3.12)
|
где sd — расстояние до экрана, sh — высота экрана,  — количество пикселей экрана по высоте.
Для каждого фрагмента строится своя ограничивающая сфера радиуса R. Со стороны наблюдателя сфера будет казаться диском радиусом R. Если считать, что все точки распределены по диску равномерно, то угловой размер расстояния между точками будет равен:
|
(3.13)
|
где M — число точек во фрагменте, d— расстояние до центра фрагмента, которое и нужно найти.
Если теперь положить, чтобы угловое расстояние между точками равнялось угловому расстоянию между пикселями, мы получим нужное расстояние до центра фрагмента:
|
(3.14)
|
В зависимости от производительности видеокарты и желаемой частоты кадров можно ввести коэффициент пропорциональности, чтобы уменьшить визуальную плотность точек.
Вышеописанный алгоритм для работы загружает все облако точек в память. Однако на 32х-битных системах существует ограничение по памяти в 2Гб. Поэтому если размер облака точек превосходит 2Гб, то необходимо предварительно разбить всё облако на несколько частей и применить алгоритм к каждой части по отдельности.
Визуализация и фильтрация точечных данных
Обычно точки имеют не только координаты, но и визуальные атрибуты (размер и цвет) и множество дополнительных атрибутов. Например, в случае лазерного сканирования это может быть интенсивность отраженного луча лазера. В случае гипоцентров землетрясений — магнитуда, время события, регион принадлежности события [11].
Визуальные атрибуты могут быть заданы изначально, а могут вычисляться на основе дополнительных атрибутов. Например, если атрибут x изменяется от 0 до 1, то цвет можно вычислить по формуле спектра [98]:
|
(3.15)
|
При этом цвет плавно изменяется от синего до красного (рис. 3 .37).
|
Рис. 3.37. Непрерывная палитра цветов
|
Для размера точек еще проще:
|
(3.16)
|
Также часто необходимо осуществлять фильтрацию облака точек по заданным параметрам. Например, показывать только точки, атрибуты которых попадают в заданный диапазон.
Вычисление визуальных атрибутов и фильтрацию можно делать на центральном процессоре. Однако этот процесс занимает время, т.к. выполняется или последовательно, или в лучшем случае распараллеливается на нескольких ядрах ЦП. При попытке выполнять такие вычисления в реальном времени для больших объемов точек произойдет серьезное падение производительности.
Однако современные видеокарты позволяют визуализировать миллионы точек с интерактивной частотой кадров и производить вычисления в вершинном шейдере прямо во время рендеринга. Можно динамически изменять цвета точек, их размер, и производить фильтрацию на основе значений вершинных атрибутов.
У разных облаков точек могут быть разные атрибуты. Даже в рамках одного облака может быть необходимо изменять параметры фильтрации и вычисления визуальных атрибутов. Для каждого случая нужно иметь свою версию вершинного шейдера. Чтобы не писать каждый раз шейдер вручную, лучше его генерировать автоматически.
Рассмотрим весь процесс подробнее.
1. Задание вершинных атрибутов. Спецификация OpenGL позволяет загружать на видеокарту вершинные атрибуты, которые далее можно использовать в вершинном шейдере. Каждый атрибут — это 4х-мерный вектор со значениями типа float [99]. Однако сырые данные могут быть в других форматах: целочисленный, дробный, булевский, дата-время. Их нужно перевести в тип с плавающей точкой. Целые числа и булевские переводятся однозначно. Приведение даты-времени зависит от требуемой точности: дни, секунды или доли секунды. Например, если все даты относятся к периоду после 1970 года, то можно использовать Unix-time представление: число секунд, прошедшее с 1го января 1970 года. Если нужно охватить больший период времени, или нужна большая точность, то дату-время можно превратить в 2 числа с плавающей точкой: одно описывает номер дня, начиная с заданного момента в прошлом, другое — время в рамках одного дня.
4 разных атрибута точки можно передать на видеокарту как компоненты 4-вектора вершинного атрибута.
2. Создание uniform-переменных. Для каждого атрибута создаются несколько uniform-переменных. 2 переменные задают минимальное и максимальное значение атрибута. Во время исполнения шейдера проверяется попадание значения атрибута в выбранный диапазон. Если он не попадает, то вершина отбрасывается. 2 булевские переменные задают условия: нужно вычислять цвет точки или размер точки на основе этого атрибута.
3. Генерация тела шейдера. В цикле по всем атрибутам к шапке и к телу вершинного шейдера добавляются вставки.
Пример, шапки для одного атрибута:
attribute vec4 attr1;
uniform float attr1xMin;
uniform float attr1xMax;
uniform bool attr1xColor;
uniform bool attr1xSize;
Пример, тела шейдера для одного атрибута:
if (attr1.x < attr1xMin || attr1.x > attr1xMax)
{
discardPoint = true;
}
else if (attr1xColor)
{
float ratio = (attr1.x - attr1xMin) /
(attr1xMax - attr1xMin);
gl_FrontColor = getColorFromPalette(ratio);
}
else if (attr1xSize)
{
float ratio = (attr1.x - attr1xMin) /
(attr1xMax - attr1xMin);
gl_PointSize = minSize + ratio * (maxSize - minSize);
}
Здесь переменная discardPoint задается один раз на весь шейдер. Также отдельно определена функция getColorFromPalette на основе формулы ( 3 .15).
Выше приведен пример проверки на попадание значения атрибута в заданный диапазон. Но могут быть и более сложные виды фильтрации. Например, проверка на принадлежность точки некоторому региону. Все облако точек делится на N областей-регионов. Каждый регион имеет свой идентификатор — число от 0 до N-1. Номер региона, к которому принадлежит точка передается в шейдер через вершинный атрибут.
Далее пользователь может выбрать какие регионы показывать. Например: 3, 5 и 10. Могут выбраны одновременно несколько регионов. Поэтому uniform-переменные attr1xMin и attr1xMax здесь уже не применимы. Вместо этого в шейдер передается массив булевских uniform-переменных, которые определяют видимость каждого региона:
uniform bool attr1xRegion[100];
if (attr1xRegion[int(attr1.x)] == false)
{
discardPoint = true;
}
Примеры применения.
Предложенный подход использовался для визуализации и фильтрации каталога гипоцентров землетрясений (рис. 3 .38, 3 .39).
|
Рис. 3.38. Региональный каталог сейсмических событий в районе Курило-Камчатской дуги, по данным КФ ГС РАН [88]
|
|
|
Рис. 3.39. Мировой каталог сейсмических событий USGS за 1900-2011 гг, по данным USGS [100], в редакции А. В. Ландера (МИТП РАН)
|
|
Каждый гипоцентр имеет атрибуты: широта, долгота, глубина, дата, время (час, мин, сек), магнитуда, регион.
Глубина задается своим реальным значением (от 5км до -700км) с типом float и используется для вычисления цвета гипоцентра. Цветовое кодирование позволяет лучше определить глубину гипоцентра при обычном (не-стереоскопическом) просмотре, а также является традиционным обозначением в геофизике. Цвет берется из линейной палитры от синего на малых глубинах до красного на больших глубинах.
Магнитуда также задается реальным значением от 0 (если не определена) до 9.5 с типом float. Значения магнитуды от минимального до максимального отображаются на диапазон размеров точек от 1го до 6ти пикселей.
Также происходит фильтрация гипоцентров по регионам. Для каждого гипоцентра хранится идентификатор региона, к которому относится гипоцентр. При выборе алгоритма фильтрации учитывались следующие условия: (1) регионы не пересекаются и (2) одновременно можно выбирать несколько регионов. Тестировался набор из 10 регионов для Курило-Камчатской дуги.
|
