Binääriavaruuden osiointi on menetelmä osioida rekursiivisesti euklidinen avaruus konveksiksi joukoiksi ja hypertasoiksi . Tämän seurauksena objektit esitetään tietorakenteena, jota kutsutaan BSP-puuksi .
BSP-puuta käytetään seuraavien toimintojen tehokkaaseen suorittamiseen 3D- tietokonegrafiikassa :
LucasArts käytti BSP-puita ensimmäisen kerran 80-luvun alussa. Ne saavuttivat suosiota kehittäjien keskuudessa id Softwaren ansiosta , joka kehitti Doom ( 1993 ) ja Quake ( 1996 ) moottorit.
BSP-puussa jokainen solmu liittyy jakoviivaan tai tasoon 2D- tai 3D-avaruudessa, vastaavasti. Tässä tapauksessa kaikki tason etupuolella makaavat objektit kuuluvat etualipuuhun ja kaikki tason takapuolella sijaitsevat kohteet kuuluvat taka-alipuuhun. Sen määrittämiseksi, kuuluuko kohde jakoviivan tai tason etu- vai takapuolelle, on tarpeen tutkia sen kunkin pisteen sijainti. Pisteen sijainti suhteessa tasoon määräytyy tason normaalin skalaaritulon ja pisteen homogeenisten koordinaattien koordinaattien avulla . Kolme tapausta on mahdollista:
Jos objektin kaikkien pisteiden skalaaritulo on suurempi kuin 0, niin se kuuluu frontaaliseen alipuuhun. Jos objektin kaikkien pisteiden skalaaritulo on pienempi kuin 0, niin se kuuluu käänteiseen alipuuhun. Jos objektin kaikkien pisteiden skalaaritulo on 0, ei ole väliä mihin alipuuhun se kuuluu. Jos objektin pisteiden skalaarituloilla on eri merkki, se leikataan halkaisutasolla siten, että tuloksena olevat kohteet sijaitsevat vain etupuolella tai vain kääntöpuolella. Jokaisen BSP-puun alisolmun kohdalla yllä oleva lause on tosi, sillä poikkeuksella, että vain ne objektit, jotka kuuluvat pääsolmun jakotason etu- tai takapuolelle, otetaan huomioon.
Yllä oleva määritelmä kuvaa vain BSP-puun ominaisuuksia , ei kerro kuinka se rakennetaan. BSP-puu rakennetaan pääsääntöisesti joukolle segmenttejä tasolle tai avaruuden monikulmioille, jotka edustavat tiettyä kuvaa tai kohtausta. Harkitse algoritmia BSP-puun rakentamiseksi avaruuden polygoneille:
Jakotaso valitaan siten, että puu tasapainotetaan, eli niin, että polygonien määrä etu- ja takaalipuussa on suunnilleen sama:
min(|N(Fi) - N(Bi)|)
missä N(Fi) on jonkin halkaisutason i etupuolella olevien polygonien lukumäärä, N(Bi) on halkaisutason i takapuolella olevien polygonien lukumäärä.
Lajittelemalla kohteita havainnolta poistumisjärjestykseen BSP-puun avulla tutkitaan vektorin ja havaintopisteen ( POV ) suhteellisia paikkoja sekä murtotasojen normaaleja. Jos jakotason normaali ja havaintovektori ovat suunnattu yhdessä , niin etuosapuu on kauempana havaitsijasta kuin käänteinen, muuten käänteinen alipuu on kauempana havaitsijasta kuin etuosapuu. Tässä tapauksessa, jos jakamistaso on havainnoijan takana, itse taso, samoin kuin etu- tai takaosapuu, eivät välttämättä ole täysin näkyvissä. Rekursiivinen algoritmi polygonien lajitteluun BSP-puun avulla on seuraava:
Menettelyn ohitussolmu (solmu) Jos solmu <> NULLPointer Jos vektorit ohjataan yhdessä (havaintovektori, solmu. jaetun tason normaali) Jos pistetuote(havaintopiste, solmu. splittason normaali) >= 0 // Taso on tarkkailijan takana, tarkkailija näkee vain etuosan alipuun TraverseSolmu(Solmu.Etualapuu); Muuten // Kone on tarkkailijan edessä, // edessä oleva alipuu on kauempana kuin taka-alipuu TraverseSolmu(Solmu.Etualapuu); AddPolygonToDisplayList(Solmu.Monikulmio); TraverseSolmu(Solmu.ReverseSubtree); Loppu Jos; Muuten Jos pistetuote(havaintopiste, solmu. splittason normaali) >= 0 // Kone on tarkkailijan edessä, // taka-alipuu on kauempana kuin etualipuu TraverseSolmu(Solmu.ReverseSubtree); AddPolygonToDisplayList(Solmu.Monikulmio); TraverseSolmu(Solmu.Etualapuu); Muuten // Taso on tarkkailijan takana, tarkkailija näkee vain käänteisen alipuun TraverseSolmu(Solmu.ReverseSubtree); Loppu Jos; Loppu Jos; Loppu Jos; loppu;Tämä algoritmi voidaan optimoida, jos otamme huomioon, että tietylle monikulmiojoukolle puulla on rappeutunut rakenne siinä tapauksessa, että jokaiselle tämän joukon polygonille kaikki jäljellä olevat polygonit sijaitsevat vain etupuolella tai vain takapuolella. Juuri tämän John Carmack teki DOOM - moottorissa . .
Rekursiivisesta nopeuttamisen algoritmi voidaan muuntaa iteratiiviseksi.
Näkymättömien pintojen leikkaaminen toteutetaan lisäämällä BSP-puuhun lisätietoa , kuten kehyksiä (rajoituslaatikot, rajoituspallot). Kehykset ovat suorakulmioita tai suuntaissärmiöitä, ympyröitä tai palloja, jotka rajoittavat aluetta, jossa tietyn alipuun monikulmiot sijaitsevat. Siten jokaisella solmulla on kaksi kehystä. Alipuu on taatusti näkymätön, ellei visuaalinen pyramidi leikkaa rajaavan objektin. Käänteinen ei ole totta. Suora lausunto riittää kuitenkin katkaisemaan huomattavan määrän kohteita.
Kehyksiä edustavien geometristen objektien valinta johtuu visuaalisen pyramidin ja kehyksen leikkauspisteen tarkistamiseen käytettävän algoritmin yksinkertaisuudesta.
Kun etsitään törmäyksiä, BSP-puuta käytetään löytämään kohdetta lähinnä oleva taso. Useimmiten kohteen rajat annetaan rajoittavalla pallolla (tai ympyrällä) laskelmien yksinkertaistamiseksi. BSP-puu kuljetetaan juuresta kohdetta lähinnä olevalle tasolle. Tässä tapauksessa, jos rajaavan pallon ja minkään tason leikkauspisteitä ei havaita, törmäystä ei ole, muuten on.
Esimerkki:
Törmäyshakumenettely (solmu, objekti) Jos solmu <> NULLPointer Jos etäisyys(solmu.taso, objekti.rajoituspallokeskus) > objekti.rajapallosäde Jos DotProduct(Object.BoundingSphereCenter, SplitPlaneNode.Normal) >= 0 // Esine on murtotason etupuolella, // kulkee vain etualipuun läpi FindCollision(solmu.etupuu, objekti); Muuten // Objekti on halkaisutason takapuolella, // kulkee vain käänteisen alipuun läpi FindCollision(Solmu.ReverseSubtree, Object); Loppu Jos; Muuten Paluu on törmäys; Loppu Jos; Muuten Paluu ei törmäystä; Loppu Jos; loppu;Rekursiivisesta nopeuttamisen algoritmi voidaan muuntaa iteratiiviseksi.
| Puu (tietorakenne) | |
|---|---|
| Binääripuut | |
| Itsetasapainottavat binaaripuut |
|
| B-puut | |
| etuliite puita |
|
Avaruuden binaarinen osiointi | |
| Ei-binääripuut |
|
| Avaruuden hajottaminen |
|
| Muut puut |
|
| Algoritmit | |