Binární oddíl prostoru

Rozdělení binárního prostoru ( rozdělení binárního prostoru nebo BSP ) je systém používaný k rozdělení prostoru na konvexní oblasti . Tyto buňky jsou ohraničeny hyperplany  ; v případě dvourozměrného (rovinného) prostoru jsou separace rovné čáry a buňky jsou čtyřúhelníky (často obdélníky ); v případě trojrozměrného prostoru jsou separacemi roviny a buňky polyhedry (často obdélníkové rovnoběžnostěny ).

Buňky jsou uspořádány v binárním stromu, který se nazývá strom BSP . Tato datová struktura usnadňuje určité operace. Je obzvláště zajímavý pro 3D vykreslování, a proto se používá ke správě grafiky určitých videoher .

Historický

• 1969 Schumacker a kol. publikovat zprávu popisující, jak pečlivě umístěné roviny ve virtuálním prostředí mohou zrychlit řazení polygonů . Tato technika využívá hloubku koherence, představu, že mnohoúhelník umístěný v polorovině nejdále od diváka nemůže maskovat mnohoúhelník umístěný v nejbližší polorovině. Tuto představu používají letové simulátory vyvinuté společnostmi General Electric a Evans & Sutherland . Vytvoření polygonové hierarchie se však provádí ručně pomocí návrháře scén.

• 1975 Bentley ze Stanfordské univerzity navrhuje strukturu stromů k -d pro vícerozměrný výzkum.

• 1980 Fuchs a kol. rozšířit myšlenku na reprezentaci virtuálních 3D objektů pomocí rovin polygonů a rekurzivně rozdělit prostor. Vytvářejí tak plně automatizovaný algoritmus pro vytváření hierarchické datové struktury pro polygony, nazývaný Binary Space Partitioning Tree (BSP Tree) . Tento proces probíhá v předvýpočtovém kroku před dodáním koncovému uživateli. Při běhu v reálném čase se řazení polygonů k určení viditelnosti provádí procházením stromu.

• 1981 Naylorova disertační práce kombinuje BSP stromy a teorii grafů k určení předpočítané viditelnosti. Zdůrazňuje použití stromů BSP jako struktury výzkumu nezávislé na prostorové dimenzi s aplikacemi na viditelnost povrchů. Práce pomocí modelu raketoplánu empiricky demonstruje, že velikost stromu a počet vytvořených nových polygonů je rozumná.

• 1983 Fuchs a kol. popsat minimální kód stromu BSP na systému vyrovnávacích pamětí rámců Ikonas. Toto je první implementace určování viditelnosti povrchu v reálném čase pomocí stromů BSP.

• 1987 Thibault a Naylor popisují, jak reprezentovat mnohostěny pomocí BSP stromů, na rozdíl od obvyklé metody B-Rep (hraniční reprezentace) . Máme zobrazení tělesa na rozdíl od zobrazení povrchů (hranice těles). Nástroje nabízené pro mnohostěn umožňují vykreslení těles popsaných pomocí konstruktivní geometrie těles (CSG) v reálném čase. Je předchůdcem metody návrhu úrovně BSP pomocí štětců , která byla zavedena v editoru Quake a znovu použita v editoru Unreal .

• 1990 Naylor, Amanatides a Thibault poskytují algoritmus sloučení dvou stromů BSP do jednoho. To umožňuje zejména: kombinovat pohybující se objekty, představované stromy BSP, se statickým prostředím také představovaným stromem BSP; rychlé provádění booleovských operací mezi mnohostěnmi (CSG); výpočty přesné srážky v O (log n × log n )  ; a správně objednat průhledné povrchy obsažené v prostupujících objektech (používané pro efekt rentgenového vidění).

• 1990 Teller a Séquin navrhují určit potenciálně viditelné prvky před dodáním softwaru, aby se urychlilo určování viditelných povrchů ve 2D ortogonálních prostředích.

• 1991 Gordon a Chen popisují efektivní metodu vykreslování front-to-back ze stromu BSP namísto obvyklého přístupu back-to-front. Používají vyhrazenou datovou strukturu, aby mocným způsobem zaznamenali části obrazovky, které již byly nakresleny a ty, které ještě nebyly nakresleny. Tento algoritmus použil John Carmack k vytvoření videohry Doom .

