Визуализация массивов поверхностей с использованием

управляемых кластерных уровней детализации

Часть 1

Thatcher Ulrich
Oddworld Inhabitants
tu@tulrich.com

Перевод с английского: Лисеенко В.В.

Источник: http://tulrich.com/geekstuff/sig-notes.pdf




Рисунок 1 – Первые три уровня кластерного дерева LOD


1 Введение


Рендеринг местности имеет важное значение для широкого класса игр и симулирующих приложений. Аппаратное обеспечение и алгоритмы продолжают быстро улучшаться, что повышает наши возможности рендеринга реалистичной местности. Сдвиг в последние годы в потребительской технике от CPU, связывающих графические конвейера, к высокоскоростным графическим вычислительным устройством специального назначения (GPU) резко изменил обмены в алгоритмах рендеринга поверхностей геометрических LOD. Новые решениия вызвали развитие GPU-ориентированных агрегированных алгоритмов детализации. Кроме того, увеличение количества и степени детализации наборов данных мы можем сделать, повысив спрос на данные, чтобы обеспечивать рендеринг, и подчеркнуть важность обработки наборов данных, которые не соответствуют оперативной памяти (вне основных наборов данных).

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

Эти примечания делают краткий обзор проблемы рендеринга идеальной поверхности, упоминают о наиболее популярных и успешных существующих алгоритмах, а затем представляют кластерный LOD, новый подход к агрегированным LOD. Кластерный LOD имеет ряд практических преимуществ по сравнению с предыдущими схемами, в том числе легкость текстурирования, низкая загрузка процессора и простота обработки не основных наборов данных.


2 Рендеринг идеальной поверхности


Визуализация идеальной местности позволит зрителю стоять на вершине высокой горы и видеть окружающую местность в мельчайших деталях, с деревьев на далекой линии хребта к гальке у ног зрителя. Зритель будет свободно перемещаться по сцене, идя через густые леса или летать быстро по воздуху непосредственно к далекому месту, где как локальное окружение, так и далекие перспективы всегда будут идеально детализированы в пределах отображения. Место представленное визуализацией идеальной местности, может быть верной моделью части реального мира, или какой-либо воображаемой местности, но в любом случае должно быть визуально богатым и интересным. Ни в одной точке зритель не должен знать о каких-либо отвлекающих артефактах, связанные со сменой данных или реорганизации геометрии в пределах визуализации.

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


3 Карты высот и LOD


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

Есть ряд хороших решений для рендеринга уровней детализации (LOD) карты высот, которые эффективно уменьшают число треугольников, которые должны быть визуализированы, за счет времени вычисления сетки. Вероятно, наиболее популярным подходом является использование ограниченного квадродерева или бинарного дерева треугольников. Наиболее часто цитируются работы [7] [4], [10], и все они работают достаточно хорошо, с количеством общедоступных реализации. Как правило, они включают некоторую предварительную обработку и небольшие дополнительные ошибки данных на вершину сверх стандартной карты высот.

Еще один важный набор алгоритмов LOD является производным от прогрессивных сетей Хоппе [5]. Прогрессивные сети сосредоточены на общих сетях, в отличие от карты высот в частности, в результате чего несколько иные обмены, но были успешно применены к картам высот.


4 Детальное и визуальное насыщение


Основная проблема, которая становится очевидной, является ограниченное количество деталей, присутствующих в данных, когда вы экспериментируете с демо-версией системы. Частота кадров высока, сеть бесшовная, но когда вы близко к земле все становится очень размытым и сглаживается, и когда вы идете высоко в вверх в конечном итоге можете увидеть границу данных.

Трудность здесь в том, что мы просто не можем хранить достаточно карты высот и текстурных данных в оперативной памяти, чтобы получить детализацию на огромных площадях как мы хотим. Одно из типичных решений для хранения очень больших наборов данных вне ядра - на локальном диске или на сетевом сервере - и страницы только для данных необходимых для конкретного представления. Некоторые из литературы по LOD, в частности, [8], рассматривают вопрос вне основном хранении, но высокого качества решений потребительского уровня по-прежнему не хватает.

С точки зрения программирования игр, есть также некоторые альтернативные подходы для решения огромных территорий, которые не связаны вне основным хранением. Один подход заключается в использовании адаптивной детализации, с использованием мульти-масштабного представления так, что "важные" области местности имеют много данных, в то время как менее важные области используют очень мало данных. Это может красиво решить некоторые практические проблемы, но это не общее решение, так как оно ставит детализацию и богатство в виртуальном мире в конфликт со свободой передвижения для просмотра.

Другой подход заключается в создании процедурных детализаций на лету при необходимости. Это очень мощная техника, но имеет существенные ограничения. Трудности здесь включают время обработки - красивые и интересные ландшафты могут быть получены процедурно с пакетами, такими как Bryce или Mojoworld, но достижение такого высокого качества занимает много процессорного времени, и должно обычно быть сделано на этапе предварительной обработки. Другая открытая проблема в создании процедурных территорий управляемых настолько, что дизайнеры игр и художники могут достичь конкретных результатов, которые они хотят.

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


