Intersection zweier ebenenbasierter Brushes (Q3 Style)

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.

Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon Top-OR » 26.02.2018, 18:33

Hallo Freunde der Geometrie!

Ich beschäftige mich gerade mit Quake(-3)-style ebenenbasierten Brushes.

Bei wem es jetzt nicht klingelt: Dies sind konvexe Körper/Volumes, die implizit durch deine Menge/Liste von Ebenen im Raum definiert werden. Sonst nix, keine Vertices, keine Koordinaten oder sonste was.

Ich benutze diese nicht (nur) im Kontext von BSP-Trees, sondern allgemein als „Volumes“ für Geometrietests (als passive Geometrie): z.B. Ellipsoiden <-> Brushes .Dies funktioniert bis jetzt auch ganz gut.


Jetzt komme ich an eine Aufgabe, die ich irgendwie nicht (effizient) gelöst bekomme:

Ich möchte diese Brush-Implementierung (weil ich diese Datenstruktur auch recht elegant finde) nun auch nutzen, um das Visibility-Culling zu machen:

Das bedeutet, dass ich meinen Frustum und auch die achsenparallelle Boundingbox der Objekte (Quader) als Brush (Volume definiert durch Ebenen) implementieren möchte. Zumindest trage ich mich mit dem Gedanken.

Nun bemerke ich, dass ich keinen (schnellen) Test habe, mit dem ich Überlagerungen (ja/nein) herausfinden kann.

Gedanken, die ich in diese Richtung habe:
Bei allem, was so in Richtung Separating-Axis-Tests geht, braucht man ja die Koordinaten der Eckpunkte (Vertices), die man auch verschiedene Achsen projiziert und dann auf (nicht-)Überlagerung prüft. Ich will vor dem Überlappungstest (Intersection) aber nicht erst die Eckpunkte des Körpers errechnen müssen.

Ich habe mal überschlagen: Selbst bei zwei einfachen Boxen mit jeweils 6 Ebenen muss man da im schlimmsten Fall aus allen möglichen Ebenen-Schnittpunkts-3-er-Tupeln beider Brushes (und das sind auf dem Papier eine dreistellige Anzahl) noch Tests machen, ob sie „innerhalb“ aller Ebenen beider Körper liegen. Polygon-Clipping an den jeweils anderen Ebenen kling auch nicht so vielversprechend. Klingt erstmal nicht effizient.

Die zweite Möglichkeit, die Vertices z.B. durch Polygon-Clipping oder Ebenen-Schnittpunkte nach Erstellung/Drehung des Brushes jeweils neu zu errechnen (und dann bis zu nächsten Veränderung vorzuhalten), klingt auch nicht allzu elegant.


Sieht hier jemand eine Möglichkeit, mit (ebenenbasierten) Brushes, eine elegante/schnelle Möglichkeit, Intersection-Tests zwischen zwei solcher Körper zu machen, ohne vorher irgendwie die Vertices zu berechnen (z.B. durch Polygon-Clipping, Schnittpunktsberechnungen)?

Falls nicht, mache ich die Visibility-Volumes eben weiterhin mit vertexbasierten Volumes. Ich fänds halt nur irgendwie charmant...

Beste Grüße,
Top-OR
--
Verallgemeinerungen sind IMMER falsch.
Benutzeravatar
Top-OR
Jens H.
Establishment
 
Beiträge: 318
Registriert: 02.03.2011, 17:32
Wohnort: Esslingen/Dessau

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon Krishty » 27.02.2018, 17:25

Ich kann dir damit zwar nicht weiterhelfen, aber danke für die Erwähnung ebenenbasierter Brushes. Ich kannte die noch nicht und sie klingen sehr nützlich …
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
 
Beiträge: 6459
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon Top-OR » 01.03.2018, 11:22

Krishty, dass es noch ein Konzept im Spielebereich gibt, was du noch nicht kennst, gibt’s aber auch nur selten? Ich freu mich, dass ich Dir (zufällig) nen neuen Impuls geben konnte.