• 1992 Tellerova disertační práce popisuje efektivní metodu pro stanovení potenciálně viditelných množin v kroku předzpracování, která umožňuje urychlit stanovení viditelných povrchů v reálném čase v 3D prostředí tvořeném polygony. Tato metoda byla použita v Quake a významně přispěla k výkonu hry.

• 1993 Naylor určuje, co charakterizuje „dobrý“ strom BPS. Matematicky měří náklady na hledání stromu a aplikuje je na stavbu „dobrých“ stromů na základě pravděpodobných případů, nikoli analýzy nejhorších případů. Správné stromy intuitivně představují objekty na různých úrovních rozlišení (strom aproximací). Tato metoda má podobnosti s Huffmanovým kódováním a náhodnými permutačními vyhledávacími stromy .

• 1993 Doktorská práce Haydera Radhy popisuje metodu (přirozené) reprezentace obrazu pomocí BSP stromů. To zahrnuje vývoj optimální konstrukční struktury stromu BSP pro libovolný obrázek. Tato struktura je založena na nové transformaci obrazu, transformaci dělící řádky získanou regresí nejmenších čtverců ( transformace dělící čáry nejmenších čtverců - chyba) . Radhova práce také vyvíjí strukturu komprese obrazu s optimální rychlostí zkreslení a přístup k manipulaci s obrázky pomocí stromů BSP.

Definice

Popis

Z geometrického hlediska jsou stromy BSP obecnou verzí platanů pro dělení prostoru. Mezi K -d stromy jsou speciální případy BSP stromy, v němž jsou letadla vyrovnané s osami a jejichž uzly obsahovat pouze jeden bod. BSP stromy jsou obecnější struktury, ve kterých mohou mít roviny jakoukoli orientaci - jsou to obecně roviny generované z polygonů - a jejichž uzly mohou obsahovat jakýkoli typ geometrického objektu - obecně „primitivní“ tvary (jednoduché geometrické tvary: polygony, kostky, koule , válce atd.).

První uzel stromu je prostor, obsahuje rovinu, která rozděluje prostor na dvě části. Jeho dva podřízené uzly jsou poloprostory, samy obsahují roviny, které rozdělují tyto podprostory na dva. Koncové uzly stromu již neobsahují žádné roviny a nazývají se „listy“.

„Úroveň podrobnosti“ - kde se zastavíme při konstrukci stromu, co uzly obsahují - závisí na oblasti použití. Například :

• u syntetických obrázků s 3D vykreslením obsahují uzly sadu polygonů, které lze nakreslit v libovolném pořadí,
  • pokud existují utracení na zadní straně , uzel obsahuje sadu konvexních polygonů,
  • pokud lze vidět obě strany polygonů (v závislosti na úhlu pohledu), uzel obsahuje pouze koplanární polygony;
• při výpočtu kolize nebo trasování paprsku obsahuje uzel část prostoru, ve kterém jsou přímé testy zachycení.

Konstrukce

Konstrukce stromu BSP se může spolehnout na velmi odlišné techniky.

Je to velmi jednoduché, když ho chcete použít pouze jako strukturu úložiště polygonů. Fyzikální motory často používají základní BSP k ukládání statické geometrie (obvykle k -d stromy ), jejich konstrukce se provádí velmi rychle.

Stroje pro videohry používají mnohem složitější stavební systémy, protože BSP se musí shodovat se strukturou typu sektoru / portálu, aby bylo možné provádět výpočty okluze. Aby byla zajištěna co nejčistší struktura, stromy se obvykle nevytvářejí z polygonální sítě, ale pomocí blokování konvexních pevných látek, jak to dělají id Tech a Unreal Engine . Id Tech pouze přidat konvexní tělesa je Unreal Engine zavádí booleovské výkop dále optimalizovat geometrii stromů.

Jakmile je strom BSP postaven, je převeden na strukturu sektoru / portálu, strukturu, na které bude spočívat okluze. Ve stroji id Tech jsou portály generovány automaticky ořezovým algoritmem , potom je okluze předpočítána v bitové masce zvané potenciálně viditelné sady . V Unreal Engine , od verze 2, je to obrácený proces: portály jsou vytvářeny ručně návrhářem a jsou přidány do geometrie stromu BSP. Okluze se vypočítává v reálném čase díky portálům.

Vzhledem k tomu, že tento proces vytváření map BSP je velmi dlouhý a jeho vývoj je nákladný, studia tvorby videoher obecně upřednostňují použití standardů id Tech nebo Unreal .

