BSP stromy

Při vykreslování objektů v prostoru narazíme na problém co vykreslit dřív a co později, aby to co je blíže pozorovateli překrývalo to co je od něj dál.

Nejjednodušším algoritmem je malířův algoritmus, ten postupně vykresluje objekty seřazené od nejvzdálenějšího k nejbližšímu. Ty co se vykreslí dřív budou překresleny těmi co se vykreslí později. Malířův algoritmus ztroskotá na příkladu který vidíme na obrázku vpravo. Kdybychom vykreslit tyto objekty v pořadí Q, P, S, R, vykreslil by se poslední objekt pruh R i přes zelený pruh Q, což je špatně. Tyto nedostatky řeší BSP stromy.

BSP strom je binární strom nesoucí informaci o rozdělení prostorů. Pokud rozdělíme prostor v němž se nachází naše barevné pruhy rovinou f(z)=3 vzniknou nám dva poloprostory - hodní A a spodní B'. A ty můžeme dělit dál. Pro ukázku jsme ještě B' rozdělili na B a C rovinou f(z) = 2. 

Do BSP stromu zapíšeme toto rozdělení tak jak vidíte na vlevo. Přičemž řešíme vztahy mezi poloprostory a podle toho je řadíme na pravou či levou větev.

Každý poloprostor pak obsahuje množinu polygonů, které do něj spadají.

Pro polygony vyznačené na obrázku vpravo by to vypadalo takto:

A = {P1, P2, S1, S2, R4, R3, Q4, Q3}

B = {P3, S3, R2, Q2}

C = {P4, S4, R1, Q1}

Vytváření BSP stromů

To jak co nejlépe rozdělit prostor tak a by byl výsledný strom co nejmenší je velké dilema. Vesměs se BSP stromy vytvářejí rekurzí a to tak že vybereme nějaký polynom, jeho rovinou rozdělíme prostor dva poloprostory. Dělící polygon umístíme do kořene a polygony do větví, podle toho zda jsou před ním nebo za ním. Celý postup opakujeme na poloprostory ve větvích, čímž se nám strom košatí. Pokud některá z dělících rovin prochází jedním polygonem, rozpůlíme ho.