Страница 1 от 1

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

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

Въведение

Когато бил формулиран първоначалният алгоритъм на дърветата за двоично разделяне на пространството (BSP), идеята била да се използват за сортиране на полигоните от света. Причината била, че не съществували хардуерно ускорени Z-буфери, а софтуерната реализация на Z-буфер била твърде бавна. Сега тази употреба е излишна, понеже хардуерно ускорените Z-буфери съществуват. Вместо това BSP-дърветата се използват в много други области, като radiosity изчисления, изобразяване на света, мрежово програмиране и откриване на колизии.

Когато BSP-дърветата били описани за пръв път през 1969-а от Shumacker et al[1]., едва ли са били замислени като алгоритъм за разработване на софтуер за забавления. Обаче в началото на 90-те BSP-дърветата започват да се използват в игровата индустрия за подобряване на скоростта и увеличаването на детайлите в картите [*]. Първата игра използвала тази технология е Doom, създаден от Джон Кармак и Джон Ромеро, две легенди на игровата индустрия [2]. От тогава почти всички екшъни от първо лице (FPS [*]) използват тази техника.

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

BSP-дървета: основи

Дървото за двоично разделяне на пространството е структура, която (както подсказва името) разделя пространството на по-малки части. Със съвременните хардуерно ускорени Z-буфери ползата е, че се разглеждат по-малки обеми от данни за дадена позиция в пространството. Но в началото на 90-те BSP-дърветата били използвани да се сортират полигоните от сцената, за да могат да се рисуват отзад напред, т.е. полигонът с най-малка Z-стойност да се рисува последен[*]. Има и други начини да се сортират полигони така, че най-близкият полигон да се рисува последен, например алгоритъмът на художника[3], но малко от тях са евтини колкото BSP-дървото, тъй като сортирането на полигоните става по време на предварителната обработка[*] на картата, а не по време на изпълнение. Алгоритъмът на генериране на BSP-дърво всъщност е разширение на алгоритъма на художника[5]. Точно както и оригиналният дизайн на BSP, алгортъмът на художника работи като рисува полигоните в сцената отзад напред. Но той има няколко сериозни недостатъка:

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

<center>
Изображение
Фигура 1: Циклично препокриване[4]
</center>

BSP алгоритъмът

Оригиналната идея за създаване на BSP-дърво е да се вземе част от полигоните от сцената и да се раздели на по-малки части така, че всяко подмножество да е изпъкнало. Което значи че всеки полигон от подмножеството е пред всеки друг полигон от същото подмножество. Полигон 1 е пред полигон 2 ако всеки връх на полигон 1 е от положителната страна на равнината определена от полигон 2, или върху нея. Куб направен от полигони обърнати с лицата навътре е изпъкнало множество, докато куб от полигони с обърнати навън лица не е.

<center>
Изображение
Фигура 2: Разликата между изпъкнало и неизпъкнало множество
</center>

Функциите, които определят дали дадено множество от полигони е изпъкнало, изглеждат така:

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

> CLASSIFY-POINT
* Вход:
*   Polygon – Полигонът спрямо който се класифицира точката.
*   Point   - 3D-точка която се класифицира спрямо равнината дефинирана от полигона.
* Изход:
*   От коя страна на полигона е точката.
* Ефект:
*   Определя от коя страна на равнината дефинирана от полигона се намира точката.

CLASSIFY-POINT (Polygon, Point)
1 SideValue = Polygon.Normal * Point
2 if (SideValue = Polygon.Distance)
3     then return COINCIDING
4 else if (SideValue < Polygon.Distance)
5     then return BEHIND
6 else return INFRONT


> POLYGON-INFRONT
* Вход:
*   Polygon1 – Полигонът за който се определя дали другият е изцяло отпред.
*   Polygon2 – Полигонът който проверяваме дали е пред първия или не.
* Изход:
*   Дали вторият полигон е пред първия или не.
* Ефект:
*   Проверява всяка точка от втория полигон дали се намира пред първия. Ако е така,
*   считаме че вторият полигон е пред първия.

POLYGON-INFRONT (Polygon1, Polygon2)
1 for each point p in Polygon2
2     if (CLASSIFY-POINT (Polygon1, p) <> INFRONT)
3         then return false
4 return true

