Создание сложной процедурной поверхности средствами GPU (Перевод) Часть 1

Исходная статья: http://http.developer.nvidia.com/GPUGems3/gpugems3_ch01.html 

Ryan Geiss
NVIDIA Corporation

1.1 Введение

Процедурные поверхности традиционно сводились к карте высот, создаваемой при помощи CPU и отображаемой видеокартой. Однако, CPU, выполняющий команды последовательно, плохо подходит для создания сложного ландшафта—хорошо распараллеливаемой задачи. К тому же, простые карты высот, которые могут быть получены при помощи CPU, не могут сформировать интересные особенности рельефа (например, пещеры или выступы).
Для получения рельефа высокой степени сложности, при достаточном количестве кадров в секунду, обратимся к GPU. Используя несколько новых возможностей DirectX 10, таких как геометрический шейдер (GS), потоковый вывод и отображение 3D текстур, мы можем использовать GPU для быстрого создания больших блоков сложного процедурного рельефа. Вместе эти блоки создают большую детализированную сетку из полигонов, которая отображает рельеф в рамках текущей пирамиды вида. Рисунок 1-1 демонстрирует это.

Рисунок 1-1 Рельеф, полностью созданный силами GPU

1.2 Алгоритм двигающихся кубов и функция плотности

На понятийном уровне, поверхность земли может быть описана функцией, называемой функцией плотности. Для каждой точки в трехмерном пространстве (x, y, z),функция принимает одномерное дробное значение. Значения варьируются, в зависимости от положения в пространстве,—от положительных до отрицательных. Если значение положительно, значит, точка находится внутри поверхности.
Если значение отрицательно, то такая точка находится снаружи (например, в воздухе или в воде). Граница между положительными и отрицательными значениями—там, где функция обращается в 0—и есть поверхность земли. Мы хотим построить сетку их полигонов в соответствии с этой поверхностью.
Мы используем GPU для создания полигонов для "блока" поверхности, в дальнейшем, эти блоки мы будем делить блоки на более мелкие 32x32x32 ячейки или воксели. Рисунок 1-2 показывает систему координат. Она находится внутри вокселя, где мы будем создавать полигоны (треугольники), которые отобразят земную поверхность. Алгоритм движения кубов позволяет создать правильные полигоны внутри единичного вокселя, принимая на вход значение плотности в каждом из восьми углов куба. На выходе мы получим до пяти полигонов. Если значение функции плотности во всех вершинах имеет одинаковый знак, то такая ячейка целиком находится внутри или во вне поверхности, то есть на выходе не получаем ни одного полигона. Во всех остальных случаях, ячейка лежит на границе земли и воздуха, поэтому на выходе будет от одного до пяти полигонов.

Рисунок 1-2 Система координат внутри вокселя

1.2.1 Создание полигонов внутри ячейки

Получение полигонов внутри ячейки принимает следующий вид: как видно из Рисунка 1-3, мы берем значение плотности во всех восьми углах и определяем, где значение положительно, а где - отрицательно. Для каждой вершины мы заводим один бит. Если плотность отрицательна, мы устанавливаем бит в ноль, иначе – в единицу.

Рисунок1-3 Воксель с известными значениями функции плотности
Затем мы логически объединим все биты ( побитовой операцией ИЛИ), чтобы получить байт, называемый экземпляр—принимающий значения 0–255. Если экземпляр равен 0 или 255, тогда ячейка целиком лежит внутри или вовне поверхности и, как было сказано ранее, не будет иметь ни одного полигона. Однако если значение экземпляра находится в диапазоне [1..254], то какое-то число полигонов будет получено.
Если экземпляр не равен ни 0, ни 255, то его используют, как индекс в таблице (в GPU используется буфер констант), чтобы определить, сколько полигонов нужно сгенерировать для каждого случая и способ их построения. Каждый полигон создается соединением трех точек (вершин) которые лежат на каком-то из 12 ребер ячейки. Рисунок 1-4 иллюстрирует основные варианты расположения полигонов в алгоритме двигающихся кубов.

Рисунок 1-4 14 основных случая алгоритма двигающихся кубов
Точное положение вершины на ребре определяют с помощью интерполяции. Вершина должна находиться в точке, где функция плотности примерно равна нулю. Например, если плотность в точке A равна 0.1, а в точке B равна -0.3, то вершина должна быть расположена на одной четвертой расстояния от A до B. Ближе к точке A.
Рисунок 1-5 иллюстрирует один из случаев. После использования экземпляра в качестве индекса таблицы, ребра, содержащие вершины, помечаются синими точками. Серые области показывают, как эти вершины должны быть соединены в треугольники. Заметим, что расположение точки на ребре зависит от значений весовой функции на концах этого ребра.

