GrafikaGyakorloInkrementalisKepszintezis

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

Mintakérdések a Számítógépes grafika és képfeldolgozás tárgy vizsgájára való felkészüléshez

Inkrementális képszintézis

84. A szem a koordináta rendszer origójában van és z irányba néz, a látószög x-ben és y-ban is 90 fokos, az első vágósík 0.1-en, a hátsó 2-n van. Adja meg azt a transzformációs mátrixot, amely a látható tartományt a [-1,-1,0], [1,1,1] sarokpontokkal definiált téglatestbe viszi át. Miért kell vágni a transzformáció végrehajtása előtt a z=0.1 síkra?

• Mivel nem volt megadva, feltételeztem, hogy (az OpenGL-lel ellentétben) a transzformáció előtt és után is jobbsodrású koordinátarendszerben vagyunk, a szem a pozitív z irányba néz, és a tartomány "állása" nem változik (vagyis pl. az elülső vágósík transzformálódik a z=0 síkba és a hátsó a z=1-be, stb.).
• A projektív transzformációk lényeges jellemzője, hogy melyik síkot viszik az ideális síkba. Minden transzformáció előállítható úgy, hogy először elvégzünk egy (nemnulla determinánsú, de azon kívül tetszőleges) projekciót, ami az ideális síkot a helyére rakja, majd ezután már csak affin transzformációkat végzünk.
• Itt tudjuk, hogy a szem, amit az ideális síkra akarunk elvinni, az origóban van. Valamint, az első és hátsó vágósíkok párhuzamosak maradnak, ezért a metszetük, a z=0, h=0 ideális egyenes is ideális marad. A sík, ami az "idealizálni" kívánt pontot és egyenest is tartalmazza, a z=0 sík, ezt visszük az ideális síkba. $\left[{\begin{array}{cccc}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{array}}\right]$ (x-et és y-t békén hagyjuk, z-t és h-t pedig kicseréljük, így lesz a z=0 síkból a h=0 ideális sík.)
• Ez a látható tartományt átviszi a (-1, -1, 10), (1, 1, 0.5) sarkú téglatestbe. Ezután csak z-t kell korrigálni, hogy a (10, 0.5) tartományból a (0, 1)-be menjen, erre megfelelő z'=z*(-1/9.5)+h*(10/9.5) (mivel most "rendes" pontokkal dolgozunk, és h=1-et használunk). Ezt az előző transzformáció után fűzve: $\left[{\begin{array}{cccc}1&0&0&0\\0&1&0&0\\0&0&10/9.5&1\\0&0&-1/9.5&0\end{array}}\right]$
• Azért kell vágni, mert a hátsó vágósík mögött lévő pontok furcsán viselkednek a transzformáció során. A negatív z-jű pontok átkerülnének a pozitív oldalra, és így "szem mögötti" dolgokat is kirajzolhatnánk, a z=0 pontok a végtelenbe kerülnének, a z=0 és hátsó vágósík közti pontok pedig nagy negatív z koordinátát kapnának.

85. Írja fel a festőalgoritmus pszeudokódját.

• Az algoritmus az egyik legprimitívebb megoldás arra, hogy egymást takaró objektumokat rajzoljunk ki. Egyszerűen sorbarendezi az objektumokat a képernyőtől való távolság szerint, és a legtávolabbitól kezdve rajzolja ki, így takarásnál a közelebbi felülírja a távolabbit. Már 3 téglalap esetén is van olyan elhelyezkedés, amit nem tud jól kirajzolni.
• A pszeudokódja nagyon egyszerű: az objektumokat rendezetten beszúrja egy listába, majd rajzoláskor a lista elemeit sorban rajzolja ki.
• Wikipédia: festőalgoritmus

86. Írja fel a Warnock algoritmus pszeudokódját.

• Az algoritmus szintén egymást takaró objektumok kirajzolására van. Lényege, hogy két esetben nagyon egyszerű a rajzolást elvégezni: ha csak egy objektumunk van (ekkor kirajzoljuk és kész), illetve ha csak egy pixelnyi területre rajzolunk (ekkor egyértelmű, milyen sorrendben vannak az objektumok). Ha egyik sem teljesül, akkor a rajzolandó területet felbonthatjuk részekre, mindegyik rész-területről eldöntjük, mely objektumok tartoznak bele, és rekurzívan kirajzoljuk a részeket. Ha egy rész-területbe csak egy objektum (darabja) esik, akkor rajzolunk, ha nem, tovább bontunk, egészen addig, amíg az 1x1 pixelt el nem érjük. Felbontani általában 2x2 negyed-tégalapra szokás.

