Geht SDF Intersection auch "exact"?

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
Antworten
joeydee
Establishment
Beiträge: 1039
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Geht SDF Intersection auch "exact"?

Beitrag von joeydee »

Basierend auf dem Post von xq (schon eine Weile her, Showroom, s.u.) und den Seiten von Quilez https://www.iquilezles.org/www/articles ... ions2d.htm habe ich auch ein wenig mit SDF-Kreiskollision gespielt.

Mit SDF ist ja auch CSG leicht machbar. Nun schreibt Quilez über die Intersection-Funktion (max(d1,d2)), sie sei nur "bound", nicht "exact", d.h. die neue Null-Isoline (Oberfläche) stimmt zwar, aber alle anderen Abstände nicht, der Gradient weiter außerhalb folglich auch nicht, d.h. er zeigt nicht unbedingt auf die Oberfläche.
Also darf man gar keine Intersections in seinem SDF nutzen, wenn man von "irgendwo" aus direkt den nächsten Hitpunkt ermitteln will (Methode siehe xq's Erklärung und Video im Spoiler unten), oder sieht jemand eine Möglichkeit?

xq hat geschrieben: 01.10.2019, 10:12
Jonathan hat geschrieben: 01.10.2019, 10:02 Sieht nett aus. Ich nehme an, du hast einen kreisförmigen Avatar und testest auf Kollision in dem du seinen Radius mit dem Ergebnis der Abstandsfunktion vergleichst?
Korrekt. Für die meisten Top-Down-Spiele reicht das ja völlig aus an Kollisionscode (alles Player Characters sind ein Kreis, wenn man nur fest genug daran glaubt).
Jonathan hat geschrieben: 01.10.2019, 10:02 Was mich dann noch interessieren würde: Wie bekommst du die Oberflächennormale bzw. den Kontaktpunkt? Im Video ist der ja mit eingezeichnet, aber mir ist nicht direkt klar, wie man den aus der SDF bekommt.
Tja, der Trick hier nennt sich "Gradient" und ist dieses feine Stückchen Code hier:

Code: Alles auswählen

glm::vec2 gradient;
{
	float x0 = get_distance_to_point(player_pos + glm::vec2(1, 0));
	float x1 = get_distance_to_point(player_pos - glm::vec2(1, 0));
	float y0 = get_distance_to_point(player_pos + glm::vec2(0, 1));
	float y1 = get_distance_to_point(player_pos - glm::vec2(0, 1));

	gradient.x = x1 - x0;
	gradient.y = y1 - y0;

	gradient = normalize(gradient);
}
Man bestimmt einfach die Richtung der größten Änderung, damit hat man dann quasi direkt die Oberflächennormale von der Oberfläche, die einem am nähsten ist. Das tolle an diesem Trick ist, dass man sich nicht mal darum kümmern muss, was passiert, wenn man mit zwei Oberflächen gleichzeitig kollidiert. Denn dann ist der Gradient der Mittelwert beider Normalen und das ganze verhält sich automatisch korrekt. Sieht man auch hier ganz schön:

Benutzeravatar
xq
Establishment
Beiträge: 1581
Registriert: 07.10.2012, 14:56
Alter Benutzername: MasterQ32
Echter Name: Felix Queißner
Wohnort: Stuttgart & Region
Kontaktdaten:

Re: Geht SDF Intersection auch "exact"?

Beitrag von xq »

joeydee hat geschrieben:Also darf man gar keine Intersections in seinem SDF nutzen, wenn man von "irgendwo" aus direkt den nächsten Hitpunkt ermitteln will (Methode siehe xq's Erklärung und Video im Spoiler unten), oder sieht jemand eine Möglichkeit?
Guck dir doch einfach mal die Isolinien an, die aus der Funktion resultieren:



(Klicken und ziehen um die beiden Kreise zueinander zu verschieben)
Also darf man gar keine Intersections in seinem SDF nutzen, wenn man von "irgendwo" aus direkt den nächsten Hitpunkt ermitteln will
Das geht soweit auch gar nicht. Du kannst nur einen Kugelumfang berechnen, aber keinen "wie weit geht mein Strahl". Das muss immer iterativ gelöst werden, für entweder X Schritte oder aber bis du nah genug ran kommst.
War mal MasterQ32, findet den Namen aber mittlerweile ziemlich albern…

Programmiert viel in ⚡️Zig⚡️ und nervt Leute damit.
joeydee
Establishment
Beiträge: 1039
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Geht SDF Intersection auch "exact"?

Beitrag von joeydee »

Ist jetzt Subtraction im Shaderbeispiel, aber hat prinzipiell dasselbe Problem.
Das geht soweit auch gar nicht. Du kannst nur einen Kugelumfang berechnen, aber keinen "wie weit geht mein Strahl".
Weiß nicht ob ich deine Aussage richtig verstehe - aber das gilt ja generell für SDF. Das ist schon klar. Ich habe keinen Strahl, ich mache genau dasselbe wie du in deiner Kollisions-Demo, den größten Kugelumfang bestimmen, sprich eine einfache Abstandsbestimmung in allen Richtungen. Hattest du deine Kollision mal mit Intersection- oder Subtraction-Operationen getestet? Falls es bei dir geht, mache ich was falsch.
Falls nicht muss man wohl leider sagen, die Intersection-Operation produziert kein SDF mehr, sondern nur noch ein SF (keine gültige Distanzinformation mehr, nur noch das Sign stimmt).

Iterativer Gradientenabstieg als nächstliegende Lösung (also dem Gradienten in angepassten Steps folgen bis ein bestimmter Grenzwert erreicht wird) macht bei mir öfters mal Probleme mit sich totlaufenden Pfaden. Bei der Shaderdemo Z.B. eine schmale Sichel: Da entsteht ein V-förmiges Tal, d.h. der Abstieg pendelt im Zickzack die Hänge hin und her, und erreicht die Oberfläche u.U. nur nach sehr vielen Iterationen. Damit gehen Vorteil und Stabilität eines echten SDF halt wieder flöten.

Ok, schade. Ich hatte ursprünglich gehofft es gibt vielleicht eine Intersection-OP, die ein echtes SDF produziert. Oder einen praktischeren/schnelleren Weg, das "falsche" SDF trotzdem für die einfache Abstandsbestimmung nutzen zu können.
Antworten