Algorytmy wypełniania
Algorytmy wypełniania
obszaru
obszaru

Są stosowane do wypełniania
obszarów, których granice są
określone.

Zapewniają poprawnie działanie na
obszarach o dowolnych kształtach.

Umożliwiają zmianę koloru prymitywów.

Nie są uzależnione od uprzednio
rysowanych obiektów (prymitywów)
Wypełnianie oparte na ilości
Wypełnianie oparte na ilości
przecięć
przecięć
Problem:
?? ??

Określenie, czy dany punkt leży
wewnątrz czy na zewnątrz obszaru.
Algorytm:
1 2 3

Z analizowanego punktu
wyprowadzamy półprostą w
dowolnym kierunku (najlepiej
1 2
poziomym).

Jeżeli półprosta przecina brzeg
obszaru nieparzystą ilość razy to
punkt leży wewnątrz obszaru.

W przeciwnym razie punkt leży na
1 czy 2?
zewnątrz obszaru.
Wady
Wady

Brak poprawności dla przypadków
szczególnych (pokrywanie, wierzchołki)
- wymagana dalsza analiza.

Częściowe wypełnianie obszaru.
Liczenie obrotów
Liczenie obrotów

Wyobraz
sobie, że
obserwujesz punkt
poruszający się po
obwodzie obszaru.

Jeżeli w trakcie
obserwacji wykonałeś co
najmniej jeden pełny
obrót to punkt obserwacji
należy do obszaru.

W przeciwnym wypadku
punkt leży poza
obszarem.
Wypełnianie obrysu
Wypełnianie obrysu
Rozpoczynamy wypełniać obrys od
punktu, który znajduje się w jego wnętrzu.

Prosty algorytm rekurencyjny:
void boundaryFill(TScreen screen, int x, int y, TColor fill, TColor boundary)
{
if (x < screen.Left || x >= screen.Right) return;
if (y < screen.Top || y >= screen.Bottom) return;
if ((screen[x][y] != boundary) && (screen[x][y] != fill)) {
screen[x][y] = fill;
boundaryFill(screen, x+1, y, fill, boundary);
boundaryFill(screen, x, y+1, fill, boundary);
boundaryFill(screen, x-1, y, fill, boundary);
boundaryFill(screen, x, y-1, fill, boundary);
}
}
Zalety i wady
Zalety i wady

Wypełnia obszar ograniczony brzegiem
o wskazanym kolorze.
Wada:

Nieefektywny dla dużych obszarów 
możliwość przepełnienia stosu.
Możliwe rozwiązanie:

Zastosowanie listy punktów zamiast
rekurencji.
Wypełnianie wielokątów
Wypełnianie wielokątów
Metoda przeglądania linii:

Wyznaczane są segmenty,
które leżą pomiędzy lewymi
i prawymi krawędziami
wielokąta.

Końce segmentów wyznaczane na
podstawie algorytmu przyrostowego.
Proces wypełniania
Proces wypełniania

Znajdz
przecięcie rozpatrywanej linii ze
wszystkimi krawędziami wielokąta.

Posortuj przecięcia według rosnącej
wartości x.

Wypełnij obszar pomiędzy parą
punktów, korzystając z reguły
parzystości.
Przypadki szczególne
Przypadki szczególne

Wartość przecięcia jest liczbą
rzeczywistą.

Wartość przecięcia jest liczbą całkowitą

Przecięcie przechodzi przez
wierzchołek.

Wierzchołki definiują
poziomą krawędz
.
Algorytm wyznaczanie lewej
Algorytm wyznaczanie lewej
krawędzi wielokąta
krawędzi wielokąta
void leftEdge( int xmin, int ymin, int xmax, int ymax,
TScreen screen, TColor color)
{
int x = xmin;
int licz = xmax  xmin;
int mian = ymax  ymin;
i = mian;
for (y = ymin; y < ymax; y++) {
screen[x][y] = color;
i += licz;
if (i > mian) {
x += 1;
i -= mian;
}
}
Globalna tablica krawędzi
Globalna tablica krawędzi

Utworzenie tablicy krawędzi
posortowanych ze względu na ich
najmniejsze współrzędne y.
8
7 -> EF |10 | 10 | | -> ED |11| 10 | | -> 0
6
5
4 -> CD |11|15 | | -> 0
3
2 -> AF |10| 7 | | -> 0
1 -> AB | 2 | 11 | | -> BC | 4 | 11 | 4/3 | -> 0
0 ymax xmin 1/a
y
Tablica aktywnych krawędzi
Tablica aktywnych krawędzi

Krawędzie posortowane ze względu na wartości x
przecięć.

Przy przesuwaniu się do następnej linii (y + 1)
tablica ta jest uaktualniana:

usuwane krawędzie, dla których ymax = y,

dodawane krawędzie, dla których ymin = y + 1
Przykłady:
dla y = 6
y = 6 => AF -> CD
Dla y = 9
y = 9 => AF -> EF -> DE -> CE
Algorytm przeglądania
Algorytm przeglądania
wierszami
wierszami

Ustaw y na najmniejszej współrzędnej y z globalnej
tablicy.

Wyzeruj tablicę aktywnych krawędzi.

Powtarzaj dopóty tablice aktywna i globalna nie są puste:

przesuń z tab. globalnej do aktywnej te krawędzie dla
których ymin = y i posortuj aktywną tab. względem x.

wypełnij piksele odpowiednią wartością w
przeglądanej linii y,

usuń z tab. aktywnych krawędzi te pozycje, dla
których y = ymax,

zwiększ y o 1,

dla każdej krawędzi, która nie jest pionowa i jest w
tab. aktywnych krawędzi, uaktualnij x dla nowego y.