5 Уровень детализации и перспективы


Перспективы на наш взгляд охватывает широкую гамму геометрических деталей, когда мы стоим на местности в реальном мире и смотрим на перспективу. Мы можем решать детализацию 1мм в гальку у наших ног, но в далеком расстоянии, 100м скала на склоне горы может быть наименьшее, что мы можем решить. То есть в 105 раз в геометрической разности размеров, благодаря полностью перспективе. Используя этот эффект имеет центральное значение для управления LOD масштабируемых местностей.

Xорошие существующие схемы вообще могут гарантировать, что сетка визуализируется в некоторой максимальной близости к экрану с пространственной ошибкой, "r", а воспользовавшись перспективой преобразования визуализации, все меньше и меньше треугольников при увеличении расстояния от наблюдателя.


6 Текстурирование


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

Как и наша геометрия, мы хотим, чтобы наши текстуры наложения были масштабируемыми более чем 105 диапазонов уровней детализации. К счастью, это не так сложно, бесшовно совпадают текстуры края, как это должно совпадать в геометрии ребер. Тайлы квадродеревьев являются простым, полностью масштабируемым решением для проблемы [12]. Серьезная трудность заключается в интеграции тайлового текстурирования с масштабируемой геометрической детализацией. Мы не можем сделать больше, чем одну текстуру карту на треугольник, и для повышения эффективности мы хотели бы сделать многие треугольники с теми же текстуры. В то же время для качества изображения и избежания LOD артефактов, мы хотели бы сохранить плотность текстуры один тексель в видимый пиксель на экране. Нам нужны наши геометрические решения LOD, которые должны быть совместимы с теми ограничениями.


7 Пред-GPU алгоритм LOD


В этих заметках я использую термин GPU для обозначения класса специализированного оборудования для обработки вершин, с низкой стоимостью, высокой скоростью, таких как NVIDIA GeForce, ATI Radeon и Sony PlayStation 2. Этот класс аппаратного оборудования имеет один или несколько плавающих точек преобразования в дополнение к аппаратному обеспечению растеризации целых пикселей, распространенному в предыдущих поколениях потребителей графического оборудования. Обработка вершин с плавающей точкой делается этими высокоскоростными GPU’s, ранее эта ответственность лежала на процессоре, который значительно ограничивал пропускную способность вывода треугольников.

До широкого внедрения GPU, LOD алгоритмы для игровых приложений сосредотачивались на сведении к минимуму числа треугольников визуализации, за счет ограниченного количества дополнительной обработки процессором. Различные опубликованные алгоритмы, например, Линдстром-Коллер CLOD [7], ROAM [4] и прогрессивные сетки [5] были приняты и адаптированы, чтобы стать полезным компонентом в арсенале игрового программиста. Дополнительной обработке необходимо вычислить масштабируемые сетки LOD, как правило, время, сэкономленное на преобразовании, компенсируется меньшим числом вершин для рендеринга.


8 Пост-GPU алгоритм LOD


С появлением графических процессоров, потребитель техники видел максимум роста скорости визуализации треуголиников. Участие процессора в визуализации может быть ограничено, лишь указынием GPU в разделе памяти, содержащем вершины модели для визуализации. Разработчики, заинтересованые в производстве высшего качество графики для игр, часто фокусируются на грубой силе всех GPU-методов (т.е. без непрерывного LOD), или подходов с очень низкой нагрузкой на процессор, как и представление независимых прогрессивных сеток[1] [11].

К сожалению, эти алгоритмы не видозависимые, и это не очевидно, как масштабировать эти методы к наборам данных местности с бесшовным 105 соотношением между ближней и дальней детализацией. Кроме того, реорганизация подходов непрерывных LOD для достижения низкой загрузки ЦП представляет много трудностей.


9 Кластерный LOD


Тем не менее, эффективный, аппаратно-дружелюбный непрерывный алгоритм LOD весьма желателен и есть ряд опубликованных подходов, которые достигли успеха в решении основных геометрических LOD задач. Эти подходы широко используют две стратегии по отдельности или в сочетании:

1) Применять видозависимые LOD алгоритмы для агрегатов примитивов, а не отдельных примитивов.

2)Кэшировать результаты алгоритма LOD вершины уровня, чтобы использовать их для подобных точек обзора.

Различные подходы, подробно изложены в [3], [1], [2], [6], [9]. Перестановок слишком много, чтобы обобщить здесь, поэтому я отсылаю вас к отдельным описаниям.

Кластерный LOD еще одна вариация для первой стратегии. Как и некоторые другие агрегированные подходы, он достигает низкие накладные расходы процессора и высокую пропускную способность треугольника, однако, уникально сочетает в себе ряд других важных преимуществ:

-Эффективное использование треугольников в агрегатах

- Текстуры LOD интегрированы с геометрией LOD.

