GRAFIKA, PRZETWARZANIE I ROZPOZNAWANIE OBRAZÓW

-DFHN /HELHG(

Przetwarzanie obrazów

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

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

Obraz





Katedra Technik Programowania


Rys. 6FKHPDW LOXVWUXMF\

p. 420 WETI tel. [phone]

Grafika

Rozpoznawanie obrazów

Z]DMHPQH ]DOH*QRFL

PL G]\ JUDILN

przetwarzaniem

Opis

obrazów i

rozpoznawaniem

obrazów.





GRAFIKA KOMPUTEROWA


�ó .RPXQLNDFMD ] F]�ĄRZLHNLHP

�ó Obrazowanie schematów

�ó 3UH]HQWRZDQLH ]HVWDZLH





GRAFIKA KOMPUTEROWA


�ó 0RGHORZDQLH NV]WD�ĄWyZ

�ó .UHOHQLH U\VXQNyZ WHFKQLF]Q\FK

�ó 6N�ĄDGDQLH SXEOLNDFML

�ó SSRU]G]DQLH PDS NDUWRJUDILD

�ó Synteza obrazów realistycznych

�ó Wizualizacja modelowanych zjawisk

�ó Animacja

�ó Plastyka

LITERATURA:

PRZETWARZANIE OBRAZÓW

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

�ó Dyskretyzacja obrazów

Graphics. Springer, Berlin 1985.

�ó Polepszanie jakoFL REUD]yZ

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

�ó Urealnianie obrazów

Wprowadzenie do grafiki komputerowej. WNT, Warszawa 1995.

�ó Rekonstrukcja obrazów

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

�ó Kompresja obrazów

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

�ó :\RGU EQLDQLH RELHNWyZ

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

�ó 8SUDV]F]DQLH NV]WD�ĄWyZ

informatique, Paris 1985.

5. M. Jankowski: Elementy grafiki komputerowej. WNT, Warszawa 1990.

ROZPOZNAWANIE OBRAZÓW

6. T. Pavlidis: Grafika i przetwarzanie obrazów. WNT, Warszawa 1987.

�ó Opis obiektów

7. J. Zabrodzki (red.): Grafika komputerowa, metody i narz dzia. WNT,

�ó Klasyfikacja obiektów

Warszawa 1994.

�ó Porównywanie obrazów

Gdask 2000

�ó Analiza struktury

2

BARWA (KOLOR)

SPOSOBY PREZENTACJI OBRAZÓW W GRAFICE KOMPUTEROWEJ:

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

�ó





GRAFIKA RASTROWA


3�ĄDV]F]\]QD REUD]X MHVW SRG]LHORQD QD SURVWRNWQH HOHPHQW\ W]Z SLNVHOH

�ó

Dwa rodzaje receptorów w ludzkim oku:

Tworzenie obrazu polega na wyznaczeniu kolorów poszczególnych pikseli

�ó

SU FLNL UHDJXM MX* SU]\ QLVNLP SR]LRPLH RZLHWOHQLD EUDN ZUD*H

i naniesieniu tych kolorów w odpowiednich miejscach poleceniem write(c).

barwnych - widzenie skotopowe (nocne);

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

�ó

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

barwy - widzenie fotopowe (dzienne).

Sposoby reprezentacji obrazów:

�ó

tablice (mapy bitowe)

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

�ó

Teoria Younga - Helmholtza Z\MDQLDMFD PHFKDQL]P SRZVWDZDQLD

�ó

drzewa czwórkowe

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

�ó

drzewa binarne

ZLDW�ĄRF]X�Ą\FK F]X�Ą\FK RGSRZLHGQLR QD EDUZ\

Kompresja:

�ó

QLHELHVN F]X�ĄR�ź β(�),

�ó

metody bez utraty informacji:

�ó

]LHORQ F]X�ĄR�ź �ł(�),

�ó

PHWRG\ NRGyZ ]PLHQQHM G�ĄXJRFL +XIIPDQ

�ó

SRPDUDF]RZRF]HUZRQ F]X�ĄR�ź ρ(�).

�ó

metody arytmetyczne

�ó

PHWRG\ V�ĄRZQLNRZH /HPSHO=LY:HOFK /=:

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

�ó

bezstratne metody kompresji danych graficznych,

VXEVWDQFML 6XPD SREXG]H GHWHUPLQXMH RGELHUDQ MDVQR�ź

QS NRGRZDQLH G�ĄXJRFL VHNZHQFML DQJ run length encoding RLE)

�ó

PHWRG\ ] XWUDW LQIRUPDFML

�ó

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

�ó

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

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

�ó

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

�ó

metody fraktalne

�ó

Modele syntezy barw:

Formy danych obrazowych:

�ó

model RGB ang. red + green + blue - czerwony + zielony + niebieski,

�ó

obrazy kolorowe

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

synteza addytywna, stosowany w monitorach kolorowych;

�ó

obrazy szare (wielopoziomowe)

type Color = integer

�ó

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

�ó

REUD]\ F]DUQRELD�ĄH GZXSR]LRPRZH

type Color = Boolean

]LHORQRQLHELHVNL NDUPD]\QRZ\ *y�ĄW\ F]DUQ\

synteza subtraktywna, stosowane w poligrafii;

�ó





GRAFIKA WEKTOROWA


2EUD] VN�ĄDGD VL ] WDNLFK RELHNWyZ MDN RGFLQHN OXE SXQNW

�ó

modele YUV, YIQ i YCbCr - luminancja + dwie chrominancje,

VWRVRZDQH Z WHOHZL]ML NRORURZHM ]JRGQH ] WHOHZL]M F]DUQRELD�Ą

Tworzenie obrazu polega na narysowaniu poszczególnych obiektów

VN�ĄDGRZ\FK SROHFHQLDPL plot(x,y,c), vector(x 1 ,y 1 ,x 2 ,y 2 ,c).

�ó

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

SU]\N�ĄDG\ XU]G]H SORWHU WDEOHW

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

hue:

red

yellow

green

cyan

blue

magenta

Sposoby reprezentacji obrazów:

NW

0°

60°

120°

180°

240°

300°

�ó

zbiór linii

type Image = list of Line

VWRVRZDQH Z GLDORJX ] F]�ĄRZLHNLHP ]JRGQH ] OXG]N LQWXLFM

�ó

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

Formy danych obrazowych:

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

�ó

REUD]\ VN�ĄDGDMFH VL ] OLQLL FLJ�Ą\FK

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

�ó

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

�ó

REUD]\ VN�ĄDGDMFH VL ] RGFLQNyZ

�ó

model TekHVC - model teoretyczny opracowany w firmie Tektronix,

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

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

3

4





Metody kompresji danych graficznych


�ó





Metody falkowe


:\NRU]\VW\ZDQH WX V GZD ILOWU\ MHGQRZ\PLDURZH ILOWU GROQRprzepustowy L

�ó

.RGRZDQLH G�ĄXJRFL VHNZHQFML ( ang. run length encoding RLE)

i lustrzany do niego filtr górnoprzepustowy H.

: 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

7ZRU]RQ\ MHVW FLJ REUD]yZ Î 1 , Î 1 , Î 1 , Î 2 , Î 2 , Î 2 , ..., În , În , În , In.



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

�ó

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





Metody transformat


H


2:1

Î +

i+1

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



H

2:1

�Ś Wykonanie zadanej transformacji T na poszczególnych blokach U

–

m�m:

Î

L

2:1

i+1

Vm� m= TUm� m (dla JPEG: DCT).

Ii

�Ś

|

Dokonanie kwantyzacji K wyników transformacji Vm� m:

Î

H

2:1

i+1

Wm� m= KVm� m (dla JPEG: wi, j = [ vi, j / qi, j ], gdzie wi, j, vi, j, qi, j V

L

2:1

elementami macierzy Wm� m, Vm� m i Qm� m, przy czym Qm� m jest wiersze

L

2:1

Ii+1

]DGDQ PDFLHU] NZDQW\]DFML

kolumny

�ó





Metody fraktalne


�Ś Linearyzacja skwantowanych wyników transformacji Wm� m (dla JPEG:

metoda ZIGZAG).

Fraktalem QD]\ZDP\ SRG]ELyU S�ĄDV]F]\]Q\ OXE LQQHM SU]HVWU]HQL

�Ś .RPSUHVMD HIHNWyZ OLQHDU\]DFML MDN PHWRG EH] XWUDW\ LQIRUPDFML GOD

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

JPEG: metoda Huffmana).

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

Rys. KomprHVMD PHWRG WUDQVIRUPDW

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

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

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

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

= ND*G\P IUDNWDOHP PR*QD ]DWHP VNRMDU]\�ź LWHUDF\MQ\ XN�ĄDG IXQNFML

�Ś 2GWZRU]HQLH SU]\EOL*RQ\FK Z\QLków transformacji Vm� m na podstawie

�ó

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

skwantowanych wyników transformacji Wm� m (dla JPEG:

NRGRZDQLH SRGRELHVWZ JHRPHWU\F]Q\FK NV]WD�ĄWyZ

vi, j = wi, j · qi, j, gdzie vi, j, wi, j, qi, j V HOHPHQWDPL PDFLHU]\ Vm� m,

�ó

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

Wm� m i Qm� m, przy czym Qm� m MHVW ]DVWRVRZDQ SRGF]DV NRPSUHVML

PDFLHU] NZDQW\]DFML

NRGRZDQLH SRGRELHVWZ Z G]LHG]LQLH NRORUyZ

�Ś Wykonanie zadanej transformacji odwrotnej T-1 na poszczególnych

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

a)

b)

5\V 'HNRPSUHVMD PHWRG WUDQVIRUPDW

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

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

16

11

10

16

24

40

51

61

17

18

24

47

66

99

99

99

12

12

14

19

26

58

60

55

18

21

26

66

99

99

99

99

x' = 0.2· x – 0.26· y + 0

14

13

16

24

40

57

69

56

24

26

56

99

99

99

99

99

14

17

22

29

51

87

80

62

47

69

99

99

99

99

99

99

y' = 0.23· x + 0.22· y + 1.6

18

22

37

56

68

109 103

77

99

99

99

99

99

99

99

99

24

35

55

64

81

104 113

92

99

99

99

99

99

99

99

99

x' = – 0.15· x + 0.28· y + 0

49

64

78

87

103 121 120 101

99

99

99

99

99

99

99

99

y' = 0.26· x + 0.24· y + 0.44

72

92

95

98

112 100 103

99

99

99

99

99

99

99

99

99

Rys. Macierze kwantyzacji Q 8�8

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

dla luminancji i dla chrominancji.

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

Rys. Linearyzacja metod =,*=$* GOD m=8).

5\V )UDNWDOQ\ OL�ź SDSURFL D L MHJR LWHUDF\MQ\ XN�ĄDG IXQNFML E

5

6

Dyskretyzacja obrazów rzeczywistych





GEOMETRIA DYSKRETNA


QVVLDG EVVLDG QVVLDG

�ó

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

piksela

piksela

piksela

�ó

=DOH*QR�ź HIHNWyZ SUyENRZDQLD RG SR�ĄR*HQLD VLDWNL SUyENRZDQLD

P

P





P


�ó

=PLDQD NV]WD�ĄWX REV]DUX SR SUyENRZDQLX

EVVLDG

EVVLDG

:DUXQHN ]JRGQRFL ]H VWD�Ą �ą GOD REV]DUX SRG]ELRUX S�ĄDV]F]\]Q\ �"Ś

piksela

piksel P

piksela

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

P





P


�Ł�

5\V 6VLHG]L SLNVHOD

EVVLDG QVVLDG

∃

P.

QVVLDG

k(Q , r

�"Ś

Fr

,





1


) ⊂ P ∈ k(Q r





1


)�Łś

�ŁŹ

�Ł�

piksela

piksela

piksela

∃ r > h

�ą ∀P ∈Fr

�"Ś �ŁŹ

&

�Ł� ,

P

P





P


�ŁŹ

�Ł�

�Ł�∃k(Q , r

2

) ⊂ �"Ś′ P ∈Frk(Q , r

2

)�Ł�

gdzie

'HILQLFMH VVLHG]WZD

�ó

%H]SRUHGQLPL VVLDGDPL EVVLDGDPL QD]\ZDP\ GZD SLNVHOH PDMFH

Fr �"Ś - brzeg obszaru �"Ś,

Fr �"Ś = �"Ś ∩ �"Ś′ ,

wspólny bok.

�"Ś GRPNQL FLH REV]DUX �"Ś,

�"Ś = �"Ś ∪ Fr �"Ś,

�ó

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

�"Ś′ GRSH�ĄQLHQLH REV]DUX �"Ś,

�"Ś′ = {P ∉ }

�"Ś ,

]H VRE W\ONR QDUR*QLNDPL

�ó

6VLDGDPL ]ZLHP\ ]DUyZQR EVVLDGyZ MDN L QVVLDGyZ

k( ,

Q r) NR�ĄR R URGNX Z SXQNFLH Q i o promieniu r.

Definicje linii:

Stwierdzenie 1:

�ó

%GURJ MHVW FLJ SLNVHOL P1, P2, ..., P n WDNL *H ∀ k∈{1, 2, .., n-1} piksele

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

P k i P k+1 V EVVLDGDPL

�ó

'URJ QGURJ MHVW FLJ SLNVHOL P

VSH�ĄQLDM ZDUXQHN ]JRGQRFL ]H VWD�Ą

1, P2, ..., P n WDNL *H ∀ k∈{1, 2, .., n-1}

�ą = 2 , wówczas próbkowanie

2

piksele P k i P k+1 V VVLDGDPL

�ó

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

]DFKRZD WRSRORJL NV]WD�ĄW REV]DUX

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

Stwierdzenie 2:

GURJ MHVW VVLDGHP RVWDWQLHJR SLNVHOD WHJR FLJX

-HOL REV]DU �"Ś

�ó

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

i kwadratowa siatka próbkowania (raster) o boku h

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

VSH�ĄQLDM ZDUXQHN ]JRGQRFL ]H VWD�Ą �ą = 10 , wówczas próbkowanie

2

Definicje konturu:

]DFKRZD WRSRORJL NV]WD�ĄW ZQ WU]D REV]DUX D NRQWXU E G]LH VL VN�ĄDGD�ź

�ó

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

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

] NU]\Z\FK ]DPNQL W\FK

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

�ó

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

MHGQHJR EVVLDGD QLH QDOH*FHJR GR WHJR ]ELRUX

Z\PDJDQD MDNR�ź

dobra

UHGQLD

OLF]ED SR]LRPyZ MDVQRFL

256

64

'HILQLFMH VSyMQRFL

obrazy szare

8 b/piksel

6 b/piksel

�ó

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

obrazy kolorowe

24 b/piksel

18 b/piksel

�ó

Zbiór pikseli jest b-spójny MHOL GOD ND*GHM SDU\ SLNVHOL WHJR ]ELRUX LVWQLHMH

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

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

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

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

7

8

Krzywe dyskretne





Odcinek dyskretny


�ó

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

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

