PótZH 2006. 12. 07., B csoport, első turnus

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.

18:15-18:45

Adott egy szakasz két végponttal a modell-koordinátarendszerben: (1,1,-3) és (1,1,3). Van egy transzformációs mátrixunk, ami modellből visz világkoordinátába:

$T_m=\left[\begin{array}{rrrr}3& 0& 0& 0\\ 0& 3& 0& 0\\ 0& 0& 3& 0\\ 0& 0& 0& 3\\ \end{array}\right]$

És van egy másik transzformációs mátrixunk, ami világkoordinátákból visz normalizált eszközkoordinátákba:

$T_{proj}=\left[\begin{array}{rrrr}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& -1\\ 0& 0& 2& 0\\ \end{array}\right]$

Mely pixeleket színezi ki a DDA szakaszrajzoló algoritmus, ha a viewport felbontása 6x6?

-- Mezzanine - 2006.12.07.

Megoldás:

A két mátrixot össze kell szorozni, majd a homogén koordinátás pontokkal balról meg kell szorozni.

$\left[\begin{array}{rrrr}3& 0& 0& 0\\ 0& 3& 0& 0\\ 0& 0& 3& 0\\ 0& 0& 0& 3\\ \end{array}\right]*\left[\begin{array}{rrrr}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& -1\\ 0& 0& 2& 0\\ \end{array}\right]=\left[\begin{array}{rrrr}3& 0& 0& 0\\ 0& 3& 0& 0\\ 0& 0& 3& -3\\ 0& 0& 6& 0\\ \end{array}\right]$

Ezzel a konkatenált mátrixszal szorozzuk meg balról az egyes pontokkal. A pontokat előtte természetesen homogén koordinátára alakítjuk, azaz mögé csapunk egy 1-est. A transzformációk után a pontok:

$p_1=\left[\begin{array}{rrrr}3& 3& -3& 9\\ \end{array}\right]$ javította: adamo
$p_2=\left[\begin{array}{rrrr}3& 3& 15& -9\\ \end{array}\right]$

A vágást a homogén koordinátarendszerben kell elvégezni, hiszen látszik, hogy átfordulás lesz (a negyedik koordináta a kettő pont között 9-ről -9-re vált, tehát a 0-t érinti!). Írjuk fel a vágósíkokat, illetve hogy azok szerint az egyes pontok a sík jó oldalán vannak, avagy sem.

Vágósíkok	[x,y,z,h]=[3,3,-3,9]	[x,y,z,h]=[3,3,15,-9]
$x\le h$	bent	kint
$x\ge -h$	bent	kint
$y\le h$	bent	kint
$y\ge -h$	bent	kint
$z\le h$	bent	kint
$z\ge -h$	bent	bent

Jól látszik, hogy $p_1=[3,3,-3,9]$ belső pont, hiszen minden vágósík szerint belülre esik. Ezután azon sorokra, ahol valamely pont kiesik a síkból, el kell végeznünk a megfelelő síkra történő vágást. Írjuk fel a szakasz egyenletét a koordinátákra külön-külön:

$x=3t+3(1-t)$
$y=3t+3(1-t)$
$z=-3t+15(1-t)$
$h=9t-9(1-t)$

Most nézzük meg, hogy az egyes vágósíkokkal való metszetüknél $t$ milyen értéket vesz fel!

$x=h⟹3t+3(1-t)=9t-9(1-t)⟹t=\frac{2}{3}$
$x=-h⟹3t+3(1-t)=-9t+9(1-t)⟹t=\frac{1}{3}$
$y=h⟹3t+3(1-t)=9t-9(1-t)⟹t=\frac{2}{3}$
$y=-h⟹3t+3(1-t)=-9t+9(1-t)⟹t=\frac{1}{3}$
$z=h⟹-3t+15(1-t)=9t-9(1-t)⟹t=\frac{2}{3}$

A fentiekből tehát kiderül, hogy a szakaszunk két helyen is metszi a vágósíkokat. Igen ám, de honnan tudjuk, hogy melyik metszéspont az, amelyik minket érdekel? Tudjuk, hogy a $p_1$ a belső pont. Ha a szakasz egyenletébe behelyettesítjük a $t=\frac{1}{3}$ értéket, akkor azt kapjuk, hogy a levágott ${p_2}^{\prime }$ pont koordinátái: $[x,y,z,h]=[3,3,-9,-3]$. Ugyanezt $t=\frac{2}{3}$-ra kiszámolva kapjuk, hogy ${p_2}^{″}=[3,3,3,3]$.

Megjegyzés: Szerintem egy apró számítási hiba miatt ${p_2}^{\prime }$ pont koordinátái: $[x,y,z,h]=[3,3,9,-3]$. -- Bandita - 2008.06.03.