WarnockDraw(Rectangle area, Array objects) {
  if (area is 1x1)
	 objects.sortByDepthAtPixel(area.x, area.y);
	 objects[0].draw();
  else if (objects.size==1)
	 objects[0].draw();
  else
	 WarnockDraw(area.upperLeftQuarter(), objects.selectVisible(area.upperLeftQuarter()));
	 WarnockDraw(area.lowerLeftQuarter(), objects.selectVisible(area.lowerLeftQuarter()));
	 WarnockDraw(area.upperRightQuarter(), objects.selectVisible(area.upperRightQuarter()));
	 WarnockDraw(area.lowerRightQuarter(), objects.selectVisible(area.lowerRightQuarter()));
}

• Wikipédia: Warnock algoritmus

87. Írjon 3D háromszög megjelenítőt, amely a képernyőkoordináta rendszerbe transzformált csúcspontokat kapja meg, és a takaráshoz z-buffer algoritmust használ. A háromszöget konstans színnel kell kitölteni. Feltételezheti, hogy a vektor műveletek rendelkezésre állnak és azt is, hogy a háromszög vetületében a koordináták az alábbi relációban állnak.

Ezen a helyen volt linkelve a Clipboard02.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

• A z-buffer egy globális float zBuffer[][] tömb, a kisebb z értékű objektum van előrébb, a képernyőt a Color pixel[][] tömbbel lehet írni. Az elején kiszámítjuk (zInc), mennyivel kell az x növelésekor a z-t növelni (levezetést lásd az OpenGL, Cg rész 98. feladatánál), majd végigfutunk először az alsó majd a felső felén a háromszögnek.

void triangle(Vector v1, Vector v2, Vector v3, Color c) {
  int x=v1.x, y=v1.y;
  float z, zInc=(v1.z*(v2.y-v3.y)+v2.z*(v3.y-v1.y)+v3.z*(v1.y-v2.y));
  zInc=zInc/(v1.x*(v2.y-v3.y)+v2.x*(v3.y-v1.y)+v3.x*(v1.y-v2.y));
  int xStart, xEnd;
  for ( ; y<v2.y; y++) {
	 xStart=v1.x+(int)((float)(v2.x-v1.x)*(float)y/(float)(v2.y-v1.y));
	 xEnd=v1.x+(int)((float)(v3.x-v1.x)*(float)y/(float)(v3.y-v1.y));
	 z=(float)v1.z+(float)(v2.z-v1.z)*(float)y/(float)(v2.y-v1.y);
	 for (x=xStart; x<=xEnd; x++) {
		if (z<zBuffer[y][x]) pixel[y][x]=c;
		z+=zInc;
	 }
  }
  for ( ; y<v3.y; y++) {
	 xStart=v2.x+(int)((float)(v3.x-v2.x)*(float)y/(float)(v3.y-v2.y));
	 xEnd=v1.x+(int)((float)(v3.x-v1.x)*(float)y/(float)(v3.y-v1.y));
	 z=(float)v2.z+(float)(v3.z-v2.z)*(float)y/(float)(v3.y-v2.y);
	 for (x=xStart; x<=xEnd; x++) {
		if (z<zBuffer[y][x]) pixel[y][x]=c;
		z+=zInc;
	 }
  }
}

88. Phong árnyalás. Adja meg, hogy az egyes vektorok milyen koordinátarendszerben értendők.

89. Phong árnyalással jelenít meg egy háromszöget, amelynek csúcspontjai világ-koordinátarendszerben (6, 4, 0),(10, 4, 0),(6, 6, 0). A háromszög csúcsaihoz rendre a következő normálvektorokat rendeltük (1,0,0),(0,1,0),(0,0,1). A háromszög diffúz, a visszaverési együttható (1, 0.5, 0.5). Egyetlen irányfényforrás van, amely a (11, 5, 4) irányból világít (R=3,G=1,B=2) intenzitással. A szem a (5, 6, 7) pontban van. Milyen színű lesz RGB színrendszerben a háromszög (8,5,0) pontja (az eredményt egy értékes jegy pontossággal kérjük)?

