Pokrycie - wada algorytmu - jak pozbyć się jego wykorzystania?

10

Wprowadzenie

Wiele głównych silników renderujących grafikę wektorową ma wadę algorytmiczną. Renderują każdy kształt osobno i antyializę, obliczając pokrycie pikseli, a następnie układają je jeden na drugim. Tak, to proste, ale prawidłowe rozwiązania są jeszcze prostsze.

Prowadzi to do problemów związanych z pomieszaniem, ponieważ ogranicza zakres pokrycia przez przejrzystość. Mieszanie alfa odbywa się zgodnie z zasadą, która nie odzwierciedla dokładnie sytuacji, na przykład weź piksel pokryty w 50%, który sąsiaduje z pikselem, który jest również objęty komplementarnością w 50%, nie kończy się w 100% pokryciu, kończy w pokryciu 75% . To, jak to wygląda, zależy od tego, jak algorytm jest dostrojony i innych szczegółów, ale w istocie jest to znany błąd. Ktoś nawet przeszedł przez kłopoty z udokumentowaniem różnych błędów silnika wraz z napisaniem artykułu pokazującego, jak można to zrobić lepiej.

wprowadź opis zdjęcia tutaj

Zdjęcie 1 : Całkowicie niereprezentatywna próbka renderowania kształtu złożonego z trójkątów z powiększonym błędem w górnym rzędzie. Źródło SVG

Problem ma proste naiwne rozwiązanie * po prostu superpróbka bez obliczania zasięgu i filtrowania obrazu w dół. Jako bonus możesz użyć lepszych algorytmów rekonstrukcji obrazu niż filtrowanie ramek (czytaj : Piksel to nie jest kwadrat 3 ). Istnieją nawet rozwiązania, które mają porównywalną szybkość jak obecne rozwiązania, a rozwiązania te są znacznie łatwiejsze w sprzętowych potokach rasteryzacji (i rzadko widuje się ten błąd na GPU, ponieważ został zbudowany, aby uniknąć tego problemu).

Nie stanowi to również problemu bez kosztów. Istnieje wiele osób zajmujących się projektowaniem graficznym, które spędzają niebagatelną ilość czasu próbując obejść ten problem ręcznie, upewniając się, że nakładają się one na siebie i że nie nakładają się, aby rozwiązać problem, który komputer powinien dla nich zrobić. I w wielu przypadkach spektakularnie zawodzi. Ale ich klienci nie dbają o to, dlaczego wystąpił błąd, muszą go naprawić.

Pytanie

Jak propaguje się błąd? Ponieważ wszyscy popełniają ten sam błąd, można stwierdzić, że używają tego samego źródła dla swojego algorytmu. Co mogło spowodować, że projektanci wybrali ten algorytm? Dlaczego tylko programiści 3D rozpoznali ten błąd, a nawet skodyfikowali jego część w swoich API i nauczaniu, podczas gdy programiści 2D nie?

Jak zapewnić, że ten błąd przestanie się dalej propagować?


Dodatek (ale nie pytam o to)

* Najwyraźniej moje twierdzenie, że superpróbkowanie działa bezbłędnie, jest nadzwyczajne i wymaga niezwykłego dowodu. Ok, więc kluczem do działania super-próbkowania jest to, że super-próbkowanie nie wykonuje przetwarzania pokrycia. Zasadniczo superpróber traktuje każdą próbkę jako próbkę punktową. Ponieważ próbka punktowa nie przyjmuje założenia o leżącym pod nią obszarze, nie powoduje porównania alfa tam, gdzie to się nie dzieje.