Příklad konstrukce

Zvažte 3D vykreslení v případě, že je pravděpodobné, že budou vidět obě strany mnohoúhelníků. Můžeme použít následující algoritmus rekurzivní konstrukce:

1. Vyberte mnohoúhelník P ze seznamu.
2. Vytvořte uzel N ve stromu BSP a vložte P do seznamu polygonů tohoto uzlu.
3. Pro každý mnohoúhelník v seznamu:
   1. Pokud je tento mnohoúhelník zcela před rovinou obsahující P, umístěte tento mnohoúhelník do seznamu mnohoúhelníků před P.
   2. Pokud je tento polygon zcela za rovinou obsahující P, umístěte tento polygon do seznamu polygonů za P.
   3. Pokud je rovina obsahující P oddělena polygonem, rozdělte mnohoúhelník na dvě roviny P a umístěte každý z polovičních polygonů do příslušného seznamu (před P, za P).
   4. Pokud je mnohoúhelník koplanární s P, přidejte jej do seznamu mnohoúhelníků pro uzel N.
4. Aplikujte tento algoritmus na seznam polygonů před P.
5. Použijte tento algoritmus na seznam polygonů za P.

Můžeme tedy uspořádat polygony od nejvzdálenějšího po nejbližší k úhlu pohledu, a proto víme, v jakém pořadí nakreslit polygony, aby se zohlednily maskovací efekty.

Konkrétněji si vezměme příklad roviny (dvourozměrného prostoru), ve které jsou geometrickými objekty úsečky . Každý segment má orientaci, takže má „přední stranu“ a „zadní stranu“, které jsou definovány při vytváření segmentu.

	Mezera obsahuje čtyři úsečky {A, B, C, D}; kdyby to byl problém s 3D vykreslováním, byly by to polygony tvořící „scénu“. Ve stromu jsou uzly stromu v kruzích a seznamy objektů před nebo za jsou v zaoblených obdélnících. Přední strana každého segmentu je označena šipkou
i.	Aplikujeme výše uvedený algoritmus: Svévolně si vybereme segment, zde A. Vytvoříme kořenový uzel obsahující A. Protínající se segmenty s linií nesoucí A jsou vyříznuty; takže máme nové segmenty, {B1, B2, C1, C2, D1, D2}. Některé jsou umístěny před A, {B2, C2, D2} a další jsou umístěny za, {B1, C1, D1}. Zpracováváme rekurzivně nejprve segmenty umístěné před A (stupně ii - v), poté segmenty umístěné za (stupně vi - vii).
ii.	Zvažujeme segmenty umístěné před A, {B2, C2, D2}. Vytvoříme podřízený uzel, vybereme libovolný segment B2 a přidáme jej do tohoto uzlu. Sekáme segment se spojnicí B2, která vytváří dva nové segmenty, {D2, D3}. Oddělujeme segmenty umístěné před B2, {D2} a segmenty umístěné za, {C2, D3}.
iii.	Zvažujeme segmenty umístěné před B2. Existuje pouze jeden segment, D2, takže vytvoříme podřízený uzel B2, který jej obsahuje, je to list stromu.
iv.	Nyní uvažujeme segmenty za B2, {C2, D3}. Svévolně vybereme segment C2 a přidáme jej do podřízeného uzlu B2, který vytvoříme. Seznam segmentů před C2 je {D3}, seznam segmentů za nimi je prázdný.
proti.	Zvažujeme seznam segmentů před C2. Jediný segment, který obsahuje, D3, je přidán do podřízeného uzlu C2, který vytvoříme.
vi.	Zpracovali jsme všechny segmenty umístěné před A; nyní jednáme s těmi, kdo jsou za tím. Vybereme libovolný segment, B1, který vložíme do podřízeného uzlu A, který vytvoříme. Rozdělíme segmenty na dva seznamy: segmenty umístěné před B1, {D1} a segmenty umístěné za {C1}.
vii.	Zpracováváme segmenty umístěné před B1. Existuje pouze jeden segment, D1, takže vytvoříme podřízený uzel B1, který jej tam umístí.
viii.	Zpracováváme segmenty za B1. Existuje pouze jeden segment, C1, takže vytvoříme podřízený uzel B1, který jej tam umístí. Strom BSP je dokončen.

BSP díry a HOM