• Phong árnyalásnál a normál-, megvilágítási, és nézeti vektort is lineárisan interpoláljuk (és az interpolált vektorokat persze normálni kell). Itt irányfényforrásunk van, tehát a megvilágítási vektor mindenhol ugyanaz, nem kell interpolálni, a felület pedig diffúz, tehát a BRDF-je nem függ a nézeti iránytól, a nézeti vektort sem kell interpolálni.
• Először előállítjuk a (8, 5, 0) pontot a csúcsok lineáris kombinációjaként, úgy, hogy az együtthatók összege 1 legyen. (8, 5, 0)=0*(6, 4, 0)+0.5*(10, 4, 0)+0.5*(6, 6, 0). Ugyanezekkel az együtthatókkal kell a normálvektorokat is kombinálni: 0*(1, 0, 0)+0.5*(0, 1, 0)+0.5*(0, 0, 1)=(0, 0.5, 0.5), ezt normálva: $(0,{\frac {1}{\sqrt {2}}},{\frac {1}{\sqrt {2}}})$
• A megvilágítási vektort normálva: $({\frac {11}{\sqrt {162}}},{\frac {5}{\sqrt {162}}},{\frac {4}{\sqrt {162}}})$, majd skalárisan szorozva a normállal: ${\frac {9}{\sqrt {324}}}=0.5=\cos \theta$ A Lambert-törvény alapján a kimenő sugársűrűség: $L_{ki}=L_{be}k_{d}\cos \theta$, ahol $k_{d}$ a visszaverési együttható osztva $\pi$-vel. Ezt kiszámolva mindegyik komponensre, a pixel színe: $({\frac {1.5}{\pi }},{\frac {0.25}{\pi }},{\frac {0.5}{\pi }})\approx (0.5,0.08,0.16)$
• Diffúz felület BRDF-je

90. Gouraud árnyalás. Milyen hardvertámogatás építhető hozzá?

• A Gouraud árnyalás a háromszögek csúcsaiban határozza meg a normálvektorok alapján a színt, majd a belső pontok színét ezek interpolációjával számítja (ellentétben a Phong árnyalással, ami a normálvektorokat interpolálja, és minden pixelt a normálvektor ismeretében külön árnyal). Egy háromszög pixeleinek színe emiatt lineárisan fogg függeni, az eredeti világkoordinátáitól, és a transzformációk utáni képernyőkoordinátáktól is. Tehát, ha a háromszög egy képernyő-sorba eső pixeleit rajzoljuk, azok színe a szomszédos pixelek közt mindig ugyanannyival változik, így ha előre kiszámítjuk ezt a növekményt, akkor a soron végiglépkedéskor mindig csak egy összeadást kell majd végrehajtanunk.
• Ezt egy regiszterrel és egy (lebegőpontos) összeadóval lehet megvalósítani. Az összeadó egyik bemenete az eltárolt szín-növekmény, a másik pedig egy regiszter, ami az előző szín-értéket tárolja. A kimenetét pedig ugyanebben a regiszterben tároljuk, és onnan rakjuk ki a kimenetre. Ha több komponensből áll a szín, akkor mindegyik komponensnek kell egy külön ilyen modul.
• A megvalósítás érdekessége, hogy mivel a színt ugyanúgy lehet soronként lineárisan számítani, mint a z-értéket vagy a textúrakoordinátákat, ezért egy ilyen hardveregység többféle műveletet is végezhet.
• Wikipédia: Gouraud árnyalás

91. Háromszög textúrázása inkrementális képszintézisben.

• Egy háromszög csúcsainak textúrakoordinátáival tulajdonképpen egy homogén lineáris transzformációt definiálunk, ami a tér pontjait a textúra pontjaira képezi. A háromszög rajzolásakor a képernyőkoordinátákból a textúra megfelelő pixelét egy ebből kiszámítható homogén lineáris transzformációval lehet megkapni.
• Ez annyiból kényelmetlen, hogy elvégzéséhez lebegőpontos osztást kellene végezni (a homogén koordinátákból a végén kiszámítani a tényleges kétdimenziós textúrakoordinátákat), ezért általában az osztást kihagyják, és a törtnek, ami a koordinátákat megadná, a nevezőjét elhagyják. Ez sokkal gyorsabbá teszi a számítást, mivel alkalmazható a z-értékek számításához is használt növekményes módszer (lásd 90. feladat), viszont torzul a megjelenített kép.
• Textúra leképzés diasor 5.-9. dia
• Wikipédia: perspektíva a textúrázásnál

92. Buckaleképzés. Elv, és cél, a buckák megadásának módja, Normálvektor számítása.