'HILQLFMD G�ĄXJRFL NU]\ZHM

�ó

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

�ó

'�ĄXJRFL NU]\ZHM QD]\ZD�ź E G]LHP\ SRPQLHMV]RQ R MHGHQ

tnej:

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

�ó ]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

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

a)

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

d)

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

5\V 'ZD Uy*QH RGFLQNL

b)

�

�ĄF]FH WH VDPH GZD SXQNW\

6WZLHUG]HQLD R F] FL ZVSyOQHM GZyFK RGFLQNyZ

c)

�

�ó

'ZD NU]\*XMFH VL RGFLQNL PRJ PLH�ź GRZROQ OLF]E SXQNWyZ ZVSyOQ\FK

(0, 1, 2, ...).

Rys.

�ó

&] �ź ZVSyOQD RGFLQNyZ PR*H QLH E\�ź VSyMQD

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

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

�ó

2GFLQHN NWyUHJR NUDFH QDOH* GR GUXJLHJR RGFLQND PR*H QLH ]DZLHUD�ź VL

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

w tym drugim odcinku.

c) krzywa, w której dla dwóch dowolnych pikseOL OH*F\FK SR Uy*Q\FK VWURQDFK

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

a)

b)

c)

E

d)

A

e)

�ą

d) NU]\ZD QLH E GFD VZRLP NRQWXUHP FHQWUDOQ\ SLNVHO � DQL GURJ SURVW Z

E

E

A

E

�ą

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

A

E

A

E

A

E

A E

�ą

A

E

A

E

A

E

A E

A E

Metody rysowania krzywych dyskretnych:

A E

A E

�ą

�ą

�ą

�ó

numeryczne

A E

�ą

�ą

A E

�ą

�ó

podstawowe, parametryczne.

E A

E A

E

A

�ą

A

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

E A

E

A

E

A

�ą

A

= f( x) lub paramet-

rycznych x

E

A

E

A

A

E A

= x( t), y = y( t) wykorzystywanych w geometrii euklidesowej,

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

E

A

A

A

�ą

�ó VWRVRZDQH ]Z�ĄDV]F]D GOD �"Z\UDILQRZDQ\FKŃU]\Z\FK QS %p]LHUD

A

A

A

E A

A

A

A

E A

�ó

warunkowe

A

A

A

E

A

�ó

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

A

A

A

A

�ó Z\QLNDM EH]SRUHGQLR ] UyZQDQLD XZLN�ĄDQHJR F( x, y) = 0

stosowanego do opisu krzywej w geometrii euklidesowej,

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

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

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

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

�ó

strukturalne

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

�ó

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

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

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

G ZVSyOQD F] �ź NU]\*XMF\FK VL RGFLQNyZ A i E nie jest spójna;

�ó NRU]\VWDM MHG\QLH ] REOLF]H FD�ĄNRZLWROLF]ERZ\FK

e) odcinek E R NRFDFK OH*F\FK QD RGFLQNX A QLH ]DZLHUD VL Z QLP Z FD�ĄRFL

�ó ]QDQH MHG\QLH GOD RGFLQNyZ L HZHQWXDOQLH RNU JyZ

9

10

Algorytmy rysowania odcinków:





Algorytm podstawowy


�ó

numeryczne

�ó

UyZQDQLH SURVWHM QD S�ĄDV]F]\(QLH

y = m * x + b

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

m ZVSy�ĄF]\QQLN NLHUXQNRZ\

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

b - wyraz wolny

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

�ó

dwa przypadki:

�ó

podstawowy

| | > 1

m

m =1

�ó

Uy*QLFRZ\ DQJ DDA - Digital Differential Analyser)

�ą

�ó

warunkowe

| | < 1

m

| | < 1

m

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

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

5\V .W QDFK\OHQLD �ą rysowanego

RGFLQND Z ]DOH*QRFL RG

�ó

Bresenhama

ZVSy�ĄF]\QQLND NLHUXQNRZHJR m.

�ó

SXQNWX URGNRZHJR DQJ midpoint)

| | > 1

m

m = -1

�ó

porównawczy Jordana

�ó

F]WHURNURNRZ\ Z RJyOQRFL ZLHlokrokowy) Gilla

�ó

| m| > 1

zamiast równania y = m * x + b

�ó

strukturalne

PR*HP\ UR]SDWU\ZD�ź UyZQDQLH x = m'

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

* y + b' ,

1

gdzie m' =

, b' = �ł b , przy czym wówczas | m' | �ń 1,

�ó

Metzgera-Bronsa

m

m

�ó

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

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

y

y

�ó

| m| �ń 1

x

e

s

e � x s, m =

�ł , b = y s �ł m* x s.

x e �ł x

$OJRU\WP\ U\VRZDQLD RGFLQNyZ ] Z\J�ĄDG]DQLHP SR]LRPDPL MDVQRFL

s

(ang. antialiasing):

�ó

numeryczne – nie omawiane tutaj

parametry procedury: x, y, xe, ye:integer; x := x s, y := y s, xe := x e, ye := y e.

�ó

warunkowe

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

�ó

z uprRV]F]RQ\P Z\J�ĄDG]DQLHP

dla | dx| �Ą | dy| (czyli |m| �ń 1):

�ó

Wu

m := dy/dx

^]D�Ą `

�ó

VWUXNWXUDOQH QLH QDGDM VL

b := y- m* x;

inc := sgn( dx);

while x � xe do

begin

Oznaczenia: ( x s , y s SRF]WHN RGFLQND

x e , y e) - koniec odcinka.

plot( x, y);

x := x+ inc;

y := round( m* x+ b)

end;

plot( xe, ye)

11

12

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

π

�ó

=D�ĄR*HQLH U\VRZDQ\ RGFLQHN QDFK\ORQ\ GR RVL 0X SRG NWHP �ą ∈ [0, ].

4

�ó

dla | m|�ń ]PLDQD ZVSy�ĄU] GQHM x o �ą1 �ł ]PLDQD ZVSy�ĄU] GQHM y o �ą m.

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

�ó

dla | m _! ]PLDQD ZVSy�ĄU] GQHM y o �ą1 �ł ]PLDQD ZVSy�ĄU] GQHM x o �ą 1 .

VVLDGHP SRSU]HGQLHJR Z NLHUXQNX �ł albo Î.

m

Rys. Kryterium wyboru

kolejnego piksela dla

d

odcinek

2

UR]ZD*DQHJR SU]\SDGNX

idealny

�ó

d 1> d 2 �ł rysowany

�ą y m

=

d

górny piksel kandydat,

Rys. Dla | m|�ń1 Zmiana

1

�ó

d

ZVSy�ĄU] GQHM

1< d 2 �ł rysowany

x o 1

dolny piksel kandydat,

�ą x=1

SRZRGXMH ]PLDQ

�ó

d

ZVSy�ĄU] GQHM

1= d 2 �ł rysowany

y o m

ostatnio

dwa

dowolny z pikseli

narysowany

piksele

piksel

kandydaci

kandydatów.

�ó

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

parametry procedury: x, y, xe, ye:integer; x := x s, y := y s, xe := x e, ye := y e.

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

zmienne procedury: z, zinc:real; inc, dx, dy:integer; dx := xe- x; dy := ye- y; xi+1:= xi +1

przy wyborze dowolnego z pikseli kandydatów,

dla | dx| �Ą | dy| (czyli |m| �ń 1):

y

�Łą i +1 przy wyborze górnego piksela kandydata,

z := y;

yi +1:= �Ł� y

�Łł i

przy wyborze dolnego piksela kandydata.

inc := sgn( dx);

zinc := dy/| dx _

^]D�Ą `

�ó

Wynik porównania d

while x � xe do

1> d 2 decyduje o wyborze kolejnego piksela

begin

do rysowania:

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

plot( x, y);

d 2 = ( yi+1)- y = ( yi+1)- m*( xi+1)- b.

x := x+ inc;

z := z+ zinc;

�ó

=DPLDVW QLHUyZQRFL d 1> d 2 PR*QD UR]ZD*D�ź ]QDN Uy*QLF\ d 1- d 2.

y := round( z)

d 1- d 2 = 2* m*( xi+1)+2* b-2* yi-1.

end;

π

�ó

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

plot( xe, ye)

4

ZL F �ą x = x e- x s ! VWG VJQ d 1- d 2) = sgn(�ą x*( d 1- d 2)).

�ó

Oznaczenie:

pi = �ą x*( d 1- d 2) =

= 2*�ą x* m*( xi+1)+2*�ą x* b-2*�ą x* yi-�ą x =

b = y s- m* x s

= 2*�ą x* m*( x

�ą

i+1)+2*�ą x* y s-2*�ą x* m* x s-2*�ą x* yi-�ą x =

y = �ą x* m

= 2*�ą y*( xi+1)+2*�ą x* y s-2*�ą y* x s-2*�ą x* yi-�ą x.

:DUWR�ź pi jest zawsze ZDUWRFL FD�ĄNRZLW.

13

14

�ó

d 1> d 2 �" d 1- d 2>0 �" pi>0 �ł

wybór górnego piksela kandydata,

$OJRU\WP SXQNWX URGNRZHJR DQJ midpoint)

d

π

1< d 2 �" d 1- d 2<0 �" pi<0 �ł

wybór dolnego piksela kandydata,

�ó

=D�ĄR*HQLH U\VRZDQ\ RGFLQHN QDFK\ORQ\ GR RVL 0X SRG NWHP �ą ∈ [0, ].

d 1= d 2 �" d 1- d 2=0 �" pi=0 �ł

wybór dowolnego piksela kandydata,

4

w algorytmie przyj WR Z\EyU JyUQHJR

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

VVLDGHP SRSU]HGQLHJR Z NLHUXQNX �ł albo Î.

�ó

3RF]WNRZD ZDUWR�ź pi:

p 0 = 2*�ą y*( x 0+1)+2*�ą x* y s-2*�ą y* x s-2*�ą x* y 0-�ą x =

x 0= x s, y 0= y s

= 2*�ą y* x s+2*�ą y+2*�ą x* y s-2*�ą y* x s-2*�ą x* y s-�ą x =

Rys. Kryterium wyboru kolejnego

odcinek

SLNVHOD GOD UR]ZD*DQHJR

= 2*�ą y-�ą x.

idealny

przypadku:

o wyborze kolejnego piksela

�ó

Modyfikacja wartoFL pi:

GHF\GXMH ]QDN ZDUWRFL

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

xi+1- xi = 1

funkcji F( x, y)= a* x+ b* y+ c

= 2

Z SXQNFLH URGNRZ\P

*�ą y-2*�ą x*( yi+1- yi) =

yi+1- yi ∈ {0,1}

=

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

ostatnio

dwa

2

SRPL G]\ SLNVHODPL

* (

�Łą

�ą y �ł �ą x) JG\ p �Ą 0 (

narysowany

piksele

i

yi +1 �ł y = 1),

i

�Ł�

piksel

kandydaci

kandydatami.

2 * �ą y

JG\ p < 0 (

�Łł

i

yi +1 �ł y = 0).

i

�ó

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,

parametry procedury: x, y, xe, ye:integer; x := x

�Łą +

s, y := y s, xe := x e, ye := y e.

y

1

przy wyborze górnego piksela kandydata,

y

i

:

�Ł�

zmienne procedury: p, pinc, pdec, dx, dy:integer; dx := xe- x; dy := ye- y; i + =

1

y

�Łł i

przy wyborze dolnego piksela kandydata.

dla dx �Ą dy �Ą 0:

p := 2* dy- dx;

�ó

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

pinc := 2* dy;

�ł c * ( y �ł y )

V

H

�ł c * ( x �ł x )

H

V

pdec := 2*( dy- dx);

Dla dwóch punktów prostej: a =

, b =

.

x * y

H

V �ł x * y

x * y

H

V �ł x * y

while x � xe do

V H

V H

begin

3U]\MPXMF c = x e* y s - x s* y e RWU]\PXMH VL a = y e - y s, b = -( x e - x s).

plot( x, y);

:DUWRFL a, b, c PR*QD ZL F WDN GREUD�ź E\ E\�Ą\ FD�ĄNRZLWH.

x := x+1;

if p < 0 then p := p+ pinc

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

�ó

3RQLHZD* SRF]WHN RGFLQND x s , y s) i jego koniec ( x e , y e OH* QD SURVWHM

end;

F( x, y ZL F

plot( xe, ye)

F( x 0, y 0) = F( x s, y s) = 0

oraz

F( x e, y e) = 0.

1

1

�ó

Oznaczenie:

fi := [F( xi+1, yi+ )] = [ a*( xi+1) + b*( yi+ ) + c] =

2

2

b

b

= a* xi + b* yi + c + a + [ ] = F( xi, yi) + a + [ ].

2

2

:DUWR�ź fi jest zawsze ZDUWRFL FD�ĄNRZLW.

15

16

1

Algorytm porównawczy Jordana

�ó

F( xi+1, yi+ ) > 0 �ł fi �Ą 0 �ł wybór górnego piksela kandydata, 2

π

�ó

Za�ĄR*HQLH U\VRZDQ\ RGFLQHN QDFK\ORQ\ GR RVL 0X SRG NWHP �ą ∈ [0, ].

1

2

F( xi+1, yi+ ) < 0 �ł fi < 0 �ł wybór dolnego piksela kandydata, 2

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

1

VVLDGHP SRSU]HGQLHJR Z NLHUXQNX �Ź, �ł albo Î.

F( xi+1, yi+ ) = 0 �ł wybór dowolnego piksela kandydata,

2

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

odcinek

�ó

3RF]WNRZD ZDUWR�ź f

idealny

i:

b

f 0 = F( x 0, y 0) + a + [ ] =

x 0= x s, y 0= y s

2

Rys. Kryterium wyboru

b

kolejnego piksela dla

= F( x s, y s) + a + [ ] =

F( x 0, y 0) = F( x s, y s) = 0

UR]ZD*DQHJR SU]\SDGNX

2

b

ostatnio

trzy

rysowany jest ten piksel,

= a + [

] .

narysowany

piksele

NWyUHJR URGHN OH*\

2

piksel

kandydaci

QDMEOL*HM RGFLQND LGHDOQHJR

�ó

0RG\ILNDFMD ZDUWRFL f

�ó

3U]\MPLMP\ *H RVWDWQLR QDU\VRZDQ\ SLNVHO PD ZVSy�ĄU] GQH x

i:

i, yi.

:yZF]DV ZVSy�ĄU] GQH NROHMQHJR SLNVHOD PRJ Z\QLH�ź

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

= a

1.

x

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

xi+1- xi = 1

i+1:= xi +1

przy wyborze prawego piksela kandydata,

= a + b

y

*( yi+1- yi) =

yi+1- yi ∈ {0,1}

i+1:= yi

a

�Łą b JG\ f

2.

x

i �Ą 0 ( yi

y

+1 �ł i = 1),

i+1:= xi

przy wyborze górnego piksela kandydata,

= �Ł�

y

a

JG\ f

�Łł

i+1:= yi +1

i < 0 ( yi

y

+1 �ł i = 0).

3.

