Wprowadzenie

Podstawową „jednostką” wypełnienia jest linia pozioma (ang. scanline). Jej granice, tj. początek i koniec wyznaczają jednoznacznie punkty przecięcia poziomej linii (o współrzędnej y) z dwiema krawędziami wielokąta. W przypadku wielokąta niewypukłego tych przecięć mogłoby być więcej — co nie znaczy że nie może być ich dokładnie dwa, ale stwierdzenie tego w ogólnym przypadku jest trudne. (Proponuję zapoznać się również z artykułem o wypełnianiu wielokątów).

Aby wypełnić trójkąt albo wypukły czworokąt należy podzielić figurę na trapezy o podstawach równoległych do osi OX — wypełnianie trapezów/trójkątów spełniających ten warunek jest bardzo proste.

Podział na trapezy wymaga zrzutowania wierzchołków (wzdłuż scanlinów) na naprzeciwległe krawędzie tak jak pokazano to na rysunkach niżej. Ponieważ współrzędna y jest znana, obliczenie współrzędnej x punktu sprowadza się do rozwiązania równania liniowego:

t = (y − y₁)/(y₂ − y1); x = x₁ + t ⋅ (x₂ − x1)

Wypełnianie trapezu

Ponieważ krawędzie trapezu są odcinkami nie ma potrzeby liczyć bezpośrednio przecięcia. Wystarczy obliczyć przyrosty współrzędnej x przy zmianie y o 1.

dx_L = (x₃ − x₁)/dy dx_R = (x₄ − x₂)/dy dy = y₂ − y₁

a następnie przy każdej zmianie współrzędnej y uaktualniać współrzędne x_L i x_R zgodnie z zależnościami:

x_L = x₁ + y ⋅ dx_L x_R = x₂ + y ⋅ dx_R y = y₁…y₂

Dzięki temu wypełnienie trapezu jest bardzo proste, oto przykładowa funkcja:

void fill_segment(int x1, int x2, int x3, int x4, int y1, int y2) {
        float dy  = y2-y1;
        float dxl = float(x3-x1)/dy;
        float dxl = float(x4-x2)/dy;

        float xl  = x1;
        float xr  = x2;
        for (int y=y1; y<y2; y++) {
                line_h(xl, xr, y);
                xl += dxl;
                yl += dxr;
        }
}

Ponieważ może zdarzyć się tak, że xl > xr więc funkcja line_h musiałaby uwzględniać i takie przypadki: w najlepszym razie poprzez zamianę kolejność x-ów, w najgorszym stawiać piksele z lewej do prawej, bądź z prawej do lewej. Można tego uniknąć i już na wstępie określić która ze współrzędnych jest „bardziej na lewo”:

• x1 != x2 — w tym przypadku decyduje oczywiście zależność x1 > x2,
• x1 == x2 — natomiast w tym zależność dxl > dxr.

if (((x1 != x2) && (x1 > x2)) || (x1 == x2) && (dxl > dxr)) {
        swap(dxl, dxr);
        swap( xl,  xr);
}

Wypełnianie trójkątów

Najpierw należy posortować wierzchołki wg rosnącego y; sortowanie najlepiej przeprowadzić metodą bąbelkową, trzeba ledwie trzech porównań:

if (P0.y < P1.y) swap(P0, P1);
if (P0.y < P2.y) swap(P0, P2);
if (P1.y < P2.y) swap(P1, P2);

W efekcie otrzymujemy posortowane wierzchołki w kolejności P₀, P₁, P₃, gdzie P₀.y = min. Następnie wierzchołek 1 rzutowany jest na krawędź 0-2, otrzymujemy nowy punkt P₁₁.

Ostatnim etapem jest wypełnienie dwóch obszarów (rosnący y):

• trójkąta P₀ − P₁ − P₁₁
• trójkąta P₁ − P₁₁ − P₂

Wypełnianie czworokątów

Tutaj nie można już wprost posortować wierzchołków względem współrzędnej y, ale należy znaleźć dwa skrajne wierzchołki: o minimalnej i maksymalnej współrzędnej y.

Jeśli wierzchołki dane są jako lista P₀, P₁, P₂, P₃, wskazać dwa indeksy (zakres 0-3) A — najmniejsza wartość y oraz D — największa. Zostają dwa wierzchołki — ich indeksy niech będą B oraz C.

Do rozpatrzenia są dwa przypadki, gdy skrajne wierzchołki P_A i P_D należą do jednej krawędzi (1), czy też nie (2).

Przykładowy program

Przykładowy program w Pythonie (wymaga biblioteki PIL):

• fill_tri_quad-demo.py