Geometrie/Viditelnost
Z Wikiknih
Obsah |
[editovat] Rastrové algoritmy viditelnosti
Cílem článku je podat informační povídání o nejpoužívanějších algoritmech pro řešení viditelnosti objektů při jejich rasterizaci.
Článek pojednává o postupech nazývaných "Z-Buffer" a "Malířův Algoritmus"
Ukázky algoritmů jsou napsány v jazyce C#
[editovat] Popis
[editovat] Z-buffer
Základem metody je použití paměti hloubky (z-buffer) která tvoří dvojrozměrné pole , jehož rozměry jsou totožné s rozměry zobrazovacího okna.Každá položka paměti obsahuje z toho bodu který leží nejblíže pozorovateli a jehož průmět leží v odpovídajícím pixelu v rastru
[editovat] Algoritmus
- Vyplň obrazovou paměť barvou pozadí
- Vyplň paměť hloubky hodnotou (-
) - Každou plochu rozlož na pixely a pro každý její pixel [xi,yi] stanov hloubku zi
- Má li zi větší hodnotu než položka [xi,yi] v z-bufferu pak
- obarvi pixel [xi,yi] v obrazové paměti barvou této plochy
- u položky [xi,yi] v z-bufferu aktualizuj hodnotu zi
[editovat] Výhody
- Vysoká rychlost
- Snadná implementace
- Správné řešení najde v každém případě
- hardwarová implementace
[editovat] Nevýhody
- Nároky na paměť jež algoritmus klade
[editovat] Malířův Algoritmus
Založeno na myšlence vykreslování všech ploch postupně odzadu dopředu, přes objekty v pozadí se kreslí objekty v popředí. Inspirováno představou práce malíře, který na podkladovou barevnou vrstvu nanáší další vrstvy. Nejprve nalezneme pro každou plochu její nejmenší souřadnici zmin a podle této souřadnice plochy iniciálně uspořádáme. První plocha v seznamu je označena jako aktivní a je podrobena několika testům, zda nepřekrývá ostatní plochy. Pokud lze po nich rozhodnout, že aktivní plocha leží za všemi ostatními, je vykreslena a vyřazena ze seznamu. V opačném případě dojde v seznamu k výměně aktivní plochy s plochou, u které dopadly všechny testy pozitivně.
[editovat] Nejpoužívanější testy překrývání
- z1max < z2min, kde z1max je největší z souřadnice aktivní plochy P1 a z2min je nejmenší z souřadnice testované plochy P2.
- Průmět aktivní plochy P1 do roviny xy nepřekrývá průmět testované plochy P2 do roviny xy.
- Všechny vrcholy aktivní plochy P1 leží v poloprostoru, určeném testovanou plochou P2 a odvráceném od pozorovatele.
- Všechny vrcholy testované plochy P2 leží v poloprostoru určeném aktivní plochou P1 a přivráceném k pozorovateli.
Mnoho implementací malířova algoritmu se však omezuje na provádění jen těch nejjednodušších testů (např. 1 a 2). To přispívá k zrychlení činnosti algoritmu.
[editovat] Upozornění
Malířův algoritmus není vhodný pro všechny případy,některé pozice (protínání) zobrazovaných objektů mohou vést k špatnému zobrazení. Pokud se objekty navzájem překrývají může to vést až k zacyklení algoritmu.
Na tyto situace se můžeme pokusit reagovat rozdělením ploch na menší části,tímto ale klesá efektivita algoritmu.
[editovat] Algoritmizace
Popis vlastního algoritmu. Veškeré objekty, metody a pochody musí být do detailu popsány.
[editovat] Aspekty naši implementace
[editovat] Malířův algoritmus
V naši implementaci není ošetřen případ kdy dochází k protnutí dvou ploch ,ani případ vzájemného zacyklení ploch
[editovat] ZBuffer algoritmus
Algoritmus by si měl poradit se všemi vzájemnými polohami ploch nicméně se může dopouštět chybného zobrazování v případech, kdy jsou zobrazované plochy dosti blízko sebe. Toto je způsobeno numerickou chybou jež vzniká při zaokrouhlování výpočtu vzdálenosti vykreslovaných bodů od pozorovatele.
[editovat] Kód v jazyce C#
Příklad řešení v jazyce C#.
[editovat] Z-Buffer
Řešení algoritmu Z-Buffer se skrývá v třídě ZBuffering. Nejprve se inicializuje pole představující jednotlivé vykreslované body na implicitní hodnotu
public void InicilizujPole()
{
// inicializuji pole a vyplni jej pocatecni hodnotou
barva = new Color[sirka, vyska];
hloubka = new float[sirka, vyska];
Color c = new Color();
c = Color.White;//Color.WhiteSmoke;
for(int indX = 0; indX < barva.GetLength(0); indX++)
{
for(int indY = 0; indY < barva.GetLength(1); indY++)
{
barva[indX,indY] = c;
hloubka[indX,indY] = maxReal;
}
}
}
Poté tyto inicializované barvy přebarvím barvami bodů jež mají nejmenší vzdálenost od pozorovatele
public void Vypocitej(Model model)
{
float dzx, dzy, zxx;
PointF horniBod, dolniBod;
Point horniBodP, dolniBodP;
float[] normV;
Color c = new Color();
Bod3D[] polynom;
// pro kazdou stenu testuji pixel a nastavuji jeho barvu a hloubku
for(int stena = 1; stena <= model.steny.Count; stena++)
{
// mixuji barvu
c = Color.FromArgb((100+stena*10)%255, (50+stena*33)%255,stena*50)%255);
polynom = this.DejPolynomSteny(stena, model);
normV = ZjistiNormalVektor((Bod3D)polynom.GetValue(0), (Bod3D) polynom.GetValue(1),(Bod3D)polynom.GetValue(2));
dzx = - (normV[0]/normV[2]);
dzy = - (normV[1]/normV[2]); //pro bod [x + 1,y ]
// zjistim si rohy testovane plochy
horniBod = new PointF(polynom[0].x, polynom[0].y);
dolniBod = new PointF(polynom[0].x, polynom[0].y);
for(int i = 1; i < polynom.Length; i++)
{
if(polynom[i].x < horniBod.X)
{
horniBod.X = (polynom[i]).x;
}
if(polynom[i].y > horniBod.Y)
{
horniBod.Y = polynom[i].y;
}
if(polynom[i].x > dolniBod.X)
{
dolniBod.X = polynom[i].x;
}
if(polynom[i].y < dolniBod.Y)
{
dolniBod.Y = polynom[i].y;
}
}
//zacinam projizdet zjistenou miniplosku
// vypocitam hloubku (zi) pro bod [indX,indY]
// a to pomoci bodu A = [x, y, z] a norm. vektoru
horniBodP = this.PrevedBodNaPixel(horniBod.X, horniBod.Y);
dolniBodP = this.PrevedBodNaPixel(dolniBod.X, dolniBod.Y);
Point[] points;
PointF[] pointsF;
for(int y = horniBodP.Y; y >= dolniBodP.Y; y--)
{
pointsF = this.DejPrunikyVBodech(model, stena, PrevedPixelNaBod(0, y).Y);
points = this.PrevedBodyNaPixely(pointsF);
for(int p = 0; p < points.Length -1; p+=2)
{
for(int x = points[p].X; x <= points[p+1].X; x++)
{
zxx = VypocitejZ2(polynom[0], normV, this.PrevedPixelNaBod(x, 0).X, pointsF[p].Y);
if(zxx < hloubka[x,y])
{
hloubka[x,y] = zxx;
barva[x,y] = c;
}
}
}
}
}
}
[editovat] Malířův Algoritmus
Algoritmus k setřídění stěn používaný malířovým algoritmem
public void SetridSteny(Model model)
{
int looping, internal_looping;
float aktualni_stena_zmin, porovnavana_stena_zmin;
int pocet_setridenych_sten, index_porovnavane_steny;
bool vysledek_testu, stena_vlozena, zamena_poradi;
Stena aktualni_stena, porovnavana_stena;
ArrayList looping_check;
looping_check=new ArrayList();
// setrideni sten podle jejich minimalni Z souradnice
setridene_steny.Add(model.steny[1]);
pocet_setridenych_sten=1;
index_porovnavane_steny=2;
if (model.steny.Count > 1)
{
// vkladani dalsich sten dle jejich Z-min
for (looping=0; looping < model.steny.Count; looping++)
{
// resetovani looping checku (nastaveni na 0)
looping_check.Add((int)0);
// pro kazdou stenu najdi jeji Z-min
aktualni_stena=((Stena)model.steny[index_porovnavane_steny]);
aktualni_stena_zmin=MinimalniZSouradnice(model,aktualni_stena);
// vlozeni/pridani na konec
stena_vlozena=false;
for (internal_looping=0; internal_looping < pocet_setridenych_sten; internal_looping++)
{
// zjisti Z-min dane zarazene steny
porovnavana_stena=((Stena)setridene_steny[internal_looping]);
porovnavana_stena_zmin=MinimalniZSouradnice(model,porovnavana_stena);
if (aktualni_stena_zmin < porovnavana_stena_zmin)
{
// vlozeni do seznamu
stena_vlozena=true;
setridene_steny.Insert(internal_looping,model.steny[index_porovnavane_steny]);
}
}
if (!(stena_vlozena))
{
// pridani na konec
setridene_steny.Add(model.steny[index_porovnavane_steny]);
}
pocet_setridenych_sten++;
index_porovnavane_steny++;
if (index_porovnavane_steny > model.steny.Count) break;
}
}
// nyni jsou steny v "setridene_steny" srovnany dle jejich rostouci z-min
if (pocet_setridenych_sten > 1)
{
for (looping=0; looping+1 < pocet_setridenych_sten; looping++)
{
zamena_poradi=false;
aktualni_stena=((Stena)setridene_steny[looping]);
porovnavana_stena=((Stena)setridene_steny[looping+1]);
//porovnavaci testy na pripadnou zmenu poradi sten
// nejprve porovname Z souradnice
vysledek_testu=PorovnaniZSouradnic(model,aktualni_stena,porovnavana_stena);
if (!(vysledek_testu))
{
// porovnavame X a Y souradnice -- TEST [A]
vysledek_testu=PorovnaniXSouradnic(model,aktualni_stena,porovnavana_stena);
if (!(vysledek_testu))
{
vysledek_testu=PorovnaniYSouradnic(model,aktualni_stena,porovnavana_stena);
if (!(vysledek_testu))
{
// vsechny vrcholy jedne steny lezi POD stenou druhe -- TEST [B]
vysledek_testu=PorovnaniStena1PodStenou2(model,aktualni_stena,porovnavana_stena);
if (!(vysledek_testu))
{
// vsechny vrcholy druhe steny lezi NAD stenou prvni -- TEST [C]
vysledek_testu=PorovnaniStena2NadStenou1(model,aktualni_stena,porovnavana_stena);
if (!(vysledek_testu))
{
// TEST [D] - prumet
zamena_poradi=true;
}
}
}
}
}
if (zamena_poradi)
{
/* porovnani looping_check - porovnavana stena nemuze byt
posunovana vpred (pred aktualni), pokud byla jiz nekdy posunovana dozadu
*/
if (((int)looping_check[looping+1]) == 1) zamena_poradi=false;
if (zamena_poradi)
{
setridene_steny[looping]=porovnavana_stena;
setridene_steny[looping+1]=aktualni_stena;
looping=((int)looping_check[looping]);
looping_check[looping]=looping_check[looping+1];
looping_check[looping+1]=looping;
looping=-1;
}
}
}
[editovat] Autoři
Tento text vypracovali studenti Univerzity Palackého v Olomouci katedry Matematické informatiky jako součást zápočtového úkolu do předmětu Počítačová geometrie.
