GrafikaGyakorloGeometriaiModellezes

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.

Mintakérdések a Számítógépes grafika és képfeldolgozás tárgy vizsgájára való felkészüléshez

Geometriai modellezés

24. Hogyan definiálható a B-spline és milyen tulajdonságai vannak?

• Wikipédia: B-spline

25. Mi a NURBS?

• Wikipédia: NURBS

26. Bizonyítsa be, hogy a Bézier görbét érinti az első két kontrolpontokra fektetett egyenes.

• Ha $P_{0},P_{1},...P_{n}$ a kontrolpontok, akkor a t paraméterértékhez tartozó pont: $P(t)=\sum _{i=0}^{n}P_{i}t^{i}(1-t)^{n-i}{n \choose i}$
• Ennek a t szerinti deriváltja (vagyis az érintővektor a t-hez tartozó helyen): ${\frac {\partial P(t)}{\partial t}}=\sum _{i=0}^{n}P_{i}(it^{i-1}(1-t)^{n-i}-t^{i}(n-i)(1-t)^{n-i-1}){n \choose i}$
• Kiemelve a t=0 esetén érdekes első két tagot:

Értelmezés sikertelen (formai hiba): {\displaystyle \frac{\partial P(t)}{\partial t} = P_0 (0 t^{-1} (1-t)^n - t^0 n (1-t)^{n-1}) {n \choose 0} + \]\[ + P_1 (1 t^0 (1-t)^{n-1} - t^1 (n-1)(1-t)^{n-2}) {n \choose 1} + \]\[ + \sum_{i=2}^n P_i (i t^{i-1} (1-t)^{n-i} - t^i (n-i)(1-t)^{n-i-1}) {n \choose i} }

• Rendezve:

Értelmezés sikertelen (formai hiba): {\displaystyle \frac{\partial P(t)}{\partial t} = P_0 (-n(1-t)^{n-1}) + \]\[ + P_1 ( (1-t)^{n-1} - t(n-1)(1-t)^{n-2})n + \]\[ + \sum_{i=2}^n P_i (i t^{i-1} (1-t)^{n-i} - t^i (n-i)(1-t)^{n-i-1}) {n \choose i} }

• t=0 helyettesítéssel a szumma elhagyható, hiszen (mivel i=2-től szummázunk) mindegyik tagban t legalább az első hatványon szerepel. Így: ${\frac {\partial P(t)}{\partial t}}{\Big |}_{t=0}=P_{0}(-n(1-0)^{n-1})+P_{1}((1-0)^{n-1}-0(n-1)(1-0)^{n-2})n=(P_{1}-P_{0})n$
• Tehát tényleg párhuzamos a kezdőpontban vett érintő az első két kontrolponton átmenő egyenessel (ugyanis ennek irányvektora a két kontrolpont vektorának különbsége).
• Wikipédia: Bézier görbe

27. Hogyan lehet előállítani egy Bézier görbét NURBS segítségével?

• A NURBS-nak speciális esete a NUBS, abból pedig előállítható a Bézier görbe. Először is, a NURBS összes kontrolpontjának súlya legyen azonos. Majd, a NURBS kontrolpontjai legyenek azonosak a kívánt Bézier görbe kontrolpontjaival, kivéve, hogy az első és az utolsó kontrolpontok háromszorosan fognak szerepelni (így egy n pontú Bézier görbe előállításához n+4 pontú NURBS-ra van szükség). Ez azért kell, hogy az első és utolsó ponton átmenjen a görbe.
• ezt még be kéne fejezni...

28. Adja meg a kvadratikus felületek általános definícióját. Milyen konkrét tagjai vannak ennek a családnak?

• A grafikából tanult definíció: $rAr^{T}=0$, ahol $r=\left[{\begin{array}{cccc}x&y&z&1\end{array}}\right]$ és A nem nullmátrix.
• A konkrét tagok: ellipszoid, elliptikus és hiperbolikus paraboloid, egyköpenyű és kétköpenyű hiperboloid, kúp, elliptikus, parabolikus és hiperbolikus henger, valamint egy elfajuló eset, a síkpár (ezt nem mindig sorolják ide).
• Wikipédia: kvadratikus felület

29. Rajzolja fel a szárnyas él adatstruktúrát, és írjon programot, amely egy lapnak kiírja az összes csúcsát.

