Grafika !PótZH 2007.12.06, B csoport, első turnus

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

1. Írjon C++ programot, ami az alább megadott felületet egy sugárral elmetszi. Visszatérési értéke bool, amiben jelzi, hogy van-e metszéspont. Továbbá számolja ki a program, a metszéspont koordinátáit, és abban a pontban a felület normálisát (normális számolása: 3pont). A felület: [math] x(u,v) = u+v \]\[ y(u,v) = u-v \]\[ z(u,v) = u*v [/math]

• Határozzuk meg, hogy milyen képlettel dönthető el, hogy egy [math] \underline{s}(x_s, y_s, z_s) [/math] pontból induló, [math] \underline{d}(x_d, y_d, z_d) [/math] irányvektorú sugár metszi-e a felületet. Akkor létezik metszéspont, ha az [math] (x(u, v), y(u, v), z(u, v))=\underline{s}+\underline{d}*t [/math] vektoregyenletnek van megoldása (az ismeretlenek: t, u, v). A két vektor akkor egyenlő, ha mindegyik komponensük egyenlő: [math] u+v=x_s+x_d*t,\; u-v=y_s+y_d*t,\; u*v=z_s+z_d*t [/math] Az első két egyenletből u és v kifejezhető t-vel, ezt behelyettesítjük a harmadikba, és t-re rendezzük: [math] t^2(x_d^2-y_d^2)+t(2x_sx_d-2y_sy_d-z_d)+(x_s^2-y_s^2-z_s)=0 [/math], és akkor van metszéspont, ha a diszkrimináns nemnegatív, és a gyökök közül legalább az egyik nemnegatív (csak a pozitív t jelenti azt, hogy a sugár "az elindulása után" metszi a felületet).
• Ha már megvan a megfelelő t (a nemnegatív gyök, ha kettő van, a kisebbik), kiszámoljuk belőle a metszéspontot, u-t és v-t (pl. az egyenletrendszer első két egyenletének felhasználásával), majd u és v ismeretében a normálist. A normálist úgy kapjuk meg, hogy vesszük a felületet leíró vektorfüggvénynek (x(u, v), y(u, v), z(u, v) a vektor három komponense) az u és v szerinti parciális deriváltjait (ez szintén két vektor), majd ezek vektoriális szorzatát.
• Az u szerinti parciális derivált: [math] (1, 1, v) [/math], a v szerinti: [math] (1, -1, u) [/math]
• A kódban feltételezem, hogy rendelkezésre áll egy Vector osztály, értelmezve vannak rá a szokásos összeadás, kivonás, skalárral szorzás, skaláris szorzat (* operátor) és vektoriális szorzat (% operátor) műveletek. A normálist és a metszéspontot a függvény pointerek segítségével adja vissza.

bool intersect(Vector source /* a sugár forrása */, Vector dir /* a sugár iránya */, \
Vector* point /* ide tárolja a metszéspontot */, Vector* normal /* ide tárolja a normálist */) {
  double a, b, c; /* a t-re vonatkozó másodfokú egyenlet együtthatói */
  double disc;	 /* a t-re vonatkozó egyenlet diszkriminánsa */
  double t1, t2;  /* a t-re vonatkozó egyenlet két gyöke */
  double t;		 /* a legközelebbi metszéspont t-je (a legkisebb pozitív gyök) */
  double u, v;	 /* a metszésponthoz tartozó paraméterértékek */
  Vector u_part, v_part;  /* a metszéspontban a parciális deriváltak */
  a=dir.x*dir.x-dir.y*dir.y;
  b=2*source.x*dir.x-2*source.y*dir.y-dir.z;
  c=source.x*source.x-source.y*source.y-source.z;
  disc=b*b-4*a*c;
  if (disc < 0) return false; /* negatív a diszkrimináns, nincs metszéspont */
  t1=(-b+sqrt(disc))/(2*a);
  t2=(-b-sqrt(disc))/(2*a);
  if (t1<0 && t2<0) return false; /* nincs pozitív gyök */
  if (t1<0) t=t2;
  else t=t1;
  (*point)=source+dir*t;
  u=((*point).x+(*point).y)/2;
  v=((*point).x-(*point).y)/2;
  u_part=Vector(1, 1, v);
  v_part=Vector(1, -1, u);
  (*normal)=u_part%v_part;
  return true;
}

2. Mit csinál (milyen műveletet) egy ponttal az alábbi transzformáció? Milyen tulajdonságok igazak rá (egyenest egyenesbe képez, affin, szögtartó, aránytartó, stb. 1 pont)? [math] \left[ \begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 2 & 2 & 2 & 2 \end{array} \right] [/math]

• Grafikában sorvektorokkal dolgozunk, amiket mátrixokkal jobbról szorzunk. Ha egy mátrix utolsó oszlopában az utolsó érték nemnulla, a többi pedig nulla, akkor affin transzformációval van dolgunk (ugyanis, a w komponenst biztosan nem nullázza ki, ha nulla volt, akkoor viszont nulla marad, tehát ideális pont ideálisba, nemideális nemideálisba megy, és az ilyen projektív transzformációk affinok is). Ilyenkor a bal felső 3x3mas mátrix adja meg a lineáris részt, a legalsó sor első három eleme pedig az eltoló részt, a jobb alsó elem pedig azt, hogy w hányszorosára változik. Mivel a projektív térből a szokványosba úgy lehet visszatérni, hogy az x, y, z komponenseket leosztjuk w-vel, ezért, ha egy projektív transzformációban mindegyik elemet ugyanannyiszorosára változtatjuk, akkor a transzformációnak ugyanaz lesz a végeredménye. Mivel a legkényelmesebb, ha w értéke nem változik, ezért osszuk le a mátrixot kettővel. Ekkor már mondhatjuk azt, hogy a lineáris rész felére zsugorítás, az eltolás pedig (1, 1, 1)-gyel tol el. Vagyis a transzformáció először felére zsugorít, majd eltol (1, 1, 1)-gyel.
• A tulajdonságok: egyenest egyenesbe képez (ez minden projektív transzformációra igaz), affin, szögtartó (mert csak kicsinyítés és eltolás van benne), aránytartó (ugyanemiatt). Lehetne még: nem lineáris (az eltolás miatt), nem "térfogat-tartó" (a kicsinyítés miatt), körüljárási irány-tartó (a vals felső mátriy determinánsának pozitív az előjele).

-- G - 2008.12.23.

-- Boci - 2007.12.13.