Aby działał konsekwentnie, jak opisano w jednej z odpowiedzi. Musimy zrobić, aby przetwarzać próbki z całkowitym próbkowaniem dla spójności. To zapewnia nas, że każdy punkt po przekształceniu w przestrzeń ekranu otrzymuje dokładnie to samo rozwiązanie dla równych współrzędnych i że żadna próbka nie jest zacieniona 2-krotnie ramką piksela. Aby to zrobić, próbka nie może wyzwolić piksela ot jest dokładnie włączona, jeśli jest to na przykład próbka z lewej strony u dołu (dlatego ustalamy, że dokładne krawędzie są przetwarzane w> vs <=). Wszystkie karty graficzne z wyjątkiem jednej konsoli działają w ten sposób. Zapewnia to, że nie trzeba buforować żadnych dodatkowych danych ani dodatkowych testów w pobliżu. To rozwiązanie jest równie stabilne, bardziej ogólne i spójne niż rozwiązania oparte na zasięgu.

Algorytm jest dokładnie taki sam jak oryginał z nieco mniejszym kodem i nieco większą liczbą próbek. Jest zatem tak samo spójny, jeśli nie bardziej niż algorytm oparty na zasięgu. Wiemy o tym, ponieważ od wieków stosujemy takie metody w prawie każdym innym polu przetwarzania sygnału, a także w kartach graficznych.

Więc czy ta metoda ma wadę? Cóż, jest to odrobinę wolniejsze, jeśli po prostu przyjmujesz naiwne założenie. Ma teoretycznie szybsze zachowanie asymptotyczne niż rasteryzator pokrycia, trochę jak raytracer, wciąż jest na równi w typowych scenach. Może to również sprawić, że stosowanie efektów splotowych będzie bardziej bolesne we wdrożeniu.

joojaa
źródło
Dodam zdjęcia do mojego amnendum po zakończeniu mojego dnia pracy. Przecież to przetwarzanie grafiki ma interpretację wizualną
joojaa

Odpowiedzi:

6

Supersampling, gdy jest wykonywany naiwnie, jest kosztownie obliczeniowy, ponieważ jeśli użyjesz na przykład połowy wielkości piksela wyświetlacza, potrzebujesz czterokrotnie więcej pamięci i szerokości pasma. Wikipedia wspomina o tym, a także wymienia adaptacyjne supersampling jako możliwe rozwiązanie. Ale to sprawia, że ​​algorytm jest znacznie bardziej wyrafinowany, złożony i trudniejszy do wdrożenia.

Myślę, że właśnie dlatego szukasz: jeśli chcesz algorytmu, który nie wymaga dużo więcej pamięci i czasu działania, sprawy stają się znacznie bardziej skomplikowane niż w naiwnym podejściu „przejrzystości”.

Doktor Brown
źródło
W rzeczywistości nie trzeba przechowywać próbek, wystarczy jedynie zapisać konfigurację rasteryzacji. Metoda oparta na pokryciu również ich nie przechowuje, więc nie jest to krok wstecz. Naiwna metoda jest prezentowana tylko dlatego, że jest łatwa do zrozumienia, możesz łatwo wykonać próbkowanie oparte na priorytetach. Ponadto, jeśli chcesz przenieść rozwiązania oparte na zasięgu na GPU, będziesz musiał wykonać dużo dodatkowej pracy i będziesz niezgodny z jego modelem.
joojaa
@joojaa: czy możesz nakreślić, co rozumiesz przez „przechowywanie ustawień rasteryzacji”, czy podać link, w którym to podejście jest wyjaśnione w taki sposób, że nie trzeba przekopać się przez> 20-stronicowy artykuł naukowy?
Doc Brown,
Każdy piksel jest od siebie niezależny, więc wystarczy zapisywać próbki podczas wykonywania piksela, po czym można je bezpiecznie odrzucić. Jeśli chcesz użyć instalatora wyższego rzędu, możesz zapisać tylko ograniczony widok. Więc wszystko, co naprawdę musisz zrobić, to przydzielić pamięć dla rdzenia procesora, więc może (16-256 bajtów na wątek)
joojaa 28.09.16
och, przepraszam, że nie musicie nawet przechowywać próbek, jeśli wykonacie filtrowanie skrzynek, możecie po prostu użyć wzoru na średnią ruchomą / bieżącą, który nie wymaga przechowywania indywidualnych próbek
joojaa 28.09.16
@joojaa: Nie rozumiem - czy nie musisz najpierw obliczać próbek dla wszystkich powiązanych kształtów , może setek lub tysięcy, a potem filtrować do ekranu rastrowego?
Doc Brown,
6

