Создание ландшафтов с применением алгоритма ROAM

Материал из Blitz Et Cetera

Введение

Алгоритм ROAM (Real-time Optimally Adapting Meshes), основанный на структуре "Бинарное дерево треугольников", представляет Duchaineau et.al. и был реализован в движке Tread Marks (http://www.TreadMarks.com). Я не претендую на 100% достоверную передачу алгоритма, но постарался оптимизировать по своему усмотрению и добавил некоторые моменты, которые нельзя реализовать штатными средствами в блице (например, отрисовка группы треугольников). Добавленные или измененные мною моменты выделены в статье. Хотелось бы сразу отметить что пример не показывает обновляющийся в реалтайме террайн, а просто демонстрирует механизм работы алгоритма. Скорость блица не позволит сделать террайн обновляющийся каждый кадр быстрее чем встроенный в Блиц3д. Алгоритм ROAM довольно труден для восприятия и поэтому я постарался максимально подробно объяснить каждое действие и максимально иллюстрировать документ наглядным материалом.

Сущность ROAM метода

Основные понятия

Для построения ландшафта нам необходима карта высот. В нашем случае это будет массив вещественных чисел HeightMap#(TerrainSize,TerrainSize) , считанный из изображения. Ключевым понятием в методе ROAM является прямоугольный треугольник. Давайте рассмотрим его структуру:

Рассматриваемый треугольник образован тремя вершинами: левый вертекс (v0), вертекс верхушки (v1) и правый вертекс (v2). На середине расстояния между боковыми точками поставим точку и назовем её центральной точкой (vC). Если провести линию от вертекса верхушки к центральной точке, то мы разделим исходный треугольник на два дочерних: левый и правый потомки. Исходный треугольник при этом будет являться для них родительским. Каждый из полученных треугольников можно разделить точно так же. Таким образом, деля треугольники до определенного уровня мы можем детализировать ландшафт настолько насколько это необходимо:

Важным моментом является понятие соседа основания (base neighbor) - это тот треугольник, который своим основанием прилежит к основанию рассматриваемого треугольника.

Деление треугольников

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

погрешность=Abs((hLeft+hRight)/2-hCenter)

hLeft,hRight - это высота по карте высот в точках правого и левого вертекса.

hCenter - это высота по карте высот центральной точке

(hLeft+hRight)/2 - интерполированная высота над центральной точкой

Например, возьмем hLeft=15.0, hRight=25.0 и hCenter=23.0. По формуле погрешность равна Abs((15+25)/2-23)=Abs(20-23)=3. Чтобы определить является ли погрешность достаточной для деления, нам понадобится переменная, назовём её RoamMaxHeightError. Её значение характеризует максимально допустимую разницу высот между фактической и желаемой. Чем меньше её значение, тем больше ландшафт будет соответствовать действительности и тем больше рисовать полигонов. И наоборот чем больше её значение, тем грубее будет ландшафт и тем меньше полигонов занимать. Если принять RoamMaxHeightError=5, то треугольник дальше разбиваться не будет, т.к. погрешность<RoamMaxHeightError (3<5). Если же принять значение RoamMaxHeightError=2, то треугольник будет разбит, т.к. погрешность превышает максимально допутимый уровень погрешности (3>2). Для примера покажу несколько рендеров ландшафта 1024*1024 с разным значением RoamMaxHeightError. Высота ландшафта от -40.96 до 40.96.

Здесь наглядно видно преимущество метода: треугольники не тратятся на отрисовку относительно плоских поверхностей, а более детально обрабатывают выпуклые поверхности.

Бинарное дерево

Теперь разберемся, почему алгоритм основан на структуре "Бинарное дерево треугольников". Как видно из предыдущей картинки каждый треугольник имеет свой индивидуальный номер. Левому потомку присваивается номер (родитель<<1), а правому (родитель<<1)+1.

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

parent = Tri Shr 1

а сдвиг влево потомков:

LeftChild =Tri Shl 1

RightChild =(Tri Shl 1)+1;

Таким образом алгоритм построения ландшафта складывается из двух частей:

1. Сначала мы рекурсивно обходим треугольники, проверяя погрешность высоты. Если погрешность превышает RoamMaxHeightError то записываем в соответствующий байт в банке памяти 1 и проверяем погрешность высоты для его потомков (для них аналогично). Если же погрешность укладывается в RoamMaxHeightError то записываем в соответствующий байт 0 и переходим к следующему шагу.
2. Теперь строим меш ландшафта по созданному нами дереву.

Diamond split

Однако даже в таком простом и наглядном алгоритме есть одна проблема. Давайте рассмотрим на примере:

У нас есть треугольник. Рассмотрим процесс его деления по шагам.

1. Имеется треугольник 1. Определяем погрешность, допустим она больше текущего RoamMaxHeightError. Поэтому разделяем его на два дочерних: 2 и 3
2. Рассматриваем треугольники 2 и 3. Допустим погрешность в треугольнике 3 не больше RoamMaxHeightError и поэтому дальше его не делим. Теперь допустим, что погрешность в треугольнике 2 достаточна для его деления на треугольники 4 и 5.
3. Треугольник 3 не имеет потомков, его структура дальше не просчитывается. Теперь рассматриваем треугольники 4 и 5. Допустим, дальше треугольник 5 остается без изменений, а 4 делится на 8 и 9.
4. В итоге мы имеем поверхность, состоящую из треугольников 3,5,8,9. Обратим внимание на стык треугольников 3, 8 и 9. Как видно 8 и 9 представляют участки с большей детализацией и 3 с меньшей. Из за этого на поверхности ландшафта будут образовываться так называемые трещины. Вот как они выглядят:

Описанная ситуация решается довольно просто. Помните, в описании структур мы говорили и понятии "соседа основания "? Для того чтобы устранить зазор в поверхности необходимо разделить и соседа основания. В оригинальном документе два прилежащих основаниями треугольника называют Diamond, из-за похожести его на алмаз или бриллиант. А операция по их делению называется Split on a diamond, то есть его разделение. После того как сосед основания будет разделен, алгоритм переходит на его родителя и его соседа основания. И так до тех пор, пока не встретятся уже оба разделенных треугольника.

Мои добавления в метод

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

Таким образом, создается две структуры в памяти, соответствующие двум треугольникам. В таком случае соседом основания из первой структуры может стать треугольник из второй структуры, что непременно мы учтем в дальнейшем (например, треугольники 1-1, 5-6, 22-25 и т.д.). Условно назовём эти треугольники разными "ветками" (branch).

В оригинале для обозначения треугольника в памяти используется довольно обширная структура, содержащая ссылку на потомков треугольника, его родителя, соседа основания, соседей основания потомков. В моей версии из этой структуры остается два числа: ссылка на соседа основания и его флаг, показывающий является ли сосед основания из текущей структуры или из другой. В памяти объявим массивы: BaseNeighbor(maxtriangles) и BaseNeighborFlag(maxtriangles). Например, соседом треугольника 4 является 7 из той же структуры, т.е. BaseNeighbor(4)=7 и BaseNeighborFlag(4)=0. Или другой пример соседом треугольника 21 является треугольник 26 из другой структуры, тогда BaseNeighbor(21)=26 и BaseNeighborFlag(21)=1.

Следующей проблемой стал быстрый и четкий алгоритм поиска соседа основания для каждого треугольника. Можно конечно было скинуть эти данные на жесткий диск, но 5 мегабайт бинарных несжимаемых данных (для террайна 1024*1024) принесли бы мало радости. Результатом детального исследования стали следующие выводы:

1. Если уровень первый, то устанавливаем в качестве соседа основания треугольник 1 и флаг 1: BaseNeighbor(1)=1 и BaseNeighborFlag(1)=1.

2. Если треугольник является левым потомком родителя и его родитель является левым потомком прародителя, то базовым соседом искомого треугольника является правый потомок правого потомка прародителя. Посмотрите на рисунок 7. Возьмем, например, номер 12. он левый потомок шестого, а шестой - левый потомок третьего. Значит соседом 12 будет правый потомок правого потомка от 3, т.е. 15. Проверимся по рисунку 1 - это правда. Аналогичное правило действует наоборот если идти от правого потомка правого потомка. Все найденные таким образом потомки получают флаг 0, т.к. находятся в одной структуре.

3. Если найти прародителя не удается (второй уровень), то такие треугольники не имеют базовых соседей.

4. Если треугольник является правым потомком родителя, в то же время как родитель является левым потомком прародителя, в этом случае мы смотрим на прародителя. Если у него нет соседа основания, то и искомый треугольник не имеет соседа основания. Если же прародитель имеет соседа основания, то соседом основания искомого треугольника будет левый потомок правого потомка соседа основания прародителя.

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

Оба ландшафта построены с одинаковым значением RoamMaxHeightError=5. На первый ландшафт ушло 1426 поликов, а на второй 758. При этом на первом видно несколько довольно крупных горок, которые алгоритм упустил из виду во втором случае. Обязательная прорисовываемая сетка с крупными тайлами хоть и увеличивает количество полигонов, но значительно повышает качество отображения. Определим минимальный размер тайла, из которых будет составлен террайн, допустим

MinimumTileSize=64

Тогда минимальный уровень найдем как:

MinTileSizeLevel=2^(RoamTerrainWidth/MinimumTileSize)

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

Практическая реализация

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

Теперь нам необходимо загрузить картинку карты высот. Я использую не обычные черно белые картинки, а двухцветные: красная компонента отражает возвышения, а зеленая - углубления. Это позволяет сделать переходы более плавными. А также одна особенность: картинка имеет разрешение не кратное 2, а (кратное 2)+1 (не 256, а 257). Дабы не производить интерполяций, а сконцентрироваться на процессе создания террайна.

Из загруженной картинки мы узнаем размеры создаваемой поверхности и затем будем выделять память согласно необходимости. Создадим также переменную RoamTerrainMaxHeight# для определния максимальной высоты в карту высот при её загрузке.

Далее определение соседей основания. Сразу же объявим перменную RoamMaxTriangles, показывающую, сколько всего треугольников создается при текущем разрешении террайна. Создаем массивы, содержащие базового соседа и его флаг. Мы перечисляем все трегуольники и заносим данные сразу в массив прямо внутри функции

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

Далее мы объявляем нужные нам переменные для бинарного дерева треугольников. RoamCriticalLevel - треугольники с номером больше этой цифры неделимые, то есть принадлежат к самому высокому уровню детализации. Банки памяти для бинарных деревьев треугольников я сохранил в элементах массива для удобства доступа к ним. Один банк для ветки 0, другой банк для ветки 1. MinTileSizeLevel подробнее был описан выше.

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

Мы написали функцию, описывающую процесс разбиения треугольников. После её работы у нас имеется сформированное дерево треугольников, согласно которому мы и будем строить меш. Теперь сделаем небольшое отступление. В дереве имеется только информация о том строить ли треугольник по данным вершинам или нет, а о создании вершин в алгоритме как то не говорится. Когда мы строим треугольник, то у нас есть данные только о координатах вершин создаваемого треугольника. Создать все вершины сразу и строить по ним трианглы не получится, поэтому вершины будут строиться динамически. Создадим массив RoamVertex(RoamTerrainWidth,RoamTerrainWidth) в котором будем хранить информацию о том, создана ли вершина или нет. Если вершина создана то значение ячейки будет больше нуля. Т.к. первый вертекс в сюрфейсе имеет номер 0, то перед каждым обновлением будет создавать ни с чем не связаный нулевой вертекс, дабы упросить записи в архиве. Таким образом при создании треугольника проверяем значение всех вертексов треугольника в массиве, и если вершина не создана, то создаем её. После чего создаем треугольник по уже точно существующим вершинам. Таким образом, функция пробегает рекурсивно по дереву и если треугольник создан, то создавая по необходимости вершины добавляет в сюрфейс треугольник.

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

Вот в общем то и все основные принципы алгоритма изложены. Полный работающий пример можно скачать в аттаче

Дальнейшие оптимизации

Следующим шагом в создании ландшафта будет добавление динамической детализации. В рассмотренном примере значение RoamMaxHeightError для всей поверхности одинаковое. Для нас необходимо сделать ландшафт наиболее детализированным вблизи камеры. Всякие попытки находить расстояние до камеры и менять значение RoamMaxHeightError согласно этому расстоянию к положительному результату пока не привели. Расчет для каждой координаты расстояния до камеры через квадратный корень очень и очень затратно. Используя маски, тоже не удалось собрать простого и быстрого примера. Поэтому я предлагаю немного другой вариант. Можно создать массив содержащий номер треугольника по координатам и его принадлежность к какой либо из ветвей, например TriangleNumber(TerrainWidth,TerrainWidth,1) (где ",0)" -номер треугольника, ",1)" - номер ветки) и затем исходя из координаты камеры находить треугольники входящие в отрезок [CamX-Dist;CamX+Dist] [CamZ-Dist;CamZ+Dist] и применять к ним функцию RoamForceSplitTri. Заносить в массив стоит треугольники с номером менее RoamCriticalTriLevel, так как это соответствует минимально необходимому уровню. Координату треугольника можно определять по центральной точке. Каждой ячейке массива будет принадлежать только два треугольника, являющиеся соседями оснований. Перебрав все треугольники можно заполнить весь массив. Одна и та же ячейка будет заполняться дважды, треугольником и его соседом основания, так что неважно какой именно треугольник будет в массиве, они оба будут поделены функцией RoamForceSplitTri. Так же есть закономерность в распределении треугольников по уровням. Нарисовав простой рисунок можно выявить эту закономерность и заставить её служить на пользу.

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

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

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

1. Статья "Real-Time Dynamic Level of Detail Terrain Rendering with ROAM"

Bryan Turner

Gamasutra

URL: http://www.gamasutra.com/features/20000403/turner_01.htm

2. Перевод этой статьи на русский с дополнениями

Yatsenko Boris

Mail: proton2@mail.ru

URL: http://gamemaker.webservis.ru/

Автор: MadMedic (e-mail: MadMedicrambler.ru, сайт: http://MadMedic.by.ru, ICQ: 240693868)