Matrica rotacije u dvodimenzionalnom prostoru. Predstavljanje rotacijskih matrica kroz Ojlerove uglove Matrični oblik Ojlerove formule

Matrica rotacije(ili kosinusna matrica smjera) je ortogonalna matrica koja se koristi za izvođenje vlastite ortogonalne transformacije u Euklidskom prostoru. Kada se bilo koji vektor pomnoži sa matricom rotacije, dužina vektora je sačuvana. Determinanta matrice rotacije jednaka je jedan.
Obično se vjeruje da se, za razliku od prijelazne matrice pri rotaciji koordinatnog sistema (baze), kada se pomnože sa matricom rotacije vektora stupca, koordinate vektora transformiraju u skladu sa rotacijom samog vektora (i a ne rotacija koordinatnih osa, odnosno koordinate rotiranog vektora se dobijaju u istom fiksnom koordinatnom sistemu). Međutim, razlika između obje matrice je samo u predznaku kuta rotacije, a jedna se može dobiti od druge zamjenom kuta rotacije suprotnim; oba su međusobno inverzna i mogu se dobiti jedno od drugog transpozicijom.

Matrica rotacije u trodimenzionalnom prostoru

Bilo koja rotacija u trodimenzionalnom prostoru može se predstaviti kao kompozicija rotacija oko tri ortogonalne ose (na primjer, oko kartezijanskih koordinatnih osa). Ovaj sastav odgovara matrici koja je jednaka proizvodu odgovarajuće tri matrice rotacije.
Matrice rotacije oko ose kartezijanskog koordinatnog sistema za ugao α u trodimenzionalnom prostoru su:
Rotacija oko x ose:

Rotacija oko y ose:

Rotacija oko ose z:

Nakon transformacije dobijamo formule:
X osa
x'=x;
y’:=y*cos(L)+z*sin(L) ;
z’:=-y*sin(L)+z*cos(L) ;

Y osa
x’=x*cos(L)+z*sin(L);
y'=y;
z’=-x*sin(L)+z*cos(L);

Z osa
x’=x*cos(L)-y*sin(L);
y’=x*sin(L)+y*cos(L);
z'=z;

Sva tri zavoja se rade nezavisno jedan od drugog, tj.

ako je potrebno rotirati oko ose Ox i Oy, prvo se vrši rotacija oko ose Ox, a zatim se u odnosu na rezultujuću tačku vrši rotacija oko ose Oy.

U ovom slučaju, pozitivni uglovi odgovaraju rotaciji vektora u suprotnom smeru kazaljke na satu u desnom koordinatnom sistemu i u smeru kazaljke na satu u levom koordinatnom sistemu, kada se posmatra suprotno od smera odgovarajuće ose. Pravi koordinatni sistem je povezan sa izborom prave baze (vidi pravilo gimleta).

Geometrijske transformacije u trodimenzionalnom prostoru

Prijelaz iz jednog pravolinijskog koordinatnog sistema u trodimenzionalnom prostoru u drugi općenito se opisuje na sljedeći način:

ili u matričnom obliku:

Razmotrimo matrice koje odgovaraju sljedećim osnovnim geometrijskim transformacijama:

1. Okretanja

2. Napetost (kompresija):

3. Refleksija (zrcaljenje)

u odnosu na avion XOY

u odnosu na avion YOZ

u odnosu na avion ZOX

4. Prijenos (pomak, kretanje) u vektor

Bitan: transformacija tačke (uz očuvanje lokacije originalnog koordinatnog sistema) odgovara izvođenju inverzne operacije transformacije koordinatnog sistema. Na primjer, tačku rotacije pod nekim uglom u smjeru kazaljke na satu oko X ose odgovara rotacija koordinatnog sistemau smjeru suprotnom od kazaljke na satu pod istim uglom.

Sve ostale transformacije, osim gore navedenih, klasificirane su kao složene transformacije. Matrice kompleksnih transformacija se dobijaju pronalaženjem proizvoda matrica koje odgovaraju osnovnim geometrijskim transformacijama koje se moraju izvesti da bi se dobila željena kompleksna transformacija (*-množenje se izvodi striktno onim redom kojim se te osnovne transformacije izvode, budući da se transformacije su nekomutativni).

Kao primjer, razmotrite složenu transformaciju koja se sastoji od rotacije za ugao oko prave linije koja prolazi kroz tačku T(X, Y, Z) i imaju vektor smjera V(l, m, n), i l 2 +m 2 +n 2 =1, tj. vektor V je samac.

Transformaciju je potrebno razložiti na nekoliko elementarnih koraka (osnovne transformacije).

Cilj: rotirati koordinatni sistem tako da os Z poklopio sa V, nakon čega će biti moguće rotirati za ugao izvođenjem osnovne transformacije - rotacije za ovaj kut oko ose Z.

Da bismo postigli ovaj cilj, izvodimo sljedeći niz osnovnih transformacija:

Perspektivna slika se javlja sa centralnom projekcijom, tj. kada je centar projekcije (oko posmatrača) na konačnoj udaljenosti od ekrana.

Matrica transformacije perspektive sa projekcijom na ravan XOY:

,
gdje je C(0, 0, c) tačka lokacije posmatrača (projekcioni centar). Ravan projekcije, tj. ekran se poklapa sa koordinatnom ravninom XOY.

3.2. 3D transformacije i projekcije

Razmotrimo trodimenzionalni Dekartov koordinatni sistem, koji je desno.

Matrica rotacije

Prihvatimo konvenciju prema kojoj ćemo pozitivnim smatrati one rotacije u kojima (ako se gleda sa kraja poluose u smjeru početka) rotacija od 90° u smjeru suprotnom od kazaljke na satu će prevesti jednu poluosu u drugu. Na osnovu ove konvencije, napravljena je sljedeća tabela koja se može koristiti i za desnoruki i lijevoruki koordinatni sistem:

Rice. 3.6. Trodimenzionalni koordinatni sistem

Slično kao što je tačka na ravni opisana vektorom ( x,y), tačka u trodimenzionalnom prostoru je opisana vektorom ( x,y,z).

Kao iu dvodimenzionalnom slučaju, da bismo mogli implementirati trodimenzionalne transformacije pomoću matrica, prijeđimo na homogene koordinate:

[x,y,x,1] ili [ X,Y,Z,H]

[x*,y*,z* 1] = , gdje N#1, N¹0.

Generalizirana 4´4 matrica transformacije za trodimenzionalne homogene koordinate ima oblik

e. [ x,y,z, 1]*T(Dx,Dy,Dz)=[x+Dx,y+Dy,z+Dz, 1].

