Докуметация Cтарт Статьи Форум Лента Вход
Не официальное русскоязычное сообщество
Главная
    Статьи
        Переводы с других сайтов
            Быстрый рендеринг ландшафта с использованием MipMapping геометрий.

Быстрый рендеринг ландшафта с использованием MipMapping геометрий.

Опубликованно: 18.12.2017, 17:16
Последняя редакция, Andry: 23.01.2018 15:41

Willem H. de Boer, whdeboer@iname.com
Проект E-mersion, Октябрь 2000, http://www.connectii.net/emersion

1 Введение

Существует множество алгоритмов, которые ускоряют рендеринг данных-ландшафта, варьирующиеся от простого древа квадрантов на основе отсечения по пирамиде видимости невидимых клочков местности, до использования наборов окклюдера для использования (постоянно действующих) Уровней Детализации. Все эти технические приемы служат для уменьшения количества треугольников, которые будет нужно пропихнуть через конвейер рендеринга. Многие алгоритмы рендеринга ландшафта используют комбинацию нескольких из этих методов, чтобы еще больше ускорить рендеринг. Известными примерами являются алгоритм ROAM [3], Lindstrom и другие. Статья SIGGRAPH 96 о рендеринге ландшафта [1] и подход NDL к рендерингу ландшафта, который будет использоваться в играх реального времени [2]. Большинство из этих алгоритмов были изобретены (задолго) до того, как аппаратное рендеринг стал стандартом отрасли, и поэтому они могут быть больше непригодны для использования в сочетании с аппаратным 3D рендерингом. Поэтому необходимо найти новые алгоритмы, которые принесут наилучшие результаты при использовании вместе с аппаратным 3D-рендерингом. Поскольку аппаратные средства для 3D способны обрабатывать и отображать большое количество треугольников на кадр, алгоритм может прибегать к более консервативным методам отсечения, тем самым не обязательно обеспечивая «идеальный набор» данных рендеринга, и увеличивая количество треугольников по конвейеру с помощью аппаратного обеспечения, можно уменьшить нагрузку на процессор. Я придумал метод, который соответствует сказанному выше, и, насколько я знаю, раньше не использовался. Алгоритм реализован как часть проекта E-mersion. В этой статье будет дано полное описание алгоритма.

2 ОБЗОР

В этом разделе описывается полностью весь алгоритм, который разбит на три отдельные части. В первой части будет дано описание представления данных ландшафта, способы его организации в памяти и способы его создания. В разделе 2 рассказывается в основном об отсечении по пирамиде видимости «клочков» ландшафта, а в последнем разделе описываются GeoMipMap-ы использующий стандартный подход mipmap для текстур, как аналогию.

2.1 Представление данных ландшафта

Представление ландшафта может быть сделано несколькими способами, но я решил использовать тот, который используется большинством современных механизмов рендеринга местности. Причина, по которой я выбрал это представление, состоит в том, что оно 1) просто в реализации, 2) требует минимум места на жестком диске, 3) подходит для GeoMipMap-ов, как объясняется в разделе 2.3. Одним из недостатков этого представления (которое в основном является 2D решением) является то, что оно не поддерживает «выступы».

Terrain-MipMapping-1

Рисунок 1: Представления блоков сетки(mesh) ландшафта, вид сверху. Белые круги представляют собой вершины сетки. Линии представляют собой соединения между вершинами. Обратите внимание, что каждый четырехугольник (или квадрат) построен из двух треугольников.