Ich bin ja eher passiv hier und konsumiere eher die Impulse von Anderen. Ich möchte an dieser Stelle mal zum Ausdruck bringen, dass ich die Gedanken(-spiele), Analysen und Anschauungen auf verschiedensten Gebieten (Hardware , APIs, Algorithmen, Datenstrukturen, Code, Gameplay, Assets) gerade auch von den erfahrenen/guten/neugierigen Leuten (wie Dir) hier im Forum extrem schätze!

Also hier, an alle aktiven ZFXler, mal ein pauschales „Danke“ für Eure Erfahrung, die Ihr hier im Forum in verschiedener Art teilt.

… auch, wenns hier gerade scheinbar nicht so voran geht … was u.U. aber auch daran liegen könnte, dass es keine so einfache/elegante/schnelle Lösung für das Problem gibt, wie ich das gerne so hätte.

Ich denke da oft drüber nach und ahne/befürchte, dass ich an Tests mit Vertices/Koordinaten für diesen Use-Case nicht vorbei komme.

Beste Grüße, Top-OR
--
Verallgemeinerungen sind IMMER falsch.
Benutzeravatar
Top-OR
Jens H.
Establishment
 
Beiträge: 318
Registriert: 02.03.2011, 17:32
Wohnort: Esslingen/Dessau

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon joeydee » 01.03.2018, 12:39

Ich habe über dein Problem auch schon nachgedacht, leider spontan auch noch nichts Offensichtliches gefunden.

allgemein als „Volumes“ für Geometrietests (als passive Geometrie): z.B. Ellipsoiden <-> Brushes .Dies funktioniert bis jetzt auch ganz gut.

Verstehe ich richtig: Ellipsoid <-> Brush geht gut, Brush <-> Brush fehlt?
(Ich bin in meinem Framework gerade am Experimentieren mit einer allgemeinen Form der Kollision/Intersection, die nicht auf Vertex-Sets beruht - falls ich rausfinde ob sich das auf solch einen Ebenenbrush übertragen lässt ohne Overhead zu produzieren sag ich natürlich Bescheid, wird leider noch ne Weile in Anspruch nehmen, und Erfolg ist natürlich auch nicht garantiert)

An der Stelle noch eine Frage zu den Ellipsoiden. Kurz ausgeholt: ich habe mich vor Jahren mal mit dem Descent-Levelformat befasst, ähnliche Epoche wie Q3 glaube ich. Ausgehend von einer Zelle (initial ein Würfel) wurden einzelne Seiten extrudiert um eine Nachbarzelle zu generieren und so einen komplexen Indoor-Level gleich mit Wand- und Portal-Informationen (für Kollision, Visibility und KI) zu schaffen; Kollisionserkennung und Tracking durch die Portale lief da auch über die Ebenengleichungen der Zellwände vs. Kugel, das fand ich ähnlich elegant. Ich hatte allerdings Kollisionsprobleme bei spitz zulaufenden Kanten und Ecken. Also z.B. ein spitzwinkliges Dreieck (Prisma) aus Ebenen - wenn man eine Kugel nur auf Ebenenabstand testet (also die Prämisse, dass der Mittelpunkt immer einen definierten Mindestabstand zu allen Ebenen des Sets haben muss), wird an der Spitze ein Hindernis erkannt wo keines ist (bei stumpfwinkligen Ecken fällt es weniger auf). Wie löst du diesen Fall?

Die zweite Möglichkeit, die Vertices z.B. durch Polygon-Clipping oder Ebenen-Schnittpunkte nach Erstellung/Drehung des Brushes jeweils neu zu errechnen

Berechnen musst du doch eigentlich nur einmalig bei Erstellung im Object-Space. Bei Drehung jagst du die durch die Objekt-Matrix, dann sind die genauso mitgedreht. Das nur am Rande - ich wäre natürlich auch weiter auf der Suche nach einem eleganten Test, der die Ebenengleichung direkt mit einbezieht. Irgendwie fühlt es sich ja danach an, dass es da was geben müsste.
joeydee
Establishment
 
Beiträge: 609
Registriert: 23.04.2003, 15:29

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon Chromanoid » 01.03.2018, 12:48

