Geometrie/Viditelnost

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#

Popis

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-hodnotu toho bodu který leží nejblíže pozorovateli a jehož průmět leží v odpovídajícím pixelu v rastru

Algoritmus

Vyplň obrazovou paměť barvou pozadí
Vyplň paměť hloubky hodnotou (- $\infty$ )
Každou plochu rozlož na pixely a pro každý její pixel $[x_{i},y_{i}]$ stanov hloubku $z_{i}$
Má-li $z_{i}$ větší hodnotu než položka $[x_{i},y_{i}]$ v z-bufferu pak
1. obarvi pixel $[x_{i},y_{i}]$ v obrazové paměti barvou této plochy
2. u položky $[x_{i},y_{i}]$ v z-bufferu aktualizuj hodnotu $z_{i}$

Výhody

Vysoká rychlost
Snadná implementace
Správné řešení najde v každém případě
hardwarová implementace

Nevýhody

Nároky na paměť jež algoritmus klade

Princip fungování algoritmu Z-BUFFER

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 $z_{min}$ 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í

$z1_{max}<z2_{min}$ , kde $z1_{max}$ je největší $z$ souřadnice aktivní plochy $P1$ a $z2_{min}$ 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.

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.

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

Popis vlastního algoritmu. Veškeré objekty, metody a pochody musí být do detailu popsány.

Aspekty naši implementace

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

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.

Kód v jazyce C#

Příklad řešení v jazyce C#.

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;
					}
				}
			}
		}
	}
}

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;
   }
  }
 }

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.