-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

L

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

2

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

•

S

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

3

B

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

b

C

r

  - 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

NW

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

4

S

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

1

,y

1

,x

2

,y

2

,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

5

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

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

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

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

49

64

78

87

103 121 120 101

99

99

99

99

99

99

99

99

72

92

95

98

112 100 103

99

99

99

99

99

99

99

99

99

Rys.  Macierze kwantyzacji Q

8×8

 dla luminancji i dla chrominancji.

Rys. Linearyzacja metod

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

6

•

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 Î

1

+

, Î

1

–

, Î

1

|

, Î

2

+

, Î

2

–

, Î

2

|

, ..., Î

n

+

, Î

n

–

, Î

n

|

, I

n

.

 

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

a)

b)

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

i

I

i+1

Î

i+1

+

Î

i+1

|

Î

i+1

–

H

L

2:1

2:1

H

L

H

L

2:1

2:1

2:1

2:1

wiersze

kolumny

7

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:

(

)

(

)

(

)

(

)

∃ >

∀ ∈

∃

⊂

∈

∃

⊂ ′

∈





















r

h

r

r

r

r

α

    

    

     

k

    

k

P

Q

P

Q

Q

P

Q

1

1

Fr

k

,

Fr

,

&

k

,

Fr

,

Ω

Ω

Ω

2

2

,

gdzie

Fr

Ω

 - brzeg obszaru 

Ω,

Fr

Ω Ω Ω

= ∩ ′

 ,

Ω

 GRPNQL FLH REV]DUX Ω,

Ω Ω

Ω

= ∪ Fr

,

′

Ω

 GRSHáQLHQLH REV]DUX Ω,

{

}

′ =

∉

Ω

Ω

P

,

(

)

k

,

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

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

2

, 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

64

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

8

G

EOMETRIA  

D

YSKRETNA

QVVLDG

piksela

P

EVVLDG

piksela

P

QVVLDG

piksela

P

EVVLDG

piksela

P

piksel P

EVVLDG

piksela

P

5\V 6VLHG]L SLNVHOD P.

QVVLDG

piksela

P

EVVLDG

piksela

P

QVVLDG

piksela

P

'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

9

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

a)

d)

b)

×

c)

×

Rys.

 

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

b)

]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);

d)

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)

 

=

 

0

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

10

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)

    b)

    c)

E

    d)

A

    e)

Æ

E

E

A

E

Æ

A

E

A

E

A

E

A E

Æ

A

E

A

E

A

E

A E

A E

A E

A E

Æ

Æ

Æ

A E

Æ

Æ

A E

Æ

E A

E A

E

A

Æ

A

E A

E

A

E

A

Æ

A

E

A

E

A

A

E A

E

A

A

A

Æ

A

A

A

E A

A

A

A

E A

A

A

A

E

A

A

A

A

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

11

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

•

Wu

•

VWUXNWXUDOQH  QLH QDGDM VL

Oznaczenia:     (xs , ys  SRF]WHN RGFLQND

xe , ye) - koniec odcinka.

12

Algorytm podstawowy

•

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

y = m * x + b

m

 ZVSyáF]\QQLN NLHUXQNRZ\

b - wyraz wolny

•

dwa przypadki:

m

m = -1

=1

|    | < 1

|    | < 1

|    | > 1

|    | > 1

 m

 m

 m

 m

α

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' = 

1

m

,  b' = 

−

b

m

,  przy czym wówczas |m'| 

≤ 1,

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

•

|m| 

≤ 1

xe ≠ xs,

m

y

y

x

x

=

−
−

e

s

e

s

,      

b

y

m x

=

−

s

s

*

.

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)

13

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

1

m

.

 ∆

 ∆ 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)

14

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

d

d

 2

 1

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,

yi

yi

yi

+ =

+







1

1

:

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.

15

•

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) =
=

2

0

1

1

2

0

1

0

*

*

(

)

(

),

(

).

∆

∆

∆

y

x

pi

yi

yi

y

pi

yi

yi

−

≥

+ −

=

<

+ −

=







JG\

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)

16

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

y

i

y

i

y

i

+ =

+







1

1

:

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

c

y

y

x

y

x

y

=

−

−

−

*

*

*

(

)

V

H

H

V

V H

,    b

c

x

x

x

y

x

y

=

−

−

−

*

*

*

(

)

H

V

H

V

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+

1

2

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

1

2

) + c] =

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

b

2

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

b

2

].

:DUWRü fi jest zawsze ZDUWRFL FDáNRZLW.

17

•

F(xi+1,yi+

1

2

) > 0

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

F(xi+1,yi+

1

2

) < 0

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

F(xi+1,yi+

1

2

) = 0