Рисунок 1-5 скрытые поверхности для преобразования в полигоны
Мы имеем на выходе список треугольников, то есть каждая тройка выходных вершин образует треугольник, а следующая за ней вершина – уже относится к другому треугольнику. Если по конкретному экземпляру нужно получить N полигонов, нам придется создать вершину (где-нибудь на грани ячейки) 3xN раз.

1.2.2 Таблицы поиска

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

1. int case_to_numpolys[256];  

   int case_to_numpolys[256];

Вторая таблица заметно больше. Получив значение экземпляра, таблица предоставляет информацию необходимую для построения до пяти треугольников внутри ячейки. Каждый из пяти треугольников описан как int3 value (3 целых числа); каждое из этих значений содержит номер ребра [0..11] которые должны быть соединены для получения треугольника. Рисунок 1-6 показывает порядок нумерации ребер.

1. int3 edge_connect_list[256][5];  

int3 edge_connect_list[256][5];

Рисунок 1-6 нумерация ребер вокселя

Например, если значения экземпляра 193, мы ищем значение case_to_numpolys[193], чтобы узнать, сколько полигонов надо получить, в данном случае - 3. Далее, edge_connect_list[193][] содержит следующие значения:

1. int3 edge_connect_list[193][0]:  11  5 10
   
2. int3 edge_connect_list[193][1]:  11  7  5
   
3. int3 edge_connect_list[193][2]:   8  3  0
   
4. int3 edge_connect_list[193][3]:  -1 -1 -1
   
5. int3 edge_connect_list[193][4]:  -1 -1 -1  

   int3 edge_connect_list[193][0]:  11  5 10

   int3 edge_connect_list[193][1]:  11  7  5

   int3 edge_connect_list[193][2]:   8  3  0

   int3 edge_connect_list[193][3]:  -1 -1 -1

   int3 edge_connect_list[193][4]:  -1 -1 -1

Для получение треугольников внутри ячейки, геометрический шейдер должен сгенерировать на выходе 9 вершин (соответствующие места на перечисленных ребрах)—формирующих 3 треугольника—для записи в вершинный буфер. Отметим, что последние два int3 имеют значения -1; они не будут использоваться, потому что мы знаем, что для данного экземпляра нужно получить всего 3 треугольника. GPU перейдет к следующей ячейке.
Мы рекомендуем скопировать таблицы с прилагаемого к этой книге DVD, потому что их создание может занять много времени. Таблицы могут быть найдены в файле models\tables.nma.

1.3 Обзор системы создания поверхности

Мы разбиваем мир на бесконечное количество одинаковых по размеру кубических блоков, как было описано ранее. В мировой системе координат, каждый блок имеет размер 1x1x1. Однако, внутри каждый блок - это 32³ вокселей, которые могут содержать полигоны. Пространство примерно из 300 буферов вершин динамически хранит те блоки, которые видны в пирамиде вида, причем, чем ближе блок, тем выше его приоритет. При попадании новых блоков в пирамиду вида (если пользователь начинает двигаться), самые удаленные вершинные буферы переиспользуются для новых блоков.
Не все блоки содержат полигоны. Обычно мы не можем узнать, содержит ли блок полигоны, до его создания. После создания каждого блока, выходной поток спрашивает GPU, были ли созданы полигоны. Блоки, не содержащие полигоны—как это обычно бывает—помечаются "пустыми" и кладутся в список, то есть они не буду бесполезно пересоздаваться. Также они не будут впустую занимать вершинный буфер.
Для каждого участка, мы сортируем все вершинные буферы (ограничивающие их параллелепипеды известны) от переднего края к дальнему. Далее если мы создаем несколько нужных нам блоков, мы выгружаем наиболее удаленные блоки из существующих, чтобы освободить вершинный буфер. В итоге, мы отображаем отсортированные блоки от начала к концу, то есть GPU не тратит время на обработку пикселей, которые будут закрыты другими частями поверхности.

1.3.1 Создание полигонов внутри блока поверхности

В целом, создание блока поверхности можно разбить на 2 шага. Подробнее мы рассмотрим их далее в соответствующих подпунктах.