Képzeljünk el egy kockát, amelyben van egy $p_1$ belső pontunk és egy olyan szakasz indul ki belőle, amely két helyen is metsz (nyilván két különböző) síkot. Hogyan lehetséges ez? Úgy, hogy igazából nem egy kockára vágunk, hanem a kockát határoló síkokra! Nyilván az lesz a számunkra érdekes metszéspont, amely a belső ponthoz közelebb esik (a másik metszéspont ugyanis már a kockán kívül, annak egyik lapja által kijelölt síkkal való metszést jelenti!). Meg kell határoznunk tehát $(d(p_1,{p_2}^{\prime })$ és $d(p_1,{p_2}^{″}))$ távolságot, és az a pont lesz a jó nekünk, amelyre ez a távolságmérték kisebb. Emlékeztető: vektorok távolságát úgy számítjuk, hogy a koordinátánkénti különbségek négyzetét összegezzük, majd az egész összegnek a gyökét vesszük.

$d(p_1,{p_2}^{\prime })=\sqrt{(3-3{)}^2+(3-3{)}^2+(-3-(-9){)}^2+(9-(-3){)}^2}=$ $\sqrt{36+144}=13.41$
$d(p_1,{p_2}^{″})=\sqrt{(3-3{)}^2+(3-3{)}^2+(-3-3{)}^2+(9-3{)}^2}=\sqrt{36+36}=8.48$

Megjegyzés: Mivel ${p_2}^{\prime }$ pont koordinátái: $[x,y,z,h]=[3,3,9,-3]$, ezért $d(p_1,{p_2}^{\prime })=\sqrt{(3-3{)}^2+(3-3{)}^2+(-3-9{)}^2+(9-(-3){)}^2}=$ $\sqrt{144+144}=16.97$
Szerencsére ez nem befolyásolja a feladat további megoldását :) -- Bandita - 2008.06.03.

Ebből látható, hogy a ${p_2}^{″}$ lesz a metszéspont, amit kerestünk, vagyis a síkokra vágott pontunk $p_2=[3,3,3,3]$-ban lesz.

Így a szakasz két végpontja a vágás, illetve homogén osztás után:

$p_1=[\frac{1}{3},\frac{1}{3},-\frac{1}{3}]$
$p_2=[1,1,1]$

A képernyőkoordinátarendszerben a szakaszt a következőképpen kapjuk meg:

$X_w=(X_d+1)\frac{V_{sx}}{2}+V_x$
$Y_w=(Y_d+1)\frac{V_{sy}}{2}+V_y$

A $p_1$ pont a képernyőn:
$X_{w1}=(\frac{1}{3}+1)\cdot 3=4$
$Y_{w1}=(\frac{1}{3}+1)\cdot 3=4$

A $p_2$ pont a képernyőn:
$X_{w2}=(1+1)\cdot 3=6$
$Y_{w2}=(1+1)\cdot 3=6$

Így a szakaszrajzoló algoritmus a (4,4), (5,5) és (6,6) pixeleket fogja kiszínezni. A vágósíkokkal való metszésszámításnál egyébként már látszódott, hogy a szakasz mind az x, mind az y (sőt, a z) vágósíkokat is ugyanazon $t=\frac{2}{3}$ paraméternél metszi, azaz éppen a képernyő jobb felső sarkán hagyja el a képernyőt.

-- NeoXon - 2006.12.08.

Megjegyzés: Ebben a gondolatmenetben egy apró hiba, hogy a vágósikok pontos számítása:

$\begin{array}{r}-1\le Xh/h\le 1\\ -1\le Yh/h\le 1\\ -1\le Zh/h\le 1\\ \end{array}$

Azaz, ha h>0:

$\begin{array}{r}-h\le Xh\le h\\ -h\le Yh\le h\\ -h\le Zh\le h\\ \end{array}$

ha h<0:

$\begin{array}{r}-h\ge Xh\ge h\\ -h\ge Yh\ge h\\ -h\ge Zh\ge h\\ \end{array}$

Ebből pedig:

Vágósíkok	[x,y,z,h]=[3,3,-3,9]	[x,y,z,h]=[3,3,15,-9]
$x\le h$	bent
$x\ge -h$	bent
$y\le h$	bent
$y\ge -h$	bent
$z\le h$	bent
$z\ge -h$	bent
$x\ge h$		bent
$x\le -h$		bent
$y\ge h$		bent
$y\le -h$		bent
$z\ge h$		bent
$z\le -h$		kint

De ez nem befolyásolja a végeredményt, szerencsére :)

-- Gyenö - 2007.10.29.