2. 3D zumiranje.

Hajde da razmotrimo djelomično promjena skale. Realizira se na sljedeći način:

Isti rezultat se može dobiti sa jednakim koeficijentima parcijalnih promjena skale. U ovom slučaju, matrica transformacije je:

4. 3D rotacija

Dvodimenzionalna rotacija o kojoj smo ranije govorili je u isto vrijeme i trodimenzionalna rotacija oko ose Z. U trodimenzionalnom prostoru, rotacija oko ose Z opisano matricom

R z()=

Matrica rotacije osi X izgleda kao

Podmatrica 3´3 se naziva ortogonalna, jer su njeni stupci međusobno ortogonalni jedinični vektori.

Matrice rotacije čuvaju dužinu i uglove, ali matrice skaliranja i translacije ne.

skinuti

Sažetak na temu:

Matrica rotacije

Plan:

1Rotacijska matrica u dvodimenzionalnom prostoru
2Matrica rotacije u trodimenzionalnom prostoru
3Svojstva matrice rotacije

Književnost

Uvod

Matrica rotacije(ili matrica kosinus smjera) je matrica čije množenje bilo kojeg vektora ne mijenja njegovu dužinu.

1.
Matrica rotacije

Matrica rotacije u dvije dimenzije

U dvodimenzionalnom prostoru, rotacija se može opisati jednim uglom θ sa sljedećom matricom linearne transformacije u kartezijanskom koordinatnom sistemu:

U ovom slučaju, pozitivni uglovi odgovaraju rotaciji u suprotnom smeru kazaljke na satu u uobičajenom desnorukom koordinatnom sistemu i u smeru kazaljke na satu u levom koordinatnom sistemu.

Sama rotacija se događa množenjem matrice rotacije vektorom koji opisuje rotiranu tačku:
.
2. Matrica rotacije u trodimenzionalnom prostoru

Matrice rotacije oko ose kartezijanskog desnog koordinatnog sistema za ugao α u trodimenzionalnom prostoru su:
, , ,
U trodimenzionalnom prostoru, možete koristiti

Matrice vektorske rotacije u kartezijanskom koordinatnom sistemu, koje odgovaraju prve dvije metode specificiranja rotacije:

Međutim, budući da množenje matrice nije komutativno, odnosno da će položaj koordinatnog sistema nakon rotacije oko tri ose zavisiti od redosleda rotacija, postoji 6 različitih tipova matrice rotacije:

1) Rotacija oko ose: X -> Y -> Z

2) Prema tome: X -> Z -> Y

3) Y -> X -> Z

4) Y -> Z -> X

5) Z -> X -> Y

6) Z -> Y -> X

Željena matrica se može dobiti sekvencijalnim množenjem matrica rotacije oko jedne ose (gore date) u skladu sa željenim redosledom.

3. Svojstva matrice rotacije

Ako je matrica koja specificira rotaciju oko ose za ugao φ, tada:

Književnost

Lurie A.I. Analitička mehanika - M.: Fizmatlit - 1961 - 824 str.

8.1.1. Transformacija koordinata u trodimenzionalnom prostoru.

Osnova programa za afine transformacije prostornih objekata, kao i njihove projekcije na ravan slike, je aparat homogenih koordinata (vidi, na primjer, LITERATURA). U ovom slučaju, sve koordinatne transformacije potrebne za konstruiranje projekcije i uspostavljanje željenog kuta opisane su matricama veličine 4 ´ 4 i predstavljene su u obliku superpozicije nekih osnovnih transformacija: prijenos točke u prostoru na fiksni vektor , rotacija oko određene ose pod datim uglom, skaliranje duž bilo koje ose , pomak, perspektiva i projekcija na jednu od glavnih koordinatnih ravnina.

Sl.8.1. Dekartov koordinatni sistem, projekcija P' tačke P na ravan XZ, mreža na kojoj je definisana površina i preseci paralelni sa ravnima XZ i YZ.

Osnovne transformacije koordinata. Razmotrimo neki Dekartov koordinatni sistem (slika 8.1). Bilo koja tačka u prostoru je u njoj predstavljena vektorskom matricom oblika (x y z). Koristićemo homogene koordinate tačke u prostoru (x y z 1).

Kao ravan slike biramo ravan XZ, opisanu jednadžbom Y = 0. Projekcija tačke objekta na ovu ravan dobija se množenjem (x y z 1) ×A, gde je

specificira transformaciju projekcije na XZ ravan.

Rotacija oko date ose (X, Y i Z, respektivno) za određeni ugao a opisuje se sledećim matricama:

gdje je a = sin a, b = cos a. Smatra se da je pozitivna rotacija u smjeru suprotnom od kazaljke na satu kada se gleda s kraja ose oko koje se predmet rotira.

Matrice transformacije prijenosa u fiksni vektor i skaliranje imaju sljedeći oblik:

Ovdje (t x , t y , t z) je vektor prijenosa; s x , s y , s z su faktori skaliranja duž X, Y i Z osa, respektivno, 1/s je ukupni faktor skaliranja.

Pomak se sastoji od promjene jedne od koordinata tačke (zavisne koordinate) za iznos proporcionalan jednoj od dvije preostale koordinate (koordinata pomjeranja). Neka je zavisna koordinata X koordinata, a koordinata pomaka Y koordinata, tada će matrica pomaka imati oblik:

gdje je F koeficijent pomaka. Projekcija tačaka objekta na ravan XZ iz centra projekcije C može se dobiti pomoću centralne projekcijske transformacije. Njegova matrica:

Ovdje centar projekcije leži na Y osi i ima Y koordinatu jednaku (-H), gdje je H > 0 (vidi sliku 8.1).

Koristeći osnovne transformacije koordinata, možete dobiti gotovo proizvoljne ravne geometrijske projekcije.

Razmotrimo prvo slučaj paralelne projekcije. U zavisnosti od ugla koji pravac projekcije čini sa ravninom slike, paralelne projekcije se dele na pravougaone (npr. aksonometrijske) i kose. U slučaju pravokutnih projekcija, smjer projekcije je okomit na ravan slike. U slučaju kosih projekcija, pravac projekcije formira ugao sa ravninom slike koji je različit od pravog ugla. Detaljnije informacije o ovim vrstama projekcija mogu se naći, na primjer, u LITERATURA.

Općenitije aksonometrijske projekcije mogu se dobiti korištenjem dvije uzastopne rotacije objekta (prvo oko Z ose za neki ugao Az, a zatim oko X ose za ugao Ax), a zatim ortogonalne projekcije na ravan XZ. Za dvije najčešće vrste aksonometrijskih projekcija - izometriju i dimetriju - uglovi rotacije imaju sljedeće vrijednosti: Az = -45 °, Ax = 35 ° i Az = -20 °, Ax = 20 °.

