Quake - Kollisionsabfrage

[Network]

Hi,

ich möchte untersuchen ob ein paar 3DModels sich schneiden.
Mein erster Gedanke war, dass ich den Komplexen 3DModels ein Radius zuteile um dann zu überprüfen ob sich andere 3DModels sich darin befinden. Evt schließe ich auch einen Quader um sie herum.
Mal schaun was schlussendlich schneller funktioniert.
Und erst wenn das true ist, mache ich die komplexen Kollisionsabfragen.

Aber ich erinnere mich an meinen damaligen Lehrer in Informatik, der andeutete wie das ganze in 3DShootern funktioniert und "Quake" zum ersten mal damit aufkam.

In dem man den Raum in große Blöcke einteilt und diese jeweils wieder in kleinere Blöcke, etc..
Dann überprüft man nur die Objekte die sich jeweils in diesen Blöcken oder Boxen befinden.

Das ist ja zwar ganz nett, und die Theorie hört sich super einfach an.
Nur ist meine Frage wie man dass den macht?
Selbstverständlich kann ich nach Objekten suchen, die sich in einem bestimmten Bereich aufhalten, und diesen Bereich dann immer kleiner machen... nur dann könnte ich ja auch gleich nur ein einziges mal die Variante verwenden, die ich im ersten Absatz erwähnt habe.
Somit müsste ich die Boxen der Objekte nur ein einziges mal miteinander vergleichen und nicht tausendmal die Schleife durchgehen...
Oder habe ich das Prinzip nicht verstanden?

Zum Zusammenfassen nochmal: Wie machte Quake das damals? Warum hunderte von immer kleiner werdenden Boxen überprüfen wenn man es auch ein eizniges mal machen kann.

Gruß
Network

 

[Fu3L]

Das was du suchst, nennt sich Scene Graph.
Du sortierst alle Objekte nach einem gewissen Kriterium. Im 2 Dimensionalen wäre ein Beispiel ein Quadtree (es gibt verschiedene Varianten):
Du hast Punktförmige Objekte. Nun unterteilst du deinen SceneGraph in immer kleinere Quadrate, bis du in jedem Quadrat nur noch einen Punkt hast. So kannst du mit deinem Punktförmigen Spieler sehr schnell feststellen, ob du in einem Bereich bist, wo sich ein Punkt befindet und wenn ja, eben nur mit einem einzigen Punkt kollidieren. Das ist natürlich ein sehr ideales Szenario.
Belies dich einfach ein wenig zum Scene Graph

 

[Marco13]

Weitere Stichworte wären Bounding Volume Hierarchy (BVH), KD-Trees, BSP-Trees ...

Der Trick bei den BVHs ist, dass man schnell ausschließen kann, dass zwei Objekte sich berühren. Zur eigentlichen Frage, falls ich sie richtig verstanden habe: Die BVH wird einmal am Anfang aufgebaut, und immer aktualisiert, wenn die Objekte sich bewegen oder verformen. (Du hattest es so beschrieben, als wolltest du die jedes mal "on the fly" ausrechnen - das würde so erstmal nicht viel Sinn machen...)

 

[Network]

Vielen Dank erstmal

[...]

Vielen Dank, jetzt kann ich endlich mal nach etwas googlen. Und ja tatsächlich das trifft (unüberaschenderweise) darauf zu. Bzw. bin ich jetzt irgendwie bei der Suche danach auf Octree abgerutscht. Hört sich jedenfals noch richtig an

[...]

Kleines Denkbeispiel...
Es sind 42 komplexe 3DModels in einem Raum. Der Raum ist eng, die Objekte sind ständig in Bewegung und prallen an den Seiten ab(<- Was jetzt mal vernachlässigt wird).
Überprüft werden soll ob die 3DModels kollidieren.

Lösung Nummer 1:
Jedes 3DModel wird mit einer Box umgeben.
Jetzt geht man den Vector durch, ob sich die Objekte schneiden. Ich habe die Rechnung nicht mehr im Kopf 42+41+40... etc. auszurechnen. Wenn meine Kopfrechnung stimmt sollten so etwa 900 Berechnungen pro Durchlauf herauskommen.
Da aber ja jedesmal der Schnitt von Boxen berechnet wird muss ja 8 mal (jeder Eckpunkt einmal) überprüft werden ob sich der Punkt innerhalb der Box mit 6 Flächen befindet.
Also im Grunde 900*6*8 = 43200 Berechnungen pro Zug.

