LebiedÅº Jacek Grafika Komputerowa

-DFHN /HELHG(
32/,7(&+1,.$ *'$6.$

:\G]LDá (OHNWURQLNL 7HOHNRPXQLNDFML L ,QIRUPDW\NL

Katedra Technik Programowania

p. 420 WETI tel. (347-)20-96

GRAFIKA KOMPUTEROWA

ITERATURA

1. R. A. Earnshaw (ed.): Fundamental Algorithms for Computer

Graphics. Springer, Berlin 1985.

2. J. D. Foley, A. van Dam, S. K. Feiner, J. F. Hughes, R. L. Phillips:

Wprowadzenie do grafiki komputerowej. WNT, Warszawa 1995.

3. J. D. Foley, A. van Dam, S. K. Feiner, J. F. Hughes: Computer Graphics:

Principles and Practice, Second Edition. Addison-Wesley, Reading 1990.

4. G. Hégron: Synthèse d’image: algorithmes élémentaires. Dunod

informatique, Paris 1985.

5. M. Jankowski: Elementy grafiki komputerowej. WNT, Warszawa 1990.
6. T. Pavlidis: Grafika i przetwarzanie obrazów. WNT, Warszawa 1987.
7. J. Zabrodzki (red.): Grafika komputerowa, metody i narz

dzia. WNT,

Warszawa 1994.

Gda

sk 2000

GRAFIKA, PRZETWARZANIE I ROZPOZNAWANIE OBRAZÓW

Obraz

Opis

Przetwarzanie obrazów

Rozpoznawanie obrazów

Grafika

Rys.

6FKHPDW LOXVWUXMF\

Z]DMHPQH ]DOH*QRFL

PL G]\ JUDILN
przetwarzaniem
obrazów i
rozpoznawaniem
obrazów.

GRAFIKA KOMPUTEROWA

•

.RPXQLNDFMD ] F]áRZLHNLHP

•

Obrazowanie schematów

•

3UH]HQWRZDQLH ]HVWDZLH

•

0RGHORZDQLH NV]WDáWyZ

•

.UHOHQLH U\VXQNyZ WHFKQLF]Q\FK

•

6NáDGDQLH SXEOLNDFML

•

SRU]G]DQLH PDS NDUWRJUDILD

•

Synteza obrazów realistycznych

•

Wizualizacja modelowanych zjawisk

•

Animacja

•

Plastyka

PRZETWARZANIE OBRAZÓW

•

Dyskretyzacja obrazów

•

Polepszanie jako

FL REUD]yZ

•

Urealnianie obrazów

•

Rekonstrukcja obrazów

•

Kompresja obrazów

•

:\RGU EQLDQLH RELHNWyZ

•

8SUDV]F]DQLH NV]WDáWyZ

ROZPOZNAWANIE OBRAZÓW

•

Opis obiektów

•

Klasyfikacja obiektów

•

Porównywanie obrazów

•

Analiza struktury

ARWA

(

KOLOR

)

ZLDWáR SURPLHQLRZDQLH HOHNWURPDJQHW\F]QH R GáXJRFL IDOL λ∈(380,780) nm.

•

Dwa rodzaje receptorów w ludzkim oku:

•

SU FLNL UHDJXM MX* SU]\ QLVNLP SR]LRPLH RZLHWOHQLD EUDN ZUD*H
barwnych - widzenie skotopowe (nocne);

•

czopki

UHDJXM GRSLHUR SU]\ Z\*V]\P SR]LRPLH RZLHWOHQLD ZUD*HQLH

barwy - widzenie fotopowe (dzienne).

•

Teoria Younga - Helmholtza

Z\MDQLDMFD PHFKDQL]P SRZVWDZDQLD

ZUD*HQLD EDUZ\ =DNáDGD RQD Z\VW SRZDQLH Z F]RSNDFK WU]HFK VXEVWDQFML

ZLDWáRF]Xá\FK F]Xá\FK RGSRZLHGQLR QD EDUZ\

•

QLHELHVN F]XáRü β(λ),

•

]LHORQ F]XáRü γ(λ),

•

SRPDUDF]RZRF]HUZRQ F]XáRü ρ(λ).

3RVWU]HJDQD EDUZD Z\QLND ]H VWRVXQNX SREXG]H W\FK SRV]F]HJyOQ\FK

VXEVWDQFML 6XPD SREXG]H GHWHUPLQXMH RGELHUDQ MDVQRü

•

Zjawisko metameryzmu

SURPLHQLRZDQLH R Uy*Q\P VNáDG]LH ZLGPRZ\P

PR*H GDZDü LGHQW\F]QH ZUD*HQLH EDUZ\ LGHQW\F]Q\ VWRVXQHN SREXG]H

WU]HFK VXEVWDQFML ZLDWáRF]Xá\FK Z F]RSNDFK

•

Modele syntezy barw:

•

model RGB ang. red + green + blue - czerwony + zielony + niebieski,
synteza addytywna, stosowany w monitorach kolorowych;

•

modele CMY i CMYK ang. cyan + magenta + yellow (+ black) -

]LHORQRQLHELHVNL NDUPD]\QRZ\ *yáW\ F]DUQ\
synteza subtraktywna, stosowane w poligrafii;

•

modele YUV, YIQ i YC

- luminancja + dwie chrominancje,

VWRVRZDQH Z WHOHZL]ML NRORURZHM ]JRGQH ] WHOHZL]M F]DUQRELDá

•

modele HSV i HLS ang. hue + saturation + value (lightness) -

RGFLH QDV\FHQLH ZDUWRü MDVQRü RGFLH DQJ hue Z\UD*DQ\ NWHP

hue:

red

yellow

green

cyan

blue

magenta

0°

60°

120°

180°

240°

300°

VWRVRZDQH Z GLDORJX ] F]áRZLHNLHP ]JRGQH ] OXG]N LQWXLFM

•

model CIE XYZ (franc. Commission Internationale de l'Eclairage),

PRGHO WHRUHW\F]Q\ DEVWUDNF\MQ\ XNáDG EDUZ RGQLHVLHQLD ; < =

•

modele CIE LUV i CIE LAB - inne modele teoretyczne CIE;

•

model TekHVC - model teoretyczny opracowany w firmie Tektronix,

RGOHJáRFL JHRPHWU\F]QH SURSRUFMRQDOQH GR Uy*QLF ZUD*H EDUZQ\FK

POSOBY PREZENTACJI OBRAZÓW W GRAFICE KOMPUTEROWEJ

•

GRAFIKA RASTROWA

3áDV]F]\]QD REUD]X MHVW SRG]LHORQD QD SURVWRNWQH HOHPHQW\ W]Z SLNVHOH
Tworzenie obrazu polega na wyznaczeniu kolorów poszczególnych pikseli
i naniesieniu tych kolorów w odpowiednich miejscach poleceniem write(c).

SU]\NáDG\ XU]G]H GUXNDUND LJáRZD VNDQHU

Sposoby reprezentacji obrazów:

•

tablice (mapy bitowe)

type Image = array [0..mx,0..my] of Color

•

drzewa czwórkowe

•

drzewa binarne

Kompresja:

•

metody bez utraty informacji:

•

PHWRG\ NRGyZ ]PLHQQHM GáXJRFL +XIIPDQ

•

metody arytmetyczne

•

PHWRG\ VáRZQLNRZH /HPSHO=LY:HOFK /=:

•

bezstratne metody kompresji danych graficznych,

QS NRGRZDQLH GáXJRFL VHNZHQFML DQJ run length encoding RLE)

•

PHWRG\ ] XWUDW LQIRUPDFML

•

PHWRG\ EH]SRUHGQLH Z G]LHG]LQLH REUD]X PLQ PHWRG\ IDONRZH

•

metody transformat, np. JPEG (ang. Joint Photographic Experts Group)

•

metody fraktalne

Formy danych obrazowych:

•

obrazy kolorowe

type Color = record red, green, blue: integer end

•

obrazy szare (wielopoziomowe)

type Color = integer

•

REUD]\ F]DUQRELDáH GZXSR]LRPRZH

type Color = Boolean

•

GRAFIKA WEKTOROWA

2EUD] VNáDGD VL ] WDNLFK RELHNWyZ MDN RGFLQHN OXE SXQNW
Tworzenie obrazu polega na narysowaniu poszczególnych obiektów

VNáDGRZ\FK SROHFHQLDPL plot(x,y,c), vector(x

,c).

SU]\NáDG\ XU]G]H SORWHU WDEOHW

Sposoby reprezentacji obrazów:

•

zbiór linii

type Image = list of Line

Formy danych obrazowych:

•

REUD]\ VNáDGDMFH VL ] OLQLL FLJá\FK

type Line = record x,y:integer; c:Color; chain: list of 0..7 end

•

REUD]\ VNáDGDMFH VL ] RGFLQNyZ

type Line = list of record x,y:integer; c:Color end

Metody kompresji danych graficznych

•

.RGRZDQLH GáXJRFL VHNZHQFML (ang. run length encoding RLE)
: REUD]LH ]OLQHDU\]RZDQ\P Z\VW SXM F] VWR FLJL SLNVHOL R WDNLP VDP\P

NRORU]H &LJL WDNLH PR*QD NRGRZDü MDNR SDU\ OLF]ED SLNVHOL L LFK NRORU

•

Metody transformat

♦

3RG]LDá REUD]X QD EORNL Um×m o rozmiarze m×m (dla JPEG: m=8).

♦

Wykonanie zadanej transformacji T na poszczególnych blokach Um×m:
Vm×m=TUm×m (dla JPEG: DCT).

♦

Dokonanie kwantyzacji K wyników transformacji Vm×m:
Wm×m=KVm×m (dla JPEG: wi,j = [vi,j / qi,j ], gdzie wi,j, vi,j, qi,j V
elementami macierzy Wm×m, Vm×m i Qm×m, przy czym Qm×m jest

]DGDQ PDFLHU] NZDQW\]DFML

♦

Linearyzacja skwantowanych wyników transformacji Wm×m (dla JPEG:
metoda ZIGZAG).

♦

.RPSUHVMD HIHNWyZ OLQHDU\]DFML MDN PHWRG EH] XWUDW\ LQIRUPDFML GOD
JPEG: metoda Huffmana).

Rys. Kompr

HVMD PHWRG WUDQVIRUPDW

♦

Dekompresja skwantowanych wyników transformacji Wm×m X*\W GR

NRPSUHVML PHWRG EH] XWUDW\ LQIRUPDFML GOD -3(* PHWRGD +XIIPDQD

♦

2GWZRU]HQLH SU]\EOL*RQ\FK Z\QLków transformacji Vm×m na podstawie
skwantowanych wyników transformacji Wm×m (dla JPEG:
vi,j = wi,j · qi,j, gdzie vi,j, wi,j, qi,j V HOHPHQWDPL PDFLHU]\ Vm×m,
Wm×m i Qm×m, przy czym Qm×m MHVW ]DVWRVRZDQ SRGF]DV NRPSUHVML

PDFLHU] NZDQW\]DFML

♦

Wykonanie zadanej transformacji odwrotnej T-1 na poszczególnych

SU]\EOL*RQ\FK Z\QLNDFK WUDQVIRUPDFML Vm×m: Um×m=T-1Vm×m (dla
JPEG: odwrotna DCT).

5\V 'HNRPSUHVMD PHWRG WUDQVIRUPDW

109 103

104 113

103 121 120 101

112 100 103

Rys. Macierze kwantyzacji Q

8×8

dla luminancji i dla chrominancji.

Rys. Linearyzacja metod

=,*=$* GOD m=8).

•

Metody falkowe

:\NRU]\VW\ZDQH WX V GZD ILOWU\ MHGQRZ\PLDURZH ILOWU GROQRprzepustowy L
i lustrzany do niego filtr górnoprzepustowy H.

7ZRU]RQ\ MHVW FLJ REUD]yZ Î

, Î

–

, Î

–

, Î

, ..., Î

, Î

–

, Î

, I

Kompresja polega tu na skwantowaniu kolorów pikseli obrazów

XWZRU]RQHJR FLJX L ]DNRGRZDQLX LFK PHWRG EH] XWUDW\ LQIRUPDFML

•

Metody fraktalne

Fraktalem

QD]\ZDP\ SRG]ELyU SáDV]F]\]Q\ OXE LQQHM SU]HVWU]HQL

PHWU\F]QHM NWyUHJR IUDJPHQW\ V SRGREQH Z MDNLP VHQVLH GR FDáRFL

0DWHPDW\F]QLH SRGRELHVWZR WR RSLVXMH VL Z IRUPLH SU]HNV]WDáFHQLD

RGZ]RURZXMFHJR FDá\ IUDNWDO QD MHJR F] ü =HVSyá WDNLFK SU]HNV]WDáFH

RGSRZLDGDMF\FK SRGRELHVWZX SRV]F]HJyOQ\FK F] FL GR FDáRFL RNUHOD

VL PLDQHP LWHUDF\MQHJR XNáDGX IXQNFML DQJ iterated function system).

= ND*G\P IUDNWDOHP PR*QD ]DWHP VNRMDU]\ü LWHUDF\MQ\ XNáDG IXQNFML

•

PHWRG\ NROD*X ,)6 DQJ iterated function system)

NRGRZDQLH SRGRELHVWZ JHRPHWU\F]Q\FK NV]WDáWyZ

•

PHWRG\ SDF]áRUNX 3,)6 DQJ partitioned iterated function system)

NRGRZDQLH SRGRELHVWZ Z G]LHG]LQLH NRORUyZ

x' = 0.85· x + 0.04· y + 0
y' = – 0.04· x + 0.85· y + 1.6

x' = 0.2· x – 0.26· y + 0
y' = 0.23· x + 0.22· y + 1.6

x' = – 0.15· x + 0.28· y + 0
y' = 0.26· x + 0.24· y + 0.44

x' = 0· x + 0· y + 0
y' = 0· x + 0.16· y + 0

5\V )UDNWDOQ\ OLü SDSURFL D L MHJR LWHUDF\MQ\ XNáDG IXQNFML E

i+1

–

2:1

wiersze

kolumny

Dyskretyzacja obrazów rzeczywistych

•

Próbkowanie - wybór dyskretnej siatki (rastra) do przedstawienia obrazu.

•

=DOH*QRü HIHNWyZ SUyENRZDQLD RG SRáR*HQLD VLDWNL SUyENRZDQLD

•

=PLDQD NV]WDáWX REV]DUX SR SUyENRZDQLX

:DUXQHN ]JRGQRFL ]H VWDá α GOD REV]DUX SRG]ELRUX SáDV]F]\]Q\ Ω

i kwadratowej siatki próbkowania (rastra) o boku h:

(

)

(

)

(

)

(

)

∃ >

∀ ∈

∃

⊂

∈

∃

⊂ ′

∈













Ω

gdzie

Ω

- brzeg obszaru

Ω,

Ω Ω Ω

= ∩ ′

Ω

GRPNQL FLH REV]DUX Ω,

Ω Ω

Ω

= ∪ Fr

′

Ω

GRSHáQLHQLH REV]DUX Ω,

{

}

′ =

∉

Ω

(

)

Q r

NRáR R URGNX Z SXQNFLH Q i o promieniu r.

Stwierdzenie 1:

-HOL REV]DU Ω i kwadratowa siatka próbkowania (raster) o boku h

VSHáQLDM ZDUXQHN ]JRGQRFL ]H VWDá

α = 2

, wówczas próbkowanie

]DFKRZD WRSRORJL NV]WDáW REV]DUX

Stwierdzenie 2:

-HOL REV]DU Ω i kwadratowa siatka próbkowania (raster) o boku h

VSHáQLDM ZDUXQHN ]JRGQRFL ]H VWDá

α = 10

, wówczas próbkowanie

]DFKRZD WRSRORJL NV]WDáW ZQ WU]D REV]DUX D NRQWXU E G]LH VL VNáDGDü
] NU]\Z\FK ]DPNQL W\FK

•

Kwantowanie - odwzorowanie kolorów w zbiór dyskretny.

Z\PDJDQD MDNRü

dobra

UHGQLD

OLF]ED SR]LRPyZ MDVQRFL

256

obrazy szare

8 b/piksel

6 b/piksel

obrazy kolorowe

24 b/piksel

18 b/piksel

: Z\QLNX NZDQWRZDQLD REUD]X PRJ SRMDZLü VL QLHSR*GDQH NUDZ G]LH

:SURZDG]HQLH QLHZLHONLHJR ORVRZHJR ]DEXU]HQLD ZDUWRFL SR]LRPyZ

MDVQRFL W]Z GU*HQLH, ang. dither XVXZD UR]P\ZD WH NUDZ G]LH

EOMETRIA

YSKRETNA

QVVLDG

piksela

EVVLDG

piksela

QVVLDG

piksela

EVVLDG

piksela

piksel P

EVVLDG

piksela

5\V 6VLHG]L SLNVHOD P.

QVVLDG

piksela

EVVLDG

piksela

QVVLDG

piksela

'HILQLFMH VVLHG]WZD

•