xi+1:= xi +1

przy wyborze prawego górnego piksela kandydata.

yi+1:= yi +1

�ó

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

parametry procedury: x, y, xe, ye:integer; x := x s, y := y s, xe := x e, ye := y e.

�ł c * ( y �ł y )

V

H

�ł c * ( x �ł x )

H

V

Dla dwóch punktów prostej: a =

, b =

.

zmienne procedury: f, df, dx, dy:integer;

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

x * y

H

V �ł x * y

V H

x * y

H

V �ł x * y

V H

dla dx �Ą dy �Ą 0:

PrzyjmujF c = - ( x e* y s - x s* y e RWU]\PXMH VL b = x e - x s, a = -( y e - y s).

df := dy- dx;

f := df+( dx div 2);

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

:DUWRFL a, b, c PR*QD ZL F WDN GREUD�ź E\ E\�Ą\ FD�ĄNRZLWH.

while x � xe do

begin

plot( x, y);

�ó

Oznaczenia:

f := F( xi, yi),

F( x 0, y 0) = F( x s, y s) = 0,

x := x+1;

f 1 := F( xi+1, yi) = f+ a,

if f < 0 then f := f+ dy

f

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

2 := F( xi, yi+1) = f+ b,

end;

f 3 := F( xi+1, yi+1) = f+ a+ b.

plot( xe, ye)

17

18

�ó

| f 1|<| f 2| & | f 1|<| f 3| �ł

wybór prawego piksela kandydata,

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

| f 2|<| f 1| & | f 2|<| f 3| �ł

wybór górnego piksela kandydata,

| f 3|<| f 1| & | f 3|<| f 2| �ł

wybór prawego górnego piksela kandydata,

�ó

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

| f 1|<| f 2| & | f 1|=| f 3| �ł

wybór prawego lub prawego górnego piksela,

1

�ó

=D�ĄR*HQLH RGFLQHN QDFK\ORQ\ GR RVL 0X SRG NWHP �ą ∈ (0, arctg ].

| f 2|<| f 1| & | f 2|=| f 3| �ł

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

4

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

'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

�ó

3RQLHZD* f 2 �Ą f 3 �Ą f 1 ZL F

SRSU]HG]DMFHJR MHGQ ] SL FLX IRUP

| f 1|<| f 2| & | f 1|<| f 3| �" | f 1|<| f 3| �ł

wybór prawego piksela kandydata,

| f 2|<| f 1| & | f 2|<| f 3| �" | f 2|<| f 3| �ł

wybór górnego piksela kandydata,

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

0 0 0 0

0 0 0 1

0 0 1 0

parametry procedury: x, y, xe, ye:integer; x := x s, y := y s, xe := x e, ye := y e.

zmienne procedury: f 1, f 2, f 3, dx, dy:integer; dx := xe- x; dy := ye- y; 0 1 0 0

1 0 0 0

dla dx �Ą 0 & dy �Ą 0:

f 1 := - dy;

�ó

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

while ( x � xe) or ( y � ye) do

F]ZyUNL SLNVHOL QDVW SXMFH ZDUXQNL

begin

0000

0001

0010

0100





1000


plot( x, y);

p

f 3 := f 1+ dx;

f 2 := f 3+ dy;

i<0

pi<0

pi<0

pi<0

pi�Ą0

if |f 1| < | f 3| then begin x := x+1; f 1 := f 1- dy end pi+2�ą y<0

pi+2�ą y<0

pi+2�ą y<0

pi+2�ą y�Ą0

pi+2�ą y-2�ą x<0

else if |f 2| < | f 3| then begin y := y+1; f 1 := f 2- dy end pi+4�ą y<0

pi+4�ą y<0

pi+4�ą y�Ą0

pi+4�ą y-2�ą x<0 pi+4�ą y-2�ą x<0

else begin x := x+1; y := y+1; f 1 := f 3- dy end 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

end;

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

plot( xe, ye)

0000

0001

0010

0100





1000


�ó

3RQLHZD*

p

f

i <

- 6�ą y

�ń p

2 �Ą f 3 �Ą f 1 ZL F

i <

- 4�ą y

�ń pi < - 2�ą y �ń pi <

0

�ń pi

| f 1|<| f 3| �" - f 1< f 3 �ł wybór prawego piksela kandydata,

�ó

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

| f 2|<| f 3| �" f 2<- f 3 �ł wybór górnego piksela kandydata, Z DOJRU\WPLH %UHVHQKDPD PR*QD ]DXZD*\�ź *H

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

8 * y

�ą

JG\ p

�Łą

i < �ł6 * y

�ą

W]Q F]ZyUND

pi

p

+4 �ł i = �Ł�8* y

�Łł �ą �ł 2 * x

�ą

JG\ pi �Ą �ł6 * y

�ą

SR]RVWD�Ą H F]ZyUNL

parametry procedury: x, y, xe, ye:integer; x := x s, y := y s, xe := x e, ye := y e.

zmienne procedury: f 1, f 2, f 3, dx, dy:integer; dx := xe- x; dy := ye- y;

�ó

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

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

dla dx �Ą 0 & dy �Ą 0:

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

f 1 := - dy;

while ( x � xe) or ( y � ye) do

0000

0001

0010

0100





1000


begin


0000

0000

0000

0000

0000

plot( x, y);

1000

0001

0001

0010

0100

f 3 := f 1+ dx;

f 2 := f 3+ dy;

0100

0010

0100

1000

if f 3 < - f 1 then begin y := y+1; f 1 := f 3 end; 0010

0001

0010

if - f 3 < f 2 then begin x := x+1; f 1 := f 1- dy end 0001

0001

end;

plot( xe, ye)

19

20

parametry procedury: x, y, xe, ye:integer; x := x s, y := y s, xe := x e, ye := y e.

Algorytm strukturalny Metzgera-Bronsa

zmienne procedury: p, pinc, pdec, dx, dy, m2, m4, m6, xe2:integer; dla dx �Ą 4* dy �Ą 0:

dx := xe- x;

dy := ye- y;

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

GRZROQHM NU]\ZHM PR*H E\�ź

p := 2* dy- dx;

pinc := 8* dy;

pdec := 8* dy-2* dx;

3

2

1

m2 := -2

kodowany jako cyfra ósemkowa

* dy;

m4 := -4* dy;

m6 := -6* dy;

xe2 := xe-2;

R]QDF]DMFD QXPHU VVLDGD

while x < xe2 do

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

begin

jakim jest ten piksel dla

4

0

if p < m6 then

{0000}

poprzedzajacego go piksela.

2GFLQHN G\VNUHWQ\ MDN L ND*G

begin

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

NU]\Z PR*QD ]DWHP RSLVD�ź

plot( x+2, y); plot( x+3, y);

5

6

7

SU]\ SRPRF\ FLJX F\IU

p := p+ pinc

end

ósemkowych zwanego kodem

�ĄDFXFKRZ\P

else

begin

3

if p < m2 then

1

Rys. 3U]\N�ĄDGRZD NU]\ZD L MHM NRG �ĄDFXFKRZ\

if p < m4 then

{0001}

1

2

0170213

begin

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

�ł 0

7 0

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

end

else

{0010}

�ó

3RVWXODW\ )UHHPDQD RGQRQLH NRGX �ĄDFXFKRZHJR RSLVXMFHJR RGFLQHN

begin

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

�ó

: NRG]LH �ĄDFXFKRZ\P PRJ Z\VW SRZD�ź FR QDMZ\*HM GZLH F\IU\

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

end

�ó

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

else if p < 0 then

{0100}

VVLDGRZD�ź VDPD ]H VRE

begin

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

�ó

6XNFHV\ZQH UR]PLHV]F]HQLH F\IU Z NRG]LH �ĄDFXFKRZ\P SRZLQQR E\�ź

end

WDN MHGQRURGQH MDN W\ONR MHVW WR PR*OLZH

else

{1000}

π

�ó

=D�ĄR*HQLH U\VRZDQ\ RGFLQHN QDFK\ORQ\ GR RVL 0X SRG NWHP �ą ∈ [0, ].

begin

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

plot( x+2, y); plot( x+3, y)

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

end;

VVLDGHP SRSU]HGQLHJR Z NLHUXQNX �ł albo Î : NRG]LH �ĄDFXFKRZ\P

p := p+ pdec

PRJ ZL F Z\VW SRZD�ź MHG\QLH F\IU\ L

end;

3RQLHZD* RGFLQHN MHVW QDMPQLHMV]HM G�ĄXJRFL NU]\Z �ĄF]F GZD SLNVHOH

x := x+4

ZL F Z NRG]LH �ĄDFXFKRZ\P SRZLQQR VL ]QDOH(�ź GRN�ĄDGQLH

end;

�ą y jedynek i �ą x-�ą y zer (�ą y = y e- y s, �ą x = x e- x s).

if x �ń xe then

{rysowanie ( dx+1) mod 4 pikseli}

begin

if x < xe then

�ó

Oznaczenia:

begin

if x �ń xe2 then

u �Łą

u �Łą

u �Łą

u �Łą

begin

plot( x, y);

x := x+1;

h ( u)

1

= �Ł�

( u) = u �ł �Ł�

( u) = u �ł �Ł�

( u) = �Ł�

�Ł��ŁŻ2�Ł�Ł� , K2

�Ł��ŁŻ2�Ł�Ł� lub K1

�Ł��ŁŻ2�Ł�Ł� , K2

�Ł��ŁŻ2�Ł�Ł� .

if p �Ą 0 then y := y+1

end;

�ó

Podstawienie wartoFL SRF]WNRZ\FK

i := 0,

plot( x, y)

a

end;

0 := �ą y,

A 0 := "1",

b

plot( xe, ye)

0 := �ą x-�ą y,

B 0 := "0".

end

21

22

�ó

1DOH*\ ]DWHP SU]HPLHV]D�ź ai �ĄDFXFKyZ Ai z bi �ĄDFXFKDPL Bi.

parametry procedury: x, y, xe, ye:integer; x := x s, y := y s, xe := x e, ye := y e.

�ó

zmienne procedury: A, B:string; w:Boolean; a, b, dx, dy:integer; dx := xe- x; Podstawienie:

ci := max( ai, bi),

ci= ai �ł Ci := Ai, Di := Bi,

dla dx �Ą dy �Ą 0:

dy := ye- y;

di := min( ai, bi),

ci� ai �ł Ci := Bi, Di := Ai,

a := dy; b := dx- dy; A := "1"; B := "0"; ci �Ą di.

w := false; {true}

c

while a � 0 do

�ó

1D MHGHQ �ĄDFXFK D

i

i SU]\SDGD UHGQLR ri =

�ĄDFXFKyZ Ci ( ri�Ą1).

d

begin

i

while a < b do

d

�ó

r

�Ł� K ( )

K ( ) �Łś

i FD�ĄNRZLWH �ł

NRG �ĄDFXFKRZ\ RGFLQND

i

�ŁŹ C 1 ir

C

ir

.

begin

i

i

D

i

�Ł�

�Ł�

�Ł�

if w then A := A+ B else A := B+ A; w := not w;

�ó

-HOL r

b := b- a

i QLH MHVW ZDUWRFL FD�ĄNRZLW WR QDOH*\ SU]HPLHV]D�ź ]H VRE

end;

a

h

r

h

r

i+1 := ci mod di

�ĄDFXFKyZ

Ai

Ci

i

DiCi 2 i

+ =

+

+

1

1

1

1

:

([ ]

)

([ ]

) i

repeat

b

h ([ r ])

h ([ r ])

i+1 := di - ( ci mod di

�ĄDFXFKyZ

Bi : C

1

i 1

i DiCi 2 i

+ =

.

if w then B := A+ B else B := B+ A; w := not w;

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

a := a- b

until a < b

end;

parametry procedury: x, y, xe, ye:integer; x := x s, y := y s, xe := x e, ye := y e.

for i := 1 to b do

for j := 1 to length( B) do

zmienne procedury: A, B:string; w:Boolean; a, b, dx, dy:integer; dx := xe- x; begin

dla dx �Ą dy �Ą 0:

dy := ye- y;

plot( x, y);

a := dy; b := dx- dy; A := "1"; B := "0"; x := x+1; if B[ j] = '1' then y := y+1

while a � 0 do

end;

begin

plot( xe, ye)

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)

23

24

$OJRU\WP VWUXNWXUDOQ\ ]H ]PLHQQ G�ĄXJRFL VHULL (ang. run length parametry procedury: x, y, xe, ye:integer; x := x s, y := y s, xe := x e, ye := y e.

slice)

zmienne procedury: a, b, a2, ba2M, ba2D, l, i, j, dx, dy:integer; dx := xe- x;

1

�ó

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

dla dx �Ą 2* dy > 0:

dy := ye- y;

2

a := dy; b := dx- dy; l := a;

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

a2 := a+ a; ba2M := b mod a2; ba2D := b div a2; VVLDGHP SRSU]HGQLHJR Z NLHUXQNX �ł albo Î : NRG]LH �ĄDFXFKRZ\P

plot( x, y);

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

for i := 1 to a do

W\P NRG]LH �ĄDFXFKRZ\P RWRF]RQD ]HUDPL JG\* ]HU MHVW ZL FHM

begin

3RQLHZD* RGFLQHN MHVW QDMPQLHMV]HM G�ĄXJRFL NU]\Z �ĄF]F GZD SLNVHOH

for j := 1 to ba2D do begin x := x+1; plot( x, y) end; ZL F Z NRG]LH �ĄDFXFKRZ\P SRZLQQR VL ]QDOH(�ź GRN�ĄDGQLH

l := l+ ba2M;

β = �ą y jedynek i �ą = �ą x-�ą y zer (�ą y = y

if l �Ą a2 then begin l := l- a2; x := x+1; plot( x, y) end; e- y s, �ą x = x e- x s).

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

β

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

�ó

.RG �ĄDFXFKRZ\ RGFLQND

0 2 i 1

�ł

1 0 2 i

�Ź �ą

�ą ,

l := l+ ba2M;

i 1

=

2β

β

if l �Ą a2 then begin l := l- a2; x := x+1; plot( x, y) end gdzie

�� =

n =

j

�ą,

A

A ... A

�Ź =

i

1

n ,

A

AA



... A

end

j =1

i =1

n

7U]HFL SRVWXODW )UHHPDQD PyZL W\OH *H ZDUWRFL �ą i SRZLQQ\ E\�ź MDN

QDMEOL*V]H VLHELH : SUDNW\FH R]QDF]D WR L* �ą i SU]\MPXMH MHGQ ] GZyFK

ZDUWRFL

�ą = �ą div (2β) lub �ą +1 = �ą div (2β)+1, przy czym

parametry procedury: x, y, xe, ye:integer; x := x s, y := y s, xe := x e, ye := y e.

2β

2β

UR]N�ĄDG W\FK ZDUWRFL SRZLQLHQ E\�ź MDN QDMEDUG]LHM UyZQRPLHUQ\ :�ĄDVQR�ź

