Algorytmy rysowania

Celem dzisiejszego ćwiczenia jest omówienie 3 algorytmów do rysowania przez modyfikację bufora pikseli:

• algorytmu rysowania na podstawie wzoru na prostą y=ax+b
• algorytmu rysowania linii Bresenhama
• rekurencyjnego algorytmu do wypełniania dowolnego kształtu

Zadanie zacznijmy od przygotowania środowiska do pracy. Zacznijmy od prostego projektu:

<style> body { background-color:#ccc; } </style>

<script src="//cdnjs.cloudflare.com/ajax/libs/p5.js/0.5.7/p5.js"></script>

<script type="text/javascript">

function setup() {

    createCanvas(512,512);

    background(255);

}

</script>

Dodamy do skryptu (pod funkcją setup) 4 zmienne reprezentujące odpowiednio współrzędne początku i końca rysowanej linii:

var x0=-1;

var y0=-1;

var x1=-1;

var y1=-1;

Nie wpiszemy współrzędnych jednak do kodu, tylko pozwolimy je użytkownikowi wybrać poprzez kliknięcie. W momencie jak użytkownik naciśnie klawisz, zapiszemy najpierw współrzędne początkowe:

function mousePressed() {

    x0=mouseX;

    y0=mouseY;

}

Potem jak użytkownik będzie poruszał myszką (z naciśniętym klawiszem) narysujemy dwa kółka odpowiadające wybranemu początkowi i końcowi:

function mouseDragged() {  

    x1=mouseX;

    y1=mouseY;  

    background(255);

    noStroke();

    fill('red');

    ellipse(x0-3,y0-3,6);

    fill('green');  

    ellipse(x1-3,y1-3,6);

}

Po opuszczeniu klawisza chcemy skasować ekran i uruchomić odpowiedni algorytm do rysowania linii:

function mouseReleased() {

  background(255);

  loadPixels();

  draw_line();

  updatePixels();

}

Zanim przejdziemy do implementowania funkcji draw_line przyda nam się funkcja do zamalowywania pikseli na kolor w odcieniach szarości:

function set_pixel(x,y,c) {

    idx=(y*512+x)*4;

    pixels[idx]=c;

    pixels[idx+1]=c;

    pixels[idx+2]=c;

    pixels[idx+3]=255;

}

Teraz możemy zadeklarować naszą funkcję do rysowania linii:

function draw_line() {  

}

Jeśli uruchomisz teraz program, możesz przetestować działanie obsługi myszy, ale na razie linie nie są jeszcze rysowane.

"Prosty" algorytm do rysowania linii

(zadanie na ocenę 3)

Algorytm ten tworzy na ekranie przybliżony kształt linii piksel po pikselu. Dla każdej kolumny rastra wyliczany jest wiersz, w którym powinien pojawić się piksel zgodnie ze wzorem na prostą:

Musimy zatem wyliczyć długość linii po osi x:

oraz długość po osi y:

Z tych dwóch zmiennych wyliczamy współczynnik przyrostu y względem x:

Oraz stały współczynnik b:

Zadaniem algorytmu jest wyliczenie dla każdej wartości x biegnącej od x₀ do x₁ wartości y używając wzoru z samej góry (y=ax+b). Użyj funkcji set_pixel, żeby zamalować poszczególne piksele linii kolorem 0 (czyli czarnym).

Warto pamiętać o jednym szczególe. Wartości x i y są zmiennymi rzeczywistymi typu Number (w języku Javascript), ale pozycje pikseli mogą być tylko liczbami całkowitymi. Domyślny sposób zaokrąglania liczb jest "w dół" (czyli Math.floor). Żeby utrzymać zgodność z algorytmem Bresenhama (w kolejnych zadaniach), warto użyć zaokrąglania metodą Math.round.

Po zaimplementowaniu algorytmu powinieneś zobaczyć jego działanie. Czy linia jest rysowana bez względu na to, jaki punkt początkowy i końcowy wybierzemy? Czy zawsze wygląda poprawnie? Czy wiesz, co należy zrobić, żeby algorytm działał w każdym przypadku (nie musisz implementować tych zmian)?

Algorytm Bresenhama

Kiedyś komputery nie były najszybsze i nie potrafiły dużo, ale grafika komputerowa i jej algorytmy sięgają dawnej przeszłości, na przykład w filmie z 1958 roku, albo w grach komputerowych z 1964 roku. Jednym z podstawowych problemów wczesnych komputerów było liczenie operacji matematycznych wykorzystujących liczby rzeczywiste. Zresztą, nawet dzisiaj można zauważyć znaczną różnicę w operacjach na liczbach całkowitych w porównaniu do liczb rzeczywistych.

Celem algorytmu Bresenhama będą zatem dwie rzeczy:

• pozbycie się liczb rzeczywistych i zastąpienie ich liczbami całkowitymi
• pozbycie się kosztownych operacji matematycznych takich jak dzielenie (we wzorze na a) i zastąpienie ich przeważnie operacjami dodawania i odejmowania

Wstęp do algorytmu (zadanie na ocenę 3.5)

W tym zadaniu skupimy się na wersji algorytmu rysującej linie tylko w pierwszej ósmej okręgu, czyli linie o nachyleniu od 0 do 45 stopni (na ekranie). Zauważ, że dla tych linii kolejne piksele mają wartość x zawsze rosnącą o 1, a y czasami rośnie o 1 a czasami pozostaje na tym samym poziomie:

Lista współrzędnych pikseli dla linii powyżej:

(1,1) (2,1) (3,2) (4,2) (5,3) (6,3) (7,3) (8,4) (9,4) (10,5) (11,5)

Zauważ również, że idealna (czarna) linia, dla kolejnych wartości x, przechodzi między dwoma sąsiadującymi pikselami o różnych wartościach y. Na przykład, dla x=2, linia przechodzi między pikselami o wartości y=1 i y=2. Naszym zadaniem jest zamalowanie piksela, który jest "bliższy" linii. Do tego celu możemy zdefiniować funkcję, która liczy odległość linii od poszczególnych pikseli. Bierzemy standardowy wzór na linię i po prostu przerzucamy y na drugą stronę wzoru:

Po przełożeniu zmiennych, tak żeby zostały zdefiniowane tylko stałe, otrzymujemy następujący wzór:

Proszę zauważyć, że ten wzór, w sposób oczywisty, dla początku i końca linii daje wartość 0. Jeśli podstawimy dla x wartość x₀, a dla y wartość y₀, wzór jest równy 0. To samo dotyczy podstawienia dla x wartości x₁ i dla y wartości y₁. Dla pozostałych punktów wzór ten wylicza odległość linii od danego piksela.

Zmodyfikuj program z poprzedniego zadania, żeby policzyć wartość D_x,y dla wszystkich punktów całego obrazu. Użyj set_pixel, podając jako kolor wartość funkcji D_x,y. Aby poprawić wygląd obrazu, zmodyfikuj funkcję set_pixel, żeby do kanału czerwonego podstawić ujemną wartość koloru, do kanału zielonego normalną wartość, a do niebieskiego wartość 0. Po wykonaniu tej części zadania powinieneś otrzymać taki obraz:

Piksele o kolorze zielonym reprezentują wartości dodatnie, kolor czerwony reprezentuje wartości ujemne, a intensywność koloru ("value" z modelu HSV) to odległość piksela od prostej leżącej na wybranej linii. Kolor czarny to oczywiście wartość 0, czyli piksele leżące dokładnie na linii.

Jednym mankamentem powyższego wzoru jest stosowanie niewydajnej operacji dzielenia dy/dx. Jak się później okaże, nie interesuje nas dokładna wartość tej odległości, tylko czy dany piksel jest powyżej, czy poniżej linii. Dzięki temu możemy zmodyfikować nasz wzór, mnożąc obydwie strony przez dowolną wartość stałą. Zdefiniujmy więc inną funkcję odległości o nazwie D z daszkiem i zdefiniujmy ją jako poprzednią funkcję D pomnożoną przez 2dx:

Jeśli wprowadzisz tę funkcję do swojego programu, otrzymasz rysunek podobny do powyższego, ale będzie się on skupiał tylko na rozróżnianiu 3 przypadków: punkty leżące poniżej linii (kolor czerwony), powyżej linii (zielony) i na samej linii (czarny).

Do zaliczenia tego zadania, pokaż Prowadzącemu obydwa rozwiązania.

Algorytm rysowania linii (zadanie na ocenę 4)

Wróćmy teraz do algorytmu rysowania linii. Celem tego zadania będzie uzyskanie podobnego rysunku jak w zadaniu na ocenę 3, ale używając algorytmu Bresenhama.

Pierwszy punkt linii niewątpliwie zamalujemy na współrzędnych x₀, y₀. Pytaniem jest, jak wybrać następny i kolejne punkty. Wykorzystując przykład linii z początku tego rozdziału wiadomo, że musi to być albo punkt (2,1) albo (2,2). Żeby wybrać odpowiedni, zastanówmy się, jaka jest wartość funkcji D dla punktu leżącego dokładnie pomiędzy tymi dwoma kandydatami. Punkt ten ma położenie (2,1.5) albo inaczej mówiąc (x₀+1,y₀+0.5):

Punkt ten nazywa się punktem środkowym, albo po angielsku midpoint. Jego wartość funkcji D z powyższego obrazka wynosi -0.1 i można ją wyliczyć za pomocą tego wzoru:

Jeśli linia znajduje się powyżej tego punktu, to chcemy zamalować górny piksel, a jeśli znajduje się poniżej, to zamalujemy dolny. Czyli jeśli wartość funkcji D jest mniejsza od 0, to zamalujemy górny piksel, czyli (x₀+1,y₀), a jeśli jest większa (lub równa) 0, to zamalujemy dolny piksel, czyli (x₀+1,y₀+1).

Teraz warto przypomnieć, że algorytm ten działa tak samo poprawnie, jeśli zastosujemy funkcję D z daszkiem. Wyliczenie jest jednak w tym przypadku o wiele prostsze, ponieważ nie mamy operacji dzielenia i używamy tylko wartości całkowitych. Wynik tej funkcji wynosi -2 (D pomnożone razy 2dx albo inaczej mówiąc razy 20) i można go wyliczyć następującym wzorem:

Po przeliczeniu wstępnego punktu, nasuwa się pytanie, jak policzyć kolejne? Otóż, zamiast liczyć wartość D_x,y dla każdego punktu środkowego linii używając powyższych wzorów, warto zauważyć, że zmiana wartości funkcji D jest taka sama między poszczególnymi punktami środkowymi. Czyli wystarczy policzyć odległość pomiędzy dowolnymi dwoma sąsiednimi punktami środkowymi i dodawać tę odległość w każdym kroku algorytmu. Takie podejście jest często stosowane w algorytmach, np. DDA wykorzystuje podobną metodę.

Jest jednak tutaj pewna istotna uwaga! Jeśli linia biegnie w taki sposób, że musimy zamalować dwa piksele obok siebie, to odległość między sąsiednimi punktami środkowymi będzie inna niż w przypadku gdy zamalujemy piksele po przekątnej.

Na przykład, na rysunku poniżej widać, że chcąc zamalować trzeci piksel po kolei, sprawdzamy punkt środkowy na prawo od poprzedniego punktu środkowego: czyli dodajemy odległość między D(x₀+2,y₀+0.5) [zielony punkt] a D(x₀+1,y₀+0.5) [czerwony punkt], czyli długość żółtej linii. Jeśli jednak zamalowujemy czwarty piksel, interesuje nas punkt środkowy, który jest na prawo i w dół od poprzedniego punktu środkowego: czyli dodajemy odległość między D(x₀+3,y₀+1.5) [niebieski punkt] a D(x₀+2,y₀+0.5) [zielony punkt], czyli długość pomarańczowej linii:

Żeby policzyć te dwa przypadki, możemy podstawić podane zmienne do wzoru powyżej (na odległość z daszkiem) i otrzymamy (rozwinięcie zostawiam Tobie do przeliczenia):

Jeszcze raz zauważ, że te odległości wyniosą dokładnie tyle samo, jeśli je podstawimy pod kolejne punkty linii.

Podsumowując, mając podane x₀,y₀,x₁ i y₁ należy zdefiniować kolejne wartości:

Początkową wartość dla D:

Wartość, jaką dodajemy do D, jeśli zostajemy na tym samym poziomie y:

Oraz wartość dodawaną do D, jeśli zwiększamy wartość y:

Kolejne kroki algorytmu są następujące:

1. wylicz powyższe wartości stałe
2. ustaw D na wartość Dp oraz y na y₀
3. dla kolejnych wartości x biegnących od x₀ do x₁ (włącznie)
   1. zamaluj bieżący piksel (oznaczony wartościami x,y)
   2. jeśli D jest mniejsze od 0 zwiększ D o wartość Deq
   3. w innym wypadku (gdy D jest większe lub równe 0) zwiększ D o wartość Dinc i dodatkowo zwiększ y o 1

Na zaliczenie tego ćwiczenia zademonstruj działanie algorytmu do rysowania linii metodą Bresenhama dla pierwszej ósmej okręgu (tak jak opisano powyżej).

Algorytm wypełnienia obszaru

(zadanie na ocenę 4.5)

Istnieje kilka algorytmów do wypełniania zamkniętego obszaru, ale na tych ćwiczeniach zaimplementujemy prawdopodobnie najprostszy (i niekoniecznie wydajny) z nich - algorytm oparty na całkowitym przeszukiwaniu obrazu. Najprostszą metodą do implementacji tego algorytmu jest podejście rekurencyjne. Niestety, w przeglądarce jesteśmy ograniczeni głębokością rekurencji, więc musimy sami wymyślić sposób na implementację tego podejścia, bez pomocy struktur samego języka programowania.

Wywołanie funkcji jest zaimplementowane przy pomocy pojęcia stosu. Stos ten ma ograniczoną pojemność, w zależności od środowiska, w jakim pracujemy. Zamiast korzystać z "systemowego" stosu, możemy zaimplementować własny. Naturalną strukturą danych implementującą stos w Javascripcie jest po prostu tablica (Array):

• tablicę inicjujemy podstawiając do zmiennej puste nawiasy kwadratowe: stos=[];
• do stosu wrzucamy element metodą push: stos.push([x,y]);
• ze stosu możemy zdjąć ostatnio dodany element metodą pop: [x,y]=stack.pop();
• ilość elementów na stosie czytamy metodą length: if(stos.length>0)

Zacznijmy rozwiązanie tego zadania od następującego programu:

<style> body { background-color:#ccc; } </style>

<script src="//cdnjs.cloudflare.com/ajax/libs/p5.js/0.5.7/p5.js"></script>

<body oncontextmenu="return false;">

<script type="text/javascript">

function setup() {

    createCanvas(512,512);

    background(255);

}

var last_x=-1;

var last_y=-1;

function mouseDragged() {  

  if(mouseButton != LEFT) return;

  if(last_x>0) {

    line(last_x,last_y,mouseX,mouseY);

  }

  last_x=mouseX;

  last_y=mouseY;

}

function mouseReleased() {

  last_x=last_y=-1;

  if(mouseButton == RIGHT) {

    loadPixels();

    flood_fill(mouseX,mouseY);

    updatePixels();

  }

}

function set_pixel(x,y,c) {

    idx=(y*512+x)*4;

    pixels[idx]=c;

    pixels[idx+1]=c;

    pixels[idx+2]=c;

    pixels[idx+3]=255;

}

function get_pixel(x,y) {

 idx=(y*512+x)*4;

 return pixels[idx];

}

//właściwa funkcja do wypełniania

function flood_fill(x,y) {

}

</script>

</body>

Jest to rozszerzenie poprzedniego programu. Lewym przyciskiem myszy rysujemy ciągłą krzywą. Dzięki temu możemy szybko narysować jakiś zamknięty kształt do wypełnienia. Prawym przyciskiem wywołujemy metodę flood_fill. Twoim zadaniem jest zaimplementowanie tej metody według następującego pseudokodu:

1. stwórz pusty stos
2. wrzuć do niego współrzędne kliknięcia myszy (x,y) - podane jako argument funkcji
3. póki stos nie jest pusty
   1. zdejmij ze stosu ostatnie współrzędne
   2. sprawdź poprawność współrzędnych
      • jeśli współrzędne nie mieszczą się na ekranie, zrób continue
   3. pobierz kolor bieżącego piksela metodą get_pixel
   4. jeśli kolor ten nie jest biały (czyli taki, jaki możemy zamalowywać), zrób continue
   5. zamaluj bieżący piksel (najlepiej jakimś kolorem innym niż czarny, np. 200)
   6. dodaj do stosu sąsiadów bieżącego piksela
      • czyli piksel powyżej (x,y-1), poniżej (x,y+1), z lewej (x-1,y) i z prawej (x+1,y)

UWAGA: Implementując ten algorytm łatwo możesz popełnić błąd powodujący nieskończoną pętlę i zawieszenie przeglądarki. Radzę korzystać z usługi, gdzie można zapisywać postęp pracy (np. jsbin.com) albo ręcznie robić kopię zapasową programu przed jego włączeniem. Innym dobrym rozwiązaniem jest dodanie licznika do pętli i ograniczenie jej uruchomienia do kilku tysięcy iteracji. Czyli w punkcie 3, zamiast sprawdzać tylko, czy stos nie jest pusty, można dodać też kolejny argument:

while(stos.length>0 && cnt>0)

Przed pętlą można zainicjować zmienną cnt wartością, np. 10000, a wewnątrz pętli można ją zmniejszać o jeden.

Rozszerzenie algorytmu Bresenhama

do rysowania we wszystkich kierunkach (zadanie na ocenę 5)

Celem tego zadania jest poprawienie algorytmu z zadania na ocenę 4, tak żeby rysować linię niezależnie od jej kąta nachylenia i wyboru punktu początkowego i końcowego przez użytkownika.

Jeśli chcesz, możesz spróbować to rozwiązać metodą opisaną na Wikipedii. Proponuję jednak inne rozwiązanie, używając następujących wskazówek:

• dx i dy powinny być wartościami bezwzględnymi
• jeśli x₀ jest mniejsze od x₁, wtedy x powinien być zwiększany o 1, w innym wypadku powinien być zmniejszany o 1 (pamiętaj o modyfikacji warunku pętli w przypadku zmniejszania - powinna być x!=x1 zamiast x<x1)
• to samo dotyczy zwiększania/zmniejszania y w zależności od tego czy y₀ < y₁

Po zastosowaniu tych wskazówek, powinno być widać już o wiele więcej linii, ale część nadal nie działa. Jeśli kąt jest przykładowo między 45 a 90 stopni, otrzymujemy krótszą linię o kącie dokładnie 45 stopni. Problemem tutaj jest, że powinniśmy ewidentnie iterować po współrzędnych y zamiast x w głównej pętli. Łatwym rozwiązaniem tego problemu jest stosowanie algorytmu normalnie, ale zamieniając miejscami współrzędne x i y, zarówno na wejściu (na początku funkcji), jak i na wyjściu (przed wywołaniem set_pixel):

• żeby sprawdzić, czy dochodzi do powyższego problemu, wystarczy porównać dx i dy - jeśli dy jest mniejsze od dx, wtedy wszystko jest ok, w innym przypadku mamy problem i należy wykonać następne punkty
• na początku funkcji (po wyliczeniu dx i dy) należy zamienić miejscami wartości wszystkich zmiennych x i y, czyli: x₀ z y₀, x₁ z y₁ oraz dx z dy
• w przypadku gdy doszło do powyższej zmiany, funkcję set_pixel należy wywoływać ze zmienioną kolejnością współrzędnych x i y, czyli set_pixel(y,x)

Jeśli wprowadzono wszystkie powyższe zmiany, algorytm powinien rysować linie w dowolnym kierunku, niezależnie od wyboru początkowego i końcowego punktu.