+---------+ +---------+ +----------+ ++ +---+ ++ | +----+ | ++ +---+ | | | | | | | +-+ | | | | | +---+ | | +------+ | +---+ | | +---+ | +------+ | | +------+ s d d ds | | | | +-+ | | | | ,... ,... ,,, ++ +---+ ++ | +----+ | ++ ++ P' "''' "''' '''' +---------+ +---------+ +----+ '' '. ' ' '' --------------------------------------------------------------------- BSP Stromy Při psaní 3d enginu se naskytne následující problém: V jakém pořadí mám vykreslovat polygony ? První 3d enginy používali Wireframe grafiku (čárový model) a proto pro ně nebylo důležité, v jakém pořadí se polygony budou vykreslovat. S nástupem stínování a texturování se ale tento problém objevil, a musel se řešit. První nápad byl jednoduše setřídit polygony podle jejich vzdálenosti od kamery. Bližší polygony jednoduše překrylyty vzdálenější (Painter's algorithm). Tento algoritmus fungoval dobře, ovšem měl spoustu nevýhod. Vzhledem k tomu, že se většinou třídilo podle středu polygonů, stávalo se, že malé polygony před většimi měli svůj střed vzdálenější, a tak docházelo k "problikávání" polygonů. (To je vidět na řadě starších dem, ovšem překvapilo mně to třeba u takového M0DE/BOMB ;)) Nehledě nato, že algoritmus selhával na polygonech jako třeba: +---+ +---+ | | | | +----+ +----+---+----+ | | | | +----+ +----+---+----+ | | | | +----+---+----+ +----+ | | | | +----+---+----+ +----+ | | | | +---+ +---+ Potom přišel na řadu Z-buffer. To jsou 2 kusy paměti, stejné velikosti jako obrazovka. Zapisuje se do něj Z pozice vykreslovaných bodů a pokud daný bod leží blíž než bod v bufferu na stejné pozici nakreslí se do druhého bufferu, pokud dál, nekreslí se. Nakonec se druhý buffer zkopíruje do VideoRAM. Velikou výhodou tohoto systému je téměř perfektní prolínání objektů s jakýmkoliv mapováním. Jeho použití je perfektně ukázáno v demu Crystal Dreams II od Tritonu. Tento systém má ovšem 2 nevýhody a to 1) potřebuje hodně paměti a 2) je pomalý díky častým přístupům do paměti. (Obě tyto nevýhody sice odstranili 3d akcelerátory, ovšem co si budeme povídat, pokud to takhle půjde dál, tak za chvíli nebude potřeba programovat vůbec, prostě si grafik koupí kartu 8dfx, pošle do ní textury, objekty a je tu demo ;) Poslední variantou Z-bufferu jsou takzvané S-buffery tedy segmentované z-buffery. Tyto buffery dosahují dost dobrých výsledků, ovšem mají poměrně složitou implementaci. Jejich popis přenechám ale raději někomu jinému, a vrhnu se na ty BSP stromy ;) Tak předně: Je lepší S-buffer nebo BSP ? Popsané algoritmy se zaměřili na proces vykreslování. To je sice hezké, ovšem ať je vykreslovací algoritmus seberychlejší, stejně musí počítat všechno co se mu zadá, i když to stejně nevykreslí. Otázka je tedy, proč počítat a nebo dokonce kreslit polygony které nejsou z daného místa v prostoru vůbec vidět. Na to se soustřeďují BSP stromy, resp. algoritmy na nich založené. Cílem BSP je tedy eliminace polygonů které se budou počítat a předávat ke kreslení, zatímco cílem S-bufferu je eliminovat vykreslování. Z toho vyplývá že BSP a S-buffer si nekonkurují, ale mohli by spolu spolupracovat. To se taky používá i v praxi (QUAKE). OK, o co teda vlastně go ? Jde o strom, neboli seznam polygonů, a jejich relativní polohy v prostoru. Jak už název napovídá nejde o strom normální, alébrž binární. To se projevuje tím, že začíná od root node (kořene) a rozvětvuje se, přičemž každá node (větev) včetně root (:)) má dvě subnody ("podvětve"). V každé takové nodě je uložen polygon který rozděluje prostor, a pár dalších informací. Tím se dostávám k onomu SP v názvu. Takže: Jak se takový strom vytváří Rozdělení prostoru probíhá následovně: Mám seznam polygonů v prostoru. Z něj si vyberu polygon, který nám rozdělí prostor na dvě části, dva poloprostory. V nodě (jelikož je první tak vlastně v rootu) si vytvořím dvě subnody. Potom vytvořím dva seznamy polygonů. V prvním budou polygony, které leží v jedné části prostoru (podle normály root polygonu (polygon který rozdělí prostor, neplést s root node, což je hlavní noda BSP stromu) buď před nebo za root polygonem), v druhém ty, ktereé leží v druhé části prostoru. Tyto seznamy předám subnodám, a celý proces opakuju (root poly si zvolím vždy z vytvořeného seznamu, ne z toho původního). Příklad ? Mno, představte si scénu , (pro názornost uvažuju 2D scénu). Je na ní vidět osm očíslovaných polygonů (pohled seshora). Nejdřív si zvolím root polygon, podle kterého se bude prostor rozdělovat. Např. polygon 4, ten rozdělí scénu na dvě skupiny polygonů, všechny ležící před polygonem 4 (5,6,7,8) a všechny za (1,2,3). A dál postupuju stejně, v každé polorovině si zvolíme root polygon, a opět vzniknou dvě skupiny atd atd., až vznikne krásný <g> strom . Jak zjistit na které straně polygonu leží polygon :) ? Jednoduše ;). Spočítám si normálu jednoho polygonu a jednoho bodu z polygonu druhého a provedu tzv. Dot Product neboli skalární součin vektorů který vydělím součinem délek obou vektorů, z čehož dostanu číslo vv: Dot(v1,v2) vv= ----------------------- Lenght(v1)*Lenght(v2) Z tohoto čísla se dá jistou goniometrickou funkcí vypočítat úhel, který tyto dva vektory svírají, ovšem mě stačí vědět, že pokud je výsledné číslo kladné, leží bod před polygonem, pokud záporné, leží za a pokud je 0, leží v rovině polygonu. Stejným způsobem otestuju všechny body daného polygonu. Pokud leží všechny body na jedné nebo druhé straně, je vše jasné, pokud několik bodů leží v úrovni polygonu a ostatní na jedné straně, polygon leží na té které straně. Pokud leží body vpředu a vzadu, polygon musí být rozdělen (viz. dále). Pozn.: Je dobré při klasifikování jednotlivých bodů neuvažovat pro detekci bodu ležícího v rovině root polygonu číslo 0 (if (vv==0) return ONPLANE;) ale nějaký toleranční rozsah, např. polovinu imaginární "tloušťky" polygonu, takže kód bude: if vv>Econst return FRONT else if vv<Econst return BACK else return ONPLANE Jak rozdělit polygon ? Takový polygon který leží zároveň v obou polovinách děleného prostoru v BSP stromu nemůže existovat, proto je potřeba ho rozdělit na dvě části resp. na dva samostatné polygony, a to na místě kudy prochází rovina tvořená root polygonem. Z čehož vypúlývá, že musím vzít všechny úsečky polygonu, které existují v obou částech prostoru, a spočítat souřadnice bodů, ve kterých jimi prochází rovina. Což se spočítá rovnicí roviny (nebo jak se to jmenuje ;)). A to následovně: Nejdříve si vyjádřím onu rovinu pomocí normály polygonu: PLANE.A = norm.X PLANE.B = norm.Y PLANE.C = norm.Z PLANE.D = -P.X*norm.X - P.Y*norm.Y - P.Z * norm.Z norm je normalizovaný normálový vektor root polygonu (normalizovaný znamená že jeho délka je 1), P je bod ležící na rovině tvořené root polygonem (např střed root polygonu) Teď si spočítám proměnné eP1 a eP2 což jsou vlastně poměry vzdálenosti bodů P1 a P2 (koncové body strany polygonu, kterou prochází root poly): eP1 = PLANE.A * P1.X + PLANE.B * P1.Y + PLANE.C * P1.Z + PLANE.D eP2 = PLANE.A * P2.X + PLANE.B * P2.Y + PLANE.C * P2.Z + PLANE.D z nich jednoduše spočítám vzdálenost průchodu od prvního bodu: t = -eP1/(eP1 - eP2) no a pak už chybí jen koordináty vzniklého bodu I : I.X = P1.X + t*(P2.X - P1.X) I.Y = P1.Y + t*(P2.Y - P1.Y) I.Z = P1.Z + t*(P2.Z - P1.Z) takže z úsečky P1-P2 vznikly dvě úsečky P1-I a I-P2 ! POZOR pokud se k bodům váží hodnoty pozice v textuře U a V, je nutné nově vzniklému bodu I dopočítat tyto hodnoty stejným způsobem jako koordináty. Jak uspořádat data? Pokud nechcete dopadnout jako já když mi při programování jedné hry vyšla minimální velikost paměti 10^20 bajtů, měli byste se zamyslet nad organizací struktury dat ;) Nejdřív se podíváme na samotný strom. Struktura bude vypadat asi nějak takhle: struct BSPtree { BSPnode *root Vertices vtx } No tak to nám zrovna moc neřeklo, je tam pointer na úplně první nodu, a list všech bodů celé scény. Zajímavější už je pohled na strukturu takového uzlu (node): struct BSPnode { BSPnode *front,*back polygon root list polylist } Front a back jsou větve stromu, resp. pointery na další nody. Root je polygon kterým dělíme prostor, a polylist je list všech polygonů v dané části prostoru (tozn. např. všechny polygony ležící před rootem z předchozí nody. Jak vybrat root polygon ? Na algoritmu jakým budu vybírat polygon kterým rozdělím prostor hodně záleží. Jde o to, aby strom byl vyvážený - tozn. aby před i za root polygonem byl zhruba stejný počet polygonů. A to z toho důvodu že to má vliv na výslednou rychlost při procházení stromem. Zároveň by se nemělo dělit zbytečně moc polygonů, jelikož to zvyšuje jejich celkový počet ve scéně, a tím zpomaluje výsledný výpočet v enginu. Proto se všechny (nebo část) polygonů z kterých vybíráme musí vyzkoušet. A to tak že vezmu jeden polygon po druhém a pro každý spočítám kolik polygonů leží na jedné straně, kolik na druhé, a kolik rozdělení tento polygon způsobí. Z toho se vypočítá "skóre" podle vztahu: score = nsplit * KSPLIT + abs(nfront-nback)*KBALANCE Nsplit je počet rozdělených polygonů, nfront a nback jsou počtu polygonů před nebo za root polygonem. KSPLIT a KBALANCE jsou koeficienty. Vyplatí se trochu si s nimi pohrát, někdy to může podstatně vylepšit celý strom. Mno, a čím menší skóre dostaneme, tím je polygon vhodnější kandidát na root polygon. Jak vytvořit takový strom - kód Jak jsem už nastánil, je to rekurzivní proces, takže kód by mohl vypadat nějak takhle: CreateTree(list plist) { root = FindRoot (plist) PartitionSpace (root, plist1, plist2) if plist1.is.not.empty.list { CreateTree(plist1) } if plist2.is.not.empty.list { CreateTree(plist2) } } Jak uložit a načíst strom z disku ? Ukládání a načítání BSP stromu se provádí podobně jako jeho vytváření. Jediný rozdíl je, že si musím zapsat jestli daná noda má další podnody (vpředu i vzadu), a zapsat ke každé nodě na disk. To se dá nastavit třeba jako byte z něhož se použijou 2 bity (přední a zadní podnoda). A opět pseudo-kód: WriteNode (node) { If node.front.exist { set flagbit in flagbyte } If node.back.exist { set flagbit in flagbyte } WriteFlags WriteNodeStructure If node.front.exist { WriteNode(front) } If node.back.exist { WriteNode(back) } } A úplně stejně i čtení ReadNode (node) { ReadFlags ReadNodeStructure If node.front.exist { ReadNode(front) } If node.back.exist { ReadNode(back) } } Jak takový strom použít ? Nejdřív základní použití BSP stromu: Standardní BSP traversal Jednoduše procházím celým stromem, a na každé nodě počítám jestli viewport (bod z kterého se dívám) leží před nebo za polygonem téhle nody. Jestli leží před, rekurzuju nejdřív přední subnodu, vykreslím polygon, a potom zadní subnodu. Pokud leží za, postup obrátím. Ale pokud viewport leží za, znamená to zároveň, že se na polygon dívám z jeho druhé strany, a tím pádem ho nemusím vykreslovat (pokud nekreslím "neviditelné" prochy záměrně, např. v drátěném modelu). No a jistě už všichni čekáte kód, tak tady ho máte ;) TraverseTree (node) { status=ClassifyPoint(ViewPort,node.root) if status=FRONT { if node.front.exist { TraverseTree (node.front) } DrawPolygon(node.root) if node.back.exist { TraverseTree (node.back) } } else { if node.back.exist { TraverseTree (node.back) } if wireframe { DrawPolygon(node.root) } if node.front.exist { TraverseTree (node.front) } } } To je ta nejjednodušší metoda. Polygony už jsou sice krásně setříděné, ale pořád ještě se kreslí polygony, které jiné polygony zcela překryjí, nebo nejsou z místa kde je kamera vůbec vidět. Další metodou založenou na BSP stromech je PVS. Ta už je ale založena přímo na podstatě členění prostoru (např. portály), a vychází z jiné konstrukce BSP stromu. Tuto metodu se vám pokusím objasnit až v příštím pokračování, zčásti i proto, abych mněl čas napsat nějaký ukázkový funkční program ;) Tím se dostávám k BSP compileru, který jsem pro tento účel sbastlil ;) Tak tady je zdroják pro DJGPPv2 ale měl by jít zkompilovat i v Linuxu. Ale jako obvykle nečekejte nic moc extra, je to spíš taková splácanina ;) Jan Dvořák a.k.a Johny Dog/Progress 1435 (johnydog@email.cz) výheň