Binární dělení prostoru

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 2. srpna 2021; ověření vyžaduje 1 úpravu .

Binární dělení prostoru je metoda  rekurzivního rozdělování euklidovského prostoru do konvexních množin a nadrovin . V důsledku toho jsou objekty reprezentovány jako datová struktura nazývaná BSP strom .

Strom BSP se používá k efektivnímu provádění následujících operací ve 3D počítačové grafice :

BSP stromy byly poprvé použity LucasArts na počátku 80. let. Mezi vývojáři si získaly oblibu díky id Software , která vyvinula motory Doom ( 1993 ) a Quake ( 1996 ).

Přehled

Ve stromu BSP je každý uzel spojen s dělicí linií nebo rovinou ve 2D nebo 3D prostoru. V tomto případě všechny objekty ležící na přední straně roviny patří do předního podstromu a všechny objekty ležící na zadní straně roviny patří do zadního podstromu. K určení, zda objekt patří k přední nebo zadní straně dělicí čáry nebo roviny, je nutné prozkoumat polohu každého z jeho bodů. Poloha bodu vzhledem k rovině je určena skalárním součinem normály roviny a souřadnicemi bodu v homogenních souřadnicích . Jsou možné tři případy:

  1. Skalární součin je větší než 0 - bod leží na přední straně roviny;
  2. Skalární součin je roven 0 - bod leží v rovině;
  3. Skalární součin je menší než 0 - bod leží na zadní straně roviny.

Pokud je pro všechny body objektu skalární součin větší než 0, pak patří do frontálního podstromu. Pokud je pro všechny body objektu skalární součin menší než 0, pak patří do reverzního podstromu. Pokud je pro všechny body objektu skalární součin roven 0, pak nezáleží na tom, do kterého podstromu patří. Pokud mají skalární součiny pro body objektu jiné znaménko, pak je rozdělovací rovinou oříznut tak, že výsledné objekty leží pouze na přední nebo pouze na rubové straně. Pro každý poduzel stromu BSP platí výše uvedené tvrzení s tou výjimkou, že v úvahu podléhají pouze ty objekty, které patří k přední nebo zadní straně dělicí roviny nadřazeného uzlu.

Stavba stromu

Výše uvedená definice pouze popisuje vlastnosti stromu BSP , neříká, jak jej vytvořit. BSP-strom je zpravidla sestaven pro množinu segmentů na rovině nebo polygonů v prostoru, které představují určitou postavu nebo scénu. Zvažte algoritmus pro konstrukci BSP stromu pro sadu polygonů v prostoru:

  1. Pokud je daná množina polygonů prázdná, ukončete algoritmus;
  2. Pro danou sadu polygonů zvolte dělící rovinu S;
  3. Vyřízněte všechny polygony protínající se s S;
  4. Přiřaďte všechny polygony umístěné na přední straně S k přednímu podstromu F a všechny polygony umístěné na zadní straně S k zadnímu podstromu B;
  5. Spusťte algoritmus rekurzivně pro množinu polygonů frontálního podstromu F;
  6. Spusťte algoritmus rekurzivně pro sadu polygonů reverzního podstromu B.

Volba štípací roviny

Dělicí rovina je zvolena tak, aby vyvážila strom, to znamená, že počet polygonů v předním a zadním podstromu je přibližně stejný:

min(|N(Fi) – N(Bi)|)

kde N(Fi) je počet polygonů na přední straně nějaké dělicí roviny i, N(Bi) je počet polygonů na zadní straně dělící roviny i.

Aplikace

Řazení objektů v pořadí podle vzdálenosti od pozorovatele

Při řazení objektů v pořadí odebírání od pozorovatele se pomocí BSP stromu zkoumají vzájemné polohy vektoru a bodu pozorování ( POV ) a normály zlomových rovin. Jsou-li normála rozdělovací roviny a pozorovací vektor směrovány společně , pak je přední podstrom dále od pozorovatele než zadní, jinak je zadní podstrom dále od pozorovatele než přední. V tomto případě, pokud je dělící rovina za pozorovatelem, pak samotná rovina, stejně jako přední nebo zadní podstrom, nemusí být plně viditelná. Rekurzivní algoritmus pro řazení polygonů pomocí stromu BSP je následující:

