GrafikaGyakorloAnalitikusGeometria

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

Analitikus geometria

1. Írja fel azon művelet mátrixát, amely egy ax+by+cz+d=0 egyenletű síkra merőlegesen vetít.

• 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_{y}-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_{y}-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] -- Pálesz - 2007.10.27.

• Megjegyzés: az [math] a^2+b^2+c^2 [/math] nevező nem hagyható el, ugyanis itt "kívülről" kapjuk a, b, c értékét, tehát nem tehetjük fel, hogy az (a, b, c) vektor egységnyi hosszú.

2. Bizonyítsa be, hogy a projektív sík egyenesének AX+BY+ch=0 egyenlete összhangban van a projektív geometria azon axiómáival, hogy "két különböző egyenes egy pontban metszi egymást", és hogy "két pont meghatároz egy egyenest".

• Egy A, B, c hármas akkor határoz meg egy projektív egyenest, ha legalább az egyik nem nulla, két ilyen hármas pedig akkor határoz meg két különböző egyenest, ha az egyik nem áll elő a másik konstansszorosaként. Ez a két feltétel pontosan azt jelenti, hogy az [math] \underline{\underline{F}}=\left[\begin{array}{rrr} A_1 & B_1 & c_1 \\ A_2 & B_2 & c_2 \end{array}\right] [/math] mátrix rangja 2. Ekkor az [math] \underline{\underline{F}}\cdot (X, Y, h)^T=(0, 0) [/math] egyenletnek végtelen sok megoldása lesz (tehát lesz nem csupa nullából álló, valódi projektív pontot kijelölő megoldás), viszont bármely két megoldás egymásnak a konstansszorosa lesz, tehát ugyanazt a projektív síkbeli pontot jelenti. Tehát pontosan egy pont van rajta mindkét egyenesen.
• A projektív síkban teljes dualitás van az egyenesek és a pontok között; ugyanezt a bizonyítás a másik állításra is működik, az [math] (A, B, c) \Leftrightarrow (X, Y, h) [/math] felcseréléssel.

3. Írja fel három pontra illeszkedő sík egyenletét az euklideszi és a projektív térben.

• 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]
• Projektív térben: először is, írjuk át az euklideszi térben érvényes egyenletet, hogy vektorok helyett a vektorok x, y, z komponensei szerepeljenek benne: [math] det \left[\begin{array}{ccc} x-x_1 & y-y_1 & z-z_1 \\ x_2-x_1 & y_2-y_1 & z_2-z_1 \\ x_3-x_1 & y_3-y_1 & z_3-z_1\end{array}\right]=0 [/math] ugyanis fent a [math] \underline{p_{2}} - \underline{p_{1}} [/math], [math] \underline{p_{3}} - \underline{p_{1}} [/math], [math] \underline{r} - \underline{p_{1}} [/math] vektorok vegyes szorzata szerepel, az pedig pont a vektorok komponenseiből felírt mátrix determinánsa. Ezután, a sík egyenletének másik levezetéséhez hasonlóan, x-et x/h-val, stb. helyettesítjük: [math] det \left[\begin{array}{ccc} x/h-x_1/h_1 & y/h-y_1/h_1 & z/h-z_1/h_1 \\ x_2/h_2-x_1/h_1 & y_2/h_2-y_1/h_1 & z_2/h_2-z_1/h_1 \\ x_3/h_3-x_1/h_1 & y_3/h_3-y_1/h_1 & z_3/h_3-z_1/h_1\end{array}\right]=0 [/math] majd (felhasználva, hogy a mátrix egy sorát konstanssal szorozva a determináns is ugyanazzal szorzódik) beszorozzuk mindegyik sort, hogy eltüntessük a törteket (az első sort [math] hh_1 [/math]-gyel, stb.): [math] det \left[\begin{array}{ccc} xh_1-x_1h & yh_1-y_1h & zh_1-z_1h \\ x_2h_1-x_1h_2 & y_2h_1-y_1h_2 & z_2h_1-z_1h_2 \\ x_3h_1-x_1h_3 & y_3h_1-y_1h_3 & z_3h_1-z_1h_3\end{array}\right]=0 [/math]
• Wikipédia: vegyes szorzat

