Rysowanie linii
Rysowanie linii
Na ekranie komputera można
narysować tylko przybliżenie idealnej
linii. Jest to spowodowane
koniecznością użycia układu
współrzędnych
o wartościach
dyskretnych.
Ważne własności linii
Ważne własności linii

Ciągłość.

Jednakowa grubość i jasność.

Dokładność (najlepsze przybliżenie
idealnej linii).

Szybkość rysowania.

Możliwość ustalenia grubości linii.
Najprostszy algorytm rysowania
Najprostszy algorytm rysowania
linii
linii
y = ax + b

Dane wejściowe:
P0(x0, y0), P1(x1, y1)

Współrzędne pikseli tworzących
linię:
Pi(xi, round(axi + b)) lub Pi(round(yi/a  b/a), yi)

Przypadek szczególny
x0 = x1  prosta pionowa.
Implementacja
Implementacja
// pseudo kod
void simpleLine(TScreen screen, TColor color, int x0, int y0, int x1, int y1) {
double a = (double) (y1 - y0) / (double)(x1 - x0),
b = y0 - a * x0;
for (int x = x0; x <= x1; x++) {
int y = a*x + b + 0.5;
screen[x][ y] = color;
}
}
Wady:

Generuje nieciągłe linie.

Wymaga obsłużenia szczególnych przypadków.
- linia pionowa;
dla x0 > x1 (zamiana współrzędnych).
-
- współczynnik a spełnia nierówność:  1 d" a d" 1

Algorytm używa czasochłonnego mnożenia i zaokrąglania.
Optymalizacja  przyspieszanie
Optymalizacja  przyspieszanie
obliczeń
obliczeń

Operacje dodawania Wykorzystanie
i odejmowania są wyników wcześniej
wykonywane szybciej wykonanych obliczeń.
niż operacje

Obliczenia na liczbach
mnożenia.
całkowitych wykonują