zmienne procedury: a, b, a2, baD, baM2, ba2M, ba2D, l, i, j, dx, dy:integer; W ]DSHZQLD QDVW SXMF\ Z]yU LWHUDF\MQ\

dla dx �Ą 2* dy > 0:

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

j �ł1

j �ł1

�ą

�Ł� �ą

=

�Ł�

a := dy; b := dx- dy; l := a; round

j

lub �ą =

j �ł 2 �ę

+

div (2β).

j

�ą

β �ą k β

2

�ł �ę

j

β

�ą k

�Ł��ŁŹ

�Łś

=

�Ł��ŁŹ

�Łś

=

a2 := a+ a; ba2M := b mod a2; ba2D := b div a2; 1

�Ł��Ł�

1

�Ł��Ł�

k

k

baD := ba2D+ ba2D; baM2 := ba2M+ ba2M;

�ó

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

if ba2M > a

β

β

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

�ł

1 0 2 i

�Ź �ą

�ą ,

gdzie



A

A ... A

�Ź =

n =

plot( x, y);

i

1

n ,

A

AA



... A ,

i 1

=

i =1

n

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

�Łą �ą div (2β)





dla �

if l �Ą a2 then begin l := l- a2; x := x+1; plot( x, y) end; j + �ą mod (2β) < 2β,

]D �ą j = �Ł�

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

�Łł �ą div (2β) +1

dla � j + �ą mod (2β) �Ą 2β,

for i := 2 to a do

�

begin

j = (�ą( j�ł1) +β) mod (2β),

for j := 1 to baD do begin x := x+1; plot( x, y) end; czyli �1 = β,

l := l+ baM2;

�Łą � j + �ą mod (2β)





dla � j + �ą mod (2β) < 2β,

if l �Ą a2 then begin l := l- a2; x := x+1; plot( x, y) end; � j+1 = �Ł��Łł

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

� j + �ą mod (2β) �ł 2β

dla � j + �ą mod (2β) �Ą 2β,

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 25

26

�ś= EDWR�ź” odcinków dyskretnych (ang. aliasing)

:\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 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 %H]ZDJRZR Z\J�ĄDG]RQ\ RGFLQHN G\VNUHWQ\ ZDJD SURVWRSDG�ĄRFLHQQD

�ó

wagowe próbkowanie powierzchni

5\V 2VWURV�ĄXSRZD IXQNFMD ZDJRZD

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 6WR*NRZD IXQNFMD ZDJRZD

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

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

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

L ZDJD VWR*NRZD QD GROH

27

28

$OJRU\WP ] XSURV]F]RQ\P Z\J�ĄDG]DQLHP DQJ antialiasing) $OJRU\WP :X ] Z\J�ĄDG]DQLHP DQJ antialiasing)

π

π

�ó

=D�ĄR*HQLH U\VRZDQ\ RGFLQHN QDFK\ORQ\ GR RVL 0X SRG NWHP �ą ∈ [0, ].

�ó

=D�ĄR*HQLH U\VRZDQ\ RGFLQHN QDFK\ORQ\ GR RVL 0X SRG NWHP �ą ∈ [0, ].

4

4

Piksele rysowane parami w pionie.

Piksele rysowane parami w pionie.

�ó

=D�ĄR*HQLH m GRVW SQ\FK SR]LRPyZ MDVQRFL

�ó

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

xi

Rys. Kryterium wyboru kolejnych

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

pikseli:

xi+1:= xi +1

�ó

k>0 �ł kolejne dwa piksele

yi

�Łą +

odcinek

y

1

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

rysowane w tych samych

i

i

idealny

y

1:

�Ł�

wierszach (

+ =

y

i

i, yi-1),

y

�Łł i

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

�ó

k<0 �ł kolejne dwa piksele

rysowane w wierszach o

�ó

,QWHQV\ZQR�ź JyUQHJR SLNVHOD MHVW ZSURVW SURSRUFMRQDOQD GR a·( i+1)-[ a·( i+1)], SR]LRP Z\*HM yi+1, yi),

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

�ó

k=0 �ł kolejny piksel (tylko

�ó

=D�ĄR*HQLH SURFHGXUD SORW x, y, c, c QDGDMH SXQNWRZL R ZVSy�ĄU] GQ\FK

ostatnio

trzy piksele

jeden) rysowany

max

narysowane

kandydaci

w górnym wierszu ( y

x, y LQWHQV\ZQR�ź Z]JO GQ c / c

ZDUWRFL FD�ĄNRZLWH

i),

max (gdzie c, cmax

piksele

(dwie pary)

FR ZL FHM c

MHVW SRPQLHMV]RQ R SRW J OLF]E\

max

�ó

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

�ó

=DPLDVW ZDUWRFL X�ĄDPNRZHM a· i-[ a· i] OHSLHM MHVW UR]ZD*D�ź ZDUWR�ź FD�ĄNRZLW

([2 n· a+0,5]· i) mod 2 n.

xi+1:= xi +1

y

�Łą i +1 dla k<0,

�ó

=D�ĄR*HQLH IXQNFMD RYHUIORZ d ]ZUDFD ZDUWR�ź true tylko wtedy,

yi +1:= �Ł�

gdy poprzednia operacja na zmiennej d ]DNRF]\�ĄD VL SU]HSH�ĄQLHQLHP

y

�Łł i

dla k�Ą0.

�ó

,QWHQV\ZQR�ź JyUQHJR SLNVHOD MHVW ZSURVW SURSRUFMRQDOQD GR k,

LQWHQV\ZQR�ź GROQHJR SLNVHOD MHVW ZSURVW SURSRUFMRQDOQD GR

parametry procedury: x, y, xe, ye:integer; x := x k.

s, y := y s, xe := x e, ye := y e.

VWD�ĄH SURFHGXU\ n {liczba bitów dla typu integer},

�ó

=D�ĄR*HQLH SURFHGXUD SORW x, y, c, c QDGDMH SXQNWRZL R ZVSy�ĄU] GQ\FK

max

nm { n- m>0, gdzie 2 m MHVW OLF]E SR]LRPyZ V]DURFL}, x, y LQWHQV\ZQR�ź Z]JO GQ c / c

ZDUWRFL FD�ĄNRZLWH

max (gdzie c, cmax

em {2 m-1};

�ó

ZamiDVW ZDUWRFL X�ĄDPNRZHM k OHSLHM MHVW UR]ZD*D�ź ZDUWR�ź FD�ĄNRZLW k*�ą x.

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

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

parametry procedury: x, y, xe, ye:integer; x := x s, y := y s, xe := x e, ye := y e.

dla dx �Ą dy �Ą 0:

d := 0;

zmienne procedury: kdx, dx, dy:integer;

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

dinc := (( dy shl n)+( dx shr 1)) div dx;

dla dx �Ą dy �Ą 0:

while x � xe do

kdx := 0;

begin

while x � xe do

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

begin

if d � 0 then plot( x, y+1, d shr nm, em); plot( x, y, dx- kdx, dx);

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

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

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

x := x+1;

end;

kdx := kdx- dy;

plot( xe, ye, em, em)

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

plot( xe, ye, 1, 1)

29

30

� XN RNU JX HOLSV\

Oktanty (ósemki)

3

2

dla orientacji

orientacja

orientacja

dodatniej

ujemna

dodatnia

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

4

1

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

=D]QDF]RQD VWU]D�ĄNDPL SU]\QDOH*QR�ź

5

8

(orientacja ujemna - zgodnie z ruchem

GR RNWDQWX Sy�ĄSURVWHM UR]JUDQLF]DMFHM

dla orientacji

wskazówek zegara, orientacja dodatnia -

]DOH*\ RG RULHQWDFML U\VRZDQLD

ujemnej

6

7

przeciwnie do ruchu wskazówek zegara).

=D�ĄR*HQLH ( x c, y c) = (0,0)

$OJRU\WP\ U\VRZDQLD �ĄXNyZ RNU JyZ HOLSV:

�ó

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

�ó

zmiennoprzecinkowe

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

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

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

else Octant := 2

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

else if y > - x then Octant := 3

else Octant := 4

�ó

podstawowy

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

�ó

parametryczny

else Octant := 6

else if y < - x then Octant := 7

�ó

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

else if y � 0 then Octant := 8

�ó

warunkowe

else if x � 0 then Octant := 1

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

else Octant := 0

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

Funkcja StartOctant( x s, y s, x e, y e) wykorzystuje ten algorytm do wyznaczenia

�ó

Bresenhama

RNWDQWyZ SLNVHOD SRF]WNRZHJR x s, y s L NRFRZHJR x e, y e). Funkcja ta

�ó

SXQNWX URGNRZHJR DQJ midpoint)

]ZUDFD QXPHU RNWDQWX SLNVHOD SRF]WNRZHJR �ĄXNX ,QLFMDOL]XMH RQD SRQDGWR

pewne zmienne globalne dla potrzeb funkcji Octant.

�ó

porównawczy Jordana

�ó

Algorytm wyznaczania numeru oktantu na podstawie ZVSy�ĄU] GQ\FK SLNVHOD

E

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

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

S

UR]SRF]\QDMF\ VL Z SXQNFLH 6

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

NRF]F\ VL QD Sy�ĄSURVWHM &(

wyznaczonej przez punkt E,

case Octant of 1: if x > y

then Octant := 1 else Octant := 2;

C

rysowany przy orientacji dodatniej.

2: if x > 0

then Octant := 2 else Octant := 3;

Uwaga: 3RGDQH QL*HM DOJRU\WP\

3: if y > - x then Octant := 3 else Octant := 4; U\VXM �ĄXNL ZJ RULHQWDFML GRGDWQLHM

4: if y > 0

then Octant := 4 else Octant := 5;

5: if x < y

then Octant := 5 else Octant := 6;

Oznaczenia: ( x s , y s SRF]WHN �ĄXNX

( x e , y e NRQLHF �ĄXNX

6: if x < 0

then Octant := 6 else Octant := 7;

( x c , y c URGHN RNU JX

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

then Octant := 8 else Octant := 1 end

=D�ĄR*HQLH

:VSy�ĄF]\QQLN NV]WD�ĄWX SLNVHOD DQJ

Funkcja Octant( x, y) wykorzystuje ten algorytm do wyznaczenia oktantu aspect ratio) wynosi 1.

piksel

v

piksela ( x, y). Funkcja ta zwraca numer oktantu tego piksela lub zero, gdy 5\V :VSy�ĄF]\QQLN NV]WD�ĄWX SLNVHOD UyZQ\ MHVW u .

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

v

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

u

�ó

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

Uwaga: 2NUJ R URGNX x c , y c) i promieniu r PR*QD RWU]\PD�ź ] RNU JX R

URGNX L SURPLHQLX

:DUXQHN WHQ QDOH*\ WHVWRZD�ź MHG\QLH Z RNWDQFLH SLNVHOD NRFRZHJR �ĄXNX

r VWRVXMF SU]HVXQL FLH R ZHNWRU x c , y c).

y* x e > y e* x �ł RVLJQL WR NRQLHF �ĄXNX

31

32

Algorytm podstawowy





Algorytm parametryczny


�ó

Ogólna zasada:

�ó

RównDQLH SDUDPHWU\F]QH RNU JX R URGNX x

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

c, y c) = (0,0) i promieniu r:

x = r

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

*cosϕ,

y = r

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

*sinϕ,

ϕ ∈ [0, 2*π)

]PLHQLDQ R SRZLQQD E\�ź ZVSy�ĄU] GQD GOD NWyUHM SU]\URVW\ V ZL NV]H

�ó

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

VWD�Ą ZDUWR�ź �ąϕ = const.

�ó

5yZQDQLH RNU JX R rodku ( x c, y c) = (0,0) i promieniu r:

x 2 + y 2 = r 2

�ó

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

xi = r*cosϕ i,

y

3

2

5\V 3RG]LD�Ą RNU JX QD RNWDQW\

i = r*sinϕ i,

WR SU]\ RULHQWDFML GRGDWQLHM QDVW SXMF\ SR QLP SLNVHO x

Dla orientacji dodatniej i dla oktantów:

i+1, yi+1) ma

ZVSy�ĄU] GQH

4

1

�ó

1, 8: y ]ZL NV]DQH R x:= [ r 2 �ł y 2 + 1],

x

2

i+1 = r*cosϕ i+1 = r*cos(ϕ i+�ąϕ) =

5

8

= r*cosϕ i*cos�ąϕ - r*sinϕ i*sin�ąϕ =

�ó

2, 3: x zmniejszane o 1, y:= [ r 2 �ł x 2 + 1],

2

= xi*cos�ąϕ - yi*sin�ąϕ,

6

7

�ó

4, 5: y zmniejszane o 1,

y

x:= [

�ł r 2 �ł y 2 + 1],

i+1 = r*sinϕ i+1 = r*sin(ϕ i+�ąϕ) =

2

= r*cosϕ i*sin�ąϕ + r*sinϕ i*cos�ąϕ =

�ó

[ ]ZL NV]DQH R y:= [

�ł r 2 �ł x 2 + 1].

= xi*sin�ąϕ + yi*cos�ąϕ,

2

5\V :DUWR�ź �ąϕ SRZLQQD SRZRGRZD�ź ]PLDQ

�ó

Uwaga: 'ZXEDMWRZ\ W\S LQWHJHU PR*H QLH Z\VWDUF]\�ź GR SU]HFKRZDQLD

r

ZDUWRFL ZVSy�ĄU] GQ\FK QLH ZL FHM QL* R

Z\QLNX PQR*HQLD SRGQRV]HQLD GR NZDGUDWX ZDUWRFL ZVSy�ĄU] GQ\FK

�ąϕ

�ąϕ� �ń1

1

r

:DUWR�ź �ąϕ

]DSHZQLD ]PLDQ ZDUWRFL

(np. 200

�ń

* ! 'ODWHJR WH* IXQNFMD SRGQRV]FD GR

r

NZDGUDWX SRZLQQD E\�ź ]EXGRZDQD QDVW SXMFR

r

ZVSy�ĄU] GQ\FK QLH ZL FHM QL* R

function sqr( u:integer):longint; begin sqr:=longint( u)

1

*longint( u) end

1DOH*\ ]DWHP SU]\M�ź �ąϕ = .

r

parametry procedury: x, y, xe, ye, xc, yc:integer; x := x s- x c, y := y s- y c,

parametry procedury: x, y, xe, ye, xc, yc:integer; x := x s- x c, y := y s- y c,

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

xe := x e- x c, ye := y e- y c,

zmienne procedury: rr:longint;

xe := x e- x c, ye := y e- y c,

dla wszystkich oktantów:

xc := x c, yc := y c.

dla oktantów nr 1 i 8:

xc := x c, yc := y c.

if StartOctant( x, y, xe, ye) � 0 then

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

begin

begin

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

v := x; z := y;

repeat

repeat

plot( x+ xc, y+ yc);

plot( x+ xc, y+ yc);

y := y+1;

u := v* c- z* s; z := v* s+ z* c; v := u; x := round(sqrt( rr-sqr( y)))

x := round( v); y := round( z)

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

until Octant( x, y) = 0

end

end

33

34

Algorytm Honga