Nur so ein Gedanke: Du musst für Dein Frustum einen BSP-Tree bauen. Die Objekte müssen dann in "Frustum-Space" umgerechnet werden. Kann man BSP-Trees einfach transformieren? Wenn ja, kann man ja für das Frustum World-Space nehmen. Das wäre für den Fall, dass Deine Objekte weiterhin leicht mit einer Menge aus Ebenen verglichen werden können.

Ich bin mir nicht sicher, aber evt. kannst Du das Konzept auch für Objekt-Objekt-Kollision nutzen. D.h. Objekte bauen auch einen BSP-Tree auf. Du musst dann den Kollisionspartner entsprechend transformieren. Wo ich gerade nicht weiter komme, ist, wie dann die Erkennung der Überschneidung ablaufen muss. Vielleicht gibt's da irgendwelche interessanten Sachen im Constructive Solid Geometry (CSG) Bereich.
Benutzeravatar
Chromanoid
Christian Kulenkampff
Moderator
 
Beiträge: 3710
Registriert: 16.10.2002, 19:39
Wohnort: Lüneburg
Alter Benutzername: atr_23

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon Top-OR » 05.03.2018, 02:17

Hallo Allerseits!

Sorry für die späte Antwort ... der Job ... die Frau ... das Kind … die Pflichten … Ihr ahnt schon! Nichtsdestotrotz Danke für die verschiedenen Gedanken!

@Joydee
joeydee hat geschrieben:Ellipsoid <-> Brush geht gut, Brush <-> Brush fehlt?

Ja, du verstehst richtig!
Das Problem mit dem spitz zu laufenden Ecken kenne ich und habe es nicht mehr.
Ich habe meine Kollisionsroutinen stark an dieses Paper hier angelehnt: http://www.peroxide.dk/papers/collision/collision.pdf

Es ist knapp 15 Jahre als und für mich immernoch sehr erhellend. Diese Jungs (Peroxide Gruppe aus Dänemark) wollten damals ein Ulima-3D-Remake machen und hatten schon einige Techdemos draussen.
Ihre Tutorials und Demos haben für mich heute wie damals immernoch eine gewaltige Faszination!

Leider wurde auch Ihr Projekt vom „Alltag“ überrollt … der Job .. die Familie … Ihr wisst schon!

