Wie kann ich vorzeichenbehaftete Distanzfelder (2D) in Echtzeit schnell generieren?

In einer früheren Frage wurde vorgeschlagen, vorzeichenbehaftete Distanzfelder vorab zu berechnen, zur Laufzeit zu laden und dann von dort aus zu verwenden.

Aus Gründen, die ich am Ende dieser Frage erläutere (für interessierte Personen), muss ich die Distanzfelder in Echtzeit erstellen.

Es gibt einige Veröffentlichungen zu verschiedenen Methoden, die in Echtzeitumgebungen praktikabel sein sollen, z. B. Methoden für Fasenabstandstransformationen und auf Voronoi-Diagrammen basierende Transformationen (wie in dieser Präsentation vom Entwickler von Pixeljunk Shooter vorgeschlagen ) Ich (und somit kann man davon ausgehen, dass viele andere Menschen) haben es sehr schwer, sie tatsächlich zu benutzen, da sie normalerweise lang sind, stark von Mathematik überfüllt und in ihrer Erklärung nicht sehr algorithmisch.

Welchen Algorithmus schlagen Sie vor, um die Distanzfelder in Echtzeit (vorteilhafterweise auf der GPU) zu erstellen, insbesondere unter Berücksichtigung der resultierenden Qualität der Distanzfelder?

Da ich auf der Suche nach einer tatsächlichen Erklärung / Anleitung im Gegensatz zu einem Link zu einer anderen Arbeit oder Folie bin, erhält diese Frage ein Kopfgeld, sobald sie für eine berechtigt ist :-).

Hier ist, warum ich es in Echtzeit tun muss:

Wenn Sie diese SDFs für große 2D-Umgebungen vorberechnen müssen (denken Sie an eine große Terraria-ähnliche Karte), würde dies bedeuten, dass Sie einen relativ hohen Overhead an Speicherplatz (und Zeit für die Kartenerstellung) akzeptieren, um mehr zu implementieren komplizierter Algorithmus, der schnell genug für die Echtzeit-SDF-Generierung ist.

Zum Beispiel würde eine relativ kleine Karte mit 1000 * 256 (Breite * Höhe) mit einer Kachelgröße von 10 * 10 Pixeln und somit Gesamtabmessungen von 10000 * 2560 Pixeln Sie bereits ungefähr 2 Megabyte an Größe kosten, wenn Sie eine relativ kleine auswählen SDF-Auflösung von 128 x 128, vorausgesetzt, Sie speichern nur die Entfernungswerte von 0 bis 255.

Offensichtlich kann dies schnell zu viel werden und ist ein Aufwand, den ich nicht haben möchte.

Es gibt noch etwas anderes:

SDFs können für viele Zwecke verwendet werden (z. B. zur Erkennung von Kollisionen), und einige nützliche Anwendungen werden möglicherweise noch nicht einmal entdeckt. Ich denke, viele Menschen werden in Zukunft nach diesen Dingen suchen, und wenn wir hier eine umfassende Antwort erhalten, werden wir wahrscheinlich vielen Menschen helfen.

Catalin Zima erklärt in seinem Artikel , wie man dynamische 2D-Schatten erzeugt - und er verwendet ein vorzeichenbehaftetes Distanzfeld (soweit ich das beurteilen kann, ist dies in diesem Zusammenhang nur ein ausgefallener Name für einen Schattenpuffer). Seine Methode benötigt eine GPU und seine Implementierung wie sie ist nicht die beste (sein Abfall unter 60 Hz bei ungefähr 20 Lichtern auf meiner Maschine, meine hat ungefähr 500 Lichtern); was zu erwarten ist, da er die Klarheit des Codes der Geschwindigkeit vorgezogen hat.

Implementierung

Genau wie von ihm umgesetzt:

1. Rendern Sie alle Schatten-Casters in eine Textur.
2. Berechnen Sie für jedes Pixel den Abstand zur Lichtmitte und weisen Sie diesen Wert dem RGB-Wert der undurchsichtigen Pixel zu.
3. Verzerren Sie das Bild so, dass es darstellt, wie eine 3D-Kamera diese Pixel gesehen hätte.
4. Verkleinern Sie das Bild mit der in seinem Artikel beschriebenen ungewöhnlichen Größe in ein 2xN-Bild (eine einfache Größenänderung funktioniert nicht).
5. Das 2xN-Bild ist jetzt Ihr vorzeichenbehaftetes Distanzfeld für alle vier Quadranten des Lichts (denken Sie daran, dass ein Quadrant im Grunde ein einzelner Kamerastumpf bei 90 Grad ist).
6. Rendern Sie die Lightmap.
7. Verwischen Sie die Lichtkarte (basierend auf dem Abstand zum Licht), sodass Sie weiche Schatten erhalten.

Meine letzte Implementierung war (jeder Schritt ist ein einzelner Shader):

1. Do (1).
2. Mach (2) und (3) .
3. Do (4). Seine Implementierung ist sehr langsam: Wenn Sie versuchen können, GPGPU dafür zu verwenden. Ich konnte GPGPU (XNA) nicht verwenden, also war das, was ich tat:
   • Richten Sie ein Netz ein, in dem die ersten N / 2 Spalten durch N / 2 Quads mit der EXAKTEN gleichen Position (die die erste Spalte des endgültigen Puffers abdeckt), aber unterschiedlichen Texturkoordinaten dargestellt wurden (dasselbe gilt für die zweiten N / 2 Spalten).
   • Deaktivieren Sie die Tiefenprüfung auf der GPU.
   • Verwenden Sie die Funktion MIN Pixel Blending.
4. Mach (6) und (7).

Es ist ziemlich genial: Es ist im Grunde eine direkte Übersetzung, wie Schatten in 3D in 2D verarbeitet werden.

Fallstricke

Die Hauptfalle ist, dass einige Objekte nicht beschattet werden sollten: In meinem Beispiel habe ich einen Liero-Klon (Echtzeitwürmer) geschrieben und wollte daher nicht, dass zum Beispiel die Würmer der Spieler beschattet werden (zumindest der eine auf dem Bildschirm jedes Spielers). Alles, was ich für diese "speziellen" Objekte getan habe, war, sie als letzten Schritt neu zu zeichnen. Die Ironie war, dass die meisten Objekte nicht beschattet waren (Würmer, Landschaftsvordergrund), so dass es hier ein Überzeichnungsproblem gibt.