Ogólny algorytm rasteryzacji jest taki, dla każdego wielokąta na obrazie.
(Wielobok definiuje się jako jedną lub więcej zamkniętych krzywych utworzonych z odcinków prostych i splajnów parametrycznych - w normalnej praktyce są to splajny drugiego rzędu (alias stożkowy kwadratowy) i splajny Béziera trzeciego rzędu (sześcienne). są zdefiniowane w taki sposób, że wnętrze jest zawsze po lewej stronie, ponieważ krzywa jest przesuwana, więc zwykłe kształty działają w kierunku przeciwnym do ruchu wskazówek zegara, a otwory biegną w prawo.)
(i) (rzutowanie) Konwertuj wielokąt na taki sam układ współrzędnych, jak docelowa bitmapa. Rozdzielczość nie musi być taka sama, a dla obrazów wygładzanych często jest większa: na przykład FreeType używa 64. piksli.
(ii) (Wykonaj monotoniczne w Y) Jeśli to konieczne, podziel każdy segment wielokąta na mniejsze segmenty, które działają stale w górę lub w dół. Ten etap jest potrzebny tylko dla zakrzywionych segmentów i jest stosunkowo łatwy przy użyciu splajnów Béziera. Zwykle metoda polega na wielokrotnym przepołowywaniu, aż do osiągnięcia monotoniczności. Odrzuć wszystkie poziome segmenty.
(iii) (zaznacz ograniczenia przebiegu) Narysuj każdy segment w tymczasową bitmapę. Użyj algorytmu Bresenhama dla linii prostych; dla krzywych, na pół, aż linia nie będzie dalej niż (powiedzmy) 1/8 piksela od krzywej rzeczywistej, a następnie użyj linii prostej od początku do końca. Podczas rysowania zaznaczaj piksele w pewien sposób, aby wskazać (a), czy są to początki, czy zakończenia biegów - zaczynają się linie w dół, a linie w górę są końcami; (b) pokrycie - ułamek piksela znajdujący się wewnątrz kształtu. W tym miejscu algorytmy różnią się szczegółami i rozróżnia się zasady likwidacji (non-zero versus even-odd).
(iv) (skanowanie) Przechodzenie między tymczasową bitmapą, wiersz po wierszu. Dla każdego wiersza skanuj od lewej do prawej. Utrzymanie stanu wskazującego, czy bieżące położenie znajduje się wewnątrz kształtu, czy nie przez (na przykład) dodanie numeru zapisanego w mapie bitowej do zapisanego numeru. W prostej rasteryzacji monochromatycznej liczba ta, zapisana w poprzednim etapie, będzie +1 przy przekraczaniu krawędzi do kształtu i -1 przy wychodzeniu z kształtu. Akumuluj przebiegi pikseli w tym samym stanie. Wyślij przebiegi do modułu rysunku: na przykład FreeType emituje przebiegi składające się z współrzędnej Y, współrzędnych początkowych i końcowych X oraz zasięgu od 0 do 255. Moduł rysunkowy może wykorzystywać pokrycie jako wartość alfa zastosowaną do bieżącego koloru rysunku lub jako maska zastosowana do tekstury.
Powyższe stanowi wielkie uproszczenie, ale daje ogólny pogląd.
Większość programów open-source użyć kodu rasteryzację pochodzący z jednego z następujących projektów:
FreeType - a rasteryzer czcionki, która zawiera zarówno mono i anty-aliasingu moduły Rasterizer które są stosunkowo łatwe w użyciu stand-alone - że jest, dla każdego kształtu, nie tylko dla czcionek. Z powodzeniem korzystałem z tego systemu w kilku komercyjnych przenośnych projektach C++.
System FreeType został zainspirowany przez Rapha Levien'a: Libart.
Anti-Grain to kolejna popularna i wpływowa biblioteka C++.
Istnieje również scan-line edge flag system wdrożony przez Kiia Kallio, który wygląda obiecująco i wydaje się być szybszy niż Anti-Grain.
Większość, ale nie wszystkie z tych bibliotek akceptują kształty wykonane z kwadratowych i sześciennych splajnów Béziera oraz segmentów prostych. Te, które tego nie robią (np. Biblioteka K. Kallio) przyjmują tylko wielokąty o prostych krawędziach; ale całkiem łatwo jest "spłaszczyć" krzywą w szeregu segmentów linii bliżej niż pożądana maksymalna odległość od rzeczywistej krzywej. FreeType robi to wewnętrznie, a jego kod można wypożyczyć w razie potrzeby.
Jakie środowisko grafiki wektorowej obecnie używasz? Wszelkie znane mi ramy mają gotowe rozwiązanie do rysowania grafiki wektorowej na ekranie lub rastrowej bitmapy, rozwiązując problem rasteryzacji. –
Zgadzam się z @DocBrown. Nie wynajduj ponownie koła, chyba że wypróbowałeś wszystkie możliwe opcje, a nawet wtedy używaj tak dużo pracy, jaką wykonały już niezliczone inne czynności, tak, abyś ponownie kroczył jak najmniejszą ilością ziemi. – cdeszaq
co jest cechą pytania, nie muszę rasteryzować żadnego konkretnego wektora i nie używam konkretnych ram. Jest to pytanie teoretyczne, i jestem ciekawy, jakie algorytmy używają te ramy i jak mogę poprawić te algorytmy przy współbieżności :) – medvedNick