Lösung Nummer 2:
OctTree. Hier muss ich bei jedem durchlauf Berechnen wo sich die 42 Objekte befinden im 3D Raum. Also muss ich bei jedem Zug alle Boxen durchlaufen und überprüfen ob das Objekt sich dort drin befindet.
Nehmen wir den Raum in 8 Boxen geteilt. Also 42(Objekte)*8(Boxen)*6(Seiten)*8(EckPunkte) = 16128 Berechnungen.
Dann sind im Schnitt jeweils 42/8 = ca. 5 Objekte in jedem Kasten, also muss nochmal (5+4+3+2)*6*8 = 672 mal überprüft werden ob eine Kollision vorliegt.
Das macht dann 16128 + 672 = 16800 Berechnungen pro Zug.
Und das jetzt mal 8, da es ja 8 Boxen gibt, ergibt 143400.

134400 > 43200

Ich weiss jetzt nicht ob ich mich irgendwo verrechnet habe oder irgendetwas vergessen. Aber meine Berechnung ergibt, dass die Octree Methode langsamer sein müsste.
Hinzu kommt noch, dass man bei der OctreeMethode Speicherzugriffe machen muss, indem man die Objekte in Vectoren schreibt, löscht und abfragt. Kommt ja nochmal zusätzlich Zeit hinzu.


Und das war meine Ursprüngliche Frage. Und ist sie immernoch, weil mir diverse Tutorials zu Octrees nicht schlüssig sind.
Habt Nachsicht wenn ich mich verrechnet habe. Habe größtenteils im Kopf gerechnet. Vieleicht habe ich ja irgendwo Fehler drin

Gruß
Network

 

[Fu3L]

Octree

Das ist eine sehr gängige Variante im 3-Dimensionalen

Ich schreibe meine Überlegungen mal mit dem Hinweis, dass ich noch keinen Scene Graph selbst implementiert habe:
Sagen wir deine 42 Objekte sind auf 5 Ebenen des Octress verteilt und du hast ein Objekt, dass sich innerhalb von 4 Quadern befindet. Diese Quader zu finden, ist relativ leicht. Im schlimmsten Fall 4*5*8 = 160 Überprüfungen. Dann kannst du deine Mesh-oder was auch immer-genaue Kollisionserkennung machen und zwar mit jeweils einem Objekt pro Quader, weil ein Quader nur ein Objekt enthält (oder wenige... bin nicht so sicher, wie mans genau implementiert)

 

[Marco13]

Die Rechnung habe ich nicht ganz nachvollzogen (auch uhrzeitbedingt). Aber es scheint, als wäre die Frage darin begründet, dass du nicht berücksichtigst, dass diese Boxen ja einen Baum bilden. Es gibt sehr (sehr, sehr, SEHR!) viel Literatur zu dem Thema (auch viele Papers), hab' mal auf die schnelle eine Google Bildersuche gemacht, auf Uni Weimar - Virtual Reality: Beschleunigungsstrukturen für echtzeitfähiges Ray-Tracing auf aktueller Hardware-Infrastruktur in Abbildung 4 sieht man's einigermaßen (wenn auch nicht so schön suggestiv, wie es sein könnte) :

http://www.uni-weimar.de/cms/fileadmin/medien/vr/pictures/asrtrt01/BVH.png

Angenommen, man müßte dort jetzt alle Dreiecke auf Kollisionen miteinander testen. Dann müßte man normalerweise für 6 Dreiecke 15 Tests machen (Für n allgemein: n*(n-1)/2 ). Solche Dreieck-Dreieck-Kollisionstests sind relativ aufwändig. Viel aufwändiger, als zwei Boxes auf überschneidungen zu testen (das sind nur 6 if-Abfragen). Wenn man aber schon die BVH aufgebaut hat, und mit dem Dreieck unten Links anfängt, muss man nur dessen Bounding Box mit den Bounding Boxes testen, die zu oberen Knoten (!) des Baums gehören, und sieht: Die Bounding Box überschneidet sich mit keiner andernen. Man kann durch den Test mit den BBs auf den höheren Ebenen des Baums schon große Teile der Szene ausschließen, und spart sich viele exakte Dreieck-Dreieck-Tests.
Da stecken einige Annahmen drin, und für 3D oder viele Objekte kommen noch Aspekte dazu, die jetzt unerwähnt bleiben. Bei Octrees, KD-Trees oder BSP-Trees (letztere werden AFAIK bei Quake verwendet, kann mich aber irren) sieht es ein bißchen anders aus, aber die grundidee ist die gleiche.

 