Das dort beschriebene Konzept der Slide-Plane habe ich adaptiert (auch wenn ich meine Slideplane nicht mehr anhand des Impulses/Movements berechne. Vielleicht hilft Dir das weiter.
Es flutscht mit Ellipsoiden hervorragend in allen Richtungen des Raumes – auch bei komplexer Brush-Umgebungs-Geometrie (selbst gebauter Q3-Level).

joeydee hat geschrieben: Berechnen musst du doch eigentlich nur einmalig bei Erstellung im Object-Space.

Ja, ich glaube auch. In Grunde baue ich gerade genau so etwas, auch wenn ich es gerne hätte, dass es direkt mit den Ebenen klappt… Määääääh!

@Chromanoid:
Danke auch für deinen Input. Ich bin mir nicht sicher, ob ich verstehe, was du meinst. Mein Problem ist ja genau die Object<->Object Intersection. Mir erschließt sich noch nicht ganz, warum ich das Ganze in einen BSP-Tree packen sollte. *grübel*
Chromanoid hat geschrieben:Constructive Solid Geometry (CSG)

CSG - Ich glaube, das sieht auf den ersten Blick interessant aus. Ich sollte da mal forschen. Danke für diese Richtung – das kannte ich so noch nicht!
--
Verallgemeinerungen sind IMMER falsch.
Benutzeravatar
Top-OR
Jens H.
Establishment
 
Beiträge: 318
Registriert: 02.03.2011, 17:32
Wohnort: Esslingen/Dessau

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon Chromanoid » 05.03.2018, 08:08

Top-OR hat geschrieben: @Chromanoid:
Danke auch für deinen Input. Ich bin mir nicht sicher, ob ich verstehe, was du meinst. Mein Problem ist ja genau die Object<->Object Intersection. Mir erschließt sich noch nicht ganz, warum ich das Ganze in einen BSP-Tree packen sollte. *grübel*
Vielleicht fehlen mir da einfach die Kenntnisse, aber ich glaube BSP-Trees und andere baumartige Strukturen sind da so ziemlich die einzigen Möglichkeiten die Anzahl der Ebenen, die Du prüfen musst, einzuschränken. Soweit ich das verstehe, ist doch das auch der eigentlich Grund, warum es überhaupt zur Einschränkung auf konvexe Körper in Quake gekommen ist - damit man damit gut einen BSP-Tree berechnen kann.

Viel Erfolg!
Benutzeravatar
Chromanoid
Christian Kulenkampff
Moderator
 
Beiträge: 3710
Registriert: 16.10.2002, 19:39
Wohnort: Lüneburg
Alter Benutzername: atr_23

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon joeydee » 05.03.2018, 10:48

Wenn auch die Prinzipien natürlich bekannt, habe ich selten eine Ausarbeitung so im Detail gesehen - klasse Paper und danke für den Link.
Allerdings wird darin das Problem der spitzen Kanten allein über die Ebenengleichung auch nicht gelöst, sondern man braucht ebenfalls Kanten- und Vertexinformationen um korrekt auf begrenzte Flächen zu testen:
... we’ll have to sweep sphere against points and edges of the triangle.

(falls ich es übersehen habe, gerne korrigieren)

Wie ermittelt man (du) denn den korrekten geringsten Abstand eines Raumpunkts zur Oberfläche eines reinen Ebenen-Sets, ohne dessen Kanten und Vertices zu kennen?
Warum ich hier nochmal im Detail nachhake:
- Falls du neben der reinen Ebenengleichung noch auf benachbarte Schnitte im Set testest, berechnest du ja eigentlich hier dennoch implizit Kanten und Vertices eines entsprechenden Polygonsets, was ein Hinweis darauf wäre, dass es in dieser Richtung "eleganter" nicht geht, spricht man braucht letztendlich einfach die Kanten-/Vertexinformation auch für Tests höherer Ordnung.
- Falls du dagegen eine Methode gefunden hast, die das eleganter hinbekommt, wäre das vielleicht ein Hinweis darauf, dass es in dieser Richtung auch einen eleganteren Ansatz für das Testen ganzer Sets untereinander geben könnte, welcher dann ebenfalls ohne Kanten/Vertices auskommen könnte.
joeydee
Establishment
 
Beiträge: 609
Registriert: 23.04.2003, 15:29

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon Top-OR » 05.03.2018, 14:23

joeydee hat geschrieben:Wenn auch die Prinzipien natürlich bekannt, habe ich selten eine Ausarbeitung so im Detail gesehen - klasse Paper und danke für den Link.
Allerdings wird darin das Problem der spitzen Kanten allein über die Ebenengleichung auch nicht gelöst, sondern man braucht ebenfalls Kanten- und Vertexinformationen um korrekt auf begrenzte Flächen zu testen:
... we’ll have to sweep sphere against points and edges of the triangle.

(falls ich es übersehen habe, gerne korrigieren)


Ich mache das ohne Vertices, weil ich die "Sliding-Plane" an der Oberfläche der (gottseidank) recht "runden" Ellipsoids anlehne (quasi als Tangente der Ellipsoidenoberfläche im Punkt, der am Nächsten zum Brush liegt [bzw. in dem Ellipsoiden Punkt, der als nächstes mit dem Brush kollidieren würde]). Dadurch brauche ich keine Informationen über vertices.

joeydee hat geschrieben:Wie ermittelt man (du) denn den korrekten geringsten Abstand eines Raumpunkts zur Oberfläche eines reinen Ebenen-Sets, ohne dessen Kanten und Vertices zu kennen?


Ich ermittle den Punkt auf dem Ellipsoiden, der als nächstes mit einer der Ebenen kollidiert (durch Testen des Elliposoiden mit allen Brush-Ebenen).
Dadurch bekomme ich für jede Brush-Ebene eine Punkt. Diesen kollidierenden Punkt auf der Brush-Ebene clippe ich mit hilfe der anderen Brush-Ebenen so, dass er auf der Oberfläche des Brushes liegt und nicht "außerhalb". Davon wähle ich den nächsten.

So ähnlich es es im Paper beschrieben. Nur, dass die sowas wie einen Kanten-Sweep-Schritt haben und ich mit den anderen Ebenen klippe. Der Grundgedanke ich aber der selbe, nur dass ich keine Vertices brauche...

.. ein bisschen konfus jetzt, aber vielleicht kannst du folgen.
--
Verallgemeinerungen sind IMMER falsch.
Benutzeravatar
Top-OR
Jens H.
Establishment
 
Beiträge: 318
Registriert: 02.03.2011, 17:32
Wohnort: Esslingen/Dessau

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon joeydee » 05.03.2018, 17:00

Bild
Beispiel: ein Prisma-Brush aus drei Ebenen, von oben betrachtet. Der Einfachheit halber für eine Kugel.

Fall A ist klar. Das beschreibst du im Prinzip. Rot wäre der nächste Kontaktpunkt und damit die Normale der "Sliding Plane".
Fall B kann man berechnen, wenn man den Schnittpunkt der grünen Ebenen kennt - aber wie geht das ohne Schnittberechnung, ausschließlich mit den Ebeneninformationen? Wie bekommst du den roten Punkt und die Normale, die ja keiner der Ebenennormalen entspricht?
Fall C hat keine Kollision, obwohl der Abstand der grauen Kugel zu allen Ebenen negativ ist. Was genau testest du, um hier keine Kollision zu bekommen?

Wenn man einmal Dynamik und Kugeln außen vor lässt, reduziert sich meine Frage eigentlich nur darauf:
Wie testest du den korrekten geometrischen Abstand eines Punktes im Raum zur Brush-Oberfläche, ohne die Schnitte der Ebenen zu berechnen?
Einfach nur den Abstand gegen alle Planes berechnen und den geringsten positiven Wert nehmen stimmt ja nicht immer, wie Fall B und C zeigt.
joeydee
Establishment
 
Beiträge: 609
Registriert: 23.04.2003, 15:29

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon Krishty » 05.03.2018, 22:58

joeydee hat geschrieben:Fall C hat keine Kollision, obwohl der Abstand der grauen Kugel zu allen Ebenen negativ ist.
Ich lese nur oberflächlich mit, aber ist in Fall C die graue Kugel nicht auf zwei positiven und einer negativen Seite?
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
 
Beiträge: 6459
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon joeydee » 06.03.2018, 08:48

Der Mittelpunkt, ja, aber der Oberflächenabstand meldet negativ. Kugelkollision ist ja immer eine punktuelle Abstandsmessung abzüglich Radius. Nur auf den Ebenentest beschränkt, würde die Kugel im Fall C eine Intersection mit 2 Ebenen melden, aber wie kann man das ausschließen wenn man den Schnittpunkt der Ebenen nicht kennt? Und umgekehrt, wie erkennt man eine Intersection, wenn man die Kugel ein wenig nach unten schiebt, und tatsächlich eine Intersection mit der Spitze stattfindet (aus reiner Ebenensicht wäre das erstmal derselbe Fall)?

Wenn man einmal Dynamik und Kugeln außen vor lässt, reduziert sich meine Frage eigentlich nur darauf:
Wie testest du den korrekten geometrischen Abstand eines Punktes im Raum zur Brush-Oberfläche

(wodurch man die korrekte Intersection einer Kugel testen könnte)

Vielleicht bin ich blind, aber ich konnte leider bisher keine "einfache" Lösung entdecken, ohne tatsächlich die Schnitte (Kanten und Vertices) zu berechnen - oder man nimmt einen hohen Fehlerquotienten in Kauf bei spitzen Winkeln.

Wenn es eine einfache Lösung gibt, könnte das für die Ausgangsfrage (elegante Intersection zweier Brushes) evtl weiterhelfen, daher halte ich das für wichtig.
joeydee
Establishment
 
Beiträge: 609
Registriert: 23.04.2003, 15:29

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon dot » 06.03.2018, 15:21

Analytische Visibility ist leider rein prinzipiell ein sehr komplexes Thema. In deinem konkreten Fall willst du effektiv rausfinden, ob die Schnittmenge zweier konvexer Körper leer ist. Nachdem deine konvexen Körper selbst als Schnittmenge der positiven (oder negativen) Halbräume eines Satzes von Ebenen definiert sind, sollte dein Problem äquivalent zur Frage sein, ob die Schnittmenge der Halbräume der Menge aller involvierten Ebenen (also die von beiden Körpern, bzw. die Begrenzungsebenen des Körpers und des jeweiligen Frustrum) leer ist oder nicht. Effektiv hast du ein Ungleichungssystem der Form
\begin{align}
a_1 \cdot x + b_1 \cdot y + c_1 \cdot z + d_1 \cdot w &\geq 0 \\
a_2 \cdot x + b_2 \cdot y + c_2 \cdot z + d_2 \cdot w &\geq 0 \\
\vdots \\
a_n \cdot x + b_n \cdot y + c_n \cdot z + d_n \cdot w &\geq 0
\end{align}

oder als Matrixungleichung
\begin{align}
\begin{bmatrix}
a_1 & b_1 & c_1 & d_1 \\
a_1 & b_1 & c_1 & d_1 \\
\vdots & \vdots & \vdots & \vdots \\
a_n & b_n & c_n & d_n \\
\end{bmatrix} \cdot \begin{bmatrix}x \\ y \\ z \\ w\end{bmatrix} \geq \begin{bmatrix}0 \\ 0 \\ \vdots \\ 0\end{bmatrix}
\end{align}

und willst wissen, ob dieses mindestens eine Lösung besitzt. Nicht gerade meine Expertise sowas, daher frag mich nicht wie man das am besten löst. 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...

Was deine Körper an sich betrifft, so willst du effektiv die konvexe Hülle der Schnittmenge der positven/negativen Halbräume der Begrenzungsebenen berechnen. 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: ). 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

