Intersection zweier ebenenbasierter Brushes (Q3 Style)

[Top-OR]

Sorry für die Verspätung .. ich habe gerade viel um die Ohren.
Und .. Uii, hier hat sich ja einiges getan. Das muss ich erstmal verdauen.

Wie bekommst du den roten Punkt und die Normale, die ja keiner der Ebenennormalen entspricht?

Also .. ich hatte einiges gemalt, um das zu veranschaulichen, finde aber keinen Hoster, an den ich aus allen Netzwerken, in denen ich mich so rumtreibe, immer rankomme. Daher in Worten:

Den Roten Punkt finde ich NICHT EXAKT, sondern nur angenähert:

Ich projiziereden mutmaßlichen Ellipsioden-Surface-Punkt (Kollisionspunkt auf dem Ellipsoiden) auf eine Brushplane.
Dann mache ich einige Male iterativ eine weitere senkrechte Projektionen dieses Punktes auf eine Brush-Ebenene, fallser sich, relativ zu dieser, noch "außerhalb" des Brushes befindet (signed distance > 0).
Wie gesagt: Das ganze einige Male iterativ ... da reichen schon 4 bis 12 Mal - je nach Brush-Komplexität.
Man erhält einen Punkt, der NICHT 100% genau auf der Brush-Oberfläche liegt, sondern u.U. etwas darüber .. aber nicht zu weit weg vom Schuss.
Das reicht für den Stützvektor/Stützpunkt der Sliding Plane. -> Der Rote Punkt.

Als Normale nehme ich die Strecke zwischen diesem Punkt und dem Ellipsoid Center bzw. den Normalvektor einer Tangentialebene eines nahem Punktes auf der Ellipsodenoberfläche. Da kann man mit experimentieren.

Für meine Use-Cases reicht das. Aber du hast recht: 100% Genau finde ich die Surface-Points ohne Vertices nicht...

[dot]

Also .. ich hatte einiges gemalt, um das zu veranschaulichen, finde aber keinen Hoster, an den ich aus allen Netzwerken, in denen ich mich so rumtreibe, immer rankomme. Daher in Worten: [...]

Wieso nicht einfach hier um Forum als Attachment hochladen? ;)

[Top-OR]

Also .. ich hatte einiges gemalt, um das zu veranschaulichen, finde aber keinen Hoster, an den ich aus allen Netzwerken, in denen ich mich so rumtreibe, immer rankomme. Daher in Worten: [...]

Wieso nicht einfach hier um Forum als Attachment hochladen? ;)

Uiii .... hatte nur geschaut, wo de gute Joeydee sein Bild verstaut hat und war dann der Meinung, man könne es nur verlinken und muss es woanders lagern. Aber ja, als Attachment. Ich reiche es nach. ;-)

[Top-OR]

Ich bezweifle aber mal, dass so etwas in der Praxis effizienter sein wird als deine Körper erstmal in Vertices/Polygone zu konvertieren und dann diese auf herkömmlichem Weg zu behandeln, insbesondere wenn man bedenkt, dass du zum Rendern am Ende sowieso Polygone brauchen wirst...

Ja, ich glaube auch, wobei ich aber in meinem "Physik"-Thread wirklich nur das vorhalte, was ich zur Berechnung der Objektdynamik brauche und nichts zum Rendern.
Im Grunde mach ich die Inersektion-Tests mit dem Separating Axis Theorem (wofür ich alle Vertices auf verschiedne Achsen projiziere und eine "Nicht-Intersection" suche.
Dazu brauche ich auch keine Faces, ne Punktmenge reicht. Das funktioniert ganz gut.

Ich bin mir fast sicher, dass es da effizientere Algorithmen gibt als Brute-Force alle Kombinationen durchzugehen (wobei ich das damals vor 15 Jahren oder wann auch immer das war auch einfach so gemacht hab...du versuchst nicht zufällig gerade das .map Format, das der Valve Hammer Editor ausspuckt, zu parsen? :mrgreen: ).

Na fast: Quake 3 BSP Objekte. Das Hammer-Map-Format stammt ja vom Ur-Quake ab. Es sind quasi Verwandte.Ich lese aber das bereits kompilierte BSP-File und überführe es in ein eignenes Format.
Die resultierenden Objekte sind bei mir nicht mehr (wie bei quake und HL) ganze Level, sondern ich platziere sie als "normale" Objekte in einem Szene-Baum (bzw. parallel in einem kleinen Physikbaum).

[youtube]iuivXQjNFnU[/youtube]

Ich würde mal vermuten dass man da basierend auf Dualtransformationen was machen kann, Stichwort Dual Plane, Upper/Lower Envelope. Schnelles Google wirft z.B. das hier auf: https://algo.kaust.edu.sa/Documents/cs372l13.pdf und http://www.cs.wustl.edu/~pless/506/l8.html

Isch gucke ... Danke Dir!

[Krishty]

Doppelte Bro-fist: einmal für die Engine und einmal für’s klassische ZFX-Thema!

[Top-OR]

Doppelte Bro-fist: einmal für die Engine und einmal für’s klassische ZFX-Thema!

Yay. In 20 Jahren ist sie (die Engine) bestimmt "fertig". Thx auch an alle, die hier Ihren Senf lassen.

Manchmal hirne ich über ein Problem und habe den Eindruck, dass ich die einfache Lösung nur übersehe und "ALLE" (tm) eine klare Vorstellung über die Lösung haben würden.
Es beruhigt mich einerseits, dass es nicht immer sooo trivial zu sein scheint. Andererseits hätte ich mich auch in diesem Fall über die triviale (-> performante & elegante [?!]) Lösung gefreut ... ;-)

