Kollisionstest SDF / Ellipsoid

[Jonathan]

Wir hatten ja neulich eine ganz ähnliche Diskussion hier, deswegen hat bestimmt jemand cleveren Input zu meinem Problem:

Ich habe eine Szene mit verschiedenen Objekten wie Kugeln, Zylindern, und Meshs repräsentiert als SDF (via Discregrid). Kugel / SDF Test ist super bequem, Zylinder / SDF wir aktuell durch Sampling von Punkten entlang der Zylinderachse inklusive einiger sinnvoller Annahmen (wie detailliert die Strukturen in der SDF sein können, etc.) implementiert und funktioniert robust. Für SDF / SDF sehe ich noch keine bequeme Möglichkeit, der Fall ist aber auch erstmal nicht so wichtig.

Wir wollen aber jetzt Ellipsoide einbauen. Ellipsoid / Zylinder sollte funktionieren wie Kugel / Zylinder mit einem transformierten Zylinder (vielleicht muss man mit dem Radius noch aufpassen), aber worüber ich gerade nachdenke ist SDF / Ellipsoid. Was mir Discregrig gibt ist der Abstand und der Gradient, zum nächsten Punkt auf der Oberfläche. Ich hab mir ein paar Testfälle aufgemalt und es scheint mir nicht so, als ob man da einen ähnlichen Trick wie bei Zylindern anwenden kann. Letztendlich "überdeckt" die kürzeste Verbindung die zweitkürzeste, die aber in Wahrheit näher an der Ellipsoidoberfläche liegen kann, als die kürzeste (wenn man vom Mittelpunkt aus sucht, wie man es bei der Kugel tut). Die SDF kann man auch nicht entlang einer Achse skalieren, weil sie dadurch die Richtung des Gradienten mehr oder weniger beliebig ändern könnte.

Ich überlege jetzt, ob man einfach ein paar Punkte auf der Ellipsoidenoberfläche clever samplen kann und dann mit ein paar wahrscheinlichen Annahmen (SDF hat keine Strukturen kleiner als Radius durch x oder so) dann einen halbwegs robusten Test bekommen kann. Er muss nicht super exakt sein, sollte aber, von den meisten Richtungen aus betrachtet, sinnvoll aussehen und stabil sein (es ist ok, wenn Objekte sich ein wenig intersektieren, aber sie sollten nicht wild hin und herspringen, wenn sie aneinander vorbei gleiten). Alternativ könnte man die "Mesh als SDF" Darstellung wieder vergessen (die wurde im Wesentlichen eingeführt, weil sie recht leicht einzubauen war) und Dreiecke in einem Octree oder so benutzen. Was meint ihr? Wie würde man das am besten einbauen?

[TomasRiker]

Klingt schwierig mit dem SDF. Im Prinzip kannst du ja nur Kugeln perfekt testen. Alle anderen Formen kannst du höchstens über eine Menge von Kugeln annähern.
Mit Octree oder einer ähnlichen Datenstruktur wäre Mesh vs. Ellipsoid letztlich zurückführbar auf Dreieck vs. Kugel, denn ein Ellipsoid ist eine nicht-uniform skalierte Kugel (Octree wird beim Durchsuchen dann invers transformiert).

[joeydee]

Für SDF / SDF sehe ich noch keine bequeme Möglichkeit

Die gibt es auch nicht. Im Prinzip willst du eine Intersection nachweisen/untersuchen. Also max(sdf1,sdf2). Da eine Intersection aber keinen exakten Distanzwert ausgibt, sondern nur >=, geht das nur iterativ annähernd, bzw. per Sampling.

[Jonathan]

Da eine Intersection aber keinen exakten Distanzwert ausgibt, sondern nur >=

Mit dem Kriterium komme ich nicht ganz hinterher. Aber gut, in meinem Fall habe ich eh keine analytische SDF, sondern eine aus einem Mesh generierte (something something Marching Cubes), und die so ziemlich einzige Operation die ich darauf machen kann, ist einen einzelnen Punkt abzufragen. Für jede Abfrage lernt man nur etwas über seine Umgebung aber man kann halt Pech haben und wenig lernen (ein Punkt mit großem Abstand sagt dir, dass da noch viel freier Raum ist, den man ggf. ignorieren kann, ein Punkt mit kleinem Abstand sagt dir nicht, ob etwas winziges in der Nähe ist, oder alles um dich herum blockiert ist). Benutzt man den Abstand könnte man vermutlich irgendein adaptives Sampling machen, welches besser ist als ein Brute-Force Sampling, aber höchstwahrscheinlich will man halt doch einfach keine SDF für diesen Fall verwenden...