• Az adatstruktúrával térbeli poliédereket lehet leírni. Minden él tartalmaz egy hivatkozást a két végpontjára, a két általa határolt lapra. Valamint, ha az általa határolt lapokon körbemennénk, akkor az élet mindkét lapon megelőzné és követné egy-egy él, ezekre az élekre is tárolunk hivatkozást. Ezen kívül, a lapok és a csúcsok is tartalmaznak hivatkozást egy élre, ami határolja őket, illetve aminek végpontjai.
• Egy lehetséges implementáció C-ben:

struct Vertex {
  unsigned int id;
  struct Edge* e; /* az egyik él, aminek végpontja */
};

struct Face {
  unsigned int id;
  struct Edge* e; /* az egyik él, ami határolja */
};

struct Edge {
  unsigned int id;
  struct Face *f1, *f2; /* a két általa határolt lap */
  struct Vertex *v1, *v2; /* a két végpont */
  struct Edge *n1, *n2, *p1, *p2; /* a rákövetkező és megelőző élek a két lapon */ 
}

void vertices(Face* f) {
  Edge *current_edge=f->e;
  Edge *temp;
  Vertex *current_vertex;
  
  if (current_edge->f1==f) temp=current_edge->n1;
  else temp=current_edge->n2;
  if (current_edge->v2==temp->v1 || current_edge->v2==temp->v2) current_vertex=current_edge->v2;
  else current_vertex=current_edge->v1;
  
  do {
	 printf("%d\n", current_vertex->id);
	 
	 if (current_edge->f1==f) current_edge=current_edge->n1;
	 else current_edge=current_edge->n2;
	 
	 if (current_edge->v1==current_vertex) current_vertex=current_edge->v2;
	 else current_vertex=current_edge->v1;
  } while (current_edge!=f->e);
}

• Egy ciklussal számon tartjuk, melyik élnél tartunk, és mindegyik lépésben kiírjuk az él és a következő él közös csúcsát. A következő él mindig az n1 vagy n2, attól függően, melyik határolja az f lapot. A ciklus előtt azt keressük meg, hogy melyik csúcs közös a következő lappal. Akkor állunk meg, mikor visszajutottunk a kiinduló élhez.
• Wikipédia: szárnyas él

30. Mik az Euler operátorok és miért van rájuk szükség?

31. Írjon C++ nyelven egy CSG fát megvalósító osztályt.

• A CSG fa testeket ír le. A fában a levelek egyszerű testek (gömb, kocka), ezek vannak összekombinálva geometriai transzformációkkal és halmazműveletekkel (metszet, unió, különbség). Pl. egy eltolt gömb és egy kocka unióját leíró fa gyökere egy "unió" node, az egyik gyereke egy kocka, a másik egy transzformáció, aminek egy gyereke egy gömb. A CSG fánál általában egyszerű eldönteni egy-egy pontról, hogy a testen belül van-e, de nehéz kirajzolni a testet.
• Itt csak az osztályok kis része van megírva, hogy látszódjon az egésznek a szerkezete, a Primitive-nek pedig jóval több leszármazottja is lehetne.

class CSG {
};

class Transformed: public CSG {
  private:
	 Transformation t;
	 CSG* obj;
};

class Composite: public CSG {
};

class Intersection: public Composite {
  private:
	 CSG *obj1, *obj2;
};

class Union: public Composite {
  private:
	 CSG *obj1, *obj2;
};

class Difference: public Composite {
  private:
	 CSG *obj1, *obj2;
};

class Primitive: public CSG {
};

class Sphere: public Primitive {
  private:
	 float r;
	 Vector center;
};

class Cube: public Primitive {
  private:
	 Vector min;
	 Vector max;
};

32. Adott egy 9 vezérlőpontra illeszkedő 3x3-as Bézier felület. A vezérlőpontok rendre p11,...,p33. Adja meg a felület normálvektorát a (0, 0.5) paraméterértékek mellett! Hogyan változik az előző feladatban kiszámolt normálvektor, ha a vezérlőpontokat a $\left[{\begin{array}{rrrr}2&0&0&0\\0&3&0&0\\0&0&4&0\\6&7&8&1\end{array}}\right]$ homogén lineáris transzformációs mátrixszal megszorozzuk?

33. Számítsa ki a harmadrendű (azaz MÁSODFOKÚ) uniform B-spline görbe bázisfüggvényeinek értékét a 0.8 értékre! Segítség: a Cox-deBoor módszert érdemes alkalmazni, és ellenőrzésképpen meg lehet nézni a konvex burok tulajdonságot.