• A valódi tárgyak felszíne nem teljesen sima, apró egyenetlenségek vannak rajta. Ezek nagyon kicsik a tárgy méreteihez képest, de a felszín kinézetét mégis láthatóan befolyásolják. Nem modellezhetőek pontosan geometriailag, és a pontos kirajzolásukhoz durván meg kellene növelni a leírás bonyolultságát. Ezért egy közelítést alkalmazunk: a felületet az egyszerű geometriájú közelítésével írjuk le, és tároljuk, a valódi felület melyik pontja mennyire tér el a közelítéstől. A megjelenítésnél az egyszerű geometriát rajzoljuk fel, de az árnyalásnál, a normálok számításánál figyelembe vesszük az eltéréseket.
• Az eltéréseket kétféleképp lehet leírni. Tárolhatjuk, hogy az egyes pontok mennyivel vannak "magasabban" illetve "mélyebben" (a felületre merőleges irányban), mint ami a geometriából következne, vagy tárolhatjuk a megjelenítéshez használt, és a geometriából számított normál különbségét.
• A normál számításához mindkét esetben az egyszerű felülethez rögzített koordinátarendszert használjuk. Ha ${\underline {s}}(u,v)$ alakban van adva, akkor az első két tengely az u és v szerinti parciális derivált (vagyis két érintővektor), a harmadik pedig az eredeti normál. Ezeket rendre ${\underline {s}}_{u},\;{\underline {s}}_{v},\;{\underline {n}}_{s}$-sel jelöljük.
• Az első esetben legyen d(u, v) a buckák magasságát leíró térkép, $d_{u},\;d_{v}$ ennek parciális deriváltjai. Az eredő normál: ${\underline {n}}_{r}={\underline {n}}_{s}+d_{u}{\underline {n}}_{s}\times {\underline {s}}_{v}-d_{v}{\underline {n}}_{s}\times {\underline {s}}_{u}$. Általában ezt még normálni kell.
• Szirmay könyv 243.-244. oldal
• Wikipédia: buckaleképzés

93. Írjon egy C függvényt, amely egy 3D háromszöget az x=0 síkra vág. A függvény bemenete tehát három pont, kimenete pedig azon háromszögek tömbje és darabszáma, amelyek a kapott háromszögnek az x=0 sík feletti részét adják ki.

• Array egy tömb típus, add() egy elemet ad hozzá, inside() egy pontról mondja meg, hogy az x>0 félsíkban van-e (1, ha igen, 0, ha nem), intersect() egy szakasz és az x=0 sík metszéspontját adja meg. A type változó utolsó 3 bitjében tároljuk el, melyik pont melyik oldalon van, majd egy switch a 8 esetet külön lekezeli (ebből csak a lényegesen különböző 4 van leírva).

int inside(Point p) {
  return (p.x>0) ? 1 : 0;
}
Point intersect(Point p1, Point p2) {
  return p1+(p2-p1)*(-p1.x/(p2.x-p1.x));
}
Array clip(Point *p1, Point *p2, Point *p3) {
  Array ret=emptyArray;
  Point temp;
  int type;
  type=inside(p1)+2*inside(p2)+4*inside(p3);
  switch (type) {
	 case 0:
		break;
	 case 1:
		add(&ret, p1);
		temp=intersection(p1, p2);  add(&ret, &temp);
		temp=intersection(p3, p1);  add(&ret, &temp);
		break;
	 case 2: /* lásd case 1 */
	 case 3:
		add(&ret, p1);
		add(&ret, p2);
		temp=intersection(p2, p3);  add(&ret, &temp);
		temp=intersection(p3, p1);  add(&ret, &temp);
		break;
	 case 4: /* lásd case 1 */
	 case 5: /* lásd case 3 */
	 case 6: /* lásd case 3 */
	 case 7:
		add(&ret, p1);
		add(&ret, p2);
		add(&ret, p3);
		break;
  }
  return ret;
}

94. Implementálja a Sutherland-Hodgman poligonvágó algoritmust 3D-ben, Descartes koordinátákban megadott háromszögekre. A megvalósítandó C++ Vagas függvény bemenete a háromszögek száma a háromszögeket tartalmazó tömb (in), a vágási tartomány két sarka (Vector min, Vector max), kimenete (referenciaváltozó) pedig a vágott háromszögeket tartalmazó tömb (out). A tömb típus (Tomb) a következő műveletekkel kezelhető:

