GrafikaGyakorloSugarkovetes

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

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

Sugárkövetés

75. Írja le azon inkrementális algoritmus elvét (ötlet + képletek), amely egy 3D szabályos rács azon celláit kiírja, amelyet egy adott sugár metsz.

• Ha a sugár az aktuális cellába az [math] r_0=(x_0, y_0, z_0) [/math] pontban lépett be (vagy onnan indul), az irányvektora [math] r_d=(x_d, y_d, z_d) [/math], és a cellahatárok az x=kc, y=kc, z=kc síkok (ahol k egész), akkor azt kell megvizsgálni, hogy az xy, yz vagy xz irányú rácssíkkal lesz-e az első metszés, és ennek megfelelően kell új cellába lépni és új kiindulópontot választani. Felteszem, hogy xd, yd és zd is nemnegatívak (a többi eset hasonló módon kezelhető, csak pár előjelet kell változtatni).
• Az x=kc síkot a [math] t=\frac{kc-x}{x_d} [/math] paraméterértéknél metszi a sugár (a sugár paraméteres egyenlete: [math] r(t)=r_0+r_d t,\; t > 0 [/math]), a legkisebb k, amire ez pozitív (vagyis a legközelebbi sík, amit a kezdőpont után metsz) x/c+1 alsó egész része, így [math] t=\frac{1}{x_d}\left\lfloor\frac{x}{c}+1\right\rfloor [/math] Ez, és a másik két síkra kiszámolt t-k közül kiválasztjuk a legkisebbet, kiszámoljuk a metszéspontot, ami az új cellában a kezdőpont lesz, és pl. ha az xz síkot metszettük először, akkor y irányban lépünk új cellába.

76. Írjon sugár és kvadratikus felület (a kvadratikus felület implicit egyenlete egy kvadratikus alak) metszési eljárást egy sugárkövető algoritmushoz. Bemenet: sugár kezdőpontja, irányvektora, a kvadratikus alak 4x4-es mátrixa.

• A kvadratikus felület egyenlete: [math] \underline{r}A\underline{r}^T=0 [/math] a sugáré: [math] \underline{r}=\underline{a}+\underline{d}t [/math] ahol t pozitív valós paraméter. A két egyenletet kombinálva: [math] (\underline{a}+\underline{d}t)A(\underline{a}+\underline{d}t)^T=0 [/math] Felhasználva a mátrixszorzás linearitását, felbonthatjuk a zárójeleket, és t hatványai szerint rendezhetünk: [math] (\underline{a}A\underline{a}^T) + (\underline{a}A\underline{d}^T + \underline{d}A\underline{a}^T)t + (\underline{d}A\underline{d}^T)t^2=0 [/math] Ennek a másodfokú egyenletnek a legkisebb pozitív valós gyökéből (ha van ilyen) számítható a sugár egyenletébe visszahelyettesítve az első metszéspont.

77. Kd-fa. A fa szerkezete, jelentése. A fa felépítésének algoritmusa. A fa bejárása, ha egy sugár által metszett cellákat szeretnénk meglátogatni a sugár kezdőpontjától mért távolság sorrendjében.

78. Írjon sugárkövető programot, amely pontszerű fényforrások által megvilágított diffúz gömböket tud megjeleníteni. A szem a 0,0,0 pontban van, a z irányba néz. Az ablak közepe a 0,0,1 pontban van, a z irányra merőleges, mérete 2x2. Az képernyő felbontása 1000x1000 pixel. Feltételezheti, hogy a 3d vektort és RGB színt megvalósító típusok rendelkezésre állnak, rájuk a szokásos operátorok működnek.

79. Octree felépítése és bejárása sugárkövetés során.

• Az octree is a sugárkövetés gyorsítására használt térpartícionáló módszer. Kiindulunk a színtér bennfoglaló téglatestjéből, és ha túl sok az objektum, mindhárom tengely mentén elfelezzük, összesen 8 cellára. Azokat a cellákat, ahol még mindig túl sok az objektum, hasonlóan osztjuk tovább. Bejárása a kd-fához hasonlóan (lásd 80. feladat) történik.
• Megjegyzés: létezik egy kicsit adaptívabb variáns is, ahol nem mindig felezünk a koordináták mentén, hanem kiválasztunk egy "középpontot", amin a három osztósík átmegy. A "középpont" kiválasztása hasonlóan problémás, mint a kd-fánál.

