Rozdělení binárního prostoru - Binary space partitioning

Proces vytváření stromu BSP

Ve výpočetní technice je rozdělení binárního prostoru ( BSP ) metoda pro rekurzivní dělení prostoru na dvě konvexní sady pomocí hyperplanes jako oddílů. Tento proces dělení vede k reprezentaci objektů v prostoru ve formě stromové datové struktury známé jako strom BSP .

Rozdělení binárního prostoru bylo vyvinuto v kontextu 3D počítačové grafiky v roce 1969. Struktura stromu BSP je užitečná při vykreslování, protože může efektivně poskytovat prostorové informace o objektech ve scéně, jako jsou objekty seřazené zepředu dozadu s ohledem na diváka v daném místě. Mezi další aplikace BSP patří: provádění geometrických operací s tvary ( konstruktivní objemová geometrie ) v CAD , detekce kolizí v robotice a 3D videohrách, ray tracing a další aplikace, které zahrnují zpracování složitých prostorových scén.

Přehled

Rozdělení binárního prostoru je obecný proces rekurzivního rozdělení scény na dvě, dokud rozdělení nesplňuje jeden nebo více požadavků. Lze to považovat za zobecnění jiných prostorových stromových struktur, jako jsou k -d stromy a čtyřstromy , kde hyperplany, které rozdělují prostor, mohou mít jakoukoli orientaci, než aby byly zarovnány se souřadnicovými osami, jako jsou v k -d stromech nebo čtveřice. Při použití v počítačové grafice k vykreslení scén složených z rovinných polygonů jsou dělící roviny často voleny tak, aby se shodovaly s rovinami definovanými polygony ve scéně.

Konkrétní volba dělící roviny a kritéria pro ukončení procesu dělení se liší v závislosti na účelu stromu BSP. Například při vykreslování počítačové grafiky je scéna rozdělena, dokud každý uzel stromu BSP neobsahuje pouze polygony, které lze vykreslit v libovolném pořadí. Když se používá utracení zezadu , každý uzel proto obsahuje konvexní sadu polygonů, zatímco při vykreslování oboustranných polygonů obsahuje každý uzel stromu BSP pouze polygony v jedné rovině. Při detekci kolize nebo sledování paprsků lze scénu rozdělit na primitivy, na nichž jsou testy kolize nebo průniku paprsků jednoduché.

Rozdělení binárního prostoru vzniklo z potřeby počítačové grafiky rychle kreslit trojrozměrné scény složené z polygonů. Jednoduchý způsob kreslení takových scén je malířův algoritmus , který vytváří polygony v pořadí vzdálenosti od diváka, zezadu dopředu, maluje na pozadí a předchozí polygony s každým bližším objektem. Tento přístup má dvě nevýhody: čas potřebný k řazení polygonů v pořadí zezadu dopředu a možnost chyb v překrývajících se polygonech. Fuchs a spoluautoři ukázali, že konstrukce stromu BSP vyřešila oba tyto problémy poskytnutím rychlé metody třídění polygonů s ohledem na dané hledisko (lineární v počtu polygonů ve scéně) a rozdělením překrývajících se polygonů, aby se předešlo chybám, které může nastat u malířova algoritmu. Nevýhodou rozdělení binárního prostoru je, že generování stromu BSP může být časově náročné. Obvykle se proto provádí jednou na statické geometrii, jako krok před výpočtem, před vykreslováním nebo jinými operacemi v reálném čase na scéně. Náklady na konstrukci stromu BSP ztěžují a neefektivní přímou implementaci pohybujících se objektů do stromu.

Stromy BSP často používají 3D videohry , zejména střílečky z pohledu první osoby a osoby s vnitřním prostředím. Mezi herní motory využívající stromy BSP patří motory Doom (id Tech 1) , Quake (varianta id Tech 2) , GoldSrc a Source . Stromy BSP obsahující statickou geometrii scény se v nich často používají společně s vyrovnávací pamětí Z , aby správně sloučily pohyblivé objekty, jako jsou dveře a postavy, na scénu pozadí. Rozdělení binárního prostoru poskytuje pohodlný způsob ukládání a získávání prostorových informací o polygonech ve scéně, ale neřeší problém s určováním viditelného povrchu .

Generace

Kanonické použití stromu BSP je pro vykreslování polygonů (které jsou oboustranné, to znamená bez zpětného utracení ) pomocí malířova algoritmu. Každý mnohoúhelník je označen přední a zadní stranou, kterou lze zvolit libovolně a ovlivňuje pouze strukturu stromu, ale ne požadovaný výsledek. Takový strom je vytvořen z netříděného seznamu všech polygonů ve scéně. Rekurzivní algoritmus pro konstrukci stromu BSP z tohoto seznamu polygonů je:

1. Vyberte polygon P ze seznamu.
2. Vytvořte uzel N ve stromu BSP a přidejte P do seznamu polygonů v tomto uzlu.
3. Pro každý další polygon v seznamu:
   1. Pokud že polygon je zcela před rovinou obsahující P , pohyb, který polygon na seznam uzlů před P .
   2. Pokud že polygon je zcela za rovinou obsahující P , pohyb, který polygon na seznam uzlů za P .
   3. Je-li, že polygon protíná s rovinou obsahující P , rozdělit do dvou polygonů a přesunout je do příslušných seznamů polygonů za a před P .
   4. V případě, že polygon leží v rovině obsahující P , přidat do seznamu mnohoúhelníků v uzlu N .
4. Aplikovat tento algoritmus na seznam polygonů před P .
5. Aplikovat tento algoritmus na seznam polygonů za P .

Následující diagram ilustruje použití tohoto algoritmu při převodu seznamu čar nebo polygonů do stromu BSP. V každém z osmi kroků (i.-viii.) Se výše uvedený algoritmus použije na seznam řádků a do stromu se přidá jeden nový uzel.

	Začněte seznamem čar (nebo ve 3D, polygonů) tvořících scénu. Ve stromových diagramech jsou seznamy označeny zaoblenými obdélníky a uzly ve stromu BSP kruhy. V prostorovém diagramu čar je směr zvolený jako 'přední' čáry označen šipkou.
já.	Podle kroků výše uvedeného algoritmu Ze seznamu vybereme řádek A, ... ... přidat do uzlu. Zbývající řádky v seznamu rozdělíme na řádky před A (tj. B2, C2, D2) a za řádky (B1, C1, D1). Nejprve zpracujeme čáry před A (v krocích ii – v), ... ... následovaný těmi vzadu (v krocích vi – vii).
ii.	Nyní použijeme algoritmus na seznam řádků před A (obsahující B2, C2, D2). Vybereme čáru B2, přidáme ji do uzlu a zbytek seznamu rozdělíme na řádky, které jsou před B2 (D2), a ty, které jsou za ní (C2, D3).
iii.	Vyberte řádek D2 ze seznamu řádků před B2 a A. Je to jediný řádek v seznamu, takže po přidání do uzlu není třeba nic dalšího dělat.
iv.	Jsme hotovi s čarami před B2, zvažte tedy čáry za B2 (C2 a D3). Vyberte jeden z nich (C2), přidejte jej do uzlu a druhý řádek vložte do seznamu (D3) do seznamu řádků před C2.
proti.	Nyní se podívejte na seznam řádků před C2. Existuje pouze jeden řádek (D3), proto jej přidejte do uzlu a pokračujte.
vi.	Nyní jsme do stromu BSP přidali všechny řádky před A, takže nyní začínáme na seznamu řádků za A. Výběrem čáry (B1) z tohoto seznamu přidáme B1 do uzlu a rozdělíme zbývající část seznam na řádky před B1 (tj. D1) a řádky za B1 (tj. C1).
vii.	Nejprve se zpracovává seznam řádků před B1, D1 je jediným řádkem v tomto seznamu, proto jej přidejte do uzlu a pokračujte.
viii.	Když se podíváme dále na seznam řádků za B1, jediným řádkem v tomto seznamu je C1, přidejte to tedy do uzlu a strom BSP je dokončen.

Konečný počet polygonů nebo čar ve stromu je často větší (někdy mnohem větší) než původní seznam, protože čáry nebo polygony, které protínají dělící rovinu, je třeba rozdělit na dva. Je žádoucí tento nárůst minimalizovat, ale také zachovat rozumnou rovnováhu v konečném stromu. Volba polygonu nebo čáry, která se použije jako dělící rovina (v kroku 1 algoritmu), je proto důležitá při vytváření efektivního stromu BSP.

Traversal

Stromem BSP se prochází lineárním časem v pořadí určeném konkrétní funkcí stromu. Opět na příkladu vizualizace oboustranné polygony pomocí algoritmu malířův, nakreslit polygon P správně požaduje, aby všechny polygony za rovinou P spočívá ve musí být vypracován první, pak polygon P a nakonec polygony před P . Pokud je toto pořadí kreslení splněno pro všechny polygony ve scéně, pak se celá scéna vykreslí ve správném pořadí. Tuto proceduru lze implementovat rekurzivním procházením stromu BSP pomocí následujícího algoritmu. Z daného místa zobrazení V k vykreslení stromu BSP,