Ландшафт выкладывается в клетки(grid) вершины которых имеют фиксированном расстоянием между ними. Горизонтальное и вертикальное число вершин в клетке должно иметь вид 2n + 1, где n ∈ [1, →). Это приводит к 2n четырёхугольнику, у которого 4 вершины являющиеся его углами, это вершины его соседних четырёхугольников. Каждый четырехугольник состоит из 2 треугольников, которые используются в качестве примитивов рисования, которые конечном итоге отправляются в графический конвейер.
Каждому x и z компоненту вершины устанавливается фиксированное значение, которое не будет изменятся в течение всего процесса. Компонент вершины который представляет собой значение-высоты ландшафта для какого то конкретного места, считывается во время загрузки ландшафта — из 8-битного растрового файла, состоящего из градаций серого цвета, который имеет размеры изображения пропорциональный клеткам(grid) ландшафта. Затем все клетки ландшафта разрезается на то, что я называю, блоки ландшафта, которые имеют фиксированный размер и должны иметь вид 2n + 1 ( n ∈ [1, →) ). Это шаг предварительной обработки, отсечения по пирамиде видимости для древа квадрантов, этап который будет разъяснён позже, и эти блоки также будут служить примитивами уровня 0 для GeoMipMap-ов (см. Раздел 2.3). На рисунке 1 показан такой блок ландшафта, который имеет 5×5 вершин. Размер блок ландшафта можете выбран какой захотите. В реализации E-mersion это 17×17, что я считаю самым быстрым, учитывая мой общий размер ландшафта-клеток 257×257. С этим нужно эксперементировать.
Одним из преимуществ этой компоновки в виде блоков ландшафта является то, что любой такой блок может быть оптимизирован для рендеринга, используя один вызов примитива-рисования для всего блока и, еще лучше, с помощью индексации, чтобы избавиться от множественного преобразования вершин. Небольшим недостатком блоков ландшафта является то, что вершины каждого из четырех ребер являются общими с соседними блоками ландшафта, и поэтому они будут преобразованы дважды.

2.2 Базовое отсечение по пирамиде видимости

Поскольку значительные части ландшафта не будут видны (т.е. не внутри пирамиды видимости) в определенных местах расположения камеры, то их не нужно рендерить, и поэтому их нужно заранее отсекать, чтобы избежать ненужных вычисления. Метод, который оказался достаточно эффективным для быстрого отсечения, представляет собой структуру данных называемую древом квадрантов(quadtrees). Я не собираюсь объяснять что такое древо квадрантов здесь, потому что в Интернете есть много хороших уроков/заметок/статей.

Древо квадрантов генерируется во время загрузки ландшафта и состоит только из 3D ограничивающих параллелепипедов. Размер ландшафта вместе с размером блоков ландшафта определяет возможную глубину древа квадрантов. Узлы древа квадрантов состоят из 3D ограничивающих параллелепипедов, которые внутри содержат ограничивающие параллелепипеды для всех под-деревьев узла, где — на листе — можно найти блока ландшафта, ограничивающий параллелепипед. Каждый лист имеет ссылку на блок ландшафта, который содержит ограничивающий параллелепипед. Причина, по которой древо квадрантов используются вместо октодрева, заключается в том, что компоновка ландшафта по существу происходит в 2D, и поэтому нам может быть достаточно 2D пространственной организационной схемы.
Блоки ландшафта помечаются как видимые, когда ограничивающий параллелепипед листа, хотя бы, частично находится внутри пирамиды видимости. После того, как вы закончите спускаться по древу, начнётся отсечение от корневого узлу дерева, и исходя из пометок блоков ландшафта видимые или невидимые, мы остаёмся только с набором блоков ландшафта, которые можно сразу отправить в графический конвейер. Поскольку сложность ландшафта может быть довольно высокой, мы не получим желаемую частоту кадров, если ландшафт не очень мал; описанный выше метод не будет достаточным для ландшафта высокой сложности (например, большые клетки). Здесь я введу новый термин: GeoMipMap-ы. Они делают этот метод рендеринга местности уникальным и подходящим для аппаратного 3D-рендеринга, как я опишу дальше.

2.3. Аналогично Mipmap текстурированию (введение в GeoMipMap-ы)

