Войти
ПрограммированиеСтатьиГрафика

HSR-алгоритм: Рендеринг ландшафта на основе карты высот.

Автор:

Здесь я представлю HSR-алгоритм для ландшафтов на основе карты высот без LOD-а, наиболее эффективный для случаев, когда камера смотрит на ландшафт сверху или под углом не более 30° от этого направления. Этим я и ограничусь в этой заключительной части статьи. Я нисколько не преумаляю значения всевозможных Quad-Tree/Octree, но по ним и так есть немало статей во всемирной сети и даже на этом сайте (например, Разбиение объектного пространства сцены путём построения octree-дерева.), а потому рассматривать то, что либо уже всем известно, или хотя бы можно легко самостоятельно найти, не вижу смысла.

Итак, какой алгоритм здесь предлагаю я.

Для начала, вспомним, как выводилась регулярная сетка в первой части статьи. Вся сетка (ландшафт) делилась на вертикальные (условно) полосы, шириной в кэш (опять же условно). Каждая полоса выводится узкими горизонтальными полосками плотно прилегающими друг к другу. И эти полоски, и большие полосы можно склеить, и вывести весь ландшафт за один батч с помощью одного стрипа. Но нам то нужно не просто вывести всё в куче, а определить, какие части ландшафта видны и вывести по возможности только их, чтобы заведомо невидимой геометрии посылалось на графический конвейер как можно меньше. Как будем разбивать ландшафт? Очевидно, части не должны быть слишком большими, чтобы много геометрии не оказывалось за пределами пирамиды видимости, но с другой стороны они не должны быть и слишком маленькими чтобы не загружать CPU большим числом батчей. Для максимально полного выполнения первой части этого условия эти куски геометрии должны быть, либо размером с треугольник, либо... являться полоской треугольников шириной в один квад - если найти начало и конец такой полоски, чтобы она ограничивалась пирамидой видимости, получится, что лишних треугольников (за пределами видимости) выведено не будет, но... выводить каждую полоску отдельно нерационально по второй части условия, т.е. батчей будет слишком много. Я предлагаю некий компромисс. Т.е. выводить не полоску в один квад шириной, а... полосу, шириной в квадов 8 толщиной, к примеру. Представьте, что на ландшафт камера смотрит сверху и видит 1 млн. квадов (2 млн. тр-ков), 1000 по ширине и 1000 по высоте. Очевидно, выводить полосами такую сетку более эффективно, чем через quad-tree, т.к. в первом случае получается ~125 батчей, а во втором (для достижения такого же КПД скрытия невидимых поверхностей) - более 15 тыс. батчей!

Может показаться, что такие длинные полосы захватывают слишком много пространства за пределами видимости, т.к. при определении начала и конца такой полосы при пересечении с frustum-ом, не может корректно учитываться высота полосы - ведь полоса проходит через весь (!) ландшафт, а значит её высота должна браться как максимальная из высот вершин, в неё входящих, т.е. полоса получается очень высокой, хотя в данном положении камеры возможно виден лишь низменный участок всей полосы, с небольшими колебаниями высот. Но на самом деле, это не создаёт каких-либо проблем при виде сверху. Более того, в примере к статье высота таких полос вообще не учитывается и берётся равной... бесконечности. Посмотрите на рисунок.

Изображение

Здесь показан вид сбоку пирамиды видимости (frustum) и одной из полос (на таком виде все полосы, на которые делится ландшафт, идут "вглубь" рисунка, и на нём может быть показана лишь одна из полос). Камера смотрит вниз, и при таком виде, а также при небольшом уклоне камеры, очевидно, что различие высоты полосы (разные высоты обозначены пунктирными линиями) не играет никакой роли, т.к. начало и конец видимой части полосы определяется только по её нижней части, т.е. высоту полос можно действительно не учитывать в определении их видимой части.

Итак, недостатки и достоинства метода я рассмотрел. Остаётся только подробнее остановиться на его реализации.

Первое, что нужно знать, это то, какие вообще полосы могут быть видны. Для определения этого нам понадобится полигональное представление пирамиды видимости, которое надо "отсечь" плоскостью Z=0 (если ось Z направлена вверх - по высоте ландшафта, а 0 - минимальная высота точки на ландшафте). В результате такого отсечения получится небольшой меш, из которого затем берётся крайняя левая вершина и крайняя правая (по X). В итоге, видимые полосы лежат в интервале между X-координатами этих двух вершин. Ну, ещё первую координату надо округлить в меньшую сторону, а вторую - в большую на величину ширины полосы. На рис. ниже на виде сверху показано пересечение frustum-а с плоскостью Z=0 в виде синего прямоугольника. Зелёным отмечены видимые полосы.

Изображение

Далее, нужно пройтись по всем видимым полосам в цикле и определить начало и конец видимой части каждой полосы. Можно придумать для этого какой-нибудь специальный алгоритм, но я решил решать задачу в общем случае. Каждую полосу можно представить в виде двух плоскостей, являющимися границами полосы по X (слева и справа). Теперь возьмём уже рассчитанный меш-отсечение frustum-а плоскостью Z=0, и отсечём его двумя плоскостями конкретной полосы. Результат - меш, остаток от frustum-а после отсечения - нам нужен только ради координат его вершин, а точнее только ради Y-координат. Как говорилось выше, полосы - вертикальные, т.е. границы по Y-координатам вершин полученного меша и определят начало и конец видимой части полосы. Дальше надо просто округлить эти границы до целого (если длина/ширина квадов ландшафта равна 1) - начальную границу в меньшую сторону, а конечную в большую. Найденная видимая часть полосы выводится за один батч, установкой соответствующих аргументов функций - в glVertexPointer устанавливается нужное смещение, соответственно началу видимой части полосы, а в glDrawElements - кол-во элементов согласно разнице конца и начала видимой части полосы.

На рис. ниже зеленым теперь отмечены не видимые полосы целиком, а только видимые части полос, определённые по границам Y-координат вершин меша, как говорилось выше.

Изображение

Пример к статье выводит ландшафт 2048х2048 квадов (8 млн. треугольников) с освещением, но без текстур (чтобы не загромождать код). Нажатием ПРОБЕЛа можно увидеть рёбра пирамиды видимости и посмотреть «со стороны» на то, какие треугольники были отправлены на отрисовку - что-то вроде проверки эффективности удаления невидимых поверхностей. В среднем в каждом кадре примера выводится более 1.6 млн. тр-ков.

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

Пример к статье: 20061028.rar (200 Кб)

Ссылки:

Batch, Batch, Batch
Using VBOs
GPU Programming Guide
Radeon 9500/9600/9700/9800 OpenGL Programming and Optimization Guide - входит в ATI OpenGL SDK
Efficient use of H/W TnL

Автор выражает благодарность G'Dever-у за помощь в редактировании статьи.

#VBO, #карта высот, #ландшафт

28 октября 2006 (Обновление: 2 ноя. 2009)