BSP díra nebo BSP díra je běžný problém, se kterým se můžete setkat při prohlížení grafu uloženého jako strom BSP. To se projevuje dírou v reprezentovaném objektu, která může být černá, nebo nechat ukázat, co je za ní; v tomto případě mluvíme o „ledovém paláci“ neboli HOM (pro zrcadlový sál ), ale můžeme mít HOM, aniž bychom měli díru BSP.

Některé díry BSP jsou náhodné: objevují se pouze z určitých úhlů pohledu. Jiné jsou trvalé: objekt chybí z jakéhokoli úhlu pohledu; obvykle se jedná o chybu úprav. Může také nastat účinek srážky s neviditelnou překážkou (ICH, neviditelný kolizní trup ): motor detekuje kolizi a brání hráči v pohybu vpřed, ale nezobrazí se žádný předmět.

Díra BSP se obvykle vyskytuje, když je geometrie příliš podrobná. Jeho řezání může vést k příliš malému měřítku, které generuje chyby související s aproximací čísel ( chyba zaokrouhlování ). Aby se těmto problémům předešlo, programy kodéru BSP zničí geometrii tam, kde je měřítko příliš malé, což způsobí díry ve stromu.

Aby se těmto otvorům zabránilo, musí být geometrie zjednodušena. Proto musí být podrobné části mapy vytvořeny s prvky, které nejsou součástí BSP: quadpatch , trimesh , modely a entity pro id Tech engine , terény a statické sítě pro Unreal Engine .

HOM nastane, když grafický modul nemá nic k zobrazení (což neznamená, že je v něm otvor BSP); Abychom ušetřili zdroje, motor pouze přetáhne starý obrázek a nevymaže ho, takže vidíme obrazové prvky zobrazené nad sebou, jako když jsou proti sobě dvě zrcadla, odtud název „ledový palác“. HOM se často vyskytuje u  stříleček z pohledu první osoby - hledisko hráče má být v omezené oblasti. Tento předpoklad však může být porušen, pokud hráč použije režim „virtuální kamery“ (režim noclip ); zobrazená část stromu BSP je pak neúplná a obsahuje otvory BSP, které odhalují prvky starého obrázku.

Cesta

Cesta stromu BSP je lineární v čase , O ( n ). Algoritmus trasy závisí na sledovaném cíli.

Vyhledání bodu je nejjednodušší operace a provádí se v malé smyčce bez nutnosti rekurzivní funkce. Vyzkoušíme, na které straně kořenové roviny je bod, potom začneme znovu na odpovídajícím dítěti a smyčkujeme, dokud nespadneme do listu, který obsahuje bod.

V případě stromu představujícího polygony, které se mají zobrazit, lze pomocí cesty stromu určit pořadí, ve kterém musí být polygony zobrazeny ( malířský algoritmus ). K tomu se používá následující algoritmus rekurzivního zobrazení:

1. Pokud je aktuálním uzlem list, zobrazte polygony obsažené v aktuálním uzlu.
2. Jinak, pokud je úhel pohledu V před aktuálním uzlem:
   1. Zobrazit podřízenou větev obsahující polygony umístěné za aktuálním uzlem.
   2. Zobrazit polygony obsažené v aktuálním uzlu.
   3. Zobrazit podřízenou větev obsahující polygony umístěné před aktuálním uzlem.
3. Jinak, pokud je úhel pohledu V za aktuálním uzlem:
   1. Zobrazit podřízenou větev obsahující polygony umístěné před aktuálním uzlem.
   2. Zobrazit polygony obsažené v aktuálním uzlu.
   3. Zobrazit podřízenou větev obsahující polygony umístěné za aktuálním uzlem.
4. Jinak je úhel pohledu V přesně v rovině spojené s aktuálním uzlem. Tak :
   1. Zobrazit podřízenou větev obsahující polygony umístěné před aktuálním uzlem.
   2. Zobrazit podřízenou větev obsahující polygony umístěné za aktuálním uzlem.

Použijme tento algoritmus na předchozí příklad:

• Začneme u kořene, uzel A. V je před uzlem (přední strana je označena šipkou), takže algoritmus použijeme rekurzivně na uzly umístěné za sebou, tj. Větev B1.
  • Aktuální uzel je B1. V je za B1, takže algoritmus aplikujeme rekurzivně na uzly umístěné vpředu, tj. Větev D1.
    • Aktuální uzel je D1. Je to list, takže zobrazujeme D1 .
  • Poté zobrazíme B1 .
  • Poté algoritmus rekurzivně aplikujeme na uzly umístěné za B1, tj. Větev C1.
    • Aktuální uzel je C1. Je to list, takže zobrazujeme C1 .