80. BSP-fa (kd-fa) felépítése és bejárása sugárkövetés során.

• Sugárkövetésnél nagyon sok számítás egy sugarat minden objektummal ütköztetni (hogy eldöntsük, melyiket metszi először), még azokkal is, amikkel "nyilvánvalóan" nem ütközhet, mert "túl messze" vannak. Erre egy megoldás valamilyen térpartícionáló módszer: a színteret valahogyan cellákra osztjuk, és meghatározzuk, melyik objektum melyikbe "lóg bele". Minden sugárnál a kezdőpontból indulunk, megnézzük, melyik cellába ér először, és ütköztetjük az abba belógó objektumokkal; ha nincs ütközés, továbbmegyünk a következő cellába, amit a sugár meglátogat. A struktúrát felépíteni (amíg az objektumok nem változnak) csak egyszer kell, a sugarak követésének ideje pedig lényegesen csökkenhet.
• A BSP-fa úgy keletkezik, hogy a teret, ha "sok" dolog van benne, kétfelé osztjuk, lehetőleg úgy, hogy kb. fele-fele arányban kerüljenek a két térfélre az objektumok, majd a két térfélre ezt rekurzívan ismételgetjük. A kd-fánál van egy plusz megkötés: csak a koordinátasíkokkal párhuzamos síkokat használunk a felosztáshoz (általában ciklikusan, azaz az első szinten xy irányú, utána yz, xz, stb.). A cellák koordinátákkal párhuzamos oldalú téglatestek, így egyszerű eldönteni, melyik objektum melyik cellába lóg bele. Felépítésnél fontos és nehéz probléma, hogy hol legyen az osztósík; elvileg az adja a legjobb eredményt, ha az összfelület egyenlő a két oldalon (de ezt meg lassú kiszámolni).
• Bejárásnál a cellák változó mérete és helye miatt nincs egyszerű képlet arra, adott cella után melyik következik. Általában meghatározzák a kilépési pontot a cellahatáron, majd "mennek még egy kicsit" a sugár mentén, és a kapott pontról a fa alapján eldöntik, melyik cellában van. Gyorsítható a dolog, ha a keresés nem a fa gyökerétől indul, hanem az elhagyott cellától először fölfele, amíg nem talál egy, a pontot tartalmazó cellát, majd onnan lefele (ha sok szintje van a fának, akkor ez kevesebb lépés lehet, ugyanis a közeli cellák gyakran a fában is közel vannak).
• Wikipédia: BSP-fa
• Wikipédia: kd-fa

81. Reguláris térháló felépítése és bejárása sugárkövetés során.

82. A 2D síkon élők (Laposföld) lakói is sugárkövető programra vágynak. Segítsen nekik! A laposföldieknél a kamera mindig a koordinátarendszer origójában van, és az x irányba néz. A látószög 90 fokos. Az ablak a szemtől egységnyi távolságban van, a felbontása 100. Laposföldön a nap irányfénynek tekinthető, amelyet a (-1, 1) irányba tekintve érzékelünk, csak 350 nm-en sugároz, mégpedig egységnyi intenzitással. Laposföldön n darab kör található, amelyeket középpontjával és sugarával adunk meg. A tárgyak diffúzak, az i. gömb diffúz visszaverődési tényezője 350 nm-en éppen i. A laposföldi monitor csak 350 nm-en sugároz, a j. pixel intenzitását a SetPixel(j, intenzitás) függvénnyel lehet beállítani. Készítse el a laposföldi sugárkövető programot C++ nyelven!