%H]SRUHGQLPL VVLDGDPL EVVLDGDPL QD]\ZDP\ GZD SLNVHOH PDMFH
wspólny bok.

•

1LHEH]SRUHGQLPL VVLDGDPL QVVLDGDPL V GZD SLNVHOH VW\NDMFH VL

]H VRE W\ONR QDUR*QLNDPL

•

6VLDGDPL ]ZLHP\ ]DUyZQR EVVLDGyZ MDN L QVVLDGyZ

Definicje linii:

•

%GURJ MHVW FLJ SLNVHOL P1, P2, ..., Pn WDNL *H ∀k∈{1, 2, .., n-1} piksele
Pk i Pk+1 V EVVLDGDPL

•

'URJ QGURJ MHVW FLJ SLNVHOL P1, P2, ..., Pn WDNL *H ∀k∈{1, 2, .., n-1}
piksele Pk i Pk+1 V VVLDGDPL

•

'URJ SURVW MHVW GURJD Z NWyUHM ZV]\VWNLH SLNVHOH FLJX VWDQRZLFHJR GURJ

V Uy*QH L *DGHQ ] QLFK QLH PD ZL FHM QL* GZyFK EVVLDGyZ Z W\P FLJX

•

'URJ ]DPNQL W MHVW GURJD Z NWyUHM SLHUZV]\ SLNVHO FLJX VWDQRZLFHJR

GURJ MHVW VVLDGHP RVWDWQLHJR SLNVHOD WHJR FLJX

•

.U]\Z G\VNUHWQ QD]\ZDP\ ND*G\ VSyMQ\ ]ELyU SLNVHOL

QLH ]DZLHUDMF\ F]ZyUHN SLNVHOL WZRU]F\FK NZDGUDW R ERNX

Definicje konturu:

•

B-konturem danego zbioru pikseli nazywamy zbiór wszystkich pikseli

QDOH*F\FK GR WHJR ]ELRUX L PDMF\FK SU]\QDMPQLHM MHGQHJR VVLDGD QLH

QDOH*FHJR GR WHJR ]ELRUX

•

Konturem (n-konturem) danego zbioru pikseli nazywamy zbiór

ZV]\VWNLFK SLNVHOL QDOH*F\FK GR WHJR ]ELRUX L PDMF\FK SU]\QDMPQLHM

MHGQHJR EVVLDGD QLH QDOH*FHJR GR WHJR ]ELRUX

'HILQLFMH VSyMQRFL

•

Zbiór pikseli jest spójny (n-spójny)

MHOL GOD ND*GHM SDU\ SLNVHOL WHJR ]ELRUX

LVWQLHMH GURJD áF]FD WH SLNVHOH L ]DZLHUDMFD VL Z W\P ]ELRU]H

•

Zbiór pikseli jest b-spójny

MHOL GOD ND*GHM SDU\ SLNVHOL WHJR ]ELRUX LVWQLHMH

EGURJD áF]FD WH SLNVHOH L ]DZLHUDMFD VL Z W\P ]ELRU]H

Krzywe dyskretne

•

.U]\Z G\VNUHWQ QD]\ZDP\ ND*G\ VSyMQ\ ]ELyU SLNVHOL

QLH ]DZLHUDMF\ F]ZyUHN SLNVHOL WZRU]F\FK NZDGUDW R ERNX

•

,QQH VSRW\NDQH Z OLWHUDWXU]H RNUHOHQLD NU]\ZHM G\VNUHtnej:

•

]ELyU E GF\ MHGQRF]HQLH VZRLP NRQWXUHP

•

]ELyU E GF\ GURJ SURVW

•

]ELyU Z NWyU\P LVWQLHMH W\ONR MHGQD GURJD PL G]\ GRZROQ SDU SLNVHOL

Rys.

3U]\NáDG\ UR]ELH*QRFL SU]\M WHM WX GHILQLFML NU]\ZHM ] LQQ\PL RNUHOHQLDPL

]ELyU E GF\ VZRLP NRQWXUHP D QLH E GF\ NU]\Z

]ELyU E GF\ GURJ SURVW MHGQRF]HQLH VZRLP NRQWXUHP D QLH E GF\ NU]\Z

c) krzywa, w której dla dwóch dowolnych pikse

OL OH*F\FK SR Uy*Q\FK VWURQDFK

]DáDPDQLD LVWQLHM GZLH GURJL MHGQD ] SLNVHOHP QDUR*Q\P ×, druga bez);

NU]\ZD QLH E GFD VZRLP NRQWXUHP FHQWUDOQ\ SLNVHO × DQL GURJ SURVW Z

NWyUHM GOD GRZROQ\FK GZyFK SLNVHOL LVWQLHM SU]\QDMPQLHM GZLH GURJL áF]ce je.

Metody rysowania krzywych dyskretnych:

•

numeryczne

•

podstawowe, parametryczne.

•

Z\QLNDM EH]SRUHGQLR ]H Z]RUyZ DQDOLW\F]QHJR y

f(x) lub paramet-

rycznych x

x(t), y

y(t) wykorzystywanych w geometrii euklidesowej,

•

QDMF] FLHM Z\PDJDM REOLF]H ]PLHQQRSU]HFLQNRZ\FK

•

VWRVRZDQH ]ZáDV]F]D GOD ÄZ\UDILQRZDQ\FK´ NU]\Z\FK QS %p]LHUD

•

warunkowe

•

%UHVHQKDPD SXQNWX URGkowego (ang. midpoint), porównawcze Jordana.

•

Z\QLNDM EH]SRUHGQLR ] UyZQDQLD XZLNáDQHJR F(x, y)

stosowanego do opisu krzywej w geometrii euklidesowej,

•

GOD V]HURNLHM NODV\ NU]\Z\FK Z\VWDUF]DM REOLF]HQLD FDáNRZLWROLF]ERZH

•

Z\NRU]\VW\ZDQH SRZV]HFKQLH GOD RGFLQNyZ L NU]\Z\FK VWR*NRZ\FK

•

strukturalne

•

áDFXFKRZH ]H ]PLHQQ GáXJRFL VHULL DQJ run length slice).

•

Z\QLNDM EH]SRUHGQLR ] RSLVX VWUXNWXUDOQHJR NU]\ZHM G\VNUHWQHM

•

NRU]\VWDM MHG\QLH ] REOLF]H FDáNRZLWROLF]ERZ\FK

•

]QDQH MHG\QLH GOD RGFLQNyZ L HZHQWXDOQLH RNU JyZ

Odcinek dyskretny

'HILQLFMD GáXJRFL NU]\ZHM

•

'áXJRFL NU]\ZHM QD]\ZDü E G]LHP\ SRPQLHMV]RQ R MHGHQ

OLF]E SLNVHOL ] NWyU\FK NU]\ZD WD VL VNáDGD

Definicja odcinka:

•

Odcinkiem

R SRF]WNX Z SLNVHOX P1 L NRFX Z SLNVHOX P2

QD]\ZDP\ QDMPQLHMV]HM GáXJRFL NU]\Z áF]F WH SLNVHOH

Z NWyUHM QVVLHG]WZD L EVVLHG]WZD NROHMQ\FK SLNVHOL FLJX

VWDQRZLFHJR NU]\Z Z\VW SXM MDN QDMEDUG]LHM UyZQRPLHUQLH

5\V 'ZD Uy*QH RGFLQNL

áF]FH WH VDPH GZD SXQNW\

6WZLHUG]HQLD R F] FL ZVSyOQHM GZyFK RGFLQNyZ

•

'ZD NU]\*XMFH VL RGFLQNL PRJ PLHü GRZROQ OLF]E SXQNWyZ ZVSyOQ\FK
(0, 1, 2, ...).

•

&] ü ZVSyOQD RGFLQNyZ PR*H QLH E\ü VSyMQD

•

2GFLQHN NWyUHJR NUDFH QDOH* GR GUXJLHJR RGFLQND PR*H QLH ]DZLHUDü VL
w tym drugim odcinku.

A E

E A

5\V 3U]\NáDG\ NU]\*RZDQLD VL RGFLQNyZ G\VNUHWQ\FK

D NU]\*XMFH VL RGFLQNL A i E QLH PDM F] FL ZVSyOQHM

E NU]\*XMFH VL RGFLQNL A i E PDM MHGHQ ZVSyOQ\ SLNVHO

F NU]\*XMFH VL RGFLQNL A i E PDM GZD ZVSyOQH SLNVHOH

G ZVSyOQD F] ü NU]\*XMF\FK VL RGFLQNyZ A i E nie jest spójna;
e) odcinek E

R NRFDFK OH*F\FK QD RGFLQNX A QLH ]DZLHUD VL Z QLP Z FDáRFL

Algorytmy rysowania odcinków:

•

numeryczne
.ROHMQH SLNVHOH RGFLQND Z\]QDF]DQH V SU]H] SRGVWDZLDQLH ]PLHQLDQHM ]H

VWDá\P NURNLHP SHZQHM ]PLHQQHM GR Z]RUyZ JHRPHWULL HXNOLGHVRZHM L

]DRNUJODQLH RWU]\PDQ\FK Z WHQ VSRVyE ZVSyáU] GQ\FK

•

podstawowy

•

Uy*QLFRZ\ DQJ DDA - Digital Differential Analyser)

•

warunkowe
.ROHMQH SLNVHOH RGFLQND Z\]QDF]DQH V VSRUyG SLNVHOLNDQG\GDWyZ QD

SRGVWDZLH SRUyZQD Z G]LHG]LQLH OLF]E FDáNRZLW\FK

•

Bresenhama

•

SXQNWX URGNRZHJR DQJ midpoint)

•

porównawczy Jordana

•

F]WHURNURNRZ\ Z RJyOQRFL ZLHlokrokowy) Gilla

•

strukturalne
.ROHMQH SLNVHOH RGFLQND Z\]QDF]DQH V QD SRGVWDZLH RSLVX VWUXNWXUDOQHJR

•

Metzgera-Bronsa

•

]H ]PLHQQ GáXJRFL VHULL DQJ. run length slice)

$OJRU\WP\ U\VRZDQLD RGFLQNyZ ] Z\JáDG]DQLHP SR]LRPDPL MDVQRFL
(ang. antialiasing):

•

numeryczne – nie omawiane tutaj

•

warunkowe

•

z upr

RV]F]RQ\P Z\JáDG]DQLHP

•

VWUXNWXUDOQH QLH QDGDM VL

Oznaczenia: (xs , ys SRF]WHN RGFLQND

xe , ye) - koniec odcinka.

Algorytm podstawowy

•

UyZQDQLH SURVWHM QD SáDV]F]\(QLH

y = m * x + b

ZVSyáF]\QQLN NLHUXQNRZ\

b - wyraz wolny

•

dwa przypadki:

m = -1

| | < 1

| | > 1

5\V .W QDFK\OHQLD α rysowanego

RGFLQND Z ]DOH*QRFL RG

ZVSyáF]\QQLND NLHUXQNRZHJR m.

•

|m| > 1

zamiast równania y = m * x + b

PR*HP\ UR]SDWU\ZDü UyZQDQLH x = m' * y + b',
gdzie m' =

, b' =

−

, przy czym wówczas |m'|

≤ 1,

ZL F SU]\SDGHN WHQ VSURZDG]D VL GR GUXJLHJR SU]\SDGNX

•

|m|

≤ 1

xe ≠ xs,

−
−

m x

−

parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye.
zmienne procedury: m, b:real; inc, dx, dy:integer; dx := xe-x; dy := ye-y;

dla |dx|

≥ |dy| (czyli |m| ≤ 1):

m := dy/dx

^]Dá `

b := y-m*x;
inc := sgn(dx);
while x

≠ xe do

begin

plot(x, y);
x := x+inc;
y := round(m*x+b)

end;

plot(xe,ye)

$OJRU\WP Uy*QLFRZ\ DQJ DDA - Digital Differential Analyser)

•

dla |m|

≤ ]PLDQD ZVSyáU] GQHM x o ±1 ⇒ ]PLDQD ZVSyáU] GQHM y o ±m.

•

dla |m

_! ]PLDQD ZVSyáU] GQHM y o ±1 ⇒ ]PLDQD ZVSyáU] GQHM x o ±

∆

∆ y m

x=1

Rys. Dla |m|

≤1 Zmiana

ZVSyáU] GQHM x o 1

SRZRGXMH ]PLDQ

ZVSyáU] GQHM y o m

parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye.
zmienne procedury: z, zinc:real; inc, dx, dy:integer; dx := xe-x; dy := ye-y;

dla |dx|

≥ |dy| (czyli |m| ≤ 1):

z := y;
inc := sgn(dx);
zinc := dy/|dx

_ ^]Dá `

while x

≠ xe do

begin

plot(x, y);
x := x+inc;
z := z+zinc;
y := round(z)

end;

plot(xe,ye)

Algorytm Bresenhama

•

=DáR*HQLH U\VRZDQ\ RGFLQHN QDFK\ORQ\ GR RVL 0X SRG NWHP α ∈ [0,

π
4

'OD WDNLHJR NWD QDFK\OHQLD α ND*G\ NROHMQ\ SLNVHO U\VRZDQHJR RGFLQND MHVW

VVLDGHP SRSU]HGQLHJR Z NLHUXQNX Ò albo Î.

narysowany

piksel

ostatnio

dwa

piksele

kandydaci

odcinek
idealny

Rys. Kryterium wyboru

kolejnego piksela dla

UR]ZD*DQHJR SU]\SDGNX

•

d1>d2 ⇒ rysowany
górny piksel kandydat,

•

d1<d2 ⇒ rysowany
dolny piksel kandydat,

•

d1=d2 ⇒ rysowany
dowolny z pikseli
kandydatów.

•

3U]\MPLMP\ *H RVWDWQLR QDU\VRZDQ\ SLNVHO PD ZVSyáU] GQH xi, yi.

:yZF]DV ZVSyáU] GQH NROHMQHJR SLNVHOD Z\QLRV

xi+1:= xi +1

przy wyborze dowolnego z pikseli kandydatów,

+ =







przy wyborze górnego piksela kandydata,

przy wyborze dolnego piksela kandydata.

•

Wynik porównania d1>d2 decyduje o wyborze kolejnego piksela
do rysowania:

d1 = y-yi = m*(xi+1)+b-yi.
d2 = (yi+1)-y = (yi+1)-m*(xi+1)-b.

•

=DPLDVW QLHUyZQRFL d1>d2 PR*QD UR]ZD*Dü ]QDN Uy*QLF\ d1-d2.
d1-d2 = 2*m*(xi+1)+2*b-2*yi-1.

•

3RQLHZD* U\VRZDQ\ RGFLQHN QDFK\ORQ\ MHVW GR RVL 0X SRG NWHP α ∈ [0,

π
4

]

ZL F ∆x = xe-xs ! VWG VJQd1-d2) = sgn(∆x*(d1-d2)).

•

Oznaczenie:

pi = ∆x*(d1-d2) =

= 2*∆x*m*(xi+1)+2*∆x*b-2*∆x*yi-∆x =
= 2*∆x*m*(xi+1)+2*∆x*ys-2*∆x*m*xs-2*∆x*yi-∆x =
= 2*∆y*(xi+1)+2*∆x*ys-2*∆y*xs-2*∆x*yi-∆x.

b = ys-m*xs

∆y = ∆x*m

:DUWRü pi jest zawsze ZDUWRFL FDáNRZLW.

•

d1>d2 ⇔ d1-d2>0 ⇔ pi>0 ⇒

wybór górnego piksela kandydata,

d1<d2 ⇔ d1-d2<0 ⇔ pi<0 ⇒

wybór dolnego piksela kandydata,

d1=d2 ⇔ d1-d2=0 ⇔ pi=0 ⇒

wybór dowolnego piksela kandydata,
w algorytmie przyj

WR Z\EyU JyUQHJR

•

3RF]WNRZD ZDUWRü pi:

p0 = 2*∆y*(x0+1)+2*∆x*ys-2*∆y*xs-2*∆x*y0-∆x =

= 2*∆y*xs+2*∆y+2*∆x*ys-2*∆y*xs-2*∆x*ys-∆x =

= 2*∆y-∆x.

x0=xs, y0=ys

•

Modyfikacja warto

FL pi:

pi+1-pi = 2*∆y*(xi+1-xi)-2*∆x*(yi+1-yi) =

= 2*∆y-2*∆x*(yi+1-yi) =
=

(

)

(

∆

−

≥

+ −







JG\

xi+1-xi = 1
yi+1-yi ∈ {0,1}

parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye.
zmienne procedury: p, pinc, pdec, dx, dy:integer; dx := xe-x; dy := ye-y;

dla dx

≥ dy ≥ 0:

p := 2*dy-dx;
pinc := 2*dy;
pdec := 2*(dy-dx);
while x

≠ xe do

begin

plot(x, y);
x := x+1;
if p < 0 then p := p+pinc

else begin y := y+1; p := p+pdec end

end;

plot(xe,ye)

$OJRU\WP SXQNWX URGNRZHJR DQJ midpoint)

•