Na slici 8.2 prikazani su primjeri izometrijskih i dimetričnih projekcija iste površine, a također je prikazano kako se ose kartezijanskog koordinatnog sistema projektuju na ravan slike.

Za konstruiranje kosih projekcija zgodno je koristiti posmičnu transformaciju. Jedna od kosih projekcija, na primjer, može se konstruirati sljedećim slijedom transformacija:

1. pomak, u kojem je zavisna osa X osa, osa pomaka je Y osa; koeficijent pomaka F = 1 ako je specificirana “pozitivna” projekcija (slika 8.3, b), i F = -1 ako je potrebna “negativna” projekcija (slika 8.3, a);

2. pomak, u kojem je zavisna osa Z osa, osa pomjeranja Y osa i koeficijent pomaka F = 1;

3. projekcija na ravan XZ.

Ako vam iz nekog razloga nijedna od navedenih standardnih paralelnih projekcija (izometrija, dimetrija i kosa projekcija) ne odgovara, potrebnu projekciju možete izraditi translacijom, rotacijom, skaliranjem i pomakom.

Koristeći ove transformacije, također možete pozicionirati snimljeni objekt u prostoru na željeni način, a zatim konstruirati neku standardnu projekciju.

Sl.8.2. Dimetrijska i izometrijska projekcija površine, kao i ose Dekartovog koordinatnog sistema.

Koristeći osnovne transformacije koordinata, također je lako formirati transformaciju koja će vam omogućiti da dobijete središnju projekciju objekta iz proizvoljnog centra projekcije na ravninu koja prolazi kroz ishodište koordinata okomito na liniju vida. Paralelna projekcija se može odrediti i na drugačiji način - vektorom smjera projekcije čiji početak leži u tački (0,0,0), a kraj određuje programer.

Dakle, da bi se konstruisala proizvoljna projekcija grafičkog objekta, dovoljno je generisati matricu transformacije, koja je superpozicija glavnih koordinatnih transformacija navedenih gore. Množenjem matrice koordinata proizvoljne tačke na desnoj strani sa matricom rezultirajuće transformacije dobijamo koordinate projekcije ove tačke na ravan slike u skladu sa odabranom metodom projekcije.

Sl.8.3. “Negativne” (a) i “pozitivne” (b) kose projekcije površine, kao i ose osa kartezijanskog koordinatnog sistema.

U nastavku su opisani programi koji implementiraju osnovne transformacije koordinata, neke standardne tipove projekcija, kao i druge alate neophodne za konstruisanje proizvoljnih ravnih geometrijskih projekcija objekata.

Transformacijski programi. Da biste konstruirali željenu projekciju trodimenzionalnog objekta, potrebno je navesti odgovarajuću transformaciju.

Programi koji definiraju transformacije su u suštini instalacijski programi. Slijed poziva za njih specificira rezultirajuću transformaciju koja odgovara određenoj metodi projekcije. Programi za crtanje će koristiti pripremljenu matricu transformacije za prikaz objekata u odabranoj projekciji.

Svaki program koji postavlja sopstvenu transformaciju formira matricu 4 ´ 4 i množi je sa leve strane sa matricom trenutne transformacije. Kao rezultat toga, transformacije će biti izvedene redoslijedom kojim su specificirane. Početne postavke izvodi program INIT, koji generiše matricu identiteta. Pozivanje na njega poništava već akumuliranu transformaciju. Očigledno, kada treba da dobijete novu rezultujuću transformaciju, morate početi pozivanjem ovog programa.

Programi ISOMET, DIMET, CABIN, VIEW, AXONOM vam omogućavaju da dobijete neke standardne projekcije grafičkih objekata. Međutim, ponekad je potrebno prvo transformirati objekt (na neki način ga pozicionirati u prostoru). U tu svrhu možete koristiti programe koji određuju rotaciju, istezanje, translaciju i pomak. To su programi: TDROT, TDSCAL, TDTRAN, SHEAR.

Bilo koja trenutna transformacija se može sačuvati (program SAVETR) i po želji vratiti (SETTR program). Općenito, koristeći program SETTR, možete postaviti proizvoljnu transformaciju kao trenutnu transformaciju, čime se proširuje raspon osnovnih transformacija koordinata.

Program INIT inicijalizira rezultirajuću transformaciju. Program bez parametara.

Program TDTRAN(DX, DY, DZ) specificira translaciju objekta u prostoru u odnosu na ishodište koordinata. Programski parametri DX,DY, DZ određuju prijenosni vektor.

Program TDROT(NAXES,ALPHA) postavlja rotaciju koordinatnog sistema u odnosu na navedenu osu za zadati ugao. Njegovi parametri:

NAXES broj ose oko koje se vrši rotacija: Dodatno, ako je NAXES< 0, угол поворота считается заданным в радианах, NAXES >0 - u stepenima; ALPHA ugao rotacije: ALPHA > 0 - rotacija se vrši suprotno od kazaljke na satu, u odnosu na osu oko koje se rotacija vrši; ALPHA< 0 — поворот выполняется по часовой стрелке.

Program TDSCAL(NAXES,SCALE) omogućava vam da rastegnete (komprimirate) duž određene ose i, eventualno, simetrično odražavate objekat. Parametri programa su sljedeći:

NAXES broj ose duž koje se vrši rastezanje (kompresija): koeficijent rastezanja (kompresije) SCALE: SCALE ³ 1 - rastezanje po SCALE puta, SCALE O (0,1) - kompresija za 1/SCALE puta, SCALE< 0 симметричное отражение относительно соответствующей координатной плоскости или начала координат и растяжение в |SCALE| раз или сжатие в 1/|SCALE| раз.

Program SHEAR(I,J,F) određuje pomak. Parametri programa:

I broj pomične koordinate: J broj zavisne koordinate; F koeficijent pomaka.

Kada je I = J, ova transformacija se degeneriše u skalirajuću transformaciju duž I-te ose sa faktorom rastezanja jednakim (F+1).

ISOMET program generiše matricu rezultirajuće transformacije da bi se dobila izometrijska projekcija uzimajući u obzir trenutnu transformaciju.

6. Prijevod i rotacije u trodimenzionalnom prostoru.

Program bez parametara.

Program DIMET vam omogućava da generišete matricu rezultirajuće transformacije da biste dobili dimetričku projekciju uzimajući u obzir trenutnu transformaciju. Program bez parametara.