Блоки ландшафта, которые находятся далеко от камеры, нет необходимости рендерить с тем же количеством деталей, что и блоки ландшафта, которые находятся рядом с камерой. Они могут быть аппроксимированной версией с более низким разрешением, тем самым резко уменьшая количество треугольников и увеличивая скорость рендеринга. Это называется Уровнем Детализации(Level of Detail), он используется во многих современных алгоритмах рендеринга ландшафта. Многие из современных алгоритмов быстрого рендеринга данных ландшафта используют некую схему уровня детализации, хотя многие из них относятся к методам расчёта-треугольников, которые не подходят для использования в сочетании с аппаратным 3D рендерингом. Чтобы уменьшить нагрузку на CPU, мы должны выполнить уровень детализации на более высоком уровне, и это — то, где и появляются GeoMipMap-ы.
Рассмотрим обычные технические приемы mipmapping для текстур [5]. Цепочка mipmap-ов создается для каждой текстуры, первый элемент в цепочке — это оригинальная текстура, а каждый последующий элемент является копией предыдущего элемента, но уменьшенным до половины его разрешения, и так до тех пор, пока не будет достигнуто желаемое количество элементов (уровней). Когда текстура находится на определенном расстоянии, d, от камеры, выбирается соответствующий уровень из цепочки mipmap, и он используется для рендеринга вместо оригинальной текстуры с высоким разрешением. Мы также можем применить этот подход к 3D сеткам, где эквивалент 3D-текстуры с высоким разрешением — это блок ландшафта, а mipmap-ы вычисляются путем масштабирования блока ландшафта. На рисунке 2 показан блок ландшафта и его прямой наследник в цепи mipmap. Эта цепочка может быть расширена другим элементом в цепочке, который имеет еще более низкое разрешение. Мы можем заранее рассчитать и хранить эти GeoMipMap-ы в памяти, это будет хорошим плюсом, во время загрузки.

Далее в этой статье будет использовать термин GeoMipMap уровня 0 для блока ландшафта с разрешением по умолчанию, и уровень GeoMipMap N ( N ∈ [1, →) ) для каждой из версий с низким разрешением.

Terrain-MipMapping-2

Рисунок 2: Разрешение по умолчанию блок сетки(mesh) ландшафта слева (GeoMipMap уровня 0) и версия с низким разрешением (GeoMipMap уровня 1) справа. Обратите внимание, что также может быть сгенерирован GeoMipMap уровня 2.

2.3.1 Выбор нужного уровня GeoMipMap

В этой части я хотел бы объяснить определение того, какой уровень GeoMipMap использовать, для того или иного расстояния (d). Использование заранее заданного (фиксированного) d для каждого уровня GeoMipMap приведет к появлению нежелательных дефектов в виде трещин. Если просто переключится с одного уровня на другой, при фиксированном d без каких-либо условий, то вы увидите как произойдёт резкое изменение геометрии; вершины добавляются при уменьшении уровня GeoMipMap, и вершины убираются при увеличении уровня GeoMipMap. Посмотрите еще раз на Рисунок 2. При переключении с уровня 0 на уровень 1 белые вершины уровня 0 будут удалены, так будет получен уровень 1. Это делает ландшафт неправильным, и выглядит он при осмотре с близкого расстояния, не таким каким вы его создали. Когда вы смотрите на текстуры с mipmapping, при отношении пикселя к текселю текущего mipmap не больше 1:1, алгоритм выбирает только mipmap с более низким разрешением, это происходит при определенном d [5]. Точный расчет для выбора нужного уровня происходит в аппаратном обеспечении, и на самом деле для нас сейчас не имеет значения. Мы можем применить эту же концепцию и к GeoMipMap-ам, чтобы уменьшить появление дефектов.

При переключении уровня GeoMipMap с 0 на 1 уменьшится детализация, что приведет к неправильности или ошибкам в блоке ландшафта. Это вызвано удалением вершин, что приведёт к изменению высоты для δ, как показано на Рисунке 3. Этот δ будет менее заметным, чем больше будет d из-за перспективы. Мы также можем проецировать δ на эквивалентную ему длину в пикселях пространства экрана (которую мы будем называть ε), что в конечном итоге будет то что пользователь заметит. Когда ε превышает определенный предел τ, скажем, 4 пикселя, ошибки будут слишком заметны, и поэтому не разрешается переключаться на более высокий уровень GeoMipMap до тех пор, пока ε не станет меньше τ. Но поскольку каждый уровень GeoMipMap состоит из некоторого количества этих ошибок (по одной на каждую удаленную вершину), мы должны как-то вычислить, какой δ взять, для проецирования пикселей экрана. Принимая получившийся δ из max{δ0, …, δn-1} (где n — количество δ в GeoMipMap) для вычисления ε, мы рассмотрели наихудший сценарий. Если это конкретное значение меньше, чем τ, то все значения ошибок GeoMipMap будут меньше, чем τ. И наоборот, если это значение будет выше чем τ, то будет как минимум, одна ошибка, которая слишком заметна (эквивалентно, больше, чем τ). Мы выбираем это δ при создании GeoMipMap и храним его. С этого момента, если упоминается δ или ε, подразумевается max{δ0, …, δn-1} и max{ε0, …, εn-1} GeoMipMap-ов (n — число значений δ или ε в GeoMipMap) ,