1. Pokud je aktuálním uzlem listový uzel, vykreslete polygony v aktuálním uzlu.
2. Jinak, pokud je místo zobrazení V před aktuálním uzlem:
   1. Vykreslete podřízený strom BSP obsahující mnohoúhelníky za aktuálním uzlem
   2. Vykreslete mnohoúhelníky v aktuálním uzlu
   3. Vykreslete podřízený strom BSP obsahující mnohoúhelníky před aktuálním uzlem
3. Jinak, pokud je místo zobrazení V za aktuálním uzlem:
   1. Vykreslete podřízený strom BSP obsahující mnohoúhelníky před aktuálním uzlem
   2. Vykreslete mnohoúhelníky v aktuálním uzlu
   3. Vykreslete podřízený strom BSP obsahující mnohoúhelníky za aktuálním uzlem
4. Jinak musí být místo zobrazení V přesně v rovině přidružené k aktuálnímu uzlu. Pak:
   1. Vykreslete podřízený strom BSP obsahující mnohoúhelníky před aktuálním uzlem
   2. Vykreslete podřízený strom BSP obsahující mnohoúhelníky za aktuálním uzlem

Rekurzivní použití tohoto algoritmu na strom BSP generovaný výše vede k následujícím výsledkům:

• Algoritmus je nejprve aplikován na kořenový uzel stromu, uzel A . V je před uzlem A , proto použijeme algoritmus nejprve na podřízený strom BSP obsahující polygony za A
  • Tento strom má kořenový uzel B1 . V je za B1, takže nejprve použijeme algoritmus na podřízený strom BSP obsahující polygony před B1 :
    • Tento strom je pouze listový uzel D1 , takže je vykreslen mnohoúhelník D1 .
  • Poté vykreslíme polygon B1 .
  • Poté použijeme algoritmus na podřízený strom BSP obsahující polygony za B1 :
    • Tento strom je pouze listový uzel C1 , takže je vykreslen mnohoúhelník C1 .
• Poté nakreslíme polygony A
• Algoritmus poté aplikujeme na podřízený strom BSP obsahující polygony před A
  • Tento strom má kořenový uzel B2 . V je za B2, takže nejprve použijeme algoritmus na podřízený strom BSP obsahující polygony před B2 :
    • Tento strom je pouze listový uzel D2 , takže je vykreslen mnohoúhelník D2 .
  • Poté vykreslíme polygon B2 .
  • Poté použijeme algoritmus na podřízený strom BSP obsahující polygony za B2 :
    • Tento strom má kořenový uzel C2 . V je před C2, takže nejprve bychom použili algoritmus na podřízený strom BSP obsahující polygony za C2 . Žádný takový strom však neexistuje, takže pokračujeme.
    • Vykreslujeme polygon C2 .
    • Algoritmus aplikujeme na podřízený strom BSP obsahující polygony před C2
      • Tento strom je pouze listový uzel D3 , takže je vykreslen mnohoúhelník D3 .

Strom je procházen v lineárním čase a vykresluje polygony v uspořádání velmi blízko ( D1 , B1 , C1 , A , D2 , B2 , C2 , D3 ) vhodné pro malířův algoritmus.

Časová osa

• 1969 Schumacker a kol. publikoval zprávu, která popisovala, jak by mohly být pečlivě umístěné roviny ve virtuálním prostředí použity k urychlení uspořádání polygonů. Tato technika využila hloubkové soudržnosti, která uvádí, že polygon na vzdálenější straně roviny nemůže žádným způsobem překážet bližšímu polygonu. To bylo použito v letových simulátorech vyrobených společností GE a Evans a Sutherland. Vytvoření polygonální organizace dat však bylo provedeno ručně scénografem.