[Empire@Home]

Wenn es dir weniger um die interne logic geht, sondern nur darum sowas berechnet zu bekommen kann ich dir empfehlen auf jbullet zu schauen. (Oder auf ein java natives bullet binding, zb zu finden bei JME3 als teilmodul)
Ansosnten wirst du bestimmt 2 Jahre brachen bis du alle Konzepte für die Constraint, collision, ect solver verstehst und die effizient implementiert bekommmst. (Insbesondere bei DBVT Broadphases wars bei mir dann entgültig vorbei, ich verstehe zwar noch die idee dahinter, aber damit ists auch schon vorbei)

Bruteforce könnte man btw jedes Triangle mit jedem triangle auf schnittpunkte testen. (Nach einem vorherigen check mit einer bounding box)


Ansonsten auf der bullet physic engine seite sind einige mehr oder wenigergute wikieinträge die den algemeinen ablauf der physic engine beschreiben.

 

[irgendjemand]

@TO
ich verstehe deine sorgen um die "vielen" berechnung nicht ...

moderen CPUs schaffen mehrere GFLOPS ... moderene GPUs sogar mehrer 100 GFLOPS bis zu 1 TFLOPS

GFLOPS = gigaFLOPS = milliarden FLoatingpoint-OPerations / Secode
ergo : 1GFLOPS = 1 mrd gleitkomma operationen pro sekunde ... und da machst du dir sorgen um die paar hunderttausend berechnung ...
denke das ist eher unbegründet ... da zu zeiten als quake rauskam und diese technik verwendete selbst MFLOPS grade mal für "supercomputer" machbar waren ... und quake lief ja auf jedem "PC" ...

und um die grafik brauchst du dir ja wohl kaum sorgen machen ... mit ner graka die 1 TFLOPS schafft *und das ist auch gar nicht mal sooo high-end ... main-stream vllt 250GFLOPS - 500GFLOPS* kann dir das rendern egal sein ... denn die collision-detection läuft eh ja über die CPU

 

[Network]

@irgendjemand
Deine Behauptungen kann ich leider nicht nachprüfen, jedoch vergisst du 3 Dinge zu beachten:
1. Evt. Müssen noch andere Berechnungen durchgeführt werden. (Siehe Spieleentwicklung). Dabei sollen natürlich die ganzen Algorithmen sich gegenseitig soviel Platz machen wie möglich. Schneller gleich besser.
2. Je kleiner die benötigten Ressourcen, desto mehr Personen kann man ansprechen. Sowieso da Java nicht auf allen Systemen so leistungsstark ist.
3. Ressourcenverschwendung. In der Industrie kommt es auf jeden Tick an. Ein paar Ticks mehr können die Kosten der Unterhaltung und Produktion vervielfachen. Überhaupt ist die Ausführung von unnötig vielen Berechnugen reine Energieverschwendung.

Wollte ich nur einmal angemerkt haben

Bei der Grafik gebe ich dir recht. Viel kann man hier nicht falsch machen. OpenGL, DirectX etc. machen ja die Arbeit

 

[Fu3L]

denke das ist eher unbegründet ... da zu zeiten als quake rauskam und diese technik verwendete selbst MFLOPS grade mal für "supercomputer" machbar waren ... und quake lief ja auf jedem "PC" ...

OpenGL, DirectX etc. machen ja die Arbeit

Wenns an so Sachen geht wie SSAO (mal englisch Wiki nachlesen), und Schatteneffekte mit teilweise transparenten Objekten, dann knickt dir auch ne moderne mittelklasse-laptop-grafikkarte schnell ein, wenn du keinen vernünftigen Scene Graph hast und so nicht vorher schon was cullen kannst.

