Egzamin Wst¦p do graki maszynowej

Prowadz¡cy: Aleksander Denisjuk

Monika Caªkowska

Sªawomir Figiel

Paweª Kami«ski

Paweª K¦dzierski

Piotr Lu±nia

Paweª Majewski

Aleksandra St¦pska

i inni

1 Percepcja wizualna i modele barw

1.1 Modele barw popularne

1.1.1 RGB
Model skªada sie z barw -czerwonej, zielonej, niebieskiej. Model wynikaj¡cy z

wªa±ciwo±ci odbiorczych ludzkiego oka, w którym wr¡zenia widzenia dowolnej

barwy mo»na wywoªa¢ przez zmieszanie w ustalonych proporcjach trzech wi¡zek

±wiatªa. W modelu tym zastosowano synteze addytywn¡, w której najni»sze

warto±ci oznaczaj¡ barwe czarn¡, za± najwy»sze biaª¡

1.1.2 CLUT
Jest to mechanizm sªu»¡cy do transforamcji z modelu w jednej gamie kolory-

stycznej do drugiej. Mechanizm ten mo»e by¢ hardwarowy jak softwerowy.

1.1.3 Web-safe colors
Bezpieczna paleta kolorów dla webmasterów, jest to zbiór barw które niezale»-

nie od wybranej palety kolorów na karcie gracznej b¦d¡ wy±wietlane popraw-

