Algorytm rysowania elipsy jest nieco trudniejszy od przedstawionego w
poprzednim rozdziale algorytmu rysowania okręgu.
Wyznaczanie punktów na obwodzie okręgu mogliśmy ograniczyć do 1/8
tego obwodu. Pozostałe punkty otrzymaliśmy w prosty sposób poprzez symetrię
względem osi OX i OY. W przypadku elipsy nie wolno nam tak postąpić - należy
wyznaczyć pełną ćwiartkę obwodu i dopiero z niej poprzez symetrię otrzymamy
pozostałe 3 ćwiartki elipsy.
Kolejne punkty obwodu elipsy będziemy wyznaczali przy założeniu, iż
środkiem elipsy jest środek układu współrzędnych. Jeśli środek leży w
punkcie Ps = (xs, ys), to po prostu
wyznaczone punkty przesuwamy o wektor (xs,ys):
P1 = (x + xs, y + ys)
P2 = (x + xs, -y + ys)
P3 = (-x + xs, -y + ys)
P4 = (-x + xs, y + ys)
Aby unikać dzielenia, przekształcamy równanie elipsy do poniższej postaci:
ry2x2 + rx2y2
= rx2ry2
Dla danego punktu P = (x,y) wyrażenie błędu:
e = ry2x2
+ rx2y2 - rx2ry2
określa położenie tego punktu w stosunku do obrysu elipsy. Jeśli e jest
ujemne, to punkt P leży wewnątrz elipsy. Jeśli e jest dodatnie, punkt P leży
poza elipsą. Jeśli wyrażenie błędu e przyjmie wartość 0, to punkt P leży
dokładnie na obrysie elipsy - jego współrzędne spełniają równanie elipsy.
Piszemy o tym dlatego, iż powierzchnia graficzna składa się z siatki pikseli
o całkowitych współrzędnych. Nie wszystkie wyznaczone punkty (szczerze
mówiąc duża większość z nich) nie będą spełniały równania elipsy,
ponieważ jej linia przebiega tak, iż nie ma pikseli dokładnie ją
odwzorowujących (patrz - rysunek po prawej stronie).
Wyznaczone piksele będą przybliżać rzeczywistą linię elipsy - zatem ze
zbioru pikseli płaszczyzny graficznej zostaną przez nasz algorytm wybrane te
piksele, których środki leżą najbliżej rzeczywistej linii elipsy.
Rysowanie elipsy rozpoczynamy od punktu P = (0,ry) i będziemy
poruszali się zgodnie z ruchem wskazówek zegara w obrębie pierwszej ćwiartki
elipsy. Jeśli przyjrzysz się dokładnie rysunkowi po prawej, to zauważysz, iż
ćwiartka elipsy dzieli się na dwie części:
- Część górna, w której współrzędna x jest systematycznie zwiększana o 1
przy każdym pikselu - współrzędna y zmniejszana jest o 1 co pewien czas.
- Część dolna, w której współrzędna y zmniejszana jest o 1 przy każdym
kolejnym pikselu, a współrzędna x zwiększa się o 1 co pewien czas.
Rozważmy górną połówkę ćwiartki elipsy. Podobnie jak w przypadku okręgu z
punktu P(x,y) możemy przejść tylko do P1(x+1,y) lub
P2(x+1,y+1). Współrzędna x jest zwiększana zawsze o 1
w górnej części ćwiartki (patrz powyżej - nachylenie stycznej). O wyborze
punktu P1 lub P2 będzie decydowało wyrażenie błędu. Policzmy je dla każdego
z punktów:
P1 = (x + 1, y)
e1 = e + ry2(x + 1)2
+ rx2y2 - rx2ry2
e1 = e + ry2x2 + 2ry2x
+ ry2
+ rx2y2 - rx2ry2,
zastępujemy : - rx2ry2
wyrażeniem - ry2x2 - rx2y2
e1 = e + ry2x2 + 2ry2x
+ ry2
+ rx2y2 - ry2x2
- rx2y2 i upraszczamy otrzymując
ostatecznie:
P2 = (x + 1, y + 1)
e2 = e + ry2(x + 1)2
+ rx2(y - 1)2 - rx2ry2
e2 = e + ry2x2 + 2ry2x
+ ry2
+ rx2y2 - 2rx2y + rx2
- rx2ry2
e2 = e + ry2x2 + 2ry2x
+ ry2
+ rx2y2 - 2rx2y + rx2
- ry2x2 - rx2y2
e2 = e + 2ry2x + ry2
- 2rx2y + rx2
Obliczamy odchyłkę:
e12 = e1 + e2
Badając znak odchyłki wybieramy:
e12 < 0 - punkt P1, czyli x → x + 1, y → y
e12 ≥ 0 - punkt P2, czyli x → x + 1, y → y - 1
Wyjaśnienie tego faktu znajdziesz w opisie
algorytmu Bresenhama dla okręgu. Wyznaczanie punktów w górnej części ćwiartki
elipsy kontynuujemy do momentu, gdy przestanie być spełniona nierówność:
ry2x ≤ rx2y
Teraz przechodzimy do rysowania dolnej części ćwiartki obwodu elipsy. Z
punktu P(x,y) możemy przejść albo do punktu P1(x,y-1),
albo do punktu P2(x+1,y-1). W dolnej części ćwiartki
współrzędna y kolejno wyznaczanych pikseli zawsze zmniejsza się o 1.
Wyznaczanie punktów kontynuujemy aż y osiągnie oś OX, czyli dopóki y ≥ 0.
Policzmy wyrażenia błędów dla każdego z punktów:
P1 = (x, y - 1)
e1 = e + ry2x2
+ rx2(y - 1)2 - rx2ry2
e1 = e + ry2x2 + rx2y2
- 2rx2y + rx2 - rx2ry2,
zastępujemy : - rx2ry2
wyrażeniem - ry2x2 - rx2y2
e1 = e + ry2x2 + rx2y2
- 2rx2y + rx2 - ry2x2
- rx2y2 i upraszczamy otrzymując
ostatecznie:
P2 = (x + 1, y + 1)
e2 = e + ry2(x + 1)2
+ rx2(y - 1)2 - rx2ry2
e2 = e + ry2x2 + 2ry2x
+ ry2
+ rx2y2 - 2rx2y + rx2
- rx2ry2
e2 = e + ry2x2 + 2ry2x
+ ry2
+ rx2y2 - 2rx2y + rx2
- ry2x2 - rx2y2
e2 = e + 2ry2x + ry2
- 2rx2y + rx2
Obliczamy odchyłkę:
e12 = e1 + e2
Badając znak odchyłki wybieramy:
e12 < 0 - punkt P2, czyli x → x + 1, y → y -
1
e12 ≥ 0 - punkt P1, czyli x → x, y → y - 1
Proponujemy czytelnikowi uzasadnienie tych wyborów.
Wejście
| xs, ys |
- |
współrzędne środka elipsy |
| rx |
- |
promień elipsy na osi OX |
| ry |
- |
promień elipsy na osi OY |
| color |
- |
kolor obrysu elipsy |
Wyjście
Narysowanie na powierzchni graficznej elipsy o środku w punkcie (xs,
ys), o promieniach rx, ry i w kolorze color
Dane pomocnicze
| x, y |
- |
współrzędne punktów na obwodzie elipsy o środku w początku układu
współrzędnych |
| e |
- |
wyrażenie błędu dla narysowanego punktu P |
| e1 |
- |
wyrażenie błędu dla punktu P1 |
| e2 |
- |
wyrażenie błędu dla punktu P2 |
Lista kroków
| K01: |
x ← 0 |
; ustalamy współrzędne punktu startowego |
| K02: |
y ← ry |
|
| K03: |
e ← 0 |
|
| K04: |
Dopóki ry2x ≤ rx2y
wykonuj kroki K05...K14 |
; górna część ćwiartki elipsy |
| K05: |
Zapal piksel (x + xs, y +
ys) na color |
; kolorujemy piksele na zadany kolor |
| K06: |
Zapal piksel (x + xs,-y +
ys) na color |
; piksele są symetryczne względem osi OX i OY |
| K07: |
Zapal piksel (-x + xs, y
+ ys) na color |
|
| K08: |
Zapal piksel (-x + xs,-y
+ ys) na color |
|
| K09: |
e1 ← e + 2ry2x
+ ry2 |
; wyrażenie błędu dla P1(x+1,y) |
| K10: |
e2 ← e1 - 2rx2y
+ rx2 |
; wyrażenie błędu dla P2(x+1,y-1) |
| K11: |
x ← x + 1 |
; w górnej części ćwiartki x zawsze jest
zwiększane o 1 |
| K11: |
Jeśli e1 + e2
< 0, idź do kroku K14 |
|
| K12: |
e ← e2 |
; wybieramy P2(x+1,y-1) |
| K13: |
y ← y - 1 i kontynuuj następny obieg
pętli K04 |
|
| K14: |
e ← e1 |
; wybieramy P1(x+1,y) |
| K15: |
Dopóki y ≥ 0 wykonuj kroki K16...K26 |
; przechodzimy do dolnej części ćwiartki |
| K16: |
Zapal piksel (x + xs, y +
ys) na color |
; kolorujemy piksele na zadany kolor |
| K17: |
Zapal piksel (x + xs,-y +
ys) na color |
; piksele są symetryczne względem osi OX i OY |
| K18: |
Zapal piksel (-x + xs, y
+ ys) na color |
|
| K19: |
Zapal piksel (-x + xs,-y
+ ys) na color |
|
| K20: |
e1 ← e - 2rx2y
+ rx2 |
; wyrażenie błędu dla P1(x,y-1) |
| K21: |
e2 ← e1 + 2ry2x
+ ry2 |
; wyrażenie błędu dla P2(x+1,y-1) |
| K22: |
y ← y - 1 |
; w dolnej części ćwiartki y zawsze jest
zmniejszane o 1 |
| K23: |
Jeśli e1 + e2
≥ 0, idź do kroku K26 |
|
| K24: |
e ← e2 |
; wybieramy punkt P2(x+1,y-1) |
| K25: |
x ← x + 1 i kontynuuj następny obieg
pętli K15 |
|
| K26: |
e ← e1 |
; wybieramy P1(x,y-1) |
| K27: |
Zakończ |
|
Na podstawie powyższego algorytmu napiszemy dwie funkcje biblioteczne. Na
końcu pliku nagłówkowego SDL_gfx.h dopisz prototypy
funkcji:
void gfxEllipse(SDL_Surface * s, Sint32 xs, Sint32 ys, Sint32 rx, Sint32 ry, Uint32 color);
void gfxClipEllipse(SDL_Surface * s, Sint32 xs, Sint32 ys, Sint32 rx, Sint32 ry, Uint32 color);
Obie funkcje rysują elipsę. Druga z nich, gfxClipEllipse(),
rysuje elipsę obciętą do prostokąta obcinania zawartego w strukturze
SDL_Surface. Wydłuża to nieco czas rysowania, jednakże w większości
zastosowań elipsa i tak jest rysowana bardzo szybko. Obie funkcje przyjmują
te same parametry wywołania:
| s |
- |
wskaźnik struktury SDL_Surface. |
| xs ys |
- |
współrzędne środka elipsy |
| rx ry |
- |
promienie elipsy odpowiednio wzdłuż osi OX i OY |
| color |
- |
kolor obrysu |
Na końcu pliku SDL_gfx.cpp dopisz definicje obu
funkcji:
// Rysuje elipsę
// s - wskaźnik struktury SDL_Surface
// xs,ys - współrzędne środka
// rx - promień elipsy na osi OX
// ry - promień elipsy na osi OY
// color - kolor obrysu
//---------------------------------------
void gfxEllipse(SDL_Surface * s, Sint32 xs, Sint32 ys, Sint32 rx, Sint32 ry, Uint32 color)
{
Sint32 x = 0, y = ry;
Sint32 e = 0, e1, e2;
Sint32 rx2 = rx * rx, ry2 = ry * ry;
Sint32 fx = 0, fy = rx2 * ry;
Uint32 w = s->w;
Uint32 wy;
Uint32 * p = (Uint32 *)(s->pixels) + ys * w + xs;
wy = y * w;
while(fx <= fy)
{
* (p + x + wy) = color;
* (p + x - wy) = color;
* (p - x + wy) = color;
* (p - x - wy) = color;
e1 = e + (fx << 1) + ry2;
e2 = e1 - (fy << 1) + rx2;
x++; fx += ry2;
if(e1 + e2 >= 0)
{
e = e2; y--; fy -= rx2; wy -= w;
}
else e = e1;
}
while(y >= 0)
{
* (p + x + wy) = color;
* (p + x - wy) = color;
* (p - x + wy) = color;
* (p - x - wy) = color;
e1 = e - (fy << 1) + rx2;
e2 = e1 + (fx << 1) + ry2;
y--; fy -= rx2; wy -= w;
if(e1 + e2 < 0)
{
e = e2; x++; fx += ry2;
}
else e = e1;
}
}
// Rysuje elipsę z obcinaniem
// s - wskaźnik struktury SDL_Surface
// xs,ys - współrzędne środka
// rx - promień elipsy na osi OX
// ry - promień elipsy na osi OY
// color - kolor obrysu
//---------------------------------------
void gfxClipEllipse(SDL_Surface * s, Sint32 xs, Sint32 ys, Sint32 rx, Sint32 ry, Uint32 color)
{
Sint32 x = 0, y = ry;
Sint32 e = 0, e1, e2;
Sint32 rx2 = rx * rx, ry2 = ry * ry;
Sint32 fx = 0, fy = rx2 * ry;
while(fx <= fy)
{
gfxClipPlot(s, x + xs, y + ys, color);
gfxClipPlot(s, x + xs,-y + ys, color);
gfxClipPlot(s,-x + xs, y + ys, color);
gfxClipPlot(s,-x + xs,-y + ys, color);
e1 = e + (fx << 1) + ry2;
e2 = e1 - (fy << 1) + rx2;
x++; fx += ry2;
if(e1 + e2 >= 0)
{
e = e2; y--; fy -= rx2;
}
else e = e1;
}
while(y >= 0)
{
gfxClipPlot(s, x + xs, y + ys, color);
gfxClipPlot(s, x + xs,-y + ys, color);
gfxClipPlot(s,-x + xs, y + ys, color);
gfxClipPlot(s,-x + xs,-y + ys, color);
e1 = e - (fy << 1) + rx2;
e2 = e1 + (fx << 1) + ry2;
y--; fy -= rx2;
if(e1 + e2 < 0)
{
e = e2; x++; fx += ry2;
}
else e = e1;
}
}
Kod funkcji został odpowiednio zoptymalizowany pod kontem zmniejszenia
liczby wykonywanych działań arytmetycznych.
Elipsę wypełniamy liniami poziomymi obcinanymi do prostokąta obcinającego
zawartego w strukturze SDL_Surface. Zasada jest bardzo prosta - wyznaczamy
kolejne punkty obrysu elipsy aż do momentu wykrycia zmiany współrzędnej y -
wtedy współrzędna x wyznacza końce linii wypełniającej elipsę i możemy ją w
prosty sposób narysować. Linie wypełniające rysujemy zawsze parami - w
symetrii względem osi OX.
Wejście
| xs, ys |
- |
współrzędne środka owalu |
| rx |
- |
promień owalu na osi OX |
| ry |
- |
promień owalu na osi OY |
| color |
- |
kolor wypełnienia owalu |
Wyjście
Narysowanie na powierzchni graficznej owalu o środku w punkcie (xs,
ys), o promieniach rx, ry i w kolorze color
Dane pomocnicze
| x, y |
- |
współrzędne punktów na obwodzie okręgu o środku w początku układu
współrzędnych |
| e |
- |
wyrażenie błędu dla punktu P |
| e1 |
- |
wyrażenie błędu dla punktu P1 |
| e2 |
- |
wyrażenie błędu dla punktu P2 |
Lista kroków
| K01: |
x ← 0 |
; ustalamy współrzędne punktu startowego |
| K02: |
y ← ry |
|
| K03: |
e ← 0 |
|
| K04: |
Dopóki ry2x ≤ rx2y
wykonuj kroki K05...K13 |
; górna część ćwiartki elipsy |
| K05: |
e1 ← e + 2ry2x
+ ry2 |
; wyrażenie błędu dla P1(x+1,y) |
| K06: |
e2 ← e1 - 2rx2y
+ rx2 |
; wyrażenie błędu dla P2(x+1,y-1) |
| K07: |
Jeśli e1 + e2
< 0, idź do kroku K12 |
|
| K08: |
Rysuj linię w kolorze color od (-x+xs,y+ys)
do (x+xs.y+ys) |
; rysujemy linie wypełniające |
| K09: |
Rysuj linię w kolorze color od (-x+xs,-y+ys)
do (x+xs.-y+ys) |
|
| K10: |
e ← e2 |
; wybieramy P2(x+1,y-1) |
| K11: |
y ← y - 1 i idź do K13 |
|
| K12: |
e ← e1 |
; wybieramy P1(x+1,y) |
| K13: |
x ← x + 1 |
; w górnej części ćwiartki x zawsze jest
zwiększane o 1 |
| K14: |
Dopóki y ≥ 0 wykonuj kroki K15...K23 |
; przechodzimy do dolnej części ćwiartki |
| K15: |
Rysuj linię w kolorze color od (-x+xs,y+ys)
do (x+xs.y+ys) |
; rysujemy linie wypełniające |
| K16: |
Rysuj linię w kolorze color od (-x+xs,-y+ys)
do (x+xs.-y+ys) |
|
| K17: |
e1 ← e - 2rx2y
+ rx2 |
; wyrażenie błędu dla P1(x,y-1) |
| K18: |
e2 ← e1 + 2ry2x
+ ry2 |
; wyrażenie błędu dla P2(x+1,y-1) |
| K19: |
y ← y - 1 |
; w dolnej części ćwiartki y zawsze jest
zmniejszane o 1 |
| K20: |
Jeśli e1 + e2
≥ 0, idź do kroku K23 |
|
| K21: |
e ← e2 |
; wybieramy punkt P2(x+1,y-1) |
| K22: |
x ← x + 1 i kontynuuj następny obieg
pętli K14 |
|
| K23: |
e ← e1 |
; wybieramy P1(x,y-1) |
| K24: |
Zakończ |
|
Na końcu pliku nagłówkowego SDL_gfx.h dopisz
prototypy funkcji:
void gfxFillEllipse(SDL_Surface * s, Sint32 xs, Sint32 ys, Sint32 rx, Sint32 ry, Uint32 color);
Funkcja rysuje wypełnioną elipsę, czyli owal. Figura jest obcinana do
prostokąta obcinającego zawartego w strukturze SDL_Surface. Posiada
identyczne parametry jak poprzednie dwie funkcje:
| s |
- |
wskaźnik struktury SDL_Surface. |
| xs ys |
- |
współrzędne środka owalu |
| rx ry |
- |
promienie owalu odpowiednio wzdłuż osi OX i OY |
| color |
- |
kolor wypełnienia |
Na końcu pliku SDL_gfx.cpp dopisz definicje funkcji:
// Rysuje wypełnioną elipsę
// s - wskaźnik struktury SDL_Surface
// xs,ys - współrzędne środka
// rx - promień elipsy na osi OX
// ry - promień elipsy na osi OY
// color - kolor obrysu
//---------------------------------------
void gfxFillEllipse(SDL_Surface * s, Sint32 xs, Sint32 ys, Sint32 rx, Sint32 ry, Uint32 color)
{
Sint32 x = 0, y = ry;
Sint32 e = 0, e1, e2;
Sint32 rx2 = rx * rx, ry2 = ry * ry;
Sint32 fx = 0, fy = rx2 * ry;
while(fx <= fy)
{
e1 = e + (fx << 1) + ry2;
e2 = e1 - (fy << 1) + rx2;
if(e1 + e2 >= 0)
{
gfxClipHLine(s,-x + xs, y + ys, color,(x << 1) + 1);
gfxClipHLine(s,-x + xs,-y + ys, color,(x << 1) + 1);
e = e2; y--; fy -= rx2;
}
else e = e1;
x++; fx += ry2;
}
while(y >= 0)
{
gfxClipHLine(s,-x + xs, y + ys, color,(x << 1) + 1);
gfxClipHLine(s,-x + xs,-y + ys, color,(x << 1) + 1);
e1 = e - (fy << 1) + rx2;
e2 = e1 + (fx << 1) + ry2;
y--; fy -= rx2;
if(e1 + e2 < 0)
{
e = e2; x++; fx += ry2;
}
else e = e1;
}
}
Poniższy program testuje wszystkie nowe funkcje rysowania okręgów, kół,
elips oraz owali.
// I Liceum Ogólnokształcące
// w Tarnowie
// Koło informatyczne
//
// P042 - Okręgi i elipsy
//-----------------------
#include <SDL/SDL_gfx.h>
#include <SDL/SDL_gui.h>
const int SCRX = 320; // stałe określające szerokość i wysokość
const int SCRY = 240; // ekranu w pikselach
const int MAXF = 15; // liczba powtórzeń rysowania figury
SDL_Surface * screen;
gfxFont * font = gfxOpenFont("vecprop9x12.fnt");
// Funkcja obsługująca przyciski poleceń
//--------------------------------------
void fnb(gfxGUIObject * sender)
{
Sint32 xs, ys, rx, ry, rr;
Uint32 color;
SDL_Rect r;
r.x = r.y = 0;
r.w = screen->w;
r.h = screen->h - 16 - font->h;
if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen);
SDL_FillRect(screen, &r, 0);
xs = screen->w >> 1;
ys = (screen->h >> 1) - 8;
rr = ys - 12 - font->h;
rx = xs - 8;
ry = ys - 12 - font->h;
switch(sender->tag)
{
case 0: for(int i = 1; i <= MAXF; i++)
{
gfxCircle(screen, xs, ys, rr, 0xffff00);
rr = ((MAXF - 1) * rr) / MAXF;
}
break;
case 1: color = 255;
for(int i = 1; i <= MAXF; i++)
{
gfxFillCircle(screen, xs, ys, rr, color << 16);
rr = ((MAXF - 1) * rr) / MAXF;
color = ((MAXF - 1) * color) / MAXF;
}
break;
case 2: for(int i = 1; i <= MAXF; i++)
{
gfxEllipse(screen, xs, ys, rx, ry, 0xffff00);
rx = ((MAXF - 1) * rx) / MAXF;
ry = ((MAXF - 1) * ry) / MAXF;
}
break;
case 3: color = 255;
for(int i = 1; i <= MAXF; i++)
{
gfxFillEllipse(screen, xs, ys, rx, ry, color + (color << 8));
rx = ((MAXF - 1) * rx) / MAXF;
ry = ((MAXF - 1) * ry) / MAXF;
color = ((MAXF - 1) * color) / MAXF;
}
break;
case 4: if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);
exit(0);
}
gfxLine(screen, xs - 5, ys, xs + 5, ys, 0xff0000);
gfxLine(screen, xs, ys - 5, xs, ys + 5, 0xff0000);
if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);
SDL_UpdateRect(screen, r.x, r.y, r.w, r.h);
}
//***********************
// *** Program główny ***
//***********************
int main(int argc, char * argv[])
{
// tablica tekstów opisujących przyciski
char * t[] = {"Okrąg", "Koło", "Elipsa", "Owal", "Zakończ"};
// tablica 5 wskaźników do przycisków
gfxButton * b[5];
if(SDL_Init(SDL_INIT_VIDEO)) exit(-1);
atexit(SDL_Quit);
if(!(screen = SDL_SetVideoMode(SCRX, SCRY, 32, SDL_HWSURFACE))) exit(-1);
// tworzymy przyciski akcji
SDL_Rect r;
r.x = r.w = 0;
r.h = font->h + 8;
r.y = screen->h - r.h - 4;
for(int i = 0; i < 5; i++)
r.w += 20 + gfxTextLength(font, t[i]);
r.x = (screen->w - r.w - 4) >> 1;
for(int i = 0; i < 5; i++)
{
r.w = 16 + gfxTextLength(font, t[i]);
b[i] = new gfxButton(i, true, screen, font, &r, t[i], fnb);
r.x += r.w + 4;
}
// Obsługujemy zdarzenia
SDL_Event event;
bool running = true;
while(running)
{
while(SDL_WaitEvent(&event))
{
bool eventfree;
for(int i = 0; i < 5; i++)
if(!(eventfree = b[i]->DoEvents(&event))) break;
if(eventfree && (event.type == SDL_QUIT))
{
running = false;
break;
}
}
}
// zamykamy czcionkę
gfxCloseFont(font);
// Usuwamy przyciski
for(int i = 0; i < 5; i++) delete b[i];
return 0;
}