Und wenn du dann noch Terrain generierst, 30-40 KI Spieler mit Wegfindungsalgorithmen und realistische Physik hast, dann bist du froh um die "paar hundert tausend" Berechnungen, die du durch den Scene Graph sparst. Die Anforderungen, die an moderne Games gestellt werden, sind eben höher als bei Quake damals. Außerdem wie Network schon sagt: Verschwenedn will man nicht und wenn man an jeder Stelle so denkt, dann kommt man nicht weit

Nicht umsonst suchen Firmen wie Crytek die besten und keine mittelmäßigen Leute...

 

[irgendjemand]

ich wollte hier auch nicht zum sinnlosen verschwenden von rechenleistung aufrufen ... sondern lediglich mal so den hinweis geben das moderne systeme die leistung haben um eben diesen haufen auf berechnungen schnell genug durchzuarbeiten das keine "laggs" auftreten ... und wenn man dann noch so "sauber" wie quake arbeitet dürfte es ja wohl keine probleme geben mal eben ein paar hunderttausend berechnungen zu machen ...

 

[Evil-Devil]

Notfalls gibt es noch die Möglichkeit die Kollisionsberechnung im Shader berechnen zu lassen.

Generell 42 Objekte mit einer Bounding Box berechnen zu lassen halte ich jetzt für nicht soviel. Du kannst dir bereits viele Rechnungen sparen, wenn du erstmal nur vergleichst ob das Objekt mit seiner Masse in Bewegungsrichtung irgendwo landet, wo auch ein anderes Objekt gelandet ist. Die Bewegung deiner Objekte ist doch gerichtet oder wechselt die von einer Sekunde auf die andere?

Sonst wie gesagt Shader. Gibt/gab schon Partikelgenaue Kollisionsberechnungen, auch wenn das manches an Performance frisst.

 

[Network]

Notfalls gibt es noch die Möglichkeit die Kollisionsberechnung im Shader berechnen zu lassen.

Generell 42 Objekte mit einer Bounding Box berechnen zu lassen halte ich jetzt für nicht soviel. Du kannst dir bereits viele Rechnungen sparen, wenn du erstmal nur vergleichst ob das Objekt mit seiner Masse in Bewegungsrichtung irgendwo landet, wo auch ein anderes Objekt gelandet ist. Die Bewegung deiner Objekte ist doch gerichtet oder wechselt die von einer Sekunde auf die andere?

Sonst wie gesagt Shader. Gibt/gab schon Partikelgenaue Kollisionsberechnungen, auch wenn das manches an Performance frisst.

Also vielen Dank.
Im Shader? Ich dachte immer der wäre für irgendwelches Grafikkrimskrams gedacht (Entschuldigung, hab mich nie damit beschäftigt )

Also das oben war nur ein Beispiel. Eig. kann es sich auch locker um 2000 Objekte handeln. Es ging einfach nur um eine Kollisionsberechnung wie sie funktioniert und war nicht auf 42 beschränkt

[Von: de.wikipedia.org]
In der Softwareentwicklung wird die Zahl 42 – ähnlich wie 0815 und 4711 – häufig von Programmierern als magische Zahl verwendet, also als fester Zahlenwert, dem jeder ansehen kann, dass er keinen tieferen Sinn hat, sondern nur ein Beispiel für einen beliebigen Wert ist.

oder irgendwelche speziellen Formen.
Und die Bewegungsrichtung kann sich zu jedem Zeitpunkt verändern.

Ich hab mich bereits in die Links der oberen Posts eingelesen und kam dabei auf die Separating Axis Theorem. Und versuche mir irgendwie immernoch klar zu machen inwieweit das ganze funktioniert und was gemacht werden muss, weil Theorie und Praxis sind auf den Tutorialseiten meilenweit entfernt

Trotzdem werd ich mal einen Blick auf die Machenschaften eines Shaders werfen

 

[Marco13]

