Algorytmy rastrowe:

rysowanie okręgu i

elipsy.

Urządzenia rastrowe:



Monitor



Kartka papieru w drukarce,ploterze

Obraz składa się ze skończonej liczby

elementów nazywanych pikselami.

Piksele tworzą siatkę prostokątną

uporządkowana w l linii i k kolumn.

l x k –rozdzielczość urządzenia graficznego.
Aspekt urządzenia graficznego - odległość

między środkami sąsiednich pikseli w
poziomie do odległości w pionie.

Rasteryzacja

Zamiana ciągłej funkcji 2D na funkcję
dyskretną (rysowanie okręgu na podstawie
równania okręgu).

Problem sprowadza się do wyboru pikseli,
którym trzeba nadać kolor, aby w efekcie
otrzymać wymagany kształt.

Algorytmy generacji
krzywych



Algorytmy numeryczne



Algorytmy inkrementacyjne

Algorytmy numeryczne -
idea

Numeryczna analiza krzywej podanej w
sposób jawny przez funkcję opisującą
krzywą i funkcje będące różniczkami
cząstkowymi.

Algorytmy
inkrementacyjne - idea



Generacja krzywych od punktu
początkowego do punktu końcowego.
Na podstawie punktu bieżącego liczy się
elementarne przesunięcie określające
punkt następny.



Wykorzystują własności geometryczne
krzywych w przestrzeni dyskretnej
(rastrowej) i ich własności strukturalne.

Algorytmy rysowania
okręgu:

Algorytm Bresenhama



dla 1/4 okręgu



dla 1/8 okręgu

Algorytm DDA(Digital Differential Analized)

Algorytm Bresenhama

Założenia:



równanie okręgu x

2

+y

2

=R

2



R - liczba naturalna



Środek okręgu w początku układu współrzędnych



kreślona jest ¼ okręgu



Kierunek kreślenia – ruch wskazówek zegara



Kolejne punkty wybierane są metodą

inkrementacyjną (dla ¼ okręgu wybierany jest

jeden z trzech sąsiednich punktów rastra)

Algorytm Bresenhama

Założenia:



Aspekt ekranu a=p/q ≠1



Ośmiokierunkowy wybór pikseli
przybliżających krzywą F(x,y)=p

2

x

2

+q

2

y

2

-

q

2

R

2

=0

Algorytm Bresenhama

Punkty okręgu generowane przez
algorytm

Algorytm Bresenhama -
idea

Taki wybór punktów aby różnica pomiędzy
promieniem poprowadzonym do
wybranego punktu rastra, a rzeczywistym
promieniem R była jak najmniejsza.

Wybór sprowadza się do analizy trzech
pikseli.

Algorytm Bresenhama



Analizę zaczynamy od punktu P

0

=(0,R)



Istotny jest punkt, którego współczynnik
kierunkowy wynosi -1

Dzieli on ćwiartkę okręgu na dwa fragmenty,

w których wybieramy różne piksele.

Algorytm Bresenhama

W pierwszym fragmencie wybieramy

pomiędzy pikselami A i B w drugim
pomiędzy B i C

Algorytm Bresenhama
Analiza punktów środkowych

Kryterium Van Akenema – rozstrzygnięcie, środek

którego z pikseli leży bliżej przybliżanego
okręgu.

Wybór zależy od wartości funkcji f w punkcie

środkowym S między alternatywnymi pikselami.

I: II:
fs

i

=f(x

i

+1,y

i

-1/2)

fs

i

=f(x

i

+1/2 ,y

i

-1)

fs

i

> 0 to punk zew. -> wybieramy I:B, II:C

fs

i

< 0 to punk wew. -> wybieramy I:A, II:B

Algorytm Bresenhama
Wartość zmiennej
decyzyjnej

Dla startowego piksela P

0

=(x

0

,y

0

)=(0,R)

wartość zmiennej decyzyjnej:

fs

0

=f(x

0

+1,y

0

-1/2)=p

2

(0+1)

2

+q(R-1/2)

2

-

q

2

R

2

=

=p

2

-q

2

R+q

2

/4

Algorytm Bresenhama
Wartość zmiennej
decyzyjnej

Dla pierwszego fragmentu okręgu p

2

x<q

2

x

zwiększamy wartość x o 1 i wybieramy A lub B
Przejście:

P

i

-> P

i+1

=A

x

i+1

=x

i

+1 y

i+1

=y

i

f(x

i+1

+1, y

i+1

-1/2)=f(x

i

+1, y

i

-1/2 ) +2p

2

x

i+1

+p

2

lub krócej:

fs

i+1

=fs

i

+2p

2

x

i+1

+p

2

Przejście:

P

i

-> P

i+1

=B

x

i+1

=x

i

+1 y

i+1