=DáR*HQLH U\VRZDQ\ RGFLQHN QDFK\ORQ\ GR RVL 0X SRG NWHP α ∈ [0,

π
4

'OD WDNLHJR NWD QDFK\OHQLD α ND*G\ NROHMQ\ SLNVHO U\VRZDQHJR RGFLQND MHVW

VVLDGHP SRSU]HGQLHJR Z NLHUXQNX Ò albo Î.

narysowany

piksel

ostatnio

dwa

piksele

kandydaci

odcinek
idealny

Rys. Kryterium wyboru kolejnego

SLNVHOD GOD UR]ZD*DQHJR
przypadku:
o wyborze kolejnego piksela

GHF\GXMH ]QDN ZDUWRFL
funkcji F(x,y)= a*x+b*y+c

Z SXQNFLH URGNRZ\P

]D]QDF]RQ\P NU]\*\NLHP

SRPL G]\ SLNVHODPL
kandydatami.

•

3U]\MPLMP\ *H RVWDWQLR QDU\VRZDQ\ SLNVHO PD ZVSyáU] GQH xi, yi.

:yZF]DV ZVSyáU] GQH NROHMQHJR SLNVHOD Z\QLRV

xi+1:= xi +1

przy wyborze dowolnego z pikseli kandydatów,

+ =







przy wyborze górnego piksela kandydata,

przy wyborze dolnego piksela kandydata.

•

Równanie ogólne prostej: F(x,y)=0, gdzie F(x,y)=a*x+b*y+c.

Dla dwóch punktów prostej: a

−

(

)

V H

, b

−

(

)

V H

3U]\MPXMF c = xe*ys - xs*ye RWU]\PXMH VL a = ye - ys, b = -(xe - xs).
:DUWRFL a, b, c PR*QD ZL F WDN GREUDü E\ E\á\ FDáNRZLWH.

•

3RQLHZD* SRF]WHN RGFLQND xs , ys) i jego koniec (xe , ye OH* QD SURVWHM
F(x,y

ZL F

F(x0,y0) = F(xs,ys) = 0

oraz

F(xe,ye) = 0.

•

Oznaczenie:

fi := [F(xi+1, yi+

)] = [a*(xi+1) + b*(yi+

) + c] =

= a*xi + b*yi + c + a + [

] = F(xi,yi) + a + [

:DUWRü fi jest zawsze ZDUWRFL FDáNRZLW.

•

F(xi+1,yi+

) > 0

⇒ fi ≥ 0 ⇒ wybór górnego piksela kandydata,

F(xi+1,yi+

) < 0

⇒ fi < 0 ⇒ wybór dolnego piksela kandydata,

F(xi+1,yi+

) = 0

⇒ wybór dowolnego piksela kandydata,

przyj

WR Z\EyU JyUQHJR JG\* ZWHG\ fi = 0.

•

3RF]WNRZD ZDUWRü fi:

f0 = F(x0,y0) + a + [

] =

= F(xs,ys) + a + [

] =

= a + [

x0=xs, y0=ys

F(x0,y0) = F(xs,ys) = 0

•

0RG\ILNDFMD ZDUWRFL fi:

fi+1-fi = F(xi+1,yi+1) - F(xi,yi) =

= a*(xi+1-xi) + b*(yi+1-yi) =
= a + b*(yi+1-yi) =

JG\

≥

+ −







(

xi+1-xi = 1
yi+1-yi ∈ {0,1}

parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye.
zmienne procedury: f, df, dx, dy:integer;

dx := xe-x; dy := ye-y;

dla dx

≥ dy ≥ 0:

df := dy-dx;
f := df+(dx div 2);

{ f := dy-((dx+1) div 2);}

while x

≠ xe do

begin

plot(x, y);
x := x+1;
if f < 0 then f := f+dy

else begin y := y+1; f := f+df end

end;

plot(xe,ye)

Algorytm porównawczy Jordana

•

áR*HQLH U\VRZDQ\ RGFLQHN QDFK\ORQ\ GR RVL 0X SRG NWHP α ∈ [0,

π
2

'OD WDNLHJR NWD QDFK\OHQLD α ND*G\ NROHMQ\ SLNVHO U\VRZDQHJR RGFLQND MHVW

VVLDGHP SRSU]HGQLHJR Z NLHUXQNX Ï, Ò albo Î.

narysowany

piksel

ostatnio

trzy

piksele

kandydaci

odcinek
idealny

Rys. Kryterium wyboru

kolejnego piksela dla

UR]ZD*DQHJR SU]\SDGNX
rysowany jest ten piksel,

NWyUHJR URGHN OH*\

QDMEOL*HM RGFLQND LGHDOQHJR

•

3U]\MPLMP\ *H RVWDWQLR QDU\VRZDQ\ SLNVHO PD ZVSyáU] GQH xi, yi.

:yZF]DV ZVSyáU] GQH NROHMQHJR SLNVHOD PRJ Z\QLHü

xi+1:= xi +1
yi+1:= yi

przy wyborze prawego piksela kandydata,

xi+1:= xi
yi+1:= yi +1

przy wyborze górnego piksela kandydata,

xi+1:= xi +1
yi+1:= yi +1

przy wyborze prawego górnego piksela kandydata.

•

Równanie ogólne prostej: F(x,y)=0, gdzie F(x,y)=a*x+b*y+c.

Dla dwóch punktów prostej: a

−

(

)

V H

, b

−

(

)

V H

Przyjmuj

F c = - (xe*ys - xs*ye RWU]\PXMH VL b = xe - xs, a = -(ye - ys).

:DUWRFL a, b, c PR*QD ZL F WDN GREUDü E\ E\á\ FDáNRZLWH.

•

Oznaczenia:

f := F(xi,yi),

F(x0,y0) = F(xs,ys) = 0,

f1 := F(xi+1,yi) = f+a,
f2 := F(xi,yi+1) = f+b,
f3 := F(xi+1,yi+1) = f+a+b.

•

|f1|<|f2| & |f1|<|f3| ⇒

wybór prawego piksela kandydata,

|f2|<|f1| & |f2|<|f3| ⇒

wybór górnego piksela kandydata,

|f3|<|f1| & |f3|<|f2| ⇒

wybór prawego górnego piksela kandydata,

|f1|<|f2| & |f1|=|f3| ⇒

wybór prawego lub prawego górnego piksela,

|f2|<|f1| & |f2|=|f3| ⇒

wybór górnego lub prawego górnego piksela,

Z DOJRU\WPLH SU]\M WR Z\EyU SUDZHJR JyUQHJR

•

3RQLHZD* f2 ≥ f3 ≥ f1 ZL F
|f1|<|f2| & |f1|<|f3| ⇔ |f1|<|f3| ⇒

wybór prawego piksela kandydata,

|f2|<|f1| & |f2|<|f3| ⇔ |f2|<|f3| ⇒

wybór górnego piksela kandydata,

Z SR]RVWDá\FK SU]\SDGNDFK Z\EyU SUDZHJR JyUQHJR SLNVHOD NDQG\GDWD

parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye.
zmienne procedury: f1, f2, f3, dx, dy:integer; dx := xe-x; dy := ye-y;

dla dx

≥ 0 & dy ≥ 0:

f1 := -dy;
while (x

≠ xe) or (y ≠ ye) do

begin

plot(x, y);
f3 := f1+dx;

f2 := f3+dy;

if |f1| < |f3| then begin x := x+1; f1 := f1-dy end
else if |f2| < |f3| then begin y := y+1; f1 := f2-dy end
else begin x := x+1; y := y+1; f1 := f3-dy end

end;

plot(xe,ye)

•

3RQLHZD* f2 ≥ f3 ≥ f1 ZL F
|f1|<|f3| ⇔ -f1<f3 ⇒ wybór prawego piksela kandydata,
|f2|<|f3| ⇔ f2<-f3 ⇒ wybór górnego piksela kandydata,

Z SR]RVWDá\FK SU]\SDGNDFK Z\EyU SUDZHJR JyUQHJR SLNVHOD NDQG\GDWD

parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye.
zmienne procedury: f1, f2, f3, dx, dy:integer; dx := xe-x; dy := ye-y;

dla dx

≥ 0 & dy ≥ 0:

f1 := -dy;
while (x

≠ xe) or (y ≠ ye) do

begin

plot(x, y);
f3 := f1+dx;

f2 := f3+dy;

if f3 < -f1 then begin y := y+1; f1 := f3 end;
if -f3 < f2 then begin x := x+1; f1 := f1-dy end

end;

plot(xe,ye)

$OJRU\WP F]WHURNURNRZ\ Z RJyOQRFL ZLHORNURNRZ\ *LOOD

•

=DPLDVW MHGQHJR SLNVHOD Z\]QDF]DP\ RG UD]X ZL FHM QS F]WHU\

•

=DáR*HQLH RGFLQHN QDFK\ORQ\ GR RVL 0X SRG NWHP α ∈ (0, arctg

'OD WDNLHJR NWD QDFK\OHQLD α NROHMQH F]ZyUNL SLNVHOL PRJ SU]\MPRZDü

XZ]JO GQLDMF Z]DMHPQH VVLHG]WZR MDN L SRáR*HQLH Z]JO GHP SLNVHOD

SRSU]HG]DMFHJR MHGQ ] SL FLX IRUP

0 0 0 0

0 0 0 1

0 0 1 0

0 1 0 0

1 0 0 0

•

5R]ZD*DMF F]WHU\ NURNL DOJRU\WPX %UHVHQKDPD RWU]\PXMHP\ GOD ND*GHM

F]ZyUNL SLNVHOL QDVW SXMFH ZDUXQNL

0000

0001

0010

0100

1000

pi<0

pi≥0

pi+2∆y<0

pi+2∆y≥0

pi+2∆y-2∆x<0

pi+4∆y<0

pi+4∆y≥0

pi+4∆y-2∆x<0 pi+4∆y-2∆x<0

pi+6∆y<0

pi+6∆y≥0

pi+6∆y-2∆x<0 pi+6∆y-2∆x<0 pi+6∆y-2∆x<0

:DUXQNL WH GDM VL XSURFLü GR SRQL*V]HM SRVWDFL

0000

0001

0010

0100

1000

pi <

-6

∆y ≤ pi < -4∆y ≤ pi < -2∆y ≤ pi <

≤ pi

•

$QDOL]XMF GOD SRZ\*V]\FK F]ZyUHN SLNVHOL VSRVyE PRG\ILNDFML ZDUWRFL pi

Z DOJRU\WPLH %UHVHQKDPD PR*QD ]DXZD*\ü *H

+ −

−







< −
≥ −

∆
∆

∆

∆
∆

JG\
JG\

W]Q F]ZyUND
SR]RVWDá H F]ZyUNL

•

'RGDWNRZH SU]\VSLHV]HQLH DOJRU\WPX PR*QD X]\VNDü XZ]JO GQLDMF

SUDZGRSRGRELHVWZD Z\VWSLHQLD NROHMQ\FK F]ZyUHN SR GDQHM F]ZyUFH

QL*V]H SR]\FMH Z WDEHOL RGSRZLDGDM PQLHMV]\P SUDZGRSRGRELHVWZRP

0000

0001

0010

0100

1000

0000

1000

0001

0010

0100

0010

0100

1000

0010

0001

0010

0001

parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye.
zmienne procedury: p, pinc, pdec, dx, dy, m2, m4, m6, xe2:integer;

dla dx

≥ 4*dy ≥ 0:

dx := xe-x;

dy := ye-y;

p := 2*dy-dx;

pinc := 8*dy;

pdec := 8*dy-2*dx;

m2 := -2*dy;

m4 := -4*dy;

m6 := -6*dy;

xe2 := xe-2;

while x < xe2 do

{rysowanie (dx+1) div 4 czwórek}

begin

if p < m6 then

{0000}

begin

plot(x, y); plot(x+1, y);
plot(x+2, y); plot(x+3, y);
p := p+pinc

end

else

begin

if p < m2 then

if p < m4 then

{0001}

begin

plot(x, y); plot(x+1, y);
plot(x+2, y); plot(x+3, y); y := y+1

end

else

{0010}

begin

plot(x, y); plot(x+1, y);
plot(x+2, y); y := y+1; plot(x+3, y)

end

else if p < 0 then

{0100}

begin

plot(x, y); plot(x+1, y); y := y+1;
plot(x+2, y); plot(x+3, y)

end

else

{1000}

begin

plot(x, y); y := y+1; plot(x+1, y);
plot(x+2, y); plot(x+3, y)

end;

p := p+pdec

end;

x := x+4

end;

if x

≤ xe then

{rysowanie (dx+1) mod 4 pikseli}

begin

if x < xe then

begin

if x

≤ xe2 then

begin

plot(x, y);

x := x+1;

if p

≥ 0 then y := y+1

end;

plot(x,y)

end;

plot(xe,ye)

end

Algorytm strukturalny Metzgera-Bronsa

5\V .D*G\ SLNVHO RGFLQND MDN L

GRZROQHM NU]\ZHM PR*H E\ü
kodowany jako cyfra ósemkowa

R]QDF]DMFD QXPHU VVLDGD
jakim jest ten piksel dla
poprzedzajacego go piksela.

2GFLQHN G\VNUHWQ\ MDN L ND*G

NU]\Z PR*QD ]DWHP RSLVDü

SU]\ SRPRF\ FLJX F\IU
ósemkowych zwanego kodem

áDFXFKRZ\P

Rys.

3U]\NáDGRZD NU]\ZD L MHM NRG áDFXFKRZ\

0170213

7 0

•

3RVWXODW\ )UHHPDQD RGQRQLH NRGX áDFXFKRZHJR RSLVXMFHJR RGFLQHN

•

: NRG]LH áDFXFKRZ\P PRJ Z\VW SRZDü FR QDMZ\*HM GZLH F\IU\

RGSRZLDGDMFH VVLHGQLP NLHUXQNRP

•

7\ONR MHGQD ] F\IU Z\VW SXMF\FK Z NRG]LH áDFXFKRZ\P PR*H

VVLDGRZDü VDPD ]H VRE

•

6XNFHV\ZQH UR]PLHV]F]HQLH F\IU Z NRG]LH áDFXFKRZ\P SRZLQQR E\ü

WDN MHGQRURGQH MDN W\ONR MHVW WR PR*OLZH

•

=DáR*HQLH U\VRZDQ\ RGFLQHN QDFK\ORQ\ GR RVL 0X SRG NWHP α ∈ [0,

π
4

'OD WDNLHJR NWD QDFK\OHQLD α ND*G\ NROHMQ\ SLNVHO U\VRZDQHJR RGFLQND MHVW

VVLDGHP SRSU]HGQLHJR Z NLHUXQNX Ò albo Î : NRG]LH áDFXFKRZ\P

PRJ ZL F Z\VW SRZDü MHG\QLH F\IU\ L
3RQLHZD* RGFLQHN MHVW QDMPQLHMV]HM GáXJRFL NU]\Z áF]F GZD SLNVHOH

ZL F Z NRG]LH áDFXFKRZ\P SRZLQQR VL ]QDOH(ü GRNáDGQLH

∆y jedynek i ∆x-∆y zer (∆y = ye-ys, ∆x = xe-xs).

•

Oznaczenia:

h ( )

= 







( )

= − 







lub

( )

= − 







( )

= 







•

Podstawienie warto

FL SRF]WNRZ\FK i := 0,

a0 := ∆y,

A0 := "1",

b0 := ∆x-∆y,

B0 := "0".

•

1DOH*\ ]DWHP SU]HPLHV]Dü ai áDFXFKyZ Ai z bi áDFXFKDPL Bi.

•

Podstawienie:
ci := max(ai,bi),

ci=ai ⇒ Ci := Ai, Di := Bi,

di := min(ai,bi),

ci≠ai ⇒ Ci := Bi, Di := Ai,

ci ≥ di.

•

1D MHGHQ áDFXFK Di SU]\SDGD UHGQLR ri

áDFXFKyZ Ci (ri≥1).

•

ri FDáNRZLWH ⇒

NRG áDFXFKRZ\ RGFLQND









)

(

)

(

•

-HOL ri QLH MHVW ZDUWRFL FDáNRZLW WR QDOH*\ SU]HPLHV]Dü ]H VRE
ai+1 := ci mod di

áDFXFKyZ

DiCi

+ =

([ ]

)

([ ]

)

bi+1 := di - (ci mod di

áDFXFKyZ

ri D

iCi

+ =

([ ])

1DOH*\ ZL F SRZWyU]\ü SRZ\*V]H NURNL GOD i := i+1.

parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye.
zmienne procedury: A, B:string; w:Boolean; a, b, dx, dy:integer; dx := xe-x;

dla dx

≥ dy ≥ 0:

dy := ye-y;

a := dy; b := dx-dy; A := "1"; B := "0";
while a

≠ 0 do

begin

w := false; {true}
if a < b then begin swap(a,b); swap(A,B) end;
repeat

if w then B := A+B else B := B+A;
w := not w;
a := a-b

until a < b;
if w then A := A+B else A := B+A;
b := b-a

end;

for i := 1 to b do

for j := 1 to length(B) do

begin

plot(x,y);
x := x+1; if B[j] = '1' then y := y+1