4. Bizonyítsa be, hogy a homogén lineáris transzformációk a konvex kombinációkat konvex kombinációkká képezik le.

• Nem tudom, jól értettem-e a feladatot, de: konvex kombinációnak az olyan lineáris kombinációt hívják, ahol mindegyik együttható 0 és 1 között van, és az együtthatók összege 1 (ugyanis egy konvex sokszög csúcsvektorainak konvex kombinációiként a sokszög minden pontja előáll, és csak azok). Mivel a lineáris transzformációk pontosan azzal a tulajdonsággal rendelkeznek, hogy a lineáris kombinációkat azonos lineáris kombinációkba viszik, ezért az állítás nyilvánvaló.
• Wikipédia: konvex kombináció

5. Írja fel azon síkpontok mértani helyének egyenletét, amelyek egy egyenestől és egy ponttól ugyanolyan távolságra vannak. Milyen alakzat ez? Terjessze ki az alakzatot a projektív síkra. Mik az ideális pontjai?

• Úgy vesszük fel a koordinátarendszert, hogy a pont a (0, 0.25) legyen, az egyenes pedig az y=-0.25 egyenes. Ekkor a ponttól való távolság négyzete egyenlő az egyenestől vett távolság négyzetével: [math] (x-0)^2+(y-0.25)^2=(y-(-0.25))^2 [/math] A zárójeleket felbontva és rendezve: [math] x^2=y [/math], tehát ez az alakzat a parabola.
• A projektív síkra kiterjesztve, az egyenes egyenletéhez hasonló módszerrel: [math] \left(\frac{x}{h}\right)^2=\frac{y}{h} [/math], átrendezve: [math] x^2=yh [/math], így a parabolán egy ideális pont van, az x=0, h=0.
• Wikipédia: parabola

6. Írjon C függvényt, amely egy egyenes és egy pont távolságát kiszámítja.

• [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]

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. Írjon C függvényt, amely két térbeli egyenes távolságát kiszámítja.

• Legyenek az egyenesek kezdőpontjai az [math] \underline{a}_1,\; \underline{a}_2 [/math] vektorok, az irányvektoraik pedig [math] \underline{d}_1,\; \underline{d}_2 [/math]. Vegyünk fel mindkét egyenesen egy-egy pontot, úgy, hogy a lehető legközelebb legyenek egymáshoz; a távolságuk egyenlő lesz az egyenesek távolságával. Legyen [math] \underline{n}=\frac{\underline{d}_1 \times \underline{d}_2}{|d_1 \times d_2|} [/math] egy mindkét egyenesre merőleges egységvektor. Erre vetítve bármely, az egyenesek pontjait összekötő szakaszt, legalább [math] |\underline{n}(a_1-a_2)| [/math] lesz a vetület hossza, tehát bármely szakasz is legalább ilyen hosszú. (Ilyen hosszú szakasz elő is állítható.)
• Párhuzamos egyeneseknél máshogy kell számolni: ekkor egyszerűen a két kezdőpont különbségének az irányvektorokra merőleges komponensének abszolútértéke a távolság.

float lineDistance(Vector a1, Vector a2, Vector d1, Vector d2) {
  Vector adiff=vectSub(a1, a2);
  Vector n=crossProduct(d1, d2);
  float temp;
  if (vectAbs(n)==0) {
	 normalize(&d1);
	 temp=dotProduct(adiff, d1);
	 return sqrt(vectAbs(adiff)*vectAbs(adiff)-temp*temp);
  } else {
	 normalize(&n);
	 return fabs(dotProduct(n, adiff));
  }
}

8. Írjon C függvényt, amely egy implicit egyenletével adott egyenes, és két végpontjával adott szakasz metszéspontját kiszámítja.

9. Írja fel a projektív sík egyeneseinek implicit (azaz nem paraméteres) egyenletét homogén koordinátákban. Bizonyítsa be, hogy a sík minden invertálható homogén lineáris transzformációja ezt az egyenest egyenesre képezi le. Melyek azok a transzformációk, amelyek az egyenest önmagára képezik le? Mi történik az egyenes normálvektorával?

