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

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.

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 ³ ). 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.

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”.

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,