Program CABIN(J) vam omogućava da generišete matricu rezultirajuće transformacije da biste dobili kosu projekciju, uzimajući u obzir trenutnu transformaciju. Programski parametar J određuje tip kose projekcije. Kada je J = 1, dobija se pozitivna projekcija, a kada je J = -1, negativna projekcija.

Program VIEW(X,Y,Z) vam omogućava da generišete matricu centralne projekcije na ravan okomitu na liniju vida. Parametri programa:

X,Y,Z koordinate centra projekcije (gledišta).

Promjenom koordinata gledišta, možete dobiti različite projekcije objekta. Da biste dobili željeni kut, ponekad je prikladnije pomicati sam objekt u prostoru, ostavljajući centar projekcije nepomično. Ovo se može postići pozivanjem TDROT i TDTRAN programa (prije pozivanja programa VIEW).

Kada pristupate programu VIEW, morate osigurati da centar projekcije ne završi unutar objekta koji se prikazuje, inače će rezultati programa za crtanje TRI biti nepredvidivi.

Program AXONOM(X,Y,Z) generiše matricu rezultirajuće transformacije kako bi se dobila aksonometrijska projekcija uzimajući u obzir trenutnu transformaciju. Pravac projekcije je određen vektorom koji povezuje tačku (X,Y,Z) sa ishodištem.

A je jednodimenzionalni niz dužine 16.

Program SETTR(A) vam omogućava da unesete sadržaj datog niza A u tekuću matricu transformacije. Pretpostavlja se da niz A sadrži sekvencijalne stupce matrice od 4 ´ 4.

Pomoćni i pomoćni programi.

Program HCUNIT(A) generiše 4 ´ 4 matricu identiteta A.

Program HCMULT(A,B) množi dvije kvadratne matrice četvrtog reda A ´B. Rezultat se stavlja na mjesto matrice A.

HCPRSP(H) program implementira centralnu transformaciju projekcije. H parametar specificira Y koordinatu centra projekcije koji se nalazi na Y osi (H > 0).

Program HCINV(X,Y,Z,XP,YP,ZP) izračunava koordinate (XP,YP,ZP) centra projekcije uzimajući u obzir inverznu transformaciju koordinata. Matrica inverzne transformacije je unaprijed izračunata.

Program HCROT1(X,Y,Z) vam omogućava da pronađete rezultujuću transformaciju koja vodi tačku A(X,Y,Z) do tačke sa koordinatama uz dve uzastopne rotacije .

Dio 8 - integracija ugaonih brzina, matrice rotacije

Dio 11 - integracija ugaonih brzina, metode višeg reda (u razvoju)

Integriranje ugaonih brzina korištenjem rotacijskih matrica

Nastavljamo našu izbornu utrku - koji će integrator ugaone brzine zauzeti svoje zasluženo mjesto na čelu (bukvalno) našeg proizvoda?

Već smo iskopali prljavštinu na uglovima Euler-Krylov - to su, naravno, poštovana i vrijedna imena, ali su vrlo stara - ne mogu podići glavu do zenita, odmah im se vrti u glavi, a oni koji vise naopačke dole iznenada izgube svoju radnu sposobnost. I generalno, ne trebaju nam kriminalci (sistemi zasnovani na uglovima)!

Danas ćemo pogledati matrice rotacije - 9 kosinusa smjera ne mogu biti pogrešni, zar ne?

Kinematička jednadžba za spregnute ose (kada se ugaona brzina projektuje na ose proizvoda) ima oblik:

Ovdje je A orijentacijska matrica.
Za korak Δt možemo napisati približnu metodu integracije:

Ova metoda je čisto linearna, koristi samo sabiranje i množenje, nema singularnih tačaka kao klasa.
Jedan nedostatak koji odmah možemo primijetiti je njegova glomaznost: koristimo 9 brojeva za predstavljanje matrica, a svaki korak integracije koristeći najjednostavniji metod („prvi red“) zahtijeva 18 množenja i 18 sabiranja (bez specijalizirane metode koja „zna“ o jedinice duž glavne dijagonale - ukupno 27 množenja). Ako to zapišemo po komponentama, dobijamo (sa superskriptom 1 – nove vrijednosti, sa superskriptom 0 – stari):

Matrična notacija nam omogućava da ovu unutrašnju složenost sakrijemo iza prekrasnih proračuna, pa je ponekad korisno zapisati proračune "iz glave" kako bismo zapamtili s čime imamo posla.
Međutim, čak ni najstariji računari na vozilu ne bi imali problema povezanih sa nedovoljnim performansama - pa, koliko je 36 operacija za računar!?

Ne, prava Ahilova peta matrica rotacije je da s vremenom one prestaju biti rotacijske matrice, a vratiti ih na pravi put nije tako lako...
Neka je početna matrica orijentacije jedinica, odnosno, osi inercijalnog i spregnutog koordinatnog sistema se poklapaju:

Nakon 72 koraka dolazimo do matrice orijentacije jednake:

dok je trebalo da stignu do matrice identiteta (rotacija za 360 stepeni!).
Ovu matricu možemo zapisati kao proizvod dva:

Druga od njih je matrica rotacije duž Z ose za ugao od 0,9° - to je akumulirana greška integracije uzrokovana prevelikim korakom. Relativno gledano, greška nije tako velika: 0,9/360 = 0,25%, što i nije tako loše s obzirom na veliki korak koji smo napravili.
Ali prva matrica se skalira duž osa X, Y. Vektor sa nultom Z komponentom će jednostavno povećati svoju dužinu - često to i nije tako loše - barem neće promijeniti smjer vektora. Na isti način, vektor (0;0;1) T će ostati nepromijenjen - sve je ispravno.
Najzanimljivije će se dogoditi sa srednjim vektorima.
Na primjer, vektor

će se pretvoriti u

ne samo da se povećava u veličini, već i mijenja smjer zbog skaliranja! Ranije je "gledao" pod uglom od 45° u odnosu na ravan X-Y, a sada pod uglom od 37° - greška više nije 0,9°, već čak 8°!

U ovom konkretnom slučaju, lako smo mogli da faktorizujemo matricu odvojeno izolujući rotaciju i skaliranje. Kada to možemo, jasno je kako ispraviti situaciju - trebamo ostaviti samo matricu rotacije i ukloniti skaliranje!
Ali zamislimo sada da smo nakon okretanja oko Z ose izvršili i rotaciju oko X ose instrumenta za 30 stepeni:

Kako najoptimalnije izolovati zavoje odvojeno od ove gomile brojeva, osloboditi se drugih transformacija prostora - pitanje je i dalje otvoreno...
Podsjetimo da su stupci orijentacijske matrice koordinate baznih vektora u inercijskom referentnom sistemu. Ovi vektori moraju imati jediničnu dužinu i biti međusobno okomiti, odnosno možemo napisati sljedeće "jednačine veze" (u ovom slučaju, dva na vrhu je eksponencija):

Zaista: sa 9 matričnih koeficijenata moramo imati tačno 3 stepena slobode, zbog čega nam je potrebno dodatnih 6 jednačina. Hajde da proverimo šta se ovde dešava:
Dužina 1. baznog vektora: 1.314
Dužina 2. baznog vektora: 1,243
Dužina 3. baznog vektora: 1,087
Ugao između 1 i 2: 90°
Ugao između 2 i 3: 103,47°
Ugao između 1 i 3: 90°

Ortonormalna osnova je prestala biti takva! Razumemo ovo, ali kako tačno da prilagodimo 9 vrednosti da ponovo bude ortonormalno?

Možete koristiti staru dobru metodu konstruisanja ortonormalne baze. Označavamo početne bazne vektore e 1, e 2, e 3:

Nazovimo transformiranu osnovu n 1, n 2, n 3.
Normalizujemo prvi vektor:

Od drugog vektora oduzimamo njegovu projekciju na prvi, nakon čega također normaliziramo:

Konačno, od trećeg vektora oduzimamo njegovu projekciju na prvi i drugi, a zatim normaliziramo:

Postoji određena lukavost u ovim formulama: čini se da smo koristili svih 9 originalnih koeficijenata da dobijemo novih 9, sada ortonormalnih. U stvari, od e 3 To uopšte nije važno! Prvo od njega oduzimamo sve nepotrebno, tako da ide pravolinijski, međusobno okomito n 1, n 2, a zatim normaliziramo njegovu dužinu - da, od ovog vektora više nema životnog prostora! Isto tako možemo napisati:

i dobiti apsolutno isti rezultat! To jest, u stvarnosti, ova metoda uzima prvih 6 koeficijenata i potpuno izbacuje posljednja 3. A prvih 6 ispada da su nejednaki: ako vjerujemo prvom stupcu "bezuslovno", onda drugom - samo dok ne bude u suprotnosti sa prvo.

Isprobajmo proceduru normalizacije na našoj matrici B:

Istovremeno, kako bi se očekivalo, n 3 ispostavilo se da je isti do posljednjeg reprezentativnog decimalnog mjesta, bez obzira na način izračunavanja - kroz e 3 ili kroz vektorski proizvod.

Sada imamo sreće - savršeno smo normalizirali matricu tako da izražava upravo ono što treba - rotaciju od 0,9° oko Z ose i rotaciju od 30° oko X ose.
Ali hajde sada da mu priđemo s druge strane - ne e 1, e 2, e 3, A e 3, e 2, e 1. Evo šta dobijate:

Umjesto 30° rotacije na X osi, ovaj put smo dobili rotaciju od 37°, efektivno implementirajući najgori slučaj!
Ispravan pristup bi bio da se riješi problem optimizacije: svaki koeficijent matrice je zbir korisnog signala i šuma. Pronađite nove koeficijente izražene u terminima starih na takav način da srednja kvadratna greška teži ka minimumu. Ali ni tada ne garantujemo najbolje performanse – ko je rekao da korišćenjem približnih konačnih rotacionih matrica unosimo slučajnu grešku!?
Hajde da razjasnimo šta je naš problem. Nismo hteli da ispišemo tačnu konačnu matricu rotacije jer ona izgleda otprilike ovako:

(promjenom redoslijeda rotacija, dobićemo različite matrice W, ali sve će biti striktno rotacijske matrice)
Iz pohlepe smo to pojednostavili:

I otkrili smo da termini drugog reda malenosti koje smo ispustili dovode do promjene oblika matrice. U našem primjeru rotacije oko Z ose, dobijamo

Proširujući u Taylorov niz do 3. reda male veličine, imamo:

Još jednom vidimo sličan efekat: greška integracije ovog puta je izuzetno mala i iznosi manje od jedne lučne sekunde, dok se najuočljivije izobličenje ponovo pojavljuje na skali. Čini se da je greška prilično mala - manja od jedne hiljadinke - ali to je dovoljno da vektor usmjeren pod uglom od 45° prema ravni XY bude "pritisnut" uz njega za dodatnih 1 lučni minut.

Dakle, čak i korištenje malog koraka integracije i korištenje metoda visokog reda ne rješava problem nagomilavanja “smeća” u matrici. I što više vremena bude prolazilo, to će više smeća biti u matrici, koje možemo samo odbaciti zajedno s korisnim podacima.

Sve navedeno ne znači da su matrice rotacije apsolutno neprikladne za integraciju ugaonih brzina. Mogu se primijeniti ako se poštuje određeni oprez - imperativ je predvidjeti proceduru "ortonormalizacije", ali ako je moguće ne prolazite kroz nju - prebacite se na dvostruku ili proširenu preciznost svuda, smanjite korak integracije, koristite numeričke brojeve visokog reda metode.

Ali kao što ćemo naučiti u sljedećem poglavlju, kvaternioni su oslobođeni većine nedostataka rotacijskih matrica i izlaze kao pobjednici u ovoj bitci.

Nastavlja se...

Razmotrimo problem nalaženja kosinusa pravca koji određuju orijentaciju pokretnog koordinatnog sistema Oxyz u odnosu na neki, nazovimo ga fiksni, koordinatni sistem OXYZ. Označimo početni koordinatni sistem pokretnog triedra sa Ox 0 y 0 z 0 i prije rotacije se shodno tome poklapao sa koordinatnim sistemom OXYZ. Neka se triedar Oxyz pomakne iz pozicije Ox 0 y 0 z 0 u trenutnu kao rezultat jedne rotacije za ugao oko ose On, koji je specificiran jedinicom jedinice u koordinatnom sistemu OXYZ. Osa On može zauzimati drugačiji pravac, ne mora se podudarati sa jednom od osa OXYZ triedra. Predstavimo korištene koordinatne sisteme i njihove veze pomoću dijagrama:

je matrica kosinusa smjera koja specificira orijentaciju triedra Ox v y v z v , od kojih jedna osa (neka prva osa Ox v) specificira orijentaciju ose rotacije On;

- matrica rotacije oko ose On.

Tada je željena matrica konačne rotacije određena relacijom

Ili, proširujući izraz i koristeći svojstva (1.9), dobijamo konačnu matricu rotacije u sljedećem obliku

(1.11)

