WYKA
AD 3
3. Wypełnianie konturów
3.1. Wypełnianie wieIoboków
Zasada parzystości:
Prosta nie przechodząca przez wierzchołek przecina
wieIobok parzystą iIość razy.
1 - prosta nie przechodzi przez wierzchołek, Iiczba
przecięć wynosi 6.
2 - prosta przechodzi przez wierzchołek, Iiczba
przecięć wynosi 3.
3 - prosta przechodzi przez wierzchołek, Iiczba
przecięć wynosi 6.
4 - prosta pokrywa się z krawędzią poziomą.
3.1.1. AIgorytm przegIądania Iinii
(scan line algorithm )
3.1.1.1. Założenia
Dany jest wieIobok ( bez krawędzi poziomych )
opisany jako zbiór krawędzi .
Opis wieloboku:
Krawędz

AB 1 5 9 2
BC 1 7 914
CD 7 121414
DE 9 12 714
EF 9 11 7 2
FA 5 11 2 2
Zasada wypełniania:
W przegIądanej Iinii naIeży wypełniać punkty
pomiędzy poszczegóInymi parami krawędzi .
Na rysunku dla y = 10 między FA - EF i DE - CD.
3.1.1.2. Opis algorytmu
Krok 0
Utworzyć gIobaIną tabIicę krawędzi (ET).
Krok 1
Ustawić y na najmniejszej wartości współrzędnej y z
gIobaInej tabIicy krawędzi (ET), czyIi y dla pierwszej
niepustej grupy krawędzi.
Krok 2
Wyzerować aktywną tabIicę krawędzi (AT).
Krok 3
Powtarzać tak długo, dopóki tabIica gIobaIna (ET) i
tabIica aktywna (AT) nie będą puste.
" Przenieść z grupy y tablicy globalnej (ET) do tablicy
aktywnej (AT) te krawędzie, dIa których =
i posortować je ze wzgIędu na x.
" Wypełnić pikseIe w Iinii y, wykorzystując pary x z
tablicy aktywnej (AT).
" Usunąć z tabIicy aktywnej (AT) te krawędzie, dIa
których = .
" Zwiększyć y o 1 (następna Iinia).
" DIa każdej pary krawędzi, która nie jest pionowa
wyIiczyć i wstawić do tabIicy aktywnej (AT) nowe
wartości x.
Krok 0 - Tworzenie gIobaInej tabIicy krawędzi (ET)
EF
DE
...
11 7 -5/2 *
12 7 7/3 *
9
...
CD
...
12 14 0 *
7
...
FA
y
...
5 11 2 0 *
...
...
AB BC
...
5 9 -7/4 *
0
1 7 9 5/6 *
0
x 1/a
KoIejność porządkowania:
" minimum - przypisanie do grupy
" minimum - porządkowanie w grupie
" minimum - porządkowanie w grupie
" minimum - porządkowanie w grupie
Krok 1
Ustawiamy y na najmniejszej wartości współrzędnej y
z gIobaInej tabIicy krawędzi.
y = 1
Krok 2
Zerujemy aktywną tabIicę krawędzi (AT).
Krok 3
Przenosimy z grupy y tablicy globalbej (ET) do tablicy
aktywnej (AT) te krawędzie, dIa których =
i sortujemy krawędzie ze wzgIędu na x.
(AT)
AB BC
y
5 9 -7/4 *
0
1 7 9 5/6 *
x 1/a
" Wypełniamy pikseIe w Iinii y, wykorzystując pary x z
tabIicy aktywnej (AT) i zasadę parzystości.
" Usuwamy z tabIicy aktywnej (AT) te krawędzie, dIa
których = , ( brak takich krawędzi )
" Zwiększamy y o 1 ( y = 2 ).
" DIa każdej pary krawędzi, która nie jest pionowa
wyliczamy i wstawiamy do tablicy aktywnej (AT)
nowe wartości x.
Sposób obIiczania nowych wartości x ;
a) = - + (algorytm DDA ),
b) algorytm Bresenhama,
(AT)
AB
BC
5 7 -7/4 *
0
2 7 10 5/6 *
y x 1/a
Koniec pierwszego przebiegu dla kroku 3
W kolejnym przebiegu uzyskamy rysunek :
Postępujemy anaIogicznie aż do osiągnięcia y = 5
DIa y = 5 rysunek wygIąda następująco:
DIa krawędzi AB zachodzi = ( koniec krawędzi ).
Usuwamy AB z tablicy aktywnej (AT).
Przenosimy do tablicy aktywnej z tablicy globalnej
(ET) krawędz
FA, dIa której = .
Porządkujemy tabIicę (AT) ze wzgIędu na x.
TabIica aktywna przybiera postać:
FA
BC
11 2 0 *
0
6 7 15 5/6 *
y x 1/a
Kontynuujemy wypełnianie aż osiągniemy koniec
krawędzi występującej w tabIicy aktywnej (AT), Iub
początek krawędzi z tabIicy gIobaInej (ET).
W rozważanym przypadku dIa y = 7, osiągamy koniec
krawędzi BC.
Uzyskany efekt wypełnienia pokazuje następny
rysunek.
Po usunięciu z tabIicy aktywnej (AT) krawędzi BC,
zwiększeniu y i przeniesieniu z tablicy globalnej (ET)
krawędzi CD tabIica aktywna przyjmuje postać:
(AT)
FA
CD
11 2 0 *
0
8 12 14 0 *
Wypełniając daIej, osiągamy wartość y = 9 .Rysunek
wygIąda następująco:
Stwierdzamy, że dIa y = 9 para krawędzi EF i DE
spełnia warunek = .
W związku z tym przenosimy krawędzie EF i DE do
TabIicy aktywnej (AT), która po uporządkowaniu
eIementów ze wzgIędu na x przybiera postać:
(AT)
FA
EF
11 7 -5/2 *
11 2 0 *
0
9
12 7 7/3 *
12 14 0 *
DE CD
TabIica gIobaIna (ET) staje się pusta. Kontynuujemy
wypełnianie między parami krawędzi z tabIicy (AT), aż
do osiągnięcia y = 11.Uzyskujemy efekt jak na
rysunku:
Usuwamy z tabIicy (AT) parę krawędzi FA, EF.
(AT)
DE
CD
12 12 7/3 *
11 12 14 0 *
0
Wypełniamy następną Iinię i osiągamy końce krawędzi
DE i CD. Usuwany krawędzie z tabIic y. TabIic a (AT)
jest już pusta, czyIi kończymy wypełnianie.
Ostateczny efekt pokazuje rysunek.
3.1.2. Problemy dodatkowe
ProbIem krawędzi poziomych:
Rozwiązanie:
Pominięcie krawędzi poziomych w tabIicy (AT).
Przykłady:
1 - w tabIicy (AT) znajdzie się AJ i BC,
2 - w tabIicy (AT) znajdzie się IJ i DE,
3 - w tabIicy (AT) znajdzie się IJ i EF,
4 - w tabIicy (AT) znajdzie się GH i FE,
Problem brzegu wieloboku:
Rozwiązanie:
" rysować pikseIe Ieżące wewnątrz wieIoboku, aIe nie
na brzegu,
" rysować pikseIe naIeżące do Iewej krawędzi,
" rysować pikseIe naIeżące do doInej krawędzi.
ProbIem wieIoboków "bardzo wąskich" :
Zastosowano poprzednio opisaną konwencję
rysowania.
Obraz wieloboku W1 składa się tyIko z jednego punktu.
Brak zadawaIającego rozwiązania przy tym sposobie
rysowania.
NaIeży zastosować wypełnianie wieIotonowe.
3.2.Wypełnianie konturu zadanego w postaci obrazu
Założenie:
Dany jest kontur i punkt Ieżący wewnątrz konturu.
3.2.1. Kontur wypukły
DIa dowoInej pary punktów wewnętrznych odcinek,
którego końcami są te punkty Ieży w całości wewnątrz
konturu.
3.2.2. Algorytm wypełniania konturu wypukłego
" wypełniamy w Iinii poczynając od punktu
startowego, aż do prawej granicy konturu,
" znajdujemy " niższy " punkt konturu i wypełniamy
Iinię do Iewej granicy konturu,
" powtarzamy tak długo, dopóki możemy znaIez
ć
punkt " niższy ",
" wracamy do punktu startowego i kontynuujemy
proces poruszając się " w górę ".
3.2.3. Kontur niewypukły
Wypełnianie przez spójność:
Algorytm:
1. Wypełniane jest ziarno,
2. Sprawdzani są koIejno sąsiedzi, jeżeIi sprawdzany
sąsiad nie naIeży do konturu, przyjmowany jest
jako nowe ziarno i następuje powrót do punktu 1.