A grafkerdes.doc feladatai
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
Letöltés itt: grafkerdes.doc
Megjegyzés: elkezdtem tömörebben formázva, témakörökre vágva beírni a feladatokat, itt:
- Gyakorlófeladatok: analitikus geometria
- Gyakorlófeladatok: geometriai modellezés
- Gyakorlófeladatok: 2D képszintézis
- Gyakorlófeladatok: illumináció
- Gyakorlófeladatok: sugárkövetés
- Gyakorlófeladatok: inkrementális képszintézis
- Gyakorlófeladatok: OpenGL, Cg nyelv
- Gyakorlófeladatok: globális illumináció
- Gyakorlófeladatok: térfogat vizualizáció
- Gyakorlófeladatok: animáció
- Gyakorlófeladatok: fraktálok
Az itt lévő kidolgozásokat letisztázva majd áttöltöm az új lapokra, és itt csak az al-lapokra mutató linkek maradnak. -- G - 2008.12.25.
Tartalomjegyzék
Analitikus geometria
1. feladat
Írja fel azon művelet mátrixát, amely egy ax+by+cz+d=0 egyenletű síkra merőlegesen vetít.
Megoldás
[math] T = \underline{v} - (\underline{v}\cdot\underline{n})\cdot\underline{n} = \left[\begin{array}{cccc} 1-a^2 & -a\cdot b & -a \cdot c & 0\\ -a \cdot b & 1-b^2 & -b \cdot c & 0\\ -a \cdot c & -b \cdot c & 1-c^2 & 0 \\ 0 & 0 & 0 & d \end{array} \right] [/math]
Nem tudom, hogy a fenti megoldás hogyan jött ki, én a következőt kaptam:
A sík normálvektora: [math]\underline{n} = (a, b, c)[/math],
[math]\underline{p}[/math] a pont, amit vetíteni akarunk.
írjuk fel a [math]\underline{p}[/math] pontból induló síkra merőleges egyenes egyenletét: [math]\underline{p}- q\underline{n}[/math]
Megkaphatjuk a sík és az egyenes metszéspontját, ha a következő egyenletet megoldjuk [math]q[/math]-ra: [math]a(p_{x}-qa)+b(p_{y}-qb)+c(p_{z}-qc)+d=0[/math]
Majd a [math]q[/math]-t visszaírva az egyenes egyenletébe megkaphatjuk a metszéspontot.
Most, hogy megvan a [math]q[/math], hogyan írjuk fel a vetítés mátrixát?
Tudjuk, hogy: [math](p_{x}, p_{y}, p_{z}, 1)*\underline{\underline{T}} = (p_{x}-qa, p_{y}-qb, p_{z}-qc, 1)[/math]
Most már csak ki kell találni a mátrix elemeit, hogy az egyenlet két oldala megegyezzen.
[math] T = \left[\begin{array}{cccc} 1-\frac{a^2}{(a^2 + b^2 + c^2)} & \frac{-a\cdot b}{(a^2 + b^2 + c^2)} & \frac{-a \cdot c}{(a^2 + b^2 + c^2)} & 0\\ \frac{-a \cdot b}{(a^2 + b^2 + c^2)} & 1-\frac{b^2}{(a^2 + b^2 + c^2)} & \frac{-b \cdot c}{(a^2 + b^2 + c^2)} & 0\\ \frac{-a \cdot c}{(a^2 + b^2 + c^2)} & \frac{-b \cdot c}{(a^2 + b^2 + c^2)} & 1-\frac{c^2}{(a^2 + b^2 + c^2)} & 0 \\ \frac{-ad}{(a^2 + b^2 + c^2)} & \frac{-bd}{(a^2 + b^2 + c^2)} & \frac{-cd}{(a^2 + b^2 + c^2)} & 1 \end{array} \right] [/math]
Ha valaki tudja, hogy esetleg miért nem jó ez a megoldás, akkor írja meg ide, thx. -- Pálesz - 2007.10.27.
A Pálesz-mátrix elemeiben az [math]a^2+b^2+c^2[/math] nevező elhagyható, ugyanis ez megegyezik az [math]\underline{n}[/math] normálvektor hosszával, amit egységnyire választunk. -- toma - 2007.10.28.
3. feladat
Írja fel három pontra illeszkedő sík egyenletét az euklideszi és a projektív térben.
Megoldás
Euklideszi térben
Ismerjük a sík 3 pontját: [math]\underline{p_{1}}[/math], [math]\underline{p_{2}}[/math], [math]\underline{p_{3}}[/math]
Tehát ismerünk 2 vektort, ami a síkon van: [math]\underline{p_{2}} - \underline{p_{1}}[/math] és [math]\underline{p_{3}} - \underline{p_{1}}[/math]
Ezeket össze keresztelve megkapjuk a sík normál vektorát: [math]\underline{n} = (\underline{p_{2}} - \underline{p_{1}}) \times (\underline{p_{3}} - \underline{p_{1}}) [/math]
A sík egyenlete: [math]\underline{n} \cdot (\underline{r} - \underline{r_{0}}) = 0[/math], behelyettesítve: [math]((\underline{p_{2}} - \underline{p_{1}}) \times (\underline{p_{3}} - \underline{p_{1}})) \cdot (\underline{r} - \underline{p_{1}}) = 0[/math]
6. feladat
Írjon C függvényt, amely egy egyenes és egy pont távolságát kiszámítja.
Általánosan:
- [math]\underline{p_{1}}[/math], [math]\underline{p_{2}}[/math] egyenes 2 pontja
- [math]\underline{p}[/math] a pont
- [math]\underline{v} = \underline{p_{2}} - \underline{p_{1}}[/math] egyenes irány vektora
[math] d = \frac{\left| (\underline{p} - \underline{p_{1}}) \times \underline{v} \right|}{\left| v \right|} [/math]
Megoldás
float distanceLinePoint(float x1, float y1, float z1,
float x2, float y2, float z2,
float px, float py, float pz)
{
//egyenes irányvektora
float vx = x2 - x1,
vy = y2 - y1,
vz = z2 - z1;
//irányvektor nagysága
float v = sqrt(vx*vx + vy*vy + vz*vz);
//irányvektor normalizálása
vx /= v; vy /= v; vz /= v;
//pont - egyenes első pontja közötti vektor
float qx = px - x1,
qy = py - y1,
qz = pz - z1;
//r = q (kereszt) v = |q|*|v|*sin(alpha)
//v-t normalizáltuk, ezért az 1, nem kell osztani
float rx = qy*vz - vy*qz,
ry = vx*qz - qx*vz,
rz = qx*vy - qy*vx;
//r vektor nagysága
return sqrt(rx*rx + ry*ry + rz*rz);
/*Másik megoldás:
q vektor skalárisan szorozva v-vel, így megvan az egyenesre
vetített q vektor nagysága. Ezt összeszorozva v-vel, és hozzáadva
az egyenes első pontjához, megvan az egyenesre vetített pont.
Innen d = a 2 pont távolsága.*/
}
7. feladat
Írjon C függvényt, amely két térbeli egyenes távolságát kiszámítja.
Megoldás
Általánosan:
- [math]\underline{p_{1}}[/math], [math]\underline{p_{2}}[/math] egyik egyenes pontjai
- [math]\underline{q_{1}}[/math], [math]\underline{q_{2}}[/math] másik egyenes pontjai
- [math]\underline{v_{1}} = \underline{p_{2}} - \underline{p_{1}}[/math] első egyenes irány vektora
- [math]\underline{v_{2}} = \underline{q_{2}} - \underline{q_{1}}[/math] második egyenes irány vektora
[math] d = \frac{\left| (\underline{p_{1}} - \underline{q_{1}}) \cdot (\underline{v_{1}} \times \underline{v_{2}}) \right|}{\left| \underline{v_{1}} \times \underline{v_{2}} \right|} [/math]
float distanceLineLine(float p1x, float p1y, float p1z,
float p2x, float p2y, float p2z,
float q1x, float q1y, float q1z,
float q2x, float q2y, float q2z)
{
//irány vektorok
float v1x = p2x - p1x,
v1y = p2y - p1y,
v1z = p2z - p1z;
float v2x = q2x - q1x,
v2y = q2y - q1y,
v2z = q2z - q1z;
//vektorok nagysága
float v1 = sqrt(v1x*v1x + v1y*v1y + v1z*v1z),
v2 = sqrt(v2x*v2x + v2y*v2y + v2z*v2z);
//normalizálás
v1x /= v1; v1y /= v1; v1z /= v1;
v2x /= v2; v2y /= v2; v2z /= v2;
//egyenesek pontjai közötti vektor
float ex = p1x - q1x,
ey = p1y - q1y,
ez = p1z - q1z;
if (abs(v1x) == abs(v2x) && abs(v1y) == abs(v2y) && abs(v1z) == abs(v2z)) {
//az egyenesek párhuzamosak, de lehet, hogy ellentétes irányuak, ezért kell abs
//a kereszt szorzat 0-t eredményezne rosszul
//mert a vektorok által bezárt szög 0, vagy 180 és sin(0) = sin(180) = 0
//a távolság |e|*|v1|*sin(alpha)
//d = |e (cross) v1|
float fx = ey*v1z - v1y*ez,
fy = v1x*ez - ex*v1z,
fz = ex*v1y - ey*v1x;
return sqrt(fx*fx + fy*fy + fz*fz);
} else {
//v1 (cross) v2
float wx = v1y*v2z - v2y*v1y,
wy = v2x*v1z - v1x*v2z,
wz = v1x*v2y - v1y*v2x;
//e (dot) w
//v-ket normalizáltuk, nem kell leosztani
return abs(ex*wx + ey*wy + ez*wz);
}
}
Egy-kis magyarázat a fenti képlethez: (forrás: http://zeus.nyf.hu/~szalonta/Trigkoord06.pdf)
Bizonyítás: Két kitérő egyenes távolságán az azokat összekötő, mindkettőre merőleges normáltranszverzális szakasz hosszát értjük. A v1 × v2 vektoriális szorzat normáltranszverzális irányú, hiszen mindkét irányvektorra merőleges vektor, osztva a hosszával, egységvektor. Ennek és a két egyenes egy-egy pontjával meghatározott (P1, Q1) reprezentánsú (q1 - p1) vektornak a skaláris szorzata éppen a (q1 - p1) vektor normáltranszverzális irányra vett merőleges vetületének hosszát adja abszolútértékben.
Ez az abs feltétel biztos? Mert sztem ez bővebb a párhuzamosságnál, pl két merőleges egyenes is lehet ilyen. lásd (1,1,0) és (1,-1,0) vektorok. -- TTb - 2008.05.26.
A kód megértését segítendő magyarázat: a felvázolt képlet egy elméleti koordinátageometria megoldás, a kód analógiája teljesen más. A megvalósítás kihasználja a vektoriális szorzat azon tulajdonságát, hogy két vektor vektoriális szorzata egy a két vektorra merőleges vektor lesz, melynek hossza |v1*sin(alpha). (Szirmay - Analitikus geometria - 7.oldal) Ami nem más, mint a v2 és v1 vektor síkján lévő v2 vektorra merőleges egyenesre vetített v1 vektor. A mi esetünkben ez pont a normáltranszverzális, melynek hossza adja a két egyenes közti távolságot. -- Paaci - 2009.01.17.
10. feladat
Lehet-e egy affin - azaz párhuzamos egyeneseket párhuzamos egyenesekbe leképező - transzformáció mátrixának negyedik oszlopa [0, 0, 0, 2]?
Megoldás
Az egységmátrix λ-szorosa az (x, y, z, h) homogén koordinátás pontot a (λx, λy, λz, λh) pontba viszi, azaz helyben hagyja. A helyben hagyás egy affin transzformáció, és λ=2-re a mátrix negyedik oszlopa pont (0, 0, 0, 2) lesz. -- Peti - 2007.10.27.
Vita
Idézet tk. 46 oldala: "Az affin transzformációkban a mátrix negyedik oszlopa mindig [0,0,0,1] alakú , tehát a pont negyedik koordinátáját nem rontja el. (...) Ha a mátrix negyedik oszlopában nem ragaszkodunk a [0,0,0,1] értékekhez, akkor egy még átalánosabb transzformáció típushoz, a projektív transzformációkhoz jutunk." Szóval szerintem a válasz a feladatra a "nem". -- Zsófi - 2007.10.28.
Sztem a fenti megoldás helyes: adott egy példát h miért lehet. Valóban definíció szerint projektyv transzformációkat kaunk, viszont az affin is projektív, és a fenti példa arra, hogy valóban lehet affin sztem, javítsatok ki ha tévednék. -- TTb - 2008.05.27.
Sztem a mátrix így néz ki (nevezzük A-nak) : [math] T = \left[\begin{array}{cccc} a11 & a12 & a13 & 0\\ a21 & a22 & a23 & 0\\ a31 & a32 & a33 & 0\\ a41 & a42 & a43 & 2\\ \end{array} \right] [/math] Ez annyiban különbözik egy általánosan megszokott affin transzformációs mátrixtól, hogy az a44 eleme 2 és nem 1 (nevezzük 1-essel A'-nek). Ha meggondoljuk ez nem baj, mert annyi változást okoz A az A'-höz képest, hogy (x, y, z, 1) helyett (x, y, z, 2)-t kapunk, ami pont egy 1/2-szeres nagyítást jelent (hiszen ha leosztjuk a pont koordinátáit 2-vel, akkor ezt kapjuk : (x/2, y/2, z/2, 1), és az x, y és z helyen a Descartes-koordinátáknak megfelelő pontot kapjuk(ha a 4. koordináta (h) 1)). A könyvből vett idézetet ellenőriztem, valóban így szerepelt, és ez nem pontos megfogalmazás. Szerintem a [0, 0, 0, 1] helyett [0, 0, 0, λ], λ ≠ 0 a helyes kifejezés. -- k317h - 2009.06.07.
13. feladat
Írja fel azon homogén lineáris transzformáció mátrixát, amely egy síkbeli pontot az xc, yc vetítési középponttal az ax+by+c=0 egyenletű egyenesre vetít.
Megoldás
[math]T = \left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & \frac{1}{c} \\ 0 & 0 & 0 \\ \end{array} \right)[/math]
Javítás:
Ez az y = c egyenletű egyenesre origó középponttal vetítő mátrix. A megoldás alapja a bmetransf slideshow 20. slide-ja: ax + by = 1 egyenletű egyenesre origó középpontú vetítés esetén a mátrix:
[math]T = \left( \begin{array}{ccc} 1 & 0 & a \\ 0 & 1 & b \\ 0 & 0 & 0 \\ \end{array} \right)[/math]
Ehhez képest az ax + by + c = 0 egyenlet helyett írhatjuk azt, hogy ax + by = 1-c, és akkor az előzőhöz hasonló egyenletet kapunk. Rátolunk egy (1-c)-vel skálázást a mátrixra: ax és by összege ez esetben nem 1, hanem annak (1-c)-szerese. Az y=c egyenesre való vetítéshez hasonlóan ez itt egy (1-c)-vel való osztásként jelenik meg a mátrix harmadik oszlopában. Mivel nem az origó a középpont, ezért még el is kell tolni az egészet (xc, yc)-vel, így a keresett mátrix:
[math]T = \left( \begin{array}{ccc} 1-c & 0 & a \\ 0 & 1-c & b \\ xc & yc & 0 \\ \end{array} \right)[/math] = [math]T = \left( \begin{array}{ccc} 1 & 0 & \frac{a}{1-c} \\ 0 & 1 & \frac{b}{1-c} \\ xc & yc & 0 \\ \end{array} \right)[/math]
Gergő -- 2007.11.29.
14. feladat
Tekintsük a következő homogén lineáris transzformációs mátrixot (a transzformálandó pontot a mátrix bal oldalára kell írni):
[math]\left( \begin{array}{ccc} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \\ \end{array} \right)[/math]
Mit csinál a transzformáció? Mi keletkezik a transzformáció után a [2, 1] és [-1, 1] pontokat összekötő szakaszból.
Megoldás
Ez egy nem-lineáris transzformáció a 2 dimenziós térben, ami a [x,y,1] alakból [x,y,x] (vagy másként [1,y/x,1]) alakba képez át. A transzformáció után a két új végpont az [1, 0.5] és az [1, -1]. A szakasz 90 fokkal elfordul, és az x tengelyre lesz merőleges, a hossza pedig megrövidül 2-ről 1,5-re. Összeségében a transzformáció minden pontot az x tengelyre merőleges, és azt 1-nél metsző egyenesre helyez át.
Javítás:
A vetítés után a szakasz hosszával nem a fent leírt dolog történik, ugyanis létrejön az átfordulási probléma; azaz az x=1 egyenesen a szakaszunk nem a 0.5 és a -1 között helyezkedik el, hanem pont ezen kívül; az eredeti szakasz [0,1] pontja pedig ideális ponttá válik! Tk. 49 oldal.
-- Zsófi - 2007.10.28.
Rajz
Ez egy homogén lineáris transzformáció 2D-ben. Középpontosan levetíti a pontokat az [math]x = 1[/math] egyenesre az origón át.
%ATTACHURL%/graph_anal_14.png
- piros egyenes: a vetítési egyenes
- kék pontok, szakasz: eredeti pontok, és a szakasz
- zöld pontok, szakasz: vetített pontok, és félegyenesek a már említett átfordulás miatt
Lásd: bmetrans.ppt 20. slide
-- DeVi - 2007.10.28.
22. feladat
Adott a következő [math]\underline{r} \rightarrow \underline{r}' [/math] 2D transzformáció, ahol [math]\underline{r}[/math], [math]\underline{r}[/math]’ és [math]\underline{b}[/math] a sík vektorai: [math] \underline{r}' = \frac{\underline{r}}{\left| \underline{r} \right |} + \underline{b} [/math]
A képletben [math]\left| \underline{r} \right|[/math] az [math]\underline{r}[/math] vektor abszolút értékét jelenti. Mibe vihet át ez a transzformáció egy szakaszt?
Megoldás
Az origó körüli 1 sugarú körre vetíti a pontokat, majd ezeket az új pontokat eltolja [math]\underline{b}[/math]-vel.
Szakaszból görbe lesz.
Megoldás 2
A trafo elsőként lenormálja a paraméterül kapott vektort, (azaz megőrzi az irányát és egységnyire változtatja a hosszát), majd eltolja azt 'b' vektorral. Egy szakaszt, ha az nem tartalmazza az origót egy Pi-nél kisebb szögű origó középpontú körivvé transzformál, majd eltolja 'b' -vel. Különben két ponttá transzformálja a szakaszt és azt tolja el, de ekkor a trafo a nullvektorra nem értelmezett.
-- <<Miki>> - 2007.10.29
23. feladat
Hogyan definiálható a B-spline és milyen tulajdonságai vannak. Sünis Könyv 58.
Megoldás
A B-spline olyan görbeleírás, amely a lokális vezérelhetőség és a simaság (deriválhatóság) között ad kompromisszumot. Approximációs görbe, tehát a vezérlőpontokon jellemzően nem halad át. (Az első és az utolsó vezérlőponton sem) Általános esetben a szomszédos csomópontok távolságára nincs megkötés.
A görbe bázisfüggvényeit úgy származtatjuk, hogy kiindulunk olyan bázisfüggvényekből, amelyek a hozzájuk tartozó csomópontintervallumon Bi=1 értéket vesznek fel, egyébként pedig nullát. Ezután a B-spline fokszámának megfelelő számszor lineáris simítást végzünk.
Ha egy B-spline fokszáma n. akkor egy vezérlőpont a görbe n+1 szegmensére van hatással, tehát a fokszám növelésével a lokális vezérelhetőség csökken.
24. feladat
Mi a NURBS.
Megoldás
Non-Uniform Rational B-Spline, a B-Spline egy kezelhetőbb változata. A vezérlőpontokhoz még egy w súlyt is rendelünk, ennek növelésével a görbe az adott pontban egyre jobban csúcsosodik. Előnye, hogy a kúpszeletek tökéletesen leírhatók legalább harmadfokú NURBS-ökkel, hátránya hogy (hacsak homogén koordinátákban nem számolunk), osztásokra is szükség van a görbe kirajzolásához.
A görbe egy pontjának meghatározása: [math] r(t) = {{\sum w_iB_i^{NUBS} r_i}\over{\sum w_jB_j^{NUBS}}} = B_i^{NURBS} r_i [/math]
A bázisfüggvények kiszámítása a NUBS bázisfüggvényeiből tehát: [math] B_i^{NURBS} = {{w_i B_i^{NUBS}}\over{\sum w_jB_j^{NUBS}}} [/math]
27. feladat
Adja meg a kvadratikus felületek általános definícióját. Milyen konkrét tagjai vannak ennek a családnak.
Megoldás
Kvadratikus felületnek nevezzük azokat a felületeket, melyek legfeljebb másodfokú implicit egyenlettel leírhatók. Általános, homogén koordinátás alakban megadva:
[math] [x, y, z, 1] Q \left[ \begin{array}{r} x \\ y \\ z \\ 1 \end{array} \right] = 0 [/math]
Ahol Q egy 4x4-es mátrix. Kvadratikus felülettel leírható például a kúp, ellipszoid, hengerpalást, paraboloid.
28. feladat
Rajzolja fel a szárnyas él adatstruktúrát, és írjon programot, amely egy lapnak kiírja az összes csúcsát.
Megoldás
Sünis könyv 140.o.
Adatszerkezet:
class Edge {
Vertex * vertex_start, vertex_end; //Az él kezdő- és végpontja
Face * face_left, face_right; //Az él jobb- és baloldali lapja
Edge * loop_left, loop_right; //A végpontból kiinduló két él
Edge * next; //Az éllista következő eleme
}
struct Vertex {
Vector point;
Edge * edge; //A csúcsot tartalmazó él
}
struct Face {
Edge * edge;
Face * next;
}
Program (vázlatosan):
void printVertex(Vertex * v) {
cout << v.x << "," << v.y << "," v.z;
}
void printVertices(Face * face) {
Edge * edge = face.edge;
Edge * current = NULL;
bool goRight = (edge.face_right == face) ? true : false;
print(edge.vertex_end);
while( edge != current ) {
if( goRight ) {
current = edge.loop_right;
} else {
current = edge.loop_left;
}
print(current.vertex_end);
}
}
29. feladat
Mik az Euler operátorok és miért van rájuk szükség. Sünis könyv 75.o.
Megoldás
Euler egyenlet: lapok + csúcsok = élek + 2
Az Euler operátorokat poligonhálóra alkalmazva az Euler tulajdonság nem sérül.
Típusai: A, Él kettévágás Egy él egy pontján felveszünk egy új csúcsot, ami ezáltal két élre bomlik. A csúcsok száma eggyel, az élek száma szintén eggyel növekszik.
B, Poligon kettévágás Egy lap két csúcsát egy új éllel kötünk össze, ezáltal a lap két lapra esik szét. Az éleg és a lapok száma egyaránt eggyel növekszik.
C, Élzsugorítás Egy élet egy pontba zsugorítunk. Az él eltűnik, a két végpontját egyesítjük. Az élek száma eggyel csökkel, a csúcsok száma eggyel csökken. Ha az élhez kapcsolódó egyik vagy minkét poligon egy háromszög, akkor az eltűnik, a a másik két éle pedig egyesül.
D, Poligon kihúzás Kiválasztunk egy lapot, és az elmozdítjuk az eredeti helyről, ehhez a kiválasztott lap éleit és csúcsait meg kell duplázni. Ha *e* éle van a kiválaszott lapnak, akkor *e* új él jön létre, és *e* új pont. Ezután az új pontokat össze kell kötni a nekik megfelelő régi pontokkal. (még *e* új él és *e* új lap.)
30. feladat
Írjon C++ nyelven egy CSG fát megvalósító osztályt.
35. feladat
Írjon erősen emelkedő szakaszt rajzoló programot, a Bresenham algoritmus alapján.
36. feladat
Írjon erősen emelkedő szakaszt rajzoló programot, a DDA algoritmus alapján.
2008-as házi feladat keretben implementált DDA szakaszrajzoló algoritmus:
Erősen emelkedő szakaszokra kicsit furán viselkedik :)
-- Bandita - 2009.01.02.
37. feladat
Írjon programot, amely egy szakaszt egy konvex sokszögre vág.
-- Geri - 2006.12.29. -- Peti - 2006.08.02. -- Sales - 2006.07.27.