end;

plot(xe,ye)

parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye.
zmienne procedury: A, B:string; w:Boolean; a, b, dx, dy:integer; dx := xe-x;

dla dx

≥ dy ≥ 0:

dy := ye-y;

a := dy; b := dx-dy; A := "1"; B := "0";
w := false; {true}
while a

≠ 0 do

begin

while a < b do

begin

if w then A := A+B else A := B+A;
w := not w;
b := b-a

end;

repeat

if w then B := A+B else B := B+A;
w := not w;
a := a-b

until a < b

end;

for i := 1 to b do

for j := 1 to length(B) do

begin

plot(x,y);
x := x+1; if B[j] = '1' then y := y+1

end;

plot(xe,ye)

$OJRU\WP VWUXNWXUDOQ\ ]H ]PLHQQ GáXJRFL VHULL (ang. run length
slice)

•

=DáR*HQLH RGFLQHN QDFK\ORQ\ GR RVL 0X SRG NWHP ϕ ∈ (0, arctg

'OD WDNLHJR NWD QDFK\OHQLD ϕ ND*G\ NROHMQ\ SLNVHO U\VRZDQHJR RGFLQND MHVW

VVLDGHP SRSU]HGQLHJR Z NLHUXQNX Ò albo Î : NRG]LH áDFXFKRZ\P

PRJ ZL F Z\VW SRZDü MHG\QLH F\IU\ L 3RQDGWR ND*GD MHG\QND E G]LH Z

W\P NRG]LH áDFXFKRZ\P RWRF]RQD ]HUDPL JG\* ]HU MHVW ZL FHM
3RQLHZD* RGFLQHN MHVW QDMPQLHMV]HM GáXJRFL NU]\Z áF]F GZD SLNVHOH

ZL F Z NRG]LH áDFXFKRZ\P SRZLQQR VL ]QDOH(ü GRNáDGQLH

β = ∆y jedynek i α = ∆x-∆y zer (∆y = ye-ys, ∆x = xe-xs).

•

.RG áDFXFKRZ\ RGFLQND

1 0

2 1

−

∏

gdzie

∑

∏

...

7U]HFL SRVWXODW )UHHPDQD PyZL W\OH *H ZDUWRFL α

SRZLQQ\ E\ü MDN

QDMEOL*V]H VLHELH : SUDNW\FH R]QDF]D WR L* α

SU]\MPXMH MHGQ ] GZyFK

ZDUWRFL

α div (2β) lub

+1 =

α div (2β)+1, przy czym

UR]NáDG W\FK ZDUWRFL SRZLQLHQ E\ü MDN QDMEDUG]LHM UyZQRPLHUQ\ :áDVQRü

W ]DSHZQLD QDVW SXMF\ Z]yU LWHUDF\MQ\

−









−

∑

round

lub

β α

−









−

∑

div (2

β).

•

2VWDWHF]QLH NRG áDFXFKRZ\ RGFLQND G\VNUHWQHJR MHVW QDVW SXMF\

1 0

2 1

−

∏

gdzie

∏

...

 α div (2β)

dla

α mod (2β) < 2β,

]D α



 α div (2β) +1

dla

α mod (2β) ≥ 2β,

= (

α(j−1) +β) mod (2β),

czyli

β,

 λ

α mod (2β)

dla

α mod (2β) < 2β,

j+1



 λ

α mod (2β) − 2β

dla

α mod (2β) ≥ 2β,

parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye.
zmienne procedury: a, b, a2, ba2M, ba2D, l, i, j, dx, dy:integer;

dx := xe-x;

dla dx

≥ 2*dy > 0:

dy := ye-y;

a := dy; b := dx-dy; l := a;
a2 := a+a; ba2M := b mod a2; ba2D := b div a2;
plot(x,y);
for i := 1 to a do

begin

for j := 1 to ba2D do begin x := x+1; plot(x,y) end;
l := l+ba2M;
if l

≥ a2 then begin l := l-a2; x := x+1; plot(x,y) end;

x := x+1; y := y+1; plot(x,y);
for j := 1 to ba2D do begin x := x+1; plot(x,y) end;
l := l+ba2M;
if l

≥ a2 then begin l := l-a2; x := x+1; plot(x,y) end

end

parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye.
zmienne procedury: a, b, a2, baD, baM2, ba2M, ba2D, l, i, j, dx, dy:integer;

dla dx

≥ 2*dy > 0:

dx := xe-x; dy := ye-y;

a := dy; b := dx-dy; l := a;
a2 := a+a; ba2M := b mod a2; ba2D := b div a2;
baD := ba2D+ba2D; baM2 := ba2M+ba2M;
if ba2M > a

then begin baD := baD+1; baM2 := baM2-a2 end;

plot(x,y);
for j := 1 to ba2D do begin x := x+1; plot(x,y) end;
l := l+ba2M;
if l

≥ a2 then begin l := l-a2; x := x+1; plot(x,y) end;

x := x+1; y := y+1; plot(x,y);
for i := 2 to a do

begin

for j := 1 to baD do begin x := x+1; plot(x,y) end;
l := l+baM2;
if l

≥ a2 then begin l := l-a2; x := x+1; plot(x,y) end;

x := x+1; y := y+1; plot(x,y);

end;

for j := 1 to ba2D do begin x := x+1; plot(x,y) end;
if l+ba2M

≥ a2 then begin x := x+1; plot(x,y) end

„

= EDWRü” odcinków dyskretnych (ang. aliasing)

5\V 2GFLQHN G\VNUHWQ\ ] Z\UD(QLH ZLGRF]Q\PL ] EDPL VFKRGNDPL

Metody usuwania „

] EDWRFL” odcinków

•

]ZL NV]HQLH UR]G]LHOF]RFL

5\V 2GFLQHN G\VNUHWQ\ Z ]ZL NV]RQHM UR]G]LHOF]RFL

•

Z\JáDG]DQLH RGFLQNyZ SR]LRPDPL MDVQRFL DQJ antialiasing)

5\V :\JáDG]RQ\ RGFLQHN G\VNUHWQ\

Rys. Model odcinka

-DNR LGHDOQH SU]\EOL*HQLH RGFLQND G\VNUHWQHJR PR*QD SU]\Mü SURVWRNW R

V]HURNRFL SLNVHOD : SU]\SDGNX RGFLQND XNRQHJR E G]LH RQ SRNU\ZDá

W\ONR IUDJPHQW\ SLNVHOL -DVQRü W\FK SLNVHOL SRZLQQD ZL F ]DOH*Hü RG

UR]PLDUyZ IUDJPHQWyZ SRNU\ZDQ\FK SU]H] WDNL SURVWRNW 8]\VNDQ\ Z WHQ

VSRVyE U\VXQHN RGFLQND GDMH ZUD*HQLH Z\JáDG]RQHJR DQJ antialiased).

:\JáDG]DQLH RGFLQNyZ G\VNUHWQ\FK DQJ antialiasing)

•

bezwagowe próbkowanie powierzchni

Rys. Bezwagowe próbkowanie powierzchni odpowiada

SURVWRSDGáRFLHQQHM IXQNFML ZDJRZHM

5\V %H]ZDJRZR Z\JáDG]RQ\ RGFLQHN G\VNUHWQ\ ZDJD SURVWRSDGáRFLHQQD

•

wagowe próbkowanie powierzchni

5\V 2VWURVáXSRZD IXQNFMD ZDJRZD

5\V 6WR*NRZD IXQNFMD ZDJRZD

5\V :DJRZR Z\JáDG]RQ\ RGFLQHN G\VNUHWQ\ ZDJD RVWURVáXSRZD X JyU\

L ZDJD VWR*NRZD QD GROH

$OJRU\WP ] XSURV]F]RQ\P Z\JáDG]DQLHP DQJ antialiasing)

•

=DáR*HQLH U\VRZDQ\ RGFLQHN QDFK\ORQ\ GR RVL 0X SRG NWHP α ∈ [0,

π
4

narysowane

ostatnio

(dwie pary)

trzy piksele

odcinek
idealny

piksele

kandydaci

Piksele rysowane parami w pionie.

Rys. Kryterium wyboru kolejnych

pikseli:

•

k>0

⇒ kolejne dwa piksele

rysowane w tych samych
wierszach (yi, yi-1),

•

k<0

⇒ kolejne dwa piksele

rysowane w wierszach o

SR]LRP Z\*HM yi+1, yi),

•

k=0

⇒ kolejny piksel (tylko

jeden) rysowany
w górnym wierszu (yi),

•

3U]\MPLMP\ *H JyUQ\ ] RVWDWQLR QDU\VRZDQ\FK SLNVHOL PD ZVSyáU] GQH xi, yi.

:yZF]DV ZVSyáU] GQH JyUQHJR SLNVHOD NROHMQHM SDU\ Z\QLRV

xi+1:= xi +1

+ =







dla k<0,

dla k

≥0.

•

,QWHQV\ZQRü JyUQHJR SLNVHOD MHVW ZSURVW SURSRUFMRQDOQD GR k,

LQWHQV\ZQRü GROQHJR SLNVHOD MHVW ZSURVW SURSRUFMRQDOQD GR k.

•

=DáR*HQLH SURFHGXUD SORWx, y, c, c

max

QDGDMH SXQNWRZL R ZVSyáU] GQ\FK

x, y

LQWHQV\ZQRü Z]JO GQ c / c

max

(gdzie c, c

max

ZDUWRFL FDáNRZLWH

•

Zami

DVW ZDUWRFL XáDPNRZHM k OHSLHM MHVW UR]ZD*Dü ZDUWRü FDáNRZLW k

∆x.

parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye.
zmienne procedury: kdx, dx, dy:integer;

dx := xe-x; dy := ye-y;

dla dx

≥ dy ≥ 0:

kdx := 0;
while x

≠ xe do

begin

plot(x, y, dx-kdx, dx);
if kdx

≠ 0 then plot(x, y-1, kdx, dx);

x := x+1;
kdx := kdx-dy;
if kdx < 0 then begin y := y+1; kdx := kdx+dx end

end;

plot(xe, ye, 1, 1)

$OJRU\WP :X ] Z\JáDG]DQLHP DQJ antialiasing)

•

=DáR*HQLH U\VRZDQ\ RGFLQHN QDFK\ORQ\ GR RVL 0X SRG NWHP α ∈ [0,

π
4

Piksele rysowane parami w pionie.

•

=DáR*HQLH

GRVW SQ\FK SR]LRPyZ MDVQRFL

•

3U]\MPLMP\ *H GROQ\ ] RVWDWQLR QDU\VRZDQ\FK SLNVHOL PD ZVSyáU] GQH xi, yi.

:yZF]DV ZVSyáU] GQH GROQHJR SLNVHOD NROHMQHM SDU\ Z\QLRV

xi+1:= xi +1

+ =







dla [a·(i+1)] > [a·i], gdzie a = tg

α,

dla [a·(i+1)] = [a·i].

•

,QWHQV\ZQRü JyUQHJR SLNVHOD MHVW ZSURVW SURSRUFMRQDOQD GR a·(i+1)-[a·(i+1)],

LQWHQV\ZQRü GROQHJR SLNVHOD MHVW ZSURVW SURSRUFMRQDOQD GR a·(i+1)+[a·(i+1)].

•

=DáR*HQLH SURFHGXUD SORWx, y, c, c

max

QDGDMH SXQNWRZL R ZVSyáU] GQ\FK

x, y

LQWHQV\ZQRü Z]JO GQ c / c

max

(gdzie c, c

max

ZDUWRFL FDáNRZLWH

FR ZL FHM c

max

MHVW SRPQLHMV]RQ R SRW J OLF]E\

•

=DPLDVW ZDUWRFL XáDPNRZHM a·i-[a·i] OHSLHM MHVW UR]ZD*Dü ZDUWRü FDáNRZLW
([2

·a+0,5]·i) mod 2

•

=DáR*HQLH IXQNFMD RYHUIORZd ]ZUDFD ZDUWRü true tylko wtedy,
gdy poprzednia operacja na zmiennej d

]DNRF]\áD VL SU]HSHáQLHQLHP

parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye.
VWDáH SURFHGXU\ n {liczba bitów dla typu integer},

nm {n-m>0, gdzie 2

MHVW OLF]E SR]LRPyZ V]DURFL},

em {2

-1};

zmienne procedury: dx, dy, d, dinc:integer;

dx := xe-x; dy := ye-y;

dla dx

≥ dy ≥ 0:

d := 0;
dinc := ((dy shl n)+(dx shr 1)) div dx;
while x

≠ xe do

begin

plot(x, y, em - (d shr nm) , em);
if d

≠ 0 then plot(x, y+1, d shr nm, em);

x := x+1; d := d+dinc {mod 2

};

if overflow(d) then y := y+1

end;

plot(xe, ye, em, em)

àXN RNU JX HOLSV\

5\V 'ZLH RULHQWDFMH SU]\ U\VRZDQLX RNU JX

(orientacja ujemna - zgodnie z ruchem
wskazówek zegara, orientacja dodatnia -
przeciwnie do ruchu wskazówek zegara).

orientacja

ujemna

orientacja
dodatnia

$OJRU\WP\ U\VRZDQLD áXNyZ RNU JyZ HOLSV:

•

zmiennoprzecinkowe

.ROHMQH SLNVHOH áXNX Z\]QDF]DQH V SU]H] SRGVWDZLDQLH ]PLHQLDQHM ]H

VWDá\P NURNLHP SHZQHM ]PLHQQHM GR Z]RUyZ JHRPHWULL HXNOLGHVRZHM

L ]DRNUJODQLH RWU]\PDQ\FK Z WHQ VSRVyE ZVSyáU] GQ\FK

•

podstawowy

•

parametryczny

•

+RQJD VWDáRSU]HFLQNRZD ZHUVMD DOJRU\WPX SDUDPHWU\F]QHJR

•

warunkowe

.ROHMQH SLNVHOH áXNX Z\]QDF]DQH V VSRUyG SLNVHOLNDQG\GDWyZ QD

SRGVWDZLH SRUyZQD Z G]LHG]LQLH OLF]E FDáNRZLW\FK

•

Bresenhama

•

SXQNWX URGNRZHJR DQJ midpoint)

•

porównawczy Jordana

5\V àXN RNU JX R URGNX Z SXQNFLH &

UR]SRF]\QDMF\ VL Z SXQNFLH 6

NRF]F\ VL QD SyáSURVWHM &(
wyznaczonej przez punkt E,
rysowany przy orientacji dodatniej.
Uwaga:

3RGDQH QL*HM DOJRU\WP\

U\VXM áXNL ZJ RULHQWDFML GRGDWQLHM

Oznaczenia: (xs , ys SRF]WHN áXNX

(xe , ye NRQLHF áXNX

(xc , yc URGHN RNU JX

=DáR*HQLH

:VSyáF]\QQLN NV]WDáWX SLNVHOD DQJ aspect ratio) wynosi 1.

5\V :VSyáF]\QQLN NV]WDáWX SLNVHOD UyZQ\ MHVW

piksel

Uwaga:

2NUJ R URGNX xc , yc) i promieniu r PR*QD RWU]\PDü ] RNU JX R

URGNX L SURPLHQLX r VWRVXMF SU]HVXQL FLH R ZHNWRU xc , yc).

Oktanty (ósemki)

5\V 3RG]LDá RNU JX QD RNWDQW\ yVHPNL

=D]QDF]RQD VWU]DáNDPL SU]\QDOH*QRü

GR RNWDQWX SyáSURVWHM UR]JUDQLF]DMFHM

]DOH*\ RG RULHQWDFML U\VRZDQLD

=DáR*HQLH (xc,yc) = (0,0)

dla orientacji

dodatniej

dla orientacji

ujemnej

•

$OJRU\WP Z\]QDF]DQLD QXPHUX RNWDQWX QD SRGVWDZLH ZVSyáU] GQ\FK SLNVHOD

if y > 0 then if x > 0 then if x > y then Octant := 1

else Octant := 2

else if y > -x then Octant := 3

else Octant := 4

else if x < 0 then if x < y then Octant := 5

else Octant := 6

else if y < -x then Octant := 7

else if y

≠ 0 then Octant := 8

else if x

≠ 0 then Octant := 1

else Octant := 0

Funkcja StartOctant(xs,ys,xe,ye) wykorzystuje ten algorytm do wyznaczenia

RNWDQWyZ SLNVHOD SRF]WNRZHJR xs,ys L NRFRZHJR xe,ye). Funkcja ta

]ZUDFD QXPHU RNWDQWX SLNVHOD SRF]WNRZHJR áXNX ,QLFMDOL]XMH RQD SRQDGWR
pewne zmienne globalne dla potrzeb funkcji Octant.

•

Algorytm wyznaczania numeru oktantu na podstawie

ZVSyáU] GQ\FK SLNVHOD

SU]\ GRGDWNRZHM ]QDMRPRFL QXPHUX RNWDQWX SRSU]HG]DMFHJR JR SLNVHOD Z

áXNX RNU JX R SURPLHQLX r > 1) rysowanym przy orientacji dodatniej:

case Octant of 1: if x > y

then Octant := 1 else Octant := 2;

2: if x > 0

then Octant := 2 else Octant := 3;

3: if y > -x then Octant := 3 else Octant := 4;
4: if y > 0

then Octant := 4 else Octant := 5;

5: if x < y

then Octant := 5 else Octant := 6;

6: if x < 0

then Octant := 6 else Octant := 7;

7: if y < -x then Octant := 7 else Octant := 8;
8: if y < 0

then Octant := 8 else Octant := 1 end

Funkcja Octant(x,y) wykorzystuje ten algorytm do wyznaczenia oktantu
piksela (x,y). Funkcja ta zwraca numer oktantu tego piksela lub zero, gdy

RVLJQL W\ ]RVWDá NRQLHF áXNX :\NRU]\VWXMH RQD SRQDGWR SHZQH ]PLHQQH

JOREDOQH ]DLQLFMDOL]RZDQH SU]H] IXQNFM 6WDUW2FWDQW

•

:DUXQHN VWZLHUG]DMF\ RVLJQL FLH NRFD áXNX GOD RULHQWDFML GRGDWQLHM

:DUXQHN WHQ QDOH*\ WHVWRZDü MHG\QLH Z RNWDQFLH SLNVHOD NRFRZHJR áXNX

y*xe > ye*x ⇒ RVLJQL WR NRQLHF áXNX

Algorytm podstawowy

•

Ogólna zasada:

3U]\ U\VRZDQLX NU]\ZHM SROHJDMF\P QD Z\]QDF]DQLX ZVSyáU] GQ\FK

NROHMQ\FK SLNVHOL SRSU]H] PRG\ILNDFM MHGQHM ]H ZVSyáU] GQ\FK R L

REOLF]DQLX GUXJLHM ZVSyáU] GQHM ]H Z]RUX DQDOLW\F]QHJR ZVSyáU] GQ

]PLHQLDQ R SRZLQQD E\ü ZVSyáU] GQD GOD NWyUHM SU]\URVW\ V ZL NV]H

•

5yZQDQLH RNU JX R rodku (xc,yc) = (0,0) i promieniu r:

x2 + y2 = r2

5\V 3RG]LDá RNU JX QD RNWDQW\

Dla orientacji dodatniej i dla oktantów:

•

1, 8: y

]ZL NV]DQH R

: [

]

−

1
2

•

2, 3: x zmniejszane o 1,

: [

]

−

1
2

•

4, 5: y zmniejszane o 1,

[

]

= −

−

1
2

•

[ ]ZL NV]DQH R

[

]

= −

−

1
2

•

Uwaga:

'ZXEDMWRZ\ W\S LQWHJHU PR*H QLH Z\VWDUF]\ü GR SU]HFKRZDQLD

Z\QLNX PQR*HQLD SRGQRV]HQLD GR NZDGUDWX ZDUWRFL ZVSyáU] GQ\FK
(np. 200* ! 'ODWHJR WH* IXQNFMD SRGQRV]FD GR

NZDGUDWX SRZLQQD E\ü ]EXGRZDQD QDVW SXMFR
function sqr(u:integer):longint; begin sqr:=longint(u)*longint(u) end

parametry procedury: x, y, xe, ye, xc, yc:integer;

x := xs-xc, y := ys-yc,

zmienne procedury: rr:longint;

xe := xe-xc, ye := ye-yc,

dla oktantów nr 1 i 8:

xc := xc, yc := yc.

if StartOctant(x,y,xe,ye) in [1, 8] then

begin

rr := sqr(x) + sqr(y);
repeat

plot(x+xc, y+yc);
y := y+1;
x := round(sqrt(rr-sqr(y)))

until not (Octant(x,y) in [1, 8])

end

Algorytm parametryczny

•

Równ

DQLH SDUDPHWU\F]QH RNU JX R URGNX xc,yc) = (0,0) i promieniu r:

x = r*cosϕ,
y = r*sinϕ,

ϕ ∈ [0, 2*π)

•

=DáR*HQLH NROHMQH SLNVHOH Z\]QDF]DQH V SRSU]H] ]PLDQ SDUDPHWUX ϕ o

VWDá ZDUWRü ∆ϕ = const.

•

-H*HOL SLNVHO xi,yi PD ZVSyáU] GQH

xi = r*cosϕi,
yi = r*sinϕi,

WR SU]\ RULHQWDFML GRGDWQLHM QDVW SXMF\ SR QLP SLNVHO xi+1,yi+1) ma

ZVSyáU] GQH

xi+1 = r*cosϕi+1 = r*cos(ϕi+∆ϕ) =

= r*cosϕi*cos∆ϕ - r*sinϕi*sin∆ϕ =
= xi*cos∆ϕ - yi*sin∆ϕ,

yi+1 = r*sinϕi+1 = r*sin(ϕi+∆ϕ) =

= r*cosϕi*sin∆ϕ + r*sinϕi*cos∆ϕ =
= xi*sin∆ϕ + yi*cos∆ϕ,

∆ϕ

∆ϕ∗ ≤1

5\V :DUWRü ∆ϕ SRZLQQD SRZRGRZDü ]PLDQ

ZDUWRFL ZVSyáU] GQ\FK QLH ZL FHM QL* R
:DUWRü ∆ϕ ≤

]DSHZQLD ]PLDQ ZDUWRFL

ZVSyáU] GQ\FK QLH ZL FHM QL* R
1DOH*\ ]DWHP SU]\Mü ∆ϕ =

parametry procedury: x, y, xe, ye, xc, yc:integer;

x := xs-xc, y := ys-yc,

zmienne procedury: c, s, u, v, z:real;

xe := xe-xc, ye := ye-yc,

dla wszystkich oktantów:

xc := xc, yc := yc.

if StartOctant(x,y,xe,ye)

≠ 0 then

begin

u := 1.0 / sqrt(sqr(x) + sqr(y)); c := cos(u); s := sin(u);
v := x; z := y;
repeat

plot(x+xc, y+yc);
u := v*c-z*s; z := v*s+z*c; v := u;
x := round(v); y := round(z)

until Octant(x,y) = 0

end

Algorytm Honga

•

Dla algorytmu parametrycznego: xi+1 = xi*cos∆ϕ - yi*sin∆ϕ, ∆ϕ ≤

yi+1 = xi*sin∆ϕ + yi*cos∆ϕ.

•

Oznaczenie:
k := [log

@ OLF]ED ELWyZ SRWU]HEQ\FK GR ]DSLVDQLD ZDUWRFL r.

•

2k-1

≤ r < 2k & 2-k <

≤ 2-k+1 Z\JRGQLH ]DWHP SU]\Mü ∆ϕ =2-k <

•

3RQLHZD* NW ∆ϕ MHVW PDá\ ZL F IXQNFMH WU\JRQRPHWU\F]QH WHJR NWD

Z\VW SXMFH Z SRZ\*V]\FK Z]RUDFK PR*QD GRü GREU]H SU]\EOL*\ü

SRF]WNRZ\PL Z\UD]DPL RGSRZLHGQLFK V]HUHJyZ 7D\ORUD

cosx

n x n

= −

+ + −

(

)

(

...

sinx

n x n

= −

+ + −

(

)

(

...

•

3U]\MPXMF SU]\EOL*HQLH FRVx ≈ 1-

2, sinx

≈ x L XZ]JO GQLDMF ∆ϕ=2-k,

RWU]\PXMH VL QDVW SXMFH Z]RU\

xi+1 = xi*(1-

*(∆ϕ)

2) - yi*∆ϕ = xi -xi*2-(2k+1) -yi*2-k,

yi+1 = xi*∆ϕ + yi*(1-

*(∆ϕ)

2) = xi*2-k+yi-yi*2-(2k+1).

•

0QR*HQLH G]LHOHQLH SU]H] n RGSRZLDGD SU]HVXQL FLX DU\WPHW\F]QHPX

=DáR*HQLH shr, shl - operacje przesuwania arytmetycznego w prawo i lewo.

parametry procedury: x, y, xe, ye, xc, yc:integer;

x := xs-xc, y := ys-yc,

zmienne procedury: k, n:integer; u, v, z:longint;

xe := xe-xc, ye := ye-yc,

dla wszystkich oktantów:

xc := xc, yc := yc.

if StartOctant(x,y,xe,ye)

≠ 0 then

begin

u := sqr(x) + sqr(y); k := 0;
while u

≠ 0 do begin u := u shr 2; k := k+1 end;

{k := trunc(log2(sqrt(sqr(x)+sqr(y))))+1;}
n := 2*k+1; v := x; z := y; v := v shl n; z := z shl n;
repeat

plot(x+xc, y+yc);
u := v-x-(z shr k); z := z-y+(v shr k); v := u;
x := v shr n; y := z shr n

until Octant(x,y) = 0

end

Algorytm Bresenhama

•

=DáR*HQLH U\VRZDQ\ áXN RNU JX ] RNWDQWX QU
'OD WDNLHJR áXNX ND*G\ NROHMQ\ SLNVHO U\VRZDQHJR RGFLQND MHVW VVLDGHP
poprzedniego w kierunku

Ï albo Ñ.

narysowany

piksel

ostatnio

dwa

piksele

kandydaci

áXN LGHDOQ\

Rys. Kryterium wyboru

kolejnego piksela dla

UR]ZD*DQHJR SU]\SDGNX

•

d1>d2 ⇒ rysowany
lewy piksel kandydat,

•

d1<d2 ⇒ rysowany
prawy piksel kandydat,

•

d1=d2 ⇒ rysowany
dowolny z pikseli
kandydatów

•

3U]\MPLMP\ *H RVWDWQLR QDU\VRZDQ\ SLNVHO PD ZVSyáU] GQH xi, yi.

:yZF]DV ZVSyáU] GQH NROHMQHJR SLNVHOD Z\QLRV

+ =

−







przy wyborze lewego piksela kandydata,

przy wyborze prawego piksela kandydata.

yi+1:= yi +1

przy wyborze dowolnego z pikseli kandydatów,

•

Wynik porównania d1>d2 decyduje o wyborze kolejnego piksela

do rysowania: d

1 2

−

(

) , d

1 2

−

(

)

(

) .

•

d1>d2 ⇔ xi

−

1 2

(

)

(

)

(

)

⇔ 2

1 2

(

)

− >

−

⇔ (2*xi-1)2 > 4*(r2-(yi+1)2)
⇔ 4*xi2-4*xi+1 > 4*(r2-(yi+1)2)
⇔ 4*xi2-4*xi+2 > 4*(r2-(yi+1)2)
⇔ 2*xi2-2*xi+1 > 2*(r2-(yi+1)2)
⇔ xi2+xi2-2*xi+1 > 2*(r2-(yi+1)2)
⇔ xi2+(xi-1)2 > 2*(r2-(yi+1)2)
⇔ xi2+(yi+1)2-r2 > r2-(xi-1)2-(yi+1)2
⇔ F(xi,yi+1)+F(xi-1,yi+1) > 0

(...)2 (xi > 0)

OLF]E\ FDáNRZLWH
/ 2

F(x,y) = x2+y2-r2

•

Oznaczenie:

pi := F(xi,yi+1)+F(xi-1,yi+1).

:DUWRü pi jest zawsze ZDUWRFL FDáNRZLW.

•

d1>d2 ⇔ pi>0 ⇒ wybór lewego piksela kandydata,
d1<d2 ⇔ pi<0 ⇒ wybór prawego piksela kandydata,
d1=d2 ⇔ pi=0 ⇒ wybór dowolnego piksela kandydata,

w algorytmie

SU]\M WR Z\EyU OHZHJR

ten przypadek nigdy nie zajdzie.

•

3RF]WNRZD ZDUWRü pi:

p0 = F(x0,y0+1)+F(x0-1,y0+1) =

= F(xs,ys+1)+F(xs-1,ys+1) =
= xs2+(ys+1)2-r2+(xs-1)2+(ys+1)2-r2 =
= xs2+ys2+2*ys+1-r2+xs2-2*xs+1+ys2+2*ys+1-r2 =
= 4*ys-2*xs+3.

x0=xs, y0=ys

x 2+y 2-r 2=0

•

0RG\ILNDFMD ZDUWRFL pi:
pi+1-pi = F(xi+1,yi+1+1)+F(xi+1-1,yi+1+1)-F(xi,yi+1)-F(xi-1,yi+1) =

= xi+12+(yi+1+1)2-r2+(xi+1-1)2+(yi+1+1)2-r2+

-xi2-(yi+1)2+r2-(xi-1)2-(yi+1)2+r2 =

= xi+12-xi2+(xi+1-1)2-(xi-1)2+2*((yi+1+1)2-(yi+1)2) =








xi2-xi2+(xi-1)2-(xi-1)2+2*((yi+2)2-(yi+1)2) =

= 4*yi+6 dla wyboru prawego piksela,

(xi-1)2-xi2+(xi-2)2-(xi-1)2+2*((yi+2)2-(yi+1)2) =

= 4*yi-4*xi+10 dla wyboru lewego piksela.

parametry procedury: x, y, xe, ye, xc, yc:integer;

x := xs-xc, y := ys-yc,

zmienne procedury: p:integer;

xe := xe-xc, ye := ye-yc,

dla oktantu nr 1:

xc := xc, yc := yc.

if StartOctant(x,y,xe,ye) = 1 then

begin

p := 4*y-2*x+3;
repeat

plot(x+xc, y+yc);
if p < 0 then p := p+4*y+6

else begin p := p+4*(y-x)+10; x := x-1 end;

y := y+1

until Octant(x,y)

≠ 1

end

$OJRU\WP SXQNWX URGNRZHJR DQJ midpoint)

•

=DáR*HQLH U\VRZDQ\ áXN RNU JX ] RNWDQWX QU
'OD WDNLHJR áXNX ND*G\ NROHMQ\ SLNVHO U\VRZDQHJR RGFLQND MHVW VVLDGHP
poprzedniego w kierunku

Ï albo Ñ.

narysowany

piksel

ostatnio

dwa

piksele

kandydaci

áXN LGHDOQ\

Rys. Kryterium wyboru

kolejnego piksela dla

UR]ZD*DQHJR SU]\SDGNX
o wyborze kolejnego
piksela decyduje znak

ZDUWRFL IXQNFML
F(x,y)=x2+y2-r2

Z SXQNFLH URGNRZ\P

]D]QDF]RQ\P NU]\*\NLHP

SRPL G]\ SLNVHODPL
kandydatami.

•

Przyjmi

MP\ *H RVWDWQLR QDU\VRZDQ\ SLNVHO PD ZVSyáU] GQH xi, yi.

:yZF]DV ZVSyáU] GQH NROHMQHJR SLNVHOD Z\QLRV

+ =

−







przy wyborze lewego piksela kandydata,

przy wyborze prawego piksela kandydata.

yi+1:= yi +1

przy wyborze dowolnego z pikseli kandydatów,

•

Oznaczenie:

fi := F(xi-

,yi+1)-

= (xi-

)2 +(yi+1)2 -r2 -

= xi2 -xi +yi2 +2*yi +1 -r2.

•

Uwaga:

:DUWRü fi := F(xi-

,yi+1) -

MHVW ]DZV]H ZDUWRFL FDáNRZLW

•

Kryterium wyboru kolejnego piksela:

•

F(xi-

,yi+1)>0 ⇔ fi ≥ 0 ⇒ rysowany lewy piksel kandydat,

•

F(xi-

,yi+1)<0 ⇔ fi < 0 ⇒ rysowany prawy piksel kandydat,

•

F(xi-

,yi+1)=0 ⇒ rysowany dowolny z pikseli kandydatów -

ten przypadek nigdy nie zajdzie.

•

Pocz

WNRZD ZDUWRü fi:

⇓

−

f0 := F(x0,y0)-

= F(xs,ys)-

= xs2 -xs +ys2 +2*ys +1 -r2 = 2*ys -xs +1.

•

0RG\ILNDFMD ZDUWRFL fi:
fi+1-fi := F(xi+1-

,yi+1+1) -

- F(xi-

,yi+1) +

= xi+12 -xi+1 +yi+12 +2*yi+1 +1 -r2 -xi2 +xi -yi2 -2*yi -1 +r2 =

= xi+12-xi2-xi+1+xi+yi+12-yi2+2*(yi+1-yi) =

= (xi+1+xi-1)*(xi+1-xi)+(yi+1+yi+2)*(yi+1-yi) =

= (xi+1+xi-1)*(xi+1-xi)+2*yi+3 =

−







JG\ Z\EUDQR SUDZ\ SLNVHO
JG\ Z\EUDQR OHZ\ SLNVHO

+ +

+ −

+ +







1 1

JG\ Z\EUDQR SUDZ\ SLNVHO
JG\ Z\EUDQR OHZ\ SLNVHO

yi+1 = yi+1
xi+1 = xi
xi+1 = xi-1

parametry procedury: x, y, xe, ye, xc, yc:integer;

x := xs-xc, y := ys-yc,

zmienne procedury: f:integer;

xe := xe-xc, ye := ye-yc,

dla oktantu nr 1:

xc := xc, yc := yc.