Terrain-MipMapping-3

Рисунок 3: Ошибка(искажение) вершины, если смотреть сбоку. Пунктирная линия представляет собой изменение-высоты (δ) геометрии, которое произойдет при удалении белой вершины. Точное значение изменения-высоты можно вычислить, вычитанием белой вершины из серой вершины. После удаления белой вершины позиция вершины будет в воображаемой серой вершине.

Чтобы узнать, целесообразно ли переключиться на более высокий уровень GeoMipMap для данного d, мы должны сравнить ε с τ для текущих GeoMipMap-ов. Если верно неравенство ε > τ, то переход на более высокий уровень приведет к слишком большому искажению. Если это не так, то разрешено переключиться на один уровень выше. Обратите внимание, что следующий уровень GeoMipMap-ов ε также ниже, чем τ, и в этом случае мы можем использовать этот уровень GeoMipMap и.т.д., до тех пор, пока не будет достигнут правильный уровень.
Правильное неравенство для решения вышеупомянутого условия можно найти в [1]. Эквивалент 3D-пространства, который использует 3D-эквивалент τ, можно найти в [4]. Формула, упомянутая в [1], вычисляет точное значение для ε с любой данной точки зрения относительно GeoMipMap. Чем выше наклон вектора просмотра камеры относительно GeoMipMap, тем меньше будет ε, и чем выше вероятность использования более высокого уровня GeoMipMap. Это означает, что, если вектор направления камеры параллелен плоскости x/z (то есть горизонтальный), ε будет иметь наивысший уровень. Мы можем использовать этот факт, чтобы ускорить наш алгоритм определения уровня GeoMipMap.

2.3.1.1 Ускорение определения уровня GeoMipMap

Из-за способности 3D-аппаратных средств прорисовки отображать большое количество треугольников, нам больше не нужно вычислять «идеальный набор» треугольников. Если использовать менее точный алгоритм, то в результате будет меньше нагрузка CPU, поэтому лучше использовать его, поскольку лучше создать лишние треугольники что бы тем самым высвободить дополнительные ресурсы CPU. Цель состоит в том, чтобы отправить столько треугольников на оборудование, сколько оно может обрабатывать.
Вернемся к определению уровня GeoMipMap. Вычисляя ε и сравнивая его с τ для каждого видимого GeoMipMap, каждый кадр может быть очень интенсивно обработан. Поскольку, согласно [1] и [4], ε зависит от d и положения камеры относительно положения GeoMipMap, нет способа предварительно вычислить ε для каждого d и поместить его в Look-Up Table ( LUT)(Таблица поиска). Но если мы будем рассматривать вектор направления камеры как постоянно горизонтальный (т.е. не вертикальный наклон), мы можем предварительно вычислить ε. Это не даст точных результатов в тех случаях, когда вертикальный наклон вектора просмотра камеры относительно GeoMipMap высок; он обычно будет использовать слишком высокую детализацию для этих случаев с высоким наклоном, но как мы читали в предыдущем параграфе это не должно быть проблемой. Мы существенно снизили нагрузку на CPU до минимума.
Чтобы еще больше ускорить эту обработку, во время загрузки-ландшафта вычисляются дополнительные поля данных в каждом уровне GeoMipMap, которое устанавливается на минимальный d (D), на котором этот уровень может использоваться. Теперь, что бы выбрать нужный уровень для каждого видимого GeoMipMap для каждого кадра, достаточно сравнить d с Dn (где n — уровень GeoMipMap-ов). См. Рисунок 4 с псевдокодом.