Man lernt ... wenn auch nicht das, was man wollte und nicht auf dem schnellen Weg.

In diesem Sinne ... heute zu seinem Todestag:

Remember to look up at the stars and not down at your feet. Try to make sense of what you see and wonder about what makes the universe exist. Be curious. And however difficult life may seem, there is always something you can do and succeed at. It matters that you don't just give up.

Also: Weiter rechnen, weiter painten, weiter modellieren, weiter coden, weiter machen!

[Schrompf]

Exakt! Mach weiter! Deine Engine sieht sehr cool aus! Du könntest aber vielleicht mal den Unity Asset Store oder so nach kostenlosen 3D-Modellen durchsuchen, um Dein Content-Mangel-Problem zu beheben (und einen ganzen Schwung LOD- und Optimierungsprobleme neu zu bekommen).

[joeydee]

Ich projiziereden mutmaßlichen Ellipsioden-Surface-Punkt (Kollisionspunkt auf dem Ellipsoiden) auf eine Brushplane.
Dann mache ich einige Male iterativ eine weitere senkrechte Projektionen dieses Punktes auf eine Brush-Ebenene, fallser sich, relativ zu dieser, noch "außerhalb" des Brushes befindet (signed distance > 0).
Wie gesagt: Das ganze einige Male iterativ ... da reichen schon 4 bis 12 Mal - je nach Brush-Komplexität.

Ich glaube ich verstehe wie du das machst.
Prinzipiell müsste man ähnlich iterativ den geringsten Abstand (respektive ob eine Überschneidung stattfindet) zwischen zwei Brushes annähern können. Prinzip: beliebigen Surface-Punkt von Brush 1 auf die Oberfläche von Brush 2 "projizieren" (sprich kürzeste Distanz finden), diesen Punkt wieder auf Brush 1 projizieren usw. mehrfach hin- und herwerfen.
Mit Boxen geht das jedenfalls, und die PingPong-Strecke nähert sich der kürzesten Entfernung zwischen den Oberflächen (was automatisch die Sliding-Normale ergibt). Bilder dazu hatte ich kürzlich im Vorstellungsthread. Für Boxen gibts allerdings eine einfache explizite Abstandsfunktion (min/max der Halbachsen vergleichen, ohne Vertex- oder Polygon-Set). Ob man diese Surface-Iteration mit deinem Ansatz irgendwie direkt kombinieren kann oder ob das iterativ verschachtelt werden müsste und damit alles ausbremst was es an Eleganz-Vorteil bringen würde, kann ich jetzt leider nicht vorhersagen (und bin dank Grippewelle auch nicht weiter zum Experimentieren gekommen, konnte leider nichtmal den Namen für das Iterationsverfahren finden).
Ich werde mir das sicher nochmal ansehen - davon abgesehen, dass iterative Näherungsverfahren wahrscheinlich nicht der beste Weg für Culling-Aufgaben sind. Und sicher auch nicht der schnellste für Kollisionen.

Für deinen Fall: wenn ich sowieso schon alles als separate Objekte splitte und verwalte, würde ich hier wahrscheinlich je Brush einmalig ein Vertex-Set berechnen und alles über Separating-Axis erledigen.

[Top-OR]

Ich glaube ich verstehe wie du das machst.
Prinzipiell müsste man ähnlich iterativ den geringsten Abstand (respektive ob eine Überschneidung stattfindet) zwischen zwei Brushes annähern können. Prinzip: beliebigen Surface-Punkt von Brush 1 auf die Oberfläche von Brush 2 "projizieren" (sprich kürzeste Distanz finden), diesen Punkt wieder auf Brush 1 projizieren usw. mehrfach hin- und herwerfen.

Ja, genau!