• Add( Haromszog h ): egy új háromszög tömbhöz vétele
• int Size( ): a tárolt háromszögek számának lekérdezése
• Elem(int i): az i. háromszög lekérése
• A háromszög típus a következő műveletekkel kezelhető:*
• Vector& P(int i): Az i. csúcs koordinátái,
• Vector& T(int i): Az i. csúcshoz tartozó uv textúrakoordináták
• A Vector-on az összeadás, skalárral szorzás műveletek már implementáltak. Ha a megoldás hasonló blokkokból áll, akkor elegendő egyetlen blokkot leírni, és szövegesen utalni arra, hogy a többiben mik lennének az eltérések. Segítség: a vágás során egy háromszögből négyszög is keletkezhet, amelyet két háromszögre kell bontani. Feltételezheti, hogy a Haromszog típus elbír 4 csúcspontot is.*

• A Vagas függvény a tartományt határoló összes síkkal meghívja a sikraVagTombot függvényt. A sikraVagTombot minden háromszögre külön meghívja a sikraVagHaromszoget függvényt, visszatérési értékként megkapja, háromszög vagy négyszög lett-e az eredmény (utóbbi esetben szétvágja két háromszögre). A sikraVagHaromszoget végigmegy a háromszög élein, és a Sutherland-Hodgman algoritmus alapján pontokat adogat a kimeneti sokszöghöz, ehhez felhasználja az inside és intersectCoeff függvényeket. Előbbi megmondja, egy p kezdőpontó, d irányvektorú síknak a "jó" oldalán van-e egy pont, utóbbi a metszéspont számításához szükséges együtthatót számolja.

bool inside(Vector p, Vector d, Vector v) {
  if ((v-p)*d>0) return true;
  return false;
}

float intersectCoeff(Vector p, Vector d, Vector v1, Vector v2) {
  return ((v2-p)*d)/((v2-v1)*d);
}

bool sikraVagHaromszoget(Vector p, Vector d, Haromszog in, Haromszog& out) {
  int outIndex=0;
  bool previousInside=inside(p, d, in.P(2)), currentInside;
  for (int i=0; i<3; i++) {
	 currentInside=inside(p, d, in.P(i));
	 if (currentInside && previousInside) {
		out.P(outIndex)=in.P(i);
		out.T(outIndex)=in.T(i);
		outIndex++;
	 } else if (currentInside && !previousInside) {
		float c=intersectCoeff(p, d, in.P((i-1+3)%3), in.P(i));
		out.P(outIndex)=in.P((i-1+3)%3)*c+in.P(i)*(1-c);
		out.T(outIndex)=in.T((i-1+3)%3)*c+in.T(i)*(1-c);
		outIndex++;
		out.P(outIndex)=in.P(i);
		out.T(outIndex)=in.T(i);
		outIndex++;
	 } else if (!currentInside && previousInside) {
		out.P(outIndex)=in.P((i-1+3)%3)*c+in.P(i)*(1-c);
		out.T(outIndex)=in.T((i-1+3)%3)*c+in.T(i)*(1-c);
		outIndex++;
	 }
  }
  if (outIndex>2) return true;
  return false;
}

void sikraVagTombot(Vector p, Vector d, Tomb in, Tomb& out) {
  Haromszog h;
  for (int i=0; i<in.Size(); i++) {
	 bool negyszog=sikraVagHaromszoget(p, d, in.Elem(i), &h);
	 if (negyszog) {
		Haromszog h1;
		h1.P(0)=h.P(0);
		h1.P(1)=h.P(1);
		h1.P(2)=h.P(2);
		h1.T(0)=h.T(0);
		h1.T(1)=h.T(1);
		h1.T(2)=h.T(2);
		out.Add(h1);
		h1.P(0)=h.P(2);
		h1.P(1)=h.P(3);
		h1.P(2)=h.P(0);
		h1.T(0)=h.T(2);
		h1.T(1)=h.T(3);
		h1.T(2)=h.T(0);
		out.Add(h1);
	 } else out.Add(h);
  }
}

void Vagas(Vector min, Vector max, Tomb in, Tomb& out) {
  Tomb temp;
  sikraVagTombot(min, Vector(1, 0, 0), in, &temp);
  in=temp;
  sikraVagTombot(min, Vector(0, 1, 0), in, &temp);
  in=temp;
  sikraVagTombot(min, Vector(0, 0, 1), in, &temp);
  in=temp;
  sikraVagTombot(max, Vector(-1, 0, 0), in, &temp);
  in=temp;
  sikraVagTombot(max, Vector(0, -1, 0), in, &temp);
  in=temp;
  sikraVagTombot(max, Vector(0, 0, -1), in, &temp);
  out=temp;
}

-- G - 2008.12.26.