Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|GrafikaGyakorloInkrementalisKepszintezis}} ===Mintakérdések a Számítógépes grafika és képfeldolgozás tárgy vizsgájára való felk…”

2012-10-21T19:58:49Z

Új oldal, tartalma: „{{GlobalTemplate|Infoalap|GrafikaGyakorloInkrementalisKepszintezis}} ===Mintakérdések a Számítógépes grafika és képfeldolgozás tárgy vizsgájára való felk…”

Új lap

{{GlobalTemplate|Infoalap|GrafikaGyakorloInkrementalisKepszintezis}}

===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. <math> \left[\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}\right] </math> (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: <math> \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] </math>
* 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.
* [http://en.wikipedia.org/wiki/Painter%27s_algorithm 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.
<pre>
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()));
}
</pre>
* [http://en.wikipedia.org/wiki/Warnock_algorithm 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.'''

{{InLineImageLink|Infoalap|GrafikaGyakorloInkrementalisKepszintezis|Clipboard02.png}}

* 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.
<pre>
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;
}
}
}
</pre>

'''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: <math> (0, \frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}) </math>
* A megvilágítási vektort normálva: <math> (\frac{11}{\sqrt{162}}, \frac{5}{\sqrt{162}}, \frac{4}{\sqrt{162}}) </math>, majd skalárisan szorozva a normállal: <math> \frac{9}{\sqrt{324}}=0.5=\cos\theta </math> A Lambert-törvény alapján a kimenő sugársűrűség: <math> L_{ki}=L_{be}k_d\cos\theta </math>, ahol <math> k_d </math> a visszaverési együttható osztva <math> \pi </math>-vel. Ezt kiszámolva mindegyik komponensre, a pixel színe: <math> (\frac{1.5}{\pi}, \frac{0.25}{\pi}, \frac{0.5}{\pi}) \approx (0.5, 0.08, 0.16) </math>
* [http://www.cs.cmu.edu/afs/cs/academic/class/16823-f06/appearance-modeling-5.ppt 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.
* [http://en.wikipedia.org/wiki/Gouraud_shading 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
* [http://en.wikipedia.org/wiki/Texture_mapping#Perspective_correctness 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 <math> \underline{s}(u, v) </math> 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 <math> \underline{s}_u,\; \underline{s}_v,\; \underline{n}_s </math>-sel jelöljük.
* Az első esetben legyen d(u, v) a buckák magasságát leíró térkép, <math> d_u,\; d_v </math> ennek parciális deriváltjai. Az eredő normál: <math> \underline{n}_r=\underline{n}_s + d_u \underline{n}_s \times \underline{s}_v - d_v \underline{n}_s \times \underline{s}_u </math>. Általában ezt még normálni kell.
* Szirmay könyv 243.-244. oldal
* [http://en.wikipedia.org/wiki/Bump_mapping 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).
<pre>
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;
}
</pre>

'''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.
<pre>
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;
}
</pre>

-- [[KisGergelyG|G]] - 2008.12.26.

[[Category:Infoalap]]

GrafikaGyakorloInkrementalisKepszintezis - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|GrafikaGyakorloInkrementalisKepszintezis}} ===Mintakérdések a Számítógépes grafika és képfeldolgozás tárgy vizsgájára való felk…”