Mit Boxen geht das jedenfalls, und die PingPong-Strecke nähert sich der kürzesten Entfernung zwischen den Oberflächen (was automatisch die Sliding-Normale ergibt). Bilder dazu hatte ich kürzlich im Vorstellungsthread. Für Boxen gibts allerdings eine einfache explizite Abstandsfunktion (min/max der Halbachsen vergleichen, ohne Vertex- oder Polygon-Set).

Naja, es geht auch für Körper, die nicht Boxen sind. Nur bekommst du dann nach drei/vier/fünf mal hin- und herwerfen (gerade in deinen Szenario-Bild mit der sehr spitzen Ecke) eben nur einen Punkt ein bisschen darüber. Reicht mir aber.

Ich werde mir das sicher nochmal ansehen - davon abgesehen, dass iterative Näherungsverfahren wahrscheinlich nicht der beste Weg für Culling-Aufgaben sind. Und sicher auch nicht der schnellste für Kollisionen.

So teuer ist das garnicht bzw. es ist nicht unakzeptabel langsam .. zumindest für das gesamte Collision Handling gesehen.
Die Iterationen hier sind ja auch nicht soo teuer .. Projektion "Punkt auf Ebene" sind ja nur "Vektorprodukte" und keine Atomphysik. Relativ preiswert noch.

Im Video oben mache ich es bereits so. Die untere Zahl oben rechts im Bild ist die Laufzeit einer Gesamt-Welt-Physik/Dynamik-Iteration" in Millisekunden (ich mache Multithreading - Dynamik-Modul ist streng entkoppelt vom Rest: für "alles" inder Szene also etwas <0.3ms auf einem Ryzen Kern @3,7Ghz; ca. bei 1,2 ms auf einem alten Core i5 Mobile [dual core] @2,5Ghz).

Zugegeben, die Szene ist nicht allzu komplex,was Dynamik angeht: Nebem dem Avatar, mit dem ich da im BSP-Model rumlaufe, stehen unter dem Berg noch 10 Goblins rum (sieht man im Video nicht), die zumindest auf das Terrain drücken/"fallen" und in der Stadt noch eine Person, die auch ständig "fällt" ... also berechnet wird. Aber sicher könnte man da noch optimieren und es ist ja noch Luft nach oben.
Ich hatte vor der Brush-Implementierung übrigens eine Vertex-basierte Boxen/Mesh-Implementierung (oriented Meshes .. das, was jetzt die Brushes sind) und die war ungefähr/gefühlt gleich schnell ... also zumindest keine Dimensionen langsamer jetzt und die Brushes sind von der Implementierung her deutlich eleganter ... finde ich.

Und ich muss bedenken: Die ganze Dynamik/Physik/Kollision Handling ist bei mir insgesamt ja auch Iterativ. Ich behandle die Kollision mit dem ersten Objekt, was ich finde, und resolve sie gleich. Ich suche nicht erst das "nächste Objekt". Dann suche ich den nächsten Kollider mit der neu resolvten Position. Bis es keine Kollision mehr gibt. Aber es gibt harte Limits: Das mach ich dann maximal X-Mal (~30 glaub ich) und dann würde ich die Bewegung einfach "hart abwürgen" bzw. je nach Konfiguration auch einfach "zulassen" (stehenbleiben bzw. durchlaufen). Ist mir aber schon ewig nicht mehr passiert, dass ich durch den Boden falle oder gegen die Wand stosse. Die Implemetierung ist inzwischen recht zuverlässig/robust. Obwohl sich das mit "Iteration" (mit Maximal-Limit) immer recht schwammig anhört, funktioniert es erstaunlich stabil. Bisher schafft er das Ganze immer in ca <6 Gesamtiterationen (pro Objekt) .. vielleicht so 2 oder 3 ..

Selbst bei recht gemeinen Kollisionsszenarion wie "seltsamen Ecken mit Schrägen darüber" ist alles noch im Limit. Sind ja auch .. Achtung .. der kommt flach .. Edge Cases.

Für deinen Fall: wenn ich sowieso schon alles als separate Objekte splitte und verwalte, würde ich hier wahrscheinlich je Brush einmalig ein Vertex-Set berechnen und alles über Separating-Axis erledigen.

Ja, das Culling (das Frustum-Objekt) mache ich tatsächlich inzwischen wieder über Vertices, wobei man sich da vor Augen führen muss, dass man zur Projektion der Vertices auf die Achsen ja auch mehrmals ein Skalarprodukt macht (wenn nicht teilweise - z.B. für die Projektion der eignen Vertices auf die eignenen Achsen - precalculated). Das kostet in Summe auch, wenn auch nicht die Welt.

Ist aber gerade scheinbar der beste Kompromis und bis ich was besseres finde, mache ich das mal weiter...