• Wikipédia: Cox-de Boor algoritmus

34. Adott egy $rAr^{T}=0$ (r=(x,y,z,1) sorvektor és A 4x4-es mátrix) kvadratikus felület, valamint azon egy p pont. Írja fel a felület normálvektorát a p pontban.

• Belátható, hogy egy f(x, y, z)=0 implicit alakkal megadott felület normálvektora az (x, y, z) pontban $grad(f)=\left({\frac {\partial f}{\partial x}},{\frac {\partial f}{\partial y}},{\frac {\partial f}{\partial z}}\right)$ Szintén belátható, hogy mátrixszorzatot hasonló szabály szerint lehet deriválni, mint rendeset: egy n tényezős szorzat deriváltja egy n tagú összeg lesz, mindegyikben az egyik tényező deriválva, a többi békén hagyva. Itt, mivel az A mátrix konstans, ezért pl. ${\frac {\partial f}{\partial x}}=\left[{\begin{array}{rrrr}1&0&0&0\end{array}}\right]\cdot A\cdot \left[{\begin{array}{rrrr}x&y&z&1\end{array}}\right]^{T}+\left[{\begin{array}{rrrr}x&y&z&1\end{array}}\right]\cdot A\cdot \left[{\begin{array}{rrrr}1&0&0&0\end{array}}\right]^{T}=(a_{11}x+a_{12}y+a_{13}z+a_{14})+(a_{11}x+a_{21}y+a_{31}z+a_{41})=(a_{11}+a_{11})x+(a_{12}+a_{21})y+(a_{13}+a_{31})z+(a_{14}+a_{41})$
• Felírva a többi parciálist is, látható, hogy a normálvektorban r van megszorozva az A mátrixnak és transzponáltjának összegével, illetve ennek az összegnek csak a bal oldali 4x3-mas részmátrixával. Így a normálvektor (normalizálás nélkül): $n(r)=r(A+A^{T})_{4x3}$

35. Adott egy Bézier felület c00,...,c44 vezérlőpontokkal. Írja fel a felület normálvektorát a (0.5,0.5) paraméterértékeknél.

• A Bézier felület leírása: $r(u,v)=\sum _{i=0}^{n}\sum _{j=0}^{m}B_{n,i}(u)B_{m,j}(v)c_{ij}$ ha nxm vezérlőpontunk van, és $B_{n,i}(t)={n \choose i}t^{i}(1-t)^{n-i}$ az i-edik n-edrendű Bézier-bázisfüggvény. A felület normálvektora a két paraméter szerinti parciális derivált vektorszorzata. Az u szerinti parciális: ${\frac {\partial r}{\partial u}}=\sum _{i=0}^{n}\sum _{j=0}^{m}{n \choose i}(iu^{i-1}(1-u)^{n-i}-u^{i}(n-i)(1-u)^{n-i-1})B_{m,j}(v)c_{ij}$, a v szerinti: ${\frac {\partial r}{\partial v}}=\sum _{i=0}^{n}\sum _{j=0}^{m}B_{n,i}(u){m \choose j}(jv^{j-1}(1-v)^{m-j}-v^{j}(m-j)(1-v)^{m-j-1})c_{ij}$
• Behelyettesítve u=v=0.5-öt és n=m=4-et: ${\frac {\partial r}{\partial u}}{\Big |}_{u=v=0.5}=0.5^{7}\sum _{i=0}^{4}\sum _{j=0}^{4}{4 \choose i}(2i-4){4 \choose j}c_{ij}$ és ${\frac {\partial r}{\partial v}}{\Big |}_{u=v=0.5}=0.5^{7}\sum _{i=0}^{4}\sum _{j=0}^{4}{4 \choose i}(2j-4){4 \choose j}c_{ij}$
• Ezek vektoriális szorzata, felhasználva a vektorszorzat linearitását: $n=0.5^{14}\sum _{i=0}^{4}\sum _{j=0}^{4}\sum _{k=0}^{4}\sum _{l=0}^{4}{4 \choose i}{4 \choose j}{4 \choose k}{4 \choose l}(2i-4)(2l-4)c_{ij}\times c_{kl}$
• Megjegyzés: ez se valami egyszerű alak, de szerintem nem is lehet ennél egyszerűbben, mivel a "bármely két vezérlőpont vektorszorzata valamilyen súllyal" dolgot nem lehet belőle eltüntetni.
• Wikipédia: Bézier felület
• Wikipédia: felületi normális

-- G - 2008.12.25.