Algorytm Bresenhama


1


�ó

Dla algorytmu parametrycznego: xi+1 = xi*cos�ąϕ - yi*sin�ąϕ, �ąϕ �ń r

�ó

=D�ĄR*HQLH U\VRZDQ\ �ĄXN RNU JX ] RNWDQWX QU

yi+1 = xi*sin�ąϕ + yi*cos�ąϕ.

'OD WDNLHJR �ĄXNX ND*G\ NROHMQ\ SLNVHO U\VRZDQHJR RGFLQND MHVW VVLDGHP

�ó

Oznaczenie:

poprzedniego w kierunku �Ź albo �ę.

k := [log r@ OLF]ED ELWyZ SRWU]HEQ\FK GR ]DSLVDQLD ZDUWRFL r.

2

1

1

�ó

2 k-1 �ń r < 2 k & 2- k < �ń 2- k+1 Z\JRGQLH ]DWHP SU]\M�ź �ąϕ =2- k < .

Rys. Kryterium wyboru

r

r

d

dwa

1

kolejnego piksela dla

�ó

3RQLHZD* NW �ąϕ MHVW PD�Ą\ ZL F IXQNFMH WU\JRQRPHWU\F]QH WHJR NWD

piksele

kandydaci

UR]ZD*DQHJR SU]\SDGNX

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

d 2

�ó

d

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

1> d 2 �ł rysowany

lewy piksel kandydat,

n

1

( 1) x 2 n

*

n

1

( 1) x 2 n

*

1

ostatnio

�ó

d

cos x = 1�ł

x 2 +..+ �ł

+... sin x = x �ł x 3+..+ �ł

+ +...

narysowany

1< d 2 �ł rysowany

2!

(2 * n)!

3!

(2 * n + 1)!

piksel

prawy piksel kandydat,

1

�ó

d 1= d 2 �ł rysowany

�ó

3U]\MPXMF SU]\EOL*HQLH FRV x ≈ 1- * x 2, sin x ≈ x L XZ]JO GQLDMF �ąϕ=2- k,

dowolny z pikseli

2

RWU]\PXMH VL QDVW SXMFH Z]RU\

�ĄXN LGHDOQ\

kandydatów

1

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

�ó

3U]\MPLMP\ *H RVWDWQLR QDU\VRZDQ\ SLNVHO PD ZVSy�ĄU] GQH x

1

i, yi.

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

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

2

x

�Łą �ł1 przy wyborze lewego piksela kandydata,

i

�ó

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

x

:

�Ł�

i + =

1

x

=D�ĄR*HQLH

przy wyborze prawego piksela kandydata.

shr, shl - operacje przesuwania arytmetycznego w prawo i lewo.

�Łł i

yi+1:= yi +1

przy wyborze dowolnego z pikseli kandydatów,

parametry procedury: x, y, xe, ye, xc, yc:integer; x := x s- x c, y := y s- y c,

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

�ó

Wynik porównania d

e- x c, ye := y e- y c,

1> d 2 decyduje o wyborze kolejnego piksela

2

2

dla wszystkich oktantów:

xc := x

do rysowania: d

x

(

1 2

=

�ł

�ł

+ ) , d = r �ł ( y +1 2

)

�ł ( �ł1).

c, yc := y c.

1

i

r

yi

2

i

xi

if StartOctant( x, y, xe, ye) � 0 then

�ó

d

�ł

2 �ł ( +1 2

)

>

2 �ł ( +1 2

)

�ł ( �ł1)

begin

1> d 2

�" xi

r

yi

r

yi

xi

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

�" 2 x �ł1 > 2

2 �ł

+1 2

*

*

(

)

i

r

yi

while u � 0 do begin u := u shr 2; k := k+1 end; (...)2 ( xi > 0)

�" (2

{ k := trunc(log2(sqrt(sqr( x)+sqr( y))))+1;}

* xi-1)2 > 4*( r 2-( yi+1)2)

n := 2

2

* k+1; v := x; z := y; v := v shl n; z := z shl n;

�" 4* xi -4* xi+1 > 4*( r 2-( yi+1)2)

OLF]E\ FD�ĄNRZLWH

repeat

�" 4 2-4

plot( x+ xc, y+ yc);

* xi

* xi+2 > 4*( r 2-( yi+1)2)

/ 2

u := v- x-( z shr k); z := z- y+( v shr k); v := u;

�" 2 2

* xi -2* xi+1 > 2*( r 2-( yi+1)2)

x := v shr n; y := z shr n

�" x 2 2

i + xi -2* xi+1 > 2*( r 2-( yi+1)2)

until Octant( x, y) = 0

end

�" x 2

i +( xi-1)2 > 2*( r 2-( yi+1)2)

�" x 2

i +( yi+1)2- r 2 > r 2-( xi-1)2-( yi+1)2

F( x, y) = x 2+ y 2- r 2

�" F( xi, yi+1)+F( xi-1, yi+1) > 0

35

36

�ó

Oznaczenie:

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

$OJRU\WP SXQNWX URGNRZHJR DQJ midpoint)

:DUWR�ź pi jest zawsze ZDUWRFL FD�ĄNRZLW.

�ó

=D�ĄR*HQLH U\VRZDQ\ �ĄXN RNU JX ] RNWDQWX QU

�ó

d 1> d 2 �" pi>0 �ł wybór lewego piksela kandydata,

'OD WDNLHJR �ĄXNX ND*G\ NROHMQ\ SLNVHO U\VRZDQHJR RGFLQND MHVW VVLDGHP

d 1< d 2 �" pi<0 �ł wybór prawego piksela kandydata, poprzedniego w kierunku �Ź albo �ę.

d 1= d 2 �" pi=0 �ł wybór dowolnego piksela kandydata,

w algorytmie SU]\M WR Z\EyU OHZHJR

Rys. Kryterium wyboru

ten przypadek nigdy nie zajdzie.

dwa

kolejnego piksela dla

piksele

�ó

3RF]WNRZD ZDUWR�ź pi:

kandydaci

UR]ZD*DQHJR SU]\SDGNX

p

o wyborze kolejnego

0 = F( x 0, y 0+1)+F( x 0-1, y 0+1) =

x 0= x s, y 0= y s

piksela decyduje znak

= F( x s, y s+1)+F( x s-1, y s+1) =

ostatnio

ZDUWRFL IXQNFML

narysowany

= x 2

s +( y s+1)2- r 2+( x s-1)2+( y s+1)2- r 2 =

piksel

F( x, y)= x 2+ y 2- r 2

Z SXQNFLH URGNRZ\P

= x 2

2

2

2

s + y s +2* y s+1- r 2+ x s -2* x s+1+ y s +2* y s+1- r 2 =

x 2+ y 2- r 2=0

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

= 4* y s-2* x s+3.

�ĄXN LGHDOQ\

SRPL G]\ SLNVHODPL

kandydatami.

�ó

0RG\ILNDFMD ZDUWRFL pi:

�ó

PrzyjmiMP\ *H RVWDWQLR QDU\VRZDQ\ SLNVHO PD ZVSy�ĄU] GQH x

p

i, yi.

i+1- pi = F( xi+1, yi+1+1)+F( xi+1-1, yi+1+1)-F( xi, yi+1)-F( xi-1, yi+1) =

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

= x

2

i+1 +( yi+1+1)2- r 2+( xi+1-1)2+( yi+1+1)2- r 2+

x

�Łą �ł1 przy wyborze lewego piksela kandydata,

- x 2

i -( yi+1)2+ r 2-( xi-1)2-( yi+1)2+ r 2 =

x

i

:

�Ł�

i + =

1

x

przy wyborze prawego piksela kandydata.

= x

2

2

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

�Łł i

�Łą

y

x 2

2

i+1:= yi +1

przy wyborze dowolnego z pikseli kandydatów,

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

�Ł�

= �Ł�

= 4* yi+6 dla wyboru prawego piksela,

�ó

Oznaczenie:

�Łł�Ł�

1

1

1

1

( x

2

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

f

2

2

i := F( xi- , yi+1)- = ( xi- )2 +( yi+1)2 - r 2 - = xi - xi + yi +2* yi +1 - r 2.

2

4

2

4

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

1

1

�ó

Uwaga: :DUWR�ź fi := F( xi- , yi+1) -

MHVW ]DZV]H ZDUWRFL FD�ĄNRZLW

2

4

parametry procedury: x, y, xe, ye, xc, yc:integer; x := x s- x c, y := y s- y c,

zmienne procedury: p:integer;

xe := x e- x c, ye := y e- y c,

�ó

Kryterium wyboru kolejnego piksela:

dla oktantu nr 1:

xc := x c, yc := y c.

1

�ó

F( xi- , yi+1)>0 �" fi �Ą 0 �ł rysowany lewy piksel kandydat, if StartOctant( x, y, xe, ye) = 1 then

2

1

begin

�ó

F( xi- , yi+1)<0 �" fi < 0 �ł rysowany prawy piksel kandydat, p := 4

2

* y-2* x+3;

1

repeat

�ó

F( xi- , yi+1)=0 �ł rysowany dowolny z pikseli kandydatów -

plot( x+ xc, y+ yc);

2

if p < 0 then p := p+4

ten przypadek nigdy nie zajdzie.

* y+6

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

until Octant( x, y) � 1

end

37

38

�ó

PoczWNRZD ZDUWR�ź f

2

2

2

Algorytm porównawczy Jordana

i:



x V +



y

V �ł r





= 0

⇓

�ó

Za�ĄR*HQLH U\VRZDQ\ �ĄXN RNU JX ] RNWDQWX QU OXE

1

1

f

2

2

0 := F( x 0, y 0)- = F( x s, y s)- = x s - x s + y s +2* y s +1 - r 2 = 2* y s - x s +1.

'OD WDNLHJR �ĄXNX ND*G\ NROHMQ\ SLNVHO U\VRZDQHJR RGFLQND MHVW VVLDGHP

4

4

poprzedniego w kierunku �Ź, �ę albo �ć.

�ó

0RG\ILNDFMD ZDUWRFL fi:

1

1

1

1

Rys. Kryterium wyboru

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

trzy

2

4

2

4

kolejnego piksela dla

piksele

kandydaci

UR]ZD*DQHJR SU]\SDGNX

= x

2

2

2

2

i+1 - xi+1 + yi+1 +2* yi+1 +1 - r 2 - xi + xi - yi -2* yi -1 + r 2 =

rysowany jest ten piksel,

GOD NWyUHJR ZDUWR�ź

= x

2

2

2

2

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

ostatnio

EH]Z]JO GQD ] ZDUWRFL

narysowany

funkcji F( x, y)= x 2+ y 2- r 2

= ( x

piksel

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

Z URGNX WHJR SLNVHOD MHVW

najmniejsza.

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

yi+1 = yi+1

�ĄXN LGHDOQ\

�Łą

2 * yi + 3

JG\ Z\EUDQR SUDZ\ SLNVHO

x

=

i+1 = xi

�Ł�

�ó

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

2 * yi �ł 2 * xi +

�Łł

5

JG\ Z\EUDQR OHZ\ SLNVHO

xi+1 = xi-1

:yZF]DV ZVSy�ĄU] GQH NROHMQHJR SLNVHOD PRJ Z\QLH�ź

2 * y

1

JG\ Z\EUDQR SUDZ\ SLNVHO

= �Łą

i+1 +

�Ł�

1.

xi+1:= xi - 1

przy wyborze lewego piksela kandydata,

�Łł2 * yi+1 �ł 2 * xi+1 +1 JG\ Z\EUDQR OHZ\ SLNVHO

yi+1:= yi

2.

xi+1:= xi

przy wyborze górnego piksela kandydata,

yi+1:= yi +1

3.

xi+1:= xi - 1

przy wyborze lewego górnego piksela kandydata.

yi+1:= yi +1

parametry procedury: x, y, xe, ye, xc, yc:integer; x := x s- x c, y := y s- y c,

zmienne procedury: f:integer;

xe := x e- x c, ye := y e- y c,

�ó

Oznaczenia:

f := F( xi, yi),

F( x 0, y 0) = F( x s, y s) = 0,

dla oktantu nr 1:

xc := x c, yc := y c.

f 1 := F( xi-1, yi) = f -2* xi +1,

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

f

begin

2 := F( xi, yi+1) = f +2* yi +1,

f := 2* y- x+1;

f 3 := F( xi-1, yi+1) = f -2* xi +2* yi +2.

repeat

plot( x+ xc, y+ yc);

�ó

| f 1|<| f 2| & | f 1|<| f 3| �ł wybór lewego piksela kandydata, y := y+1;

| f 2|<| f 1| & | f 2|<| f 3| �ł wybór górnego piksela kandydata, if f < 0 then f := f+2* y+1

| f 3|<| f 1| & | f 3|<| f 2| �ł wybór lewego górnego piksela kandydata, else begin x := x-1; f := f+2*( y- x)+1 end

| f 1|<| f 2| & | f 1|=| f 3| �ł wybór lewego lub lewego górnego piksela, until Octant( x, y) � 1

| f 2|<| f 1| & | f 2|=| f 3| �ł wybór górnego lub lewego górnego piksela, end

w alJRU\WPLH SU]\M WR Z\EyU OHZHJR JyUQHJR

39

40

�ó

3RQLHZD* f 2 �Ą f 3 �Ą f 1 ZL F

2NUJ

| f 1|<| f 2| & | f 1|<| f 3| �" | f 1|<| f 3| �ł

wybór lewego piksela kandydata,

3

2

| f

�ó

$E\ QDU\VRZD�ź SH�ĄHQ RNUJ R URGNX x

2|<| f 1| & | f 2|<| f 3| �" | f 2|<| f 3| �ł

wybór górnego piksela kandydata,

c, y c) i

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

promieniu r Z\VWDUF]\ GRNRQD�ź REOLF]H MHG\QLH GOD

4

1

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

RNWDQWX ZVSy�ĄU] GQH x, y SR]ZDODM Z\]QDF]\�ź

5

8

parametry procedury: x, y, xe, ye, xc, yc:integer; x := x s- x c, y := y s- y c,

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

6

7

zmienne procedury: f 1, f 2, f 3:integer;

xe := x

( y, x), (- y, x), (- x, y), (- x,- y), (- y,- x), ( y,- x), ( x,- y).

e- x c, ye := y e- y c,

dla oktantu nr 1 lub 2:

xc := x c, yc := y c.





Elipsa


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

begin

3

2

�ó

$E\ QDU\VRZD�ź SH�ĄQ HOLSV R URGNX x c, y c) i

f 1 := -2* x+1;

Sy�ĄRVLDFK p i q Z\VWDUF]\ GRNRQD�ź REOLF]H GOD

4

1

repeat

MHGQHM �źZLDUWNL F]\OL GOD GZyFK RNWDQWyZ QS QU

plot( x+ xc, y+ yc);

L 2WU]\PDQH GOD WHM �źZLDUWNL ZVSy�ĄU] GQH x, 5

8

f 3 := f 1+2* y+1;

f 2 := f 3+2* x-1;

