BSP дървета: теория и реализация. Част III

Преводни и оригинални статии в областта на разработката на игри.
gemicha
Site Admin
Site Admin
Мнения: 2930
Регистриран: 20 ное 2003 22:20
Местоположение: USA

BSP дървета: теория и реализация. Част III

Мнение от gemicha » 13 яну 2004 12:00

Автор: Samuel Ranta-Eskola
Превод: Иван Колев
Публикувано с разрешение на DevMaster.net

Продължение ...


Анализ на сложността

Извикването на CHOOSE-DIVIDING-POLYGON е от порядък O(n<sup>2</sup> lg n), който присъства и в остатъка от функцията, освен в рекурсивните извиквания. Ако допуснем че разделянето на множеството полигони е почти равно, можем да формулираме следната функция за пресмятане на ограничението на GENERATE-BSP-TREE:

T(n) = 2T(n/2) + O(n<sup>2</sup> lg n)

Използвайки "Master" теоремата [5, глава 4.3] получаваме че порядъкът на сложността е tita (n<sup>2</sup> lg n), където n е броят на полигоните във входящото множество.

Следва пример за генериране на BSP-дърво. Структурата по-долу е началното множество полигони, които сме номерирали за удобство. Това множество ще бъде разделено на BSP-дърво.

<center>
Изображение
Фигура 6: Примерна структура
</center>


За да можем да пуснем алгоритъма, трябва да изберем две константи, а именно: MINIMUMRELATION и MINRELATIONSCALE. Намерихме, че ако изберем MINIMUMRELATION = 0.8 и MINRELATIONSCALE = 2 ще получим добър резултат, но с тези числа би могло да се експериментира. Колкото по-голямо е MINIMUMRELATION, толкова по-балансирано ще е дървото, но може би ще се увеличи и броят на разцепените полигони.

Началното множество полигони очевидно не е изпъкнало, така че може да бъде избран разделящ. След бърз поглед върху структурата виждаме че полигони {1,2,6,22,28} не могат да бъдат използвани, понеже дефинират изпъкналата обвивка на множеството. Но всички останали полигони са кандидати за разделящ. Полигоните които разцепват минимален брой други полигони и дават най-добро съотношение между размерите на двете подмножества са 16 и 17 - те лежат на една и съща линия и не разцепват друг полигон. Двете получени подмножества са почти еднакви, а именно по 15 и 13 полигона съответно в отрицателното и положителното. Да изберем полигон 16 за разделящ. Резултатът изглежда така:


<center>
Изображение
Фигура 7: Резултатът от разделянето с полигон 16
</center>


Нито лявото, нито дясното поддърво съдържат изпъкнало множество полигони, така че и в двете трябва да бъде избран нов разделящ полигон.

В лявото поддърво {1,2,6,7} са от изпъкналата обвивка, значи не могат да бъдат избрани. Полигони 4 и 10 са на една линия и не разцепват никой от останалите. Размерите на подмножествата са по 7 и 8 полигона съответно в отрицателното и положителното, което е добър баланс. Избираме 4 за разделящ.

{16,17,22,23,28} съдържат дясното поддърво, така че не могат да бъдат разделящи. Полигоните които не разцепват други са {18,19,27,26}, но размерите на получените подмножества ще бъдат 3 и 11. 3/11 е под минималното отношение (0.5), така че ще трябва да проверим другите полигони за по-балансирано решение. Всеки от {20,21,24,25} разцепва точно по един полигон, но най-балансирани подмножества се получават за полигон 21, който след разцепване на полигон 22 дава подмножества с размери 6 и 8.

Това е резултатът след тези операции:

<center>
Изображение
Фигура 8: Втората стъпка
</center>

Никое от поддърветата не съдържа изпъкнало множество, така че алгоритъмът продължава по същия начин; полученото дърво ще изглежда така:

<center>
Изображение
Фигура 9: Окончателното дърво
</center>

Въпреки че това не е оптималното решение, то е доста близо до него и не отнема толкова много време.

Изобразяване на BSP-дървото