Kosinusi pravca koji određuju orijentaciju On ose rotacije softvera za ugao. Dakle, pozicija pokretnog koordinatnog sistema se specificira pomoću četiri parametra: , .

Matrični oblik Ojlerove formule

Neka je tačka M određena u koordinatnom sistemu SC m, koji je definisan vektorom

gdje su projekcije vektora na ose koordinatnog sistema SC m, koji je označen indeksom “m”.

Odredimo linearnu brzinu tačke M u projekcijama na ose koordinatnog sistema SC m. Prema Ojlerovoj formuli imamo

. (1.12)

Evo vektora ugaone brzine koordinatnog sistema SC m u odnosu na koordinatni sistem SC s, izraženog u projekcijama ovog vektora na ose koordinatnog sistema SC m.

Koristeći matrični oblik vektorskog proizvoda, pišemo

Zapišimo rezultat u matričnom obliku

, (1.13)

Gdje (1.14)

Indeks “~” (tilda) ukazuje na koso-simetrični oblik ove matrice.

Poissonova formula

U tradicionalnom obliku notacije, ugaona brzina se može predstaviti kao

Imajte na umu da je u formuli (1.13) uslov bio implicitno postavljen

U opštem slučaju, kada radni odnos izvedemo na drugačiji način.

Hajde da razlikujemo odnos

Ili u drugom obliku

(1.18)

Matrica rotacije u trodimenzionalnom prostoru

Nakon transformacije dobijamo formule:
X osa
x"=x;
y":=y*cos(L)+z*sin(L) ;
z":=-y*sin(L)+z*cos(L) ;

Y osa
x"=x*cos(L)+z*sin(L);
y"=y;
z"=-x*sin(L)+z*cos(L);

Z osa
x"=x*cos(L)-y*sin(L);
y"=-x*sin(L)+y*cos(L);
z"=z;

Sva tri zavoja se rade nezavisno jedan od drugog, tj. ako je potrebno rotirati oko ose Ox i Oy, prvo se vrši rotacija oko ose Ox, a zatim se u odnosu na rezultujuću tačku vrši rotacija oko ose Oy.

U dvodimenzionalnom prostoru, rotacija se može opisati jednim uglom sa sljedećom matricom linearne transformacije u kartezijanskom koordinatnom sistemu:

Rotacija se izvodi množenjem matrice rotacije vektorom stupca koji opisuje rotiranu tačku:

Koordinate (x",y") kao rezultat rotacije tačke (x,y) imaju oblik:

U ovom slučaju pozitivni uglovi odgovaraju rotaciji vektora u suprotnom smeru kazaljke na satu u uobičajenom desnom koordinatnom sistemu i u smeru kazaljke na satu u levom koordinatnom sistemu.

[uredi] Matrica rotacije u trodimenzionalnom prostoru

Matrice rotacije oko ose kartezijanskog koordinatnog sistema za ugao α u trodimenzionalnom prostoru su:

Rotacija oko x ose:

Rotacija oko y ose:

Rotacija oko ose z:

U ovom slučaju, pozitivni uglovi odgovaraju rotaciji vektora u suprotnom smeru kazaljke na satu u desnom koordinatnom sistemu, a u smeru kazaljke na satu u levom koordinatnom sistemu, ako gledate u ravninu rotacije sa strane poluprostora, gde su vrednosti koordinata ose oko koje se vrši rotacija su pozitivne. Pravi koordinatni sistem je povezan sa izborom prave baze (vidi pravilo gimleta).

Svojstva matrice rotacije.

Svojstva matrice rotacije

Ako je matrica koja specificira rotaciju oko ose za ugao ϕ, tada:

· (trag matrice rotacije)

· (matrica ima determinantu identiteta).

· ako se redovi (ili stupci matrice) smatraju koordinatama vektora, tada su tačni sljedeći odnosi:

· Matrica obrnute rotacije se dobija uobičajenom transpozicijom matrice rotacije naprijed, tj. .

24. Bresenhamov algoritam za rasterizaciju segmenta.

Bresenhamov algoritam(engleski) Bresenhamov linijski algoritam) je algoritam koji određuje koje tačke na dvodimenzionalnom rasteru moraju biti osenčene da bi se dobila bliska aproksimacija prave linije između dve date tačke. Ovo je jedan od najstarijih algoritama u kompjuterskoj grafici - razvio ga je Jack E. Bresenham u IBM-u 1962. godine. Algoritam se široko koristi, posebno za crtanje linija na ekranu računara. Postoji generalizacija Bresenhamovog algoritma za konstruisanje krivulja 2. reda.

Algoritam

Segment je nacrtan između dvije tačke - ( x 0 ,y 0) i ( x 1 ,y 1), pri čemu ovi parovi označavaju kolonu i red, redom, čiji se brojevi povećavaju desno i dolje. Prvo ćemo pretpostaviti da naša linija ide dolje i udesno, s horizontalnom udaljenosti x 1 − x 0 iznad vertikale y 1 − y 0, tj. nagib linije u odnosu na horizontalu je manji od 45°. Naš cilj je to za svaku kolonu x između x 0 i x 1 , odredite koju liniju y najbliže pravoj i nacrtaj tačku ( x,y).

Opća formula za liniju između dvije tačke je:

Pošto znamo kolonu x, zatim linija y dobija se zaokruživanjem na cjelinu sljedeće vrijednosti:

Međutim, nema potrebe za izračunavanjem tačne vrijednosti ovog izraza. Dovoljno je to napomenuti y raste iz y 0 i za svaki korak dodajemo x jedan i dodajte u y vrijednost nagiba

što se može unaprijed izračunati. Štaviše, na svakom koraku radimo jednu od dvije stvari: ili ostajemo isto y, ili ga povećajte za 1.

Koje od ova dva odabrati može se odlučiti praćenjem vrijednost greške, što znači vertikalnu udaljenost između trenutne vrijednosti y i tačnu vrijednost y za struju x. Kad god se povećamo x, povećavamo vrijednost greške za iznos nagiba s, dato gore. Ako je greška premašila 0,5, linija je postala bliža sljedećem y, pa povećavamo y za jedan, dok se istovremeno smanjuje vrijednost greške za 1. U implementaciji algoritma ispod, plot(x,y) crta tačku, a abs vraća apsolutnu vrijednost broja:

funkcija linija(x0, x1, y0, y1) int deltax:= abs(x1 - x0) int deltay:= abs(y1 - y0) pravi greška:= 0 pravi deltaerr:= deltay / deltax int y:=y0 za x od x0 to ako greška >= 0,5 y:= y + 1 greška:= greška - 1,0