Operacja mnożenia
się szybciej niż
jest szybsza od
obliczenia na liczbach
operacji dzielenia.
rzeczywistych
Algorytm przyrostowy
Algorytm przyrostowy
(DDA)
(DDA)
yi+1 = axi+1 + b =
= a(xi + "x) + b =
= axi + a "x + b =
= yi + a"x
dla "x = 1
yi+1 = yi + a

Wada. Zaokrąglanie.
Algorytm DDA (pseudo kod)
Algorytm DDA (pseudo kod)
void lineDDA(TScreen screen, TColor color,
else {
int x0, int y0, int x1, int y1){
double a = (double)dx/(double)dy;
screen[x0][ y0] = color;
double x = x0;
int dx = x1 - x0,
if (dy < 0) {
dy = y1 - y0;
dy = -1;
if (fabs(dx) >= fabs(dy)) {
a = -a;
double a = (double)dy/(double)dx;
}
double y = y0;
else dy = 1;
if (dx < 0) {
while (y0 != y1) {
dx = -1;
y0 += dy;
a = -a;
x += a;
} else dx = 1;
screen[x][ y0] = color;
while (x0 != x1) {
}
x0 += dx;
}
y += a;
}
screen[x0][ y] = color;
}
}
Algorytm z punktem
Algorytm z punktem
środkowym (Bresenham)
środkowym (Bresenham)
Równanie prostej wyrażone
poprzez funkcję uwikłaną:
F(x, y) = dy�x  dx�y + b�dx = 0
Własności:
F(x,y) = 0  dla (x, y) leżącego
na prostej.
F(x,y) = > 0  dla (x, y)
leżącego powyżej prostej.
F(x,y) < 0  dla (x, y) leżącego
poniżej prostej.
dec = F(S) = F(x + 1, y + �)
Algorytm z punktem
Algorytm z punktem
środkowym (Bresenham)
środkowym (Bresenham)

Wybór kolejnego punku S (Wartość zmiennej dec dla
następnego kroku można otrzymać bez obliczania
F(S)):
- jeżeli poprzednio było D to:
dec = dec + dy
- jeżeli poprzednio było G to:
dec = dec + (dy - dx).

Mnożymy stronami równanie F(S) = 0 przez 2, aby
wyeliminować ułamki i operować tylko na liczbach
całkowitych.
Implementacja algorytmu
Implementacja algorytmu
Bresenhama
Bresenhama
// działa dla przypadku:
while (x < x1) {
// 0 <= a <= 1 i x0 < x1
if (dec <= 0)
void lineBresenhamSimple(TScreen screen,
dec += incD;
TColor color, int x0, int y0, int x1, int y1) {
else {
int dy = y1 - y0;
dec += incG;
int dx = x1 - x0;
y++;
int dec = 2 * dy - dx;
}
int incG = (dy - dx) * 2;
x++;
int incD = dy * 2;
screen[x][y] = color;
int x = x0;
}
int y = y0;
}
screen[x0][y0] = color;
Algorytm z punktem
Algorytm z punktem
środkowym
środkowym

Działa dla dowolnie określonej linii.

Można rozpocząć wyznaczanie punków linii
(odcinka) od środka w kierunku jednego końca.
Piksele w kierunku drugiego końca można
wyznaczyć bez obliczeń korzystając z symetrii.
Implementacja
Implementacja
void lineBresenham(TSreem screem, TColor color,
else {
int x0, int y0, int x1, int y1) {
int dec = dx - (dy >> 1);
int dy = y1 - y0;
while (y0 != y1) {
int dx = x1 - x0;
if (dec >= 0) {
int stepx, stepy;
x0 += stepx;
if (dy < 0) { dy = -dy; stepy = -1; } else { stepy = 1; }
if (dx < 0) { dx = -dx; stepx = -1; } else { stepx = 1; }
dec -= dy;
dy <<= 1; // dy = 2*dy
}
dx <<= 1; // dx = 2*dx
y0 += stepy;
screen[x0][ y0] = color;
dec += dx;
if (dx > dy) {
screen[x0][y0] = color;
int dec = dy - (dx >> 1); // to samo co dy - 2dx
}
while (x0 != x1) {
}
if (dec >= 0) {
}
y0 += stepy;
dec -= dx;
}
x0 += stepx;
dec += dy;
screen[x0][y0] = color;
}
}
Algorytm z podwójnym
Algorytm z podwójnym
krokiem (Xiaolin Wu)
krokiem (Xiaolin Wu)

Dwukrotnie zredukowana
liczba decyzji (wyznaczamy
parę pikseli a nie
pojedynczy piksel).

dec = 4dy  dx.

Dla 0 < a < � jeżeli:
- dec mniejsze od zera to
wzór 1;
- dec < 2dy wzór 2;
- w pozostałych przypadkach
3;

Przyrost:
deci+1 = di + 4dy dla deci < 0;
-
deci+1 = di + 4dy  2dx w
-
pozostałych przypadkach.
Rysowanie okręgów
Rysowanie okręgów

Ciągłość.

Jednakowa grubość i jasność.

Dokładność (najlepsze przybliżenie
idealnego okręgu).

Szybkość rysowania.

Możliwość ustalenia grubości okręgu.
Prosty algorytm rysowania
Prosty algorytm rysowania
okręgu
okręgu

Równanie okręgu:
x2 + y2 = r2
y = ą r2 - x2 , 0 d" x d" r

Czterokrotna
symetria.

Wykorzystanie
Wady:
przesunięcia.

Metoda nieefektywna
(stosowanie mnożenia
i pierwiastków).

Brak ciągłości.
Wykorzystanie ośmiokrotnej
Wykorzystanie ośmiokrotnej
symetrii
symetrii
// pseudo kod Builder c++
void putPixel(TScreem screem, int x, int y, Color color, int xs, int ys) {
screem[x + xs][y + ys] = color;
screem[y + xs][x + ys] = color;
screem[y + xs][-x + ys] = color;
screem[x + xs][-y + ys] = color;
screem[-x + xs][-y + ys] = color;
screem[-y + xs][-x + ys] = color;
screem[-y + xs][x + ys] = color;
screem[-x + xs][y + ys] = color;
}
Algorytm z punktem
Algorytm z punktem
środkowym (Bresenham)
środkowym (Bresenham)
F(x, y) = x2 + y2 + r2 = 0
Własności:
" F(x,y) = 0  dla (x, y)
leżącego na okręgu.
" F(x,y) = > 0  dla (x, y)
leżącego poza okręgiem.
" F(x,y) < 0  dla (x, y)

Wykonujemy obliczenia
leżącego wewnątrz
okręgu. dla drugiego oktantu.

d = F(S) = F(x + 1, y + �)
Korzystamy z
ośmiokrotnej symetrii.
Wyznaczenie nowego
Wyznaczenie nowego
punktu okręgu
punktu okręgu
dold = F(x + 1, y  �) = (x + 1)2 + (y  �)2  r2
Przy wyborze punktu G (dold < 0) następny punkt
środkowy obliczamy z:
dnewG = F(x + 2, y  �) = (x + 2)2 + (y  �)2  r2
stąd "G = dnewG  dold = 2x + 3.
Jeżeli dold e" 0 to wybieramy punkt D:
dnewD = F(x + 2, y  3/2) = (x + 2)2 + (y  3/2)2  r2
stąd "D = dnewD  dold = 2x  2y + 5.
Uwaga !. Do obliczenia d bierzemy współrzędne
x i y poprzednio wyznaczonego piksela.
Funkcja rysująca okrąg
Funkcja rysująca okrąg
void drawCircle(int xs, int ys, int r, TColor

Rozpoczynamy od
color, TScreen screen){
int x = 0, y = r;
(0, r),
// double d = 5.0/4.0 - r;
d = 5/4  r.
int d = 1 - r;
putPixel(screen, x, y, color, xs, ys);

Można
while (y > x) {
wyeliminować if (d < 0) {
d += (x << 1) + 3; //d += x << 1 + 3;
ułamki zmieniając
} else {
powyższą instrukcję
d+= ((x - y) << 1) + 5;
y--;
na d = 1 - r
}
x++;
putPixel(screen, x, y, color, xs, ys);
}
}
Problemy
Problemy

Kolejność punktów końcowych
Czy odcinek rysowany z punktu P1 do P2 pokrywa
się z odcinkiem rysowanym z punktu P2 do P1?

Zmiana jasności odcinka w zależności
od jego nachylenia.
Pogrubianie prymitywów
Pogrubianie prymitywów

Powielanie pikseli.
- przy nachyleniu linii od -1 do
1 powielane są piksele w
kolumnach, w pozostałych
przypadkach w wierszach.
Wady

Pionowe lub poziome końce
odcinka.

Brak pikseli przy przejściu od
powielania poziomego do
pionowego (lub odwrotnie) 
widoczne zwężenie.
Pogrubianie prymitywów
Pogrubianie prymitywów

Ruchome pióro.
- dowolny kształt pióra,
- naturalne zakończenie końców linii
Wada:

Pogrubione linie
o nachyleniu
ok. ą450.
Usuwanie zakłóceń 
Usuwanie zakłóceń 
antyaliasing
antyaliasing

Aliasing  widoczne ząbkowane
zakłócenia linii ukośnych.

Antyaliasing  usuwanie lub
redukcja aliasingu.

Zwiększenie rozdziel-
czości?

Tak, ale potrzeba
więcej pamięci.

Redukuje problem
ale nie usuwa go.
Bezwagowe próbkowanie
Bezwagowe próbkowanie
powierzchni
powierzchni
Założenia:

Każda rysowana na ekranie
linia posiada niezerową
grubość  przypomina
prostokąt.

Piksele mają kształt kwadratu.

Na jasność piksela wpływa
tylko stopień jego pokrycia
przez linię.
Poziom szarości piksela linii
zależy od wielkości jego
pokrycia przez fragment linii.
Wagowe próbkowanie
Wagowe próbkowanie
powierzchni
powierzchni
Zmiana trzeciego założenia na:

Jasność piksela zależy od jego
odległości od środka linii.

Przyjmujemy, że piksel na kształt stożka.

Jasność piksela jest
proporcjonalna do
objętości części stożka
leżącej nad częścią
wspólną piksela i linii.
Nadpróbkowanie
Nadpróbkowanie
ang. supersampling
ang. supersampling

Generowanie w pamięci obrazu o
większej rozdzielczości. Wyświetlanie na
ekranie obrazu o mniejszej
rozdzielczości (uśrednianie obszarów).

Sposoby nadpróbkowania:

losowe,

jednorodne,

jitter (roztrzęsione).

Duże wymagania pamięci,
przepustowości i szybkości procesorów
graficznych (od Geforce2)