if StartOctant(x,y,xe,ye) = 1 then

begin

f := 2*y-x+1;
repeat

plot(x+xc, y+yc);
y := y+1;
if f < 0 then f := f+2*y+1

else begin x := x-1; f := f+2*(y-x)+1 end

until Octant(x,y)

≠ 1

end

Algorytm porównawczy Jordana

•

áR*HQLH U\VRZDQ\ áXN RNU JX ] RNWDQWX QU OXE

'OD WDNLHJR áXNX ND*G\ NROHMQ\ SLNVHO U\VRZDQHJR RGFLQND MHVW VVLDGHP
poprzedniego w kierunku

Ï, Ñ albo Í.

narysowany

piksel

ostatnio

trzy

piksele

kandydaci

áXN LGHDOQ\

Rys. Kryterium wyboru

kolejnego piksela dla

UR]ZD*DQHJR SU]\SDGNX
rysowany jest ten piksel,

GOD NWyUHJR ZDUWRü

EH]Z]JO GQD ] ZDUWRFL
funkcji F(x,y)=x2+y2-r2

Z URGNX WHJR SLNVHOD MHVW
najmniejsza.

•

3U]\MPLMP\ *H RVWDWQLR QDU\VRZDQ\ SLNVHO PD ZVSyáU] GQH xi, yi.

:yZF]DV ZVSyáU] GQH NROHMQHJR SLNVHOD PRJ Z\QLHü

xi+1:= xi - 1
yi+1:= yi

przy wyborze lewego piksela kandydata,

xi+1:= xi
yi+1:= yi +1

przy wyborze górnego piksela kandydata,

xi+1:= xi - 1
yi+1:= yi +1

przy wyborze lewego górnego piksela kandydata.

•

Oznaczenia:

f := F(xi,yi),

F(x0,y0) = F(xs,ys) = 0,

f1 := F(xi-1,yi) = f -2*xi +1,
f2 := F(xi,yi+1) = f +2*yi +1,
f3 := F(xi-1,yi+1) = f -2*xi +2*yi +2.

•

|f1|<|f2| & |f1|<|f3| ⇒ wybór lewego piksela kandydata,
|f2|<|f1| & |f2|<|f3| ⇒ wybór górnego piksela kandydata,
|f3|<|f1| & |f3|<|f2| ⇒ wybór lewego górnego piksela kandydata,
|f1|<|f2| & |f1|=|f3| ⇒ wybór lewego lub lewego górnego piksela,
|f2|<|f1| & |f2|=|f3| ⇒ wybór górnego lub lewego górnego piksela,

w al

JRU\WPLH SU]\M WR Z\EyU OHZHJR JyUQHJR

•

3RQLHZD* f2 ≥ f3 ≥ f1 ZL F
|f1|<|f2| & |f1|<|f3| ⇔ |f1|<|f3| ⇒

wybór lewego piksela kandydata,

|f2|<|f1| & |f2|<|f3| ⇔ |f2|<|f3| ⇒

wybór górnego piksela kandydata,

Z SR]RVWDá\FK SU]\SDGNDFK Z\EyU OHZHJR JyUQHJR SLNVHOD NDQG\GDWD

parametry procedury: x, y, xe, ye, xc, yc:integer;

x := xs-xc, y := ys-yc,

zmienne procedury: f1, f2, f3:integer;

xe := xe-xc, ye := ye-yc,

dla oktantu nr 1 lub 2:

xc := xc, yc := yc.

if StartOctant(x,y,xe,ye) in [1, 2] then

begin

f1 := -2*x+1;
repeat

plot(x+xc, y+yc);
f3 := f1+2*y+1;

f2 := f3+2*x-1;

if |f1| < |f3| then begin x := x-1; f1 := f1-2*x+1 end
else if |f2| < |f3| then begin y := y+1; f1 := f2-2*x+1 end
else begin x := x-1; y := y+1; f1 := f3-2*x+1 end

until not (Octant(x,y) in [1, 2])

end

•

3RQLHZD* f2 ≥ f3 ≥ f1 ZL F
|f1|<|f3| ⇔ -f1<f3 ⇒ wybór lewego piksela kandydata,
|f2|<|f3| ⇔ f2<-f3 ⇒ wybór górnego piksela kandydata,

Z SR]RVWDá\FK SU]\SDGNDFK Z\EyU OHZHJR JyUQHJR SLNVHOD NDQG\GDWD

parametry procedury: x, y, xe, ye, xc, yc:integer;

x := xs-xc, y := ys-yc,

zmienne procedury: f1, f2, f3:integer;

xe := xe-xc, ye := ye-yc,

dla oktantu nr 1 lub 2:

xc := xc, yc := yc.

if StartOctant(x,y,xe,ye) in [1, 2] then

begin

f1 := -2*x+1;
repeat

plot(x+xc, y+yc);
f3 := f1+2*y+1;

f2 := f3+2*x-1;

if f3 < -f1 then begin y := y+1; f1 := f3 end;
if -f3 < f2 then begin x := x-1; f1 := f1-2*x+1 end

until not (Octant(x,y) in [1, 2])

end

2NUJ

•

$E\ QDU\VRZDü SHáHQ RNUJ R URGNX xc,yc) i
promieniu r

Z\VWDUF]\ GRNRQDü REOLF]H MHG\QLH GOD

jednego oktantu (np. nr 1). Otrzymane dla tego

RNWDQWX ZVSyáU] GQH x, y SR]ZDODM Z\]QDF]\ü

SLNVHOH RNU JX ]H ZV]\VWNLFK RPLX RNWDQWyZ (x,y),
(y,x), (-y,x), (-x,y), (-x,-y), (-y,-x), (y,-x), (x,-y).

Elipsa

•

$E\ QDU\VRZDü SHáQ HOLSV R URGNX xc,yc) i

SyáRVLDFK p i q Z\VWDUF]\ GRNRQDü REOLF]H GOD

MHGQHM üZLDUWNL F]\OL GOD GZyFK RNWDQWyZ QS QU

L 2WU]\PDQH GOD WHM üZLDUWNL ZVSyáU] GQH x,
y

SR]ZDODM Z\]QDF]\ü SLNVHOH HOLSV\ ]H

ZV]\VWNLFK üZLDUWHN (x,y), (-x,y), (-x,-y), (x,-y).

3U]\NáDGRZ\ DOJRU\WP U\VRZDQLD HOLSV\ DOJRU\WP .DSSHOD

procedure Ellipse(xc, yc, p, q: integer);
var x, y: integer; pp, qq, pp2, qq2, f, fx, fy: longint;
begin

x := p;

y := 0;

pp := p*p;

qq := q*q;

pp2 := 2*pp;

qq2 := 2*qq;

f := pp - p*qq + qq div 4;

fx := qq2*p;

fy := 0;

while fx > fy do

{oktant nr 1 (oraz nr 4, 5, 8)}

begin

plot(x+xc, y+yc);

plot(-x+xc, y+yc);

plot(-x+xc, -y+yc); plot(x+xc, -y+yc);
y := y+1;

fy := fy+pp2;

if f < 0 then f := f+fy+pp
else begin x := x-1; fx := fx-qq2; f := f-fx+fy+pp end

end;

f := f - (fx+fy) div 2 + qq - pp - (qq-pp) div 4;
repeat

{oktant nr 2 (oraz nr 3, 6, 7)}

plot(x+xc, y+yc);

plot(-x+xc, y+yc);

plot(-x+xc, -y+yc); plot(x+xc, -y+yc);
x := x-1;

fx := fx-qq2;

if f > 0 then f := f-fx+qq
else begin y := y+1; fy := fy+pp2; f := f-fx+fy+qq end

until x < 0

end

Znajdowanie konturu

•

Konturem danego zbioru pikseli nazywamy zbiór wszystkich pikseli

QDOH*F\FK GR WHJR ]ELRUX L PDMF\FK SU]\QDMPQLHM MHGQHJR EVVLDGD QLH

QDOH*FHJR GR WHJR ]ELRUX

•

Znajdowanie wszystkich konturów dowolnego zbioru pikseli:
procedura AllContourTracing.

:\V]XNDQLH VSRUyG ZV]\VWNLFK SLNVHOL ]ELRUX W\FK NWyUH PDM

SU]\QDMPQLHM MHGQHJR EVVLDGD QLH QDOH*FHJR GR WHJR ]ELRUX

•

Znajdowanie pojedynczego konturu spójnego podzbioru zbioru pikseli:
procedura ContourTracing.

6WRSQLRZH Z\V]XNLZDQLH SRF]ZV]\ RG ZVND]DQHJR SLNVHOD SLNVHOL

NRQWXUX SRSU]H] DQDOL] VVLHG]WZD NROHMQR ]QDMGRZDQ\FK SLNVHOL NRQWXUX

piksel

konturu

piksel

spoza

zbioru

5\V 3U]\NáDGRZ\ ]ELyU

pikseli i jego kontur.

5\V .ROHMQRü SU]HJOGDQLD VVLDGyZ SLNVHOD

NRQWXUX Z FHOX ]QDOH]LHQLD QDVW SQHJR
piksela konturu.

{ var pixel: array[minx..maxx, miny..maxy] of (empty, interior, contour); }

procedure AllContourTracing;
var x,y: coordinate;
begin

for x:=minx to maxx do

for y:=miny to maxy do

if pixel[x,y]

HPSW\ then

if (pixel[x–1,y]=empty) or

(pixel[x+1,y]=empty) or
(pixel[x,y–1]=empty) or
(pixel[x,y+1]=empty) then pixel[x,y]:=contour

end;

procedure neighbour(var nx,ny:coordinate; x,y:coordinate; s:direction);
begin

case s of

0: begin nx:=x+1; ny:=y

end;

1: begin nx:=x+1; ny:=y–1 end;
2: begin nx:=x;

ny:=y–1 end;

3: begin nx:=x–1; ny:=y–1 end;
4: begin nx:=x–1; ny:=y

end;

5: begin nx:=x–1; ny:=y+1 end;
6: begin nx:=x;

ny:=y+1 end;

7: begin nx:=x+1; ny:=y+1 end

end

end;

{ var pixel: array[minx..maxx, miny..maxy] of (empty, interior, contour); }

procedure ContourTracing(bx,by:coordinate; bs:direction);
varx,y,nx,ny: coordinate;

s: direction;

begin

^ NRQWUROD Z\PDJD VWDZLDQ\FK SU]HG GDQ\PL SRF]WNRZ\PL `
if pixel[bx,by]

LQWHULRU then exit; { punkt (bx,by QLH QDOH*\ GR ]ELRUX `

bs:= bs mod 8 - bs mod 2;
neighbour(nx,ny,bx,by,bs);
if pixel[nx,ny]

HPSW\ then exit ^ VVLDG SXQNWX bx,by QDOH*\ GR ]ELRUX `

^ Z\]QDF]HQLH NRFRZHJR NLHUXQNX EVVLDGD SR REHMFLX NRQWXUX `
s:=bs;
repeat

bs:= (bs+7) mod 8;
if bs=s then

begin

pixel[bx,by]:=contour;
exit

^ QLH PD VVLDGyZ QDOH*F\FK GR ]ELRUX ]ELyU MHGQRSXQNWRZ\ `

end;

neighbour(nx,ny,bx,by,bs)

until pixel[nx,ny]

HPSW\

if odd(bs) then bs:= (bs+1) mod 8 else bs:= (bs+2) mod 8;

{ znajdowanie konturu }
x:=bx; y:=by;
repeat

pixel[x,y]:=contour;
repeat

s:= (s+1) mod 8;
neighbour(nx,ny,x,y,s)

until pixel[nx,ny]

HPSW\

x:=nx; y:=ny;
if odd(s) then s:= (s+5) mod 8 else s:= (s+6) mod 8

until (x=bx) and (y=by) and (s=bs)

end;

:\SHáQLDQLH NRQWXUX

•

0HWRG\ Z\SHáQLDQLD NRQWXUX

•

0HWRGD Z\SHáQLDQLD NRQWXUX ] NRQWURO SDU]\VWRFL -

Z\SHáQLDQLH ZV]\VWNLFK NRQWXUyZ SURFHGXUD $OO&RQWRXU)LOOLQJ

3U]HJOGDQLH ZV]\VWNLFK SLNVHOL REUD]X NROHMQ\PL OLQLDmi poziomymi.

:\NU\FLH QLHSDU]\VWHM OLF]E\ SU]HFL ü NRQWXUX ] ]DGDQ OLQL SR]LRP

QD OHZR RG GDQHJR SLNVHOD R]QDF]D *H QDOH*\ RQ GR ZQ WU]D ]ELRUX

$E\ Z\NU\ü IUDJPHQW\ NRQWXUX VW\F]QH GR OLQLL SR]LRP\FK QDOH*\ GOD

ND*GHM OLQLL SR]LRPHM SU]HDQDOL]RZDü OLQLH GR QLHM VVLHGQLH -HOL Z

MHGQHM ] OLQLL VVLHGQLFK JyUQHM DOER GROQHM Z VVLHG]WZLH Z\NU\WHJR

IUDJPHQWX NRQWXUX QLH PD *DGQHJR SLNVHOD NRQWXUX WR MHVW WR IUDJPHQW
konturu styczny do linii poziomej.

5\V 3U]\NáDGRZ\

kontur. Fragmenty
konturu styczne do
linii poziomych nie

SRZLQQ\ E\ü
traktowane jako

SU]HFL FLD NRQWXUX ]
liniami poziomymi.

5\V 3U]\NáDGRZ\ NRQWXU

dla którego
procedura
AllContourFilling

]DV\JQDOL]XMH EáG

'RSLHUR XVXQL FLH
z tego konturu
pikseli oznaczonych

NU]\*\NDPL

XPR*OLZL

SUDZLGáRZH Z\NR
nanie tej procedury.

{ var pixel: array[minx..maxx, miny..maxy] of (empty, interior, contour); }

procedure AllContourFilling;
var x,y: coordinate; above,below: integer; oddintsect: Boolean;
begin

for y:=miny to maxy do

begin

oddintsect:=false;
x:=minx;
while x

maxx do

if pixel[x,y]

FRQWRXU

then

begin

if oddintsect then pixel[x,y]:=interior;
x:=x+1

end

else

begin

if (pixel[x-1,y-1]=contour) or (pixel[x,y-1]=contour)

then above:=1 else above:=0;

if (pixel[x-1,y+1]=contour) or (pixel[x,y+1]=contour)

then below:=1 else below:=0;

repeat

if (pixel[x+1,y-1]=contour) and (pixel[x,y-1]

FRQWRXU

then above:=above+1;

if (pixel[x+1,y+1]=contour) and (pixel[x,y+1]

FRQWRXU

then below:=below+1;

x:=x+1;

until (pixel[x,y]

FRQWRXU or (xmaxx);

if odd(above) and odd(below) then oddintsect:= not oddintsect;
if odd(above)

RGGbelow) then HUURU ^ Eá GQD V\WXDFMD `

end

end;

•

0HWRGD Z\SHáQLDQLD NRQWXUX SU]H] VSyMQRü (przez sianie) -

Z\SHáQLDQLH ]DGDQHJR NRQWXUX SURFHGXU\ )LOO L &RQWRXU)LOOLQJ

3U]HJOGDQLH ZH ZV]\VWNLFK NLHUXQNDFK SRF]ZV]\ RG ]DGDQHJR SLNVHOD

W]Z ]LDUQD NROHMQ\FK EVVLDGyZ D* GR RVLJQL FLD NRQWXUX