Das mit den Shadern ist so eine Sache. Erstens wird daran noch fleißig geforscht, und zweitens ist es nichts, was man mal so aus dem Handgelenk einfach runterschreibt... (Halt' dich gefälligst zurück, Fancy! ). Viele Konzepte aus der Kollisionserkennung sind schwer auf Shader-Architekturen übertragbar (schon angefangen bei Hierarchien und rekursivem Traversieren von Bäumen). Ansehen kann man es sich natürlich, aber zu glauben, dass man da als "Anfänger" was zum Laufen bringt, wäre schon arg optimistisch - und in jedem Fall besteht die Gefahr, dass der Arbeitsaufwand unverhältnismäßig hoch ist (im Vergleich zu einer algorithmisch guten plain-Java-Implementierung).

 

[Network]

Also ich hab mir Shader angeschaut und meine Vermutung wurde bestätigt. Ich hab schonmal vor Jahren kommerziell an Shadern rumgeschrieben (Das war mir garnicht so direkt bewusst) für diverse Effekte. Das war aber wirklich noch vor Jahren, da gabs noch nicht viel zu beachten und es war relativ einfach. Und da gings um Glow- und Wischeffekte. Wies heute ist weiss ich natürlich nicht.

Aber kann man mit Shadern tatsächlich Kollisionen berechnen?
Also Pixelgenaue Kollisionen könnte ich mir vorstellen, aber weniger (für eine CPU jedenfals) rechenintensivere Methoden auch? Das entzieht sich meinem alten Verständnis was Shader können und sollen. Und ob das dann wirklich "sparsamer" ist ist auch eine Frage.
Also interessieren tut es mich schon, wenn auch nicht sinnvoll interessiert aber der Interessehalber.

 

[Evil-Devil]

Hab eine kurze SUche getan und auf Gamasutra noch was gefunden. Gamasutra - Features - Advanced Collision Detection Techniques

Ich bin mir sicher das es dort und auf den anderen Dev Sites noch mehr gute Literatur zu dem Thema geben wird, die auch etwas aktueller ist.

 

[Guest2]

Moin,

Halt' dich gefälligst zurück, Fancy!

ich halt mich schon zurück, seitdem Network das Topic eröffnet hat.

Immerhin ist Quake inzwischen 16 Jahre alt, da hat sich in der Zwischenzeit schon einiges getan. Bei einer modern angelten Rendering Pipeline weiß die CPU oft gar nicht genau, wo sich die einzelnen Objekte befinden und noch viel seltener, wo sich einzelne Dreiecke befinden. Alle CPU basierten Ansätze funktionieren dann schon nicht mehr sinnvoll.

Ein relativ abgeschlossenes Beispiel gibt es z.B. von NVIDIA: Real-Time Rigid Body Simulation on GPUs


Ein GPU Ansatz zur Kollisionserkennung macht aber imho in der Tat wirklich nur dann Sinn, wenn man Shader auch schon für alles andere einsetzt. Nach dem was bisher hier im Thread steht, ist imho ein CPU basierter Ansatz praktischer.

Viele Grüße,
Fancy

 

[Fu3L]

Wie siehts denn aus, wenn ich das Ergebnis auf der CPU weiternutzen möchte? Also Aktionen ausführen oder so. Wie mach ich das? Ich kenn bisher nur "Datenrückgabe" durch rendern eines Bildes in einen Offscreen Buffer (oder so ähnlich)

 

[Guest2]

Das kommt drauf an, welche Ergebnisse an die CPU zurückgegeben werden sollen. Sollen die Ergebnisse des Fragment-Shaders zurückgegeben werden, dann bieten sich FBO/PBO schon an. Wenn die Ergebnisse des Vertex- oder Geometrie-Shaders zurückgegeben werden sollen, bietet sich Transform-Feedback an. Mit OpenGL 4.0 gab es da auch einige zusätzliche Spielsachen (bisschen runterscrollen).

Viele Grüße,
Fancy

 

[Fu3L]

Danke^^ Sieht auf jeden Fall so kompliziert aus wie ihr sagt^^

 

[irgendjemand]

um mal noch ne andere frage aufzuwerfen : wie würde man "normalen cpu kram" auf der GPU berechnen wenn man z.b. KEIN cuda *nvidia* zur verfügung hat weil man eben eine AMD karte hat ? dann müsste man sich mit OpenGL/DirectX einen würg-a-raund basteln ... oder gibts dann für AMD karten eine ähnliche "sprache" um normale berechnungen auf der graka laufen zu lassen ?

 

[Marco13]

Ja, OpenCL - gibt's für Intel, NVIDIA, AMD, und andere: Khronos OpenCL API Registry
Eine Java-Anbindung davon (und Links zu mehreren weiteren) gibt's auf jocl.org - Java bindings for OpenCL (Schamlose Eigenwerbung )