2006. 06. 20. (keresztféléves vizsga!)

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.

1.) Feladat

3D szakaszok vágása homogén koordinátákban. Vágási tartomány = 1p, szakasz egyenlete homogén koordinátákban = 1p, metszésszámítás = 1p, vágási algoritmus = 2p.

Vágási tartomány: $-h<=X_{h}<=h,-h<=Y_{h}<=h,-h<=Z_{h}<=h,h>0$

Szakasz egyenlete:
$x(t)=t*x_{0}+(1-t)*x_{1}$
$y(t)=t*y_{0}+(1-t)*y_{1}$
$z(t)=t*z_{0}+(1-t)*z_{1}$
$h(t)=t*h_{0}+(1-t)*h_{1}$

Metszésszámítás: megoldjuk a következő egyenleteket. $x(t)=h(t),y(t)=h(t),z(t)=h(t)$

Cohen-Sutherland vágási algoritmus:
Jelöljük a térrészeket 6-6 bittel, a bit 0 ha a kijelölt kockán belül vagyunk, 1 ha kívül. (tk. 199)

C1 = P1 kódja
C2 = P2 kódja
int f;

while(true) {
  if( C1 == 0 && C2 == 0 ) return true;  //triviális elfogadás, mindkét pont belül van
  if( C1 & C2 != 0 ) return false;		 //triviális elutasítás, mindkét pont kívül van

  if( C1>>5 ^ C2>>5 ) {
	 f = 5;
  }
  else if( C1>>4 ^ C2>>4 ) {
	 f = 4;
  }
  ...
  else {
	 f = 0;
  }

  P = intersect(P1, P2, f);  //metszéspont a (6-f). síkkal
  C = P kódja

  if( C1>>f == 1 ) {
	 P1 = P;
	 C1 = C;
  } else {
	 P2 = P;
	 C2 = C;
  }
}

2.) Feladat

Egy játék karakterének aktuális állapotát két tömb írja le. Az első tömb a háromszögek csúcsainak indexeit tartalmazza (egymás utáni három egész egy-egy háromszög három csúcsának indexe). A másik tömb a csúcsokat tartalmazza. A csúcstömb elemei struktúrák, amelyek az x,y,z koordinátákat foglalják magukban.
A karakter [vx,vy,vz] sebességgel mozog. Egy lövedék érkezik az adott Dt hosszú időkeret elején az [X,Y,Z] pontba [VX,VY,VZ] sebességgel. Írjon FOLYTONOS ÜTKÖZÉS-DETEKTÁLÓ függvényt, amely eldönti, hogy ebben a keretben a lövedék eltalálja-e a karaktert. Feltételezheti, hogy a karakter modellje topológiailag helyes, és hogy a lövedék a keret elején még a karakteren kívül van. Az implementációban feltételezheti, hogy a vektorokra az összeadás(+), kivonás(-), skaláris és skalárral való szorzás(*), valamint a vektoriális szorzás(%) rendelkezésre állnak.

Elv = 1p, Képletek = 2p, C implementáció = 2p

Elv: amennyiben egy 3D alakzat topológiailag helyes (azaz értelmezhető a térfogata), akkor úgy tudjuk megállapítani hogy a belsejében vagyunk-e hogy az adott pontból egy sugarat indítunk (ez esetben a lövedék sebességével ellentétes irányba célszerű). Számoljuk a sugár testtel való metszéspontjait, és ha páratlan metszést találunk akkor a testen belül, ha párosat akkor azon kívül van a lövedék. (Ehhez még fel kell tenni azt hogy a keretek kellően kis időközönként követik egymást, különben előfordulhat hogy a lövedék pl. átugorja a játékos karját)