y SR]ZDODM Z\]QDF]\�ź SLNVHOH HOLSV\ ]H

if |f 1| < | f 3| then begin x := x-1; f 1 := f 1-2* x+1 end ZV]\VWNLFK �źZLDUWHN

6

7

( x, y), (- x, y), (- x,- y), ( x,- y).

else if |f 2| < | f 3| then begin y := y+1; f 1 := f 2-2* x+1 end else begin x := x-1; y := y+1; f 1 := f 3-2* x+1 end until not (Octant( x, y) in [1, 2])

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

end

procedure Ellipse( xc, yc, p, q: integer);

�ó

3RQLHZD* f

var x, y: integer; pp, qq, pp 2, qq 2, f, fx, fy: longint; 2 �Ą f 3 �Ą f 1 ZL F

begin

| f 1|<| f 3| �" - f 1< f 3 �ł wybór lewego piksela kandydata, x := p;

y := 0;

| f 2|<| f 3| �" f 2<- f 3 �ł wybór górnego piksela kandydata, Z SR]RVWD�Ą\FK SU]\SDGNDFK Z\EyU OHZHJR JyUQHJR SLNVHOD NDQG\GDWD

pp := p* p;

qq := q* q;

pp 2 := 2* pp;

qq 2 := 2* qq;

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

fx := qq 2* p;

fy := 0;

parametry procedury: x, y, xe, ye, xc, yc:integer; x := x s- x c, y := y s- y c,

while fx > fy do

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

begin

zmienne procedury: f 1, f 2, f 3:integer;

xe := x e- x c, ye := y e- y c,

plot( x+ xc, y+ yc);

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

dla oktantu nr 1 lub 2:

xc := x c, yc := y c.

plot(- x+ xc, - y+ yc); plot( x+ xc, - y+ yc); if StartOctant( x, y, xe, ye) in [1, 2] then

y := y+1;

fy := fy+ pp 2;

begin

if f < 0 then f := f+ fy+ pp

f 1 := -2

else begin x := x-1; fx := fx- qq 2; f := f- fx+ fy+ pp end

* x+1;

repeat

end;

plot( x+ xc, y+ yc);

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

repeat

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

* y+1;

f 2 := f 3+2* x-1;

if f 3 < - f 1 then begin y := y+1; f 1 := f 3 end; plot( x+ xc, y+ yc);

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

if - f 3 < f 2 then begin x := x-1; f 1 := f 1-2

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

* x+1 end

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

x := x-1;

fx := fx- qq 2;

end

if f > 0 then f := f- fx+ qq

else begin y := y+1; fy := fy+ pp 2; f := f- fx+ fy+ qq end until x < 0

end

41

42

Znajdowanie konturu

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

�ó

Konturem danego zbioru pikseli nazywamy zbiór wszystkich pikseli

procedure AllContourTracing;

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

var x, y: coordinate;

QDOH*FHJR GR WHJR ]ELRUX

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;

5\V 3U]\N�ĄDGRZ\ ]ELyU

pikseli i jego kontur.

�ó

Znajdowanie wszystkich konturów dowolnego zbioru pikseli:

procedure neighbour(var nx, ny:coordinate; x, y:coordinate; s:direction); procedura AllContourTracing.

begin

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

case s of

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

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

end;

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

�ó

Znajdowanie pojedynczego konturu spójnego podzbioru zbioru pikseli:

2: begin nx:= x;

ny:= y–1 end;

procedura ContourTracing.

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

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

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

end;

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

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

7

6

5

end

end;

piksel piksel

spoza

4

konturu

5\V .ROHMQR�ź SU]HJOGDQLD VVLDGyZ SLNVHOD

zbioru

NRQWXUX Z FHOX ]QDOH]LHQLD QDVW SQHJR

1

2

3

piksela konturu.

43

44

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

:\SH�ĄQLDQLH NRQWXUX

procedure ContourTracing( bx, by:coordinate; bs:direction);

�ó

0HWRG\ Z\SH�ĄQLDQLD NRQWXUX

var x, y, nx, ny: coordinate;

�ó

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

s: direction;

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

begin

^ NRQWUROD Z\PDJD VWDZLDQ\FK SU]HG GDQ\PL SRF]WNRZ\PL `

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

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

if pixel[ bx, by]�ŹLQWHULRU then exit; { punkt ( bx, by QLH QDOH*\ GR ]ELRUX `

QD OHZR RG GDQHJR SLNVHOD R]QDF]D *H QDOH*\ RQ GR ZQ WU]D ]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 `

5\V 3U]\N�ĄDGRZ\

s:= bs;

kontur. Fragmenty

repeat

konturu styczne do

bs:= ( bs+7) mod 8;

linii poziomych nie

if bs= s then

SRZLQQ\ E\�ź

begin

traktowane jako

pixel[ bx, by]:=contour;

SU]HFL FLD NRQWXUX ]

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

liniami poziomymi.

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; $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

{ znajdowanie konturu }

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

x:= bx; y:= by;

IUDJPHQWX NRQWXUX QLH PD *DGQHJR SLNVHOD NRQWXUX WR MHVW WR IUDJPHQW

repeat

konturu styczny do linii poziomej.

pixel[ x, y]:=contour;

repeat

s:= ( s+1) mod 8;

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

5\V 3U]\N�ĄDGRZ\ NRQWXU

until pixel[ nx, ny]�ŹHPSW\

dla którego

x:= nx; y:= ny;

procedura

if odd( s) then s:= ( s+5) mod 8 else s:= ( s+6) mod 8

AllContourFilling

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

]DV\JQDOL]XMH E�ĄG

end;

'RSLHUR XVXQL FLH

z tego konturu

pikseli oznaczonych

NU]\*\NDPL

XPR*OLZL

SUDZLG�ĄRZH Z\NR

nanie tej procedury.

45

46

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

�ó

0HWRGD Z\SH�ĄQLDQLD NRQWXUX SU]H] VSyMQR�ź (przez sianie) -

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

procedure AllContourFilling;

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

var x, y: coordinate; above, below: integer; oddintsect: Boolean; W]Z ]LDUQD NROHMQ\FK EVVLDGyZ D* GR RVLJQL FLD NRQWXUX

begin

for y:= miny to maxy do

procedure Fill( x, y: Integer); { x, y ZVSy�ĄU] GQH ]LDUQD `

begin

begin

oddintsect:=false;

if pixel[ x, y] = empty then

x:= minx;

begin

while x�" maxx do

pixel[ x, y] := interior;

if pixel[ x, y]�ŹFRQWRXU

Fill( x+1, y); Fill( x, y-1); Fill( x-1, y); Fill( x, y+1) then

end

begin

end

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

x:= x+1

end

5\V :\SH�ĄQLHQLH

else

SU]\N�ĄDGRZHJR NRQ

begin

118

WXUX Z\ZR�ĄDQLHP

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

4

3

2

then above:=1 else above:=0;

10

6

5

4

procedury Fill( x, y)

ELD�ĄH OLF]E\

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

9 6 7 5 0 0 1 1

R]QDF]DM NROHMQR�ź

then below:=1 else below:=0;

repeat

8 6

2 2 3 3

czarne cyfry - poziom

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

rekurencji).

then above:= above+1;

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

x

then below:= below+1;

x:= x+1;

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

until ( pixel[ x, y]�ŹFRQWRXU or ( x• maxx);

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

if odd( above) and odd( below) then oddintsect:= not oddintsect; UHNXUHQFML SURZDG]F Z SUDNW\FH GR SU]HSH�ĄQLHQLD VWRVX

if odd( above) �Ź RGG below) then HUURU ^ E�Ą GQD V\WXDFMD `

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

end

end

end;

5\V :\SH�ĄQLHQLH

SU]\N�ĄDGRZHJR NRQ

9 1

WXUX Z\ZR�ĄDQLHP

5 1 6 1 7 1 8 1

procedury

ContourFilling( x, y)

y

0 0 1 0 2 0 3 0

ELD�ĄH OLF]E\

R]QDF]DM NROHMQR�ź

4 1

100 110

czarne cyfry - poziom

rekurencji).

x

47

48

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

FLHQLDQLH NV]WD�ĄWyZ

procedure ContourFilling( x, y: coordinate);

�ó

1D S�ĄDV]F]\(QLH HXNOLGHVRZHM

procedure filling( x, y: coordinate; dy: integer);

var ax, ay, bx, by: coordinate; afind, bfind: Boolean;

Definicja:

begin

�ó

Szkieletem Sk�"Ś zbioru �"Ś QD]\ZDP\ ]ELyU SXQNWyZ R QDVW SXMFHM

if pixel[ x, y]=empty then

Z�ĄDVQRFL

repeat

�Ł�

A � B

�Łś

�ŁŹ∃ ∈Fr �"Ś

�Ł�

ax:= x; ay:= y+ dy;





A


P ∈Sk �"Ś �" P ∈�"Ś





AP


�ŁŹ

= BP

�Ł�

bx:= x; by:= y- dy;





B


∃ ∈Fr �"Ś

�Ł��ŁŹ

∀

�Ł�

C ∈Fr �"Ś CP �Ą AP

while pixel[ ax, ay]=empty do ax:= ax-1;

�Ł�

if ax�Ź x then ax:= ax+1;

�ó

1D S�ĄDV]F]\(QLH G\VNUHWQHM

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

if bx�Ź x then bx:= bx+1;

Definicja:

afind:= pixel[ ax, ay]=empty;

�ó

Piksel konturu nazywamy powtarzalnym JG\ VSH�ĄQLD RQ SU]\QDMPQLHM

bfind:= pixel[ bx, by]=empty;

jeden z trzech warunków:

pixel[ x, y]:=interior;

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

x:= x+1;

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

while pixel[ x, y]=empty do

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

begin pixel[ x, y]:=interior;

Z FLJX SLNVHOL VWDQRZLF\P GURJ RSLVXMF NRQWXU

if ( pixel[ x, ay]=empty) and ( pixel[ x-1, ay]�ŹHPSW\

Definicja:

then

begin if afind

�ó

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

then filling( ax, ay, dy)

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

else afind:=true;

�ó

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

ax:= x

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

end;

NWyUH QLH V SLNVHODPL SRZWDU]DOQ\PL

if ( pixel[ x, by]=empty) and ( pixel[ x-1, by]�ŹHPSW\

until

QLH XVXQL WR *DGQHJR SLNVHOD

then

begin if bfind

then filling( bx, by,- dy)

�ó

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

else bfind:=true;

RSLVD�ź Z]RUFDPL VVLHG]WZ

bx:= x

end;

A A A

A A A

5\V :]RUFH RGSRZLDGDMFH

A A C

x:= x+1

X

A X

pierwszemu (�) i trzeciemu*)

X K

end;

B B B

A

B

(�ą) warunkowi.

B B C

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

0° 90° 180° 270°

JG\ QLH V VSH�ĄQLRQH SR]RVWD�ĄH ZDUXQNL

0° 90° 180° 270°

if bfind

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

�ó X - piksel powtarzalny konturu;

K - piksel konturu;

else begin x:= ax; y:= ay end

until not ( afind or bfind)

�ó A, B, C - grupa pikVHOL R]QDF]RQ\FK W VDP OLWHU PD W Z�ĄDVQR�ź L* FR

end;

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

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

begin

if pixel[ x, y]�ŹHPSW\ then exit;

�ó

%DGDQLH SRZWDU]DOQRFL Z\Paga zatem jedynie sprawdzenia

repeat x:= x-1 until pixel[ x, y]�ŹHPSW\

QDMEOL*V]HJR VVLHG]WZD SLNVHOD NRQWXUX

x:= x+1;

filling( x, y,1)

�ó

3RGHMFLH ZJ GHILQLFML DOJRU\WP FLHQLDQLD SURFHGXUD 'HI7KLQQLQJ

end;

�ó

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

49

50

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

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

procedure Thinning;

procedure DefThinning;

^ FLHQLDQLH QD SRGVWDZLH GHILQLFML V]NLHOHWX `

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

begin

repeat

repeat

finish:=true; s:=0;

finish:=true;

repeat

AllContourTracing;

for y:= miny to maxy do for x:= minx to maxx do for y:= miny to maxy do for x:= minx to maxx do if pixel[ x, y]=contour then if pixel[ x, y]=interior then

begin

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

e:=0; i:=0; m:=0;

if pixel[ nx, ny]=empty then

for s:=0 to 7 do

{ konstrukcja wzorców }

begin pattern:=false;

begin

r:=( s+2) mod 8;

e:= e shl 1; i:= i shl 1; m:= m shl 1; repeat

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

neighbour( nx, ny, x, y, r);

if pixel[ nx, ny]=empty

if pixel[ nx, ny]=empty then

then e:= e or 1

begin first:=false; second:=false;

else

begin i:= i or 1;

q:=( s+1) mod 8;

if pixel[ nx, ny]�ŹLQWHULRU then m:= m or 1

repeat

end

neighbour( nx, ny, x, y, q);

end;