=y

i

-1

fs

i+1

=fs

i

+2p

2

x

i+1

+p

2

-2q

2

y

i+1

Algorytm Bresenhama
Wartość zmiennej
decyzyjnej

Dla drugiego fragmentu okręgu p

2

x>q

2

x

zwiększamy wartość y o 1 i wybieramy B lub

C.

Wybór B,lub C powinien zależeć od nowej

wartości

f(x

i+1

+1/2, y

i+1

-1), a nie od starej f(x

i+1

+1,

y

i+1

-1/2).

Różnica pomiędzy nimi wynosi:

Algorytm Bresenhama

Nowa wartość zmiennej
decyzyjnej

Poprzednio obliczoną zmienną decyzyjną

wystarczy zmodyfikować o tę wartość:

Korzystając z rekurencji przeanalizować

wybór punktu B lub C.

Algorytm Bresenhama
Wartość zmiennej
decyzyjnej

Przejście P

i

-> P

i+1

=B

x

i+1

=x

i

+1 y

i+1

=y

i

-1

fs

i+1

= f(x

i+1

+1/2, y

i+1

-1)=fs

i

+2p

2

x

i+1

-

2q

2

y

i+1

+q

2

Przejście P

i

-> P

i+1

=C

x

i+1

=x

i

y

i+1

=y

i

-1

fs

i+1

=fs

i

-2q

2

y

i+1

+q

2

Algorytm Bresenhama -
przypomnienie



p,q,R – liczby naturalne



Znak zmiennej decyzyjnej fs

i

decyduje o

wyborze piksela.

Algorytm Bresenhama dla
elipsy

Ta sama procedura jak przy rysowaniu koła.
Założenia:



Równanie elipsy:



Rysujemy w I ćwiartce układu współrzędnych



Zaczynamy od pkt (0,b) zgodnie z ruchem
wskazówek zegara.



W każdym kroku stawiamy symetrycznie 4
pkt. elipsy.

Algorytm Bresenhama dla
elipsy

Założenia:



Ośmiokierunkowy wybór pikseli
przybliżających krzywą F(x,y)=b

2

x

2

+a

2

y

2

-

a

2

b

2

=0



Początkową osią wiodącą jest oś OX



W punkcie zmiany osi wiodącej
współczynnik nachylenia stycznej do elipsy
wynosi -1 (tg 135

o

)

Algorytm Bresenhama dla
elipsy



Kryterium przejścia osi wiodącej z OX na
OY.

Algorytm Bresenhama dla
elipsy



Do określenia, który piksel znajduje się
bliżej kreślonej figury stosujemy jak dla
okręgu kryterium Van Akenema

Algorytm DDA



Podstawą rysowania figury jest postać
opisującego ją równania różniczkowego.



Algorytm korzystający z operacji
mnożenia i funkcji trygonometrycznych,
wolna realizacja.



Zasada działania – równoczesne
zwiększanie x i y o niewielki przyrost ε.



Rysujemy 1/8 okręgu.

Algorytm DDA



Postać równania różniczkowego przy
założeniach:

środek okręgu=początek układu

współrzędnych

Algorytm DDA



Obliczanie współrzędnych kolejnych punktów:
x

i+1

=x

i

+εy

i

y

i+1

=y

i

-ε

2

y

i

- ε x

i

Wartości przyrostów nie są stałe i muszą być

obliczane dla każdego x,y przy użyciu
operacji mnożenia.



Mnożenie można zastąpić przesunięciami
przy

założeniu:

Algorytm DDA



Algorytm ten nie rysuje okręgu lecz
elipsę ale dla małych ε, błąd ten można
uważać za pomijalnie mały.

Dokładny algorytm DDA -
okrąg



Punktem wyjścia dla tej metody jest
równanie parametryczne okręgu o
promieniu R i środku w początku układu
współrzędnych.

Dokładny algorytm DDA -
okrąg

Zależności trygonometryczne dla sąsiednich

punktów okręgu:

Dokładny algorytm DDA -
okrąg

Definiujemy Θ jako kąt pomiędzy
promieniami poprowadzonymi do dwóch
sąsiednich punktów okręgu.

Dokładny algorytm DDA -
okrąg

Po przekształceniach

trygonometrycznych:

postać macierzowa:

Dokładny algorytm DDA -
okrąg



Z rekurencyjnego charakteru zależności
wynika, że wielkość kąta Θ jest stała dla
każdej iteracji.



Wielkość kąta Θ zależy od liczby punktów
tworzących okrąg, a ta zwiększa się wraz z
promieniem.



Dla małych Θ algorytm generuje ciągłe i
dokładne łuki ale dla małych promieni bardzo
wydłuża się czas kreślenia jeżeli zakres
rozdzielczości zostanie przekroczony.