⇒ wybór dowolnego piksela kandydata,

przyj

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

•

3RF]WNRZD ZDUWRü fi:

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

b

2

] =

= F(xs,ys) + a + [

b

2

] =

= a + [

b

2

].

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) =

= 

a

b

fi

yi

yi

a

fi

yi

yi



JG\

JG\

≥

+ −

=

<

+ −

=







0

1

1

0

1

0

(

),

(

).

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)

18

Algorytm porównawczy Jordana

•

Za

á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ü

1.

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

przy wyborze prawego piksela kandydata,

2.

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

przy wyborze górnego piksela kandydata,

3.

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

c

y

y

x

y

x

y

=

−

−

−

*

*

*

(

)

V

H

H

V

V H

,    b

c

x

x

x

y

x

y

=

−

−

−

*

*

*

(

)

H

V

H

V

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.

19

•

|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)

20

$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

1

4

].

'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<0

pi<0

pi≥0

pi+2∆y<0

pi+2∆y<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≥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 <

0

≤ pi

•

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

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

pi

pi

y

y

x

pi

y

pi

y

+ −

=

−







< −
≥ −

4

8

8

2

6

6

*

*

*

*

*

∆
∆

∆

∆
∆

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

0000

0000

0000

0000

1000

0001

0001

0010

0100

0100

0010

0100

1000

0010

0001

0010

0001

0001

21

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

22

Algorytm strukturalny Metzgera-Bronsa

0

1

2

3

4

5

6

7

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

3

1

Rys.

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

1

2

0170213

’ 0

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 ( )

1

2

u

u

= 







, 

K2

2

( )

u

u

u

= − 







     lub     

K1

2

( )

u

u

u

= − 







, 

K2

2

( )

u

u

= 







.

•

Podstawienie warto

FL SRF]WNRZ\FK i := 0,

a0 := ∆y, 

A0 := "1",

b0 := ∆x-∆y,

B0 := "0".

23

•

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

ci

di

=

áDFXFKyZ Ci  (ri≥1).

•

ri  FDáNRZLWH ⇒

NRG áDFXFKRZ\ RGFLQND

i

d

i

r

i

C

i

D

i

r

i

C









)

(

)

(

1



K

K

.

•

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

áDFXFKyZ

Ai

Ci

ri

DiCi

ri

+ =

+

+

1

1

1

1

:

([ ]

)

([ ]

)

h

h2

     i

bi+1 := di - (ci mod di

áDFXFKyZ

Bi

Ci

ri D

iCi

ri

+ =

1

1

:

([ ])

([ ])

h

h2

.

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)

24

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)

25

$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

1

2

].

'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

 

   

0

1 0

2 1

2

1

i

i

i

−

=

∏

α

α

β

,

gdzie

α

α

β

j

j

=

∑

=

1

2

,

A

A

A

i

i

n

=

∏

=

1

1

β

...

 ,



n

n

A

AA

A

...

=

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

α

β

2

 = 

α div (2β)   lub   

α

β

2

+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\

α

α

α

β

j

k

k

j

j

=

−









=

−

∑

round

2

1

1

lub

α

α

β α

β

j

k

k

j

j

=

−

+









=

−

∑

2

1

1

 div (2

β).

•

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

 

   

0

1 0

2 1

2

1

i

i

i

−

=

∏

α

α

β

,

gdzie

  

A

A

A

i

i

n

=

∏

=

1

1

β

...

 ,



n

n

A

AA

A

...

=

,

 α div (2β)

dla   

λ

j

 + 

α mod (2β) < 2β,

]D α

j

=



 α div (2β) +1

dla  

λ

j

 + 

α mod (2β) ≥ 2β,

λ

j

 = (

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

czyli

λ

1

 = 

β,

 λ

j

 + 

α mod (2β)

dla   

λ

j

 + 

α mod (2β) < 2β,

λ

j+1

=



 λ

j

 + 

α mod (2β) − 2β

dla  

λ

j

 + 

α mod (2β) ≥ 2β,

26

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

27

„

= 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).

28

:\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

29

$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

y

i

x

i

k

i

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

yi

yi

yi

+ =

+







1

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)

30

$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 

m

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

yi

yi

yi

+ =

+







1

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

n

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

n

.

•

=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

m

 

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

em {2

m

-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

n

};

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

end;

plot(xe, ye, em, em)

31

à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

C

S

E

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

u

v

.

u

v

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).

32

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)

1

2

3

4

5

6

7

8

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

33

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

1

2

3

4

5

6

7

8

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

Dla orientacji dodatniej i dla oktantów:

•

1, 8:  y

]ZL NV]DQH R 

x

r

y

: [

]

=

−

+

2

