Grafika komputerowa - Podstawowe algorytmy rastrowe

1. Najczęściej rysowanym prymitywem geometrycznym jest odcinek.

2. Algorytm zmiennoprzecinkowy:
  • Punkty początkowy P1(x1,y1) i końcowy P2(x2,y2) przybliżamy dwoma najbliższymi pikselami
  • Dla równania linii y=ax+b wyznaczamy kolejne wartości xi dla kolejnych pikseli i dla nich wyliczamy wartości yi= | _a xi + b + 0,5_ |
Niestety dla linii o nachyleniu większym od 45 stopni algorytm wyznaczający jeden piksel dla każdej kolumny powoduje generowanie nieciągłych odcinków. 

3. Algorytm Bresenhama:
  • Obliczenia tylko na liczbach całkowitych dla a należącego do przedziału [0;1] dla a>1 i a<0 symetria
  • Idea tego algorytmu polega na optymalnym wyborze następnego piksela z dwóch możliwych do wyboru tak aby zminimalizować błąd popełniany przy obliczaniu odległości punktów rastra od rzeczywistej linii.

4. Wyplenienie obszarów:

Algorytm powinien działać dla obszarów wklęsłych i posiadających dziury 
  • wypełnienie przez kontrolę parzystości 
Obszar do wypełnienia przeglądany jest wzdłuż poziomych linii. Nieparzyste przecięcia obszaru brzegu obszaru oznaczają rozpoczęcie wypełniania kolejnych pikseli zadanym kolorem, parzyste - koniec wypełniania. Przecięcie brzegu nie występuje, gdy zarówno pierwszy jak i ostatni piksel w ciągu pikseli o kolorze krawędzi mają w swoim sąsiedztwie piksel krawędziowy w rzędzie tylko niższym lub tylko wyższym.
  • wypełnianie przez spójność
Wypełnianie przez spójność zakłada znajomość punktu startowego wewnątrz obszaru. Punkt ten jest wypełniany, a następnie startując z niego wypełniamy punkty sąsiednie (jeśli oczywiście istnieją – jeśli nie są już wypełnione, ani nie są punktami granicznymi obszaru). Jednocześnie punkty sąsiednie stają się wyjściowymi dla wypełniania w następnym kroku. Procedura ta jest powtarzana dopóki można wskazać punkty wyjściowe (niewypełnione) wewnątrz obszaru.

4. Antyaliasing polega na rozmywaniu krawędzi, które obserwowane z pewnej odległości sprawiają wrażenie "płynnego" przejścia bez widocznych schodków pomiędzy kolorem obiektu i kolorem tła.

5. Prefiltering polega na obliczaniu jasności piksela na podstawie określenia jak duża powierzchnia piksela zajęta jest przez obiekt. 

6. Supersampling polega na zwiększeniu gęstości rastra powyżej rozmiaru bitmapy (rozdzielczości ekranu), a następnie uśrednieniu informacji z tego rastra dla rzeczywistych pikseli. Jakość piksela jest proporcjonalna do ilości "części"piksela, które są przysłonięte co najmniej w połowie.