Supersampling nie rozwiąże problemu w ogóle: sprawi, że będzie mniej zauważalny. Przy pikselach o połowę mniejszym problem będzie w połowie tak zauważalny, ale nie zniknie.

Architektonicznym punktem tych projektów jest to, że chcemy, aby polecenie „renderowanie trójkąta ABC” miało określone znaczenie. Nie chcemy, aby była niejednoznaczna, chyba że jest uważana za część zbioru poleceń rysunkowych - na przykład ma jedno znaczenie, gdy „renderowanie trójkąta BCD” znajduje się również w kolekcji (o tym samym lub innym kolorze), a inne znaczenie, gdy to nie jest.

Biorąc pod uwagę na przykład tysiąc trójkątów, nawet znalezienie wszystkich trójkątów, które dzielą bok lub część boku z ABC, jest ciężkie obliczeniowo (pamiętając, że trzeba to powtórzyć tysiąc razy). Istnieje również wiele innych praktycznych problemów: zwłaszcza, że ​​wszystkie oryginalne żądania renderowania muszą zostać zachowane, nawet jeśli zostały narysowane dawno temu, na wypadek, gdyby trzeba je było ponownie ocenić z powodu nowego, dodatkowego żądania.

Najważniejsze jest to, że idealnie spójne rozwiązanie nie jest możliwe. Pozostaje pytanie: czy powinniśmy spróbować poprawić obecną sytuację, kiedy możemy? Ogólnie rzecz biorąc, odpowiedź na to pytanie brzmi: Nie. Idealnie konsekwentna realizacja modelu jest zawsze lepsze, nawet jeśli sam model ma ograniczenia zostały przedstawione. Alternatywą byłaby implementacja, która czasem robi się lepiej, a czasem nie, bez możliwości, aby programiści wiedzieli, które z nich utrzymają się w danym przypadku. Co więcej, może przejść od „robi lepiej” do „nie robi lepiej” w wyniku drobnych zmian dokonanych przez programistę - lub nawet w wyniku tych, na które programista nie ma wpływu. Przewidywalność w kontekście programowania jest daleka,

Martin Kochański
źródło
Jest to problem z obliczaniem zasięgu, jeśli moje supersampling NIE wykonuje obliczenia zasięgu, to nie ma problemów, ponieważ zbiega się z odpowiedzią rea, nie tylko zmniejszając problem. Czy potrzebujesz kodu, aby to udowodnić? Tak działa twoja karta graficzna i nie występuje ten problem. W przeciwnym razie każda gra, którą zobaczysz, wykazywałaby problem. Nie kupuję tej odpowiedzi, ponieważ jest ona oparta na fałszywej logice.
joojaa
Gry @joojaa albo nie wykonują żadnego wygładzania, albo używają super-próbkowania do wygładzania, co daje zazwyczaj cztery poziomy wygładzania. Nie jest to wystarczające do grafiki o jakości prezentacji, w której wymagane jest około 64 poziomów wygładzania krawędzi. Więc gry zamieniają jeden problem na inny.
Pete Kirkham,
@PeteKirkham zależy od twojego ustawienia, niektóre gry pozwalają ci określić ilości próbek. W każdym razie nie potrzebujesz więcej niż 16 próbek do uzyskania poziomu prezentacji AA, jeśli używasz filtru wyższego rzędu niż filtrowanie pudełkowe. Zwróć uwagę, że obraz braku błędu w moim przykładzie jest wykonywany przez supersampling wewnątrz reasterizera sprzętowego.
joojaa