2

1
2

,

•

2, 3:  x zmniejszane o 1,  

y

r

x

: [

]

=

−

+

2

2

1
2

,

•

4, 5:  y zmniejszane o 1,  

x

r

y

:

[

]

= −

−

+

2

2

1
2

,

•

  [ ]ZL NV]DQH R 

y

r

x

:

[

]

= −

−

+

2

2

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

34

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

r

r

r

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

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

1

r

]DSHZQLD ]PLDQ  ZDUWRFL

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

1

r

.

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

35

Algorytm Honga

•

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

1

r

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

•

Oznaczenie:
k := [log

2 

r

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

•

2k-1 

≤ r < 2k  &  2-k < 

1

r

 

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

1

r

.

•

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

x

n x n

n

= −

+ + −

+

1

1

2

2

1

2

2

!

..

(

)

(

)!

...

*

*

    sinx

x

x

n x n

n

= −

+ + −

+

+

+

1

3

3

1

2

1

2

1

!

..

(

)

(

)!

...

*

*

•

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

1

2

*x

2,  sinx 

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

RWU]\PXMH VL  QDVW SXMFH Z]RU\

xi+1 = xi*(1-

1

2

*(∆ϕ)

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

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

1

2

*(∆ϕ)

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

36

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\

d

d

2

1

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

x

i

x

i

x

i

+ =

−







1

1

:

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

xi

r

yi

1

2

1 2

=

−

−

+

(

) ,    d

r

yi

xi

2

2

1 2

1

=

−

+

−

−

(

)

(

) .

•

d1>d2 ⇔ xi

r

yi

r

yi

xi

−

−

+

>

−

+

−

−

2

1 2

2

1 2

1

(

)

(

)

(

)

⇔ 2

1

2

2

1 2

*

*

(

)

xi

r

yi

− >

−

+

⇔ (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

37

•

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

38

$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

x

i

x

i

x

i

+ =

−







1

1

:

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-

1

2

,yi+1)-

1

4

 = (xi-

1

2

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

1

4

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

•

Uwaga:

:DUWRü fi := F(xi-

1

2

,yi+1) - 

1

4

MHVW ]DZV]H ZDUWRFL FDáNRZLW

•

Kryterium wyboru kolejnego piksela:

•

F(xi-

1

2

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

•

F(xi-

1

2

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

•

F(xi-

1

2

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

ten przypadek nigdy nie zajdzie.

39

•

Pocz

WNRZD ZDUWRü fi:

        















⇓

=

−

+

0

2

2

2

r

y

x

V

V

f0 := F(x0,y0)-

1

4

 = F(xs,ys)-

1

4

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

•

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

1

2

,yi+1+1) - 

1

4

 - F(xi-

1

2

,yi+1) + 

1

4

 =

= 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 =

=

+

−

+







2

3

2

2

5

*

*

*

yi

yi

xi

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

=

+ +

+ −

+ +







2

1 1

2

1

2

1

1

*

*

*

yi

yi

xi

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

40

Algorytm porównawczy Jordana

•

Za

á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ü

1.

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

przy wyborze lewego piksela kandydata,

2.

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

przy wyborze górnego piksela kandydata,

3.

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

41

•

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

42

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).

1

2

3

4

5

6

7

8

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).

1

2

3

4

5

6

7

8

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

43

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

1

2

3

4

5

6

7

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.

44

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

45

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

46

:\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.

47

{ 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 (x•maxx);

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

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

end

end

end;

48

•

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

end

0

1

2

3

4

5

6

7

8

9

10

11

0

1

2

3

2

3

4

5

6

6

7

8

x

y

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

2

3

10 11

8

7

6

1

4

0

5

9

0

0

0

0

1

1

1

1

1

0

0

1

x

y

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).

49

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

50

FLHQLDQLH NV]WDáWyZ

•

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

•

Szkieletem Sk

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

ZáDVQRFL

P

P

A

B

A

B

AP

BP

C

CP

AP

∈

⇔

∈

∃ ∈

∃ ∈

≠
=

∀ ∈

≥





















Sk

Fr

Fr

Fr

Ω

Ω

Ω
Ω

Ω

•

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

•

Piksel konturu nazywamy powtarzalnym

 JG\ VSHáQLD RQ SU]\QDMPQLHM

jeden z trzech warunków:

1.

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

2.

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

3.

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

A A A

5\V :]RUFH RGSRZLDGDMFH

A A C

X

A X

pierwszemu (

Å) i trzeciemu

*)

X K

B B B

A

B

(

Æ) warunkowi.

B B C

0

°

 90

°

0

°

 90

°

 180

°

 270

°

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

0

°

 90

°

 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.

51

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

52

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