Ich habe ein bisschen mehr über die Ellipsen nachgedacht. Das scheint ähnlich aussichtslos, man kann die SDF nicht effizient transformieren um aus der Ellipse wieder eine Kugel zu machen, und die SDF erlaubt halt nur Abfragen mit einer Kugel. Man könnte überlegen die SDF mit einer anderen Abstandsfunktion zu generieren, aber die Ellipse kann sich ja auch drehen und dann müsste die SDF einen anderen Kontaktpunkt liefern können. Ist einfach aussichtslos, schätze ich.

[TomasRiker]

Natürlich könntest du, wie du schon gesagt hast, den Ellipsoiden mit vielen Punkten samplen. Je nach dem, wie schnell die Punkt-Abfrage im SDF ist, wäre das vielleicht OK.
Da kann man auch noch allerhand optimieren: Wenn dein erster gesampelter Punkt z. B. eine genügend große Distanz zurückliefert (größer als die maximale Distanz von diesem Punkt zu irgendeinem anderen Punkt auf dem Ellipsoiden), dann kannst du direkt abbrechen, weil du mit Sicherheit ausschließen kannst, dass irgendein anderer Punkt auf dem Ellipsoiden nah genug ist. Anderenfalls kannst du ggf. einen Teil der zukünftigen Samples überspringen (wenn dein erster Punkt die Distanz 10 hatte, dann brauchst du nur Punkte zu testen, deren Distanz zum ersten Punkt mindestens 10 ist).

Vielleicht magst du uns etwas mehr über den konkreten Einsatzzweck verraten?

[joeydee]

Mit dem Kriterium komme ich nicht ganz hinterher. Aber gut, in meinem Fall habe ich eh keine analytische SDF

Das ist egal, wie die interne Funktion aussieht. SDF heißt ja erstmal nur dass zu einer Position ein Distanzwert zurückgeliefert wird. Intersection (auch Union oder Difference) ist auch nur eine solche SDF-Funktion die zwei solcher Distanzfunktionen schluckt und wiederum einen Distanzwert zurückliefert, und lässt sich genauso weiterverarbeiten/rendern/kombinieren wie alle anderen.
Nur: Viele SDFs liefern einen genauen Distanzwert zurück, es funktioniert die typische Oberflächen-"Projektion": Abfragepos-Gradient*Distanz (p-n*d), und du hast immer einen Punkt exakt auf der Oberfläche.
Intersection liefert aber mit p-n*d u.U. nur einen Punkt außerhalb der Oberfläche, d.h. du musst diesen neu sampeln bis er sich nicht oder nur noch gering ändert.

Nun zurück zum Kollisionsgedanken:
Wenn man relativ einfach nachweisen könnte, dass 2 beliebige SDFs als Intersection eine solide Figur (oder nur leeren Raum) generieren, hätte man direkt eine Antwort Kollision ja/nein. Für eine exakte SDF-Funktion könnte man wahrscheinlich mit wenigen Samples per p-n*d vorhandenes Volumen nachweisen, da die Punkte immer auf der Oberfläche landen. Bei Intersection kommt aber praktisch immer ein Ergebnis raus, das größer als das tatsächliche Volumen ist, also auch >0 wenn gar kein Volumen vorhanden ist. Man muss sich da also "ransampeln", mit max steps und unterem Grenzwert arbeiten, um einigermaßen eine Antwort zu bekommen.

Es wäre prinzipiell übrigens dasselbe wie diese Methode:
Nimm irgendeinen Punkt von SDF A (z.B. den Mitelpunkt), "projiziere" ihn mittels p-n*d auf die Oberfläche von SDF B ("nächster Punkt"), nimm diesen und projiziere ihn auf die Oberfläche von A usw. hin und her bis Toleranz unter- oder Steps überschritten ist. Kannst du leicht mal ausprobieren. Sieht dann etwa so aus, die gelbe Linie im GIF ist die Verbindung der beiden letzten Punkte aus diesem Test: https://zfx.info/viewtopic.php?p=58142#p58142
Bedenke aber, dass es unendlich viele Linien geben müsste wenn z.B. 2 Boxen plan aufeinanderliegen. Also es gibt gar nicht unbedingt "den" geringsten Abstand mit eindeutigen Kontaktpunkten.