For Each GeoMipMap Level N             Для Каждого GeoMipMap Уровня N
    Compare L to DN                        Сравните L с DN
    if (L > DN) store to RESULT            Если (L > DN) сохраните в RESULT
End For                                Конец Для
return RESULT                          возврата RESULT

Рисунок 4: Псевдокод для выбора соответствующего уровня GeoMipMap, где L — расстояние от камеры до центра GeoMipMap в 3D, и D это Dn.

2.3.1.2 Предварительное вычисление d

Чтобы предварительно вычислить Dn для каждого уровня GeoMipMap, используйте уравнение, из Уравнение 1. Это уравнение принимает δ как параметр и возвращает соответствующую Dn. Обратите внимание, что желательно иметь симметричную пирамиду-видимости, которая должна быть настроена с использованием параметров (l, r, b, t, n, f) пирамиды-видимости.

 

Dn = |δ| · C

 

Уравнение 1: Используйте это уравнение что бы вычислить Dn для δ. C — константа, которая может быть вычислена с помощью уравнения, которое вы найдёте в Уравнении 1a)

 

C =
A
T

 

Уравнение 1a), используется для вычисления C. A и T, являются константами, которые могут быть вычислены с помощью уравнений, которые вы найдёте в 1b) и 1c) соответственно.

 

A =
n
|t|

 

Уравнение 1b), используемое для вычисления A. n — это плоскость отсечения, а t — верхняя координата плоскости отсечения, как в (l, r, b, t, n, f)

 

T =
2 · τ
vres

 

Уравнение 1c), используется для вычисления T. vres — это разрешение экрана по вертикали в пикселях.

Чтобы сохранить инструкцию с квадратным корнем каждый раз, когда расстояние от текущей камеры до GeoMipMap должно рассчитыватся в режиме реального времени, Уравнение 1 можно переписать, как показано в Уравнение 2. Предварительное вычисление Dn2 в режиме реального времени будет вычислять уменьшение расстояние от GeoMipMap до камеры d2 = (ex — cx)2 + (ey — cy)2 + (ez — cz)2, где e — вектор [ex, ey, ez], который является текущим положением камеры, и c — вектор [cx , cy , cz], который является центром текущего обрабатываемого GeoMipMap.

 

Dn2 = δ2 · C2

 

Уравнение 2: квадрат Уравнения 1, сохраняющий инструкцию с квадратным корнем для каждого вычисления d на каждый GeoMipMap за кадр.

2.3.2. Решение проблемы разрывов-геометрий