{Ë NRQWUROD ZDUXQNX SRZWDU]DOQRFL �Źf pixel[ nx, ny]�ŹHPSW\ then first:=true; pattern:=( i= m) or {È NRQWUROD ZDUXQNX SRZWDU]DOQRFL `

q:=( q+1) mod 8

((( i and $70)�Ź and (( i and $07)�Ź and (( e and $88)=$88)) or until ( q= r) or first;

((( i and $1C)�Ź and (( i and $C1)�Ź and (( e and $22)=$22)) or q:=( r+1) mod 8;

((( i and $01)�Ź and (( i and $7C)�Ź and (( e and $82)=$82)) or repeat

((( i and $40)�Ź and (( i and $1F)�Ź and (( e and $A0)=$A0)) or neighbour( nx, ny, x, y, q);

((( i and $10)�Ź and (( i and $C7)�Ź and (( e and $28)=$28)) or if pixel[ nx, ny]�ŹHPSW\ then second:=true;

((( i and $04)�Ź and (( i and $F1)�Ź and (( e and $0A)=$0A)) or q:=( q+1) mod 8

{È NRQWUROD ZDUXQNX SRZWDU]DOQRFL �ąntil ( q= s) or second; ((( i and $41)�Ź and (( m and $80)�Ź and (( e and $08)�Ź and pattern:= first and second

((( e and $41)=0) or ((( i and $30)�Ź and (( i and $06)�Ź or end;

((( i and $05)�Ź and (( m and $02)�Ź and (( e and $20)�Ź and r:=( r+2) mod 8

((( e and $05)=0) or ((( i and $C0)�Ź and (( i and $18)�Ź or until ( r= s) or pattern;

((( i and $14)�Ź and (( m and $08)�Ź and (( e and $80)�Ź and if pattern then pixel[ x, y]:=skeleton

((( e and $14)=0) or ((( i and $03)�Ź and (( i and $60)�Ź or else pixel[ x, y]:=contour

((( i and $50)�Ź and (( m and $20)�Ź and (( e and $02)�Ź and end

((( e and $50)=0) or ((( i and $0C)�Ź and (( i and $81)�Ź

end;

if pattern then pixel[ x, y]:=skeleton else finish:=false for y:= miny to maxy do for x:= minx to maxx do end;

if pixel[ x, y]=contour then

for y:= miny to maxy do for x:= minx to maxx do begin pixel[ x, y]:=empty;

if pixel[ x, y]=contour then pixel[ x, y]:=empty finish:=false

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

until finish;

s:=( s+2) mod 8

for y:= miny to maxy do for x:= minx to maxx do until s=0

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

end;

end;

51

52

12

12

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





Filtracja


12


13

123

konturu z zaznaczonymi

�ó

Filtry liniowe - RSLV\ZDQH PDFLHU]DPL RNUHODMF\PL ZS�Ą\Z SLNVHOD L MHJR

2

2

pikselami powtarzalnymi.

2

3 3

1



VVLDGyZ QD QRZ ZDUWR�ź F]\OL NRORU SLNVHOD

&\IU\ ZVND]XM ZDUXQHN

1

2

�ó

)LOWU\ GROQRSU]HSXVWRZH �ą XVXZDQLH V]F]HJy�ĄyZ UR]P\ZDQLH REUD]X

2

3

definicji, z którego wynika

H

I

H

I

H

I

H

I

12

23

SRZWDU]DOQR�ź SLNVHOD NRQWXUX

G 1 1 1 G

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

2

- piksel figury

G 1 1 1 G

G 1 1 1 G

G 1 2 1 G

G 1 1 1 G

J

K

J

K

J

K

J

K

- piksel konturu

�ó

Filtry górnoprzepustowe – w\NU\ZDQLH NUDZ G]L Z\RVWU]DQLH REUD]X

H

I

H

I

- piksel powtarzalny konturu

G 0 0 0 G

G 0 0 0 G

�ó gradient Robertsa

G -1 0 0 G

G 0 0 -1 G

G 0 1 0 G

G 0 1 0 G

1 1 1

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

J

K

J

K

1 2 2 1

FLHQLHQLD V]NLHOHW MDNR ]ELyU

H

I

H

I

1 2 3 3 2 1

G -1 -1 -1 G

G -1 0 1 G

otrzymany w wyniku cyklicznego

1 2 3 2 3 2 1

�ó maska Prewitta

G 0 0 0 G

G -1 0 1 G

1 2 2 1 2 3 2 1

odrzucania punktów konturu nie

G 1 1 1 G

G -1 0 1 G

1 2 2 1

1 2 2 1

E GF\FK SXQNWDPL SRZWDU]DO

J

K

J

K

1 2 1

1 2 2 1

nymi (wg definicji szkieletu) –

H

I

H

I

H

I

1 2 2 1

1 2 2 1

procedura DefThinning. Cyfry

G -1 -2 -1 G

G -1 0 1 G

G -2 -1 0 G

1 2 2 1

1 2 1

ZVND]XM HWDS\ SRGF]DV NWyU\FK

�ó maska Sobela

G 0 0 0 G

G -2 0 2 G

G -1 0 1 G

1 2 3 3 2 1 1 1 1 2 3 2 1

GDQ\ SLNVHO QDOH*\ GR NRQWXUX

G 1 2 1 G

G -1 0 1 G

G 0 1 2 G

1 2 3 2 2 2 2 2 2 2 3 2 1

J

K

J

K

J

K

1 2 2 1 1 1 1 1 1 1 2 2 1

- piksele figury

H

I

H

I

H

I

1 2 2 1

1 2 1

1 2 2 1

1 2 2 1

- piksele szkieletu

G -1 -1 1 G

G -1 1 1 G

G -5 -5 3 G

1 1 1

1 1 1

�ó wykrywanie

G -1 -2 1 G

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

J

K

J

K

J

K

3 4 1

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

H

I

H

I

H

I

3 5 4 1

FLHQLHQLD V]NLHOHW MDNR ]ELyU

G 0 -1 0 G

G -1 -1 -1 G

G 1 -2 1 G

3 4 7 5 4 1

�ó laplasjan

G -1 4 -1 G

G -1 8 -1 G

G -2 4 -2 G

otrzymany w wyniku wykonania

3 4 6 6 6 5 1

DOJRU\WPX NODV\F]QHJR FLHQLDQLD

G 0 -1 0 G

G -1 -1 -1 G

G 1 -2 1 G

3 5 2 2 3 5 4 1

J

K

J

K

J

K

3 4 2 1

2 3 5 1

D ZL F QLH ZJ GHILQLFML V]NLHOHWX

�ó

Filtry nieliniowe

3 5 1

3 5 4 1

– procedura Thinning. Cyfry

�ó NRPELQRZDQH Z\NU\ZDMFH NUDZ G]LH

3 4 5 1

2 3 5 1

ZVND]XM NROHMQR�ź DQDOL]\

(np. pierwiastek sumy kwadratów pionowej i poziomej maski Prewitta)

3 7 5 1

3 5 1

pikseli jako konturu.

�ó medianowy, maksymalny, minimalny

3 4 7 5 4 4 4 4 4 4 5 4 1

�ó operacje logiczne

3 7 6 6 6 6 6 6 6 6 6 5 1

�ó adaptacyjne

3 5 2 2 2 2 2 2 2 2 3 5 1

- piksele figury

3 4 5 1

3 5 1

3 5 2 1

2 3 4 1

- piksele szkieletu

3U]HNV]WD�ĄFHQLD PRUIRORJLF]QH

2 2 1

2 2 1

�ó

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

�ó

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

53

54

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

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

�ó

8N�ĄDG\ ZVSy�ĄU] GQ\FK

�ó

8N�ĄDG\ ZVSy�ĄU] GQ\FK

�ó

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

�ó

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

Y

x

Z

Z

x r

= cos

*

ϕ

X

ϕ

x r

= cos

*

ϕ

z

z

y r

= sin

*

ϕ

y r

= sin

r

*

ϕ

y

y

x R

= cos sin

*

ϕ *

�Ś

r

�Ś

y R

= sin sin

*

ϕ *

�Ś

�Ś

R

R

ϕ

z R

= cos

y

*

�Ś

x

X

Y

X

x

Y

r

ϕ

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

ϕ

r

x

y

�Ł� x'�Łą

�Ł� x�Łą

�ó

3RGVWDZRZH SU]HNV]WD�ĄFHQLD OLQLRZH Z SU]HVWU]HQL

X

Y

p' =



, p =

�ŁŻ �Ł�

�ŁŻ �Ł�

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

dwuwymiarowej:

�Ł� y'�Ł

�Ł� y�Ł

�ó

SU]HVXQL FLH WUDQVODFMD R ZHNWRU

�ó

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

b:

p' = I * p + b

�Ł�1 0�Łą

gdzie I =

�ó

SU]HVXQL FLH WUDQVODFMD R ZHNWRU b:

p' = I

�ŁŻ

�Ł�

* p + b

�Ł�0 1�Ł

�Ł�1 0 0�Łą

�Ł� x'�Łą

�Ł� x�Łą

�ŁŻ

�Ł�

�ŁŻ �Ł�

�ŁŻ �Ł�

�ó

REUyW ZRNy�Ą SXQNWX q R NW 3

p' = D

gdzie I = 0 1 0

p' = y' p



,

= y

* p + (I - D) * q

�ŁŻ

�Ł�

�ŁŻ �Ł�

�ŁŻ �Ł�

�Ł�cosϕ �ł sinϕ�Łą

�ŁŻ�Ł�0 0 1�Ł��Ł

�ŁŻ�Ł� z'�Ł��Ł

�ŁŻ�Ł� z�Ł��Ł

gdzie D = �ŁŻ

�Ł�

�Ł�sinϕ cosϕ �Ł

�ó

REUyW ZRNy�Ą SXQNWX q:

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

�ó

MHGQRN�ĄDGQR�ź R VNDOL k Z]JO GHP SXQNWX q: p' = k

�Ł� d

d

d

xx

xy

xz �Łą

* I * p + (1 - k) * q

�ŁŻ

�Ł�

�ó

V\PHWULD URGNRZD Z]JO GHP SXQNWX q:

p' = -I

gdzie D = d

d

d

przy czym: d FRV . ,

* p + 2 * q

�ŁŻ yx

yy

yz �Ł�

uv

uv

�ŁŻ d

d

d �Ł�

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

�ó

V\PHWULD RVLRZD Z]JO GHP SURVWHM q , q :

p' = G

�Ł�

uv

zx

zy

zz �Ł

1

2

* p + h

1

�Ł�( x

x )

( y

y )

2 ( x

x ) ( y

y )

2 �ł

2

1

�ł 2 �ł

2

*

1

2 �ł

*

1

2 �ł

1 �Łą

G =

,

�ó

MHGQRN�ĄDGQR�ź R VNDOL k Z]JO GHP SXQNWX q: p' = k * I * p + (1 - k) * q 2

2 �ŁŻ

2

2 �Ł�

( x

x )

( y

y )

2 ( x

x ) ( y

y )

( y

y )

( x

x )

2 �ł

1

+ 2 �ł 1 �Ł� * 2 �ł

*

1

2 �ł

1

2 �ł

1

�ł 2 �ł 1 �Ł

�ó

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

p' = F * p + h

2 * ( x * y

x

y )

( y

y )

x

x

�Ł�1 0 0�Łą

�Ł�0�Łą

�Ł� x 0 �Łą

2

1 �ł

*

1

2

�Ł��ł 2 �ł 1 �Łą

�Ł� 1 �Łą

�Ł� 2 �Łą

h =

czym

przy



,





q


, q

;

1 =

2 =

2

2 �ŁŻ

�Ł�

�ŁŻ �Ł�

�ŁŻ �Ł�

�ŁŻ

�Ł�

�ŁŻ �Ł�

�ŁŻ �Ł�

( x

x )

( y

y )

x

x

y

y

gdzie F = 0 1 0

, h = 0

q = y

2 �ł

1

+ 2 �ł 1 �Ł� 2 �ł 1 �Ł

�Ł� 1�Ł

�Ł� 2 �Ł

�ŁŻ

�Ł�

�ŁŻ �Ł�

�ŁŻ 0 �Ł�

�Ł��ł1

�Łą

0

�Ł�2 * a�Łą

�Ł�1 0 �Łą

�Ł� 0 �Łą

�ŁŻ�Ł�0 0 0�Ł��Ł

�ŁŻ�Ł� a�Ł��Ł

�ŁŻ�Ł� z 0 �Ł��Ł

dla osi x= a: G =



, h =

�ŁŻ

�Ł�

�ŁŻ

�Ł� ; dla osi y= b: G =



, h =

�ŁŻ

�Ł�

�ŁŻ

�Ł�

�Ł� 0 1�Ł

�Ł� 0 �Ł

�Ł�0 �ł �Ł

1

�Ł�2 * b�Ł

�ó

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

�ó

rzut perspektywiczny z punktu q

z

a

0 �ł

QD S�ĄDV]F]\]Q

�Ł�

�Łś

z= a:

p' = F *

* (p �ł q) + q + h

�ŁŹ�ŁŹ

�Ł��Ł�

�Ł� z

z

0 �ł

�Ł�

55

56

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

z

Obrazy trójwymiarowe

�ó

F ij( x, y) := ( yi- yj)* x - ( xi- xj)* y + xi* yj - xj* yi, P k := ( xk, yk).

�ó

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

�ó

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

�ó

DQDOLW\F]QD UyZQRFL QLHUyZQRFL QS �ń x�ń2 &

1, P2: F12( x, y) = 0.

0�ń y�ń2 & 0�ń z�ń2 ∨ 0�ń x�ń1 & 0�ń y�ń1 & 2�ń z�ń3.

�ó

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

x

y

1 Z VWURQ SXQNWX

�ó

szkieletowD EU\�ĄD ZLHORFLDQ ILJXUD ZLHORNW





P


QS ZLHU]FKR�ĄNL $ % &

2): F12( x, y) < 0, dla punktów po lewej stronie: F12( x, y) > 0.

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),

�ó

UyZQDQLH SURVWHM SURVWRSDG�ĄHM SU]HFKRG]FHM SU]H] SXQNW P0:

. / 0 1 FLDQ\ $'&% &',+ %&+*

( x 1- x 2)* x + ( y 1- y 2)* y - ( x 1- x 2)* x 0 - ( y 1- y 2)* y 0 = 0.

EFGHIJ, EJNM, EMLF, KLMN, ABGFLK, AKNJID.

�ó

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

�ó

dwa odcinki P1P2 i P3P4 SU]HFLQDM VL �"

RSHUDFMH VN�ĄDGDQLD QS SU]HVNDORZDQ\ R MHGQRN�ĄDGQR�ź V]HFLDQ

sgn(F12( x 3, y 3)) � sgn(F12( x 4, y 4)) & sgn(F34( x 1, y 1)) � sgn(F34( x 2, y 2)).

jednostkowy (tzn. 0�ń x�ń1 & 0�ń y�ń1 & 0�ń z�ń1) ∪ SU]HVXQL W\ WUDQVODFMD

R ZHNWRU V]HFLDQ MHGQRVWNRZ\

�ó

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

�ó

]D SRPRF GU]HZD yVHPNRZHJR EU\�Ą\ OXE

�ó

SURVWRNW R ERNDFK UyZQROHJ�Ą\FK GR RVL x

czwórkowego (figury); np. dla 0�ń x�ń4 & 0�ń y�ń4

min�ń x�ń xmax & ymin�ń y�ń ymax.

& 0�ń z�ń4: (0,0,0,0,(0,0,0,0,0,0,1,0),0,1,0).

�ó

ZLHORNW Z\SXN�Ą\ R ZLHU]FKR�ĄNDFK XSRU]GNRZDQ\FK ]JRGQLH ] UXFKHP

wskazówek zegara P1, P2,... P n: ∀ i∈{1,2,.. n} F i( i mod n + 1)( x, y) < 0.

�ó

:LGRF]QR�ź FLDQ SRZLHU]FKQLH ]DV�ĄRQL WH

�ó

ZLHORNW GRZROQ\ R ZLHU]FKR�ĄNDFK XSRU]GNRZanych zgodnie z ruchem

5\V 3U]HV�ĄDQLDQLH

wskazówek zegara P1, P2,... P n:

FLDQ QLH MHVW

�ó

SRG]LD�Ą QD ZLHORNW\ Z\SXN�ĄH

UHODFM SU]HFKR

�ó

NRQWUROD SDU]\VWRFL OLF]E\ SU]HFL �ź GRZROQHM Sy�ĄSURVWHM Z\FKRG]FHM

GQL D E DQL

z punktu Q ] ERNDPL ZLHORNWD

DQW\V\PHWU\F]Q

�ó

REOLF]HQLH VXP\ NWyZ σ := �ę i=1.. n � P iQP( i mod n + 1) (σ = 360°

(c).

a)

b)

c)

�" Q QDOH*\ GR ZLHORNWD σ = 0° �" Q QLH QDOH*\ GR ZLHORNWD

�ó

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

�ó

SR�ĄR*HQLH RGFLQND Q

�ó

analiza zwrotów wektorów normalnych dla wieORFLDQX Z\SXN�ĄHJR

1Q2 Z]JO GHP ZLHORNWD

�ó

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

�ó

SURVWRNW R ERNDFK UyZQROHJ�Ą\FK GR RVL

�ó

algorytm Ricciego;

�ó

algorytm Appela;

�ó

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

�ó

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

�ó

SR�ĄR*HQLH ZLHORNWD Z]JO GHP LQQHJR ZLHORNWD F] �ź ZVSyOQD

�ó

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

�ó

DOJRU\WP ] EXIRUHP J�Ą ERNRFL

Definicja:

�ó

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

�ó

Punkt P=( xp, yp) SU]HV�ĄDQLD RGFLQHN SURVW l MHOL Sy�ĄSURVWD SR]LRPD

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

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

p, x < xp) przetnie l.

poziomymi.

Definicja:

�ó

Odcinek a SU]HV�ĄDQLD odcinek b MHOL FR QDMPQLHM MHGHQ ] SXQNWyZ RGFLQND

�ó

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

a SU]HV�ĄDQLD RGFLQHN b L RED RGFLQNL VL QLH SU]HFLQDM

b





a


y


l


y


Rys. Ilustracja





P


definicji


a)

b)

c)

d)

P'





c


SU]HV�ĄDQLDQLD

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

x

x

57

58

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





Wyznaczanie cieni


Rys. Wyznaczanie cieni.

�ó

dwukrotne

rozstrzyganie

(UyG�ĄR

a)

b)

c)

d)

problemu

ZLDW�ĄD

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

]DV�ĄDQLDQLD

ekran

�ó

=D�ĄR*HQLD

0RGHORZDQLH RZLHWOHQLD

�ó

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

�ó

(UyG�ĄD ZLDW�ĄD SXQNWRZH OLQLRZH SRZLHU]FKQLRZH

const n ^ PDNV\PDOQD OLF]ED FLDQ `

