Geometrie/Viditelnost
Rastrové algoritmy viditelnosti
[editovat | editovat zdroj]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#
Popis
[editovat | editovat zdroj]Z-buffer
[editovat | editovat zdroj]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-hodnotu toho bodu který leží nejblíže pozorovateli a jehož průmět leží v odpovídajícím pixelu v rastru
Algoritmus
[editovat | editovat zdroj]- Vyplň obrazovou paměť barvou pozadí
- Vyplň paměť hloubky hodnotou (-)
- Každou plochu rozlož na pixely a pro každý její pixel stanov hloubku
- Má-li větší hodnotu než položka v z-bufferu pak
- obarvi pixel v obrazové paměti barvou této plochy
- u položky v z-bufferu aktualizuj hodnotu
Výhody
[editovat | editovat zdroj]- Vysoká rychlost
- Snadná implementace
- Správné řešení najde v každém případě
- hardwarová implementace
Nevýhody
[editovat | editovat zdroj]- Nároky na paměť jež algoritmus klade
Princip fungování algoritmu Z-BUFFER
Malířův Algoritmus
[editovat | editovat zdroj]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 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ě.
Nejpoužívanější testy překrývání
[editovat | editovat zdroj]- , kde je největší souřadnice aktivní plochy a je nejmenší souřadnice testované plochy .
- Průmět aktivní plochy do roviny nepřekrývá průmět testované plochy do roviny .
- Všechny vrcholy aktivní plochy leží v poloprostoru, určeném testovanou plochou a odvráceném od pozorovatele.
- Všechny vrcholy testované plochy leží v poloprostoru určeném aktivní plochou 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.
Upozornění
[editovat | editovat zdroj]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.
Ukázka konfliktní pozice při níž může dojít u malířova algoritmu ke špatnému zobrazení
Ukázka situace která může vést k zacyklení malířova algoritmu
Na tyto situace se můžeme pokusit reagovat rozdělením ploch na menší části,tímto ale klesá efektivita algoritmu.
Algoritmizace
[editovat | editovat zdroj]Popis vlastního algoritmu. Veškeré objekty, metody a pochody musí být do detailu popsány.
Aspekty naši implementace
[editovat | editovat zdroj]Malířův algoritmus
[editovat | editovat zdroj]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
ZBuffer algoritmus
[editovat | editovat zdroj]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.
Kód v jazyce C#
[editovat | editovat zdroj]Příklad řešení v jazyce C#.
Z-Buffer
[editovat | editovat zdroj]Ř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;
}
}
}
}
}
}
Malířův Algoritmus
[editovat | editovat zdroj]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;
}
}
}
Autoři
[editovat | editovat zdroj]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.