Edit: LaTeX ist wohl kaputt!?
Benutzeravatar
dot
Michael Kenzel
Establishment
 
Beiträge: 1640
Registriert: 06.03.2004, 19:10

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon EyDu » 06.03.2018, 17:30

dot hat geschrieben:und willst wissen, ob dieses mindestens eine Lösung besitzt. Nicht gerade meine Expertise sowas, daher frag mich nicht wie man das am besten löst. 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...

Ich habe mir das Ungleichungssystem nicht ganz genau angeschaut, aber Ungleichungen und Ebenen schreien geradezu nach linearen Programmen. Um zu testen, ob überhaupt eine Lösung existiert, sollte die Startphase des Simplex-Verfahrens genügen.
EyDu
 
Beiträge: 82
Registriert: 24.08.2002, 18:52
Wohnort: Berlin

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon Chromanoid » 06.03.2018, 20:54

dot hat geschrieben:Edit: LaTeX ist wohl kaputt!?
Ich hoffe ich hab's jetzt gelöst. MathJax muss ich wohl außerdem hochladen, da der Script eigentlich gar nicht mehr geserved werden soll...
dot hat geschrieben:Nachdem deine konvexen Körper selbst als Schnittmenge der positiven (oder negativen) Halbräume eines Satzes von Ebenen definiert sind, sollte dein Problem äquivalent zur Frage sein, ob die Schnittmenge der Halbräume der Menge aller involvierten Ebenen (also die von beiden Körpern, bzw. die Begrenzungsebenen des Körpers und des jeweiligen Frustrum) leer ist oder nicht.
Ich glaube genau mit dieser Problematik beschäftigt sich ja auch CSG. Siehe z.B. http://pages.mtu.edu/~rmdsouza/CSG_BSP.html, edit: das hier sieht auch spannend aus: http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf Allerdings kann ich mir kaum vorstellen, dass das dadurch irgenwie effizienter wird. Da CSG ja eigentlich das kompliziertere Problem ist. Ich glaube daher, dass Du mit Deiner Einschätzung völlig richtig liegst und man lieber zusätzliche Daten wie Eckpunkte und Schnittkanten o.Ä. speichern sollte, um das was man sonst erst zwischendrin berechnen müsste vorzuhalten.