10. Lehet-e egy affin - azaz párhuzamos egyeneseket párhuzamos egyenesekbe leképző - transzformáció mátrixának negyedik oszlopa [0, 0, 0, 2]?

• 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.

11. A projektív tér síkjainak homogén lineáris transzformációi. A projektív tér síkjának egyenlete. A transzformáció mibe viszi át a síkot (feltételezheti, hogy a transzformációs mátrix invertálható), bizonyítás. Mi történik a sík normálvektorával? Mi ennek a következménye az OpenGL működésére?

12. Tekintsük a projektív térben a [1, 2, 3, 4] és [-4,-3,-2,-1] homogén koordinátákkal azonosított végpontok konvex kombinációiként előálló szakaszt! Mekkora a szakasz hossza?

13. Í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.

14. 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}{rrr} 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?

15. Adott a következő homogén lineáris transzformáció (a transzformálandó pont helyvektorát sorvektornak kell tekinteni): [math] \left[ \begin{array}{rrrr} 8 & 0 & 0 & 0 \\ 0 & 6 & 0 & 0 \\ 0 & 0 & 4 & 0 \\ 8 & 6 & 4 & 2 \end{array} \right] [/math] Adja meg azon ponthalmaz egyenletét, amelyre ez a transzformáció a 8x+6y+8z + 6 = 0 egyenletet kielégítő ponthalmazt leképezi! Először írja le a megoldás menetét, azután végezze el a szükséges számításokat.

16. Adott két pont Descartes koordinátákkal: (3,6), (-2,5). Adja meg erre a két pontra illeszkedő egyenes ideális pontját homogén koordinátákban!

17. Bizonyítsa be, hogy ha egy invertálható transzformációs mátrix 4. oszlopa [0, 0, 0, 1], akkor a transzformáció affin, azaz párhuzamos egyeneseket párhuzamos egyenesekre képez le (a transzformálandó pont homogén koordinátáit sorvektornak tekintjük és a mátrixszal jobbról szorozzuk)!

18. Írja fel a 3D projektív tér összes ideális síkjának és ideális egyenesének egyenletét (az ideális térelem csak ideális pontokat tartalmaz). Hány ideális sík és egyenes van?

19. Írja fel a projektív sík egy körének egyenletét! Mi lesz abból a körből, amelynek középpontja egy ideális ponton van? Segítség: a kör egyenlete homogén koordinátákban annak analógiájára, ahogyan az egyenes egyenletét a síkban, és a sík egyenletét a térben bevezettük.

• A kör egyenlete euklideszi síkon: [math] (x-x_0)^2+(y-y_0)^2-r^2=0 [/math] Amit itt a pont x koordinátájának nevezetünk, azt a projektív síkon úgy lehet kiszámítani, hogy az x koordinátát h-val leosztjuk (homogén osztás). Legyen a pont (aminek a körön lévőségét el akarjuk dönteni) negyedik koordinátája h, a középponté [math] h_0 [/math]. Ekkor a projektív síkon az egyenlet: [math] (\frac{x}{h}-\frac{x_0}{h_0})^2+(\frac{y}{h}-\frac{y_0}{h_0})^2-r^2=0 [/math] beszorozva [math] hh_0 [/math]-lal, hogy ne legyen benne tört: [math] (xh_0-x_0h)^2+(yh_0-y_0h)^2-r^2h^2h_0^2=0 [/math]
• Ha a középpont az ideális egyenesen van, akkor [math] h_0=0 [/math], ezt behelyettesítve: [math] (x_0^2+y_0^2)h^2=0 [/math] Mivel egy pontnak nem lehet mindhárom koordinátája nulla, ezért nem lehet [math] x_0,\; y_0 [/math] közül mindkettő nulla, tehát a négyzetösszegük sem, így h-nak kell nullának lennie. Tehát ha egy kör középpontja az ideális egyenesen van, akkor a kör az ideális egyenes lesz. (Igen, a projektív síkon van értelme annak, hogy a kör egy egyenes lesz.)