type SRO\JRQV ^ RSLV NV]WD�ĄWX FLDQ\ `

�ó

odbicia:

I

n

o QDW *HQLH RZLHWOHQLD >O[@

z

l

type faces = array [1.. n] of record colour:integer; polygon:polygons end; Rys. Zjawisko odbicia.

var background LQWHJHU ^ NRORU W�ĄD `

n - wersor normalny do powierzchni

var face: faces;

e

l - wersor kierunku padania promieni

�ą ϕ ϕ

�ó

7\S Z\OLF]HQLRZ\ PR*OLZH SR�ĄR*HQLD NDGUX Z]JO GHP U]XWX FLDQ\

z - wersor kierunku odbicia zwierciadlanego

e ZHUVRU NLHUXQNX SR�ĄR*HQLD REVHUZDWRUD

type location = (outside {a}, inside {b}, other {c,d});

�ó

rozproszone:

kr* I o*FRV3 kr* I o*( n° l)

�ó

FunkcMD VSUDZG]DMFD SR�ĄR*HQLH NDGUX Z]JO GHP U]XWX FLDQ\

�ó

zwierciadlane:

kz* I o*cos m. kz* I o*( z° e) m m∈[1,200]

function Position( x 1, y 1, x 2, y 2: integer; var polygon: polygons): location;

�ó

W�ĄR RZLHWOHQLRZH

kt* I o

�ó

3URFHGXUD Z\SH�ĄQLDMFD NDGU GDQ\P NRORUHP

�ó

FD�ĄNRZLWH QDW *HQLH ZLDW�ĄD RGELMDQHJR

procedure Rectangle( x 1, y 1, x 2, y 2, colour: integer); E

I = ( k

o

t + kr*( n° l) + kz*( z° e) m) * I o, gdzie I o = 2

�ó

3URFHGXUD HOLPLQDFML SRZLHU]FKQL ]DV�ĄRQL W\FK

E o ZLDW�ĄR�ź *UyG�ĄD ZLDW�ĄD >FG@

r

r RGOHJ�ĄR�ź RG (UyG�ĄD ZLDW�ĄD

procedure HiddenFace( x 1, y 1, x 2, y 2, first, last: integer; var face: faces); var x, y, i: integer;

&LHQLRZDQLH SRZLHU]FKQL EU\�Ą ZLHORFLHQQ\FK

begin

�ó

brak cieniowania VWD�ĄD LQWHQV\ZQR�ź RZLHWOHQLD FLDQ\

if first < 1 then first := 1; if last > n then last := n; HIHNW 0DFKD VNRNL RZLHWOHQLD QD NUDZ G]LDFK

for i := first to last do

�ó

metoda Gourauda LQWHUSRODFMD ZDUWRFL QDW *HQLD ZLDW�ĄD RGELWHJR

case Position( x 1, y 1, x 2, y 2, face[ i]. polygon) of

�ó

Z ZLHU]FKR�ĄNDFK ZLHORFLDQX ZHUVRU QRUPDOQ\ MHVW UHGQL

outside: begin { nic nie rób } end;

DU\WPHW\F]Q ZHUVRUyZ QRUPDOQ\FK FLDQ ]DZLHUDMF\FK ZLHU]FKR�ĄHN

inside:

begin { kadr w kolorze iWHM FLDQ\ `

�ó

QD NUDZ G]LDFK OLQLRZD LQWHUSRODFMD QDW *HQLD QD SRGVWDZLH MHJR

Rectangle( x 1, y 1, x 2, y 2, face[ i]. colour); ZDUWRFL Z ZLHU]FKR�ĄNDFK E GF\FK NUDFDPL GDQHM NUDZ G]L

exit {procedure}

�ó

ZHZQWU] FLDQ\ OLQLRZD LQWHUSRODFMD QDW *HQLD QD SRGVWDZLH MHJR

end;

ZDUWRFL Z QDMEOL*V]\FK ] ND*GHM VWURQ\ SXQNWDFK NUDZ G]L OH*F\FK QD

other:

begin ^ GDOV]\ SRG]LD�Ą `

tej samej linii poziomej co dany punkt.

x := ( x 1+ x 2) div 2; y := ( y 1+ y 2) div 2;

�ó

metoda Phonga - interpolacja wersorów normalnych;

HiddenFace( x 1, y 1, x, y, i, last, face);

�ó

Z ZLHU]FKR�ĄNDFK ZLHORFLDQX ZHUVRU QRUPDOQ\ MHVW UHGQL

HiddenFace( x 1, y+1, x, y 2, i, last, face); DU\WPHW\F]Q ZHUVRUyZ QRUPDOQ\FK FLDQ ]DZLHUDMF\FK ZLHU]FKR�ĄHN

HiddenFace( x+1, y 1, x 2, y, i, last, face);

�ó

QD NUDZ G]LDFK OLQLRZD LQWHUSRODFMD ZHUVRUyZ QRUPDOQ\Fh na

HiddenFace( x+1, y+1, x 2, y 2, i, last, face); SRGVWDZLH W\FK*H Z ZLHU]FKR�ĄNDFK E GF\FK NUDFDPL GDQHM NUDZ G]L

exit {procedure}

�ó

ZHZQWU] FLDQ\ OLQLRZD LQWHUSRODFMD ZHUVRUyZ QRUPDOQ\FK QD

end

SRGVWDZLH W\FK*H Z QDMEOL*V]\FK ] ND*GHM VWURQ\ SXQNWDFK NUDZ G]L

end; {case}

OH*F\FK QD WHM VDPHM OLQLL SR]LRPHM FR GDQ\ SXQNW

Rectangle( x 1, y 1, x 2, y 2, background)

�ó

OHG]HQLH SURPLHQL RGWZRU]HQLH GURJL ZV]\VWNLFK SURPLHQL ZLHWOQ\FK

end; {procedure}

SDGDMF\FK QD GDQ\ SLNVHO

59

60

Modelowanie krzywych i powierzchni

�ó

NU]\ZH VNOHMDQH NU]\ZH JL WH DQJ splines)

Modelowanie krzywych:

�ó

funkcja sklejana IXQNFMD JL WD VWRSQLD p MHVW WR IXQNFMD SRNU\ZDMFD

n �Ł� n�Łś

VL SU]HG]LD�ĄDPL ] Uy*Q\PL ZLHORPLDQDPL VWRSQLD p, przy czym funkcja

�ó

i

n�ł

krzywe Béziera:

i





p


( t)

n

=

* t * 1

(

�ę

�ł t)

* p

dla



t

i

∈[ ]

1

,

0

,

0

�ŁŹ�ŁŹ �Ł��Ł�

,

ta, jak i jej p SLHUZV]\FK SRFKRGQ\FK V FLJ�ĄH





p


i


i - punkty kontrolne.

i=0 �Ł� �Ł�

�ó

Z�ĄDVQRFL NU]\ZHM

�ó

funkcje B-sklejane m�ń n, t �ń t �ń...�ń t �ń...�ń t �ń t

�ń...�ń t

�ó

NUDFH Z SXQNWDFK

0

1

m

n

n+1

n+ m+1

p0, p n:

p0, n(0) = p0, p0, n(1) = p n.

1

�Łą

t

dla ∈ [ ,

],

�ó

+

styczna w punkcie p

i

t

i

t

1

0 do odcinka p0p1:

p'0, n(0) = n*(p1-p0).

n

( t) =

i



�Ł�

= ..

0 n + m

,

0 i

�ó

styczna w punkcie p

0

t

dla ∉ [ ,

�Łł

i

t

i

t

],

1

+

n do odcinka p n-1p n: p'0, n(1) = n*(p n-p n-1).

�ó

mieFL VL Z XZ\SXNOHQLX SXQNWyZ NRQWUROQ\FK

t �ł

t + + �ł t

i = ..

0 n + m �ł k

i

t

k i 1

�ó

VSH�ĄQLD ]DOH*QR�ź p

n

( t) =

* n

( t)

�ł

+

* n

( t

k, i

k

,

1 i

k �ł ,

1 i



),

1

+

0, n( t) = (1- t)*p0, n-1( t) + t*p1, n( t).

t + �ł

t + + �ł

k = ..

0 m

k

i

t

i

k

1

i

t

i

1

+

wielom

�ó

iany Bernsteina b

( t Fergusona

i



)

f



( t) :

n, i

n, i

�ó

funkcje B-sklejane n

n

n

�Ł�

m, i ( i=0.. n)

n �Łś

�ł

VWDQRZL ED] GOD IXQNFML

q( t ) =

a * n

( t ).

�ę





p


( t) =

b

( t)

i

n i

* p

b



,

( t)

�ę

=

* t * 1

( �ł t)

dla



i = 0.. n,

i

m, i

0, n

n, i

i

n, i

�ŁŹ�ŁŹ �Ł��Ł�

i

sklejanych stopnia m

i =0

i=0

�Ł� �Ł�

RNUHORQ\FK Z SU]HG]LDOH

n

( t ) = 0 dla t [

∉ t , t

],

+ +

n

n

m, i

i

i m 1

[ t





p


( t) =

f

( t)

m, tn+1] i �śsklejanych” dla

* q

f



,

( t)

�ę

=

b

( t

dla



)

i

�ę

= ..

0 n,

n

( t ) �Ą 0 dla dowolnego t ,

0, n

n, i

i

n, i

n, k

ZDUWRFL SDUDPHWUyZ t

m, i

m+1,.., tn:

i=0

k = i

�ó

Z�ĄDVQRFL

n

n

�ę

= 1 dla ∈

�Ł�

n

( t )

t

[ t , t

].

n �Łś �Ł� k �ł 1�Łś

m, i

m

n+1

k + i

k

�ó

RJUDQLF]RQ\ L ]ZDUW\ QRQLN

f

( t) =

f



,

1

( t) =

*

* (

�ę

�ł )

1

* t

dla



i = 1.. n,

i =0

n,0

n, i

�ŁŹ�ŁŹ �Ł��Ł� �ŁŹ�ŁŹ

�Ł��Ł�

k

k

�Ł� �Ł�

�ł i

�ó

ZDUWRFL QLHXMHPQH

k = i

�Ł�

�Ł�

i

�ó

unormowanie:

p =





q


dla




i

�ę

= 0.. n

, q = p

, q = p �ł p

dla



i

�ł

= ..

1 n,

i

k

0

0

i

i

i 1

k =0

�ó





krzywe sklejane


b


( t) = f

( t) �ł f

( t

dla



)

i

+

= 0.. n �ł

b



,

1

( t) = f

( t).

krzywe opisane parametrycznie funkcjami sklejanymi, przy czym

n, i

n, i

n, i 1

n, n

n, n

�"VNOHMHQLDŹLHORPLDQyZ QDVW SXM GOD W\FK VDP\FK ZDUWRFL SDUDPHWUX

�ó

wyznaczanie punktów krzywej:

�ó

algorytm de Casteljau:

p0, n( t) = (1- t)*p0, n-1( t) + t*p1, n( t) n

for i := 0 to n do r

t

[

∈ t , t

],

i := p i;

�ó

m

n+

krzywe B-sklejane

1

: q( t ) =

n

( t ) p

�ę

,

for j := 1 to n do

m,

*

i

i

p - punkty kontrolne.

i 0

i

=

for i := 0 to n- j do r i := r i + t * (r i+1 - r i);

�ó

zmiana punktu p i RGNV]WD�ĄFD NU]\Z ORNDOQLH W\ONR GOD t∈[ ti, ti+ m+1].

p0, n( t) := r0.

�ó

algorytm Hornera:

�ó

wyznaczanie punktów krzywej:

( t < 0,5)

n �Ł� n

n

�Łś �Ł� t �Łś i

l := 1; k := 1;





p


( t

�ó

algorytm de Boora-Coxa dla t∈( t

n

) = 1

( �ł t) *

,

0

�ę �ŁŹ�ŁŹ �Ł��Ł�*�ŁŹ

�Ł� * p i

k, tk+1):

c := t / (1- t); s := p

�Ł� i �Ł� �Ł�1�ł t �Ł�

for i := 0 to m do r

n;

i=0

i := p k- m+ i;

for i := 1 to n do

for j := 1 to m do

begin l := l

for i := 0 to m- j do r

*(1- t); k := k*( n- i+1) /i; s := c * s + k * p n- i end; i := r i + ( t- ti+ j)/( ti+ m+1- ti+ j) * (r i+1 - r i); p

q( t) := r

0, n( t) := l * s.

0.

�ó

algorytm Hornera: ( t > 0,5)

n �Ł� n

n

�Łś �Ł�1�ł t �Łś i

n

k

l := 1; k := 1;





p


( t

0 n

) = t *

,

�ę �ŁŹ�ŁŹ �Ł��Ł�*�ŁŹ

�Ł� * p n�ł i

q( t ) =

n

( t ) p

�ę

=

n

( t ) p dla t

�ę

∈( t , t

)

m,

*

i

i

m,

*

i

i

k

k +1

c := (1- t) / t; s := p

�Ł� i �Ł� �Ł� t �Ł�

0;

i=0

i =0

i = k �ł m

for i := 1 to n do

begin l := l* t; k := k*( n- i+1) /i; s := c * s + k * p i end; p0, n( t) := l * s.

61

62