Postup BypassNode(Node) If Node <> NULLPointer Pokud jsou vektory spoluřízeny (Vektor pozorování, Node.Normal Of SplitPlane) Pokud DotProduct(ObservationPoint, Node.Normal of SplitPlane) >= 0 // Rovina je za pozorovatelem, pozorovatel vidí pouze přední podstrom TraverseNode(Node.FrontSubtree); v opačném případě // Letadlo je před pozorovatelem, // přední podstrom je dále než zadní podstrom TraverseNode(Node.FrontSubtree); AddPolygonToDisplayList(Node.Polygon); TraverseNode(Node.ReverseSubtree); EndIf; v opačném případě Pokud DotProduct(ObservationPoint, Node.Normal of SplitPlane) >= 0 // Letadlo je před pozorovatelem, // zadní podstrom je dále než přední podstrom TraverseNode(Node.ReverseSubtree); AddPolygonToDisplayList(Node.Polygon); TraverseNode(Node.FrontSubtree); v opačném případě // Rovina je za pozorovatelem, pozorovatel vidí pouze obrácený podstrom TraverseNode(Node.ReverseSubtree); EndIf; EndIf; EndIf; Konec;

Tento algoritmus lze optimalizovat, pokud vezmeme v úvahu, že pro určitou množinu polygonů má strom degenerovanou strukturu, v případě, že pro každý polygon z této množiny leží všechny zbývající polygony pouze na přední nebo pouze na zadní straně. Přesně to udělal John Carmack v enginu DOOM . .

Algoritmus pro zrychlení z rekurzivního lze převést na iterativní.

Ořezávání neviditelných povrchů

Oříznutí neviditelných povrchů je implementováno zavedením dalších informací do BSP stromu , jako jsou rámce (ohraničující rámečky, ohraničující koule). Rámy  jsou obdélníky nebo rovnoběžnostěny, kruhy nebo koule, které omezují oblast, kde se nacházejí polygony určitého podstromu. Každý uzel má tedy dva rámce. Je zaručeno, že podstrom bude neviditelný, pokud vizuální pyramida neprotíná ohraničující objekt. Opak není pravdou. K odříznutí zpracování značného počtu objektů však stačí přímé prohlášení.

Volba geometrických objektů, které představují rámce, vychází z jednoduchosti algoritmu pro kontrolu průsečíku vizuální pyramidy s rámem.

Hledání kolizí

Při hledání kolizí se strom BSP používá k nalezení roviny nejblíže k objektu. Nejčastěji jsou hranice objektu dány ohraničující koulí (nebo kružnicí) pro zjednodušení výpočtů. Strom BSP se projde od kořene k rovině nejblíže objektu. V tomto případě, pokud nejsou detekovány žádné průsečíky ohraničující koule s žádnou rovinou, pak ke kolizi nedochází, jinak ano.

Příklad:

Postup vyhledávání kolizí (uzel, objekt) If Node <> NULLPointer If Distance(Knot.Plane, Object.BoundingSphereCenter) > Object.BoundingSphereRadius Pokud DotProduct(Object.BoundingSphereCenter, SplitPlaneNode.Normal) >= 0 // Objekt je na přední straně lomové roviny, // procházet pouze předním podstromem FindCollision(Node.FrontSubtree, Object); v opačném případě // Objekt je na zadní straně rozdělovací roviny, // procházet pouze zpětným podstromem FindCollision(Node.ReverseSubtree, Object); EndIf; v opačném případě Návrat je kolize; EndIf; v opačném případě Return No Collision; EndIf; Konec;

Algoritmus pro zrychlení z rekurzivního lze převést na iterativní.

Literatura

Odkazy