20. Tekintsük a projektív tér [a, b, c, d] homogén négyessel megadott síkját. Írja fel ezen sík ideális egyenesének paraméteres egyenletét!

21. Írjon C++ függvényt, amely a bemeneti paraméteréül a projektív sík két egyenesét kapja, kiszámítja a két egyenes metszéspontját, a metszéspontot vetíti az origó középpontú, egység sugarú körre, és a vetület Descartes koordinátáit adja vissza.

22. Adott a következő [math] r \rightarrow r^\prime [/math] 2D transzformáció, ahol r, r'; és a, b, c a sík vektorai: [math] r^\prime = \left[\frac{a\cdot r}{c\cdot r}, \frac{b\cdot r}{c\cdot r}\right] [/math] Mibe vihet át ez a transzformáció egy szakaszt?

• A feladatban nagyon lényeges pont, hogy a két tört nevezője azonos. Ugyanis, ha áttérünk (kétdimenziós) homogén koordinátákra, akkor az [math] r^\prime [/math] vektort felírhatjuk a következőképp is: [math] r^\prime = \left[ \frac{a\cdot r}{c\cdot r}, \frac{b\cdot r}{c\cdot r}, 1 \right] = \left[ a\cdot r, b\cdot r, c\cdot r \right] [/math] ahol a harmadik elem a w homogén koordináta. Ezt pedig - felhasználva az a, b, c vektorok x és y komponenseit - mátrixos alakba írhatjuk: [math] \left[ \begin{array}{r} r_x^\prime \\ r_y^\prime \\ r_w^\prime \end{array} \right] = \left[ \begin{array}{rrr} a_x & a_y & 0 \\ b_x & b_y & 0 \\ c_x & c_y & 0 \end{array} \right] \left[ \begin{array}{r} r_x \\ r_y \\ 1 \end{array} \right] [/math]
• A fenti transzformáció tehát nem más, mint egy kétdimenziós projekció. Ez egyenest egyenesbe visz, viszont szakaszok esetében bonyolultabb a helyzet. Végig lehet gondolni, hogy - attól függően, a szakasz valamelyik pontja ideális pont lesz-e, vagy sem - szakasz, félegyenes, vagy "inverz szakasz" (egy egyenes, amiből egy szakasz ki van vágva) lehet a kép. Egy projektív transzformáció egyik legfontosabb jellemzője, hogy melyik egyenest viszi át az ideális egyenesbe, illetve a konkrét esetben az, hogy ez az egyenes milyen viszonyban van a szakaszunkkal:
  • Ha az ideálisba átmenő egyenesnek nincs közös pontja a szakasszal, akkor nem történik semmi "különleges", egy szakasz lesz a kép.
  • Ha az egyenes a szakasz egyik végpontján átmegy, a másikon nem, akkor félegyenest kapunk.
  • Ha a szakasz benne fekszik az egyenesben, akkor szakaszt kapunk, csakhogy az ideális egyenesen.
  • Ha az egyenes a szakaszt belső pontjában metszi, akkor "inverz szakaszt" kapunk.

23. Adott a következő [math] r \rightarrow r^\prime [/math] 2D transzformáció, ahol r, r' és b a sík vektorai: [math] r^\prime = \frac{r}{\left| r \right|} + b [/math] A képletben [math] \left| r \right| [/math] az r vektor abszolútértékét jelenti. Mibe vihet át ez a transzformáció egy szakaszt?

• Az első lépésben a vektort osztjuk a saját abszolút értékével. Könnyen látható, hogy ez nem más, mint az origó körüli egységsugarú körre való vetítés (középpontosan, az origóból). Ez általában egy körívet eredményez, kivéve két speciális esetet: ha a szakasz egyenese átmegy az origón, de az origó nincs a szakaszban, akkor egyetlen pont ("nulla hosszú körív") lesz az eredmény. Ha viszont az origó benne van a szakaszban, akkor két, a körön átellenesen elhelyezkedő pont lesz az eredmény.
• A második lépésben csak egy eltolást végzünk, ami a fenti alakzatok alakját nem változtatja meg.

-- G - 2008.12.25.