Koordinátatengelyek forgatása a térben. A forgatási mátrixok ábrázolása Euler-szögekkel
A 2D-s térben az elforgatás egyetlen szöggel leírható a következő, derékszögű, derékszögű lineáris transzformációs mátrixszal:
Az elforgatást úgy hajtjuk végre, hogy a forgatási mátrixot megszorozzuk egy, az elforgatott pontot leíró oszlopvektorral:
.
Az (x, y) pont elforgatásának eredményeként kapott koordináták (x, y") így néznek ki:
Ebben az esetben a pozitív szögek a vektor óramutató járásával ellentétes forgásának felelnek meg a szokásos, jobbos koordinátarendszerben, és az óramutató járásával megegyező irányban a balos koordinátarendszerben.
[szerkesztés] Forgatási mátrix a 3D térben
Forgatási mátrixok a derékszögű koordinátarendszer tengelye körül egy szöggel α három dimenzióban a következők:
· Forgatás az x tengely körül:
,
Elforgatás az y tengely körül:
,
· Forgatás a z tengely körül:
.
Ebben az esetben a pozitív szögek megfelelnek a vektor jobb oldali koordinátarendszerben az óramutató járásával ellentétes, bal oldali koordinátarendszerben az óramutató járásával megegyező irányba történő elforgatásának, ha a forgási síkot a féltér oldaláról nézzük, ahol az értékek azon tengely koordinátái, amely körül a forgatást végrehajtják, pozitívak. A megfelelő koordinátarendszer a megfelelő alap kiválasztásához kapcsolódik (lásd gimlet szabály).
A forgási mátrix tulajdonságai.
A forgási mátrix tulajdonságai
Ha egy mátrix, amely egy tengely körüli elforgatást határoz meg ϕ szöggel, akkor:
(forgási mátrix nyoma)
(a mátrixnak van egységhatározója).
Ha a mátrix sorait (vagy oszlopait) a vektorok koordinátáinak tekintjük, akkor a következő összefüggések igazak:
o
· A fordított forgási mátrixot az előre forgó mátrix szokásos transzpozíciójával kapjuk, pl. .
24. Bresenham-algoritmus szegmensraszterizáláshoz.
Bresenham algoritmusa(Angol) Bresenham vonalalgoritmusa) egy olyan algoritmus, amely meghatározza, hogy a kétdimenziós raszter mely pontjait kell árnyékolni, hogy két adott pont közötti egyenes közelítését kapjuk. Ez az egyik legrégebbi algoritmus a számítógépes grafikában – Jack E. Bresenham (Jack E. Bresenham) fejlesztette ki az IBM-nél 1962-ben. Az algoritmust széles körben használják, különösen vonalak rajzolására a számítógép képernyőjén. Létezik a Bresenham-algoritmus általánosítása a másodrendű görbék készítésére.
Algoritmus
Két pont között szakaszt húzunk - ( x 0 ,y 0) és ( x 1 ,y 1), ahol ezek a párok egy oszlopot és egy sort tartalmaznak, amelyek száma jobbra és lefelé növekszik. Először feltételezzük, hogy a vonalunk lefelé és jobbra megy a vízszintes távolsággal x 1 − x A 0 jobban teljesít, mint a függőleges y 1 − y 0, azaz a vonal lejtése a vízszintestől kisebb, mint 45°. Célunk minden oszlopra vonatkozik x között x 0 és x 1 , határozza meg, melyik sort y a vonalhoz legközelebb, és rajzoljon egy pontot ( x,y).
A két pont közötti egyenes általános képlete:
Mivel ismerjük az oszlopot x, majd a vonal y a következő értéket egész számra kerekítve kapjuk:
Ennek a kifejezésnek a pontos értékét azonban nem szükséges kiszámítani. Elég ezt megjegyezni y től nő y 0 és minden egyes lépéshez hozzáadjuk x egység, és add hozzá y lejtő értéke
ami előre kiszámítható. Sőt, minden lépésnél két dolgot teszünk: vagy megtartjuk ugyanazt y vagy növeld 1-gyel.
A kettő közül melyiket válasszam - nyomon követéssel lehet eldönteni hibaérték, ami azt jelenti - az aktuális érték közötti függőleges távolság yés pontos érték yáramhoz x. Valahányszor növeljük x, növeljük a hibaértéket a meredekség mértékével s felett. Ha a hiba meghaladja a 0,5-öt, a sor közelebb került a következőhöz y, tehát növeljük y eggyel, miközben a hibaértéket 1-gyel csökkentjük. Az alábbi algoritmus megvalósításában a plot(x,y) pontot rajzol, az abs pedig a szám abszolút értékét adja vissza:
funkció sor(x0, x1, y0, y1) int deltax:= abs(x1 - x0) int deltay:= abs(y1 - y0) igazi hiba:= 0 igazi deltaerr:= deltay / deltax int y:= y0 számára x tól től x0 nak nek ha hiba >= 0,5 y:= y + 1 hiba:= hiba - 1,0Ezzel a megközelítéssel az a probléma, hogy valós értékekkel, mint például hiba és deltaerr, a számítógépek viszonylag lassúak. Ezenkívül a lebegőpontos számítások hibákat halmozhatnak fel. Ezen okok miatt a legjobb, ha csak egész számokkal dolgozunk. Ez megtehető a deltax által használt összes valós érték megszorzásával. A probléma csak a 0,5 konstanssal van - de ebben az esetben elég az egyenlőtlenség mindkét oldalát megszorozni 2-vel. A következő kódot kapjuk:
funkció sor(x0, x1, y0, y1) int deltax:= abs(x1 - x0) int deltay:= abs(y1 - y0) int hiba:= 0 int deltaerr:= deltay int y:= y0 számára x tól től x0 nak nek x1 plot(x,y) error:= hiba + deltaerr ha 2 * hiba >= deltax y:= y + 1 hiba:= hiba - deltaxAz egész számok 2-vel való szorzása a bit balra tolásával valósul meg.
Most gyorsan megrajzolhatunk 1-nél kisebb meredekségű egyeneseket jobbra lefelé. Marad az algoritmus kiterjesztése minden irányban történő rajzolásra. Ezt tükörreflexiókkal érik el, pl. előjelváltás (az 1. lépést -1 váltja fel), változócsere xÉs y, a szakasz eleje koordinátáit felcserélve a végének koordinátáival.
[szerkesztés] Vonalak rajzolása
Megvalósítás C++ nyelven:
Void drawLine(int x1, int y1, int x2, int y2)( int deltaX = abs(x2 - x1); int deltaY = abs(y2 - y1); int jelX = x1< x2 ? 1: -1; int signY = y1 < y2 ? 1: -1; int error = deltaX - deltaY; for (;;) { setPixel(x1, y1); if(x1 == x2 && y1 == y2) break; int error2 = error * 2; if(error2 >-deltaY) ( hiba -= deltaY; x1 += jelX; ) if(hiba2< deltaX) { error += deltaX; y1 += signY; } }}
25. Bresenham-algoritmus egy kör raszterizálására.
Körök rajzolása
Létezik Bresenham algoritmusa is a körök rajzolására. Építési módszerében hasonló a vonal rajzolásához. Ebben az algoritmusban az első kvadránshoz körívet készítünk, a többi kvadránshoz pedig szimmetrikusan kapjuk meg a körpontok koordinátáit. Az algoritmus minden lépésében három pixelt veszünk figyelembe, és ezek közül választjuk ki a legmegfelelőbbet úgy, hogy összehasonlítjuk a középpont és a kiválasztott pixel távolságát a kör sugarával.
// R - sugár, X1, Y1 - a középpont koordinátái int x:=0 int y:= R int delta:= 2 - 2 * R int hiba:= 0 míg(y >= 0) rajzolási pixel(X1 + x, Y1 + y) rajzolási képpont (X1 + x, Y1 - y) rajzolási képpont (X1 - x, Y1 + y) rajzolási képpont (X1 - x, Y1 - y) hiba = 2 * (delta + y) - 1 ha((delta< 0) && (error <= 0)) delta += 2 * ++x + 1 folytatni hiba = 2 * (delta - x) - 1 ha((delta > 0) && (hiba > 0)) delta += 1 - 2 * --y folytatni x++ delta += 2 * (x - y) y--
Void drawCircle(int x0, int y0, int sugár) ( int x = 0; int y = sugár; int delta = 2 - 2 * sugár; int hiba = 0; while(y >= 0) ( setPixel(x0 + x) , y0 + y); setPixel(x0 + x, y0 - y); setPixel (x0 - x, y0 + y); setPixel(x0 - x, y0 - y); hiba = 2 * (delta + y) - 1 ;if(delta< 0 && error <= 0) { ++x; delta += 2 * x + 1; continue; } error = 2 * (delta - x) - 1; if(delta >0 && hiba > 0) ( --y; delta += 1 - 2 * y; folytatás; ) ++x; delta += 2* (x - y); --y; ))
Wu simító algoritmusa.
Wu algoritmus egy szegmens simítással raszterré bontására szolgáló algoritmus. Wu Xiaolin javasolta ( Xiaolin Wu, innen ered az algoritmus jól bevált neve oroszul) a Computer Graphics magazin 1991 júliusában megjelent cikkében. Az algoritmus ötvözi a kiváló minőségű kereskedést és a Bresenham-algoritmushoz közeli sebességet élsimítás nélkül.
Algoritmus
A vízszintes és függőleges vonalak nem igényelnek élsimítást, ezért külön rajzolják meg őket. A fennmaradó vonalakat Wu algoritmusa a főtengely mentén bejárja, és a koordinátákat a nem fő tengely mentén illeszti a Bresenham-algoritmushoz hasonló módon. A különbség az, hogy Wu algoritmusában minden lépésnél nem egy, hanem két pont van beállítva. Például ha a főtengely az x, akkor az (x, y) és (x, y + 1) koordinátájú pontokat veszi figyelembe. A hiba nagyságától függően, amely megmutatja, hogy a pixelek milyen messze mentek el az ideális vonaltól a melléktengely mentén, az intenzitás e két pont között oszlik meg. Minél távolabb van a pont az ideális vonaltól, annál kisebb az intenzitása. Két pixel intenzitásértékei mindig egyet adnak, vagyis ez egy pixel intenzitása pontosan az ideális vonalon. Egy ilyen eloszlás ugyanazt az intenzitást adja a vonalnak a teljes hosszában, miközben azt az illúziót kelti, hogy a pontok nem ketten, hanem egyenként helyezkednek el a vonal mentén.
Az algoritmus eredménye
Megvalósítás pszeudokódban (csak x-line esetén):
funkció plot(x, y, c) van // rajzol egy pontot koordinátákkal (x, y) // és c fényerővel (ahol 0 ≤ c ≤ 1) funkció rész (x) a visszatérés x egész része funkció kör (x) a visszatérés ipart (x + 0,5) // kerekítés a legközelebbi egész számra funkció fpart(x) a visszatérés tört x funkció rajzol_vonal(x1,y1,x2,y2) az, ha x2< x1 akkor csere(x1, x2) csere(y1, y2) vége ha dx:= x2 - x1 dy:= y2 - y1 gradiens:= dy ÷ dx // folyamat kezdőpontja xend:= kerek(x1) yend:= y1 + gradiens × (xend - x1) xgap:= 1 - fpart(x1 + 0,5) xpxl1:= xend ypxl1:= ipart(yend) plot(xpxl1, ypxl1, 1 - fpart(yend) × xgap) plot(xpxl1, ypxl1 + 1, fpart(yend) × xgap) intery:= yend + gradiens // hurok első y-metszéspontja // kezeli a végpontot xend:= kerek(x2) yend:= y2 + gradiens × (xend - x2) xgap:= fpart(x2 + 0,5) xpxl2:= xend // a fő ciklusban lesz használva ypxl2:= ipart(yend) plot(xpxl2, ypxl2, 1 - fpart(yend) × xgap) plot(xpxl2, ypxl2 + 1, fpart(yend) × xgap) // főhurok számára x tól től xpxl1 + 1 nak nek xpxl2 - 1 csináld telek(x, rész(köz), 1 - fpart(köz)) telek(x, ipart(köz) + 1, fpart(köz)) intery:= intery + gradiens ismétlés funkció26. Árnyékoló algoritmusok.
Árnyékolási algoritmus
Az árnyékolási algoritmust nagyon gyakran használják a számítógépes grafikában a határokkal rendelkező alakzatok árnyékolására. Ennek az algoritmusnak lehet más alkalmazása is, például egy test tömegközéppontjának megkeresésére használható a képéről.
2D bittérképes algoritmusok: Árnyékolás
Tekintsünk algoritmusokat egy tetszőleges kontúr festésére, amely már raszterben van megrajzolva. Először egy pixelt találunk az alakzat körvonalában. Módosítsa ennek a képpontnak a színét a kívánt kitöltési színre. Ezután az összes szomszédos pixel színét elemzi. Ha valamelyik szomszédos képpont színe nem egyezik meg a körvonal szegélyszínével vagy a kitöltő színével, akkor ennek a pixelnek a színe kitöltőszínre változik.
Egyszerű rekurzív kitöltés.
Pixel ProcedureFill (x, y, BColor, Color: Integer);
(x, y – magpont koordinátái, BColor – szegély színe,
Szín - kitöltési szín)
C:=GetPixel (x,y) (az aktuális pixelszín elemzése)
ha (C<>BColor) és (C<>Szín) akkor
PutPixel(x, y, szín);
PixelFill(x+1, y, BColor, Color);
PixelFill(x, y+1, BColor, Color);
PixelFill(x-1, y, BColor, Color);
PixelFill(x, y-1, BColor, Color);
Ez az algoritmus nem veremre optimalizált, és az egyik leglassabb festési algoritmus (átlagosan csak minden negyedik hívást használnak festésre). Az algoritmus nem tudja kitölteni a kitöltési szín által határolt területeket. Hasonló algoritmust készíthet rekurzió nélkül, ha verem helyett tömböket használ.
Algoritmus vonalakkal való festéshez.
1. Van egy magpont koordinátákkal (x st , y st)és a rekurzív hívások kezdeti cselekvési iránya dir=1. A bal és jobb oldali határok paraméterei kezdetben egybeesnek a magpont koordinátájával: x PL = x st , x PR = x st . Az eljárás ún LineFill, ahol:
2. Van x L és x R - bal és jobb oldali szegély, amelyek között megrajzolódik az aktuális vízszintes vonal.
3. Növekedés történik y=y+irés x L és x R között a pixelek színét elemzi felett vonal. Ha nem egyezik a kitöltési színnel, az eljárást LineFill-val rekurzívan hívják rendező = 1és x PL = x L , x LR = x R .
4. Növekedés történik y=y-dirés x L-től az előző x PL értékig kiindulva elemzi a vonal alatti képpontok színét. Ha a pixel színe eltér a kitöltési színtől, az eljárást rekurzív módon hívja meg dir = -1és x PL = x L , x PR = x R .
5.
Ugyanazon vízszintes vonal mentén haladva az előző x PR-től x R-ig a szín elemzése megtörténik alatt vonal. Ha bármely képpont színe eltér a kitöltés színétől, az eljárást rekurzív módon hívjuk meg dir = -1és x PL = x L , x PR = x R .
Az alábbiakban egy példa ennek az algoritmusnak a megvalósítására C++ nyelven:
void LineFill(int x, int y, int dir, int xPL, int xPR)
// ez a változó tárolja a pixel színét
// AKTUÁLIS HATÁROK BEÁLLÍTÁSA xL ÉS xR
szín = GetPixel(--xL,y);
// xL=xL-1 kerül a függvényhívásba
while (szín != bszín); // bcolor - szegélyszín
szín = GetPixel(++xR,y);
while (szín !=bszín);
Vonal (xL,y, xR,y, Mycolor);
//ez lehet bármilyen vonalrajzoló függvény
// A VONAL FÖLTI PIXELEK ELEMZÉSE
for (x=xL; x<=xR; x++) {
szín = GetPixel(x, y+dir);
ha (szín !=bszín)
x = LineFill(x, y+dir, dir, xL, xR);
// A BAL VONAL ALATT A PIXELEK ELEMZÉSE
for (x=xL; x<=xPL; x++) {
szín = GetPixel(x, y-dir);
ha (szín !=bszín)
// A JOBB oldali VONAL ALATT A PIXELEK ELEMZÉSE
for (x=xPR; x<=xR; x++) {
szín = GetPixel(x, y-dir);
ha (szín !=bszín)
x = LineFill (x, y-dir, -dir, xL, xR);
A programokban a LineFill függvényt a következőképpen hívják:
LineFill(xst, yst, 1, xst, xst);
Nyilvánvalóan vannak más hatékony kitöltési algoritmusok is. Például a kontúr matematikai leírását használó kitöltési algoritmusok a kitöltendő sokszög konkrét alakjához (pl. téglalap vagy kör) vannak társítva. Ebben az esetben előfordulhat, hogy a kontúr egyáltalán nem jelenik meg a raszterben. Ugyanakkor bármilyen textúra könnyen használható kitöltésként.
27. Algoritmus a Sutherland-Cohen szegmens levágására.
Cohen-Sutherland algoritmus(Angol) Cohen-Sutherland) egy algoritmus szegmensek vágására, azaz egy olyan algoritmus, amely lehetővé teszi a szegmens téglalapot metsző részének meghatározását. Dan Cohen és Ivan Sutherland fejlesztette ki a Harvardon 1966-1968 között, és az AFIPS konferencián tették közzé 1968-ban.
Az algoritmus leírása
Az algoritmus a síkot 9 részre osztja egyenes vonalakkal, amelyek a téglalap oldalait alkotják. Mind a 9 részhez négy bites kód tartozik. A bitek (a legalacsonyabbtól a legmagasabbig) azt jelentik, hogy „balra”, „jobbra”, „lent”, „felül”. Más szóval, a sík azon három részének, amelyek a téglalaptól balra vannak, a legkisebb jelentőségű bit 1, és így tovább.
Az algoritmus meghatározza a szegmens végpontjainak kódját. Ha mindkét kód nulla, akkor a szegmens teljesen a téglalapon belül van. Ha a bitenkénti ÉS kódok nem egyenlők nullával, akkor a szegmens nem metszi a téglalapot (mivel ez azt jelenti, hogy a szegmens mindkét végpontja a téglalap azonos oldalán van). Más esetekben az algoritmus kiválaszt egy végpontot a téglalapon kívül, megkeresi a szakasz legközelebbi metszéspontját a téglalap oldalait alkotó egyenesek egyikével, és ezt a metszéspontot használja a szakasz új végpontjaként. . A lerövidített szegmenst ismét átvezetjük az algoritmuson.
A 3D-s modell algoritmusának megvalósítása megegyezik a 2D-s megvalósítással, azzal a különbséggel, hogy négy bites kód helyett hatbites kódot használnak (további két bit mélység).
28. A középpont szerinti felosztás algoritmusa.
A forgatási mátrix a koordinátarendszer vagy objektum, jelenet elforgatására szolgál.
Forgatási mátrixok a főtengelyek körül.
Forgatási mátrix tetszőleges tengely körül.
Általánosított forgatási mátrix.
Kívánatos lenne az objektum térbeli helyzetét egyértelműen beállítani. Nyilvánvaló, hogy bármely pozíciót egyedileg határoz meg 3 különböző tengely körüli forgatás. De felmerül a kérdés, hogy milyen sorrendben forgassuk és hogyan válasszuk ki a tengelyeket?
Az általánosított forgatási mátrix többféleképpen adható meg. Egyrészt fix tengelyek körül forgathatjuk az objektumot. Másrészt az objektumhoz tartozó tengelyek körül lokálisnak is nevezik őket. Érdemes megjegyezni, hogy a mátrixszorzás művelete nem kommutatív, ezért a pozíció egyedi meghatározásához nem csak 3 szöget kell ismerni, hanem a mátrixszorzási sémát is.
2 népszerű séma létezik.
1) Forgatási mátrix az Euler-szögek alapján.
2) A forgási mátrix a repülőgép szögeiben (LA): yaw, pitch and roll (yaw, pitch and roll).
Tekintettel arra, hogy az első nagyszámú számítást igényel, a gyakorlatban általában a másodikat használják.
Forgatási mátrix az Euler-szögek alapján.
Az Euler-szögek három olyan szög, amelyek egyértelműen meghatározzák a merev test tájolását, és meghatározzák az átmenetet a rögzített koordinátarendszerből a mozgóba.
A mozgó koordinátarendszer egy testhez kapcsolódó koordinátarendszer. Néha azt mondják a fagylaltban a testben. Mielőtt megadnánk a szögek meghatározását, még egy dologra van szükségünk. A csomópontok vonala ON - az OXY és az Oxy sík metszésvonala
α (vagy φ) az Ox tengely és az ON tengely közötti szög. Értéktartomány )