Когда два соседних GeoMipMap-а ландшафта имеют разные уровни детализации, будут возникать трещины на краях GeoMipMap-ов. Это нежелательно для любого приложения с рендерингом ландшафта, и этого следует избегать. Края GeoMipMap-ов с большей детализацией (т.е. больше вершин) содержат более полную информацию о карте высот, в отличие от краёв GeoMipMap-ов, с меньшей детализацией, и в местах где эти два GeoMipMap-а отделяются друг от друга общими ребрами, появляется разрывы-геометрии. Решение этой проблемы по сути подразумевает перерасстановку соединений вершин, чтобы края плотно подходили друг другу.
Один из способов решения этой проблемы, это добавить дополнительные вершины на край со стороны более низкого уровня детализации из двух GeoMipMap-ов, чтобы он подходил к краю GeoMipMap-а с большим количеством деталей. Это означает, что по умолчанию компоновка вершин и связывание вершин для низкого уровня GeoMipMap должны изменятся динамически и должны обновляться всякий раз, когда соседний GeoMipMap изменяет уровни. Дополнительная копия исходного GeoMipMap-а должна быть создана и сохранена в памяти. Это медленная и потребляющая память задача, поэтому этого способа следует избегать.
Другим способом решения этой проблемы является выровнять те вершины краёв с большей детализации GeoMipMap-а, которые добавляют детали, так что бы они соответствовали краю с более низкой детализацией GeoMipMap. Это вызовет так называемые T-junctions или T-vertices. Из-за неточностей с плавающей запятой они обеспечивают очень заметный эффект «отсутствия пикселей».
Я нашел хороший способ разрешения проблемы разрывов или трещин геометрий ландшафта, который не изменяет компоновку вершин уровня GeoMipMap, и не будет создавать эффект «недостающих пикселей». Единственное, что он делает, это изменяет связи (или индексацию) вершин для высокой детализации GeoMipMap. Взгляните на Рисунок 5. Вы увидите более высокую детализацию GeoMipMap-а, которая отделяет левый край (не показан на Рисунке 5) с более низкой детализацией GeoMipMap-а. Серые вершины несут дополнительные данные карты высот, что вызывает трещины. Путем пропуска этих вершин из «связывания», край будет бесшовно сопоставляться с более низкой детализацией GeoMipMap. Быстрый способ рендерить это — использовать два раздутых-треугольника для этого края, выходящих из верхней левой верхней чёрной вершины и черной вершины непосредственно под ним. Остальные вершины рисуются обычным способом. Этот процесс должен выполняться для каждого из четырех ребер, которые соединяют GeoMipMap с GeoMipMap-ами более низкой детализации. При реализации алгоритма это означает, что каждый GeoMipMap уровня 0 должен иметь ссылки на всех своих четырех соседей.
Недостатком этого метода является то, что при изменении связности вершин произойдет небольшое изменение (gouraud — гуро) затенения. Иногда это может быть пятнистость в режиме реального времени, но это едва заметно.

Terrain-MipMapping-4

Рисунок 5: Решение T-junctions и разрывы-геометрии ландшафта между более высоким уровнем (низкое разрешение) GeoMipMap с левой стороны. Обратите внимание: хотя вершины, отмеченные серым, они все еще являются частью этой сетки(mesh) GeoMipMap, они не будут рендерится из-за использования раздутых-треугольников. Пропуск предпочтительней добавления вершин, так как ничего не нужно менять для любого GeoMipMap-а. Они могут оставаться неизменными, единственное, что меняется, — это данные связывания.

3 ДОПОЛНЕНИЕ К ОСНОВНОМУ ПОДХОДУ

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

3.1. Трилинейный GeoMipMapping

Хотя использование пиксельных ошибок пространства-экрана для выбора уровней GeoMipMap приведет к значительному уменьшению появления дефектов, они все равно ещё изредка будут появляться, особенно когда τ задано высокое значение. Несмотря на то, что задание τ как 1 или меньше, исключает в целом их появление, это также означает, что вероятность использования более высокого уровня GeoMipMap (низкая детализация) будет очень низкой. Необходимо найти определенное значение τ, которое дает хороший баланс между сохранением низких значений количества-треугольников и сохранением появления-дефектов на достаточно низком уровне. Это значение уникально для каждого приложения. Чтобы сохранить количество треугольников низким, без каких-либо появляющихся дефектов, я снова использую аналогию с текстурным mipmapping, рассматривая технический прием, называемый Трилинейная Фильтрация(Trilinear Filtering).
Когда вы смотрите на обычный текстурный mipmapping, можно четко увидеть границы того, где два mipmap-а разных уровней касаются друг друга. Эти границы или линии, бывают на фиксированном расстоянии от камеры и могут быть устранены с помощью Трилинейной Фильтрации. Я не собираюсь объяснять детали Трилинейной Фильтрации здесь, но концепция проста. Вместо того, чтобы выбирать дискретный mipmap для определенного d и использовать его до достижения d, для которого может использоваться mipmap более высокого уровня, интерполяция mipmap с mipmap на один уровень выше, вычисляется с использованием дроби расстояния на оба mipmap-а с предварительно вычисленным d. Это даст плавное смешивание mipmap-ов для любого значения d. Этот же принцип может быть применен к GeoMipMap-ам. Посмотрите еще раз на Рисунок 2. Уровень GeoMipMap 0 имеет определенный предварительно рассчитанный d (D0), который указывает, какой d этого уровня может заменять предыдущий уровень для рендеринга. Следующий уровень имеет эквивалент d (D1). Если мы вычислим дробь между этими двумя, как показано в Уравнении 3, мы можем использовать эту дробь как множитель (см. Уравнение 4) для белых вершин уровня GeoMipMap 0. Это будет медленно «трансформировать(morphing)» уровень 0 в уровень 1 до d достигшего D1, после чего уровень 0 может быть заменен уровнем 1. Это по существу заменяет внезапное изменение (popping — выскакивать, появлятся) уровней GeoMipMap плавным переходом между ними.

 

