Tomasz Hebisz
Grafika komputerowa
Instytut Sterowania i Systemów Informatycznych
1. Transformacje obiektów
Mówiąc o grafice komputerowej należy dużą uwagę zwrócić na przekształcenia figur
geometrycznych na płaszczyźnie i w przestrzeni. Ważnym zagadnieniem jest sposób
realizacji transformacji obiektów graficznych. Najczęściej obiekty takie są opisywane
zbiorem wyróżnionych punktów, dlatego też omawiane transformacje będą dotyczyły
pojedynczych punktów, a nie np. równań algebraicznych opisujących krzywe.
1.1. Przekształcenia punktów na płaszczyźnie
(przekształcenia 2D)
1.1.1. Przesunięcie (translacja)
Dowolny punkt na płaszczyźnie, opisany za pomocą pary (x, y), można przesunąć
na nową pozycję dodając do współrzędnych punktu wielkość przesunięcia. Obrazem
punktu P = (x, y) po przesunięciu o wektor t = [t
x
, t
y
] jest punkt P
0
= (x
0
, y
0
) taki,
że
x
0
= x + t
x
,
y
0
= y + t
y
.
Jeżeli zdefiniuje się wektory kolumnowe:
P =
"
x
y
#
,
P
0
=
"
x
0
y
0
#
,
T =
"
t
x
t
y
#
,
to równanie translacji można zapisać również macierzowo:
"
x
0
y
0
#
=
"
x
y
#
+
"
t
x
t
y
#
albo
P
0
= P + T
1.1.2. Skalowanie
Figury, opisane za pomocą punktów na płaszczyźnie, mogą być skalowane poprzez
mnożenie odciętych przez współczynnik s
x
(wzdłuż osi x) oraz mnożenie rzędnych przez
współczynnik x
y
(wzdłuż osi y):
x
0
= s
x
x,
y
0
= s
y
y,
"
x
0
y
0
#
=
"
s
x
0
0
s
y
#
·
"
x
y
#
albo
P
0
= S · P.
1. Transformacje obiektów
2
Skalowanie odbywa się względem początku układu współrzędnych. Gdy współczynniki
skalowania są mniejsze od 1 (s
x
< 1 i s
y
< 1), to wówczas obiekt zmniejsza się i przybliża
się do środka układu współrzędnych. W przypadku, gdy współczynniki skalowania są
większe od 1 (s
x
> 1 i s
y
> 1), to wówczas obiekt zwiększa się i oddala od środka układu
współrzędnych.
Jeżeli współczynniki skalowania posiadają równą wartość (s
x
= s
y
), wówczas proporcje
obiektu nie ulegają zmianie i mówi się o skalowaniu jednorodnym. Jeżeli natomiast
współczynniki skalowania są różne (s
x
6= s
y
), to proporcje skalowanego obiektu ulegną
zmianie. W takim przypadku ma się do czynienia z tzw. skalowaniem niejednorodnym.
1.1.3. Obroty
Punkty mogą być obracane o kąt ϕ wokół początku układu współrzędnych. Najlepiej
jest
wtedy przedstawić
obiekt
w
układzie
współrzędnych
biegunowych.
Wtedy
współrzędnymi punktu P będą odległość r od początku układu i kąt ψ między osią x,
a prostą OP . Współrzędne kartezjańskie punktu P
są określone zależnościami
trygonometrycznymi
x = r · cos (ψ),
y = r · sin (ψ).
Obrazem punktu P po obrocie o kąt ϕ wokół początku układu jest punkt P
0
o współrzędnych biegunowych (r, ψ + ϕ). Stąd
x
0
= r · cos (ψ + ϕ) = r · cos (ψ) · cos (ϕ) − r · sin (ψ) · sin (ϕ),
y
0
= r · sin (ψ + ϕ) = r · cos (ψ) · sin (ϕ) − r · sin (ψ) · cos (ϕ),
zatem ostatecznie otrzymuje się
x
0
= x · cos (ϕ) − y · sin (ϕ),
y
0
= x · sin (ϕ) + y · cos (ϕ).
W postaci macierzowej przekształcenie takie można zapisać następująco
"
x
0
y
0
#
=
"
cos (ϕ) − sin (ϕ)
sin (ϕ)
cos (ϕ)
#
·
"
x
y
#
albo
P
0
= R · P.
1.2. Łączenie przekształceń
Jeżeli zachodzi potrzeba dokonania transformacji obiektu względem punktu P
0
=
(x
0
, y
0
), który nie jest środkiem układu współrzędnych, to takie przekształcenie można
złożyć z poprzednich. W tym celu trzeba najpierw przesunąć punkt P
= (x, y)
o wektor [−x
0
, −y
0
], następnie obrócić punkt P
0
= (x − x
0
, y − y
0
), a następnie wykonać
przesunięcie o wektor [x
0
, y
0
].
Na podstawie powyższego przykładu można zauważyć, że byłoby wygodnie traktować
wszystkie przekształcenia w sposób jednolity, co pozwalałoby na łatwe łączenie różnych
przekształceń.
1. Transformacje obiektów
3
Reprezentacje macierzowe przekształceń przesunięcia, skalowania i obrotu mają
następującą postać
P
0
= T + P,
P
0
= R · P,
P
0
= S · P.
Niestety przesunięcie (translacja) jest traktowane inaczej niż skalowanie lub obrót i nie
da się tego przekształcenia przedstawić w formie mnożenia wektora przez macierz, jeżeli
punkty traktuje się, w sposób naturalny, jako składowe wektora dwuwymiarowego. Można
jednak przejść do współrzędnych jednorodnych, uznając punkty z R
∈
jako punkty z R
3
,
leżące na płaszczyźnie z = 1, a więc o trzech współrzędnych (x, y, 1).
1.2.1. Translacja
x
0
y
0
1
=
1 0 t
x
0 1 t
y
0 0
1
·
x
y
1
,
albo
P
0
= T(t
x
, t
y
) · P
gdzie
T(t
x
, t
x
) =
1 0 t
x
0 1 t
y
0 0
1
.
Zatem złożenie dwóch operacji translacji można przedstawić następująco
P
0
= T(t
x1
, t
y1
) · P,
P
00
= T(t
x2
, t
y2
) · P
0
,
P
00
= T(t
x2
, t
y2
) · (T(t
x1
, t
y1
) · P) = (T(t
x2
, t
y2
) · T(t
x1
, t
y1
)) · P,
czyli, w postaci macierzowej wynikową wartość translacji można zapisać następująco
1 0 t
x1
0 1 t
y1
0 0
1
·
1 0 t
x2
0 1 t
y2
0 0
1
=
1 0 t
x1
+ t
x2
0 1 t
y1
+ t
y2
0 0
1
.
1.2.2. Skalowanie
x
0
y
0
1
=
s
x
0
0
0
s
y
0
0
0
1
·
x
y
1
,
albo
P
0
= S(s
x
, s
y
) · P
gdzie
S(s
x
, s
x
) =
s
x
0
0
0
s
y
0
0
0
1
.
Zatem złożenie dwóch operacji skalowania można przedstawić następująco
P
0
= S(s
x1
, t
s1
) · P,
1. Transformacje obiektów
4
P
00
= S(s
x2
, s
y2
) · P
0
,
P
00
= S(s
x2
, s
y2
) · (S(s
x1
, s
y1
) · P) = (S(s
x2
, s
y2
) · S(s
x1
, s
y1
)) · P,
czyli, w postaci macierzowej wynikową wartość skalowania można zapisać następująco
s
x1
0
0
0
s
y1
0
0
0
1
·
s
x2
0
0
0
s
y2
0
0
0
1
=
s
x1
s
x2
0
0
0
s
y1
s
y2
0
0
0
1
.
1.2.3. Rotacja
x
0
y
0
1
=
cos (ϕ) − sin (ϕ) 0
sin (ϕ)
cos (ϕ)
0
0
0
1
·
x
y
1
,
albo
P
0
= R(ϕ) · P
gdzie
R(ϕ) =
cos (ϕ) − sin (ϕ) 0
sin (ϕ)
cos (ϕ)
0
0
0
1
.
Zatem w przypadku złożenia dwóch operacji rotacji, wynikową wartość rotacji można
zapisać następująco
cos (ϕ) − sin (ϕ) 0
sin (ϕ)
cos (ϕ)
0
0
0
1
·
cos (α) − sin (α) 0
sin (α)
cos (α)
0
0
0
1
=
cos (ϕ + α) − sin (ϕ + α) 0
sin (ϕ + α)
cos (ϕ + α)
0
0
0
1
.
1.2.4. Przekształcenia pochylające
Pochylenie wzdłuż osi x
SH
x
=
1 a 0
0 1 0
0 0 1
.
Pochylenie wzdłuż osi x
SH
y
=
1 0 0
b 1 0
0 0 1
.
1.2.5. Łączenie różnych przekształceń
Podstawowym celem składania kilku przekształceń w jedno, jest fakt, że można
wówczas zastosować jedną macierz złożoną.
Przykładowo, aby obrócić obiekt wokół pewnego punktu P
1
można zadanie podzielić
na trzy łatwe podzadania:
1. Przesunięcie tak, aby punkt P
1
znalazł się w srodku układu współrzędnych.
1. Transformacje obiektów
5
2. Obrót.
3. Przesunięcie tak, aby punkt znajdujący się w środku układu współrzędnych
znalazł się w punkcie P
1
.
W postaci zależności matematycznych można takie złożenie zapisać następująco
T(x
1
, y
1
)·R(ϕ)·T(−x
1
, −y1) =
1 0 x
1
0 1 y
1
0 0
1
·
cos (ϕ) − sin (ϕ) 0
sin (ϕ)
cos (ϕ)
0
0
0
1
·
1 0 −x
1
0 1 −y
1
0 0
1
=
=
cos (ϕ) − sin (ϕ) x
1
1 − cos (ϕ) + y
1
sin (ϕ)
sin (ϕ)
cos (ϕ)
y
1
1 − cos (ϕ) + x
1
sin (ϕ)
0
0
1
1.3. Współrzędne obiektów na ekranie
W większości zastosowań, obiekty umieszczane są w rzeczywistym układzie
kartezjańskim. Przy wizualizacji ich na urządzeniu graficznym staje się konieczne przejście
od układu rzeczywistego do układu współrzędnych danego urządzenia wizualizującego.
Odwzorowanie rzeczywistych współrzędnych na współrzędne układu urządzenia
zaczyna się od określenia tzw. okna współrzędnych świata, czyli obszaru prostokątnego
we współrzędnych świata rzeczywistego oraz odpowiadającego mu obszaru prostokątnego
we współrzędnych ekranu, zwanego polem wizualizacji.
Odwzorowywanie można określić jako złożenie czterech przekształceń:
1. Określenie okna we współrzędnych świata rzeczywistego.
2. Przesunięcie okna do początku układu współrzędnych.
3. Skalowanie okna, aby dopasować je do wymiaru pola wizualizacji.
4. Przesunięcie pola wizualizacji do właściwej pozycji na ekranie.
Powyższe odwzorowanie można zapisać następująco
M
wv
= T(u
min
, v
min
) · S
u
max
− u
min
x
max
− x
min
,
v
max
− v
min
y
max
− y
min
!
· T(−x
min
, −y
min
) =
=
1 0 u
min
0 1 v
min
0 0
1
·
u
max
−u
min
x
max
−x
min
0
0
0
v
max
−v
min
y
max
−y
min
0
0
0
1
·
1 0 −x
min
0 1 −y
min
0 0
1
=
u
max
−u
min
x
max
−x
min
0
−x
min
·
u
max
−u
min
x
max
−x
min
+ u
min
0
v
max
−v
min
y
max
−y
min
−y
min
·
v
max
−v
min
y
max
−y
min
+ v
min
0
0
1
.
Zatem powymnożeniu punktu P przez M
wv
otrzymuje się P
0
= M
wv
[x, y, 1]
T
czyli
P
0
=
(x − x
min
) ·
u
max
−u
min
x
max
−x
min
+ u
min
(y − y
min
) ·
v
max
−v
min
y
max
−y
min
+ v
min
1
1. Transformacje obiektów
6
Jeżeli okno i pole wizualizacji nie mają takich samych stosunków wysokości
do szerokości, to ma miejsce skalowanie niejednorodne.
1.4. Reprezentacja macierzowa przestrzeni 3D
Podobnie, jak przekształcenia 2D mogą być opisywane za pomocą macierzy o wymiarze
3 × 3, przeksztaćenia 3D mogą być reprezentowane za pomocą macierzy 4 × 4, jeżeli
wykorzystane zostaną również współrzędne jednorodne do reprezentowania punktów
z przestrzeni trójwymiarowej.
1.4.1. Przesunięcie w 3D
Przesunięcie w 3D jest zwykłym rozszerzeniem przesunięcia w 2D
T(t
x
, t
y
, t
z
) =
1 0 0 t
x
0 1 0 t
y
0 0 1 t
z
0 0 0
1
,
to znaczy
T(t
x
, t
y
, t
z
) · [x, y, z, 1]
T
= [x + t
x
, y + t
y
, z + tz, 1]
T
1.4.2. Skalowanie w 3D
Podobnie, jak przesunięcie, skalowanie w 3D jest rownież zwykłym rozszerzeniem
skalowania w 2D
S(s
x
, s
y
, s
z
) =
s
x
0
0
0
0
s
y
0
0
0
0
s
z
0
0
0
0
1
,
to znaczy
S(s
x
, s
y
, s
z
) · [x, y, z, 1]
T
= [s
x
x, s
y
y, s
z
z, 1]
T
1.4.3. Obrót w 3D
Obrót 2D jest szczególnym przypadkiem obrotu w 3D, to znaczy obrotem wokół osi
z. Obrót ten oraz pozostałe obroty wokół innych osi można przedstawić następująco
R
z
(ϕ) =
cos (ϕ) − sin (ϕ) 0 0
sin (ϕ)
cos (ϕ)
0 0
0
0
1 0
0
0
0 1
R
x
(ϕ) =
1
0
0
0
0 cos (ϕ) − sin (ϕ) 0
0
sin (ϕ)
cos (ϕ)
0
0
0
0
1
1. Transformacje obiektów
7
R
y
(ϕ) =
cos (ϕ)
0
sin (ϕ)
0
0
1
0
0
− sin (ϕ) 0 cos (ϕ) 0
0
0
0
1
1.4.4. Pochylanie w przestrzeni 3D
Pochylenie w płaszczyźnie z
SH
xy
(sh
x
, sh
y
) =
1 0 sh
x
0
0 1 sh
y
0
0 0
1
0
0 0
0
1
P
0
= [x + sh
x
z, y + sh
y
z, z, 1]
T
Pochylenie w płaszczyźnie y
SH
xz
(sh
x
, sh
z
) =
1 sh
x
0 0
0
1
0 0
0 sh
z
1 0
0
0
0 1
P
0
= [x + sh
x
y, y, z + sh
z
y, 1]
T
Pochylenie w płaszczyźnie x
SH
yz
(sh
y
, sh
z
) =
1
0 0 0
sh
y
1 0 0
sh
z
0 1 0
0
0 0 1
P
0
= [x, y + sh
y
x, z + sh
z
x, 1]
T
2. Grafika żółwia
2.1. Współrzędne biegunowe — grafika żółwia
Grafika żółwia jest techniką rysowania krzywych, w której zastosowano pojęcie
względnego opisu ruchu oraz rysowania we współrzędnych biegunowych. Takie połączenie
pozwala na osiągnięcie efektywnego narzędzia do rysowania wielokątów na płaszczyźnie,
a także w przestrzeni 3D. Proces rysowania obiektów opisany jest tutaj za pomocą
sprecyzowania kierunku oraz odległości nowopowstałych odcinków. Program rysujący
przechowuje bieżący kierunek. Podczas rysowania nowego odcinka, najpierw ustala się
parametr zmiany kierunku, a następnie definiuje się długość nowokreślonego odcinka.
Taką zasadę tworzenia rysunków zastosowano również w urządzeniach kreślących, takich
jak plottery.
W grafice żółwia zdefiniowane są następujące operacje:
❏ RysujWprzód(dystans) — operacja rysuje z bieżącej pozycji w ustalonym kierunku
linię o długości określonej wartością parametru dystans.
❏ PrzesuńWprzód(dystans) — realizuje operację taką samą, jak operacja RysujWprzód,
ale bez rysowania linii.
❏ ObrótWPrawo(kąt) — obraca żółwia w prawo o kąt określony wartością parametru
kąt. Obrót w lewo realizowany jest za pomocą ujemnej wartości parametru kąt.
Każdy ruch żółwia jest opisany za pomocą współrzędnych biegunowych (tzn. za
pomocą kierunku i odległości). Dodatkowymi operacjami, które można zdefiniować, są
operacje ObrótWLewo(kąt), ObróćNaKierunek(kąt) oraz RysujWtył(dystans).
Rysunek 2.1 pokazuje typowy wygląd ekranu, na którym mały trójkąt w kole oznacza
położenie i kierunek żółwia.
Przykład z rysunku 2.1 został wygenerowany za pomocą następujących komend:
Procedure Dom; begin
RysujWprzód(20);
{ lewa ściana }
ObrótWPrawo(45);
{ obrót w prawo o~45 stopni }
RysujWprzód(28.2);
{ lewa część dachu }
ObrótWPrawo(90);
{ itd... }
RysujWprzód(28.2);
ObrótWPrawo(45);
RysujWPrzód(20);
ObrótWPrawo(90);
RysujWprzód(40);
{ ostatnia linia }
ObrótWPrawo(90);
{ obrót żółwia do wyjściowej pozycji }
2. Grafika żółwia
9
@
@
@
@
@
6
d
Rysunek 2.1: Przykład grafiki żółwia
end;
Procedura rysująca dom, zwraca żółwia ustawionego w pozycji wyjściowej. Takie
ustawienie żółwia jest zwykle stosowane w przypadku procedur rysujących takie elementy
graficzne, jak np. rys. 2.2.
@
@
@
@
@
@
6
d
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
Rysunek 2.2: Wielokrotne zastosowanie procedury Dom
2. Grafika żółwia
10
Rys. 2.2 narysowany został za pomocą następującego kodu programu
for i:=1 to 8 do begin
Dom;
ObrótWPrawo(45);
end;
Procedury posługujące się grafiką żółwia są bardzo łatwe w implementacji. Globalna
zmienna CD oznacza kierunek i jest definiowana w zastosowaniu ze zmienną CP . CD jest
kątem mierzonym w stopniach, w kierunku przeciwnym do ruchu wskazówek zegara od
osi x. Rysunek 2.3 pokazuje, jak, za pomocą elementarnej trygonometrii, obliczana jest
wartość
współrzędnych
kartezjańskich
nowego
punktu,
po
wykonaniu
operacji
RysujWprzód(dystans).
6
?
A
A
K
CP
CD
dist
dist · sin
π·CD
180
Rysunek 2.3: Efekt procedury RysujWprzód()
Procedurę RysujWprzód() można zrealizować zatem za pomocą następującego kodu
programu:
const TWOPI = 6.283185308; { 2 pi }
type point = record
x: real;
y: real;
end;
var CD: real;
CP: point;
Procedure RysujWprzód(dist: real); var angle: real;
p: point;
begin
angle := TWOPI * CD / 360.0; { konwersja stopni na radiany }
p.x := CP.x + dist * cos(angle);
p.y := CP.y + dist * sin(angle);
2. Grafika żółwia
11
LineTo(p.x, p.y);
CP := p
end;
Procedura ObrótWPrawo() może więc wyglądać następująco:
Procedure ObrótWPrawo(angle: real); begin
CD := CD - angle
end;
Procedura PrzesuńWprzód() jest prawie identyczna z procedurą RysujWprzód().
W praktyce zamiast używać procedur RysujWprzód(), czy PrzesuńWprzód(), częściej
stosuje
się
procedury
SchowajŻółwia()
oraz
PokażŻółwia().
Wówczas
do
przemieszczania żółwia stosuje się funkcji Naprzód(). Funkcja ta przemieszcza żółwia
w kierunku CD w sposób widoczny (z opuszczonym piórem) lub w sposób niewidoczny
(z
podniesionym
piórem),
w
zależności
od
wartości
pewnej
globalnej
zmiennej widać-żółwia. Zmienna ta jest typu logicznego i określa tryb rysowania.
Procedury
SchowajŻółwia()
oraz
PokażŻółwia()
modyfikują
wartość
zmiennej widać-żółwia.
Rysunek 2.4: Przykład rysunku narysowanego za pomocą grafiki żółwia
2.1.1. Zastosowanie grafiki żółwia — spirale
Grafika żółwia dostarcza dobrego narzędzia do rysowania dużej i różnorodnej rodziny
krzywych zwanych spiralami (polyspiral ).
2. Grafika żółwia
12
Aby narysować spiralę, należy zacząć od bieżącej pozycji i kreślić w pewnym
początkowym kierunku odcinek o długości dist. następnie należy skręcić o jakiś kąt (angle)
i kreślić kolejny odcinek o długości większej lub mniejszej od poprzedniej. Zmiana długości
odcinka określana jest najczęściej pewną zmienną incr. Za pomocą tych trzech parametrów
można zbudować olbrzymi zbiór różnorodnych obrazków. Rys. 2.5 pokazuje kilka spiral
z ich parametrami (dist, angle, incr ). Jeśli incr posiada wartość 0, wówczas rysunek
nie zwiększa ani nie zmniejsza swoich rozmiarów. Jeśli dodatkowo kąt angle posiada
wartość 360
◦
/k, wówczas figura powtórzy się po k segmentach.
Rysunek 2.5: Przykłady spiral
3. Mapowanie współrzędnych
Bardzo często zachodzi potrzeba przeliczenia współrzędnych rzeczywistych na
współrzędne ekranu. Rys. 3.1 pokazuje okno W we współrzędnych rzeczywistych oraz
okno ekranowe (viewport ) V w tzw. znormalizowanych jednostkach urządzenia (normalized
device coordintates).
6
y
-
x
W
r
(x, y)
W
l
W
r
W
t
W
b
6
dy
-
dx
r
(dx, dy)
V
l
V
r
V
t
V
b
Rysunek 3.1: Współrzędne rzeczywiste i wspoółrzędne okna ekranowego
Lewą, prawą, dolną oraz górną pozycję okna W oznaczono przez W
l
, W
r
, W
t
oraz W
b
.
Podobne oznaczenia przyjęto dla okna ekranowego. Dla dowolnego punktu (x, y) okna
W , należy obliczyć odpowiadające mu współrzędne w oknie ekranowym V , np. (dx, dy).
Aby odległości od punktów pozostały proporcjonalne, do opisania współrzędnych można
zastosować równania liniowe
dx = s
x
x + t
x
,
dy = s
y
y + t
y
,
w których należy ustalić odpowiednie wartości współczynników s
x
, s
y
, t
x
oraz t
y
. Jeżeli
x = W
l
, wówczas dx = V
l
, zatem pierwsze równanie przyjmie postać V
l
= s
x
W
l
+ t
x
.
Podobnie, gdy x = W
r
, to dx = V
r
, zatem V
r
= s
x
W
r
+ t
x
. W ten sam sposób można
przeanalizować współrzędne y. Ostatecznie otrzymuje się
s
x
=
V
r
− V
l
W
r
− W
l
,
s
y
=
V
t
− V
b
W
t
− W
b
,
t
x
=
V
l
W
r
− W
l
V r
W
r
− W
l
,
t
y
=
V
b
W
t
− W
b
V t
W
t
− W
b
.
3. Mapowanie współrzędnych
14
3.1. Programowa realizacja mapowania
Programowa realizacja mapowania nie powinna sprawić wiele kłopotów. W pierwszej
kolejności należy zdefiniować typ danych, przechowujący współrzędne prostokąta rect.
Przechowuje on lewą l, prawą r, górną t oraz dolną b współrzędną brzegów prostokąta.
type
rect = record
l, t, r, b: real;
end;
procedure SetRect(left, top, right, bott:real; var r:rest); begin
with r do begin
l := left; t := top; r := right; b := bottom
end
end;
Okno rzeczywistych współrzędnych oraz okno ekranowe przedstawione są za pomocą jako
var W,V: rect. Następnie należy obliczyć wartości zmiennych s
x
, s
y
, t
x
oraz t
y
. Można
to zrealizować np. za pomocą procedury MapRect(W,V: rect; sx,tx,sy,ty:Real);.
W celu zwiększenia efektywności, zmienne te mogą zostać zdefiniowane globalnie. Ich
wartości można używać w procedurach tworzących rysunek, takich jak Line() itp.
Umożliwia to mapowanie rzeczywistych współrzędnych pWorld:Point na współrzędne
ekranowe pNDC:point, np.:
pNDC.x := sx * pWorld.x + ts; pNDC.y := sy * pWorld.y + ty;
Procedura kreśląca linię, która uwzględnia takie mapowanie, może wyglądać
następująco:
procedure Line(p1,p2:point); var pNDC1,pNDC2:point; begin
{ ewentualna modyfikacja współrzędnych związana z kadrowaniem }
pNDC1.x := sx * p1.x + tx;
pNDC1.y := sy * p1.y + ty;
pNDC2.x := sx * p2.x + tx;
pNDC2.y := sy * p2.y + ty;
LineNCD(pNDC1,pNDC2)
end;
Powyższa procedura może zostać uzupełniona o algorytm kadrowania (clipping), który
zostanie opisany w dalszej części.
Podobną analizę można przeprowadzić dla współrzędnych biegunowych.
3.2. Kadrowanie linii
Z kadrowaniem linii mamy do czynienia w przypadku, gdy kreślona krawędź
rzeczywistego obiektu nie mieści się w całości w oknie. Operację kadrowania zrealizować
3. Mapowanie współrzędnych
15
można w procedurze Cli[p(var p1,p2:points; var vis:boolean);. Procedura ta
przycina segmenty linii pomiędzy p
1
oraz p
2
, zapisanych w rzeczywistych współrzędnych,
do rozmiaru okna. Jeżeli odcinek częściowo „wystaje” za obszar okna ekranowego, to
współrzędne jednego z konńcowych punktów (p
1
lub p
2
) zostają obliczone na nowo tak,
aby punkt ten znajdował się na granicy okna, a wartość zmiennej vis zostaje ustawiona
na True. W przypadku, gdyby cały odcinek znalazł się poza oknem, zmiennej vis zostanie
przypisana wartość False. Rys. 3.2 pokazuje typowe sytuacje, obejmujące zakres działania
procedury Clip(). Zatem Clip() wykonuje jedną z czterech czynności dla każdej linii,
z której zbudowany jest rysunek:
❏ Nic nie robi, jeśli cała linia mieści się w oknie (segment CD).
❏ Eliminuje całą linię, gdy ta w całości znajduje się poza oknem (segment AB).
❏ „Przycina” jeden z końców, gdy jeden z punktów końcowych znajduje się poza
granicami okna (segment ED).
❏ Przycina obydwa końce odcinka, gdy obydwa punkty końcowe znajdują się poza
oknem, ale część odcinka znajduje się wewnątrz okna ekranowego (segment AE).
E
P
P
P
P
P
P
P
P
P
A
B
A
A
A
A
A
A
C
D
Rysunek 3.2: Kadrowanie krzywych do rozmiaru okna
Ze względu na fakt, że istnieje wiele możliwych ustawień odcinnka względem okna,
należy zastanowić się nad efektywnym podejściem do problemu kadrowania. Od procedury
kadrującej wymaga się dużej efektywności, gdyż w typowym rysunku mogą znaleźć się
setki lub tysiące segmentów, a każdy musi zostać poddany operacji przycinania. Algorytm
Cohena-Sutherlanda stosuje w tym celu algorytm dziel i rządź.
3.2.1. Algorytm Cohena-Sutherlanda
Algorytm Cohena-Sutherlanda szybko wykrywa i reaguje na dwa podstawowe
przypadki. Pierwszym jest sytuacja, w której obydwa końcowe punkty odcinka zawierają
się w oknie. Wówczas cały odcinek musi znajdować się wewnątrz okna i nie ma nic do
odrzucenia. Drugim przypadkiem jest sytuacja, w której obydwa końcowe punkty leżą
poza jedną z krzywych ograniczających okno. W takim przypadku cały odcinek leży poza
3. Mapowanie współrzędnych
16
oknem i powinien zostać w całości odrzucony. Sytuację taką przedstawia rysunek 3.3.
Taka sytuacja występuje najczęściej, gdy zastosowane jest małe okno do przedstawienia
rysunku składającego się z dużej liczby segmentów.
6
y
-
x
W
W
l
W
r
W
t
W
b
r
r
A
B
A
A
A
A
A
A
r
r
C
D
Rysunek 3.3: Akceptacja bądź odrzucenie segmentu
Do określenia, czy końcowe punkty segmentu leżą wewnąrz lub na zewnątrz okna,
można zastosować podejście polegające na sprawdzeniu dla każdego położenia punktu
względem tzw. granicy półprzestrzeni. Całą przestrzeń dzieli się na dwie części, a granica
pomiędzy nimi ustalana jest prostą stanowiącą jednocześnie krawędź okna. Jeżeli obydwa
końce segmentu znajdują się w części, w której nie występuje okno, to oznacza, że segment
ma zostać odrzucony. Jeżeli dla wszystkich czterech krawędzi okna obydwa końce
segmentu zawierają się w tej częśi przestrzeni, w której leży okno, wówczas cały segment
zawiera się w oknie. Każdą krawędź okna można przedstawić w postaci nieskończonej
prostej. Do przechowywania wartości określających położenie punktów względem krawędzi
okna można zdefiniować następujący typ danych:
type
half_space_code = record
l, t, r, b: boolean
end;
Przypomina ona strukturę rect, ale zamiast wartości typu Real przechowuje ona wartości
logiczne. Składowe przyjmują wartość False, gdy punkty znajdują się po właściwej stronie
krzywej określającej odpowiednią krawędź okna lub True w przeciwnym przypadku.
Gdyby np. punkt leżał wewnątrz okna W , wówczas struktura half_space_code
zawierałaby wartości (false, false, false, false). Powyższych obliczeń można dokonać
poprzez wywołanie dla każdego punktu procedury:
procedure Encode(p: point; var c: half_space_code); begin
c.l := (p.x < W.l);
c.r := (p.x > W.r);
c.b := (p.y < W.b);
c.t := (p.y > W.t)
end;
3. Mapowanie współrzędnych
17
Rysunek
3.4
przedstawia
sposób
określania
wartości
składowych
struktury
half_space_code.
false
6
true
?
true
6
false
?
true
false
-
false
true
-
W
c.t
c.b
c.l
c.r
Rysunek 3.4: Określanie wartości składowych struktury half space code
Punkt p
1
z wartościami struktury half space code, przechowywanymi w zmiennej c1
będzie znajdował się wewnątrz okna, jeśli wszystkie wartości struktury c1 będą
równe false, co może być podsumowane w jednej zmiennej logicznej in1:
in1 := (not c1.l) and (not c1.t) and (not c1.r) and (not c1.b);
Zatem segment kreślony od punktu p
1
do p
2
będzie w całości narysowany jeśli obydwa
końcowe punkty będą znajdowały się wewnątrz okna ((in1 and in2) = true). Natomiast
odrzucenie nastąpi, gdy zmienna
reject := (c1.l and c2.l) or (c1.r and c2.r) or (c1.t and c2.t)
or (c1.b and c2.b);
przyjmie wartość true.
Jeśli nie zajdzie żaden z powyższych warunktów, to segment musi być analizowany
dalej. W tym celu zastosowano metodę dziel i rządź (divide and conquer ). Segment jest
dzielony w miejscu przecięcia z którąś z krawędzi okna, i test jest wykonywany powtórnie
dla nowopowstałego odcinka. Jeżeli odcinek i tym razem nie spełni warunku odrzucenia
oraz akceptacji, wówczas znów dzieli się go, lecz tym razem stosując inną krawędź okna
i znów powtarza się test.
Rysunek 3.5 pokazuje przypadek, w którym segment jest dzielony prawą krawędzią
okna W . Współrzędne punktu A muszą zostać obliczone. Jego współrzędna x jest równa
współrzędnej prawej krawędzi okna (A
x
= W.r). Współrzędna A
y
wymaga skorygowania
p
1
.y o wartość d, lecz d jest równe e pomnożone przez nachylenie odcinka m. Zatem nową
wartość punktu p
1
oblicza się ze wzoru:
p1.y := p1.y + (W.r - p1.x)*m;
3. Mapowanie współrzędnych
18
6
y
-
x
W
W
l
W
r
W
t
W
b
r
r
P
2
P
1
A
r
-
e
6
?
d
Rysunek 3.5: Przycinanie segmentu w miejscu przecięcia z krawędią okna
Jeśli odcinek jest pionowy, wówczs jego nachylenie nie może zostać obliczone (m = ∞).
Zatem przed obliczeniem m należy sprawdzić czy p1.x = p2.x. Jeśli ten warunek jest
spełniony, wówczas algorytm przycinania odcinka znacznie się upraszcza.
Powyższy algorytm umieszczony został w procedurze Clip(). Warunkiem stopu dla
algorytmu jest albo zaakceptowanie odcinka, albo odrzucenie go. Poniżej przedstawiono
kod procedury Clip() w języku Pascal
procedure Clip(var p1,p2:point, var vis:boolean); var
c1,c2,tmp_cd: half_space_code;
tmp_pt: point;
m: real; {pochylenie linii}
int1, in2, done: boolean;
procedure Encode(p: point; var c: half_space_code);
begin
c.l := (p.x < W.l);
c.r := (p.x > W.r);
c.b := (p.y < W.b);
c.t := (p.y > W.t)
end;
begin {Clip}
done := false;
vis := false;
repeat
Encode(p1,c1);
Encode(p2,c2);
in1 := (not c1.l) and (not c1.t) and (not c1.r) and (not c1.b);
in2 := (not c2.l) and (not c2.t) and (not c2.r) and (not c2.b);
if in1 and in1 then {odcinek zaakceptowany}
begin
done := true;
vis := true
3. Mapowanie współrzędnych
19
end
else if (c1.l and c2.l) or (c1.r and c2.r)
or (c1.t and c2.r) or (c1.b and c2.b) then
begin {odcinek odrzucony}
done := true;
vis := false
end
else begin {przynajmniej jeden punkt w środku}
if in1 then
begin { zamiana p1, p2 i c1,c2 }
tmp_cd := c1; c1 := c2; c2 := tmp_cd;
tmp_pt := p1; p1 := p2; p2 := tmp_pt
end;
if p2.x = p1.x then {linia pionowa}
begin
if c1.t then
p1.y := W.t {p1 jest powyżej}
else if c1.b then
p1.y := W.b {p1 jest poniżej}
end
else begin { linia nie jest pionowa }
m := (p2.y - p1.y)/(p2.x - p1.x); {nachylenie}
if c1.l then
begin
p1.y := p1.y + (W.l - p1.x) * m;
p1.x := w.l
end
else if c1.r then
begin
p1.y := p1.y + (W.r - p1.x) * m;
p1.x := W.r
end
else if c1.b then
begin
p1.x := p1.x + (W.b - p1.y)/m;
p1.y := W.b
end
else if c1.t then
begin
p1.x := p1.x + (W.t - p1.y)/m;
p1.y := W.t
end
end
{linia pionowa}
end
{przynajmniej jeden punkt w środku}
3. Mapowanie współrzędnych
20
until done
end; {Clip}
4. Wykresy liniowe i słupkowe
Prezentacja
danych
jest
często
bardzo
istotnym
elementem
prezentacji
multimedialnych. Z wielu form wykresów, wykresy liniowe oraz słupkowe są najczęściej
stosowane. Są one skonstruowane na podstawie listy lub tabeli danych liczbowych. Wykres
jest wizualną prezentacją tych danych w przyjemnej dla oka i łatwej w zrozumieniu
i interpretacji formie.
Dane wejściowe mogą pochodzić z trzech głównych źródeł:
❏ Dane otrzymane z pomiarów. Na przykład, gdy obserwuje się pewien eksperyment
i zapisuje się wartości wskazywane przez termometr, woltomierz lub inne urządzenie
pomiarowe. Innym przykładem jest akwizycja danych przez ankietera od losowo
wybranych osób i stworzenie listy zapisanych numerycznie odpowiedzi.
❏ Dane obliczone z równań matematycznych. W tym przypadku źródłem danych może
być wartość funkcji matematycznej, dla różnej wartości parametrów wejściowych, np.
f (x) = sin(2πx) + cos
5
(7πx)/x
3
.
Próba zinterpretowania przebiegu takiej funkcji w pamięci może być trudna, natomiast
przedstawienie go w postaci wykresu z pewnością sprawę ułatwia.
❏ Dane pochodzące z symulacji komputerowej. Wiele programów komputerowych jest
zaprojektowanych tak, aby symulować przebieg jakiegoś procesu. Proces ten jest często
modelowany poprzez zbiór równań, które opisują sposób zachowania się projektu.
4.1. Reprezentacja źródła danych
Dla każdego źródła danych, kreślona jest wynikowa sekwencja y
1
, y
2
, . . . , y
n
. Aby
przechowywać powyższe wartości, można zdefiniować typ danych sequence:
type
sequence = record
num = 0..maximum;
values: array[1..maximum] of real
end;
Dane mogą być prezentowane w różny sposób. Najczęściej, w przypadku wykresów
liniowych lub słupkowych, wartości y
i
, gdzie i = 1, . . . , n, są traktowane jako współrzędne
y i umieszczane w równych odstępach wzdłuż osi x. Wartości x dobierane są zgodnie z
równaniem
x
i
= i.
4. Wykresy liniowe i słupkowe
22
Różnice pomiędzy wykresami liniowymi oraz słupkowymi polegają na sposobie prezentacji
i łączenia poszczególnych punktów wykresu.
4.2. Wybór okna
Istotnym problemem jest dobór rozmiaru okna oraz ustalenie jego wewnętrznych
współrzędnych. Rozmiar okna powinien być tak dobrany, aby pomieścić całą krzywą
wykresu oraz pewien obszar marginesu. Krzywa wykresu rozciąga się od 1 do n oraz
od y
min
do y
max
, określonych jako najmniejsza i największa wartość danych wejściowych.
Te ekstremalne wartości można obliczyć z pomocą funkcji
procedure Extremes(s: sequence; var min, max: real); var i:
Integer; begin
with s do begin
if num=0 then writeln(’Error! No data!’)
else begin
min := values[1]; max := min;
if num > 1 then for i := 2 to num do
begin
if values[i] < min then min := values[i];
if values[i] > max then max := values[i]
end {for}
end {else}
end {with}
end;
Po wyznaczeniu wartości y
min
oraz y
max
, można ustalić i przechować rozmiar okna W ,
używając funkcji SetRect(1.0-bord,ymax+bord,data.num+bord,ymin-bord);.
4.3. Wykresy liniowe
Mając określony rozmiar okna można przystąpić do rysowania wykresu liniowego.
W tym celu można posłużyć się następującą funkcją
procedure LineGraph(data: sequence); const bord=0.3; var
ymin, ymax: real;
i: integer;
begin
if data.num > 1 then begin
Extremes(data,ymin,ymax);
SetRect(1-bord,ymax+bord,data.num+bord,ymin-bord,W);
.
. {użytkownik wybiera okno na ekranie V}
.
MapRects(W,V,sx,tx,sy,ty); {Ustawienie mapowania z okna W na V}
4. Wykresy liniowe i słupkowe
23
with data do
begin
MoveTo_(1.0,values[1]);
for i := 2 to num do LineTo_(i+0.0,values[i])
end;
Line_(1.0,ymin,1.0,ymax); {oś pionowa}
Line_(1.0,0.0,data.num,0.0) {oś pozioma}
end
end;
6
-
@
@
H
H
@
@
H
H
@
@
Rysunek 4.1: Przykład działania procedury LineGraph()
4.4. Wykresy słupkowe
Wykresy słupkowe (bar graphs) oferują alternatywny format wyświetlania sekwencji
danych. Na wykresie tym każda wartość wejściowa określa wysokość słupka.
Aby wykonać prosty wykres słupkowy można zastosować procedurę BarGraph(data:
sequence; width: real). i-ty słupek zaczyna się we współrzędnych (i, 0). Zmienna
width oznacza szerokość słupka. Każdy słupek reprezentowany jest poprzez prostokąt
oparty na osi x.
6
-
Rysunek 4.2: Przykład działania procedury BarGraph()
Trochę więcej kłopotów może sprawić rysowanie wykresu słupkowego, na którym
słupki rysowane są tak, jakby były trójwymiarowe. Na rysunku 4.3 przedstawiono
przykładowy wykres oraz sposób konstruowania pojedynczego słupka. W przypadku
takiego wykresu, zamiast zwykłego prostokąta, każdy słupek ma trzy ściany, które
4. Wykresy liniowe i słupkowe
24
reprezentują front, bok oraz górę „bloku”. Wysokość bloku określona jest wartością danej
wejściowej. Dolna krawędź boku rozpoczyna się w punkcie (i + width, 0.0) i biegnie
przekątnie pod kątem θ do punktu (i + 1, (1 − width) ∗ tan(θ)). Górną płaszczyznę można
skonstruować podobnie.
6
-
6
-
B
B
M
θ
-
@
@
width
-
1−width
i
i + 1
v
i
Rysunek 4.3: Trójwymiarowy wykres słupkowy