• Pak zobrazí .
• Poté algoritmus rekurzivně aplikujeme na uzly umístěné před A, tj. Větev B2.
  • Aktuální uzel je B2. V je za B2, takže algoritmus aplikujeme rekurzivně na uzly umístěné vpředu, tj. Větev D2.
    • Aktuální uzel je D2. Je to list, takže zobrazujeme D2 .
  • Poté zobrazíme B2 .
  • Poté algoritmus rekurzivně aplikujeme na uzly umístěné za B2, tj. Větev C2.
    • Aktuální uzel je C2. V je před C2, takže algoritmus rekurzivně aplikujeme na uzly za ním.
      • Neexistuje žádný uzel.
    • Poté zobrazíme C2 .
    • Poté je algoritmus rekurzivně aplikován na uzly umístěné před C2, tj. Větev D3.
      • Aktuální uzel je D3. Je to list, takže zobrazujeme D3 .

Uzel se prochází lineárně v čase a polygony se zobrazují v pořadí od nejvzdálenějšího k nejbližšímu (D1, B1, C1, A, D2, B2, C2, D3), jak to vyžaduje malířův algoritmus.

Použití ve videohrách

Ve videohrách jsou určité předměty nebo předměty pohyblivé. Konstrukce stromu BSP proto musí být provedena pokaždé, když je obraz obnoven. Je to předpočítávací krok.

Vzhledem ke složitosti vytváření stromů BSP vhodných pro herní enginy mnoho společností nevyvíjí vlastní formát map, ale používá stávající enginy, zejména standardy Unreal a id Tech ( Quake ) . Například motor Half-Life je založen na motoru Quake 1 . Současným standardem je Unreal Engine . Id Tech , kolem komunity open source , se stala standardní formát používaný BSP vývojů amatér nebo nezávislé.

Různá pozorování níže jsou proto v zásadě založena na studiu těchto dvou standardních formátů.

Okluze / kolize / stínové projekce

Toto jsou hlavní funkce stromů BSP: optimalizovat výpočty kolizí, okluzí a stínů.

Motor Doom vypočítal okluzi v reálném čase přímo v rutině zobrazení oříznutím objednaných obličejů pomocí BSP. Zemětřesení motoru a jeho deriváty precompute okluze v seznamech skupin listů, které mohou být viděny navzájem ( potenciálně viditelné sadě ) . U modernějších motorů je okluze založena na branách a bránách, BSP ztrácí svou okluzivní funkci, ale stále slouží jako skladovací struktura pro vnitřní prostředí .

U starších motorů byly výpočty kolizí založeny přímo na kartáčích (konvexních pevných látkách) použitých ke konstrukci hřídele. V Doomově motoru byly tyto kartáče postaveny samotným stromem. V novějších motorech jsou srážky založeny na fyzickém motoru, jehož kolizní mapa může být zcela nezávislá na struktuře stromu.