> IS-CONVEX-SET
* Вход:
*   PolygonSet – Множеството от полигони което проверяваме за изпъкналост
* Изход:
*   Изпъкнало ли е множеството или не.
* Ефект:
*   Проверява всеки полигон спрямо всеки друг полигон дали са един пред друг,
*   ако които и да е два полигона не изпълняват това условие, множеството не е
*   изпъкнало.

IS-CONVEX-SET (PolygonSet)
1 for i f 0 to PolygonSet.Length ()
2     for j f 0 to PolygonSet.Length ()
3         if(i <> j && not POLYGON-INFRONT(PolygonSet[i], PolygonSet[j]))
4             then return false
5 return true
Функцията POLYGON-INFRONT е несиметрично сравнение, т.е. ако Polygon2 е пред Polygon1, не е задължително Polygon1 да е пред Polygon2. Това се вижда лесно от следния пример:

<center>
Изображение
Фигура 3: Несиметричната природа на сравнението
POLGON-INFRONT
</center>

На фиг. 3 Polygon1 е пред Polygon2 понеже точките p3 и p4 са от положителната страна на Polygon2, но Polygon2 не е пред Polygon1 понеже p2 е зад Polygon1. Тази идея може да бъде леко модифицирана, понеже нуждата от изпъкнали множества не е толкова остра, когато могат да се използват хардуерно ускорени Z-буфери. По-нататък в тази серия статии ще бъде описано как може да се реши това.

Структурите от данни за BSP-дърво могат да се дефинират така:

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

class BSPTree
{
    BSPTreeNode RootNode          // Кореновият възел на дървото
}
class BSPTreeNode
{
    BSPTree Tree                  // Дърво на което принадлежи възелът
    BSPTreePolygon Divider        // Полигонът който лежи посредата на двете поддървета
    BSPTreeNode *RightChild       // Дясно поддърво на този възел
    BSPTreeNode *LeftChild        // Ляво поддърво на този възел
    BSPTreePolygon PolygonSet[]   // Множество от полигони в този възел
}
class BSPTreePolygon
{
    3DVector Point1               // Връх 1 на полигона
    3DVector Point3               // Връх 2 на полигона
    3DVector Point3               // Връх 3 на полигона
}
Както се вижда, всеки полигон е представен само от три точки. Това е така, защото хардуерът на графичните карти е проектиран да изобразява триъгълници. Но алгоритъмът за генериране на BSP-дървета е проектиран да работи с полигони с всякакъв брой върхове, стига те да са в една равнина.

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

Дефинирахме алгоритъм, POLYGON-INFRONT, който може да определи дали един полигон е от положителната страна на друг. Сега трябва да модифицираме алгоритъма така, че да може да разпознава дали вторият полигон пресича равнината определена от първия. Алгоритъмът изглежда така:

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

> CALCULATE-SIDE
* Вход:
*   Polygon1 – Полигон спрямо който проверяваме.
*   Polygon2 – Полигонът който проверяваме.
* Изход:
*   От коя страна на Polygon1 се намира Polygon2.
* Ефект:
*   Проверява всяка точка от втория полигон спрямо първия. Ако има точки от
*   положителната страна и няма от отрицателната, приемаме че Polygon2 е пред Polygon1.
*   Ако има точки от отрицателната страна и няма от положителната, приемаме че Polygon2
*   е зад Polygon1. Ако всички точки лежат върху равнината, считаме че Polygon2 е
*   копланарен с Polygon1. Последният възможен случай е да има точки и от двете страни
*   на равнината, тогава Polygon2 пресича Polygon1.

CALCULATE-SIDE (Polygon1, Polygon2)
1  NumPositive = 0, NumNegative = 0
2  for each point p in Polygon2
3     if (CLASSIFY-POINT (Polygon1, p) = INFRONT)
4         then NumPositive = NumPositive + 1
5     if (CLASSIFY-POINT (Polygon1, p) = BEHIND)
6         then NumNegative = NumNegative + 1
7  if (NumPositive > 0 && NumNegative = 0)
8     then return INFRONT
9  else if(NumPositive = 0 && NumNegative > 0)
10    then return BEHIND
11 else if(NumPositive = 0 && NumNegative = 0)
12    then return COINCIDING
13 else return SPANNING
Продължава ...