След като BSP-дървото е създадено, изобразяването на полигоните в него е много лесно, с нулева вероятност за дефект в изображението. По-долу е описан алгоритъмът на този процес. Преполагаме че функцията IS-LEAF при подаден BSP-възел връща true ако е възелът е листо, иначе false.

Код: Избери всички

> DRAW-BSP-TREE
* Вход:
*   Node – Възелът за изобразяване.
*   Position – Позицията на наблюдателя.
* Изход:
*   Няма
* Ефект:
*   Изобразява полигоните съдържащи се във възела и неговите поддървета.

DRAW-BSP-TREE (Node, Position)
1  if (IS-LEAF(Node))
2      DRAW-POLYGONS (Node.PolygonSet)
3      return
 
   // Пресмятаме в кое поддърво се намира наблюдателят.
4  Side = CLASSIFY-POINT (Node.Divider, Position)
 
   // Ако наблюдателят е в дясното поддърво, изобразяваме първо него.
5  if (Side = INFRONT || Side = COINCIDING)
6      DRAW-BSP-TREE (Node.RightChild, Position)
7      DRAW-BSP-TREE (Node.LeftChild, Position)
 
   // Иначе изобразяваме първо лявото.
8  else if(Value = BEHIND)
9      DRAW-BSP-TREE (Node.LeftChild, Position)
10     DRAW-BSP-TREE (Node.RightChild, Position)
Този начин на изобразяване не дава никакво намаление на броя полигони, които се изобразяват на екрана. Тъй като една карта може да се състои от стотици хиляди полигони, това не е добро решение. Възлите, или дори полигоните, които не се виждат, би трябвало да се отхвърлят. Това се нарича скриване на невидимите повърхности. Има няколко начина да се направи това, ще обясним някои от тях в следващата статия от серията.

Четива по темата

Sunsted, Tod. 3D computer graphics: Moving from wire-frame drawings to solid, shaded models
Sobey, Anthony. Software Engineering
Southwick, Andrew R. Quake Rendering Tutorial
Meanie, Mr.. Binary Space Partitioning Trees
Royer, Dan. Dan’s Programming Tutorials
Feldman, Mark. Introduction to Binary Space Partioning Trees
Литература
Shumacker, R., Brand, R., Gilliland, M., Sharp, W. Study for Applying Computer-Generated Images to Visual Simulation
http://www.idsoftware.com/
Sobey, Anthony. Software Engineering and Sunsted, Tod. 3D computer graphics: Moving from wire-frame drawings to solid, shaded models
Feldman, Mark. Introduction to Binary Space Partioning Trees, 1997
Cormen, Thomas H. Leiserson, Charles E. and Rivest, Ronald L.: Introduction to Algorithms

Речник

FPS - Екшън от първо лице, игра която се гледа от погледа на играча и където целта е да се елиминират опонентите.

Карта- Обект, който съдържа геометрията на света.

BSP-дърво - Дърво на двоично разделяне на пространството, дървовидна структура използвана за разбиване на картата на по-малки части.

Z-стойност - Това е оценка за близостта на полигона до позицията на наблюдателя.

Честота на кадрите - Брой обновявания на екрана в секунда. Това няма нищо общо с честотата на развивката на монитора. Това е броят изобразявания на света в секунда. Обикновено трябва да е над 30 пъти в секунда, за да създаде плавно усещане.

Предварителна обработка - Изчисления които се извършват преди изпълнението на програмата, като по този начин спестяват ценно процесорно време, което може да се използва за други цели.

Полигон - Полигон е равнинна фигура, състояща се от върхове и ръбове. Триъгълникът, квадратът, шестоъгълникът са полигони, но и всяка затворена поредица от отсечки образува полигон. Важното за нашето приложение е, че всички върхове трябва да лежат в една равнина.

Уравнение на равнина - Математическата формула за равнина в триизмерното пространство. Ax+By+Cz+D, където A-D са константните коефициенти на уравнението, A-C е нормалата към равнината, а D е разстоянието от началото на координатната система до равнината, по посока на нормалата й.

Възел - Част от дърво. Всеки възел има ляво и дясно поддърво.

Превод: Иван Колев
Публикувано с разрешение на http://www.DevMaster.net

Отговори