procedure Fill(x, y: Integer); { x, y

ZVSyáU] GQH ]LDUQD `

begin

if pixel[x,y] = empty then

begin

pixel[x,y] := interior;
Fill(x+1,y); Fill(x,y-1); Fill(x-1,y); Fill(x,y+1)

end

3URFHGXUD )LOO QLH MHVW HIHNW\ZQD JG\* GOD ND*GHJR SLNVHOD MHVW

Z\NRQ\ZDQH RVREQH Z\ZRáDQLH SU]H] FR V]\ENR URQLH SR]LRP

UHNXUHQFML SURZDG]F Z SUDNW\FH GR SU]HSHáQLHQLD VWRVX

2 ZLHOH U]DG]LHM GR UHNXUHQFML RGZRáXMH VL SURFHGXUD &RQWRXU)LOOLQJ

10 11

5\V :\SHáQLHQLH

SU]\NáDGRZHJR NRQ

WXUX Z\ZRáDQLHP
procedury Fill(x,y)

ELDáH OLF]E\

R]QDF]DM NROHMQRü
czarne cyfry - poziom
rekurencji).

5\V :\SHáQLHQLH

SU]\NáDGRZHJR NRQ

WXUX Z\ZRáDQLHP
procedury
ContourFilling(x,y)

ELDáH OLF]E\

R]QDF]DM NROHMQRü
czarne cyfry - poziom
rekurencji).

{ var pixel: array[minx..maxx, miny..maxy] of (empty, interior, contour); }

procedure ContourFilling(x,y: coordinate);

procedure filling(x,y: coordinate; dy: integer);
var ax,ay,bx,by: coordinate; afind,bfind: Boolean;
begin

if pixel[x,y]=empty then

repeat

ax:=x; ay:=y+dy;
bx:=x; by:=y-dy;
while pixel[ax,ay]=empty do ax:=ax-1;
if ax

x then ax:=ax+1;

while pixel[bx,by]=empty do bx:=bx-1;
if bx

x then bx:=bx+1;

afind:=pixel[ax,ay]=empty;
bfind:=pixel[bx,by]=empty;
pixel[x,y]:=interior;
x:=x+1;
while pixel[x,y]=empty do

begin pixel[x,y]:=interior;

if (pixel[x,ay]=empty) and (pixel[x-1,ay]

HPSW\

then

begin if afind

then filling(ax,ay,dy)
else afind:=true;

ax:=x

end;

if (pixel[x,by]=empty) and (pixel[x-1,by]

HPSW\

then

begin if bfind

then filling(bx,by,-dy)
else bfind:=true;

bx:=x

end;

x:=x+1

end;

if afind and bfind then filling(ax,ay,dy);
if bfind

then begin x:=bx; y:=by; dy:=-dy end
else begin x:=ax; y:=ay end

until not (afind or bfind)

end;

begin

if pixel[x,y]

HPSW\ then exit;

repeat x:=x-1 until pixel[x,y]

HPSW\

x:=x+1;
filling(x,y,1)

end;

FLHQLDQLH NV]WDáWyZ

•

1D SáDV]F]\(QLH HXNOLGHVRZHM
Definicja:

•

Szkieletem Sk

Ω zbioru Ω QD]\ZDP\ ]ELyU SXQNWyZ R QDVW SXMFHM

ZáDVQRFL

∈

⇔

∈

∃ ∈

≠
=

∀ ∈

≥













Ω

Ω
Ω

Ω

•

1D SáDV]F]\(QLH G\VNUHWQHM
Definicja:

•

Piksel konturu nazywamy powtarzalnym

JG\ VSHáQLD RQ SU]\QDMPQLHM

jeden z trzech warunków:

Z\VW SXMH FR QDMPQLHM GZXNURWQLH Z GURJDFK RSLVXMF\FK NRQWXU

QLH PD VVLDGyZ ZHZQWU] REV]DUX RWRF]RQHJR NRQWXUHP

PD FR QDMPQLHM MHGQHJR EVVLDGD ] NRQWXUX NWyU\ QLH VVLDGXMH ] QLP

Z FLJX SLNVHOL VWDQRZLF\P GURJ RSLVXMF NRQWXU

Definicja:

•

Szkieletem danego zbioru pikseli jest zbiór pikseli, otrzymany w wyniku

F\NOLF]QHJR RGU]XFDQLD SLNVHOL NRQWXUX QLH E GF\FK SLNVHODPL SRZWDU]DOQ\PL

•

Szkieletem jest zatem zbiór otrzymany w wyniku wykonania algorytmu:

repeat

]QDOH]LHQLH NRQWXUX L XVXQL FLH ]H ]ELRUX W\FK SLNVHOL NRQWXUX

NWyUH QLH V SLNVHODPL SRZWDU]DOQ\PL

until

QLH XVXQL WR *DGQHJR SLNVHOD

•

:DUXQNL Z\VW SXMFH Z GHILQLFML SLNVHOL SRZWDU]DOQ\FK NRQWXUX PR*QD

RSLVDü Z]RUFDPL VVLHG]WZ

A A A

5\V :]RUFH RGSRZLDGDMFH

A A C

A X

pierwszemu (

Å) i trzeciemu

X K

B B B

(

Æ) warunkowi.

B B C

180

270

JG\ QLH V VSHáQLRQH SR]RVWDáH ZDUXQNL

180

270

•

X - piksel powtarzalny konturu;

K - piksel konturu;

•

A, B, C - grupa pik

VHOL R]QDF]RQ\FK W VDP OLWHU PD W ZáDVQRü L* FR

QDMPQLHM MHGHQ ] QLFK QDOH*\ GR ]ELRUX MHOL RED SLNVHOH & QDOH* GR

]ELRUX RVWDWQL Z]RU]HF WR SU]\QDOH*QRü SLNVHOL $ L % MHVW GRZROQD

•

%DGDQLH SRZWDU]DOQRFL Z\Paga zatem jedynie sprawdzenia

QDMEOL*V]HJR VVLHG]WZD SLNVHOD NRQWXUX

•

3RGHMFLH ZJ GHILQLFML DOJRU\WP FLHQLDQLD SURFHGXUD 'HI7KLQQLQJ

•

3RGHMFLH XSURV]F]RQH DOJRU\WP NODV\F]Q\ FLeniania: procedura Thinning.

{ var pixel: array[minx..maxx, miny..maxy] of (empty, interior, contour, skeleton); }

procedure DefThinning;

^ FLHQLDQLH QD SRGVWDZLH GHILQLFML V]NLHOHWX `

var x,y,nx,ny: coordinate; e,i,m: byte; s: direction; finish, pattern: Boolean;
begin

repeat

finish:=true;
AllContourTracing;
for y:=miny to maxy do for x:=minx to maxx do if pixel[x,y]=contour then

begin

e:=0; i:=0; m:=0;
for s:=0 to 7 do

{ konstrukcja wzorców }

begin

e:=e shl 1; i:=i shl 1; m:=m shl 1;
neighbour(nx,ny,x,y,s);
if pixel[nx,ny]=empty

then e:=e or 1
else

begin i:=i or 1;

if pixel[nx,ny]

LQWHULRU then m:=m or 1

end

end;

{

Ë NRQWUROD ZDUXQNX SRZWDU]DOQRFL `

pattern:=(i=m) or {

È NRQWUROD ZDUXQNX SRZWDU]DOQRFL `

(((i and $70)

and ((i and $07) and ((e and $88)=$88)) or

(((i and $1C)

and ((i and $C1) and ((e and $22)=$22)) or

(((i and $01)

and ((i and $7C) and ((e and $82)=$82)) or

(((i and $40)

and ((i and $1F) and ((e and $A0)=$A0)) or

(((i and $10)

and ((i and $C7) and ((e and $28)=$28)) or

(((i and $04)

and ((i and $F1) and ((e and $0A)=$0A)) or

{

È NRQWUROD ZDUXQNX SRZWDU]DOQRFL `

(((i and $41)

and ((m and $80) and ((e and $08) and

(((e and $41)=0) or (((i and $30)

and ((i and $06) or

(((i and $05)

and ((m and $02) and ((e and $20) and

(((e and $05)=0) or (((i and $C0)

and ((i and $18) or

(((i and $14)

and ((m and $08) and ((e and $80) and

(((e and $14)=0) or (((i and $03)

and ((i and $60) or

(((i and $50)

and ((m and $20) and ((e and $02) and

(((e and $50)=0) or (((i and $0C)

and ((i and $81)

if pattern then pixel[x,y]:=skeleton else finish:=false

end;

for y:=miny to maxy do for x:=minx to maxx do

if pixel[x,y]=contour then pixel[x,y]:=empty
else if not finish and (pixel[x,y]=skeleton) then pixel[x,y]:=interior

until finish;
for y:=miny to maxy do for x:=minx to maxx do

if pixel[x,y]=interior then pixel[x,y]:=skeleton

end;

{ var pixel: array[minx..maxx, miny..maxy] of (empty, interior, contour, skeleton); }
procedure Thinning;
var x,y,nx,ny: coordinate; q,r,s: direction; finish, pattern, first, second: Boolean;
begin

repeat

finish:=true; s:=0;
repeat

for y:=miny to maxy do for x:=minx to maxx do

if pixel[x,y]=interior then

begin neighbour(nx,ny,x,y,s);

if pixel[nx,ny]=empty then

begin pattern:=false;

r:=(s+2) mod 8;
repeat

neighbour(nx,ny,x,y,r);
if pixel[nx,ny]=empty then

begin first:=false; second:=false;

q:=(s+1) mod 8;
repeat

neighbour(nx,ny,x,y,q);
if pixel[nx,ny]

HPSW\ then first:=true;

q:=(q+1) mod 8

until (q=r) or first;
q:=(r+1) mod 8;
repeat

neighbour(nx,ny,x,y,q);
if pixel[nx,ny]

HPSW\ then second:=true;

q:=(q+1) mod 8

until (q=s) or second;
pattern:= first and second

end;

r:=(r+2) mod 8

until (r=s) or pattern;
if pattern then pixel[x,y]:=skeleton

else pixel[x,y]:=contour

end

end;

for y:=miny to maxy do for x:=minx to maxx do

if pixel[x,y]=contour then

begin pixel[x,y]:=empty;

finish:=false

end;

s:=(s+2) mod 8

until s=0

until finish

end;

123

3 3

5\V 3U]\NáDGRZD ILJXUD L SLNVHOH MHM

konturu z zaznaczonymi
pikselami powtarzalnymi.

&\IU\ ZVND]XM ZDUXQHN
definicji, z którego wynika

SRZWDU]DOQRü SLNVHOD NRQWXUX

- piksel figury

- piksel konturu

- piksel powtarzalny konturu

1 1 1
1 2 2 1

1 2

3 3

2 1

1 2

2 1

2 2

1 2

2 1

2 2

1 2

3 3

2 1 1 1 1

2 3

2 1

5\V 3U]\NáDGRZD ILJXUD L HIHNW MHM

FLHQLHQLD V]NLHOHW MDNR ]ELyU
otrzymany w wyniku cyklicznego
odrzucania punktów konturu nie

E GF\FK SXQNWDPL SRZWDU]DO
nymi (wg definicji szkieletu) –
procedura DefThinning. Cyfry

ZVND]XM HWDS\ SRGF]DV NWyU\FK

GDQ\ SLNVHO QDOH*\ GR NRQWXUX

1 2

2 2 2 2 2 2 3

2 1

2 2

1 1 1 1 1 1 1

2 2

- piksele figury

2 2

1 1 1

- piksele szkieletu

3 4 1
3 5 4 1

3 4

5 4 1

3 4

5 1

2 2 3

4 1

2 1

2 3

4 1

3 4

2 3

5 1

3 4

5 4 4 4 4 4 4

4 1

5\V 3U]\NáDGRZD ILJXUD L HIHNW MHM

FLHQLHQLD V]NLHOHW MDNR ]ELyU
otrzymany w wyniku wykonania

DOJRU\WPX NODV\F]QHJR FLHQLDQLD

D ZL F QLH ZJ GHILQLFML V]NLHOHWX
– procedura Thinning. Cyfry

ZVND]XM NROHMQRü DQDOL]\
pikseli jako konturu.

6 6 6 6 6 6 6 6

5 1

2 2 2 2 2 2 2 2 3

3 4

3 5 1

- piksele figury

3 5 2 1

2 3 4 1

2 2 1

- piksele szkieletu

Filtracja

•

Filtry liniowe -

RSLV\ZDQH PDFLHU]DPL RNUHODMF\PL ZSá\Z SLNVHOD L MHJR

VVLDGyZ QD QRZ ZDUWRü F]\OL NRORU SLNVHOD

•

)LOWU\ GROQRSU]HSXVWRZH ± XVXZDQLH V]F]HJyáyZ UR]P\ZDQLH REUD]X

G 1 1 1 G

G 1 2 1 G

G 1 1 1 G

•

G 1 1 1 G

G 1 2 1 G

G 2 4 2 G

G 1 0 1 G

G 1 1 1 G

G 1 2 1 G

G 1 1 1 G

•

Filtry górnoprzepustowe – w

\NU\ZDQLH NUDZ G]L Z\RVWU]DQLH REUD]X

G 0 0 0 G

•

gradient Robertsa

G -1 0 0 G

G 0 0 -1 G

G 0 1 0 G

G -1 -1 -1 G

G -1 0 1 G

•

maska Prewitta

G 0 0 0 G

G -1 0 1 G

G 1 1 1 G

G -1 0 1 G

G -1 -2 -1 G

G -1 0 1 G

G -2 -1 0 G

•

maska Sobela

G 0 0 0 G

G -2 0 2 G

G -1 0 1 G

G 1 2 1 G

G -1 0 1 G

G 0 1 2 G

G -1 -1 1 G

G -1 1 1 G

G -5 -5 3 G

•

wykrywanie

G -1 -2 1 G

G -5 0 3 G

QDUR*QLNyZ

G 1 1 1 G

G -1 1 1 G

G 3 3 3 G

G 0 -1 0 G

G -1 -1 -1 G

G 1 -2 1 G

•

laplasjan

G -1 4 -1 G

G -1 8 -1 G

G -2 4 -2 G

G 0 -1 0 G

G -1 -1 -1 G

G 1 -2 1 G

•

Filtry nieliniowe

•

NRPELQRZDQH Z\NU\ZDMFH NUDZ G]LH
(np. pierwiastek sumy kwadratów pionowej i poziomej maski Prewitta)

•

medianowy, maksymalny, minimalny

•

operacje logiczne

•

adaptacyjne

3U]HNV]WDáFHQLD PRUIRORJLF]QH

•

(UR]MD ± RGU]XFHQLH SLNVHOL ]ELRUX VVLDGXMF\FK ] SLNVHODPL spoza zbioru.

•

'\ODWDFMD ± GRGDQLH SLNVHOL VSR]D ]ELRUX VVLDGXMDF\FK ] SLNVHODPL ]ELRUX

3U]HNV]WDáFHQLD Z SU]HVWU]HQL GZXZ\PLDURZHM

•

8NáDG\ ZVSyáU] GQ\FK

•

GZXZ\PLDURZH NDUWH]MDVNL x,y i biegunowy r3

x r

y r

= cos

= sin

5\V 3UDZRVNU WQ\ L OHZRVNU WQ\ GZXZ\PLDURZ\ XNáDG ZVSyáU] GQ\FK

•

3RGVWDZRZH SU]HNV]WDáFHQLD OLQLRZH Z SU]HVWU]HQL
dwuwymiarowej:

•

SU]HVXQL FLH WUDQVODFMD R ZHNWRU b:

p' = I * p + b

gdzie













•

REUyW ZRNyá SXQNWX q R NW 3

p' = D * p + (I - D) * q

gdzie













−

cos

sin

cos

•

MHGQRNáDGQRü R VNDOL k Z]JO GHP SXQNWX q: p' = k * I * p + (1 - k) * q

•

V\PHWULD URGNRZD Z]JO GHP SXQNWX q:

p' = -I * p + 2 * q

•

V\PHWULD RVLRZD Z]JO GHP SURVWHM q

, q

p' = G * p + h













−

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(





































−

czym

przy

)

(

)

(

)

(

)

(

;

dla osi x=a:























−

; dla osi y=b:

























−

























3U]HNV]WDáFHQLD Z SU]HVWU]HQL WUyMZ\PLDURZHM

•

8NáDG\ ZVSyáU] GQ\FK

•

WUyMZ\PLDURZH NDUWH]MDVNL x,y,z; sferyczny R3, L F\OLQGU\F]Q\ r3z.

x r

y r

= cos

= sin

x R

= cos sin

y R

= sin sin

z R

= cos

Θ
Θ

5\V 3UDZRVNU WQ\ L OHZRVNU WQ\ WUyMZ\PLDURZ\ XNáDG ZVSyáU] GQ\FK

•

3RGVWDZRZH SU]HNV]WDáFHQLD OLQLRZH Z SU]HVWU]HQL WUyMZ\PLDURZHM

•

SU]HVXQL FLH WUDQVODFMD R ZHNWRU b:

p' = I * p + b

gdzie





































•

REUyW ZRNyá SXQNWX q:

p' = D * p + (I - D) * q

gdzie













•

MHGQRNáDGQRü R VNDOL k Z]JO GHP SXQNWX q: p' = k * I * p + (1 - k) * q

•

U]XW RUWRJRQDOQ\ QD SáDV]F]\]Q z=a:

p' = F * p + h

gdzie





































•

3U]\NáDG SU]HNV]WDáFHQLD QLHOLQLRZHJR Z SU]HVWU]HQL WUyMZ\PLDURZHM

•

rzut perspektywiczny z punktu q

QD SáDV]F]\]Q z=a:

przy czym: d

FRV .

NW SRPL G]\ REUD]HP RVL u L RVL v









−

)

(

3RáR*HQLH RELHNWyZ JHRPHWU\F]Q\FK Z]JO GHP VLHELH

•

(x,y) := (y

-y

)*x - (x

-x

)*y + x

- x

:= (x

•

UyZQDQLH SURVWHM SU]HFKRG]FHM SU]H] SXQNW\ P

, P

: F

(x,y) = 0.

•

GOD SXQNWyZ SR SUDZHM VWURQLH SURVWHM SDWU]F ] SXQNWX P

Z VWURQ SXQNWX

): F

(x,y) < 0, dla punktów po lewej stronie: F

(x,y) > 0.

•

UyZQDQLH SURVWHM SURVWRSDGáHM SU]HFKRG]FHM SU]H] SXQNW P

-x

)*x + (y

-y

)*y - (x

-x

)*x

- (y

-y

)*y

= 0.

•

dwa odcinki P

i P

SU]HFLQDM VL ⇔

sgn(F

))

≠ sgn(F

)) & sgn(F

))

≠ sgn(F

)).

•

SRáR*HQLH SXQNWX Q = (x,y Z]JO GHP ZLHORNWD

•

SURVWRNW R ERNDFK UyZQROHJá\FK GR RVL x

min

≤x≤x

max

& y

min

≤y≤y

max

•

ZLHORNW Z\SXNá\ R ZLHU]FKRáNDFK XSRU]GNRZDQ\FK ]JRGQLH ] UXFKHP
wskazówek zegara P

, P

,... P

∀i∈{1,2,..n} F

i(i mod n + 1)

(x,y) < 0.

•

ZLHORNW GRZROQ\ R ZLHU]FKRáNDFK XSRU]GNRZanych zgodnie z ruchem
wskazówek zegara P

, P

,... P

•

SRG]LDá QD ZLHORNW\ Z\SXNáH

•

NRQWUROD SDU]\VWRFL OLF]E\ SU]HFL ü GRZROQHM SyáSURVWHM Z\FKRG]FHM
z punktu Q

] ERNDPL ZLHORNWD

•

REOLF]HQLH VXP\ NWyZ σ := ∑

i=1..n

∠P

(i mod n + 1)

(

σ = 360°

⇔ Q QDOH*\ GR ZLHORNWD σ = 0° ⇔ Q QLH QDOH*\ GR ZLHORNWD

•

SRáR*HQLH RGFLQND Q

Z]JO GHP ZLHORNWD

•

SURVWRNW R ERNDFK UyZQROHJá\FK GR RVL

•

ZLHORNW Z\SXNá\ FR QDMZ\*HM GZD SU]HFL FLD ] ERNDPL ZLHORNWD

•

SRáR*HQLH ZLHORNWD Z]JO GHP LQQHJR ZLHORNWD F] ü ZVSyOQD

Definicja:

•

Punkt P=(x

)

SU]HVáDQLD RGFLQHN SURVW l MHOL SyáSURVWD SR]LRPD

Z\FKRG]FD ] P Z OHZ VWURQ W]Q y = y

, x < x

) przetnie l.

Definicja:

•

Odcinek a

SU]HVáDQLD odcinek b MHOL FR QDMPQLHM MHGHQ ] SXQNWyZ RGFLQND

SU]HVáDQLD RGFLQHN b L RED RGFLQNL VL QLH SU]HFLQDM

Rys. Ilustracja

definicji

SU]HVáDQLDQLD

Obrazy trójwymiarowe

•

5HSUH]HQWDFMD RELHNWyZ JUDILF]Q\FK EU\á L ILJXU

•

DQDOLW\F]QD UyZQRFL QLHUyZQRFL QS ≤x≤2 &
0

≤y≤2 & 0≤z≤2 ∨ 0≤x≤1 & 0≤y≤1 & 2≤z≤3.

•

szkieletow

D EU\áD ZLHORFLDQ ILJXUD ZLHORNW

QS ZLHU]FKRáNL $ % &
D(2,0,0), E(1,1,2), F(0,1,2), G(0,2,2), H(2,2,2), I(2,0,2), J(1,0,2),

. / 0 1 FLDQ\ $'&% &',+ %&+*
EFGHIJ, EJNM, EMLF, KLMN, ABGFLK, AKNJID.

•

konstruktywna (ang. constructive solid geometry) (obiekty elementarne +

RSHUDFMH VNáDGDQLD QS SU]HVNDORZDQ\ R MHGQRNáDGQRü V]HFLDQ
jednostkowy (tzn. 0

≤x≤1 & 0≤y≤1 & 0≤z≤1) ∪ SU]HVXQL W\ WUDQVODFMD

R ZHNWRU V]HFLDQ MHGQRVWNRZ\

•

]D SRPRF GU]HZD yVHPNRZHJR EU\á\ OXE
czwórkowego (figury); np. dla 0

≤x≤4 & 0≤y≤4

& 0

≤z≤4: (0,0,0,0,(0,0,0,0,0,0,1,0),0,1,0).

•

:LGRF]QRü FLDQ SRZLHU]FKQLH ]DVáRQL WH

•

DOJRU\WP\ RSHUXMFH QD SU]HVWU]HQL GDQ\FK

•

analiza zwrotów wektorów normalnych dla wie

ORFLDQX Z\SXNáHJR

•

NRQWUROD XSRU]GNRZDQLD ZLHU]FKRáNyZ GOD ZLHORFLDQX Z\SXNáHJR

•

algorytm Ricciego;

•

algorytm Appela;

•

DOJRU\WP\ RSHUXMFH QD SU]HVWU]HQL REUD]X

•

DOJRU\WP GOD SRZLHU]FKQL ]DGDQHM IXQNFM GZyFK ]PLHQQ\FK

•

DOJRU\WP ] EXIRUHP Já ERNRFL

•

DOJRU\WP SU]HJOGDQLD OLQLDPL SR]LRP\PL

5\V 3U]HJOGDQLH U]XWyZ FLDQ OLQLDPL

poziomymi.

•

DOJRU\WP ] X*\FLHP GU]HZD F]ZyUNRZHJR ÄG]LHO L ]Z\FL *DM´

5\V 0R*OLZH SRáR*HQLD U]XWX FLDQ\ Z]JO GHP SURVWRNWQHJR NDGUX

5\V 3U]HVáDQLDQLH

FLDQ QLH MHVW

UHODFM SU]HFKR

GQL D E DQL

DQW\V\PHWU\F]Q
(c).

(OLPLQDFMD SRZLHU]FKQL ]DVáRQL W\FK ] X*\FLHP GU]HZD F]ZyUNRZHJR

5\V 0R*OLZH SRáR*HQLD SURVWRNWQHJR NDGUX Z]JO GHP U]XWX FLDQ\

•

=DáR*HQLD

•

FLDQ\ SRVRUWRZDQH RG QDMEOL*V]HM GR QDMGDOV]HM Z WDEOLF\ face:
const n

^ PDNV\PDOQD OLF]ED FLDQ `

type

SRO\JRQV ^ RSLV NV]WDáWX FLDQ\ `

type faces = array [1..n] of record colour:integer; polygon:polygons end;
var background

LQWHJHU ^ NRORU WáD `

var face: faces;

•

7\S Z\OLF]HQLRZ\ PR*OLZH SRáR*HQLD NDGUX Z]JO GHP U]XWX FLDQ\
type location = (outside {a}, inside {b}, other {c,d});

•

Funkc

MD VSUDZG]DMFD SRáR*HQLH NDGUX Z]JO GHP U]XWX FLDQ\

function Position(x1,y1,x2,y2: integer; var polygon: polygons): location;

•

3URFHGXUD Z\SHáQLDMFD NDGU GDQ\P NRORUHP
procedure Rectangle(x1, y1, x2, y2, colour: integer);

•

3URFHGXUD HOLPLQDFML SRZLHU]FKQL ]DVáRQL W\FK

procedure HiddenFace(x1, y1, x2, y2, first, last: integer; var face: faces);
var x, y, i: integer;
begin

if first < 1 then first := 1; if last > n then last := n;
for i := first to last do

case Position(x1, y1, x2, y2, face[i].polygon) of

outside: begin { nic nie rób } end;
inside:

begin { kadr w kolorze i

WHM FLDQ\ `

Rectangle(x1, y1, x2, y2, face[i].colour);
exit {procedure}

end;

other:

begin

^ GDOV]\ SRG]LDá `

x := (x1+x2) div 2; y := (y1+y2) div 2;
HiddenFace(x1, y1, x, y, i, last, face);
HiddenFace(x1, y+1, x, y2, i, last, face);
HiddenFace(x+1, y1, x2, y, i, last, face);
HiddenFace(x+1, y+1, x2, y2, i, last, face);
exit {procedure}

end

end; {case}

Rectangle(x1, y1, x2, y2, background)

end; {procedure}

Wyznaczanie cieni

Rys. Wyznaczanie cieni.

•

dwukrotne
rozstrzyganie
problemu

]DVáDQLDQLD

0RGHORZDQLH RZLHWOHQLD

•

(UyGáD ZLDWáD SXQNWRZH OLQLRZH SRZLHU]FKQLRZH

•

odbicia:

Io QDW *HQLH RZLHWOHQLD >O[@

Rys. Zjawisko odbicia.

n - wersor normalny do powierzchni
l - wersor kierunku padania promieni
z - wersor kierunku odbicia zwierciadlanego
e

ZHUVRU NLHUXQNX SRáR*HQLD REVHUZDWRUD

•

rozproszone:

kr*Io*FRV3 kr*Io*(n°l)

•

zwierciadlane:

kz*Io*cosm. kz*Io*(z°e)m

∈[1,200]

•

WáR RZLHWOHQLRZH

kt*Io

•

FDáNRZLWH QDW *HQLH ZLDWáD RGELMDQHJR
I = (kt + kr*(n°l) + kz*(z°e)m) * Io,

Eo ZLDWáRü *UyGáD ZLDWáD >FG@
r

RGOHJáRü RG (UyGáD ZLDWáD

&LHQLRZDQLH SRZLHU]FKQL EU\á ZLHORFLHQQ\FK

•

brak cieniowania

VWDáD LQWHQV\ZQRü RZLHWOHQLD FLDQ\

HIHNW 0DFKD VNRNL RZLHWOHQLD QD NUDZ G]LDFK

•

metoda Gourauda

LQWHUSRODFMD ZDUWRFL QDW *HQLD ZLDWáD RGELWHJR

•

Z ZLHU]FKRáNDFK ZLHORFLDQX ZHUVRU QRUPDOQ\ MHVW UHGQL

DU\WPHW\F]Q ZHUVRUyZ QRUPDOQ\FK FLDQ ]DZLHUDMF\FK ZLHU]FKRáHN

