Jak mogę szybko generować podpisane pola odległości (2D) w czasie rzeczywistym?

W poprzednim pytaniu zasugerowano, że podpisane pola odległości można wstępnie obliczyć, załadować w czasie wykonywania, a następnie użyć z tego miejsca.

Z powodów, które wyjaśnię na końcu tego pytania (dla osób zainteresowanych), muszę utworzyć pola odległości w czasie rzeczywistym.

Istnieje kilka artykułów na temat różnych metod, które powinny być wykonalne w środowiskach czasu rzeczywistego, takich jak metody transformacji odległości Chamfer i transformacje oparte na przybliżeniu diagramu Voronoi (jak zasugerowano w tej prezentacji przez twórcę Pixeljunk Shooter ), ale Ja (a zatem można założyć, że wielu innych ludzi) bardzo trudno mi je wykorzystać, ponieważ są one zwykle długie, w dużym stopniu nadęte matematyką i niezbyt algorytmiczne w wyjaśnieniach.

Jaki algorytm zaproponowałbyś do tworzenia pól odległości w czasie rzeczywistym (korzystnie na GPU), szczególnie biorąc pod uwagę wynikową jakość pól odległości?

Ponieważ szukam rzeczywistego wyjaśnienia / samouczka, a nie linku do innego artykułu lub slajdu, to pytanie otrzyma nagrodę, gdy będzie się kwalifikować do :-).

Oto dlaczego muszę to robić w czasie rzeczywistym:

Jeśli musisz wstępnie obliczyć te pliki SDF dla dużych środowisk 2D (pomyśl o dużej mapie podobnej do Terraria), oznacza to, że akceptujesz dość duże obciążenie przestrzeni dyskowej (i czas generowania mapy) na rzecz implementacji bardziej skomplikowany algorytm wystarczająco szybki do generowania SDF w czasie rzeczywistym.

Na przykład stosunkowo niewielka mapa o wielkości 1000 * 256 (szerokość * wysokość) o wielkości kafelka 10 * 10 pikseli, a zatem o całkowitych wymiarach 10000 * 2560 pikseli, kosztowałaby już około 2 megabajty rozmiaru, jeśli wybierzesz stosunkowo małą Rozdzielczość SDF 128 x 128, przy założeniu, że przechowujesz tylko wartości odległości od 0 do 255.

Oczywiście może to szybko stać się zbyt duże i jest to narzut, którego nie chcę mieć.

Jest coś jeszcze:

Pliki SDF mogą być używane do wielu rzeczy (takich jak wykrywanie kolizji), a niektóre przydatne aplikacje potencjalnie nawet jeszcze nie zostały odkryte. Myślę, że wiele osób będzie szukać tych rzeczy w przyszłości, a jeśli otrzymamy wyczerpującą odpowiedź tutaj, myślę, że pomożemy wielu ludziom.

Catalin Zima wyjaśnia, jak osiągnąć dynamiczne cienie 2D w swoim artykule - i używa podpisanego pola odległości (z tego, co mogę powiedzieć, to tylko wymyślna nazwa bufora cieni w tym kontekście). Jego metoda wymaga procesora graficznego, a jego implementacja jako nie jest najlepsza (jego spadł poniżej 60 Hz przy około 20 światłach na mojej maszynie, moje uzyskało około 500 świateł); czego należy się spodziewać, ponieważ faworyzował on czystość kodu nad szybkością.

Realizacja

Dokładnie tak, jak go wdraża:

1. Renderuj wszystkie kółka cieni w teksturę.
2. Obliczyć odległość do środka światła dla każdego piksela i przypisać tę wartość do RGB nieprzezroczystych pikseli.
3. Zniekształć obraz, aby reprezentował sposób, w jaki kamera 3D widziałaby te piksele.
4. Squash obraz do rozmiaru 2xN przy użyciu niezwykłej wielkości opisanej w jego artykule (zwykła zmiana rozmiaru nie zadziała).
5. Obraz 2xN jest teraz Twoim podpisanym polem odległości dla wszystkich czterech ćwiartek światła (pamiętaj, że jedna ćwiartka to w zasadzie pojedynczy fragment aparatu pod kątem 90 stopni).
6. Renderuj lightmap.
7. Rozmyj mapę świetlną (na podstawie odległości od światła), aby uzyskać miękkie cienie.

Moja końcowa implementacja to (każdy krok to pojedynczy moduł cieniujący):

1. Zrób (1).
2. Wykonaj (2) i (3) .
3. Zrób (4). Jego implementacja jest naprawdę powolna: jeśli możesz spróbować użyć do tego GPGPU. Nie mogłem używać GPGPU (XNA), więc zrobiłem to:
   • Skonfiguruj siatkę, w której pierwsze N ​​/ 2 kolumny były reprezentowane przez kwadraty N / 2 o DOKŁADNEJ tej samej pozycji (obejmującej pierwszą kolumnę bufora końcowego), ale różniących się współrzędnymi tekstury (to samo dla drugich kolumn N / 2)
   • Wyłącz testowanie głębokości na GPU.
   • Użyj funkcji mieszania pikseli MIN.
4. Czy (6) i (7).

Jest dość genialny: jest to w zasadzie bezpośrednie tłumaczenie sposobu, w jaki cienie są obsługiwane w 3D na 2D.

Pułapki

Główną pułapką jest to, że niektóre obiekty nie powinny być zasłaniane: w moim przykładzie pisałem klon Liero (robaki w czasie rzeczywistym) i dlatego nie chciałem, na przykład, robaków graczy, które powinny być zasłaniane (przynajmniej ten na ekranie każdego gracza). Wszystko, co zrobiłem dla tych „specjalnych” obiektów, to przerysowanie ich jako ostatni krok. Ironią losu było to, że większość obiektów nie była zacieniona (robaki, pierwszy plan krajobrazu), więc jest tutaj problem z przerysowaniem.