Vrhané stíny byly představeny v Unreal Engine nebo Doom 3 . Doom 3 používá algoritmus velmi podobný algoritmu použitému k vykreslení tváří, zcela založeném na BSP (viz Carmack's Reverse ).

Matematická evoluce v klasických videohrách

BSP se používá téměř ve všech 3D hrách od Doom , Unreal , Quake a Half-Life .

Doomův motor stavěl BSP z polygonálních sektorů. Motor Quake / Half-Life staví BSP z konvexních pevných látek. Systém modelování stromů BSP používaný Unreal Engine zvaný konstruktivní objemová geometrie zavádí pojem booleovského výkopu  : používají se „obrácené“ pevné látky, které zefektivňují konstrukci BSP, tento systém má tu výhodu, že snižuje riziko HOM nebo Otvor BSP (viz výše ), konstrukční chyby společné pro všechny motory.

Vizuální evoluce

Nejprve použitý ve dvou rozměrech pro všechny úrovně pod Doomem , BSP 2d původně neumožňoval vytvářet překrývající se kusy na ose Z (výšková osa). Jednalo se však o inherentní omezení motoru, Doom Engine , který, nyní revoluční, se nyní jeví jako extrémně omezený.

Je to s jeho variací ve 3D v motoru Quake a jeho nástupců Quake II nebo Quake III a jeho konkurentů Unreal , nebo o něco později Half-Life, které BSP dosáhne svého maximálního využití, jsou dekorace obohacené díky znásobení výkon motorů, ale také rychlost zpracování a výpočetní výkon mikroprocesorů a stále silnější vzhled grafických karet . BSP poté představoval největší část celkové architektury úrovní ve 3D. To bylo v této době, kdy se začali objevovat herci dekorací, kteří nebyli tvořeni BSP, ale jen málo z nich a namáhavé stvoření. Prefabrikované systémy umožňují vytvářet složité struktury, ukládat je nezávisle na aktuální úrovni a později je nekonečně opakovaně používat. Tyto „prefabriky“ jsou poté upřednostňovány před aktéry dekorací, ale jsou vyrobeny z BSP a mají všechny nevýhody.

Kombinace BSP s podrobnými strukturami zobrazení

Nevýhodou BSP je, že je vhodná pro architekturu s nízkým počtem polygonů (nízký polygon) , pro podrobnosti je nutné přidat prvky jiné než BSP.

V nedávných hrách (přibližně od roku 2000) má BSP tendenci být spojen s architektonickými detaily a složitými dekoracemi s lépe optimalizovanými systémy.

Nejvýraznějším příkladem je nepochybně statická síť  (en) a terény Unreal Engine , které se objevily s druhou verzí enginu v roce 2002, ve hře Unreal II . Tyto objekty jsou vývojem hráčů dekorace jiných než BSP, kteří mají tendenci obsazovat většinu funkcí dříve přiřazených BSP: mobilní objekty, architektonické detaily a stále více a velké obecné tvary místností.

Id Tech 3 zaveden quadpatch (křivky) a oka jakékoliv. Systémy zavřít na Unreal své terény / staticmesh však méně optimalizována.

Důvody této náhrady jsou jednoduché: statické sítě (a jejich ekvivalenty v jiných motorech) nejsou citlivé na všechny problémy spojené s BSP: HOM, „solid phantoms“ (v rámci Half-Life ) atd. Zlepšují také rychlost úrovní načítání: lze vytvořit instanci statické sítě . To znamená, že motoru stačí načíst objekt pouze jednou a poté jej duplikovat tolikrát, kolikrát je potřeba, s příslušnými změnami, které se na něj použijí.

Na druhou stranu to nezlepšuje rychlost zobrazení: každý takto „klonovaný“ objekt musí být stále zobrazen samostatně. Snížení počtu přístupů na pevné disky však může u některých her stále zlepšit výkon.

Vnější úrovně

Vnější úrovně používají velmi málo BSP a upřednostňují přizpůsobenější struktury, jako jsou výšky a osmičky .

Jelikož terénní systémy BSP vyžadují velké množství silně deformovaných BSP, které způsobují stále více problémů a chyb , byly současně se statickými sítěmi zavedeny generátory terénu , aby se vytvořily velké části s velmi vysokou geometrií optimalizované pro tyto typy vykreslení. Kombinované použití statických sítí a stále výkonnějších generátorů terénu vede k vytvoření úrovní, které někdy obsahují posměšný počet objektů BSP: v Unreal Tournament 2004 vám tyto systémy umožňují vytvářet úrovně obsahující dvě velké prázdné kostky, z nichž jedna obsahuje terén a statické sítě a druhým je Skybox . Hry jako Unreal a Half-Life používaly terén BSP, který byl velmi hranatý a obtížně optimalizovatelný.

Povrchové osvětlení

Osvětlení povrchů BSP prošlo třemi hlavními fázemi. Prvním bylo jednoduché statické osvětlení používané v Doom a Doom II: Hell on Earth  : několik definovaných úrovní osvětlení umožňuje, aby byla úroveň osvětlena téměř rovnoměrně.

Hry nové generace umožňovaly velmi živé atmosféry díky dynamickému a kontrastnímu osvětlení, jako jsou určité úrovně Unreal , Unreal Tournament , Half-Life . V Quake 3 si můžete vybrat mezi tímto dynamickým osvětlovacím systémem nebo systémem Lightmap  : barevné textury aplikované průhledností na geometrii úrovně pro simulaci rozdílů ve světle. Tento proces zakazuje jakékoli dynamické světlo, ale umožňuje velmi přesné a výrazné stíny. Pod UT2003 a jeho přímým nástupcem UT2004 tvoří Lightmaps téměř veškeré osvětlení BSP. Některé dynamické osvětlovací systémy přetrvávají, ale jsou velmi nákladné z hlediska zdrojů, což nutí motor každou chvíli aktualizovat Lightmaps. Světla také nemohou vrhat stíny tak realistické a detailní jako statická světla.

Novější hry jako Doom 3 jsou vysoce optimalizované a jejich osvětlovací systémy, podrobné i dynamické, vám umožňují vrhat velmi dobře spravované stíny na BSP, ale také na herce dekorace.

Další aplikace

Obecně se stromové struktury používají pro mnoho algoritmů. Například můžeme použít binární oddíl k nalezení nejbližších sousedů bodu nebo hledání podle rozsahu  : konstrukce stromu je náročná na zdroje, ale jeho cesta je mnohem rychlejší než systematické tažení všech bodů. K -d strom je zajímavé v tomto ohledu, protože příčky algoritmy, aby bylo možné postavit zhruba vyrovnaná stromy s několika prázdných buněk a velkorozměrových / malého rozměru mobilního příznivé pro výzkum.

Upuštění od BSP v moderních grafických kanálech

BSP se dlouho používalo ve videoherních enginech, jako jsou staré verze Quake nebo Unreal, protože mělo dvě výhody: třídit tváře v době, kdy 3d nebyl vykreslen GPU, a automaticky generovat Velmi jemný graf buněk a portálů, který umožňoval vypočítat okluzi k nejbližšímu polygonu.

Struktura BSP však měla nevýhodu generování mnoha chyb: „díry“, „úniky“, „zkreslení“, „ploché listy“ a špatně optimalizované stromy kvůli mnoha téměř zmateným plánům.

V moderních 3D motorech se okluze provádí objekt za objektem („chunk“ nebo „batch“), proto se používají hrubší buňky, které lze modelovat ručně (cry engine), nebo dokonce automaticky generované kostky (neskutečné 4, knihovna umbra používaná jednota a id tech 6). Poté použijeme úložné struktury odvozené od bsp (osminové a kd-stromy, založené na ortogonálních rovinách, tedy ne přibližných normálech), které mají tu výhodu, že jsou stabilní a během jejich konstrukce neprodukují chyby.

Na druhé straně BSP zůstává používán jako nástroj pro modelování k urychlení „konstruktivní geometrie těles“, konstrukce složitých těles z jednoduchých těles.

Poznámky a odkazy

1. (in) Robert A. Schumacker , Brigitta Brand , Maurice G. Gilliland a Werner H. Sharp , Study for Applying Computer-Generated Images to Visual Simulation , US Air Force Human Resources Laboratory,1969, 142  s..
2. (in) Jon Louis Bentley , „  Multidimenzionální binární vyhledávací stromy používané pro asociativní vyhledávání  “ , Communications of the ACM , vol.  18, n o  9,1975, str.  509-517 ( DOI  10.1145 / 361002.361007 ).
3. (en) Henry Fuchs , Zvi M. Kedem a Bruce F Naylor , „  On Visible Surface Generation by A Priori Tree Structures  “ , SIGGRAPH '80 Proceedings of the 7th každoroční konference o počítačové grafice a interaktivních technikách , New York, ACM,1980, str.  124–133 ( DOI  10.1145 / 965105.807481 ).
4. (in) William C. Thibault a Bruce F. Naylor , „  Operace množin jsou mnohostěny pomocí stromů dělících binární prostor  “ , SIGGRAPH '87 Sborník ze 14. výroční konference Počítačová grafika a interaktivní technologie , New York, ACM,1987, str.  153–162 ( DOI  10.1145 / 37402.37421 ).
5. (in) S. Chen a D. Gordon , „  Front-to-Back Display of BSP Trees  “ , IEEE Computer Graphics & Algorithms ,Září 1991, str.  79–85 ( číst online [PDF] ).
6. viz například použití stromu k -d pro tento účel: (en) „  Re: Pairwise distance of a obrovské množství bodů  “ , on users Scilab - Mailing Lists Archives , 29. srpna 2014, 16:38
7. zejména s metodou dělení posuvných středových bodů

Související články

• Painterův algoritmus
• Octree
• Čtyřstrom
• Mapový soubor zkompilovaný pro editor Valve Hammer ( Half-Life , Counter-Strike …) nebo Doom and Quake .