•

QD NUDZ G]LDFK OLQLRZD LQWHUSRODFMD QDW *HQLD QD SRGVWDZLH MHJR

ZDUWRFL Z ZLHU]FKRáNDFK E GF\FK NUDFDPL GDQHM NUDZ G]L

•

ZHZQWU] FLDQ\ OLQLRZD LQWHUSRODFMD QDW *HQLD QD SRGVWDZLH MHJR

ZDUWRFL Z QDMEOL*V]\FK ] ND*GHM VWURQ\ SXQNWDFK NUDZ G]L OH*F\FK QD
tej samej linii poziomej co dany punkt.

•

metoda Phonga - interpolacja wersorów normalnych;

•

Z ZLHU]FKRáNDFK ZLHORFLDQX ZHUVRU QRUPDOQ\ MHVW UHGQL

DU\WPHW\F]Q ZHUVRUyZ QRUPDOQ\FK FLDQ ]DZLHUDMF\FK ZLHU]FKRáHN

•

QD NUDZ G]LDFK OLQLRZD LQWHUSRODFMD ZHUVRUyZ QRUPDOQ\Fh na

SRGVWDZLH W\FK*H Z ZLHU]FKRáNDFK E GF\FK NUDFDPL GDQHM NUDZ G]L

•

ZHZQWU] FLDQ\ OLQLRZD LQWHUSRODFMD ZHUVRUyZ QRUPDOQ\FK QD

SRGVWDZLH W\FK*H Z QDMEOL*V]\FK ] ND*GHM VWURQ\ SXQNWDFK NUDZ G]L

OH*F\FK QD WHM VDPHM OLQLL SR]LRPHM FR GDQ\ SXQNW

•

OHG]HQLH SURPLHQL RGWZRU]HQLH GURJL ZV]\VWNLFK SURPLHQL ZLHWOQ\FK

SDGDMF\FK QD GDQ\ SLNVHO

ekran

(UyGáR

ZLDWáD

α ϕ ϕ

gdzie

Modelowanie krzywych i powierzchni

Modelowanie krzywych:

•

krzywe Béziera:
pi - punkty kontrolne.

•

ZáDVQRFL NU]\ZHM

•

NUDFH Z SXQNWDFK p

, p

0,n

(0) = p

, p

0,n

(1) = p

•

styczna w punkcie p

do odcinka p

0,n

(0) = n

-p

•

styczna w punkcie p

do odcinka p

n-1

: p'

0,n

(1) = n

-p

n-1

•

mie

FL VL Z XZ\SXNOHQLX SXQNWyZ NRQWUROQ\FK

•

VSHáQLD ]DOH*QRü p

0,n

(t) = (1-t)

0,n-1

(t) + t

1,n

(t).

(

)

(

dla

)

(

)

(

)

(

dla

)

(

)

(

)

(

dla

)

(

)

(

)

(

)

(

dla

)

(

)

(

)

(

)

(

)

(

Fergusona

)

(

teina

iany Berns

wielom

−













−













−













−

•

∑

•

wyznaczanie punktów krzywej:

•

algorytm de Casteljau:
for i := 0 to n do r

:= p

;

for j := 1 to n do

for i := 0 to n-j do r

:= r

+ t

i+1

- r

);

0,n

(t) := r

•

algorytm Hornera:

(t < 0,5)

l := 1; k := 1;
c := t / (1-t); s := p

;

for i := 1 to n do

begin l := l

(1-t); k := k

(n-i+1)/i; s := c

s + k

n-i

end;

0,n

(t) := l

•

algorytm Hornera:

(t > 0,5)

l := 1; k := 1;
c := (1-t) / t; s := p

;

for i := 1 to n do

begin l := l

t; k := k

(n-i+1)/i; s := c

s + k

end;

0,n

(t) := l

]

[

dla

)

(

)

(

∈

−













∑

0,n

(t) = (1-t)

0,n-1

(t) + t

1,n

(t)

∑













−













−

)

(

)

(

∑











 −









−

)

(

•

NU]\ZH VNOHMDQH NU]\ZH JL WH DQJ splines)

•

funkcja sklejana

IXQNFMD JL WD VWRSQLD p MHVW WR IXQNFMD SRNU\ZDMFD

VL SU]HG]LDáDPL ] Uy*Q\PL ZLHORPLDQDPL VWRSQLD p, przy czym funkcja
ta, jak i jej p

SLHUZV]\FK SRFKRGQ\FK V FLJáH

•

funkcje B-sklejane m

≤n, t

≤ t

≤...≤ t

≤ t

n+1

≤...≤ t

n+m+1

(

)

(

)

(

[

dla

[

dla

)

(

−







∉

∈

−

•

funkcje B-sklejane n

m,i

(i=0..n)

VWDQRZL ED] GOD IXQNFML
sklejanych stopnia m

RNUHORQ\FK Z SU]HG]LDOH
[t

, t

n+1

] i „sklejanych” dla

ZDUWRFL SDUDPHWUyZ t

m+1

,.., t

•

ZáDVQRFL

•

RJUDQLF]RQ\ L ]ZDUW\ QRQLN

•

ZDUWRFL QLHXMHPQH

•

unormowanie:

•

krzywe sklejane
krzywe opisane parametrycznie funkcjami sklejanymi, przy czym

ÄVNOHMHQLD´ ZLHORPLDQyZ QDVW SXM GOD W\FK VDP\FK ZDUWRFL SDUDPHWUX

•

krzywe B-sklejane: q

( )

[

m i

∈

∑

- punkty kontrolne.

•

zmiana punktu pi RGNV]WDáFD NU]\Z ORNDOQLH W\ONR GOD t∈[t

, t

i+m+1

•

wyznaczanie punktów krzywej:

•

algorytm de Boora-Coxa dla t

∈(t

, t

k+1

for i := 0 to m do r

:= p

k-m+i

;

for j := 1 to m do

for i := 0 to m-j do r

:= r

+ (t-t

i+j

)/(t

i+m+1

-t

i+j

)

i+1

- r

);

q(t) := r

q( )

( ).

( )

[ ,

( )

[

t t

m i

i m

m i

∉

≥

∈

+ +

∑

dla

dla dowolnego

dla

( )

(

)

m i

i k m

∈

= −

∑

dla

Wyszukiwarka

Podobne podstrony:
Grafika komputerowa 2
Grafika komputerowa i OpenGL
GIMP, SZKOŁA, Informatyka, Grafika Komputerowa
I Ćwiczenie 5, WAT, semestr III, Grafika komputerowa
GRAFIKA KOMPUTEROWA
Grafika Komputerowa, edukacja i nauka, Informatyka
Grafika komputerowa I 8 Drze Nieznany
94693452120-cad wersja mikro, Grafika komputerowa
I7X1S1 Loay Achmasiewicz, WAT, semestr III, Grafika komputerowa
Grafika komputerowa 2
Podstawy grafiki komputerowej, 18
komp grafika komputerowego
I Ćwiczenie 6, WAT, semestr III, Grafika komputerowa
50, WAT, semestr III, Grafika komputerowa
SPR-ANKI, Studia, WAT Informatyka, s3 - GK - lab grafika komputerowa, Lab2
Zadanie IY4S1, Studia, WAT Informatyka, s3 - GK - grafika komputerowa, LAB2
sprawozdanie3, Studia, WAT Informatyka, s3 - GK - lab grafika komputerowa, Lab4

więcej podobnych podstron