edit: Ich habe irgendwie übersehen, dass es hier ja nur um konvexe Körper geht. Da sollte ein BSP-Tree ja eigentlich keine nur Vorteile bringen, wenn man geschickt partitioniert. Das spielt glaube ich sofort dann eine Rolle, wenn man die erste Schnittkante zweier Ebenen berechnet hat. Dann will man sofort wissen welche Ebene man als nächstes gegen diese Schnittkante testen muss. Vielleicht kann man da also wirklich durch das Vereinigen von Bäumen etwas gewinnen... Mmhh

Noch ein Nachtrag dazu: Mit Tree Merging kann man tatsächlich wohl in O(log n) rauskriegen (bei n Ebenen in einem Partionierungs-BSP-Tree), ob zwei Objekte überlappen, die lediglich durch Ebenen repräsentiert werden:
Tree Merging.PNG
Quelle: https://pdfs.semanticscholar.org/c496/6 ... 4af2c9.pdf
Benutzeravatar
Chromanoid
Christian Kulenkampff
Moderator
 
Beiträge: 3710
Registriert: 16.10.2002, 19:39
Wohnort: Lüneburg
Alter Benutzername: atr_23

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon Top-OR » 13.03.2018, 23:35

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.

joeydee hat geschrieben: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...
Zuletzt geändert von Top-OR am 14.03.2018, 03:08, insgesamt 3-mal geändert.
--
Verallgemeinerungen sind IMMER falsch.
Benutzeravatar
Top-OR
Jens H.
Establishment
 