t =
(d — Dn)
(Dn+1 — Dn)

 

Уравнение 3: Расчет интерполяционной дроби t. d — расстояние от камеры до GeoMipMap, Dn — предварительно рассчитанная d для текущего GeoMipMap, а Dn + 1 — предварительно рассчитанная d для следующего GeoMipMap.

 

v, = v — t · δv

 

Уравнение 4: Используется для вычисления нового положения вершин, v ,, для белых вершин v. δv — изменение высоты (ошибка геометрии) v. Смотрите Рисунок 3.

Любые белые вершины края, которые являются соседними с GeoMipMap-ами более низкой детализаций, не должны умножаться на t, поскольку они больше не вносят вклад в GeoMipMap (см. Раздел 2.3.2).

3.2 Основы Поступательного стриминга GeoMipMap

Существуют определенные приложения, которые требуют визуализации данных-ландшафта, которые не будут полностью помещаться в память. Чтобы решить эту проблему, необходимо загружать только те блоки ландшафта, которые необходимо рендерить или, которые расположены рядом с камерой, только их нужно загружать с диска и сохранять в памяти. Всякий раз, когда блоки ландшафта, которые еще не хранятся в памяти, становятся видимыми, их необходимо загружать с диска. Это можно сделать посредством стриминга.
При запуске приложения древо квадрантов генерируется для всей местности. Координаты узлов ограничивающих объёмов x и z могут быть вычислены заранее, и y-координата должна быть считаны из файла данных-ландшафта, растрового изображения.

Нам нужно пройти через каждый блок ландшафта и сделать следующее:

  1. Загрузить блок ландшафта
  2. Рассчитать ограничивающий объём блоков ландшафта и сохраните его в соответствующем листе
  3. Рассчитать все уровни GeoMipMap для этого блока ландшафта
  4. Вычислите Dn для каждого Уровня GeoMipMap и сохраните его в блоках ландшафта листа древа квадрантов.
  5. Стереть все GeoMipMapУровни и продолжить шаги с 1. по 5. для следующих блоков ландшафта

После этого у нас остается древо квадрантов всего ландшафта, каждый лист которого содержит все Dn значения его блоков ландшафта. Обратите внимание, что мы не сохранили никаких GeoMipMap-ов.
Во время выполнения, значения Dn видимых листьев древа квадрантов сравниваются с текущим d, и соответствующий уровень GeoMipMap создается с диска. Всякий раз, когда d меньше, чем загруженный в настоящий момент Dn GeoMipMap-ов, соответствующий уровень GeoMipMap создается поступательно. Это краткое описание технического приёма и оно может быть дополнительно расширено.

4 РЕЗУЛЬТАТЫ В РЕЖИМЕ РЕАЛЬНОГО ВРЕМЕНИ

Метод, описанный в этой статье, реализован в рамках Проекта E-mersion. В настоящее время он использует только базовый алгоритм; функции вроде тех что описаны в разделе 3, не были реализованы, хотя их и не сложно интегрировать их в средство рендеринга ландшафта E-mersion. На рисунке 6 показан скриншот GeoMipMap-ов в действии. Как вы можете видеть, блоки ландшафта, которые находятся дальше от зрителя, нарисованы с использованием высоких уровней из цепочки GeoMipMap (то есть с более низким разрешением), за исключением случаев когда ошибка геометрии слишком высока даже для этого расстояния.
Целые блоки ландшафта рисуются с использованием вызова одного drawprimitive с использованием индексированных вершин для дальнейшего ускорения рендеринга. В этой демонстрации используется τ = 8.0. Средняя частота кадров 50 с-1 достигается с примерно 11 000 треугольников на кадр, на PentiumII 434 МГц с видеокартой Diamond Viper 550 и 64 МБ ОЗУ.