• 1980 Fuchs a kol. rozšířil Schumackerův nápad na reprezentaci 3D objektů ve virtuálním prostředí pomocí rovin, které leží shodně s polygony, k rekurzivnímu rozdělení 3D prostoru. To poskytlo plně automatizované a algoritmické generování hierarchické polygonální datové struktury známé jako strom pro dělení binárních prostorů (BSP Tree). Proces probíhal jako krok předběžného zpracování offline, který byl proveden jednou pro každé prostředí/objekt. Za běhu bylo uspořádání viditelnosti závislé na pohledu generováno procházením stromu.
• 1981 Naylor's Ph.D. diplomová práce poskytla úplný vývoj obou stromů BSP a graficko-teoretický přístup s využitím silně propojených komponent pro viditelnost před výpočtem a také propojení mezi těmito dvěma metodami. Byly zdůrazněny stromy BSP jako dimenzionálně nezávislá struktura prostorového vyhledávání s aplikacemi pro určování viditelného povrchu. Součástí práce byla také první empirická data prokazující, že velikost stromu a počet nových polygonů byly přiměřené (pomocí modelu raketoplánu).
• 1983 Fuchs a kol. popsal implementaci mikrokódu stromového algoritmu BSP na systém vyrovnávací paměti rámců Ikonas. Toto byla první ukázka stanovení viditelného povrchu v reálném čase pomocí stromů BSP.
• 1987 Thibault a Naylor popsali, jak lze libovolný mnohostěn reprezentovat pomocí stromu BSP na rozdíl od tradičního b-rep (hraniční reprezentace). To poskytlo solidní reprezentaci vs. reprezentaci na povrchu. Operace množin na mnohostěnech byly popsány pomocí nástroje, který umožňuje konstruktivní geometrii (CSG) v reálném čase. Toto byl předchůdce návrhu úrovně BSP pomocí „ štětců “, který byl představen v editoru Quake a vyzvednut v editoru Unreal.
• 1990 Naylor, Amanatides a Thibault poskytli algoritmus pro sloučení dvou stromů BSP za vzniku nového stromu BSP ze dvou původních stromů. To poskytuje mnoho výhod, včetně kombinace pohybujících se objektů reprezentovaných stromy BSP se statickým prostředím (také reprezentovaným stromem BSP), velmi efektivních operací CSG na polyhedře, přesné detekce kolizí v O (log n * log n) a správného uspořádání transparentních povrchy obsažené ve dvou vzájemně se prostupujících objektech (bylo použito pro efekt rentgenového vidění).
• 1990 Teller a Séquin navrhli offline generování potenciálně viditelných sad za účelem urychlení určování viditelného povrchu v ortogonálních 2D prostředích.
• 1991 Gordon a Chen [CHEN91] popsali účinný způsob provádění vykreslování front-to-back ze stromu BSP, spíše než tradiční přístup back-to-front. Využili speciální datovou strukturu k efektivnímu zaznamenávání částí obrazovky, které byly nakresleny a které teprve budou vykresleny. Tento algoritmus společně s popisem stromů BSP ve standardní učebnici počítačové grafiky dne ( Computer Graphics: Principles and Practice ) použil John Carmack při tvorbě hry Doom (videohry) .
• 1992 Tellerův Ph.D. diplomová práce popsala efektivní generování potenciálně viditelných sad jako krok předzpracování k urychlení určování viditelné plochy v reálném čase v libovolných 3D polygonálních prostředích. To bylo použito v Quake a významně to přispělo k výkonu této hry.
• 1993 Naylor odpověděl na otázku, co charakterizuje dobrý strom BSP. K matematickému měření očekávaných nákladů na vyhledávání stromu použil modely očekávaných případů (spíše než analýzu nejhorších případů) a toto opatření použil ke stavbě dobrých stromů BSP. Intuitivně strom představuje objekt způsobem s více rozlišeními (přesněji jako strom aproximací). Jsou vykresleny rovnoběžky s Huffmanovými kódy a pravděpodobnostními binárními vyhledávacími stromy.
• 1993 Hayder Radha's Ph.D. práce popisuje (přirozené) metody reprezentace obrazu pomocí stromů BSP. To zahrnuje vývoj optimálního rámce konstrukce stromu BSP pro libovolný libovolný vstupní obraz. Tento rámec je založen na nové transformaci obrazu, známé jako transformace dělicí čáry LPE (Least-Square-Error (LSE)). Diplomová práce H. Radhy také vyvinula optimální kompresní rámec pro rychlostní zkreslení (RD) a přístupy pro manipulaci s obrázky pomocí stromů BSP.

Viz také

• kd strom
• Octree
• Quadtree
• Hierarchické shlukování , alternativní způsob rozdělení dat 3D modelu pro efektivní vykreslování.
• Řezání gilotinou

Reference

Další reference

externí odkazy

• Naylor, BF (2005). „Výukový program o dělících stromech binárního prostoru“ . Citační deník vyžaduje |journal=( nápověda )
• Prezentace stromů BSP
• Další prezentace stromů BSP
• Java applet, který ukazuje proces generování stromu
• Diplomová práce o generování BSP
• Stromy BSP: Teorie a implementace
• BSP ve 3D prostoru