A tér bináris particionálása

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. augusztus 2-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A bináris térbeli particionálás egy módszer az  euklideszi tér konvex halmazokra és hipersíkokra való rekurzív particionálására . Ennek eredményeként az objektumok egy BSP-fának nevezett adatstruktúraként jelennek meg .

A BSP fa a következő műveletek hatékony végrehajtására szolgál a 3D számítógépes grafikában :

A BSP fákat először a LucasArts használta a 80-as évek elején. A fejlesztők körében a Doom ( 1993 ) és a Quake ( 1996 ) motorokat kifejlesztő id Software - nek köszönhetően váltak népszerűvé .

Áttekintés

A BSP-fában minden csomópont egy 2D-s, illetve 3D-s térbeli hasítóvonalhoz vagy síkhoz van társítva. Ebben az esetben a sík elülső oldalán fekvő összes objektum az elülső részfához tartozik, és a sík hátsó oldalán fekvő összes objektum a hátsó részfához tartozik. Annak megállapításához, hogy egy objektum egy osztásvonal vagy sík elülső vagy hátsó oldalához tartozik-e, meg kell vizsgálni minden pontjának helyzetét. Egy pont helyzetét a síkhoz viszonyítva a sík normálisának skaláris szorzata és a pont homogén koordinátáinak koordinátái határozzák meg . Három eset lehetséges:

  1. A skaláris szorzat nagyobb, mint 0 - a pont a sík elülső oldalán található;
  2. A skaláris szorzat egyenlő 0-val - a pont a síkon fekszik;
  3. A skaláris szorzat kisebb, mint 0 - a pont a sík hátoldalán található.

Ha az objektum minden pontjára a skaláris szorzat nagyobb, mint 0, akkor a frontális részfához tartozik. Ha az objektum minden pontjára a skaláris szorzat kisebb, mint 0, akkor a fordított részfához tartozik. Ha egy objektum minden pontjára a skaláris szorzat egyenlő 0-val, akkor nem mindegy, hogy melyik részfához tartozik. Ha egy objektum pontjainak skaláris szorzatai eltérő előjelűek, akkor azt a hasítósík úgy vágja el, hogy a kapott objektumok csak az elülső vagy csak a hátoldalon feküdjenek. A BSP fa minden alcsomópontjára a fenti állítás igaz, azzal az eltéréssel, hogy csak azokat az objektumokat kell figyelembe venni, amelyek a szülőcsomópont felosztási síkjának elülső vagy hátsó oldalához tartoznak.

Faépítés

A fenti definíció csak a BSP fa tulajdonságait írja le , nem mondja meg, hogyan kell felépíteni. A BSP-fát általában egy síkon vagy térbeli sokszögeken lévő szegmensek halmazára építik fel, amelyek egy bizonyos ábrát vagy jelenetet képviselnek. Tekintsük a BSP-fa felépítésének algoritmusát egy térbeli sokszöghalmazhoz:

  1. Ha az adott sokszöghalmaz üres, akkor fejezzük be az algoritmust;
  2. Egy adott sokszöghalmazhoz válasszunk egy S hasítósíkot;
  3. Vágja ki az összes S-t metsző sokszöget;
  4. Az S elülső oldalán található összes sokszög hozzárendelése az elülső F részfához, és az S hátsó oldalán található összes sokszög a hátsó B részfához;
  5. Futtassa le az algoritmust rekurzívan az F frontális részfa sokszögeinek halmazára;
  6. Futtassa rekurzív módon az algoritmust a fordított B részfa sokszögeinek halmazára.

Választható hasítási sík

A felosztási síkot úgy választjuk meg, hogy egyensúlyba kerüljön a fa, vagyis hogy az elülső és a hátsó részfák sokszögeinek száma megközelítőleg azonos legyen:

min(|N(Fi) - N(Bi)|)

ahol N(Fi) az i hasítósík elülső oldalán lévő sokszögek száma, N(Bi) az i hasítósík hátoldalán lévő sokszögek száma.

Alkalmazás

Objektumok rendezése a megfigyelőtől való távolság szerint