nie(nawet w sklai szaro±ci i palecie czarno biaªej - oczywi±cie w tych przypadkach

strona b¦dzie czarno biaªa ale z odzwierciedleniem nasycenia czerni.

1.1.4 CMYK
Przestrze« barw skªadaj¡ca si¦ z Cyjanu(odcie« niebieskiego), Magenty (poª¡-

czenie czerwieni i niebieskiego np fuksja) , ›óªtego(troche bielszy od standardo-

wej »óªcieni), Czarny (O niezbyt gª¦bokiej czerni). Paleta ta zostaªa opracowana

na potrzeby poligrai.

CMY jest modelem opisuj¡cym kolory na no±nikach biernych - czyli takich,

które jedynie odbijaj¡ ±wiatªo - na przykªad obrazy, fotograe. W przeciwie«-

stwie do no±ników aktywnych - które emituj¡ ±wiatªo - na przykªad monitory.

Nazwa modelu pochodzi od nazw jego barw skªadowych. S¡ to odpowiednio: C

(ang. Cyan), M (ang. Magneta), »óªty Y (ang. Yellow). Skªadowe C oraz M nie

maj¡ odpowiedników polskich, ale mo»na przyj¡¢ »e M to okolice purpury a C

to okolice turkusu (lub bª¦kitu). Kolory w tym modelu zapisywane s¡ poprzez

1

podanie intensywno±ci trzech barw skªadowych (c, m, y). W zale»no±ci od re-

prezentacji skªadowe te przyjmuj¡ najcz¦±ciej warto±ci zmiennoprzecinkowe od

0 do 1, b¡d¹ warto±ci caªkowite od 0 do 255. W naszych rozwa»aniach przyj-

miemy t¡ pierwsz¡ reprezentacj¦. Model ten reprezentowany jest przez sze±cian.

Poszczególne wymiary tego sze±cianu odpowiadaj¡ skªadowym: C, M oraz Y.

Sze±cian ten jest bardzo podobny do sze±cianu opisuj¡cego model RGB - biel

oraz czer« zamienione s¡ miejscami.

1.2 Telewizyjne

1.2.1 YUV
Model barw, w którym Y odpowiada za jasno±¢ obrazu (luminancj¦), a UV

koduj¡ barw¦  s¡ to dwa kanaªy chrominancji.

Macierz przeksztaªcenia rgb do yuv

0, 299

0, 587

0, 114

−0, 147

−0, 289

0, 437

0, 615

−0, 515

−0, 1

*

R
G
B

=

Y
U
V

Macierz przeksztaªcenia youv do rgb

1

0

0, 140

1

−0, 396

−0, 581

1

2, 029

0

*

Y
U
V

=

R
G
B

1.2.2 YUQ





Y

I

Q





=





0.299

0.587

0.114

0.596

−0.275

−0.321

0.212

−0.528

0.311









R
G
B





1.2.3 YCbCr
Model przestrzeni kolorów, u»ywany do cyfrowego przesyªania oraz przechowy-

wania obrazów i wideo. Wykorzystuje do tego trzy typy danych: Y  skªadow¡

luminancji, Cb  skªadow¡ ró»nicow¡ chrominancji Y-B, stanowi¡c¡ ró»nic¦ mi¦-

dzy luminancj¡ a niebieskim, oraz Cr  skªadow¡ chrominancji Y-R, stanowi¡c¡

ró»nic¦ mi¦dzy luminancj¡ a czerwonym. Kolor zielony jest uzyskiwany na pod-

stawie tych trzech warto±ci. YCbCr nie jest bezwzgl¦dn¡ przestrzeni¡ kolorów,

jest sposobem na opisanie informacji na podstawie danych o kolorze w postaci

RGB. Warto±¢ YCbCr mo»na okre±li¢ tylko na podstawie tych danych.

1.3 Modele sto»kowe

1.3.1 HSV
Model ten nawi¡zuje do sposobu, w jakim widzi ludzki narz¡d wzroku, gdzie

wszystkie barwy postrzegane s¡ jako ±wiatªo pochodz¡ce z o±wietlenia. Wedªug

tego modelu wszelkie barwy wywodz¡ si¦ ze ±wiatªa biaªego, gdzie cz¦±¢ widma

zostaje wchªoni¦ta, a cz¦±¢ odbita od o±wietlanych przedmiotów. Symbole w

nazwie modelu to pierwsze litery nazw angielskich dla skªadowych opisu barwy:

H  odcie« ±wiatªa (ang. Hue) wyra»ona k¡tem na kole barw przyjmuj¡ca

warto±ci od 0° do 360°. Model jest rozpatrywany jako sto»ek, którego podstaw¡

jest koªo barw.

2

S  nasycenie koloru (ang. Saturation) jako promie« podstawy oraz skªadowa

V  (ang. Value) równowa»na nazwie B  moc ±wiatªa biaªego (ang. Bright-

ness) jako wysoko±¢ sto»ka.

1.3.2 HSL
Modeli przestrzeni kolorów postrzeganych przez ludzi. Ten sposób opisowy miaª

polega¢ na tym, »e ka»dej barwie postrzeganej przez czªowieka jest przyporz¡d-

kowany jeden punkt w przestrzeni trójwymiarowej identykowany przez trzy

skªadowe: (h,s,l).

H: Hue  (z ang. odcie«, barwa), o warto±ciach z przedziaªu: od 0 do 360

stopni.

S: Saturation  nasycenie koloru. z przedziaªu 0...1 albo 0...100%.

L: Lightness  ±rednie ±wiatªo biaªe, z przedziaªu 0...1 albo 0...100%.

Ten model zakªadaª, »e barwy postrzegane przez czªowieka dadz¡ si¦ opisa¢

wªa±nie za pomoc¡ takich trzech wspóªrz¦dnych oraz dodatkowo z warunkiem,

»e punkty znajduj¡ si¦ na powierzchni bryªy obustronnego sto»ka.

1.4 Modele percepcyjnie równomierne

1.4.1 CIE - LUV
Tró jchromatycz ny model barw CIE LUV , oznaczany tak»e jako CIE L*u*v*.

Ukªad CIE LUV jest ukªadem percepcyjnie równomiernym co pozwala na in-

tuicyjne powi¡zanie o dlegªo±c i punktów na wykre sie chromatycz no± ci z

ró»nic¡ wra»e« barwy ±wiateª o tych samych luminac jach. Wi¦ksza odlegªo±¢

odpowiada wi¦kszym ró»nicom we wra»eniach, a ta sama odlegªo±¢ - zbli»onym

ró»nicom wra»e« barwy.

1.4.2 CIE - LAB
Kolorymetryczny model przestrzeni barw , rozci¡gaj¡cy si¦ pomi¦dzy barwami

przeciwstawnymi, tworz¡cymi nast¦puj¡ce wymiary: wymiar L oznaczaj¡cy ja-

sno±¢, oraz wymiary a i b. Przestrze« barw L*a*b* jest opisana jako trójwy-

miarowy system koordynat. O± a przedstawia udziaª barwy zielonej lub czerwo-

nej w analizowanej barwie, przy czym odcienie koloru zielonego maj¡ warto±¢

ujemn¡, a odcienie koloru czerwonego  warto±¢ dodatni¡. O± b przedstawia

udziaª barwy niebieskiej lub »óªtej w analizowanej barwie, przy czym odcienie

koloru niebieskiego maj¡ warto±¢ ujemn¡, a odcienie koloru »óªtego  warto±¢

dodatni¡. Skale osi a i b rozci¡gaj¡ si¦ pomi¦dzy warto±ciami -150 i +100

oraz -100 i +150, bez wzgl¦du na to, »e niektóre warto±ci nie posiadaj¡ swojego

odpowiednika w kolorze. Poniewa» przy tworzeniu przestrzeni uwzgl¦dniono po-

strzeganie barw, spektrum kolorów nie jest kwadratem, lecz nieregularn¡ bryª¡.

O± L opisuje jasno±¢ barwy w obr¦bie warto±ci od 0 do 100

3

1.5 Przeksztaªcanie modeli

1.5.1 RGB ↔ HSL

Algorithm 1 Algorytm RGB →HSV

x = MIN(MIN(red, grn), blu);

val = MAX(MAX(red, grn), blu);

if x == val then

hue=0

sat=0;

else

if red == x then

f = grn - blu

else if grn == x then

f = blu - red

else

f = red - grn

end if

end if

if red == x then

i = 3

else if grn == x then

i = 5

else

i = 1

end if

hue = ((i - f / (val - x)) * 60) % 360

sat = (val - x) / val

4

Algorithm 2 Algorytm HSV → RGB
Dane wejsciowe: hue, sat, val

Dane wyjsciowe: red, grn, blu

if val == 0 then

red = 0

grn = 0

blu = 0

else

hue /= 60

i = (hue)

f = hue-i

p = val * (1 - sat)

q = val * (1 - (sat * f))

t = val * (1 - (sat * (1 - f)));

if i == 0 then

red = val

grn = t

blu = p

else if i == 1 then

red = q

grn = val

blu = p

else if i==2 then

red = p

grn = val

blu = t

else if i==3 then

red = p

grn = q

blu = val

else if i==4 then

red = t

grn = p

blu=val

else if i==5 then

red = val

grn = p

blu = q

end if

end if

1.5.2 RGB ↔ CMY










C = 1 − R

M = 1 − G

Y = 1 − B

5

1.5.3 RGB ↔ YUV
Opisane w 1.2.1

1.5.4 YUQ↔ YUV
Opisane w 1.2.1

1.5.5 YCbCr ↔ RGB

[Y Cb Cr]=[R G B]*

0.299

−0.168935

0.499813

0.587

−0.331665

−0.418531

0.114

0.50059

−0.081282

+

0

128
128





R
G
B





=





1

0

1.40210

1

−0.34414

−0.71414

1

1.77180

0









Y

C

b

− 128

C

r

− 128





2 Formaty kompresji plików gracznych i kom-

presja obrazów

2.1 SVG

Otwarty format graki wektorowej oparty na XML

Prymitywy graczne:

ˆ Prostok¡t: <rect width=300 height=100>

ˆ Okr¡g: <circle cx=100 cy=50 r=3>

ˆ Elipsa: <ellipse cx=100 cy=150 rx=50 ry=40>

ˆ Linia: <line x1=10 y1=20 x2=100 y2=300>

ˆ Wielobok: <polygon points=220,110 300,210 170,250>

ˆ Šamana: <polyline points=0,0 0,20>

ˆ ‘cie»ka: <path d=M250 150 L150 350 L350 350 Z />

2.1.1 Filty
Format SVG obsªuguje ltry graczne, które mog¡ wpªywa¢ na grak¦. Umo»-

liwia to dodanie do obrazu ró»nych efektów jak np. rozmycie Gaussa, czy gra-

dienty.

2.2 PostScript

Uniwersalny j¦zyk przeznaczony do urz¡dze« poligracznych. Zostaª specjal-

nie zaprojektowany do tworzenia znaków tekstowych i obrazów gracznych na

drukowanych stronach.

Wykorzystuje odwrotn¡ notacj¦ - najpierw pojawiaj¡ si¦ argumenty, a potem

dziaªanie na nich.

6

2.2.1 EPS - Encapsulated PostScript
Format plików, b¦d¡cy podzbiorem j¦zyka PostScript, sªu»¡cy do przechowywa-

nia pojedynczych stron graki wektorowej w postaci umo»liwiaj¡cej osadzanie

ich w innych dokumentach.

2.3 TIFF

Format plików graki rastrowej. Wykorzystuje kompresje stratn¡ i bezstratn¡.

Ma modularn¡ budow¦ pozwalaj¡c¡ rozszerza¢ jego mo»liwo±ci.

2.4 PNG

Rastrowy format plików gracznych oraz system bezstratnej kompresji danych

gracznych. Obsªuguje przezroczysto±¢ przez kanaª alfa. C = C

i

α + C

b

(1 − α)

2.4.1 Korekcja gamma
Korekcja gamma jest operacj¡ przeskalowuj¡c¡ warto±ci jasno±ci pikseli obrazu.

Dla warto±ci γ poni»ej 1 nast¡pi przyciemnienie obrazu, za± dla warto±ci powy»ej

1 jego rozja±nienie.

2.4.2 Adam7
Adam7 to algorytm przeplotu stosowany w obrazach PNG. Przeplatany obraz

PNG podzielony jest na 7 podobrazów, z których ka»dy tworzony jest dzi¦ki

replice wzoru o wymiarach 8x8 na caªym obrazie docelowym. Podobrazy s¡

nast¦pnie zapisywane w pliku PNG w kolejno±ci rosn¡cej.

1

6

4

6

2

6

4

6

7

7

7

7

7

7

7

7

5

6

5

6

5

6

5

6

7

7

7

7

7

7

7

7

3

6

4

6

3

6

4

6

7

7

7

7

7

7

7

7

5

6

5

6

5

6

5

6

7

7

7

7

7

7

7

7

2.4.3 Sprawdzanie poprawno±ci
2.4.4 Filtracja
Jedn¡ z technik zastosowanych w PNG jest aplikowanie prostych ltrów gra-

cznych, które mog¡ upro±ci¢ dane obrazu przed kompresj¡, zwi¦kszaj¡c jej

wydajno±¢. Jest dost¦pne kilka ltrów (np. ró»nica mi¦dzy s¡siednimi pikse-

lami/liniami), które s¡ dobierane dla ka»dej linii pliku z osobna.

Filtrowanie obrazu wykonywane jest przed wªa±ciw¡ kompresj¡ i jej celem

jest uzyskanie optymalnego stopnia kompresji. Dost¦pnych jest pi¦¢ typów l-

trów:

1. None - brak

2. Sub - optymalizuje kompresj¦ obrazów z poziomymi wzorami lub przej-

±ciami tonalnymi.

7

3. Up - optymalizuje kompresj¦ obrazów z równymi wzorami pionowymi

4. Average - poprawia kompresj¦ niewielkich zakªóce« poprzez wyrównywanie

warto±ci kolorów przylegªych pikseli

5. Paeth - optymalizuje kompresj¦ niewielkich zakªóce« obrazu poprzez po-

wtórne nadawanie warto±ci kolorów przylegªych

Wybór typu ltru dokonywany jest oddzielnie dla ka»dego wiersza obrazu (w

obrazach z przeplotem oddzielnej ltracji podlega ka»da cz¦±ciowa linia). Infor-

macja o wybranym ltrze zapami¦tywana jest w pojedynczym bajcie poprze-

dzaj¡cym wªa±ciwe dane obrazu. Procesowi ltracji poddawane s¡ tak»e dane

opisuj¡ce kanaª alfa obrazu. Ka»dy z ltrów operuje na peªnych bajtach - w ra-

zie takiej potrzeby brakuj¡ce bity, bajtu opisuj¡cego ostatnie piksele w wierszu,

uzupeªniane s¡ zerami. Oczywi±cie po dekompresji obrazu przeprowadzany jest

proces odwrotny do ltracji.

2.5 JPEG

Format graki rastrowej wykorzystuj¡cy kompresj¦ stratn¡.

Obraz jest konwertowany z kanaªów czerwony-zielony-niebieski (RGB) na

jasno±¢ (luminancj¦) i 2 kanaªy barwy (chrominancje).

Ka»dy z kanaªów (jasno±¢ i 2 kanaªy barw) jest dzielony na bloki (8x8). Na

takich blokach wykonywana jest DTC. Zamiast warto±ci pikseli posiadamy teraz

informacje o ±redniej warto±ci pikseli i cz¦stotliwo±ci ich zmiany.

Potem dane te poddawane s¡ kwantyzacji (z liczb zmiennoprzecinkowych

nast¦puje zamiana na caªkowite). Wspóªczynniki DTC uporz¡dkowane s¡ tak,

aby zera le»aªy obok (zygzakowato) siebie dzi¦ki czemu dobrze si¦ kompresuj¡.

Wykorzystywany jest do tego algorytm Humana.

Algorytm umo»liwia wybór stopnia kompresji.

3 Rasteryzacja

3.1 Rasteryzacja odcinka

Algorytm Bresenhama
Zmienne u»ywane w programie:

ˆ (x, y) - wspóªrz¦dne abstrakcyjne punktu. Podane w liczbach rzeczywi-

stych. Okre±laj¡c miejsce, gdzie punkt faktycznie by¢ powinien.

ˆ (i, j) - wspóªrz¦dne ekranowe punktu. Podane w liczbach caªkowitych.

Okre±laj¡ piksel na ekranie do zapalenia.

Zaªó»my, »e x

2

> x

1

, y

2

≥ y

1

, a ponadto x

2

− x

1

≥ y

2

− y

1

.

Aby przej±¢ od abstrakcyjnych wspóªrz¦dnych do ekranowych wykonujemy za-

okr¡glanie na tych wspóªrz¦dnych.

8

Algorithm 3 Algorytm Bresenhama
Wej±cie: (i

1

, j

1

)

- wspóªrz¦dne pocz¡tku, (i

2

, j

2

)

- wspóªrz¦dne ko«ca

Wyj±cie: narysowanie odcinka

m := 2(j

2

− j

1

)

b := 0

writePixel(i

1

, j

1

)

j := j

1

P := i

2

− i

1

for i := i

1

+ 1

to i

2

do do

b := b + m

if b > P then

j := j + 1

b := b - 2P

end if

writePixel(i, j)

end for

3.1.1 Przykªad
Dokonajmy rasteryzacji odcinka o pocz¡tku w punkcie (2, 2) i ko«cu w punkcie

(10, 7).

Pocz¡tek

m = 10

b = 0

zamaluj (2, 2)

j = 2

P = 8

For 1

i = 3

b = 10 > P

j = 3

b = -6

zamaluj (3, 3)

For 2

i = 4

b = 4 < P

zamaluj (4, 3)

For 3

i = 5

b = 14 > P

j = 4

b = -2

zamaluj (5, 4)

For 4

i = 6

b = 8 = P

zamaluj (6, 4)

For 5

i = 7

b = 18 > P

j = 5

b = 2

zamaluj (7, 5)

For 6

i = 8

b = 12 > P

j = 6

b = -4

zamaluj (8, 6)

For 7

i = 9

b = 6 < P

zamaluj (9, 6)

For 8

i = 10

b = 16 > P

j = 7

b = 0

zamaluj (10, 7)

9

j\i 1 2 3 4 5 6 7 8 9 10 11

1

2

P

3

1 2

4

3 4

5

5

6

6 7

7

K

8

Tablica 1: Kolejno±¢ wy±wietlania wierzchoªków algorytmem Bresenhama

3.2 Rasteryzacja okr¦gu

Zaªo»enia
Aby narysowa¢ okr¡g wystarczy podda¢ rasteryzacji tylko poªow¦ ¢wiartki okr¦gu.

Reszta powstaje przez symetri¦.

Zaªó»my, »e dany jest okr¡g o ±rodku w punkcie (0, 0) i promieniu R. Ra-

steryzacj¦ rozpoczynamy w wierzchoªku (0, R).

Równianie okr¦gu:

x

2

+ y

2

= R

2

x

2

+ y

2

− R

2

= 0

4 · (x

2

+ y

2

− R

2

) = 0

Algorytm poszukiwaª b¦dzie nast¦pnego piksela do zamalowania. Zaªó»my, »e

znajdujemy si¦ w punkcie (x, y).

Aby stwierdzi¢ jak nale»y si¦ przesun¡¢ nale»y rozwa»y¢ powy»sze równanie

okr¦gu w punkcie (x + 1; y -

1
2

), czyli wtedy gdy przesuniemy si¦ o jeden w

prawo i póª w dóª.

f (x, y) = 4((x + 1)

2

+ (y −

1

2

)

2

− R

2

)

10

Je»eli funkcja przyjmie warto±ci wi¦ksze od zera to zamalowujemy piksel znaj-

duj¡cy si¦ w dole i w prawo, a w przeciwnym przypadku tylko ten po prawej.

Sposób wyznaczania kolejnych warto±ci:

ˆ Dla przej±cia w prawo: f(x + 1, y) = f(x, y) + 8x + 12.

ˆ Dla przej±cia w dóª i prawo: f(x + 1, y − 1) = f(x, y) + 8x − 8y + 20.

ˆ W szczególno±ci dla (0, R): f(0, R) = 5 − 4R

Algorithm 4 Algorytm rasteryzacji okr¦gu
Wej±cie: Okr¡g o promieniu R, którego ±rodek znajduje si¦ w (0, 0)

Wynik: Wy±wietlenie okr¦gu

i := 0

j := R

f := 5 - 4R

zamaluj(i, j)

while i ≤ j do

if f > 0 then

f := f + 8i - 8j + 20

j := j - 1

else

f := f + 8i + 12

end if

i := i + 1

zamaluj(i, j)

end while

Przykªad
Dokonajmy rasteryzacji okr¦gu o promieniu 5.

Pocz¡tek

i = 0

j = 5

f = -15

zamaluj(0, 5)

While 1

f = -15 + 12 = -3

i = 1

zamaluj(1, 5)

While 2

f = -3 + 8 + 12 = 17

i = 2

zamaluj(2, 5)

While 3

f = 17 + 16 - 40 + 20 = 13
j = 4
i = 3
zamaluj(3, 4)

While 4

f = 13 + 24 - 32 + 20 = 25
j = 3
i = 4
zamaluj(4, 3)

11

j\i 0 1 2 3 4 5

6

5

P 1 2

4

3

3

4

2

Tablica 2: Kolejno±¢ wy±wietlania wierzchoªków przy rasteryzacji okr¦gu

3.3 Rasteryzacja elipsy

Zaªo»enia
Rasteryzacj¦ rozpoczynamy od wierzchoªka (0, b)

Elipsa jest dana równaniem:

x

2

a

2

+

y

2

b

2

= 1

x

2

a

2

+

y

2

b

2

− 1 = 0

4a

2

b

2

 x

2

a

2

+

y

2

b

2

− 1



= 0

Rasteryzacja elipsy skªada si¦ z dwóch etapów ze wzgl¦du na to, »e elipsa po-

siada tylko dwie osie symetrii. W pierwszym poruszamy si¦ w obszarze elipsy

wyznaczanym przez maª¡ póªo± (a

2

y > b

2

x

).

Aby stwierdzi¢ jak nale»y si¦ najpierw przesuwa¢ nale»y rozwa»y¢ powy»sze

równanie elipsy w punkcie (x + 1; y -

1
2

), czyli wtedy gdy przesuniemy si¦ o

jeden w prawo i póª w dóª.

f (x, y) = 4a

2

b

2

 (x + 1)

2

a

2

+

(y −

1
2

)

2

b

2

− 1



Je»eli warto±¢ funkcji b¦dzie wi¦ksza od zera to przechodzimy w prawo i w

dóª, a je»eli mniejsza od zera to tylko w prawo.

ˆ Dla przej±cia w prawo: f(x + 1, y) = f(x, y) + 8b

2

x + 12b

2

ˆ Dla przej±cia w prawo i w dóª: f(x + 1, y − 1) = f(x, y) + 8b

2

x − 8a

2

y +

12b

2

+ 8a

2

ˆ W szczególno±ci: f(0, b) = 4b

2

− 4a

2

b + a

2

W etapie drugim poruszamy si¦ po obszarze wyznaczanym przez du»¡ póªo±

(b

2

x > a

2

y

). Musimy rozwa»y¢ równanie elipsy w punkcie (x +

1
2

; y − 1)

:

g(x, y) = 4a

2

b

2

 (x +

1
2

)

2

a

2

+

(y − 1)

2

b

2

− 1



Podobnie jak poprzednio, je»eli warto±¢ funkcji b¦dzie wi¦ksza od zera to prze-

chodzimy w prawo i w dóª, a je»eli mniejsza od zera to tylko w dóª.

ˆ Dla przej±cia z jednej póªosi na drug¡: g(x, y) = f(x, y) − 4b

2

x + 3b

2

−

4a

2

y + 3a

2

12

ˆ Dla przej±cia w dóª: g(x, y − 1) = g(x, y) − 8a

2

y + 12a

2

ˆ Dla przej±cia w prawo i w dóª: g(x + 1, y − 1) = g(x, y) + 8b

2

x − 8a

2

y +

8b

2

− 12a

2

Algorithm 5 Algorytm rasteryzacji elipsy
Wej±cie: Elipsa o ±rodku (0, 0), o promieniach a, b ∈ N

Wyj±cie: Wy±wietlenie elipsy.

i = 0

j = b

f = 4b

2

− 4a

2

b + a

2

zamaluj(i, j)

while b

2

i ≤ a

2

j

do

if f > 0 then

f = f + 8b

2

i − 8a

2

j + 12b

2

+ 8a

2

j = j - 1

else

f = f + 8b

2

i + 12b

2

end if

i = i + 1

zamaluj(i, j)

end while

g = f − 4b

2

i − 3b

2

− 4a

2

j + 3a

2

while j > 0 do

if g ≤ 0 then

g = g + 8b

2

i − 8a

2

j + 8b

2

+ 12a

2

i = i + 1

else

g = g − 8a

2

j + 12a

2

end if

j = j - 1

zamaluj(i, j)

end while

Przykªad
Dokonajmy rasteryzacji elipsy o promieniach a = 5, b = 3:

Pocz¡tek

i = 0

j = 3

f = 4 · 9 − 4 · 25 · 3 + 25 = −239

zamaluj(0, 3)

While 1

f = −239 + 12 · 9 = −131

i = 1

zamaluj(1, 3)

While 2

f = −131 + 8 · 9 + 12 · 9 = 49

i = 2

zamaluj(2, 3)

While 3

f = 49+8·9·2−8·25·3+12·9+8·25 =

−99

j = 2

i = 3

zamaluj(3, 2)

While 4

13

f = −99 + 8 · 9 · 3 + 12 · 9 = 225

i = 4

zamaluj(4, 2)

While 5

f = 225 + 8 · 9 · 4 − 8 · 25 · 2 + 12 ·

9 + 8 · 25 = 421

j = 1

i = 5

zamaluj(5, 1)

While 1

g = 421−4·9·5−3·9−4·25+3·25 =

189

g = 189 − 8 · 25 + 12 · 25 = 289

j = 0

zamaluj(5, 0)

j\i 0 1 2 3 4 5

4

3

P 1 2

2

3 4

1

5

0

6

Tablica 3: Kolejno±¢ rasteryzacji punktów elipsy

3.4 Wypeªnianie wieloboku

3.4.1 Przegl¡danie liniami poziomymi
Zaªo»enia
Wielobok b¦dzie przegl¡dany linia po linii. Zamalowywane b¦d¦ te piksele w

ka»dej linii, które znajduj¡ si¦ wewn¡trz wieloboku.

14

Algorytm

Algorithm 6 Wypeªnianie wieloboku - przegl¡danie liniami poziomymi
Wej±cie: lista kraw¦dzi wieloboku {[(x

i

, y

i

), (x

i+1

, y

i+1

)]}

Wyj±cie: Wypeªnione wn¦trze wieloboku

Usu« kraw¦dzie poziome

Uporz¡dkuj wierzchoki w kraw¦dziach, aby y

i

< y

i+1

Uporz¡dkuj kraw¦dzie w kolejno±ci rosn¡cych y

i

TAK = ∅

TAK - Tabela Aktywnych Kraw¦dzi

y := y

i

pierwszej kraw¦dzi

repeat

TAK = TAK ∪

{kraw¦dzie, których pierwszy koniec jest na linii

y}

for all kraw¦dzi z TAK do

Oblicz wspórz¦dn¡ x punktu przeci¦cia z lini¡ poziom¡ y

end for

Posortuj TAK w kolejno±ci rosn¡cych wspórz¦dnych x punktów przeci¦-

cia

for all kolejnych par kraw¦dzi z TAK do

Rysuj odcinek poziomy na linii y, mi¦dzy ich punktami przeci¦cia z lini¡

y

end for

y = y + 1

TAK = TAK \ {kraw¦dzie, którch drugi koniec jest na linii y}

until TAK = ∅

Przykªad
3.4.2 Przez zalewanie
Zaªo»enia
Obszar jest czterospójny - tzn. z ka»dego punktu z wn¦trza wielok¡ta mo»na

przej±¢ do czterech s¡siednich. Brzeg obszaru jest o±miospójny - z ka»dego

punktu z brzegu mo»na przej±¢ do o±miu s¡siednich.

Idea jest taka, »e nie mo»na przekroczy¢ brzegu.

Algorithm 7 Wypeªnianie przez zalewanie - rekurencja
Wej±cie: punkt(i, j)

Wyj±cie: zamalowany obszar

if niezamalowany wewn¦trzny piksel (i, j) then

Zamaluj poczynaj¡c z (i - 1, j)

Zamaluj poczynaj¡c z (i, j - 1)

Zamaluj poczynaj¡c z (i + 1, j)

Zamaluj poczynaj¡c z (i, j + 1)

end if

15

Algorithm 8 Wypeªnianie przez zalewanie - stos
Wej±cie: punkt (x, y) le»¡cy w obszarze

Wyj±cie: zamalowany obszar

Stos S = ∅

zamaluj(x, y)

S = S ∪ (x, y)

while S 6= ∅ do

S = S \ (i, j)

Zdj¦cie elem. i przypisanie go do zmiennych i i j

if niezamalowany wewn¦trzny piksel (i - 1, j) then

zamaluj (i - 1, j)

S = S ∪ (i - 1, j)

end if

if niezamalowany wewn¦trzny piksel (i, j - 1) then

zamaluj (i, j - 1)

S = S ∪ (i, j - 1)

end if

if niezamalowany wewn¦trzny piksel (i + 1, j) then

zamaluj (i + 1, j)

S = S ∪ (i + 1, j)

end if

if niezamalowany wewn¦trzny piksel (i, j + 1) then

zamaluj (i, j + 1)

S = S ∪ (i, j + 1)

end if

end while

Przykªad

j\i 0 1 2 3 4 5 6 7 8

0

x x x

1

x x x x

x

2

x

x

3

x

x

4

x

x

5

x

x

6

x x x x x

7

8

(a) Obszar pocz¡tkowy

j\i 0

1

2

3

4

5

6

7

8

0

x

x

x

1

x

x

x

x

7

8

9

x

2

x 25 24

5

4

6

10 12 x

3

x 23 22

1

P

3

11 13 x

4

x

21 20

2

15 14

x

5

x

19 18 17 16

x

6

x

x

x

x

x

7

8

(b) Kolejno±¢ zamalowania pikseli

Tablica 4: Wypeªnianie przez zalewanie - stos

16

4 Algorytm obcinania i okienkowania

4.1 Odcinanie prostych i odcinków

4.1.1 Algorytm Sutherlanda-Cohena
Wst¦p
Celem algorytmów odcinania i okienkowania jest wyznaczenie odcinka, prostej,

fragmentu gury, który le»y wewn¡trz okna (ustalonej bryªy wielosciennej).

Niech dany b¦dzie odcinek, którego ko«cami s¡ punkty p

1

= (x

1

, y

1

)

, p

2

=

(x

2

, y

2

)

. Dana jest równie» prosta opisana równaniem: ax + by = c. Wspóª-

czynnik t dany b¦dzie wtedy wzorem:

t =

c − ax

1

− by

1

a(x

2

− x

1

) + b(y

2

− y

1

)

Je»eli t /∈ [0, 1] to prosta i odcinek s¡ rozª¡czne.

Je»eli t ∈ [0, 1] to prosta i odcinek przecinaj¡ si¦.

Zaªo»enia

ˆ Dane s¡ punkty ko«cowe odcinka i prostok¡tne okno.
ˆ Proste, na których le»¡ kraw¦dzie okna, dziel¡ pªaszczyzn¦ na 9 obszarów
ˆ Przyporz¡dkowujemy im czterobitowe kody Graya (rysunek a)

Sprawdzanie, czy odcinek mie±ci si¦ w oknie:

1. Wyznaczamy kody obszarów, do których nale»¡ ko«ce odcinka
2. Je»eli oba kody na tej samej, dowolnej pozycji maj¡ jedynk¦ to caªy odci-

nek le»y poza oknem (rysunek b)

3. Je»eli oba punkty ko«cowe maj¡ kod 0000, to caªy odcinek le»y wewn¡trz

okna

4. Je»eli kody s¡ ró»ne od zera, ale jedynki na »adnej pozycji nie pokrywaj¡

si¦, to odcinek mo»e mie¢ cz¦±ci wewn¡trz okna

Rysunek 1: Algorytm Sutherlanda-Cohena - podziaª okna na obszary

17

Algorithm 9 Algorytm Sutherlanda-Cohena
Wªa±ciwy algorytm
Wej±cie: odcinek [p

1

, p

2

]

Wyj±cie: cz¦±¢ odcinka wewn¡trz okna

c

1

= kod(p

1

)

c

2

= kod(p

2

)

while c

1

or c

2

Dopóki c

1

i c

2

nie s¡ 0000. do

if c

1

iloczyn logiczny c

2

Czy jaka± pozycja ma 1 w obu kodach? then

∅

end if

if c

1

then

Zamie«(p

1

, c

1

)

else

Zamie«(p

2

, c

2

)

end if

end while

Procedura zamie«
Wej±cie: c = kod(p), c 6= 0, c & c' = 0

Wyj±cie: Punkt, który le»y na tym samym odcinku, kod od tego punktu ma

mniej niezerowych bitów

if pierwszy bit niezerowy then

p zamieniamy na przeci¦cie z y = top

c = kod(p)

else if drugi bit niezerowy then

p zamieniamy na przeci¦cie z y = bottom

c = kod(p)

else if trzeci bit niezerowy then

p zamieniamy na przeci¦cie z x = right

c = kod(p)

else if czwarty bit niezerowy then

p zamieniamy na przeci¦cie z x = left

end if

18

Przykªad

1001

1000

1010

0001

0010

0101

0100

0110

0000

A

B

C

D

F

H

G

E

Rysunek 2: Algorytm Sutherlanda - Cohena - przykªad

Niebieskie linie zostaj¡ odrzucone przez algorytm. Czerwone mimo i» le»¡ poza

ekranem nie zostan¡ automatycznie odrzucone i trzeba wykona¢ dla nich dodat-

kowe sprawdzenie,

4.1.2 Algorytm Lianga-Barsky'ego
Zaªo»enia
Wad¡ poprzedniego algorytmu jest to, »e obliczane s¡ odcinki, które nast¦pnie

zostan¡ odrzucone,

Skorzystajmy z parametrycznego przedstawienia odcinka:

(

x = x

1

+ s · (x

2

− x

1

) = x

1

+ t · ∆x

dla t ∈ [0, 1]

y = y

1

+ s · (y

2

− y

1

) = y

1

+ t · ∆y

Odcinek le»y w oknie je»eli

left ≤ x

1

+ t∆x ≤

right

bottom ≤ y

1

+ t∆y ≤

top

Wtedy wyznaczy¢ mo»emy parametry:

p

1

= −∆x

q

1

= x

1

−

left

p

2

= ∆x

q

2

=

right − x

1

p

3

= −∆y

q

3

= y

1

−

bottom

p

4

= ∆y

q

4

=

top − y

1

19

Algorithm 10 Algorytm Lianga-Barsky'ego
Wej±cie: Odcinek o ko«cach (x

1,

y

1

) i (x

2

, y

2

)

Wyj±cie: Wycinek odcinka le»¡cy w oknie

for k = 1 to 4 do

if p

k

== 0

Odcinek jest równolegy do kraw¦dzi then

if q

k

< 0

then

Odrzu¢ odcinek

end if

end if

if p

k

< 0

Odcinek wchodzi do okna then

u

k

= max(0,

q

k

p

k

)

end if

if p

k

> 0

then

v

k

= min(

q

k

p

k

, 1)

end if

end for

u = max(u

k

)

v = min(v

k

)

if u > v then

odcinek poza oknem

end if

return przedzia odcinka s ∈ [u, v]

4.2 Algorytm Sutherlanda-Hodgmana

4.2.1 Zaªo»enia
Algorytm Sutherlanda-Hodgmana jest analitycznym algorytmem obcinania, który

znajduje cz¦±¢ wspóln¡ dwóch wielok¡tów, przy czym wielok¡t obcinaj¡cy musi

by¢ wypukªy (wielok¡t obcinany mo»e by¢ wypukªy lub niewypukªy); wielo-

k¡ty s¡ dane jako ci¡gi wierzchoªków.

4.2.2 Algorytm
Algorytm jest iteracyjny i wykorzystuje strategi¦ dziel i zwyci¦»aj. Wykorzy-

stuje fakt, i» wielok¡t wypukªy mo»na przedstawi¢ jako cz¦±¢ wspóln¡ póªpªasz-

czyzn wyznaczanych przez boki tego wielok¡ta.

W jednym kroku algorytmu znajdywana jest cz¦±¢ wspólna wielok¡ta oraz

póªpªaszczyzny, a otrzymany w ten sposób wielok¡t jest przetwarzany w kroku

kolejnym:

1. W = obcinany wielok¡t
2. W_o = wypukªy wielok¡t obcinaj¡cy
3. dla wszystkich kraw¦dzi W_o wykonuj:

(a) L := wyznacz prost¡ na której le»y kraw¦d¹

(b) W := wyznacz cz¦±¢ wspóln¡ wielok¡ta W i póªpªaszczyzny zdenio-

wanej przez prost¡ L

20

Rysunek 3: Przykªad obcinania literki W (W jak Wikipedia) przez pi¦ciok¡t.

Po przejrzeniu wszystkich wierzchoªków otrzymuje si¦ ci¡g wierzchoªków wie-

lok¡ta b¦d¡cego cz¦±ci¡ wspóln¡ W i póªpªaszczyzny. Niestety mo»e zdarzy¢ si¦

tak, »e wielok¡t zostanie rozdzielony na dwa lub wi¦cej wielok¡tów i wówczas

pojawiaj¡ si¦ dodatkowe kraw¦dzie le»¡ce na prostej L. Mo»na je jednak wyeli-

minowa¢ po zako«czeniu caªego algorytmu.

4.2.3 Problem Cz¦±ci wspólnej wielok¡ta i póªpªaszczyzny
Pewnym problemem jest okre±lenie po której stronie prostej L znajduje si¦ wn¦-

trze wielok¡ta obcinaj¡cego W

o

. Rozwi¡zanie jest nast¦puj¡ce: nale»y prze-

gl¡da¢ wierzchoªki W

o

kolejno, tzn. (v

0

, v

1

), (v

1

, v

2

), . . . , (v

i

, v

j

), . . . , (v

n

, v

0

)

i

na ich postawie wyznacza¢ równanie prostej, np. w postaci parametrycznej:
v

i

+ t · (v

j

− v

i

)

. Wówczas je±li wierzchoªki s¡ podawane w kierunku przeciwnym

do ruchu wskazówek zegara, to wektory normalne wszystkich prostych wskazuj¡

wn¦trze.

Najwa»niejszym elementem algorytmu jest wyznaczanie cz¦±ci wspólnej wie-

lok¡ta W i póªpªaszczyzny. Przegl¡dane s¡ kolejne wierzchoªki w sposób (v

0

, v

1

), (v

1

, v

2

), . . . , (v

i

, v

j

), . . . (v

n

, v

0

)

,

w jednej iteracji analizowana jest tylko jedna kraw¦d¹; oznaczmy pierwszy wierzchoªekv

i

przez

S, drugi v

j

przez N:

1. Je±li obydwa wierzchoªki le»¡ wewn¡trz W

o

, wówczas zapami¦tywany jest

tylko wierzchoªek N.

21

2. Je±li obydwa wierzchoªki le»¡ na zewn¡trz, wówczas »aden wierzchoªek nie

jest zapami¦tywany.

3. W przeciwnym razie kraw¦d¹ W przecina prost¡ L i nale»y obliczy¢ punkt

przeci¦cia (ozn. P) odcinka S{N} z prost¡:

ˆ je±li S le»y wewn¡trz a N na zewn¡trz, to zapami¦tywany jest tylko

punkt przeci¦cia P;

ˆ Je±li jest odwrotnie (N wewn¡trz, S na zewn¡trz) to zapami¦tywane

s¡ dwa punkty: P i N (w tej kolejno±ci).

4.3 Algorytm Weilera-Athertona

4.3.1 Zaªo»enia
Algorytm Weilera-Athertona umo»liwia wyznaczenie cz¦±ci wspólnej, w ró»nych

zastosowaniach, sumy lub ró»nicy dwóch wielok¡tów dowolnych, tj. niekoniecz-

nie wypukªych, Dopuszcza dane wielok¡ty, których brzegi mog¡ skªada¢ si¦ z

wielu zamkni¦tych ªamanych; wielok¡ty takie mog¡ by¢ niejednospójne, tj. z

dziurami, albo nawet niespójne.

4.3.2 Algorytm
Podstawowe wymaganie, konieczne aby wynik byª dobrze okre±lony, to wªa±ciwe

zorientowanie brzegu. Dla ustalenia uwagi przyjmiemy umow¦, »e ka»da kra-

w¦d¹ jest zorientowana w ten sposób, »e poruszaj¡c si¦ wzdªu» niej zgodnie z

orientacj¡ mamy wn¦trze wielok¡ta po prawej stronie. Aby wyznaczy¢ przeci¦cie

wielok¡tów, kolejno:

1. Konstruujemy reprezentacje dwóch grafów zorientowanych(kierunek poka-

zuj¡ strzaªki, graf ze strzaªkami); wierzchoªkami i kraw¦dziami ka»dego z

nich s¡ wierzchoªki i zorientowane kraw¦dzie jednego z wielok¡tów.

2. Znajdujemy wszystkie punkty przeci¦cia kraw¦dzi jednego wielok¡ta z kra-

w¦dziami drugiego. Dzielimy kraw¦dzie, na których le»¡ te punkty, na

22

kawaªki; doª¡czamy w ten sposób nowe wierzchoªki do grafu, zachowu-

j¡c uporz¡dkowanie punktów podziaªu kraw¦dzi w grae. Wprowadzamy

dodatkowe powi¡zanie mi¦dzy wierzchoªkami grafów, które odpowiadaj¡

temu samemu punktowi (przeci¦cia). Tworzy si¦ w ten sposób jeden graf,

którego kraw¦dzie reprezentuj¡ kawaªki brzegu jednego lub drugiego wie-

lok¡ta.

3. Znajdujemy wierzchoªek grafu, który jest wierzchoªkiem przeci¦cia wielo-

k¡tów. Mo»e to by¢ wierzchoªek odpowiadaj¡cy punktowi przeci¦cia brze-

gów wielok¡tów, a je±li takiego nie ma, to mo»emy sprawdzi¢, czy jaki±

wierzchoªek le»y wewn¡trz drugiego wielok¡ta, korzystaj¡c z reguªy pa-

rzysto±ci. Wybieramy wychodz¡c¡ ze znalezionego wierzchoªka kraw¦d¹,

która jest kraw¦dzi¡ przeci¦cia (wyboru dokonujemy na podstawie orien-

tacji brzegów).

Zaczynaj¡c od znalezionego wierzchoªka, obchodzimy graf, a» do traenia po-

nownie na wierzchoªek, z którego wyszli±my. W ka»dym wierzchoªku, który

odpowiada przeci¦ciu brzegów, wybieramy kraw¦d¹ wielok¡ta innego ni» ten,

po którego kraw¦dzi poruszali±my si¦. Odwiedzone wierzchoªki wyprowadzamy;

ich ci¡g reprezentuje odpowiednio zorientowany fragment (zamkni¦t¡ ªaman¡)

przeci¦cia wielok¡tów danych.

Algorytm ko«czy dziaªanie po stwierdzeniu braku nieodwiedzonego wierz-

choªka nale»¡cego do brzegu wielok¡tów.

Maj¡c algorytm, który wyznacza przeci¦cie wielok¡tów, ªatwo mo»emy otrzy-

ma¢ algorytm wyznaczania sumy lub ró»nicy; dany brzeg okre±la wielok¡t, ale

tak»e jego dopeªnienie  wystarczy tylko odwróci¢ orientacj¦ wszystkich kra-

w¦dzi. W ten sposób sum¦ wielok¡tów otrzymamy jako dopeªnienie przeci¦cia

ich dopeªnie«.

Wa»ne dla poprawnej implementacji algorytmu jest uwzgl¦dnienie przypad-

ków, gdy wielok¡ty maj¡ wspólne wierzchoªki lub gdy ich kraw¦dzie maj¡ wspólne

odcinki. Pewne punkty mog¡ te» by¢ ko«cami wi¦cej ni» dwóch kraw¦dzi wielo-

k¡ta. Istotna jest mo»liwo±¢ wykonywania dziaªa« na wielok¡tach otrzymanych

za pomoc¡ tego algorytmu, i wtedy takie sytuacje zdarzaj¡ si¦ cz¦sto.

4.3.3 Przykªad

23

5 Geometria maszynowa

5.1 Macierz przeksztaªcenia anicznego

Niech B = T

u

◦ A

b¦dzie przeksztaªceniem anicznym, u =



u

1

u

2



, A =



a

11

a

12

a

21

a

22



. Macierz¡ przeksztaªcenia anicznego w R

2

nazywa si¦ macierz:

M

B

=





a

11

a

12

u

1

a

21

a

22

u

2

0

0

1





. Niech (x, y) b¦dzie punktem, wzgl¦dem którego do-

konywane jest przeksztaªcenie. Przeksztaªcenie zachodzi w nast¦puj¡cy sposób:





a

11

a

12

u

1

a

21

a

22

u

2

0

0

1









x
y

1





=





a

11

x + a

12

y + u

1

a

12

x + a

22

y + u

2

1





. Obrót, skalowanie oraz

przesuni¦cie równolegªe s¡ przykªadami przeksztaªce« anicznych.

5.1.1 Obrót
Obrót polega na obróceniu obiektu o dany k¡t. Odbywa si¦ on wzgl¦dem punktu
(0, 0)

osi wspóªrz¦dnych. Aby dokona¢ obrotu, potrzebujemy punktu i k¡ta

obrotu α. Obrót nie zmienia k¡tów gury, a tylko jej poªo»enie. Macierz obrotu

wygl¡da nast¦puj¡co:





cosθ

−sinθ

0

sinθ

cosθ

0

0

0

1





.

Przykªad:
Chcemy obróci¢ trójk¡t o wierzchoªkach A = (4, 4), B = (5, 6)i C = (2, 5) o k¡t
30

. B¦dziemy potrzebowali sinusa i cosinusa tego k¡ta.

cos30 =

√

3

2

= 0, 866

sin30 =

1
2

= 0, 5

Obliczamy poªo»enie wierzchoªka A po wykonaniu obrotu:





0, 866

0, 5

0

−0, 5

0, 866

0

0

0

1









4
4
1





=





0, 866 ∗ 4 + 0, 5 ∗ 4 + 0

0, 5 ∗ (−4) + 0, 866 ∗ 4 + 0

1





=





5, 464
1, 464

1





.

Obliczyli±my, »e po przeksztaªceniu A = (5, 464; 1, 464). W analogiczny

sposób mo»na obliczy¢ poªo»enie pozostaªych wierzchoªków. Je»eli obliczymy

wspóªrz¦dne wszystkich wierzchoªków, jeste±my w stanie wykre±li¢ nowy trójk¡t.

5.1.2 Skalowanie
Skalowanie polega na zmianie wymiarów obiektu o wspóªczynnik λ

1

na osi X

i wspóªczynnik λ

2

na osi Y. Je»eli wspóªczynnik jest wi¦kszy od zera, obiekt

jest powi¦kszany, je»eli mniejszy od zera - obiekt jest pomniejszany. Macierz

przeksztaªce« dla skalowania:





λ

1

0

0

0

λ

2

0

0

0

1









x
y

1





=





λ

1

∗ x

λ

2

∗ y

1





.

24

Przykªad:
Zaªo»my, »e chcemy podda¢ trójk¡t skalowaniu λ

1

= 0, 5

, λ

2

= 1, 5

. Nale»y

wtedy po kolei obliczy¢ wspóªrz¦dne ka»dego wierzchoªka. Je»eli jednym z wierz-

choªków jest punkt A = (4, 4), to otrzymamy:





0, 5

0

0

0

1, 5

0

0

0

1









4
4
1





=





0, 5 ∗ 4
1, 5 ∗ 4

1





=





2
6
1





.

Po przeksztaªceniu A = (2, 6). Analogicznie mo»na obliczy¢ poªo»enie pozo-

staªych wierzchoªków.

5.1.3 Przesuni¦cie równolegªe
Przesuni¦cie równolegªe polega na przesuni¦ciu wspóªrz¦dnych punktu o podan¡

warto±¢ u

1

wzdªu» osi X oraz warto±¢ u

2

wzdªu» osi Y. Macierz przeksztaªce«

dla przesuni¦cia równolegªego:





1

0

u

1

0

1

u

2

0

0

1









x
y

1





=





x + u

1

y + u

2

1





.

Przykªad:

Zaªó»my, »e chcemy przesun¡¢ równolegle trójk¡t o 3 na osi X i o 4 na osi Y.

Nale»y wtedy po kolei obliczy¢ wspóªrz¦dne ka»dego wierzchoªka. Je»eli jednym

z wierzchoªków jest punkt A = (4, 4), to otrzymamy:





1

0

3

0

1

4

0

0

1









4
4
1





=





4 + 3
4 + 4

1





=





7
8
1





.

Po przeksztaªceniu A = (7, 8). Analogicznie mo»na obliczy¢ poªo»enie pozo-

staªych wierzchoªków.

6 Rzutowanie

6.1 Algorytm malarza

Zasada dziaªania algorytmu malarza jest nast¦puj¡ca:

1. Posortuj ±ciany w kolejno±ci od najdalszej do najbli»szej obserwatora,

2. Namaluj je w tej kolejno±ci.

Prosta idea niech nie przesªania faktu, »e mog¡ istnie¢ konikty widoczno±ci, w

których ±ciana poªo»ona w zasadzie dalej zasªania cz¦±¢ ±ciany bli»szej obser-

watora. Dlatego po posortowaniu (np. ze wzgl¦du na odlegªo±¢ od obserwatora

najbli»szego punktu ka»dej ±ciany) konieczne jest sprawdzenie i ewentualna mo-

dykacja uporz¡dkowania ±cian.

25

Rysunek 4: Przykªad problemu z jakimi algorytm sobie nie poradzi

6.2 Algorytm bufora gª¦boko±ci

W algorytmie tym mamy prostok¡tn¡ tablic¦ liczb, o wymiarach równych wy-

miarom szeroko±ci i wysoko±ci obrazu w pikselach. Algorytm ten jest dosy¢

zasobo»erny

1. Przypisz wszystkim elementom z-bufora warto±¢, która reprezentuje nie-

sko«czono±¢, albo najwi¦ksz¡ dopuszczaln¡ odlegªo±¢ od obserwatora.

2. Kolejno dla ka»dej ±ciany, narysuj jej rzut (tj. dokonaj jego rasteryzacji za

pomoc¡ algorytmu przegl¡dania liniami poziomymi). Dla ka»dego piksela,

który nale»y do rzutu ±ciany, nale»y przy tym obliczy¢ wspóªrz¦dn¡ z (tj.

gª¦boko±¢) punktu w ukªadzie obserwatora. Kolor danej ±ciany przypi-

sujemy pikselowi tylko wtedy, gdy obliczona wspóªrz¦dna z jest mniejsza

ni» aktualna zawarto±¢ bufora gª¦boko±ci. Jednocze±nie z przypisaniem

koloru nale»y uaktualni¢ zawarto±¢ bufora.

Rysunek 5: Inicjalizacja i nadpisywanie bufora nowymi warto±ciami

6.3 Rodzaje

6.3.1 Rzutowanie równolegªe
Rzutowanie nazywamy równolegªym, gdy promienie rzutuj¡ce s¡ prostymi rów-

nolegªymi. Jest to przeksztaªcenie, w którym ignorujemy warto±¢ wspóªrz¦dnej

z: (x, y, z) → (x, y).

26

Macierz rzutowania równolegªego







2

r−l

0

0

−

r+l
r−l

0

2

t−b

0

−

t+b
t−b

0

0

−

2

f −n

−

f +n
f −n

0

0

0

1







Oznaczenia:

r, l (right, left) - granice wspóªrz¦dnej okre±laj¡cej szeroko±¢ (l ≤ x ≤ r)

b, t (bottom, top) - granice wspóªrz¦dnej okre±laj¡cej wysoko±¢ (b ≤ y ≤ t)

n, f (near, far) - granice wspóªrz¦dnej okre±laj¡cej gª¦boko±¢ (n ≤ −z ≤ f)

6.3.2 Rzutowanie perspektywiczne
Rzutowanie nazywamy perspektywicznym, gdy promienie rzutuj¡ce tworz¡ p¦k

prostych. Rzutowanie perspektywiczne mo»na opisa¢ w nast¦puj¡cy sposób:
(x, y, z) → (−

dx

z

, −

dy

z

, A +

B

z

)

.

Macierz rzutowania perspektywicznego






d

0

0

0

0

d

0

0

0

0

−A

−B

0

0

−1

0







Funkcja gª¦boko±ci
Niech A =

f +n
f −n

, B =

2f n

f −n

.

Wówczasg l˛eboko´s´c(z) = A +

B

z

.

Bryªa widzenia
Bryªa widzenia jest zbiorem punktów, których rzuty nale»¡ do klatki tzn. pro-

stok¡tu le»¡cego w rzutni (intuicyjnie: mo»na sobie wyobrazi¢ klatk¦ jako ekran,

na którym jest wy±wietlany obraz).

Macierz:







2n

r−l

0

r+l
r−l

0

0

2n

t−b

t+b
t−b

0

0

0

−

f +n
f −n

−

2f n

f −n

0

0

−1

0







.

Niech θ oznacza k¡t widzenia, a =

w

h

oznacza format obrazu (aspect ratio).

Wówczas macierz rzutowania perspektywicznego mo»na zapisa¢ nast¦puj¡co:







1
a

ctg(θ/2)

0

0

0

0

ctg(θ/2)

0

0

0

0

−

f +n
f −n

−

2f n

f −n

0

0

−1

0







27

6.4 Zastosowanie

6.4.1 Cie«
Jest to przeksztaªcenie (x, y, z) → (

x

1−y/y

0

, 0,

z

1−y/y

0

)

. Macierz przeksztaªcenia

dla tworzenia cienia:







1

0

0

0

0

0

0

0

0

0

1

0

0

−

1

y

0

0

1







.

6.4.2 Z-ghtning
Jest to graczna anomalia spowodowana przez dwie powierzchnie o takich sa-

mych warto±ciach w buforze gª¦boko±ci. Wizualnie manifesuje si¦ to naprze-

miennym wy±wietlaniem fragmentów powierzchni tych primitywów, aby unikn¡¢

z-ghtingu stosuje si¦ bufory gª¦boko±ci o wy»szej rozdzielczo±ci, lub po prostu

przesuwa si¦ geometri¦ tak, aby powierzchnie przestaªy ze sob¡ kolidowa¢.

7 O±wietlenie

7.1 Model odbicia ±wiatªa Phonga

Model odbicia Phonga jest jest modelem odbicia ±wiatªa. Zakªada si¦, »e ¹ró-

dªem ±wiatªa jest punkt., a ±wiatªo ma trzy skªadowe: RGB(α).

‘wiatªo docieraj¡ce do obserwatora jest sum¡:

ˆ ‘wiatªa odbijanego zwierciadlanie: I

s

ˆ ‘wiatªa rozproszonego: I

d

ˆ ‘wiatªa otoczenia: I

a

ˆ ‘wiatªa emitowanego powierzchni¡: I

e

I = I

s

+ I

d

+ I

a

+ I

e

7.1.1 Odbicie rozproszone
Jest to ±wiatªo, które rozprasza si¦ na obiekcie i ma kolor taki jak przypisany

do obiektu. ‘wiatªo rozprasza si¦ we wszystkich kierunkach równomiernie.

(a) Model pogl¡dowy

(b) Model matematyczny

Rysunek 6: Rozproszenie ±wiatªa

28

‘wiatªo rozproszone obliczamy zgodnie z modelem Lamberta:

I

d

= ρ

d

I

I

n

d

cos θ

gdzie:

ˆ I

I

n

d

- nat¦»enie ±wiatªa, które zostanie rozproszone

ˆ ρ

d

- wspóªczynnik odbicia ±wiatªa

ˆ θ - k¡t padania ±wiatªa

7.1.2 Odbicie zwierciadlane
‘wiatªo odbija si¦ od obiektu i nie zmienia swojej barwy. Odbite ±wiatªo jest

emitowane w¡sk¡ wi¡zk¡ w jednym kierunku.

(a) Model pogl¡dowy

(b) Model matematyczny

Rysunek 7: Odbicie zwierciadlane

Nat¦»enie ±wiatªa odbitego zwierciadla wyznacza nast¦puj¡cy wzór:

I

s

= ρ

s

I

I

n

s

(cos ϕ)

f

gdzie:

ˆ ρ

s

- wspóªczynnik odbicia zwierciadlanego

ˆ I

I

n

s

- nat¦»enia ±wiatªa padaj¡cego

ˆ ϕ - ró»nica mi¦dzy k¡tem rzeczywistym obserwacji, a k¡tem doskonaªego

odbicia

ˆ f - wspóªczynnik okre±laj¡cy wªa±ciwo±ci powierzchni

7.1.3 ‘wiatªo otoczenia
‘wiatªo, które wynika z wªasno±ci otoczenia.

I

a

= ρ

a

I

I

n

a

gdzie

ˆ ρ

a

- wspóªczynnik otoczenia

ˆ I

I

n

a

- nat¦»enie ±wiatªa padaj¡cego

29

7.1.4 ‘wiatªo emitowane powierzchni¡
‘wiatªo emitowane, gdy obiekt ±wieci.

I

e

=

Const

7.2 Cieniowanie

7.2.1 Cieniowanie Gourauda
Zaªo»enia
Pªaszczyzna cieniowana podzielona na trójk¡ty (inne wielok¡ty s¡ triangulowane).

Zastosowania:

ˆ Obliczenie wektorów normalnych do wierzchoªków wielok¡tów i wyznacze-

nie k¡ta padania ±wiatªa w danym miejscu bryªy  pozwala to na obliczenie

jasno±ci danego wierzchoªka

ˆ Cieniowanie wzdªu» kraw¦dzi wielok¡tów metod¡ interpolacji liniowej

ˆ Cieniowanie wzdªu» kolejnych wierszy wielok¡tów (te» metod¡ interpo-

lacji liniowej)

Uogólnienie algorytmu  uwzgl¦dnienie oprócz interpolacji jasno±ci równie» in-

terpolacji barw

30

Algorytm

Algorithm 11 Cieniowanie Gourauda

1. Posortuj wierzchoªki trójk¡ta wzgl¦dem ich wspólrz¦dnych y. (od najm-

niejszej do najwi¦kszej)

2. Oblicz przyrosty mi¦dzy wierzchoªkami trójk¡ta na podstawie wzorów.

dx

12

=

x

2

−x

1

y

2

−y

1

; dx

12

=

x

3

−x

1

y

3

−y

1

; dx

23

=

x

3

−x

2

y

3

−y

2

; i

12

=

i

2

−i

1

y

2

−y

1

; i

13

=

i

3

−i

1

y

3

−y

2

;

i

23

=

i

3

−i

2

y

3

−y

2

W przypadku koloru 24 bitowego nale»y interpolowa¢ ka»d¡ ze skªadowych

koloru oddzielnie.

3. y = y

1

; x

11

= x

1

; x

12

= x

2

; c

1

= c

1

; c

2

= c

2

4. Rysuj lini¦ poziom¡ od punktu (x

11

,y) do punktu (x

12

,y) z pªynnym prze±-

ciem koloru od c

1

do c

2

,

5. x

11

= x

11

+ dx

12

6. x

12

= x

12

+ dx

13

7. c

1

= c

1

+ i

12

8. c

2

= c

2

+ i

13

9. y = y +1

10. Je»eli y < y

2

skacz do punktu 4.

11. y = y

2

; x

11

= x

2

; x

12

= x

3

; c

1

= c

2

; c

2

= c

3

12. Rysuj lini¦ poziom¡ do punktu (x

11

,y) do punktu (x

12

,y) z pªynnym prze-

j±ciem koloru od c

1

do c

2

, pami¦taj aby sprawdzi¢ cz x

11

≤ x

12

(w razie

potrzeby zmie« kolejno±¢ punktów).

13. x

11

= x

11

+ dx

13

14. x

12

= x

12

+ dx

13

15. c

2

= c

2

+ i

13

16. c

3

= c

3

+ i

23

17. y = y + 1

18. Je»eli y < y

3

to skacz do punktu 10

31

Przykªad

Kula cieniowana algorytmem Gourauda. Widoczne s¡ poszczególne elementy

pojedy«czych wielok¡tów.

Uwagi
Mo»na straci¢ ±wiatªo odbijane zwierciadlane na du»ych wielobokach (dlatego

stosuje si¦ podziaª na jak najmniejsze wieloboki)

Mo»na nie zauwa»y¢ ±wiatªa na szerokiej ±cianie

Wynik zale»y od blisko±ci ±wiatªa wierzchoªków oraz od orientacji prostopadªych

w wierzchoªkach

7.2.2 Cieniowanie Phonga
Zaªo»enia
Pªaszczyzna cieniowana podzielona na trójk¡ty (inne wielok¡ty s¡ triangulowane).

Algorytm
1. Wyznaczamy wektor normalny w wierzchoªku w ten sam sposób jak w

cieniowaniu Gouraud.

2. Wyznaczamy interpolowany wektor normalny dla ka»dego piksela (to

znaczy dla punktu powierzchni odpowiadaj¡cego pikselowi).

3. Wyznaczamy barw¦ piksela, na podstawie interpolowanego wektora nor-

malnego korzystaj¡c z wybranego modelu odbicia ±wiatªa

32

Przykªad

Na rysunku powy»ej zostaª pokazany przykªad cieniowania trójk¡ta, dla

którego dane s¡ normalne ~

N

A

, ~

N

B

i ~

N

C

Przed rasteryzacj¡ pikseli w wier-

szu y (y jest podany we wspóªrz¦dnych ekranu) obliczane s¡ normalne

~

N

A−B

i

~

N

A−C

. Nast¦pnie, dla ka»dego piksela w wierszu wyznaczana jest normalna

~

N

X

.

Uwagi
Kosztowne obliczenia

Interpolacja we wspóªrz¦dnych ekranowych (mog¡ wyst¡pi¢ nieporz¡dane

efekty przy projekcji perspektywicznej)

Caªa informacja o kolorach i kierunkach ±wiatªa powinna by¢ przechowywana

do ostatniego stadium oblicze« - algorytm kosztowny ze wzgl¦du na pami¦¢

7.3 ™ródªa

7.3.1 ‘wiatªo punktowe
‘wiatªo punktowe emitowane jest z okre±lonego punktu i rozchodzi si¦ we wszys-

tkich kierunkach z jednakowym nat¦»eniem. Posiada zdeniowan kolor, inten-

sywno±¢, pozycj¦, zasi¦g dziaªania i wspóªczynniki, okre±laj¡ce sposób zanikania

±wiatªa, wraz z oddalaniem si¦ od ¹ródªa. ‘wiatªa punktowe s¡ znacznie bardziej

kosztowne pod wzgl¦dem obliczeniowym od ±wiateª kierunkowych. U»ywany do

odwzorowywania obiektów, np. »arówki.

I=Is+Id+Ia+Ie (patrz wy»ej)

wspóªczynnik tªumienia: a=

1

a

o

+a

1

d+a

2

d

2

, gdzie d - odlegªo±¢ od ¹ródªa ±wiatªa

33

7.3.2 ‘wiatªo kierunkowe
‘wiatªo kierunkowe posiada jedynie kierunek, kolor i intensywno±¢. Promienie

emitowane z tego typu ¹ródªa rozchodz¡ si¦ w caªej pªaszczy¹nie, równolegle

do kierunku padania ±wiatªa. Dla tego typu ±wiatªa nie mo»na okre±li¢ ta-

kich parametrów jak zasi¦g, czy sposób zaniku. Ten typ ±wiatªa jest najmniej

czasochªonny obliczeniowo. U»ywany do imitowania ¹ródeª ±wiatªa oddalonych

(umieszczonych w niesko«czono±ci) od sceny, np. sªo«ce, ksi¦»yc.

7.3.3 ‘wiatªo spot
Posiada okre±lony kolor, intensywno±¢, pozcyj¦, kierunek w przestrzeni, k¡ty

mi¦dzy kraw¦dziami tworz¡cymi sto»ki oraz parametr, okre±laj¡cy sposób zanika-

nia ±wiatªa mi¦dzy granic¡ sto»ka wewn¦trznego, a sto»ka zewn¦trznego. ‘wiatªo

rzucane przez tego typu reektor skªada si¦ z dwóch sto»ków: wewn¦trzny jest

ja±niejszy, emituj¡cy wªa±ciwe ±wiatªo i zewn¦trzny, zwykle ciemniejszy, okre±la-

j¡cy obszar, w którym ±wiatªo zanika.

I={

I

0

(cosψ)

p

, je ˙

zeli ψ < ψ

0

w przeciwny przypadku 0

8 Teksturowanie

8.1 Idea

ˆ Tekstura zawiera informacje o kolorach, które maj¡ zast¡pi¢ obliczone

kolory powierzchni.

ˆ Tekstura zawiera informacje o kolorach, blasku, przezroczysto±ci, które

maj¡ zmieni¢ charakterystyki powierzchni po obliczniach o±wietlenia i

cieniowania.

ˆ Tekstura zawiera parametry, maj¡ce wpªyw na obliczenie o±wietlenia (wspóªczyn-

nik odbicia, przemieszczenie wektoru normalnego, etc).

8.2 Czym jest tekstura ?

ˆ Zdj¦cie, obrazek skanowany, utworzony edytorem gracznym.
ˆ Obrazek zaprogramowany (skompilowany, generowany nabie»¡co).

34

ˆ Obrazek generowany podaczas mapowania (odbicie).

Teksturowanie [0, 1] × [0, 1] → model

8.3 Mapowanie tekstury

Odwzorowanie wspóªrz¦dnych dwuwymiarowej tekstury na wspóªrz¦dne obiektu

trójwymiarowego nazywane jest mapowaniem(mapowaniem tekstury)

Wybór lokalnych wspóªrz¦dnych dla tekstury

ˆ Pªaszczyzna.
ˆ Sze±cian.
ˆ Powierzchnia parametryzowana

P (u, v)
Wspóªrz¦dne na teksturze zale»¡ od u i v. (Mo»e by¢ równie» odp(u, v),

wektoru normalnego do powierzchi, etc.)

8.3.1 Mapowanie cylindryczne
Mapowanie cylindryczne stosuje si¦ do obiektów cylindrycznych, wª¡czaj¡c obiekty

o powierzchniach okresowych oraz posiadaj¡cych punkt pocz¡tkowy i ko«cowy,

jak np. sto»ki oraz wyci¡gni¦cia po prolach.

ˆ p(θ, y) = (r sin θ, y, r cos θ), 0 6 θ < 360, −h/2 6 y 6 h/2

ˆ s =

θ

360

, t =

y+h/2

h

8.3.2 Mapowanie sferyczne
Mapowanie sferyczne stosuje si¦ do obiektów sferycznych, wª¡czaj¡c cz¦±ciowe

kule.

P (θ, ϕ) = (r sin θ cos ϕ, r sin ϕ, r cos θcosϕ)

ˆ s =

θ

360

, t =

ϕ

180

+

1
2

ˆ s =

θ

360

, t =

sinϕ

2

+

1
2

8.3.3 Mapowanie torusa

P (θ, ϕ) = ((R + r cos ϕ) sin θ, r sin ϕ, (R + r cos ϕ) cos θ)

s =

θ

360

, t =

ϕ

360

8.4 Aliasing

8.4.1 Idea

ˆ Rozdzielczo±¢ tekstury jest mniejsza od rozdzielczo±ci ekranu
ˆ Rozdzielczo±¢ tekstury jest wi¦ksza od rozdzielczo±ci ekranu
ˆ Miganie, interferencja, plamy
ˆ Obiekty ruszaj¡ce si¦

35

8.4.2 Mipmapping
Mipmapping to technika teksturowania bitmapami wykorzystywana w grace

trójwymiarowej, która pozwala unikn¡¢ artefaktów i tym samym uzyska¢ lepsz¡

jako±¢ obrazów.

Mipmapping

ˆ Zastosowanie skalowanych tekstur

ˆ Interpolacja najbli»szych tekstur

ˆ Zwi¦kszenie pr¦dko±ci

ˆ Zwi¦kszenie pami¦ci o 33%

ˆ Jest implemientowany sprz¦towo

8.4.3 Supersampling
Innym rodzajem antyaliasingu jest supersampling (nadpróbkowanie). Jest to

rozwi¡zanie polegaj¡ce na u»yciu tzw. Brute force do rozwi¡zania problemu

aliasingu. W tej technice obraz jest renderowany w rozdzielczo±ci odpowiada-

j¡cej wielokrotno±ci rozdzielczo±ci docelowej, a uzyskany tym sposobem du»o

wi¦kszy obraz jest dyskretyzowany do wªa±ciwej, ni»szej rozdzielczo±ci.

ˆ Zwykªy

ˆ Stochastyczny

ˆ Jittering (uktacje)

8.5 Mapowanie wypukªo±ci

Mapowanie wypukªo±ci (ang. bump mapping)  technika teksturowania, która

symuluje niewielkie wypukªo±ci powierzchni, bez ingerencji w geometri¦ obiektu

trójwymiarowego

ˆ Zmiana wektora normalnego

ˆ Przed obliczniem o´swietlenia

8.6 Mapowanie ±rodowiska

Dany jest maªy zwierciadlany obiekt (kula, sze±cian).

Oblicza si¦ (robi si¦ zdj¦cie) mapa tekstury jako obraz otoczenia widoczny

od±rodka obiektu

36

9 Krzywe Béziera

9.1 Parametryzacja

Parametryzajc¡ krzywej na pªaszczy¹nie nazywamy odwzorowanie:
p : [a, b] → R

2

gdzie [a,b] jest pewnym odcinkiem zawartym w R.

p(t) = (x(t) , y(t)), gdzie x, y s ˛

a ci ˛

ag lymi f unkcjami [a, b] → R

Uwaga: dla ka»dej parametryzacji mo»emy wyznaczy¢ parametryzacj¦ repre-

zentuj¡c¡ t¡ sam¡ krzyw¡ ale o parametrze t ∈ [0, 1]. Parametrzyacje takie

ró»ni¡ si¦ tylko tym jak szybko punkt przebiega po krzywej gdy zmieniamy t.

9.2 Wielomiany Bernsteina i denicja krzywej Béziera

Wielomiany Bernsteina n-tego stopnia deniujemy nast¦puj¡co:

B

n

i

(t) =

n

i



t

i

(1 − t)

n−i

gdzie i = 0, . . . , n

.

Wida¢, »e i-ty wielomian jest i-tym skªadnikiem rozwini¦cia wzorem Newtona

wyra»enia:

1

n

= (t + (1 − t))

n

=

n

X

i=0

n

i



t

i

(1 − t)

n−i

=

n

X

i=0

B

n

i

(t)

Przykªad:Wielomian Bernsteina stopnia 3

B

i

(u) =

3

i

u

i

(1 − u)

3−i

st¡d:
B

0

(u) = (1 − u)

3

, B

1

(u) = 3u(1 − u)

2

, B

2

(u) = 3u

2

(1 − u)

, B

3

(u) = u

3

suma wynosi:

P

3
i=i

B

i

(u) =

P

3
i=0

3

i

∗ u

i

(a − u)

3−i

= (u + (1 − u))

3

= 1

Krzyw¡ Béziera n-tego stopnia deniujemy jako krzyw¡ o parametryzacji: p(t) =

P

n
i=0

p

i

B

n

i

(t)

gdzie: p

0

, p

1

, . . . , p

n

s¡ wybranymi punktami tworz¡cymi ªaman¡

kontroln¡. Intuicyjnie mo»na to rozumie¢ tak: ka»dy punkt ªamanej kontrol-

nej ma swój wielomian Bernsteina, który dla danego t decyduje o tym jak du»y

wpªyw (jak bardzo przyci¡ga) ma na poªo»enie punktu krzywej p(t) dany punkt

kontrolny.

Przykªad: Krzywa Béziera stopnia 3.

q (u) = B

0

(u) p

0

+ B

1

(u) p

1

+ B

2

(u) p

2

+ B

3

(u) p

3

(u + (1 − u)) = (1 − u)

3

+ 3u (1 − u)

2

+ 3u

2

(1 − u) + u

3

dla u ∈ [0.1]

37

1 = B

0

(u) + B

1

(u) + B

2

(u) + B

3

(u)

0 ≤ B

i

(u) ≤ 1

(a) Krzywa Béziera trzeciego

stopnia

(b) Punkty kontrolne le»¡ po

ró»nych stronach krzywej

(c) Punkty kontrolne zostaªy za-

mienione miejscami

Rysunek 8: Krzywe Beziera

9.3 Wªasno±ci wielomianów Bernsteina i ich konsekwencje

dla krzywych Béziera

1. B

n

i

(t) = (1 − t) B

n−1

i

(t) + t B

n−1

i−1

(t)

- wzór rekurencyjny na obliczenie wie-

lomianu n-tego stopnia przy pomocy wielomianów n-1 stopnia.
Konsekwencja: algorytm deCasteljau daj¡cy mo»liwo±¢ du»o wydajniej-

szego obliczenia punktu krzywej dla danego t.

2. P

n
i=0

B

n

i

(t) = 1

- rozkªad jedynki.

Konsekwencja: niezmienniczo±c aniczn¡ krzywej Béziera. Oznacza to,

»e mo»emy ªaman¡ kontroln¡ potraktowa¢ dowolnym przeksztaªceniem a-

nicznym (np obrót, przesuni¦cie, skalowanie) a otrzymana w ten sposób

ªamana b¦dzie reprezentowa¢ krzyw¡ Béziera o takim samym ksztaªcie,

b¦d¡c¡ obrazem wyj±ciowej krzywej w danym przeksztaªceniu (czyt. ob-

rócon¡, przesuni¦t¡, przeskalowan¡).

3. ∀

t∈[0,1]

B

n

i

(t) ≥ 0

- nieujemno±¢.

Konsekwencja: w poª¡czeniu z 1. daje wªasno±¢ otoczki wypukªej.

4. ∀

t∈(0,1)

B

n

i

(t) > 0

- dodatnio±¢.

Konsekwencja: na poªo»enie ka»dego punktu krzywej (poza pierwszym

i ostatnim) maj¡ wpªyw wszystkie punkty ªamanej kontrolnej.

38

5. B

n

0

(0) = 1, B

n

i

(0) = 0

dla ka»dego i=1,.., n.

Konsekwencja: krzywa zawsze przechodzi przez pierwszy punkt kontro-

lny

6. B

n

n

(1) = 1 B

n

i

(1) = 0

dla ka»dego i=1,.., n.

Konsekwencja: krzywa zawsze przechodzi przez ostatni punkt kontrolny.

7. B

n

i

(t) = B

n

n−1

(1 − t)

- symetryczno±¢.

Konsekwencja: je»eli ªamana kontrolna jest symetryczna to krzywa

któr¡ reprezentuje równie» jest symetryczna.

8. B

n

i

(t) = 0

gdy t =

i

n

- to znaczy,»e i-ty wieolomian Bernsteina osi¡ga

ektremum (dokªadnie maksimum) dla t =i/n

Konsekwencja: punkt kontrolny p

i

ma najwi¦kszy wpªyw na poªo»enie

punktu p(

i

n

)

krzywej.

9.4 Algorytm de Casteljau

9.4.1 Zaªo»enia
Dana jest dowolna ªamana zdeniowana przez n + 1 wierzchoªków p

0

, p

1

, ..., p

n

oraz liczba t ∈ [0, 1] .Ka»dy odcinek ªamanej jest dzielony w stosunku t : 1 − t,

czego wynikiem jest n wierzchoªków, które wyznaczaj¡ now¡ ªaman¡. Proces

powtarzny jest do chwili, a» zostanie jeden punkt p (t), co wymaga n kroków.

Ostatecznie otrzymuje si¦ n + 1 ci¡gów punktów(indeks górny oznacza krok al-

gorytmu)

p

(0)
0

, p

(0)
1

, p

(0)
2

, p

(0)
3

, p

(0)
4

..., p

(0)
n

p

(1)
0

, p

(1)
1

, p

(0)
2

, p

(0)
3

, ..., p

(1)
n

...

p

(1)
0

, p

(1)
1

, ..., p

(1)
n

p

(n−1)
0

, p

(n−1)
1

p

(n)
0

Punkt p(t)

(n)

le»y na krzywej Béziera, której ªaman¡ kontroln¡ tworz¡ wyj±-

ciowe punkty p

(0)
0

, p

(0)
1

, p

(0)
2

, . . . , p

(0)
n

. Wykonuj¡c algorytm dla wszystkich t z

przedziaªu[0, 1] otrzymywane s¡ wszystkie punkty krzywej Béziera.

9.4.2 Algorytm

39

Algorithm 12 Algorytm de Casteljau
Wej±cie: p

0

, p

1

, ... p

n

- punkty kontrolne, t ∈ [0, 1] - parametr

Wyj±cie: punkt p(t) le»¡cy na krzywej

p

(0)
i

:= p

i

, i = 0, 1, ... , n

for j:=1 to n do

for i:=0 to n do

p

(j)
i

:= (1 − t) p

(j−1)
i

+ t p

(j−1)
i+1

end for

end for
p(t) := p

(n)
0

9.4.3 Przykªad dla czterech punktów kontrolnych p

0

, p

1

, p

2

, p

3

i t =

1
2

n = 3
p

(1)
i

oznacz.

=

r

i

= (1 − t) ∗ p

i

+ t ∗ p

i+1

r

0

=

1
2

p

0

+

1
2

p

1

r

1

=

1
2

p

1

+

1
2

p

2

r

2

=

1
2

p

2

+

1
2

p

3

p

(2)
i

oznacz.

=

s

i

= (1 − t) ∗ r

1

+ t ∗ r

i+1

s

0

=

1
2

r

0

+

1
2

r

1

=

1
4

p

0

+

2
4

p

1

+

1
4

p

2

=

1
4

p

0

+

1
2

p

1

+

1
4

p

2

s

1

=

1
2

r

1

+

1
2

r

2

=

1
4

p

1

+

2
4

p

2

+

1
4

p

3

=

1
4

p

1

+

1
2

p

2

+

1
4

p

3

p

(3)
i

oznacz.

=

t

i

= (1 − t) ∗ s

1

+ t ∗ s

i+1

t

0

=

1
2

s

0

+

1
2

s

1

=

1
8

p

0

+

2
8

p

1

+

1
8

p

2

+

1
8

p

1

+

2
8

p

2

+

1
8

p

3

=

1
8

p

0

+

3
8

p

1

+

3
8

p

2

+

1
8

p

3

p(

1
2

) = t

0

Rysunek 9: Algorytm de Casteljau dla czterech punktów kontrolnych

9.4.4 Wykorzystanie algorytmu do podziaªu krzywej Béziera na dwie

krzywe Béziera

p

(0)
0

, p

(0)
1

, p

(0)
2

, p

(0)
3

, p

(0)
4

..., p

(0)
n

p

(1)
0

, p

(1)
1

, p

(0)
2

, p

(0)
3

, ..., p

(1)
n

...

p

(1)
0

, p

(1)
1

, ..., p

(1)
n

p

(n−1)
0

, p

(n−1)
1

40

p

(n)
0

Za pomoc¡ algorytmu mo»na podzieli¢ krzyw¡ na dwie krzywe w punkciep(t).

Šamane kontrolne s¡ wyznaczane przez punkty le»¡ce na brzegach przedstaw-

ionego wy»ej "trójk¡ta punktów" - ªaman¡ kontroln¡ pierwszej krzywej opisuj¡
punkty: p

(0)
0

, p

(1)
0

, . . . , p

(n−1)
0

, p

(n)
0

,

a drug¡:p

(0)
n

, p

(1)
n−1

, . . . , p

(n−1)
1

, p

(n)
0

.

Obie krzywe

s¡ tego samego stopnia co dzielona krzywa. Przykªad:
Niech q (u)b¦dzie krzyw¡ Beziera o punktach kontrolnych p

0

, p

1

, p

2

, p

3

. Wt-

edy q

1

= q (u/2)

b¦dzie krzyw¡ Beziera o punktach kontrolnych p

0

, r

0

, s

0

, t

0

,

q

2

(u) = q ((u + 1) /2)

b¦dzie krzyw¡ Beziera o punktach t

0

, s

1

, r

2

, p

3

.

Figure 10: Podziaª krzywej

9.5 Krzywa Béziera jako ci¡g odcinków prostych

Aby renderowa¢ krzyw¡ Béziera dzieli si¦ j¡ za pomoc¡ algorytmu de Casteljau

tak wiele razy a» otrzymane kawaªki b¦d¡ do±¢ pªaskie aby móc je narysowa¢

za pomoc¡ odcinków prostych. Aby oceni¢ czy dany kawaªek jest wystarczaj¡co

pªaski oblicza si¦ odlegªo±¢ punku q(1/2) od punku b¦d¡cego ±rodkiem odcinka

ª¡cz¡cego pocz¡tek i koniec krzywej jak pokazano na rysunku. I porównuje z

arbitralnie ustalon¡ liczb¡ ε. Je»eli odlegªo±¢ jest mniejsza dany kawaªek krzywej

zast¦puje si¦ odcinkiem ª¡cz¡cym jej pierwszy i ostatni punkt. Je»eli nie rozbij¡

si¦ j¡ na dwie krzywe, o wspólnym punkcie q(1/2) zgodnie z 9.4.4.

q(1/2)

p

0

p

1

p

2

p

3

1/2(p

0

+p

3

)

Rysunek 11: Rasteryzacja krzywej Béziera

41

||q(1/2) − 1/2(p

0

+ p

3

)|| ≤ 

Z algorytmu de Casteljau otrzymujemy:

q (1/2) = 1/8p

0

+ 3/8p

1

+ 3/8p

2

+ 1/8p

3

|| − 3/8|| ||p

0

− p

1

− p

2

+ p

3

|| ≤ 

||p

0

− p

1

− p

2

+ p

3

|| ≤

8

3



9.6 Wªa±ciwo±¢ i konsekwencje otoczki wypukªej

Otoczka wypukªa zbioru- jest to najmniejszy zbiór wypukªy, który zawiera tem

zbiór.

Š¡cz¡c ze sob¡ kolejne punkty kontrolne krzywej Béziera otrzymamy pewien

wielok¡t. Z 2 i 4 wªasno±ci wielomianów Bernsteina mo»na pokaza¢, »e wszystkie

punkty krzywej le»¡ wewn¡trz otoczki wypukªej tego wielok¡ta.

Ilustruje to rysunek na którym pokazano dwie krzywe q

1

oraz q

1

i ich otoczki

wypukªe w których si¦ zawieraj¡.

Rysunek 12: Otoczka wypukªa

9.7 Sklejanie krzywych

Aby poª¡czy¢ ze sob¡ dwie krzyw Bezier wystarczy aby ostatni punkt kontrolny

pierwszej pokrywaª si¦ z pierwszym drugiej (na rys. p

1,3

= p

2,0

)

. Zazwyczaj

jednak interesuje nas aby poª¡czenie byªo gªadkie. Aby to osi¡gn¡¢ wystarczy,

aby przedostatni punkt pierwszej krzywej, punkt zª¡czenia oraz drugi punkt

krzywej le»aªy na jednej linii (na rys. p

1,2

, p

1,3

= p

2,0

, p

2,1

). Mocniejszym

warunkiem na gªadko±¢ jest aby pochodne obu krzywych w punkcie poª¡czenia

byªy równe tzn. q

1

(1)

0

= q

2

(0)

0

.

42

Rysunek 13: Sklejanie krzywych Beziera

9.7.1 Splajny Catmulla-Roma
Zaªo»enia
Dane s¡ punkty P

0

, ..., P

m

i w¦zªy u

i

= i

dla i = 0, ..., m. Okre±li¢ parametry-

zowan¡ krzyw¡ q (u)tak, »eby q (i) = P

i

dla i = 1, ..., m − 1.Krzywa Catmull-

Rom skªada si¦ z m-2 krzywych Beziera.Punkty kontrolne wybiera si¦ tak, »eby

krzywa byªa klasy C

1

.

Syngularno±¢

9.8 Podwy»szanie stopnia

9.8.1 Zaªo»enia
Mamy krzyw¡ Beziera st. n o punktach kontrolnych: p

0,

p

1

, ... p

n

i parametryza-

cji p(t). Chcemy ªaman¡ kontroln¡ reprezentuj¡c¡ t¡ sam¡ krzyw¡ ale maj¡c¡

o jeden punkt kontrolny wi¦cej.

43

p(t) =

n

X

i=0

p

i

B

n

i

(t) = (t+(1−t))

n

X

i=0

p

i

B

n

i

(t) = t

n

X

i=0

p

i

B

n

i

(t)+(1−t)

n

X

i=0

p

i

B

n

i

(t) =

= p

0

(tB

n

0

(t)+(1−t)B

n

0

(t))+

n

X

i=1

(p

i

n + 1 − i

n + 1

B

n+1

i

(t)+p

i−1

i

n + 1

B

n+1

i

(t))+p

n

B

n+1

n+1

(t) =

p

0

B

n+1

0

(t) +

n

X

i=1

(p

i

n + 1 − i

n + 1

B

n+1

i

(t) + p

i−1

i

n + 1

B

n+1

i

(t)) + p

n

B

n+1

n+1

(t) =

n+1

X

i=0

ˆ

p

i

B

n+1

i

(t)

W ten sposób przedstawili±my nasz¡ krzyw¡ postaci krzywej stopnie n+1.

9.8.2 Algorytm

Algorithm 13 Algorytm podwy»szania stopnia
Wej±cie: p

0

, p

1

, ... p

n

- punkty kontrolne

Wyj±cie:

ˆ

p

0

, ˆ

p

1

, ... ˆ

p

n

, ˆ

p

n+1

-

punkty

kontrolne

krzywej

stopnia

n+1

for i:=0 to n+1 do do

ˆ

p

i

=

n+1−i

n+1

p

i

+

i

n+1

p

i−1

end for

9.8.3 Przykªad

q0 (0) = 2 (P

1

+ P

0

) = 3

 ˜

P

1

+ ˜

P

0



3 ˜

P

1

= 2P

1

− 2P

0

+ 3P

0

˜

P

1

=

P

0

+2P

1

3

q0 (1) = 2 (P

2

+ P

1

) = 3

 ˜

P

2

+ ˜

P

1



3 ˜

P

1

= 3P

2

− 2P

2

+ 2P

1

˜

P

1

=

P

0

+2P

1

3

˜

P

i

=

iP

i−1

+(k−i+1)P

i

k+1

˜

P

n+1

= P

10 OpenGL

10.1 Obiekt tablicy wierzchoªków

Dane obejmuj¡ce m.in. wspóªrz¦dne wierzchoªków prymitywów (punkty, listy

linii, serie linii, listy trójk¡tów i serie trójk¡tów) i dane kolorów wierzchoªków

przechowywane s¡ w jednej lub kilku tablicach i renderowane bezpo±rednio z

pomini¦ciem mechanizmu glBegin/glEnd. Mechanizm tablic wierzchoªków jest

bardziej elastyczny, poniewa» dane przechowywane w tablicach (tablicy) mo»na

44

w dowolny sposób modykowa¢. Stanowi to istotn¡ ró»nic¦ w stosunku do list

wy±wietlania, których gªównym ograniczeniem jest statyczno±¢.

10.2 Immendiate mode

program przekazuje ci¡g polecen do ´ GPU'. Styl programowania aplikacji bib-

liotek gracznych, gdzie zachodzi bezpo±redni rendering graczny obiektu na

ekranie. Nie wyklucza podwójnego buforowania.

10.3 Obiekt bufora

Przechowuje tablic¦ niesformatowan¡ pami¦ci przydzielonej w kontek±cie OpenGL

(aka: GPU). Mog¡ by¢ u»ywane do przechowywania danych wierzchoªków, pik-

seli pobranych z obrazów lub bufor ramki, i wiele innych rzeczy.

10.4 Shadery

krótki program komputerowy, który w grace trójwymiarowej opisuje wªa±ci-

wo±ci pikseli oraz wierzchoªków.

10.4.1 Vertex Shader
Cieniowanie wierzchoªkowe. Jego zadaniem jest transformacja poªo»enia wierz-

choªka w wirtualnej przestrzeni 3D na wspóªrz¦dne 2D na ekranie. Cieniowanie

wierzchoªkowe mo»e operowa¢ na poªo»eniu, kolorze i wspóªrz¦dnych tekstur, ale

nie mo»e tworzy¢ nowych wierzchoªków. Wyj±cie cieniowania wierzchoªkowego

jest wej±ciem dla nast¦pnego etapu w potoku, jakim jest albo cieniowanie ge-

ometryczne (je±li jest obecne) albo rasteryzator(dziaªanie polegaj¡ce na jak na-

jwierniejszym przedstawieniu pªaskiej gury geometrycznej na urz¡dzeniu ras-

trowym, dysponuj¡cym sko«czon¡ rozdzielczo±ci¡).

10.4.2 Geometry Shader
Cieniowanie geometryczne  pozwala na dodawanie lub usuwanie wierzchoªków z

siatki wierzchoªków. Mo»e by¢ u»ywane do proceduralnego tworzenia obiektów

geometrycznych albo do dodawania obj¦to±ciowych detali istniej¡cych siatek

wierzchoªków. Je±li cieniowanie geometryczne jest u»ywane, to wtedy wyj±cie z

niego jest przekazywane do rasteryzatora.

10.4.3 Fragment Shader
Cieniowanie pikseli  jest jednostk¡ odpowiadaj¡c¡ za wyliczanie koloru pikseli.

OpenGL  "fragment shader". Piksele na wej±cie ich cieniowania s¡ pobier-

ane z rasteryzatora, który wypeªnia wielok¡ty przesyªane z potoku gracznego.

Cieniowanie pikseli jest najcz¦±ciej u»ywane do o±wietlenia sceny i innych pow-

i¡zanych efektów, np. Bump-mappingu lub kolorowania.

10.5 Kontekst

Context  obiekt posredniczy pomi edzy programem , a urz¡dzeniem OpenGL.

45

10.6 Funkcje deprecated

Kazda wersja OpenGL (powyzej 3.0) ma cz¦±¢ funkcji ´ deprecated, które mog¡

zostac usuni¦te w nast¦pnych ´ wersjach

ˆ Core Prole ag

ˆ Compatibility Prole ag

ˆ Forward Compatible ag

ˆ Debug ag

10.7 Biblioteki wspomogaj¡ce

10.7.1 FreeGLUT
Pozwala u»ytkownikowi tworzy¢ i zarz¡dza¢ oknami u»ywaj¡cymi OpenGL na

wielu platformach. Pozwala równie» obsªugiwa¢ mysz, klawiatur¦ i d»ojstik

10.7.2 GLEW
Programistyczna biblioteka mi¦dzyplatformowa do j¦zyka C/C++, pomagaj¡ca

w odpytywaniu i ªadowaniu rozszerze« OpenGL. GLEW dostarcza efektywne

mechanizmy do okre±lania w czasie uruchamiania programu dost¦pnych rozsz-

erze« na danej platformie. Wszystkie rozszerzenia OpenGL s¡ wylistowane w

jednym pliku nagªówkowym, który z kolei jest maszynowo generowany na pod-

stawie ocjalnej listy rozszerze«.

10.8 Etapy tworzenia programu w OpenGL

1. Utworzenie kontekstu, skªadaj¡cego sie z naglówków, main, initialize, in-

icjalizacji OpenGL, Inicjalizacji Okna, Obsªugi zdarze«, Zmiany rozmiaru

okna, funkcji renderowania,

2. Doª¡czanie biblioteki GLEW

10.9 Obiekt VAO

Jest to obiekt, ª¡cz¡cy w sobie kilka atrybutów takich jak poªo»enie wierz-

choªków na ekranie, wspóªrz¦dne tekstury oraz wektory normalne.

46

10.10 Tryby renderowania

Figure 14: Tryby renderowania

Figure 15: Potok renderingu

47

Spis tre±ci

1 Percepcja wizualna i modele barw

1

1.1 Modele barw popularne . . . . . . . . . . . . . . . . . . . . . . .

1

1.1.1 RGB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.1.2 CLUT . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.1.3 Web-safe colors . . . . . . . . . . . . . . . . . . . . . . . .

1

1.1.4 CMYK . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2 Telewizyjne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2.1 YUV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2.2 YUQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2.3 YCbCr . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.3 Modele sto»kowe . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.3.1 HSV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.3.2 HSL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.4 Modele percepcyjnie równomierne . . . . . . . . . . . . . . . . .

3

1.4.1 CIE - LUV . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.4.2 CIE - LAB . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.5 Przeksztaªcanie modeli . . . . . . . . . . . . . . . . . . . . . . .

4

1.5.1 RGB ↔ HSL . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.5.2 RGB ↔ CMY . . . . . . . . . . . . . . . . . . . . . . . .

5

1.5.3 RGB ↔ YUV . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.5.4 YUQ↔ YUV . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.5.5 YCbCr ↔ RGB . . . . . . . . . . . . . . . . . . . . . . .

6

2 Formaty kompresji plików gracznych i kompresja obrazów

6

2.1 SVG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.1.1 Filty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.2 PostScript . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.2.1 EPS - Encapsulated PostScript . . . . . . . . . . . . . . .

7

2.3 TIFF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.4 PNG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.4.1 Korekcja gamma . . . . . . . . . . . . . . . . . . . . . . .

7

2.4.2 Adam7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.4.3 Sprawdzanie poprawno±ci . . . . . . . . . . . . . . . . . .

7

2.4.4 Filtracja . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.5 JPEG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

3 Rasteryzacja

8

3.1 Rasteryzacja odcinka . . . . . . . . . . . . . . . . . . . . . . . . .

8

3.1.1 Przykªad . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.2 Rasteryzacja okr¦gu . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.3 Rasteryzacja elipsy . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3.4 Wypeªnianie wieloboku . . . . . . . . . . . . . . . . . . . . . . . . 14

3.4.1 Przegl¡danie liniami poziomymi . . . . . . . . . . . . . . . 14

3.4.2 Przez zalewanie . . . . . . . . . . . . . . . . . . . . . . . . 15

48

4 Algorytm obcinania i okienkowania

17

4.1 Odcinanie prostych i odcinków . . . . . . . . . . . . . . . . . . . 17

4.1.1 Algorytm Sutherlanda-Cohena . . . . . . . . . . . . . . . 17

4.1.2 Algorytm Lianga-Barsky'ego . . . . . . . . . . . . . . . . 19

4.2 Algorytm Sutherlanda-Hodgmana . . . . . . . . . . . . . . . . . . 20

4.2.1 Zaªo»enia . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.2.2 Algorytm . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.2.3 Problem Cz¦±ci wspólnej wielok¡ta i póªpªaszczyzny . . . 21

4.3 Algorytm Weilera-Athertona . . . . . . . . . . . . . . . . . . . . 22

4.3.1 Zaªo»enia . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.3.2 Algorytm . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.3.3 Przykªad . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

5 Geometria maszynowa

24

5.1 Macierz przeksztaªcenia anicznego . . . . . . . . . . . . . . . . . 24

5.1.1 Obrót . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5.1.2 Skalowanie . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5.1.3 Przesuni¦cie równolegªe . . . . . . . . . . . . . . . . . . . 25

6 Rzutowanie

25

6.1 Algorytm malarza . . . . . . . . . . . . . . . . . . . . . . . . . . 25

6.2 Algorytm bufora gª¦boko±ci . . . . . . . . . . . . . . . . . . . . . 26

6.3 Rodzaje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

6.3.1 Rzutowanie równolegªe . . . . . . . . . . . . . . . . . . . . 26

6.3.2 Rzutowanie perspektywiczne . . . . . . . . . . . . . . . . 27

6.4 Zastosowanie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

6.4.1 Cie« . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

6.4.2 Z-ghtning . . . . . . . . . . . . . . . . . . . . . . . . . . 28

7 O±wietlenie

28

7.1 Model odbicia ±wiatªa Phonga . . . . . . . . . . . . . . . . . . . . 28

7.1.1 Odbicie rozproszone . . . . . . . . . . . . . . . . . . . . . 28

7.1.2 Odbicie zwierciadlane . . . . . . . . . . . . . . . . . . . . 29

7.1.3 ‘wiatªo otoczenia . . . . . . . . . . . . . . . . . . . . . . . 29

7.1.4 ‘wiatªo emitowane powierzchni¡ . . . . . . . . . . . . . . 30

7.2 Cieniowanie

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

7.2.1 Cieniowanie Gourauda . . . . . . . . . . . . . . . . . . . . 30

7.2.2 Cieniowanie Phonga . . . . . . . . . . . . . . . . . . . . . 32

7.3 ™ródªa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

7.3.1 ‘wiatªo punktowe . . . . . . . . . . . . . . . . . . . . . . 33

7.3.2 ‘wiatªo kierunkowe . . . . . . . . . . . . . . . . . . . . . . 34

7.3.3 ‘wiatªo spot . . . . . . . . . . . . . . . . . . . . . . . . . 34

8 Teksturowanie

34

8.1 Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

8.2 Czym jest tekstura ? . . . . . . . . . . . . . . . . . . . . . . . . . 34

8.3 Mapowanie tekstury . . . . . . . . . . . . . . . . . . . . . . . . . 35

8.3.1 Mapowanie cylindryczne . . . . . . . . . . . . . . . . . . . 35

8.3.2 Mapowanie sferyczne . . . . . . . . . . . . . . . . . . . . . 35

8.3.3 Mapowanie torusa . . . . . . . . . . . . . . . . . . . . . . 35

49

8.4 Aliasing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

8.4.1 Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

8.4.2 Mipmapping . . . . . . . . . . . . . . . . . . . . . . . . . 36

8.4.3 Supersampling . . . . . . . . . . . . . . . . . . . . . . . . 36

8.5 Mapowanie wypukªo±ci . . . . . . . . . . . . . . . . . . . . . . . . 36

8.6 Mapowanie ±rodowiska . . . . . . . . . . . . . . . . . . . . . . . . 36

9 Krzywe Béziera

37

9.1 Parametryzacja . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

9.2 Wielomiany Bernsteina i denicja krzywej Béziera . . . . . . . . 37

9.3 Wªasno±ci wielomianów Bernsteina i ich konsekwencje dla krzy-

wych Béziera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

9.4 Algorytm de Casteljau . . . . . . . . . . . . . . . . . . . . . . . . 39

9.4.1 Zaªo»enia . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

9.4.2 Algorytm . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

9.4.3 Przykªad dla czterech punktów kontrolnych p

0

, p

1

, p

2

, p

3

i t =

1
2

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

9.4.4 Wykorzystanie algorytmu do podziaªu krzywej Béziera na

dwie krzywe Béziera . . . . . . . . . . . . . . . . . . . . . 40

9.5 Krzywa Béziera jako ci¡g odcinków prostych . . . . . . . . . . . . 41

9.6 Wªa±ciwo±¢ i konsekwencje otoczki wypukªej . . . . . . . . . . . 42

9.7 Sklejanie krzywych . . . . . . . . . . . . . . . . . . . . . . . . . . 42

9.7.1 Splajny Catmulla-Roma . . . . . . . . . . . . . . . . . . . 43

9.8 Podwy»szanie stopnia . . . . . . . . . . . . . . . . . . . . . . . . 43

9.8.1 Zaªo»enia . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

9.8.2 Algorytm . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

9.8.3 Przykªad . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

10 OpenGL

44

10.1 Obiekt tablicy wierzchoªków . . . . . . . . . . . . . . . . . . . . . 44

10.2 Immendiate mode . . . . . . . . . . . . . . . . . . . . . . . . . . 45

10.3 Obiekt bufora . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

10.4 Shadery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

10.4.1 Vertex Shader . . . . . . . . . . . . . . . . . . . . . . . . . 45

10.4.2 Geometry Shader . . . . . . . . . . . . . . . . . . . . . . . 45

10.4.3 Fragment Shader . . . . . . . . . . . . . . . . . . . . . . . 45

10.5 Kontekst . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

10.6 Funkcje deprecated . . . . . . . . . . . . . . . . . . . . . . . . . . 46

10.7 Biblioteki wspomogaj¡ce . . . . . . . . . . . . . . . . . . . . . . . 46

10.7.1 FreeGLUT . . . . . . . . . . . . . . . . . . . . . . . . . . 46

10.7.2 GLEW . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

10.8 Etapy tworzenia programu w OpenGL . . . . . . . . . . . . . . . 46

10.9 Obiekt VAO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

10.10Tryby renderowania . . . . . . . . . . . . . . . . . . . . . . . . . 47

Lista algorytmów

1

Algorytm RGB →HSV . . . . . . . . . . . . . . . . . . . . . . . .

4

2

Algorytm HSV → RGB . . . . . . . . . . . . . . . . . . . . . . .

5

50

3

Algorytm Bresenhama . . . . . . . . . . . . . . . . . . . . . . . .

9

4

Algorytm rasteryzacji okr¦gu . . . . . . . . . . . . . . . . . . . . 11

5

Algorytm rasteryzacji elipsy . . . . . . . . . . . . . . . . . . . . . 13

6

Wypeªnianie wieloboku - przegl¡danie liniami poziomymi . . . . 15

7

Wypeªnianie przez zalewanie - rekurencja . . . . . . . . . . . . . 15

8

Wypeªnianie przez zalewanie - stos . . . . . . . . . . . . . . . . . 16

9

Algorytm Sutherlanda-Cohena . . . . . . . . . . . . . . . . . . . 18

10

Algorytm Lianga-Barsky'ego . . . . . . . . . . . . . . . . . . . . 20

11

Cieniowanie Gourauda . . . . . . . . . . . . . . . . . . . . . . . . 31

12

Algorytm de Casteljau . . . . . . . . . . . . . . . . . . . . . . . . 40

13

Algorytm podwy»szania stopnia . . . . . . . . . . . . . . . . . . . 44

Spis rysunków

1

Algorytm Sutherlanda-Cohena - podziaª okna na obszary . . . . 17

2

Algorytm Sutherlanda - Cohena - przykªad . . . . . . . . . . . . 19

3

Przykªad obcinania literki W (W jak Wikipedia) przez pi¦ciok¡t. 21

4

Przykªad problemu z jakimi algorytm sobie nie poradzi . . . . . . 26

5

Inicjalizacja i nadpisywanie bufora nowymi warto±ciami . . . . . 26

6

Rozproszenie ±wiatªa . . . . . . . . . . . . . . . . . . . . . . . . . 28

7

Odbicie zwierciadlane . . . . . . . . . . . . . . . . . . . . . . . . 29

8

Krzywe Beziera . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

9

Algorytm de Casteljau dla czterech punktów kontrolnych . . . . 40

10

Podziaª krzywej . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

11

Rasteryzacja krzywej Béziera . . . . . . . . . . . . . . . . . . . . 41

12

Otoczka wypukªa . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

13

Sklejanie krzywych Beziera . . . . . . . . . . . . . . . . . . . . . 43

14

Tryby renderowania . . . . . . . . . . . . . . . . . . . . . . . . . 47

15

Potok renderingu . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

51