MadMedic's HomePage | Статьи | Создание ландшафтов с применением алгоритма ROAM

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

1 Введение

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

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

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

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

Картинка 0

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

Картинка 1

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

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

Теперь рассмотрим, по какому принципу происходит деление родительского треугольника на дочерние. Чтобы узнать необходимо ли нам разбивать треугольник, нужно определить насколько форма описываемвая треугольником отличается от фактической высоты по 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.

Картинка 2

Рисунок	RoamMaxHeightError	Количество полигонов
2.1	10.0	323
2.2	2.0	5032
2.3	0.75	25348

Таблица 0

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

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

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

Картинка 3

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

parent = Tri Shr 1

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

LeftChild =Tri Shl 1
RightChild =(Tri Shl 1)+1;

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

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

2.4 Diamond split

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

Картинка 4

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

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 с меньшей. Из за этого на поверхности ландшафта будут образовываться так называемые трещины. Вот как они выглядят:

Картинка 5

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

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

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

Картинка 6

Таким образом, создается две структуры в памяти, соответствующие двум треугольникам. В таком случае соседом основания из первой структуры может стать треугольник из второй структуры, что непременно мы учтем в дальнейшем (например, треугольники 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, т.к. находятся в одной структуре.
   Картинка 7
   
3. Если найти прародителя не удается (второй уровень), то такие треугольники не имеют базовых соседей.
4. Если треугольник является правым потомком родителя, в то же время как родитель является левым потомком прародителя, в этом случае мы смотрим на прародителя. Если у него нет соседа основания, то и искомый треугольник не имеет соседа основания. Если же прародитель имеет соседа основания, то соседом основания искомого треугольника будет левый потомок правого потомка соседа основания прародителя.
   Картинка 8
   

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

Картинка 9

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

MinimumTileSize=64

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

MinTileSizeLevel=2^(RoamTerrainWidth/MinimumTileSize)

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

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

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

Graphics3D 640,480,0,2
Global RoamMaxHeightError#=5.0
Global MinimumTileSize=64

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

Картинка 10

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

;Устанавливаем максимальную высоту
RoamTerrainMaxHeight#=40.96
;Грузим картинку
HmapImage=LoadImage("roam_hmap.jpg")
;Достаем из картинки раземр террайна
Global RoamTerrainWidth=ImageWidth(HmapImage)-1
;создаем массив с картой высот
Dim RoamTerrainHeight#(RoamTerrainWidth,RoamTerrainWidth)
;считываем массив из картинки
SetBuffer ImageBuffer(HmapImage)
LockBuffer ImageBuffer(HmapImage)
For PixX=0 To RoamTerrainWidth
For PixY=0 To RoamTerrainWidth
        Pixel=ReadPixelFast(PixX,PixY)
        RedColor=(Pixel Shr 16) And ($000000FF)
        GreenColor=(Pixel Shr 8) And ($000000FF)
        RoamTerrainHeight#(PixX,PixY)=(RedColor/255.0)*RoamTerrainMaxHeight-(GreenColor/255.0)*RoamTerrainMaxHeight
Next
Next
UnlockBuffer ImageBuffer(HmapImage)
SetBuffer BackBuffer()
;Удаляем картинку, она нам более не нужна
FreeImage HmapImage

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

;маскимальное количество треугольников в террайне

RoamMaxTriangles=RoamTerrainWidth*RoamTerrainWidth*2-1
;массивы содержащие базового соседа и его флаг
Dim RoamBaseNeighbor%(RoamMaxTriangles)
Dim RoamBaseNeighborFlag%(RoamMaxTriangles)

Function  FindTriBaseNeighbor(Number)
;если для данного треугольника уже задан сосед, то мы пропускаем
If RoamBaseNeighbor(number)>0 : Return : EndIf
;если это треугольник 1,2 или 3
If Number<4
        Select Number
                Case 1
                        RoamBaseNeighbor(Number)=1
                        RoamBaseNeighborFlag(Number)=1 ;сосед в другой структуре
                Case 2
                        RoamBaseNeighbor(Number)=0      ;нет соседа
                        RoamBaseNeighborFlag(Number)=0
                Case 3
                        RoamBaseNeighbor(Number)=0      ;нет соседа
                        RoamBaseNeighborFlag(Number)=0
        End Select
Return
EndIf
;поиск родителя и его обоих детей
Parent=Number Shr 1
ParentLeftChild=(Parent Shl 1)
ParentRightChild=(Parent Shl 1)+1

;поиск прародителя и его обоих детей
PraParent=Parent Shr 1
PraParentLeftChild=(PraParent Shl 1)
PraParentRightChild=(PraParent Shl 1)+1

;случай №3 в разделе "Мои добавления в метод " 
If Number=ParentLeftChild And Parent=PraParentLeftChild
        ;находим правого потомка правого потомка  прародителя,
        PraParentRightChildRightChild=(PraParentRightChild Shl 1)+1
        ;который является соседом основания искомого треугольника
        RoamBaseNeighbor(Number)=PraParentRightChildRightChild
        RoamBaseNeighborFlag(Number)=0
        ;искомый треуольник является также соседом основания
        ;правого потомка правого потомка прародителя
        RoamBaseNeighbor(PraParentRightChildRightChild)=Number
        RoamBaseNeighborFlag(PraParentRightChildRightChild)=0
Return
EndIf

;тот же случай №3 , но в обратную сторону
If Number=ParentRightChild And Parent=PraParentRightChild
        ;находим левого потомка левого потомка  прародителя,
        PraParentLeftChildLeftChild=(PraParentLeftChild Shl 1)
        ;который является соседом основания искомого треугольника
        RoamBaseNeighbor(Number)=PraParentLeftChildLeftChild
        RoamBaseNeighborFlag(Number)=0
        ;искомый треуольник является также соседом основания
        ;левого потомка левого потомка прародителя
        RoamBaseNeighbor(PraParentLeftChildLeftChild)=Number
        RoamBaseNeighborFlag(PraParentLeftChildLeftChild)=0
Return
EndIf

;Теперь проверяем есть ли у прародителя сосед основания

PraParentBaseNeighbor=RoamBaseNeighbor(PraParent)
PraParentBaseNeighborFlag=RoamBaseNeighborFlag(PraParent)

;если нет, то и у искомого быть не может
If PraParentBaseNeighbor=0
        RoamBaseNeighbor(Number)=0
        RoamBaseNeighborFlag(Number)=0
        Return
EndIf

;проверим случай №4
;если искомый треугольник првый потомок, а родитель - левый
If Number=ParentRightChild And Parent=PraParentLeftChild
        ;соседом будет левый потомок правого потомка соседа основания прародителя
    PraParentBaseNeighborRightChild=(PraParentBaseNeighbor Shl 1)+1
    PraParentBaseNeighborRightChildLeftChild=(PraParentBaseNeighborRightChild Shl 1)
        ;заносим в массив и копируем флаг от флага прародителя
    RoamBaseNeighbor(Number)=PraParentBaseNeighborRightChildLeftChild
    RoamBaseNeighborFlag(Number)=PraParentBaseNeighborFlag
        ; и наоборот
    RoamBaseNeighbor(PraParentBaseNeighborRightChildLeftChild)=Number
    RoamBaseNeighborFlag(PraParentBaseNeighborRightChildLeftChild)=PraParentBaseNeighborFlag
    Return
EndIf

;Теперь остается проверить случай №4 наоборот
;когда искомый треугольник левый потомок, а родитель - правый
If Number=ParentLeftChild And Parent=PraParentRightChild
        ;соседом будет левый потомок правого потомка соседа основания прародителя
    PraParentBaseNeighborLeftChild=(PraParentBaseNeighbor Shl 1)
    PraParentBaseNeighborLeftChildRightChild=(PraParentBaseNeighborLeftChild Shl 1)+1
        ;заносим в массив и копируем флаг от флага прародителя
    RoamBaseNeighbor(Number)=PraParentBaseNeighborLeftChildRightChild
    RoamBaseNeighborFlag(Number)=PraParentBaseNeighborFlag
        ; и наоборот
    RoamBaseNeighbor(PraParentBaseNeighborLeftChildRightChild)=Number
    RoamBaseNeighborFlag(PraParentBaseNeighborLeftChildRightChild)=PraParentBaseNeighborFlag
EndIf

End Function

;непосредственно перебор всех треугольников и поиск их соседей оснований
For CurrentNumber=1 To RoamMaxTriangles
  FindTriBaseNeighbor(CurrentNumber)


Next

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

;проверим несколько треугольников из дебага по картинке
For i=1 To 31
DebugLog "Tri# "+Str(i)+" Base neighbor: "+Str(RoamBaseNeighbor(i)) +" Flag: "+Str(RoamBaseNeighborFlag(i))
Next

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

;Все трегольники после этого числа не будут делиться
Global RoamCriticalTriLevel=RoamTerrainWidth*RoamTerrainWidth-1
;создаем банки памяти для хранения бинароного дерева треугольников
Dim RoamTriangle(1)
RoamTriangle(0)=CreateBank(RoamTerrainWidth*RoamTerrainWidth*2) ;ветка 0 - правый верхний треугольник
RoamTriangle(1)=CreateBank(RoamTerrainWidth*RoamTerrainWidth*2) ;ветка 1 - левый нижний треугольник
;Минимальная детализация
Global MinTileSizeLevel=2^(RoamTerrainWidth/MinimumTileSize)

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

; Функция, определяющая стоит ли бить треугольник или нет

Function RoamBreakTriangle(x0,z0,x1,z1,x2,z2,Number,Branch)

;если треугольник входит в число наиболее детализированных
If Number>RoamCriticalTriLevel
        ;помечаем как не битый и выходим
        PokeByte(RoamTriangle(Branch),Number,0)
        Return
EndIf

;Если треугольник входит в число треугольников наименьшей детализации
If Number=RoamMaxHeightError
        ; - " -
        xC=(x0+x2)/2
        zC=(z0+z2)/2
        LeftChild=(Number Shl 1)
        RightChild=(Number Shl 1)+1
        PokeByte(RoamTriangle(Branch),Number,1)
        RoamBreakTriangle(x1,z1,xC,zC,x0,z0,LeftChild,Branch)
        RoamBreakTriangle(x2,z2,xC,zC,x1,z1,RightChild,Branch)
        ; если у треугольника есть сосед основания то разбиваем
        ; его специальной функцией (см ниже)
        If RoamBaseNeighbor(Number)>0
                ;Обратите внимание что результирущая ветка находится через маску Xor
                RoamForceSplitTri(RoamBaseNeighbor(Number),Branch Xor RoamBaseNeighborFlag(Number))
        EndIf

EndIf
End Function 
;функция, разбивающая соседа основания треугольника
Function RoamForceSplitTri(Number,Branch)
;если треугольник уже разбит то выходим
If PeekByte(RoamTriangle(Branch),Number)=1
        Return
EndIf
;помечаем как разбитый
PokeByte(RoamTriangle(Branch),Number,1)
;пробуем разбить его соседа основания
If RoamBaseNeighbor(Number)>0
        RoamForceSplitTri(RoamBaseNeighbor(Number),Branch Xor RoamBaseNeighborFlag(Number))
EndIf
;и переходим к родителю
Parent=Number Shr 1
RoamForceSplitTri(Parent,Branch)

End Function

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

;создаем меш

Global RoamMesh=CreateMesh()
;помещаем меш в центр мира
PositionEntity RoamMesh,-0.5*RoamTerrainWidth,0,-0.5*RoamTerrainWidth
;грзим текстуру и текстурим
tex=LoadTexture("sand.jpg")
ScaleTexture tex,4,4
EntityTexture RoamMesh,tex
;создаем сурфейс и массив вертексов
Global RoamSurface=CreateSurface(RoamMesh)
Dim RoamVertex(RoamTerrainWidth,RoamTerrainWidth)

;функция создающая треугольник па банку памяти
Function RoamCreateTriangle(x0,z0,x1,z1,x2,z2,Number,Branch)
;если треугольник разбит, то переходм к его потомкам
 If PeekByte(RoamTriangle(Branch),Number)=1
        xC=(x0+x2)/2
        zC=(z0+z2)/2
        LeftChild=(Number Shl 1)
        RightChild=(Number Shl 1)+1
        RoamCreateTriangle(x1,z1,xC,zC,x0,z0,LeftChild,Branch)
        RoamCreateTriangle(x2,z2,xC,zC,x1,z1,RightChild,Branch)
        Return
Else
        ;или создаем тругольник

        ;проверяем создан ли вертекс 0
        If RoamVertex(x0,z0)=0
                RoamVertex(x0,z0)=AddVertex(RoamSurface,x0,RoamTerrainHeight(x0,z0),z0,x0,z0)
        EndIf

        ;проверяем создан ли вертекс 1
        If RoamVertex(x1,z1)=0
                RoamVertex(x1,z1)=AddVertex(RoamSurface,x1,RoamTerrainHeight(x1,z1),z1,x1,z1)
        EndIf

        ;проверяем создан ли вертекс 2
        If RoamVertex(x2,z2)=0
                RoamVertex(x2,z2)=AddVertex(RoamSurface,x2,RoamTerrainHeight(x2,z2),z2,x2,z2)
        EndIf
        ;создаем 
        AddTriangle (RoamSurface,RoamVertex(x0,z0),RoamVertex(x1,z1),RoamVertex(x2,z2))
EndIf
End Function

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

Function CreateLand()
;очищаем банки памяти обеих ветвей треугольников
FreeBank RoamTriangle(0)
FreeBank RoamTriangle(1)
;и создаем заново пустые
RoamTriangle(0)=CreateBank(RoamTerrainWidth*RoamTerrainWidth*2)
RoamTriangle(1)=CreateBank(RoamTerrainWidth*RoamTerrainWidth*2)
;пересоздаем массив вертексов
Dim RoamVertex(RoamTerrainWidth,RoamTerrainWidth)
;очищаем сурфейс и создаем вертекс 0
ClearSurface RoamSurface,1,1
AddVertex RoamSurface,0,0,0
;разбиваем треугольники
RoamBreakTriangle(0,RoamTerrainWidth,RoamTerrainWidth,RoamTerrainWidth,RoamTerrainWidth,0,1,0)
RoamBreakTriangle(RoamTerrainWidth,0,0,0,0,RoamTerrainWidth,1,1)
;создаем треугольники
RoamCreateTriangle(0,RoamTerrainWidth,RoamTerrainWidth,RoamTerrainWidth,RoamTerrainWidth,0,1,0)
RoamCreateTriangle(RoamTerrainWidth,0,0,0,0,RoamTerrainWidth,1,1)
;обновляем нормали
UpdateNormals(RoamMesh)
End Function

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

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

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

Картинка 11

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

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

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

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/

По всем замечаниям и предложениям обращаться на e-mail

(c) MadMedic 2005-2011