Annyit tennék hozzá, hogy a folytonos ütközés-detektálás pontosan azt jelenti, hogy nem számít, milyen időközönként vizsgáljuk az ütközést. Bonyolultan szólva tehát a feladat az, hogy megvizsgáljuk, hogy a keret elején lévő golyópozíciót a keret végén lévő golyópozícióval való összekötésből adódó szakasznak van-e pontja, mely a testen belül halad. Ez elbonyolítás, mert ha topológiailag helyes, akkor a golyó - amiről tudjuk, hogy a keret elején nincsen benne a testben - sebességvektora metsz egyetlen háromszöget is, akkor biztosan lesz olyan időpillanat (most vegyük úgy egyelőre, hogy a karakter nem mozog), amikor a test belsejében van a golyó a keret eleje és vége közt eltelt időben. Ha a karomat háromszögekkel közelítem és bármelyiket metszi a golyó útja a keret eleje és vége közt, akkor bizony vérezni fogok hiába metszett páros számszor a golyó. Problémát jelenthet továbbá az, hogy a karakter is mozog. Ez nem hagyható figyelmen kívül pélául akkor mikor Neo a golyók sebességének nagyságrendjébe eső gyorsasággal hajolgat el. Ha az ő mozgását nem lelassítva figyelnénk (a kulcskeret jóval hosszabb lenne mint a film lassított jelenete) és figyelmen kívül hagynánk a mozgását, akkor simán szétlőte volna Smith ügynök. A golyóra van három paraméteres egyenletünk (ilyesmi alakúak: x=X+VX*t), egy háromszögre pontjai pedig egy sík egyenletét adja, ezt úgy kéne megkonstruálni, hogy a sík egyenlete függjön az időtől is. A háromszög 3 pontja mozgásban: P1=p1+(xv,yv,zv)*t, P2=p2+(xv,yv,zv)*t, P3=p3+(xv,yv,zv)*t. Innen felírható, hogy N=(P2-P1)X(P3-P1)/|(P2-P1)X(P3-P1) és hogy P1*N=0 ami pedig a sík egyenlete. Van tehát 4 ismeretlenünk és 4 egyenlet. Ebből adódik az ütközés helye és ideje ha egyáltalán van ilyen (nyilván le kell vizsgálni, hogy valóban a háromszög belsejében van a metszéspont). Ezt minden háromszögre el kell végezni és tehát ha bármelyikre is adódik egy metszéspont, akkor ott ütközés volt. Megj: ez itt most O(n) lépésszám, de pl egy karakter-karakter ütközésnél O(n*n) lenne, ezért szoktak trükközni, hogy mondjuk csak a befoglaló téglatesteket/ellipszoidokat ütköztetik -- FodorBálint - 2008.01.02.

3.) Feladat

Mit csinál a grafikus kártya a pixelárnyalóban és az után? Hogyan változik a működés a következők hatására?

glEnable/Disable(GL_TEXTURE_2D)
glEnable/Disable(GL_DEPTH_TEST)
glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_REPLACE)
glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_MODULATE)
glEnable/Disable(GL_LIGHTING)
glEnable/Disable(GL_BLEND)

Megoldás:
=glEnable/Disable(GL_TEXTURE_2D)=
Ki/be kapcsolja a textúrázást, a pixelárnyalóban a pixel színébe beleszól a textúra adott színe is.
=glEnable/Disable(GL_DEPTH_TEST)=
Mélységteszt, ha be van kapcsolva akkor a pixelárnyalóban csak akkor íródik felül az aktuális pixel, ha a z-buffer értékénél kisebb a most számolt "pixel távolsága". Aki írt már pixel shadert az tudja, hogy a vertex shader-ben transzformált (modell és projekciós) pontokat úgy kapja meg a pixel shader, hogy megkapja a pont mélységét is. Ez azért van így mert innen lehet eldönteni, hogy az adott pixelt rajzoljuk-e (volt-e már közelebbi pont beírva a z-bufferbe) vagy sem. Nem tudom, hogy teljesen korrket-e ez a leírás FIXME.
=glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_REPLACE)=
Ennek akkor van értelme, ha textúrázunk, mert ilyenkor a glColor függvénnyel beállított szín felül fog íródni a textúra színével.
=glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_MODULATE)=
Ennek akkor van értelme, ha textúrázunk, mert ilyenkor pixel színe (anyag színe + fényezés) össze fog szorzódni a textúra színével
=glEnable/Disable(GL_LIGHTING)=
Fényezés ki/be.
=glEnable/Disable(GL_BLEND)=
Átlátszóság ki/be.
-- FodorBálint - 2008.01.03.

4.) Feladat