-Легко интегрируется с вне основным хранением.

-Эффективный, гладкий морфинг вершин, нет выталкивания вершин.

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

Отрицательные характеристики включают в себя:

- Требуется нетривиальная предварительная обработка.

- Набор данных должен быть статическим.

- Использует больше треугольников, чем алгоритм примитивного уровня, с той же экранно-пространственной ошибкой.

- Некоторые размеры данных наверху, зависят от lossiness предварительной обработки.

Общий подход к кластерному LOD, изложенный в [1], хотя в контексте использования видонезависимых прогрессивных сеток для кластеров. [2] описывает использование ячеек квадродеревьев, с морфингом статических сеток, чтобы избежать появления артефактов, но опирается на регулярные подразделения сетки внутри каждой сети, и не так легко поддается подкачки извне

Метод, изложенный в этих записках, опирается на те идеи и разрабатывает ряд важных деталей.

В основе метода лежит дерево статических, в значительной степени независимых предобработанных сеток. Дерево и его компоненты сетки ("куски", кластеры) создаются на предварительном этапе, на основе сетки с высоким уровнем детализации. Каждый кусок только примитив статической сетки, что может быть визуализирован glDrawElements () или DrawPrimitive () вызовов, а также дополнительный быстрый проход морфинга. Кластер в корне дерева представляет целый объект с низким уровнем детализации. Дочерние кластеры корневого узла разделяют объект на несколько частей, и каждая часть независимо представляет свою часть объекта с более высоким уровнем детализации, чем родительская.

Это соотношение является рекурсивным до некоторой произвольной глубины. Каждый блок имеет ограничивающий объем связанный с ним, а также максимальную геометрическую ошибку, "S". "S" представляет собой максимальное геометрическое отклонение кластера (в пространстве объекта) от части основной сетки , которую он детализировано представляет.

Для простоты, я назначу же "S" для всех сеток на определенном уровне кластерного дерева. Кроме того, я вычисляю "S", как:

Где L является уровнем в дереве. Например, если корневой узел дерева является одной сеткой, что представляет собой объект с не более 16 единицами отклонения от оригинальной сетки полной детализации ("S" (0) = 16), то второй уровень состоит из нескольких кусков (кластеров), что каждый представляет часть объектов с не более 8 единицами отклонения от полной детализации сетки ("S" (L) = 8). На пятом уровне вниз по дереву, куски каждого представляют собой лишь малую часть объекта, и только 1 единица отклонения ("S" (4) = 1).

Когда мы применяем эту схему расщепления карты высот, простой подход состоит в организации дерева как квадродерева из подквадратов карты высот (см. рис. 1). Это также может быть удобным, когда мы рассматриваем текстуры.


10 Видозависимый рендеринг


Во время выполнения, для визуализации объекта, мы просто выбираем куски, которые представляют каждую часть объекта для удовлетворения нашей желаемой визуальной точности. Так как мы имеем ограничивающий объем для каждого блока, и максимальную геометрическую ошибку вершин кластера, мы можем использовать стандартную формулу LOD для консервативного определения максимальной вершины экранно-пространственной ошибки, "р", для кластера:



Где "S" является максимальной геометрической погрешностью кластера, D является расстоянием от точки зрения до ближайшей точки на ограничивающем объеме кластера, и K является фактором перспективы масштабирования, который принимает во внимание размер окна и поля-обзора , и вычисляется следующим образом:



Отметим, что "р" измеряется в центре окна просмотра, что несколько либерально, но разумно, как это принято в литературе LOD. С точки зрения эффективности, нет никаких веских причин не использовать более точную, более дорогую экранно-пространственную ошибку метрики, в отличие от по вершинных алгоритмом LOD, вид метрики как правило, только нужно оценивать пару сотен раз в кадре. Тем не менее, эта упрощенная метрика является очень эффективной на практике, и потому, что она не зависит от направления просмотра, сетка LOD остается абсолютно стабильной, когда зритель поворачивается на месте.

Простой способ оценить наше LOD-дерево и визуализировать кластерную модель для обхода дерева нужно начиная с корня. Мы начнем с выбора значения для нашей максимально допустимой экранно-пространственной ошибки, "r". Тогда, учитывая кластер, мы можем использовать уравнение 1 для определения приемлемой экранно-пространственной ошибки. Если это так, то мы визуализируем кластер и не рекурсивно для детей. Если это не приемлемо, то мы выполняем рекурсивно в дочерних узлах. Псевдокод:


Есть две большие проблемы вышеописанного алгоритма:

1. Соседние кластеры в различных LOD будут иметь трещины в месте соприкосновения.

2. Когда точка зрения приближается к кластеру, кластер будет разделен на несколько дочерних кластеров, и внезапно появится форма сетки. Поскольку многие вершины выталкиваются в то же время, это гораздо более нежелательно, чем если одна вершина появится в ROAM или PM-реализация.

Далее следуют эффективные решения обеих проблем.