Пробную демонстрацию можно найти на моем сайте (URL вверху этой статьи) на главной странице. И конечно же, требуется оборудование для 3D рендеринга.

Terrain-MipMapping-5

Рисунок 6: Смешение двух скриншотов полученных из одного и того же положения камеры, при рендеринга рельефа в E-mersion. Одно изображение которое четко показывает GeoMipMap-ы в действии.

5. ВЫВОД

В этой статье я описал метод рендеринга данных ландшафта с высокой скоростью с использованием аппаратного 3D-рендеринга. Из-за способности аппаратного 3D-рендеринга отображать большое количество треугольников, нужно разработать алгоритм, который использует это, и способен обрабатывать большое количество треугольников, сохраняя нагрузку на CPU на низком уровне. Это означает, что алгоритм должен прибегать к более консервативным методам отсечения, то есть не предоставляя «идеальный набор данных». Метод, описанный в этой статье, на мой взгляд является, подходящим решением этой проблемы. Избегая как можно большего количества проверок на треугольник, я написал расширение на основе-блочного Уровня Детализации. Уровень Детализации основанный на блоках оказался очень полезным и быстрым при использовании в аппаратном 3D-рендеринге из-за низкой нагрузки на CPU. Заметные появляющиеся дефекты — которые характерны методам УД на основе блоков — были уменьшены за счет использования пиксельных ошибок пространства экрана и могут быть полностью устранены с использованием описанного метода трилинейной «трансформации(morphing)». В то время как основанный на блоках УД использовался и раньше, я никогда не видел, чтобы он использовался подобно текстурным mipmap-ам в работе с GeoMipMap-ами. Этот метод не слишком сложно понять и, что более важно, он не приведет к сложному (читаемому: медленно) коду, что является одним из ключевых факторов при разработке алгоритмов, которые будут использоваться вместе с аппаратным 3D-рендерингом. Цитата «Keep It Simple, Stupid(Будь проще, тупица)» определенно относится к алгоритмам, использующим аппаратный 3D-рендеринг.

Об авторе

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

Благодарности

Спасибо Kent Kuné за помощь в разработке графического дизайна проекта E-mersion; Эдварду Кметту за то, что он дал мне полезные советы при решении проблем с разрывами-геометрий ландшафта; Саймону О’Коннору и Джакко Биккеру за то, что нашли время, чтобы прочитать и высказать своё мнение об ещё неготовой версии этой статьи; и Lourens Veen за то, что этот документ стало возможно просматривать как файл Portable Document Format(PDF).


Список цитированной литературы

1. Real-Time, Continuous Level of Detail Rendering of Height Fields. Peter Lindstrom, David Koller, William Ribarsky, Larry F. Hodges, Nick Faust, and Gregory A. Turner. In Proceedings of ACM SIGGRAPH 96, August
1996, pp. 109-118.
http://www.cc.gatech.edu/gvu/people/peter.lindstrom/

2. The NetImmerse Terrain System. Dave Eberly, Director of Engineering, Numerical Design, Ltd.
http://www.ndl.com/terrainwhitepaper.html

3. ROAMing Terrain: Real-time Optimally Adapting Meshes. Mark Duchaineau, LLNL, Murray Wolinksy, LANL, David E. Sigeti, LANL, Mark C. Miller, LLNL, Charles Aldrich, LANL, Mark B. Mineev-Weinstein, LANL.
http://www.llnl.gov/graphics/ROAM/

4. Continuous LOD Terrain Meshing Using Adaptive Quadtrees. Thatcher Ulrich, Slingshot Game Technology.
http://www.gamasutra.com/features/20000228/ulrich_01.htm

5. Real-Time Rendering. Tomas Möller, Eric Haines. A K Peters, Ltd. ISBN 1-56881-101-2


Переведено для jmonkeyengine.ru, оригинал.
Автор перевода: Andry

Добавить комментарий

Содержание

jMonkeyEngine.ru © 2017. Все права сохранены.