Problem sa ovim pristupom je što računari rade relativno sporo sa stvarnim vrednostima kao što su greška i deltaerr. Osim toga, greške se mogu akumulirati tokom izračunavanja s pomičnim zarezom. Iz ovih razloga, bolje je raditi samo s cijelim brojevima. To se može učiniti množenjem svih stvarnih vrijednosti koje koristi deltax. Jedini problem je sa konstantom 0,5 - ali u ovom slučaju dovoljno je pomnožiti obje strane nejednakosti sa 2. Dobijamo sljedeći kod:

funkcija linija(x0, x1, y0, y1) int deltax:= abs(x1 - x0) int deltay:= abs(y1 - y0) int greška:= 0 int deltaerr:=deltay int y:=y0 za x od x0 to x1 plot(x,y) greška:= greška + deltaerr ako 2 * greška >= deltaks y:= y + 1 greška:= greška - deltaks

Množenje sa 2 za cijele brojeve se implementira pomakom bita ulijevo.

Sada možemo brzo nacrtati linije usmjerene udesno i dolje sa vrijednošću nagiba manjom od 1. Ostaje proširiti algoritam na crtanje u svim smjerovima. To se postiže spekularnim refleksijama, tj. promena predznaka (korak od 1 se zamenjuje sa -1), razmena varijabli x I y, razmjenjujući koordinate početka segmenta sa koordinatama kraja.

[uredi] Crtanje linija

Implementacija u C++:

Void drawLine(int x1, int y1, int x2, int y2)( int deltaX = abs(x2 - x1); int deltaY = abs(y2 - y1); int signX = 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) ( greška -= deltaY; x1 += znakX; ) if(error2< deltaX) { error += deltaX; y1 += signY; } }}

25. Bresenhamov algoritam za rasterizaciju kruga.

Crtanje krugova

Postoji i Bresenhamov algoritam za crtanje krugova. Metoda konstrukcije je slična crtanju linije. U ovom algoritmu se konstruiše kružni luk za prvi kvadrant, a koordinate tačaka kružnice za preostale kvadrante dobijaju se simetrično. U svakom koraku algoritma razmatraju se tri piksela, a najpogodniji se bira poređenjem udaljenosti od centra do odabranog piksela sa radijusom kruga.

// R - radijus, X1, Y1 - koordinate centra int x:= 0 int y:= R int delta:= 2 - 2 * R int greška:= 0 dok(y >= 0) drawpixel(X1 + x, Y1 + y) drawpixel(X1 + x, Y1 - y) drawpixel(X1 - x, Y1 + y) drawpixel(X1 - x, Y1 - y) greška = 2 * (delta + y) - 1 ako((delta< 0) && (error <= 0)) delta += 2 * ++x + 1 nastaviti greška = 2 * (delta - x) - 1 ako((delta > 0) && (greška > 0)) delta += 1 - 2 * --y nastaviti x++ delta += 2 * (x - y) y--

Void drawCircle(int x0, int y0, int radijus) ( int x = 0; int y = radijus; int delta = 2 - 2 * radijus; int greška = 0; while(y >= 0) ( setPixel(x0 + x , y0 + y); setPixel(x0 + x, y0 - y); setPixel(x0 - x, y0 + y); setPixel(x0 - x, y0 - y); greška = 2 * (delta + y) - 1 ; if(delta< 0 && error <= 0) { ++x; delta += 2 * x + 1; continue; } error = 2 * (delta - x) - 1; if(delta >0 && greška > 0) ( --y; delta += 1 - 2 * y; nastavi; ) ++x; delta += 2 * (x - y); --y; ))

Wu-ov algoritam za izravnavanje.

Wuov algoritam je algoritam za dekomponovanje segmenta u raster sa zaglađivanjem. Predložio ga je Wu Xiaolin ( Xiaolin Wu, otuda i dobro utvrđeno rusko ime za algoritam) u članku objavljenom u časopisu Computer Graphics u julu 1991. Algoritam kombinuje visokokvalitetno uklanjanje alijasinga i brzinu blisku onoj kod Bresenham algoritma bez anti-aliasinga.

Algoritam

Horizontalne i vertikalne linije ne zahtijevaju anti-aliasing, pa se crtaju zasebno. Za preostale linije, Wu algoritam ih prosljeđuje duž glavne ose, birajući koordinate duž manje ose slično Bresenham algoritmu. Razlika je u tome što se u Wu algoritmu ne uspostavlja jedna, već dvije tačke na svakom koraku. Na primjer, ako je glavna os X, tada se razmatraju tačke sa koordinatama (x, y) i (x, y+1). U zavisnosti od veličine greške, koja pokazuje koliko su pikseli otišli od idealne linije duž neprimarne ose, intenzitet se raspoređuje između ove dve tačke. Što je tačka udaljenija od idealne linije, njen intenzitet je manji. Vrijednosti intenziteta dva piksela uvijek se zbrajaju u jedan, to jest, ovo je intenzitet jednog piksela koji pada tačno na idealnu liniju. Ova distribucija će liniji dati isti intenzitet cijelom dužinom, stvarajući iluziju da se tačke nalaze duž linije ne po dvije, već jedna po jedna.

Rezultat algoritma

Implementacija u pseudokodu (samo za x red):

funkcija dijagram (x, y, c) je // crta tačku s koordinatama (x, y) // i svjetlinom c (gdje je 0 ≤ c ≤ 1) funkcija dio(x) je povratak cijeli broj x funkcija okruglo (x) je povratak ipart(x + 0,5) // zaokružiti na najbliži cijeli broj funkcija fpart(x) je povratak razlomak x funkcija crta_linija(x1,y1,x2,y2) je ako x2< x1 onda swap(x1, x2) swap(y1, y2) kraj ako dx:= x2 - x1 dy:= y2 - y1 gradijent:= dy ÷ dx // obradimo početnu tačku xend:= okruglo(x1) yend:= y1 + gradijent × (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 + gradijent // prvi y-presjek za petlju // krajnja točka procesa xend:= okruglo(x2) yend:= y2 + gradijent × (xend - x2) xgap:= fpart(x2 + 0,5) xpxl2:= xend // će se koristiti u glavnoj petlji ypxl2:= ipart(yend) plot(xpxl2, ypxl2, 1 - fpart(yend) × xgap) plot(xpxl2, ypxl2 + 1, fpart(yend) × xgap) // glavna petlja za x od xpxl1 + 1 to xpxl2 - 1 uradi plot(x, ipart(intery), 1 - fpart(intery)) plot(x, ipart(intery) + 1, fpart(intery)) intery:= intery + gradijent funkcija ponavljanja

