Бинарна подела простора
Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
У рачунарству, бинарна подела простора (БСП) је метод за рекурзивну поделу простора.
Ова подела доводи до представљања објеката унутар простора путем структуре стабла података, познате као БСП стабло.
Бинарна подела простора је развијена у контексту 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. Примените овај алгоритам на листу полигона иза П.
Следећи дијаграм илуструје коришћење овог алгоритма у конвертовању листе линија или полигона у БСП стабло.
Коначан број полигона или линија у дрвету је често већи од оригиналног списка, јер полигони или линије морају да се поделе на два дела. Пожељно је да се минимизира овај пораст, али и да се одржи разуман биланс у крајњем дрвету. Стога је важан избор полигона (у првом кораку алгоритма) за стварање ефикасног БСП стабла.
Референце уреди