3D - Engine 07 - S-buffer
Zdravím všechny programátory a programátorky, co se pořád chodí dívat, jestli něco nepřibylo
a jejich snahu chválím. Omlouvám se za svoji lenost a budu se to snažit dohnat. Tak jsem
slíbil, že se podíváme na S-Buffery a je to tady. Tak napřed :
Co to je S-Buffer a jak to funguje ?
S-Buffer je jak název napovídá buffer segmentů (spanů). To vám asi moc neříká, co ? Z-Buffer funguje jako buffer všech souřadnic Z na celém obraze. Ale přitom na povrchu polygonů je Z rozložená lineárně, tak proč ji zbytečně počítat pro celou obrazovku ? Dělá se to tak, že při rasterizaci se polygon nekreslí, ale jeho jednotlivé segmenty se posílají do bufferu a tam se protínají s ostatními. Segmenty jsou na řádce obvykle seřazené (rychleji se v nich hledá), obsahují svoji pozici (první a poslední x) a souřadnice textury. Nakonec se zavolá nějaká funkce, která vykreslí celý obsah bufferu do paměti.
S-Buffer versus Z-Buffer S-Buffer
Varianty S-Bufferu
S-Buffer má jednu variantu, a tou je takzvaný C-Buffer (coverage). Ten trochu řeší problém se složitostí scény. Funguje to tak, že se segmenty napřed dají do bufferu, protnou se a to, co z nich zbude se okamžitě kreslí. Vyžaduje to ale polygony setříděné odpředu dozadu. Potom se vlastně v Bufferu neuchovává nic kromě x-pozic segmentů a segmenty se tudíž mohou spojovat, a tak jich nevznikne tolik a vyhledávání je pořád rychlé. Možná že se dokopu k tomu, udělat example, abyste to mohli srovnat s klasickým S-Bufferem.
Realizace
Pro S-Buffer je nejlepší asi dvousměrný spojový seznam. (můžete zkusit klasické pole s binárním hledáním, ale tohle bude asi rychlejší) Spojový seznam je struktura, kde každá buňka má pointer na předchozí a další buňku :
Takhle nějak by to vypadalo v c-čku. První buňka má ukazatel prev = NULL a poslední zase next = NULL. Nevýhodou tohoto seznamu je nemožnost indexace, k buňce si musíte "doskákat". Výhodou je, že pro přesunutí / přidání buňky nemusíte posouvat celé pole. K seznamu ještě potřebujete něco, co bude velice rychle přidělovat paměť na nové segmenty. (kdybyste alokovali paměť po kouscích při kreslení, nebylo by to moc rychlé) Něco takového se obvykle dělá pomocí manageru, který na začátku naalokuje např. 1000 segmentů a když si o ně rasterizer řekne, nějaké mu přidělí. Když vyčerpá všech 1000, naalokuje dalších 1000 a tak pořád. Jediný problém je, že by se neměly měnit pointery na jednotlivé prvky, ale to lehce vyřeší dvojrozměrné pole. (realloc() občas změní adresu celého pole).
Potom je potřeba nějaká struktura pro obrazovou řádku, jejichž pole vlastně tvoří S-Buffer.
seg je pointer na první segment, n_seg_num je počet segmentů ve scanline a n_seg_used je počet použitých segmentů (do scanline se segmenty jen přidávají, takže nelze spoléhat na posledí segment kde next = NULL). Ze scanline se tedy udělá seznam a každé se pro začátek přiřadí 50 segmentů. n_seg_used se všude nastaví na 0 a může začít rasterizace. Pro ni potřebujeme nějakou funkci, která segmenty protne. Jak na to ? Dva segmenty mohou být jen v několika vzájemných polohách :
Proč se rozlišuje přidaný a stávající segment ? To proto abyste se lépe orientovali v example,
protože tam jsou jednotlivé pozice označeny právě takhle. Když už pomocí různých podmínek
zjistíte, kam (pod jakou situaci) segment patří, je jednoduché ho rozdělit. Stačí k tomu
znalost rovnice přímky, pomocí které spočítáte průsečíky obou segmentů a podle toho se
situace řeší.
Example
Example je v podstatě na stejné úrovni jako BSP-Engine z minulého dílu, jen používá S-Buffer. Je to proto, abyste mohli zhruba porovnat rychlost této techniky. Example však nedemonstruje sílu S-Bufferu naplno, protože se v podstatě nemá co překreslovat. V místnosti jsou jen ty pilíře, které velké překreslení nezpůsobí. Proto je tam ještě jeden svet.3ds a svet.bsp, kde je zase stejný svět, ale naplno v něm dolehne nedokonalost samotného BSP. Je to taková chodba s trojúhelníkovým profilem, neměl jsem na to moc času. Když se podíváte z kraje, BSP-Stromy budou několikrát překreslovat obrazovku - napřed se nakreslí chodba vzadu, pak ta před ní a nakonec ta ve které stojíte. S-Buffer ale bude kreslit jen to, co je vidět. Kód nebudu nějak dopodrobna vysvětlovat, protože vlastně není co. Tak popořadě :
Directx.cpp
Font_Eng.cpp
Load_3ds.cpp
Main.cpp
Matice.cpp
Pyramid.cpp
Raster.cpp
Seg_Man.cpp
Tak, a to je konec, tády dády dá ...
Tady si můžete stáhnout examplesák + zdroják :
Co to je S-Buffer a jak to funguje ?
S-Buffer je jak název napovídá buffer segmentů (spanů). To vám asi moc neříká, co ? Z-Buffer funguje jako buffer všech souřadnic Z na celém obraze. Ale přitom na povrchu polygonů je Z rozložená lineárně, tak proč ji zbytečně počítat pro celou obrazovku ? Dělá se to tak, že při rasterizaci se polygon nekreslí, ale jeho jednotlivé segmenty se posílají do bufferu a tam se protínají s ostatními. Segmenty jsou na řádce obvykle seřazené (rychleji se v nich hledá), obsahují svoji pozici (první a poslední x) a souřadnice textury. Nakonec se zavolá nějaká funkce, která vykreslí celý obsah bufferu do paměti.
S-Buffer versus Z-Buffer S-Buffer
- Méně závislý na rozlišení (velikost = výška, segmentů na řádce s rozlišením nepřibývá)
- Nulové překreslování (ušetří čas v texturovací smyčce)
- Dobré prolínání objektů
- Závisí na složitosti scény
- Zabere relativně málo paměti
- Závislý na rozlišení (velikost = výška × šířka)
- Neomezené překreslování
- Dobré prolínání objektů
- Nezávisí na složitosti scény
- Zabere hodně paměti
Varianty S-Bufferu
S-Buffer má jednu variantu, a tou je takzvaný C-Buffer (coverage). Ten trochu řeší problém se složitostí scény. Funguje to tak, že se segmenty napřed dají do bufferu, protnou se a to, co z nich zbude se okamžitě kreslí. Vyžaduje to ale polygony setříděné odpředu dozadu. Potom se vlastně v Bufferu neuchovává nic kromě x-pozic segmentů a segmenty se tudíž mohou spojovat, a tak jich nevznikne tolik a vyhledávání je pořád rychlé. Možná že se dokopu k tomu, udělat example, abyste to mohli srovnat s klasickým S-Bufferem.
Realizace
Pro S-Buffer je nejlepší asi dvousměrný spojový seznam. (můžete zkusit klasické pole s binárním hledáním, ale tohle bude asi rychlejší) Spojový seznam je struktura, kde každá buňka má pointer na předchozí a další buňku :
|
Takhle nějak by to vypadalo v c-čku. První buňka má ukazatel prev = NULL a poslední zase next = NULL. Nevýhodou tohoto seznamu je nemožnost indexace, k buňce si musíte "doskákat". Výhodou je, že pro přesunutí / přidání buňky nemusíte posouvat celé pole. K seznamu ještě potřebujete něco, co bude velice rychle přidělovat paměť na nové segmenty. (kdybyste alokovali paměť po kouscích při kreslení, nebylo by to moc rychlé) Něco takového se obvykle dělá pomocí manageru, který na začátku naalokuje např. 1000 segmentů a když si o ně rasterizer řekne, nějaké mu přidělí. Když vyčerpá všech 1000, naalokuje dalších 1000 a tak pořád. Jediný problém je, že by se neměly měnit pointery na jednotlivé prvky, ale to lehce vyřeší dvojrozměrné pole. (realloc() občas změní adresu celého pole).
Potom je potřeba nějaká struktura pro obrazovou řádku, jejichž pole vlastně tvoří S-Buffer.
|
seg je pointer na první segment, n_seg_num je počet segmentů ve scanline a n_seg_used je počet použitých segmentů (do scanline se segmenty jen přidávají, takže nelze spoléhat na posledí segment kde next = NULL). Ze scanline se tedy udělá seznam a každé se pro začátek přiřadí 50 segmentů. n_seg_used se všude nastaví na 0 a může začít rasterizace. Pro ni potřebujeme nějakou funkci, která segmenty protne. Jak na to ? Dva segmenty mohou být jen v několika vzájemných polohách :
Example
Example je v podstatě na stejné úrovni jako BSP-Engine z minulého dílu, jen používá S-Buffer. Je to proto, abyste mohli zhruba porovnat rychlost této techniky. Example však nedemonstruje sílu S-Bufferu naplno, protože se v podstatě nemá co překreslovat. V místnosti jsou jen ty pilíře, které velké překreslení nezpůsobí. Proto je tam ještě jeden svet.3ds a svet.bsp, kde je zase stejný svět, ale naplno v něm dolehne nedokonalost samotného BSP. Je to taková chodba s trojúhelníkovým profilem, neměl jsem na to moc času. Když se podíváte z kraje, BSP-Stromy budou několikrát překreslovat obrazovku - napřed se nakreslí chodba vzadu, pak ta před ní a nakonec ta ve které stojíte. S-Buffer ale bude kreslit jen to, co je vidět. Kód nebudu nějak dopodrobna vysvětlovat, protože vlastně není co. Tak popořadě :
Directx.cpp
Rozhraní pro directy. Tady se nezměnilo vůbec nic.
(můžete to samozřejmě přepsat, pokud děláte pod dosem / linuxem)
|
Font_Eng.cpp
Tohle se taky nezměnilo. Je tady funkce pro nahrávání truecolor bitmap (chystám ukázky
jak nahrávat i jiné formáty - .jpeg .pcx .tga .raw možná .gif a .png) a funkce pro tisk
normálního stringu do videopaměti. (font je v bitmapě)
|
Load_3ds.cpp
Modul pro nahrávání *.3ds scén. Možná přibude modul pro nahrávání Quake ]|[ levelů, protože
hodně z vás (podle mailů) nemá 3d - studio / 3d - max. Možná že dám něco do downloadů...
|
Main.cpp
Funkce WinMain() skrývá inicializační funkce, loadování .. a ve funkci Wokno se kreslí
obraz a hýbe kamerou. Tady je to nejdůležitější pro S-Buffer :
InitScreen() smaže S-Buffer (označí ve všech scanline počet nepoužitých segmentů na 0 - to samé, co dělal Clean_ZBuffer();) Potom je tam smyčka co kreslí jednotlivé objekty, ta se taky nezměnila, jen potom funkce DrawObject() vypadá jinak. No a nakonec se volá funkce ReleaseScreen(), která vykreslí obsah S-Bufferu do nějaké videopaměti. |
Matice.cpp
Standardní operace s maticemi 4. řádu ...
(co dodat ? - uspořádání matice je shodné s maticemi v OpenGL)
|
Pyramid.cpp
Klipovací pyramida, snad beze změny ...
|
Raster.cpp
Pozor, tak tady je toho dost. V Init_Engine() se vytvoří S-Buffer :
Na začátku se naalokuje pole Scanline o velikosti shodné s výškou obrazu. Potom se každé scanline přiřadí st_segs (= 20) segmentů a počet použitých se nastaví na 0. (Takže volání InitScreen() je při prvním snímku zbytečné. Jo, ještě první řádek - zavolá se náš Memory Manager, aby si ukousl něco paměti pro přidělování segmentů). v Uninit_Engine() se zase tohle všechno uvolní. Potom jsou tam navíc funkce InitScreen() a ReleaseScreen(), které smažou / vykreslí S-Buffer (jejich obsah je velice prostý, snad to všichni pochopíte.) Jen snad - v ReleaseScreen (jak vás možná napadlo) by se obrazovka mohla zrovna mazat, takže by úplně odpadlo volání InitScreen(), ale jsou tu případy, kdy obsah bufferu budeme ještě potřebovat (kreslení sprite, efektů ...) Dál, ve funkci Draw_Polygon() není jako parametr videopaměť, protože se polygon nekreslí do video, ale do S-Bufferu. Jinak rasterizace probíhá normálně, jen je tam jeden segment, kterému se na začátku nastaví parametry jako textura, její rozložení po obrazovce ... (parametry stejné po celém polygonu) a při kreslení každé řádky se nastaví ještě specifické parametry (pozice, pozice textury) a pošle se do S-Bufferu. V DrawObject() je změna taky jen to, že nepřenáší pointer videopaměti. |
Seg_Man.cpp
To je v podstatě srdce S-Bufferu. Na začátku je několik konstant :
startup_seg = 1024; - počet segmentů na začátku
seg_inc = 256; - počet segmentů, které se budou alokovat, když dojde těch 1024.
Nemusí to být mocniny dvou, jen mi došla fantazie. S tím seg_inc je dobré si pohrát,
aby když počet segmentů o pár přeroste doustupné se zbytečně nealokovalo moc paměti.
Nakonec ještě přidám pár grafů, jak to v praxi vypadá. Potom je tam pole stack, které
funguje jako zásobník, ze kterého se přiděluje paměť. Funguje to tak, že první dimenze
se mění. Druhá dimenze je v prvním případě pole o velikosti 1024 prvků (startup seg)
a dál už jen 256 (seg_inc). Proč je to takhle složitě ? Kdyby se volalo realloc() jen
pro jednorozměrné pole, mohla by se změnit (a taky že se mění) jeho adresa. Takhle se mění
jen adresa první dimenze pole, na čemž nezáleží a adresa jednotlivých segmentů zůstává
pořád stejná (Používá se spojový seznam -> uchovávají se jen pointery na jeho prvky, tudíž
jejich adresa se nesmí změnit.) Potom následuje pár proměnných, které informují o tom,
jak velké už je primární pole, kolik z něj je už přiděleno a zda se poslední přidělování
paměti povedlo (mem_stat). Potom následují funkce na uvolnění paměti - UninitSManager(),
uvolnění všech naalokovaných segmentů (ale ne z paměti - jen pro opětovné přidělení)
Reset_SManager(), pro zjištění kolik paměti je naalokováno (GetMem_Usage()) a jestli někde
není chyba (GetMem_Status()). Funkce Grow_Reservoir() zvětší zásobník o seg_inc jednotek.
Následující funkce jsou pro přidělování segmentů :
Každá funkce, pokud ve scanline nemá dostatek segmentů, volá Grow_Reservoir(); Potom následuje funkce, kterou volá rasterizer, když chce přidat segment :
Tady se segment protíná s ostatními. Makro SEG_Z(seg, x) zjistí z-souřadnici segmentu seg na nějaké x souřadnici. A SEG_SPLIT(a, b) zjistí pozici průsečíku dvou segmentů a a b. Můžete si zkontrolovat podmínky, jak sedí na ilustrační obrázek na začátku.
|
Tady si můžete stáhnout examplesák + zdroják :
No, a o čem to bude příště ? Když se podíváte na obrázek, vidíte že ty díry ve stropě jsou
trochu "rozsypané" - textura je moc velká na obraz, takže se přeskakují některé její pixely.
důsledkem čehož je blikání těch mříží. To odstraníme právě příště metodou, která se nazývá
Mip-Mapping (ale o tom opravdu až příště)
Jo, tady jsou ještě ty grafy (je to počet segmentů o různé délce v každé scéně) :
Jo, tady jsou ještě ty grafy (je to počet segmentů o různé délce v každé scéně) :
1 ( 100) : ************************************** 2 ( 127) : ************************************************ 3 ( 130) : ************************************************* 4 ( 130) : ************************************************* 5 ( 100) : ************************************** 6 ( 103) : *************************************** 7 ( 107) : **************************************** 8 ( 99) : ************************************* 9 ( 98) : ************************************* 10 ( 83) : ******************************* 11 ( 82) : ******************************* 12 ( 68) : ************************** 13 ( 134) : ************************************************** 14 ( 35) : ************** 15 ( 37) : ************** 16 ( 38) : *************** 17 ( 29) : *********** 18 ( 34) : ************* 19 ( 34) : ************* 20 ( 30) : ************ 21 ( 31) : ************ 22 ( 26) : ********** 23 ( 25) : ********** 24 ( 27) : *********** 25 ( 22) : ********* 26 ( 19) : ******** 27 ( 18) : ******* 28 ( 13) : ***** 29 ( 13) : ***** 30 ( 11) : ***** 31 ( 5) : ** 32 ( 3) : ** 33 ( 4) : ** 34 ( 5) : ** 35 ( 7) : *** 36 ( 3) : ** 37 ( 3) : ** 38 ( 5) : ** 39 ( 6) : *** 40 ( 4) : ** 41 ( 5) : ** 42 ( 5) : ** 43 ( 3) : ** 44 ( 4) : ** 45 ( 9) : **** 46 ( 8) : *** 47 ( 10) : **** 48 ( 9) : **** 49 ( 11) : ***** 50 ( 8) : *** 51 ( 6) : *** 52 ( 4) : ** 53 ( 2) : * 54 ( 131) : ************************************************* 55 ( 2) : * 56 ( 3) : ** 57 ( 2) : * 58 ( 2) : * 59 ( 3) : ** 60 ( 76) : ***************************** 61 ( 2) : * 63 ( 1) : * 64 ( 3) : ** 65 ( 2) : * 66 ( 2) : * 67 ( 6) : *** 68 ( 4) : ** 71 ( 1) : * 72 ( 1) : * 73 ( 1) : * 74 ( 4) : ** 76 ( 1) : * 77 ( 1) : * 78 ( 2) : * 79 ( 2) : * 80 ( 2) : * 81 ( 2) : * 82 ( 2) : * 83 ( 1) : * 84 ( 3) : ** 85 ( 2) : * 86 ( 1) : * 87 ( 3) : ** 88 ( 1) : * 89 ( 3) : ** 90 ( 3) : ** 91 ( 2) : * 92 ( 1) : * 93 ( 2) : * 94 ( 7) : *** 95 ( 2) : * 96 ( 1) : * 97 ( 5) : ** 98 ( 3) : ** 99 ( 1) : * 100 ( 3) : ** 101 ( 4) : ** 102 ( 2) : * 104 ( 6) : *** 105 ( 4) : ** 106 ( 2) : * 107 ( 4) : ** 108 ( 2) : * 109 ( 3) : ** 110 ( 4) : ** 111 ( 8) : *** 112 ( 7) : *** 113 ( 2) : * 114 ( 4) : ** 115 ( 5) : ** 116 ( 10) : **** 117 ( 59) : *********************** 118 ( 2) : * 196 ( 3) : ** 197 ( 2) : * 198 ( 3) : ** 199 ( 3) : ** 200 ( 2) : * 201 ( 3) : ** 202 ( 3) : ** 203 ( 2) : * 204 ( 3) : ** 205 ( 8) : ***Takhle to vypadá v jednoduché scéně - převažují segmenty s malou délkou
1 ( 270) : ********************************************* 2 ( 302) : ************************************************** 3 ( 285) : ************************************************ 4 ( 262) : ******************************************** 5 ( 266) : ********************************************* 6 ( 265) : ******************************************** 7 ( 223) : ************************************* 8 ( 216) : ************************************ 9 ( 166) : **************************** 10 ( 171) : ***************************** 11 ( 133) : *********************** 12 ( 128) : ********************** 13 ( 124) : ********************* 14 ( 117) : ******************** 15 ( 95) : **************** 16 ( 88) : *************** 17 ( 92) : **************** 18 ( 61) : *********** 19 ( 64) : *********** 20 ( 61) : *********** 21 ( 63) : *********** 22 ( 53) : ********* 23 ( 65) : *********** 24 ( 48) : ******** 25 ( 52) : ********* 26 ( 41) : ******* 27 ( 51) : ********* 28 ( 35) : ****** 29 ( 38) : ******* 30 ( 41) : ******* 31 ( 35) : ****** 32 ( 21) : **** 33 ( 23) : **** 34 ( 26) : ***** 35 ( 20) : **** 36 ( 23) : **** 37 ( 22) : **** 38 ( 22) : **** 39 ( 10) : ** 40 ( 10) : ** 41 ( 13) : *** 42 ( 10) : ** 43 ( 6) : * 44 ( 14) : *** 45 ( 7) : ** 46 ( 9) : ** 47 ( 11) : ** 48 ( 10) : ** 49 ( 8) : ** 50 ( 10) : ** 51 ( 9) : ** 52 ( 8) : ** 53 ( 7) : ** 54 ( 6) : * 55 ( 6) : * 56 ( 3) : * 57 ( 3) : * 58 ( 4) : * 59 ( 3) : * 60 ( 3) : * 61 ( 5) : * 62 ( 2) : * 63 ( 3) : * 64 ( 4) : * 65 ( 3) : * 66 ( 2) : * 67 ( 5) : * 68 ( 2) : * 69 ( 3) : * 70 ( 5) : * 72 ( 4) : * 73 ( 3) : * 74 ( 2) : * 75 ( 3) : * 76 ( 4) : * 77 ( 1) : * 78 ( 5) : * 79 ( 3) : * 80 ( 2) : * 81 ( 3) : * 82 ( 3) : * 83 ( 3) : * 84 ( 3) : * 85 ( 2) : * 86 ( 3) : * 87 ( 4) : * 88 ( 1) : * 89 ( 3) : * 90 ( 4) : * 91 ( 1) : * 92 ( 2) : * 93 ( 4) : * 94 ( 2) : * 95 ( 2) : * 96 ( 4) : * 98 ( 4) : * 99 ( 4) : * 100 ( 2) : * 101 ( 2) : * 102 ( 3) : * 103 ( 2) : * 104 ( 3) : * 105 ( 2) : * 106 ( 2) : *A tohle byl obrázek terénu. Delší segmenty se téměř nevyskytují.
(není moc vidět že to je terén - není tam stínování...)
... tak zase příště !
-tHE SWINe-
Valid HTML 4.01