26. Algoritmi slikanja.

Algoritam slikanja

Algoritam slikanja se vrlo često koristi u kompjuterskoj grafici za slikanje oblika koji imaju ivice. Ovaj algoritam može imati i druge primjene, na primjer može se koristiti za pronalaženje centra mase tijela iz njegove slike.

Algoritmi 2D rasterske grafike: senčenje

Razmotrimo algoritme za slikanje proizvoljne konture koja je već nacrtana u rasteru. Prvo, piksel se nalazi unutar obrisa oblika. Promijenite boju ovog piksela u željenu boju ispune. Zatim se analizira boja svih susjednih piksela. Ako boja nekog susjednog piksela nije jednaka boji ivice ili boji ispune, tada se boja tog piksela mijenja u boju ispune.

Jednostavan rekurzivni padding.

Procedura PixelFill(x, y, BColor, Color: Integer);

(x, y – koordinate polazne tačke, BColor – boja granice,

Boja – boja punjenja)

C:=GetPixel (x,y) (analizirajte trenutnu boju piksela)

ako (C<>BBoja) i (C<>Boja).

PutPixel(x, y, Boja);

PixelFill(x+1, y, BBoja, Boja);

PixelFill(x, y+1, BBoja, Boja);

PixelFill(x-1, y, BColor, Color);

PixelFill(x, y-1, BColor, Color);

Ovaj algoritam nije optimiziran za korištenje memorije steka i jedan je od najsporijih algoritama za sjenčanje (u prosjeku, samo jedan od četiri poziva se koristi za sjenčanje). Algoritam ne može ispuniti područja ograničena bojom ispune. Možete napraviti sličan algoritam bez rekurzije ako koristite nizove umjesto steka.

Algoritam za slikanje linijama.

1. Postoji početna tačka sa koordinatama (x st , y st) i početni smjer djelovanja rekurzivnih poziva dir=1. Parametri lijeve i desne granice u početku se poklapaju sa koordinatama početne tačke: x PL = x st , x PR = x st . Procedura se zove LineFill, pri čemu:

2. Postoje x L i x R – lijeva i desna granica između kojih trenutna horizontalna linija je nacrtana.

3. Povećanje je napravljeno y=y+dir i, između x L i x R, analizira se boja piksela gore linija. Ako se ne podudara s bojom ispune, postupak LineFill poziva se rekurzivno sa dir = 1 i xPL = xL, xLR = xR.

4. Povećanje je napravljeno y=y–dir i, počevši od x L do prethodne vrijednosti x PL, analizira se boja piksela ispod linije. Ako se boja piksela razlikuje od boje ispune, procedura se poziva rekurzivno sa dir = –1 i xPL = xL, xPR = xR.

5. Nastavljajući duž iste horizontalne linije od prethodnog x PR do x R, analizira se boja ispod linija. Ako se boja bilo kojeg piksela razlikuje od boje ispune, procedura se poziva rekurzivno sa dir = –1 i xPL = xL, xPR = xR.
Ispod je primjer implementacije ovog algoritma u C++:

void LineFill(int x, int y, int dir, int xPL, int xPR)

// ova varijabla će pohraniti boju piksela

// POSTAVI TRENUTNE GRAnice xL I xR

boja = GetPixel(--xL,y);

// xL=xL-1 se stavlja u poziv funkcije

while (boja != bcolor); // bcolor – boja ivice

boja = GetPixel(++xR,y);

while (boja !=bcolor);

Linija(xL,y, xR,y, Mycolor);

//ovo može biti bilo koja funkcija crtanja linija

// ANALIZIRAJ PIKSELE IZNAD CRTE

za (x=xL; x<=xR; x++) {

boja = GetPixel(x, y+dir);

if (boja !=bcolor)

x = Ispuna linije(x, y+dir, dir, xL, xR);

// ANALIZIRAJTE PIKSELE ISPOD LINIJE LIJEVO

za (x=xL; x<=xPL; x++) {

boja = GetPixel(x, y-dir);

if (boja !=bcolor)

// ANALIZIRAJTE PIKSELE ISPOD LINIJE DESNO

za (x=xPR; x<=xR; x++) {

boja = GetPixel(x, y-dir);

if (boja !=bcolor)

x = LineFill(x, y–dir, –dir, xL, xR);

U programima se funkcija LineFill poziva na sljedeći način:

LineFill(xst, yst, 1, xst, xst);

Jasno je da postoje i drugi efikasni algoritmi za popunjavanje. Na primjer, algoritmi za popunjavanje koji koriste matematički opis konture povezani su sa specifičnim oblikom poligona koji treba popuniti (na primjer, pravougaonik ili krug). U tom slučaju, kontura se možda uopće neće prikazati u rasteru. U isto vrijeme, lako je koristiti bilo koju teksturu kao ispunu.

27. Sutherland-Cohen algoritam rezanja segmenta.

Cohen-Sutherland algoritam(engleski) Cohen-Sutherland) je algoritam za odsijecanje segmenata, odnosno algoritam koji vam omogućava da odredite dio segmenta koji siječe pravougaonik. Razvili su ga Dan Cohen i Ivan Sutherland na Harvardu 1966-1968, a objavljen na konferenciji AFIPS 1968.

Opis algoritma

Algoritam dijeli ravan na 9 dijelova pravim linijama, koje formiraju stranice pravougaonika. Svakom od 9 dijelova dodijeljen je četverobitni kod. Bitovi (od najmanje značajnog do najznačajnijeg) znače “lijevo”, “desno”, “ispod”, “iznad”. Drugim riječima, ona tri dijela ravni koja se nalaze lijevo od pravougaonika imaju najmanji bitni bit jednak 1, i tako dalje.

Algoritam određuje kod za krajnje tačke segmenta. Ako su oba koda jednaka nuli, tada je segment u potpunosti sadržan u pravokutniku. Ako bitovsko I kodova nije nula, tada segment ne siječe pravougaonik (pošto to znači da su obje krajnje točke segmenta na istoj strani pravougaonika). U drugim slučajevima, algoritam odabire krajnju tačku koja je izvan pravougaonika, pronalazi najbližu tačku preseka segmenta sa jednom od linija koje formiraju stranice pravougaonika i koristi ovu tačku preseka kao novu krajnju tačku segmenta. Skraćeni segment se ponovo propušta kroz algoritam.

Implementacija algoritma za trodimenzionalni model je identična dvodimenzionalnoj implementaciji, osim što se umjesto četverobitnog koda koristi šestobitni kod (dodatna dva bita dubine).

28. Algoritam particioniranja srednje tačke.