Szybkie rysowanie linii antyaliasingowych

11

Algorytm linii Bresenhama to sposób rysowania linii prostych przy użyciu tylko szybkich operacji na liczbach całkowitych (dodawanie, odejmowanie i mnożenie przez 2). Generuje jednak linie aliasu. Czy istnieje równie szybki sposób rysowania linii antyaliasingu?

antialiasing pixel-graphics line-drawing znak
źródło
1
Kilka pytań ... czy wykonujesz logikę rysowania na CPU lub GPU? Czy szukasz algorytmów całkowitych lub zmiennoprzecinkowych?
Alan Wolfe,
5
@AlanWolfe, algorytmy całkowite na CPU - to samo środowisko, dla którego został zaprojektowany algorytm Bresenhama.
Mark
3
en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorytm jest klasyczny, choć strona wikipedia jest w połowie wypalona i nie mam dostępu do gazety. To wydaje się leniwe pytanie, ponieważ dość łatwo jest znaleźć to, wykonując podstawowe wyszukiwanie w Google.
yuriks,
2
Myśląc na głos, wydaje mi się, że przystosowanie Bresenhama do rysowania linii o grubości wielu pikseli powinno być łatwe. Następnie możesz wykonać wygładzanie krawędzi, obliczając odległość każdego centrum pikseli od idealnej linii matematycznej i stosując funkcję odwrotności.
Nathan Reed,
2
Nie mogę jednak oznaczyć komentarza jako poprawnego.
Mark

Odpowiedzi:

9

Czy istnieje równie szybki sposób rysowania linii antyaliasingu?

Nie, ponieważ z definicji wygładzona linia dotyka większej liczby pikseli. Takie algorytmy będą wolniejsze.

W oprogramowaniu do rasteryzacji wszechobecnym sposobem rysowania linii wygładzonych jest algorytm linii Xiaolin Wu . Nie jest trudne do wdrożenia, a poza tym pod tym linkiem znajduje się niezwykle wysokiej jakości pseudokod.

W sprzętowej rurze rastrowej prymityw linii jest rozszerzany do kwadratu przestrzeni ekranowej przez domyślny (lub podany przez użytkownika) moduł cieniujący geometrię, a następnie rysowany jako dwa trójkąty, które można następnie wygładzić w zwykły sposób.

W raytracer istnieje wiele opcji. Warto pomyśleć o tym, jak naprawdę narysować obiekt 1D. Może jako walec (woo shadows!). Zauważ, że wprowadza to kwestie perspektywy / skrócenia, które mogą (lub nie) być tym, czego chcesz. Nie ma wyraźnego uogólnienia. Potem, oczywiście, cokolwiek robisz, po prostu próbkujesz to.

imallett
źródło
„a poza tym pod tym linkiem jest niezwykle wysokiej jakości pseudokod”, nie zgadzam się. Ten pseudo kod prawdopodobnie nie jest prawidłową implementacją algorytmu Wu, chociaż wydaje się, że był używany w niezliczonych miejscach w sieci. Oryginalny algorytm Wu wyciągnął z obu końców do środka w kierunku centrum i był w rzeczywistości szybszy niż Bresenham, ponieważ wykonuje około połowę więcej operacji, nawet jeśli zapisuje więcej pikseli. Mówię o faktycznym algorytmie Wu, a nie tym opublikowanym w powiązanym artykule na Wikipedii.
Octopus
@Octopus [Wyraża niejasny sceptycyzm, szczególnie w przypadku szybszego bitu, ale brakuje mu kontekstu do obalenia lub potwierdzenia - jeśli tak, źródła, poprawki i zmiany są oczywiście mile widziane.]
imallett
Zależy od tego, co liczysz. Jeśli rysujesz z obu końców do wewnątrz, algorytm Wu wykonuje połowę obliczeń, ale zapisuje dwa razy więcej pikseli. Patrz Tabela 1 w artykule Wu, link na Wikipedii. Więc jeśli zapisywanie pikseli jest kosztowne, tak jak w przypadku zapisu do TFT na połączeniu szeregowym, algorytm Wu jest droższy niż Bresenham. (Muszę przyznać, że nie rozumiem, dlaczego algorytm Bresenhama również nie może używać symetrii.)
Jan-Åke Larsson,
1
Ale zgadzam się z @Octopus, nawet akceptując „rysowanie od jednego końca do drugiego”, pseudokod jest algorytmem Wu tylko wtedy, gdy przez cały czas używana jest arytmetyka liczb całkowitych. Kod, który widzę online, używa arytmetyki zmiennoprzecinkowej, co jest znaczącą zmianą. W artykule Wu algorytm wykorzystuje tylko arytmetykę całkowitoliczbową (lub w rzeczywistości arytmetykę o stałym punkcie).
Jan-Åke Larsson,