• Scene osztály tárolja a színteret, display függvénye végigfut a 100 pixelen, és mindegyiknek a középpontján át lő egy origóból kiinduló sugarat. A trace függvény megkeresi a sugár első metszéspontját, kiszámítja a napfény járulékát (ha a nap felé menő sugár nem ütközik akadályba), majd rekurzívan meghívja magát a visszavert sugárra.
• Megjegyzés: a függvények source paramétere az tárolja, melyik objektumtól jött a sugár. Ennek hiányában a visszavert sugár (a számítási pontatlanságok miatt) esetleg ugyanazt az objektumot metszené, mint amiről az előbb visszaverődött. Egyébként kíváncsi vagyok, hogy hogy fogják a kétdimenziós kódomat elolvasni a laposföldiek...

class Scene {
  Array<Circle> circles;
  Vector sun(-1, 1);
  void display() {
	 for (int i=0; i<100; i++) {
		setPixel(i, trace(Vector(0, 0), Vector(1, -1+0.01*(float)(2*i+1)), -1, 10));
	 }
  }
  float trace(Vector start, Vector dir, int source, int maxDepth) {
	 int circle, c2;
	 float color=0;
	 Vector intersection, i2, reflected;
	 if (!firstIntersection(start, dir, source, &circle, &intersection)) return 0;
	 if (!firstIntersection(intersection, sun, circle, &c2, &i2)) color+=1*brdf(circle, intersection, sun);
	 reflected=reflect(circle, intersection, dir);
	 if (maxDepth>0) color+=trace(intersection, reflected, circle, maxDepth-1)*brdf(circle, intersection, reflected);
	 return color;
  }
  bool firstIntersection(Vector start, Vector dir, int source, int* circle, Vector* intersection) {
	 float tMin=FLOAT_MAX, t;
	 bool ret=false;
	 for (int i=0; i<circles.size(); i++) {
		if (i!=source && intersect(start, dir, *circle, &t, intersection) && t<tMin && ) {
		  tMin=t;
		  (*obj)=i;
		  ret=true;
		}
	 }
	 return ret;
  }
  bool intersect(Vector start, Vector dir, int circle, float* t, Vector* intersection) {
	 Vector center=circles[circle].center-start;
	 float r=circles[circle].r;
	 float p=(dir*center)/(dir*dir), q=(center*center-r*r)/(dir*dir);
	 if (p*p<q) return false;
	 if (p-sqrt(p*p-q)>0) {
		(*intersection)=start+dir*(p-sqrt(p*p-q));
		return true;
	 } else if (p+sqrt(p*p-q)>0) {
		(*intersection)=start+dir*(p+sqrt(p*p-q));
		return true;
	 } else return false;
  }
  Vector reflect(int circle, Vector intersection, Vector dir) {
	 Vector normal=(intersection-circles[circle].center).normalize();
	 return dir-(2*normal*dir)*normal;
  }
  float brdf(int circle, Vector intersection, Vector dir) {
	 Vector normal=(intersection-circles[circle].center).normalize();
	 float cosTheta=normal*dir.normalize();
	 return (cosTheta>0 ? cosTheta : 0);
  }
};

83. Írjon sugár háromszög metszéspontszámító függvényt C++-ban. A sugarat a kezdőpontjának helyvektorával, és irányvektorával adjuk meg. A háromszöget a három csúcsának helyvektorával adjuk meg.

• Ki kell számítani a sugár egyenesének és a háromszög síkjának metszéspontját. Ezután még azt kell leellenőrizni, hogy a sugár a kezdőpontja után metssze a síkot (vagyis a metszésponthoz tartozó paraméterérték pozitív legyen) és a metszéspont a háromszög belsejében legyen.

bool intersect(Ray ray, Triangle triangle, Vector& intersection) {
  Vector normal=(triangle.v2-triangle.v1)%(triangle.v3-triangle.v1);
  float t=((triangle.v1-ray.start)*normal)/(ray.direction*normal);
  if (t<=0) return false;
  intersection=ray.start+ray.direction*t;
  if (((v2-v1)%(intersection-v1))*normal>0) return false;
  if (((v3-v2)%(intersection-v2))*normal>0) return false;
  if (((v1-v3)%(intersection-v3))*normal>0) return false;
  return true;
}

• Sugárkövetés diasor 9. dia

-- G - 2008.12.26.