A grafkerdes.doc feladatai

A VIK Wikiből

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.


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:

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.

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


Nem tudom, hogy a fenti megoldás hogyan jött ki, én a következőt kaptam:

A sík normálvektora: ,

a pont, amit vetíteni akarunk.

írjuk fel a pontból induló síkra merőleges egyenes egyenletét:

Megkaphatjuk a sík és az egyenes metszéspontját, ha a következő egyenletet megoldjuk -ra:

Majd a -t visszaírva az egyenes egyenletébe megkaphatjuk a metszéspontot.

Most, hogy megvan a , hogyan írjuk fel a vetítés mátrixát?

Tudjuk, hogy:

Most már csak ki kell találni a mátrix elemeit, hogy az egyenlet két oldala megegyezzen.

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 nevező elhagyható, ugyanis ez megegyezik az 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: , ,

Tehát ismerünk 2 vektort, ami a síkon van: és

Ezeket össze keresztelve megkapjuk a sík normál vektorát:

A sík egyenlete: , behelyettesítve:



6. feladat

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

Általánosan:

  • , egyenes 2 pontja
  • a pont
  • egyenes irány vektora

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:

  • , egyik egyenes pontjai
  • , másik egyenes pontjai
  • első egyenes irány vektora
  • második egyenes irány vektora

Egy kis magyarázat a fenti képlethez: 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. (forrás: http://zeus.nyf.hu/~szalonta/Trigkoord06.doc)

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);		  
	 }
}

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) : 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

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:

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:

=

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):



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 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ő 2D transzformáció, ahol , ’ és a sík vektorai:

A képletben az 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 -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:

A bázisfüggvények kiszámítása a NUBS bázisfüggvényeiből tehát:



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:

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:

Ezen a helyen volt linkelve a(z) DDA.cpp nevű fájl ("DDA.cpp" link szöveggel) a régi wiki http://wiki-old.sch.bme.hu/bin/view/Infoalap/SzgGrafFeladatok oldaláról. (Ha szükséged lenne a fájlra, akkor a pontos oldalmegnevezéssel együtt küldd el a wiki@sch.bme.hu címre a kérésedet)


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.