Az objektumok megfigyelőből való eltávolításának sorrendjében történő rendezésekor a BSP fa segítségével a vektor és a megfigyelési pont ( POV ) egymáshoz viszonyított helyzetét, valamint a töréssíkok normálisait vizsgáljuk. Ha a hasítósík normálja és a megfigyelési vektor együtt irányított , akkor az elülső részfa távolabb van a megfigyelőtől, mint a fordított részfa, ellenkező esetben a fordított részfa távolabb van a megfigyelőtől, mint az elülső. Ebben az esetben, ha a hasító sík a megfigyelő mögött van, akkor maga a sík, valamint az elülső vagy hátsó részfa nem feltétlenül látható teljesen. A sokszögek BSP-fával történő rendezésének rekurzív algoritmusa a következő:

Eljárás bypassNode (csomópont) Ha Node <> NULLPointer Ha a vektorok együtt vannak irányítva (megfigyelési vektor, csomópont. osztott sík normál) Ha DotProduct(ObservationPoint, Node.Normal of SplitPlane) >= 0 // A sík a megfigyelő mögött van, a megfigyelő csak az elülső részfát látja TraverseNode(Node.FrontSubtree); Másképp // A repülő a megfigyelő előtt van, // az elülső részfa távolabb van, mint a hátsó részfa TraverseNode(Node.FrontSubtree); AddPolygonToDisplayList(Node.Polygon); TraverseNode(Node.ReverseSubtree); EndIf; Másképp Ha DotProduct(ObservationPoint, Node.Normal of SplitPlane) >= 0 // A repülő a megfigyelő előtt van, // a hátsó részfa távolabb van, mint az első részfa TraverseNode(Node.ReverseSubtree); AddPolygonToDisplayList(Node.Polygon); TraverseNode(Node.FrontSubtree); Másképp // A sík a megfigyelő mögött van, a megfigyelő csak a fordított részfát látja TraverseNode(Node.ReverseSubtree); EndIf; EndIf; EndIf; Vége;

Ez az algoritmus optimalizálható, ha figyelembe vesszük, hogy egy bizonyos sokszöghalmaz esetében a fa degenerált szerkezetű, abban az esetben, ha ebből a halmazból minden sokszögnél az összes többi sokszög csak az elülső vagy csak a hátsó oldalon található. John Carmack pontosan ezt tette a DOOM motorban . .

A rekurzívból való gyorsítás algoritmusa iteratívvá alakítható.

Láthatatlan felületek levágása

A láthatatlan felületek kivágása további információk , például keretek (határoló dobozok, határoló gömbök) beillesztésével valósul meg a BSP fában . A keretek  téglalapok vagy paralelepipedonok, körök vagy gömbök, amelyek korlátozzák azt a területet, ahol egy bizonyos részfa sokszögei találhatók. Így minden csomópontnak két kerete van. A részfa garantáltan láthatatlan, hacsak a vizuális piramis nem metszi a határoló objektumot. Ennek a fordítottja nem igaz. A közvetlen utasítás azonban elegendő jelentős számú objektum feldolgozásának megszakításához.

A kereteket ábrázoló geometriai objektumok kiválasztása a vizuális piramis és a keret metszéspontjának ellenőrzésére szolgáló algoritmus egyszerűségéből fakad.

Ütközések keresése

Ütközések keresésekor a BSP fa segítségével találjuk meg az objektumhoz legközelebb eső síkot. Leggyakrabban egy objektum határait határoló gömb (vagy kör) adja meg a számítások egyszerűsítése érdekében. A BSP fát a gyökértől az objektumhoz legközelebb eső síkhoz kell áthaladni. Ebben az esetben, ha a határoló gömbnek egyetlen síkkal sem metszéspontját észleljük, akkor nincs ütközés, ellenkező esetben igen.

Példa:

Ütközéskereső eljárás (csomópont, objektum) Ha Node <> NULLPointer Ha Távolság(Csomó.Sík, Objektum.HatárgömbKözép) > Objektum.HatárgömbRadius Ha DotProduct(Object.BoundingSphereCenter, SplitPlaneNode.Normal) >= 0 // A tárgy a törési sík elülső oldalán van, // csak az elülső részfán halad át FindCollision(Node.FrontSubtree, Object); Másképp // A tárgy a hasítósík hátoldalán van, // csak a fordított részfa bejárása FindCollision(Node.ReverseSubtree, Object); EndIf; Másképp A visszatérés ütközés; EndIf; Másképp Return No Collision; EndIf; Vége;

A rekurzívból való gyorsítás algoritmusa iteratívvá alakítható.

Irodalom

Linkek