Бинарна подела простора

У рачунарству, бинарна подела простора (БСП) је метод за рекурзивну поделу простора.

Ова подела доводи до представљања објеката унутар простора путем структуре стабла података, познате као БСП стабло.

Бинарна подела простора је развијена у контексту 3Д компјутерске графике, где БСП структура стабла омогућава брзо приступање информацијама о објектима.

Преглед

Бинарна подела простора је генерички процес рекурзивне поделе на два дела док дељење задовољава један или више услова. Може се посматрати као генерализација других просторних структура стабла. Специфичан избор плана и критеријума зависи од сврхе БСП стабла.

На пример, у компјутерском графицкочком приказивању, сцена се дели док сваки чвор у БСП стаблу садржи само полигоне који се приказују у произвољном редоследу.

БСП стабла често користе 3Д видео игре.

Генерисање

Основна употреба БСП стабла је за приказивање полигона (који су двострани). Сваки полигон који би могао бити произвољно изабран је одредјен првом и другом страном.

Такво дрво је конструисано од несортиране листе свих полигона.

Рекурзивни алгоритам за израду БСП стабла од те листе полигона је:

1. Изабрати полигон П са листе.

2. Направити чвор Н у БСП стаблу и додати П на листу полигона у том чвору.

  1) Ako je taj poligon ceo ispred ravni koja sadrži P, pomerite taj poligon na listu čvorova ispred P.
  2) Ako je taj poligon ceo iza ravni koja sadrži P, pomerite taj poligon na listu čvorova iza P.
  3) Ako taj poligon preseca ravan koja sadrži P, podelite ga na dva poligona i pomerite ih na odgovarajućim listama poligona
     ispred i iza P.
  4)Ako taj poligon leži u ravni koja sadrži P, dodajte ga na listu poligona u čvor N.

4. Примените овај алгоритам на листу полигона испред П.

5. Примените овај алгоритам на листу полигона иза П.

Следећи дијаграм илуструје коришћење овог алгоритма у конвертовању листе линија или полигона у БСП стабло.

	Почните са листом линија (или у 3Д, полигона) које чине сцену. У дијаграмима стабала, листе се означавају заобљеним правоугаоницима и чворови у БСП стаблу круговима. У просторном дијаграму линија, правац линије се означава стрелицом.
и.	Пратећи кораке алгоритма Бирамо линију, А, са листе... ...и додајемо је у чвор Поделимо преостале линије у листи у оне испред А ( Б2, Ц2, Д2), и оне иза (Б1, Ц1, Д1). Прво обрадимо линије испред А (корацима ии-в) ... затим оне иза (корацима ви–вии).
ии.	Примењујемо алгоритам на листу линија испред А (Б2, Ц2, Д2). Изаберемо линиију, Б2, додајемо је у чвор и делимо остатак листе у оне линије које су испред Б2 (Д2), и оне које су иза (Ц2, Д3).
иии.	Изаберите линију, Д2, са листе линија испред Б2. То је једина линија на листи, тако да након што је додамо у чвор, ништа више не треба да се уради.
ив.	Обрадили смо линије испред Б2, па прелазимо на линије иза (Ц2 и Д3). Изаберемо једну од њих (Ц2), додамо је у чвор и ставимо другу линију (Д3) у листу линија испред Ц2.
в.	Сада погледамо листу линија испред Ц2. Постоји само једна линија (Д3), тако да је додајемо у чвор и настављамо.
ви.	Сада смо додали све линије испред А на БСП стабло, почињемо са листом линија иза А. Бирамо линију (Б1) са ове листе, додајемо Б1 у чвор и делимо остатак листе у линије испред Б1 (Д1) и линије иза Б1 (Ц1).
вии.	Обрадјујемо прву листу линија испред Б1, Д1 је једина линија на овој листи, тако да је додајемо у чвор и настављамо.
виии.	Гледајући следеће на листи линија иза Б1, једина линија на овој листи је Ц1, додамо је у чвор и БСП стабло је завршено.

Коначан број полигона или линија у дрвету је често већи од оригиналног списка, јер полигони или линије морају да се поделе на два дела. Пожељно је да се минимизира овај пораст, али и да се одржи разуман биланс у крајњем дрвету. Стога је важан избор полигона (у првом кораку алгоритма) за стварање ефикасног БСП стабла.

Спољашње везе

• БСП треес пресентатион
• Анотхер БСП треес пресентатион
• А Јава апплет тхат демонстратес тхе процесс оф трее генератион
• А Мастер Тхесис абоут БСП генератинг
• БСП Треес: Тхеорy анд Имплементатион
• БСП ин 3Д спаце