1. Сначала, мы используем блоки пиксельных шейдеров (PS) для подсчета функции плотности каждого угла ячейки внутри и записываем результаты в большую 3D текстуру. Блоки создаются по одному за раз, поэтому нам достаточно одной общей 3D текстуры. Однако, так как текстура хранит функции плотности в углах ячейки, ее размер 33x33x33, предпочтительнее чем 32x32x32 (количество ячеек в блоке).
   
2. Далее, мы осматриваем каждый воксель и создаем нужные полигоны внутри него, если это необходимо. Полигоны выписываются в буфер вершин, где они могут хранится и выводится на экран, пока они находятся в пределах видимости.

1.3.2 Получение значений плотности

Отображение в 3D текстуру – отчасти новая идея, то есть этому необходимы некоторые объяснения. Для GPU 3D текстура представима как массив 2D текстур. Для запуска PS, который записывает в каждый пиксель слоя, мы рисуем два треугольника, которые вместе покрывает отображаемый слой. Для покрытия всех слоев, мы используем исключение. В DirectX, это означает не более чем вызов ID3D10Device::DrawInstanced() (это лучше, чем вызов обычной функции Draw()) с параметром numInstances равным 33. Эта процедура эффективно рисует пару треугольников 33 раза.
Вершинный шейдер (VS) узнает, какой экземпляр рисуется в данный момент, установкой входного атрибута, используя SV_InstanceID; эти значения из диапазона от 0 до 32, в зависимости от того, какой экземпляр отображается. VS может передать это значение геометрическому шейдеру, который выведет в атрибут SV_RenderTarget - ArrayIndex. Семантика определяет, к какому слою 3D текстуры (целевого массива) на самом деле относится треугольник. В этом случае, PS по каждому пикселю 3D текстуры. На DVD смотри shaders\1b_build_density_vol.vsh и .gsh.
В общем, PS, отображающий эти треугольники, получает на вход мировые координаты и выдает дробное значение функции плотности. Математика, которая преобразует вход к выходу, и есть наша функция плотности.

1.3.3 Создание интересующей нас функции плотности

Единичный вход весовой функции:

1. float3 ws;  

     float3 ws;

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

• Выборка из исходных текстур, таких как 1D, 2D, 3D, и кубических карт
  
• Буферы констант, таких как таблицы
  
• Математические функции, такие как cos(), sin(), pow(), exp(), frac(), floor(), и арифметика

Для начала, расположим плоскость земли в y = 0:

1. float density = -ws.y;  

     float density = -ws.y;

Это разделит мир на положительные значения, которые ниже плоскости земли y = 0 (назовем землей), и отрицательные, которые выше этой плоскости (назовем воздухом). Хорошее начало! Рисунок 1-7 показывает результат.

Рисунок 1-7 Мы начинаем с плоской поверхности
Далее, сделаем поверхность более интересной, добавляя элемент случайности, как показано на Рисунке 1-8. Мы просто используем мировые координаты (ws) для выборки из маленькой (16³) повторяющейся 3D текстуры полной случайных значений ("шума") из диапазона [-1..1], следующим образом:

1. density += noiseVol.Sample(TrilinearRepeat, ws).x; 

density += noiseVol.Sample(TrilinearRepeat, ws).x;

Рисунок 1-8 Поверхность с одним уровнем шума
Рисунок 1-8 показывает как изменяет поверхность при добавлении однооктавного шума.
Отметим, что мы можем пересчитывать ws для смены частоты (частоты изменения шума в зависимости от положения в пространстве). Мы также можем пересчитывать результат выбора перед добавлением значения плотности; пересчет меняет амплитуду или силу шума. Для получения поверхности на Рисунке 1-9, следующая строчка шейдерного кода использует "функцию" шума с двойной частотой и половинной амплитудой:

1. density += noiseVol.Sample(TrilinearRepeat, ws*2).x*0.5; 

density += noiseVol.Sample(TrilinearRepeat, ws*2).x*0.5;

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

Рисунок 1-10 три октавы на высокой частоте создают больше деталей

1. density += noiseVol1.Sample(TrilinearRepeat, ws*4.03).x*0.25;
   
2. density += noiseVol2.Sample(TrilinearRepeat, ws*1.96).x*0.50;
   
3. density += noiseVol3.Sample(TrilinearRepeat, ws*1.01).x*1.00; 

density += noiseVol1.Sample(TrilinearRepeat, ws*4.03).x*0.25;

density += noiseVol2.Sample(TrilinearRepeat, ws*1.96).x*0.50;

density += noiseVol3.Sample(TrilinearRepeat, ws*1.01).x*1.00;

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

Рисунок 1-11 Добавление низкочастотного шума с большой амплитудой для создания гор