Beiträge: 318
Registriert: 02.03.2011, 17:32
Wohnort: Esslingen/Dessau

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon dot » 13.03.2018, 23:39

Top-OR hat geschrieben: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? ;)
Benutzeravatar
dot
Michael Kenzel
Establishment
 
Beiträge: 1640
Registriert: 06.03.2004, 19:10

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon Top-OR » 13.03.2018, 23:43

dot hat geschrieben:
Top-OR hat geschrieben: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. ;-)
--
Verallgemeinerungen sind IMMER falsch.
Benutzeravatar
Top-OR
Jens H.
Establishment
 
Beiträge: 318
Registriert: 02.03.2011, 17:32
Wohnort: Esslingen/Dessau

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon Top-OR » 14.03.2018, 00:15

dot hat geschrieben: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.

dot hat geschrieben: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).



dot hat geschrieben: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!
--
Verallgemeinerungen sind IMMER falsch.
Benutzeravatar
Top-OR
Jens H.
Establishment
 
Beiträge: 318
Registriert: 02.03.2011, 17:32
Wohnort: Esslingen/Dessau

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon Krishty » 14.03.2018, 00:59

Doppelte Bro-fist: einmal für die Engine und einmal für’s klassische ZFX-Thema!
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
 
Beiträge: 6459
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon Top-OR » 14.03.2018, 20:07

Krishty hat geschrieben: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:
Stephen Hawking hat geschrieben: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!
--
Verallgemeinerungen sind IMMER falsch.
Benutzeravatar
Top-OR
Jens H.
Establishment
 
Beiträge: 318
Registriert: 02.03.2011, 17:32
Wohnort: Esslingen/Dessau

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon Schrompf » 15.03.2018, 08:37

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).
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.
Benutzeravatar
Schrompf
Thomas Ziegenhagen
Moderator
 
Beiträge: 3710
Registriert: 26.02.2009, 00:44
Wohnort: Dresden
Benutzertext: Lernt nur selten dazu

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon joeydee » 15.03.2018, 12:48

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.
joeydee
Establishment
 
Beiträge: 609
Registriert: 23.04.2003, 15:29

Re: Intersection zweier ebenenbasierter Brushes (Q3 Style)

Beitragvon Top-OR » 15.03.2018, 20:20

joeydee hat geschrieben: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!
joeydee hat geschrieben: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.

joeydee hat geschrieben: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.

joeydee hat geschrieben: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...
--
Verallgemeinerungen sind IMMER falsch.
Benutzeravatar
Top-OR
Jens H.
Establishment
 
Beiträge: 318
Registriert: 02.03.2011, 17:32
Wohnort: Esslingen/Dessau


Zurück zu Algorithmen und Datenstrukturen

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast