Использование PVS - дерева

Введение

PVS — Potentially Visible Set (Потенциально видимый набор) — один из методов отсечения невидимой геометрии, основанный на расчете видимости в разных точках на протяжении всего уровня. В ситуациях, когда расчет сложен, просчитать видимость возможно только на этапе пре-процессинга, что хорошо подходит для статичных игровых сцен.

Весь игровой (не игровой) уровень разделяется на сегменты равного или произвольного размера.

В процессе отрисовки берём позицию камеры и смотрим, в каком сегменте находимся. После этого, в зависимости от типа найденных данных, смотрим какие объекты нужно рисовать для данной позиции (в каждом сегменте сохранён список видимых объектов), или перед отрисовкой объекта проверяем видим ли он (каждый сегмент хранит информацию о видимости всех остальных).

Учимся работать с PVS деревом в движке

Сначала составим логическое визуальное PVS - дерево. Представим, что камера (наблюдатель) находится в комнате номер 1, визуально определим по рисунку, что камера (наблюдатель) может увидеть из этой комнаты. Это будут комнаты 2 и 3, не забываем, что и комната 1 тоже видна. По аналогии определим видимые объекты для всех комнат (представляя, что камера поочередно находится в них).

В итоге, получится структура данных, представленная в таблице:

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

Запись данных в движке

Для записи данных в движке создан специальный класс PVS.

Сначала познакомимся с методами этого класса, необходимыми для создания PVS - дерева:

• addMeshToPVS() - метод добовляет в PVS - дерево ключевой объект;


• addElement() - метод добовляет потенциально видимый объект по ключу (по ключевому объекту);


• addElements() - метод добовляет потенциально видимые объекты (представленные в виде индексированного массива) по ключу (по ключевому объекту).

Теперь перейдем непосредственно к записи данных. Допустим, все объекты (комнаты) конвертировали встроенным в движок классом MeshConverter в классы (с именами Room1, Room2,..., Room14).

Создадим метод и назовем его например, setupGeometries. В нем добавим все объекты (комнаты) на сцену и запишем во временный буфер (индексированный массив, созданный в основном классе) ссылки на объекты (комнаты). Можно и не добавлять временный буфер, а брать объекты с корневого объекта сцены this.scene.root.children.

private function setupGeometries():void

{

var mesh:Mesh;

mesh = new Room1();

this.tempArray.push(mesh);

this.scene.addChild(mesh);

mesh = new Room2();

this.tempArray.push(mesh);

this.scene.addChild(mesh);

mesh = new Room3();

this.tempArray.push(mesh);

this.scene.addChild(mesh);

mesh = new Room4();

this.tempArray.push(mesh);

this.scene.addChild(mesh);

mesh = new Room5();

this.tempArray.push(mesh);

this.scene.addChild(mesh);

mesh = new Room6();

this.tempArray.push(mesh);

this.scene.addChild(mesh);

mesh = new Room7();

this.tempArray.push(mesh);

this.scene.addChild(mesh);

mesh = new Room8();

this.tempArray.push(mesh);

this.scene.addChild(mesh);

mesh = new Room9();

this.tempArray.push(mesh);

this.scene.addChild(mesh);

mesh = new Room10();

this.tempArray.push(mesh);

this.scene.addChild(mesh);

mesh = new Room11();

this.tempArray.push(mesh);

this.scene.addChild(mesh);

mesh = new Room12();

this.tempArray.push(mesh);

this.scene.addChild(mesh);

mesh = new Room13();

this.tempArray.push(mesh);

this.scene.addChild(mesh);

mesh = new Room14();

this.tempArray.push(mesh);

this.scene.addChild(mesh);

}

Теперь создадим метод и назовем его например, addPVS. Не забываем, что в индексированном массиве первый элемент записывается под индексом 0, т.е если надо получить объект Room1, обращаемся к нулевому индексу (this.tempArray[0]).

private function addPVS():void

{

var pvs:PVS = new PVS();

// Добавляем в PVS - дерево ключевые объекты (комнаты), берем данные из таблицы.

pvs.addMeshToPVS(this.tempArray[0]);

pvs.addMeshToPVS(this.tempArray[1]);

pvs.addMeshToPVS(this.tempArray[2]);

pvs.addMeshToPVS(this.tempArray[3]);

pvs.addMeshToPVS(this.tempArray[4]);

pvs.addMeshToPVS(this.tempArray[5]);

pvs.addMeshToPVS(this.tempArray[6]);

pvs.addMeshToPVS(this.tempArray[7]);

pvs.addMeshToPVS(this.tempArray[8]);

pvs.addMeshToPVS(this.tempArray[9]);

pvs.addMeshToPVS(this.tempArray[10]);

pvs.addMeshToPVS(this.tempArray[11]);

pvs.addMeshToPVS(this.tempArray[12]);

pvs.addMeshToPVS(this.tempArray[13]);

// Добавляем потенциально видимые объекты по ключу (ключевому объекту), берем данные из таблицы.

var elements:Array;

elements = [this.tempArray[0], this.tempArray[1], this.tempArray[2]];

pvs.addElements(this.tempArray[0], elements);

elements = [this.tempArray[1], this.tempArray[0], this.tempArray[2], this.tempArray[3], this.tempArray[7]];

pvs.addElements(this.tempArray[1], elements);

elements = [this.tempArray[2], this.tempArray[0], this.tempArray[1], this.tempArray[3], this.tempArray[7], this.tempArray[4], this.tempArray[8]];

pvs.addElements(this.tempArray[2], elements);

elements = [this.tempArray[3], this.tempArray[2], this.tempArray[7], this.tempArray[4], this.tempArray[5], this.tempArray[1], this.tempArray[8]];

pvs.addElements(this.tempArray[3], elements);

elements = [this.tempArray[4], this.tempArray[3], this.tempArray[5], this.tempArray[2], this.tempArray[7], this.tempArray[6]];

pvs.addElements(this.tempArray[4], elements);

elements = [this.tempArray[5], this.tempArray[3], this.tempArray[4], this.tempArray[6]];

pvs.addElements(this.tempArray[5], elements);

elements = [this.tempArray[6], this.tempArray[5], this.tempArray[4]];

pvs.addElements(this.tempArray[6], elements);

elements = [this.tempArray[7], this.tempArray[3], this.tempArray[2], this.tempArray[8], this.tempArray[9], this.tempArray[1], this.tempArray[4]];

pvs.addElements(this.tempArray[7], elements);

elements = [this.tempArray[8], this.tempArray[7], this.tempArray[9], this.tempArray[2], this.tempArray[3]];

pvs.addElements(this.tempArray[8], elements);

elements = [this.tempArray[9], this.tempArray[7], this.tempArray[8], this.tempArray[10], this.tempArray[11], this.tempArray[12]];

pvs.addElements(this.tempArray[9], elements);

elements = [this.tempArray[10], this.tempArray[12], this.tempArray[11], this.tempArray[9], this.tempArray[13]];

pvs.addElements(this.tempArray[10], elements);

elements = [this.tempArray[11], this.tempArray[10], this.tempArray[9], this.tempArray[12]];

pvs.addElements(this.tempArray[11], elements);

elements = [this.tempArray[12], this.tempArray[13], this.tempArray[10], this.tempArray[9], this.tempArray[11]];

pvs.addElements(this.tempArray[12], elements);

elements = [this.tempArray[13], this.tempArray[12], this.tempArray[10]];

pvs.addElements(this.tempArray[13], elements);

// Итак, создали и заполнили PVS - дерево, осталось только передать его в сцену.

this.scene.pvs = pvs;

}

private function addPVS():void

{

var pvs:PVS = new PVS();

pvs.addElements(pvs.addMeshToPVS(this.tempArray[0]), [this.tempArray[0], this.tempArray[1], this.tempArray[2]]);

pvs.addElements(pvs.addMeshToPVS(this.tempArray[1]), [this.tempArray[1], this.tempArray[0], this.tempArray[2], this.tempArray[3], this.tempArray[7]]);

pvs.addElements(pvs.addMeshToPVS(this.tempArray[2]), [this.tempArray[2], this.tempArray[0], this.tempArray[1], this.tempArray[3], this.tempArray[7], this.tempArray[4], this.tempArray[8]]);

pvs.addElements(pvs.addMeshToPVS(this.tempArray[3]), [this.tempArray[3], this.tempArray[2], this.tempArray[7], this.tempArray[4], this.tempArray[5], this.tempArray[1], this.tempArray[8]]);

pvs.addElements(pvs.addMeshToPVS(this.tempArray[4]), [this.tempArray[4], this.tempArray[3], this.tempArray[5], this.tempArray[2], this.tempArray[7], this.tempArray[6]]);

pvs.addElements(pvs.addMeshToPVS(this.tempArray[5]), [this.tempArray[5], this.tempArray[3], this.tempArray[4], this.tempArray[6]]);

pvs.addElements(pvs.addMeshToPVS(this.tempArray[6]), [this.tempArray[6], this.tempArray[5], this.tempArray[4]]);

pvs.addElements(pvs.addMeshToPVS(this.tempArray[7]), [this.tempArray[7], this.tempArray[3], this.tempArray[2], this.tempArray[8], this.tempArray[9], this.tempArray[1], this.tempArray[4]]);

pvs.addElements(pvs.addMeshToPVS(this.tempArray[8]), [this.tempArray[8], this.tempArray[7], this.tempArray[9], this.tempArray[2], this.tempArray[3]]);

pvs.addElements(pvs.addMeshToPVS(this.tempArray[9]), [this.tempArray[9], this.tempArray[7], this.tempArray[8], this.tempArray[10], this.tempArray[11], this.tempArray[12]]);

pvs.addElements(pvs.addMeshToPVS(this.tempArray[10]), [this.tempArray[10], this.tempArray[12], this.tempArray[11], this.tempArray[9], this.tempArray[13]]);

pvs.addElements(pvs.addMeshToPVS(this.tempArray[11]), [this.tempArray[11], this.tempArray[10], this.tempArray[9], this.tempArray[12]]);

pvs.addElements(pvs.addMeshToPVS(this.tempArray[12]), [this.tempArray[12], this.tempArray[13], this.tempArray[10], this.tempArray[9], this.tempArray[11]]);

pvs.addElements(pvs.addMeshToPVS(this.tempArray[13]), [this.tempArray[13], this.tempArray[12], this.tempArray[10]]);

this.scene.pvs = pvs;

}

Возможно у вас остался вопрос: "Почему и за счет чего, PVS -дерево дает прирост скорости рендеринга?"

Рассмотрим на нескольких примерах, за счет чего повышается производительность:

Пример A, рисунок ниже.

Камера (наблюдатель) находится в 1 комнате и смотрит вниз (в сторону 3 комнаты).

При рендеринге без PVS - дерева в пирамиду видимости попадают комнаты: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 и все они проходят через конвеерную обработку (через все алгоритмы) и рисуются на экран, т.е движок выводит на экран 10 комнат.

При рендеринге с PVS - деревом в пирамиду видимости попадают комнаты: 1, 2, 3 и рисуются только они, т.е. движок проводит мат. расчеты и рисует только 3 комнаты, а не 10.

Пример Б, рисунок ниже.

Камера (наблюдатель) находится в 14 комнате и смотрит в левый нижний угол рисунка (в сторону 6 комнаты).

При рендеринге без PVS - дерева в пирамиду видимости попадают комнаты: 14, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 и все они проходят через конвеерную обработку (через все алгоритмы) и рисуются на экран, т.е движок выводит на экран 11 комнат, хотя визуально понятно, что мы смотрим в стену 14 комнаты и не можем видеть другие комнаты.

При рендеринге с PVS - деревом в пирамиду видимости попадает и соответственно рисуется только комната 14, т.е. движок проводит мат. расчеты и рисует всего одну комнату, а не 11.

Пример и исходник к уроку

Этот пример и более полный исходник вы можете скачать.