Egy affin modellezési transzformáció a [0,0,0],[1,1,1] AABB sarkaival a következőt teszi: A [0,0,0] sarkot a [2,3,4] pontba viszi át, a [1,0,0] sarkot a [6,5,5] pontba viszi át, a [1,1,0] sarkot a [3,6,5] pontba viszi át, a [1,1,1] sarkot a [7,8,9] pontba viszi át. Írja fel a transzformációt! Miért fontos az a kitétel, hogy a trafó affin(1p)? A trafó kiszámítása (3p). Egy korábbitól eltérő másik transzformációs mátrix megadása (1p).

AABB: Axis Aligned Bounding Box, koordinátatengelyekkel párhuzamos élű befoglaló téglatest (Sünis könyv 350. o.: Az ütközésszámítás gyorsítása)
Affin transzformáció: lineáris transzformáció + eltolás, homogén koordinátás alak esetén egy 4x4es mátrix-szal fejezhető ki:

$M=\left[{\begin{array}{rrrr}a_{11}&amp;a_{12}&amp;a_{13}&amp;0\\a_{21}&amp;a_{22}&amp;a_{23}&amp;0\\a_{31}&amp;a_{32}&amp;a_{33}&amp;0\\p_{1}&amp;p_{2}&amp;p_{3}&amp;1\\\end{array}}\right]$

ahol $a_{ij}$-k a lineáris transzformációt, $p_{i}$-k az eltolást jelentik.
A pontokat homogén koordinátás alakban felírva kapunk néhány egyenletet:

$[0,0,0,1]\cdot M=[2,3,4,1]$
$[1,0,0,1]\cdot M=[6,5,5,1]$
$[1,1,0,1]\cdot M=[3,6,5,1]$
$[1,1,1,1]\cdot M=[7,8,9,1]$

Azért fontos, hogy a transzformáció affin, mert így a mátrixban csak 12 ismeretlen van, és mivel a 4 pontból 4*3 = 12 egyenletet tudunk felírni, így megoldható az egyenletrendszer.

$[0,0,0,1]\cdot M=[p_{1},p_{2},p_{3},1]=[2,3,4,1]$ ebből $p_{1}=2,p_{2}=3,p_{3}=4$
$[1,0,0,1]\cdot M=[a_{11}+p_{1},a_{12}+p_{2},a_{13}+p_{3},1]$ ebből $a_{11}=4,a_{12}=2,a_{13}=1$
$[1,1,0,1]\cdot M=[a_{11}+a_{21}+p_{1},a_{12}+a_{22}+p_{2},a_{13}+a_{32}+p_{3},1]$ ebből $a_{21}=-3,a_{22}=1,a_{23}=0$
$[1,1,1,1]\cdot M=[a_{11}+a_{21}+a_{31}+p_{1},a_{12}+a_{22}+a_{32}+p_{2},a_{13}+a_{23}+a_{33}+p_{3},1]$ ebből $a_{31}=4,a_{32}=2,a_{33}=4$

Megvan tehát a transzformációs mátrix összes eleme:

$M=\left[{\begin{array}{rrrr}4&amp;2&amp;1&amp;0\\-3&amp;1&amp;0&amp;0\\4&amp;2&amp;4&amp;0\\2&amp;3&amp;4&amp;1\\\end{array}}\right]$

Most már csak az a kérdés, hogy hogyan lehet egy korábbitól eltérő másik transzformációs mátrix megadni?

Ez egy homogen transzformacio. Ha a matrixot megszorozzuk 2-vel, akkor (a,b,c,d) helyett (2a,2b,2c,2d) pontot fogjuk kapni, ami ugyanaz a projektiv terben. Tehat a kapott matrixot tetszoleges konstanssal szorozva ekvivalens trafo-t kapunk.

Például: $M^{'}=2\cdot M=\left[{\begin{array}{rrrr}8&amp;4&amp;2&amp;0\\-6&amp;2&amp;0&amp;0\\8&amp;4&amp;8&amp;0\\4&amp;6&amp;8&amp;2\\\end{array}}\right]$

-- pluhi - 2007.01.12.
-- Geri - 2007.01.12.
-- Csapszi - 2007.01.15.