Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki |  Impressum

Aktuelle Zeit: Mo Jul 15, 2019 19:29

Foren-Übersicht » Programmierung » Allgemein
Unbeantwortete Themen | Aktive Themen



Ein neues Thema erstellen Auf das Thema antworten  [ 3 Beiträge ] 
Autor Nachricht
 Betreff des Beitrags: Kollisions-Erkennung wie verwaltet?
BeitragVerfasst: Sa Mär 16, 2019 00:46 
Offline
DGL Member
Benutzeravatar

Registriert: Fr Jul 12, 2002 07:15
Beiträge: 916
Wohnort: Dietzhölztal / Hessen
Programmiersprache: C/C++, Obj-C
Hi,

ich wende mich gerade dem Themen bereich zu, vor dem ich mich immer gedrückt habe: Collision Detection. Und mir geht es jetzt nicht um die Frage, wie minimiere ich die Anzahl der zu prüfenden Polygone. Auch nicht um die mathematische Themen, sondern eher um die Frage danach, wie man das eigentlich am besten verwaltet, was die Level-Geometry angeht.

Für die Außenwelt denke ich, wird ja erstmal ein Terrain-Collision-Decetion-Algorithmus verwedet (was Boden ist, ist ja klar definiert), die Objekte in der Welt (Bäume, Zäune, Schilder, Was-Auch-Immer) dann vermutlich mit Axis-Aligned Bounding Boxen. Und dann ggf. im Detail auf die Polygone, wenn notwendig. Richtig?

Wie aber sieht das bei aus, wenn man z. B. ein Dungeon betritt. Wird da auch der Boden für Terrain-Collision verwendet und die Wände auf Polygon-Ebene geprüft? Aber wann ist eine Wand dann eine Wand? Aber 45°, ab 70° Winkel zum Boden? Oder wird da eine andere Art der Kollision-Erkennung verwendet? Und wenn ich in der Außenwelt ein Haus betrete, was wird dann dort verwendet. Gibt es ein allgemeines vorgehen, dass so ziemlich alles abdeckt? Oder werden in den Level-Editoren der Game-Engines für jede Wand, jeden Boden, etc. extra Informationen für die Kollosionserkennung übergeben?

Irgendwie hab ich mich bei meinen Überlegungen gedanklich etwas verlaufen, wäre nett, wenn ihr mir helfen könntet. Was ist da die beste Lösung?

Gruß
Marc

_________________
Und was würdest Du tun, wenn Du wüsstest, dass morgen Dein letzter Tag auf dieser Erde ist?


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Sa Mär 16, 2019 15:05 
Offline
DGL Member
Benutzeravatar

Registriert: Mi Aug 14, 2013 21:17
Beiträge: 570
Programmiersprache: C++
Auf jeden Fall musst du irgendeine Art von Raumunterteilungsverfahren einsetzen (z. B. Octrees), um die Anzahl der zu testenden Kollisionen zu reduzieren. Darüber hinaus hängt es wohl auch von der Beschaffenheit der Welt ab, was sich am ehesten anbietet. Ist die Welt komplett statisch, kannst du im Prinzip einen Octree nehmen und in seinen Blättern die Referenzen zu den entsprechenden Dreiecken hinterlegen. So könntest du vermutlich relativ effizient Kollisionstests auf Dreiecksebene durchführen.

Wenn es Objekte gibt, die sich verformen oder ihren Standort ändern, ist dieser Ansatz ungeeignet, weil man den Baum ständig neu bauen bzw. umbauen müsste. Dann sollte man sich außerdem noch die Frage stellen, ob man dreiecksgenaue Kollisionserkennung überhaupt will, oder ob z. B. Kugeln und Zylinder in manchen Fällen die bessere (und weniger rechenintensive) Annäherung an eine Form sind als Dreiecke. Ich muss sagen, dass ich für mich auch noch keine in der Praxis zufriedenstellende Lösung gefunden habe.

_________________
So aktivierst du Syntaxhighlighting im Forum: [code=pascal ][/code], [code=cpp ][/code], [code=java ][/code] oder [code=glsl ][/code] (ohne die Leerzeichen)


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Mo Apr 08, 2019 12:56 
Offline
DGL Member
Benutzeravatar

Registriert: Di Mai 18, 2004 16:45
Beiträge: 2550
Wohnort: Berlin
Programmiersprache: C/C++, C#
Zerlege deine Probleme und betrachte sie separat.
Es gibt diverse Spatial Systeme, um möglichst viele Objekte möglichst schnell aus den zu prüfenden Pool zu bekomme. Z.B. Octree, Quadtree, Portals und Seperate Axis Theorem.
Nutzt für die jeweiligen Probleme das einfachste Mittel, wobei Einfach hier meint, schnell zu implementieren und einfach zu verstehen. So kannst du bei Performance Probleme sehr schnell und gezielt entscheiden wie du optimieren kannst.

Wenn es um Spieler und NPCs geht, werden in der Regel NavMeshes generiert, welche fest legen, wo die Akteure sich bewegen können.
Recast ist z.B. ein Tool welches die herstellen kann. Dort sagt man auch welche Höhenunterschiede und Neigungen ein Akteur überwinden kann und entsprechend werden Bereiche raus genommen, die nicht passierbar sind.

Für Dynamische Objekte(ausser NPCs) wird oft mit dem Seperate Axis Theorem gearbeitet, weil es sehr einfach zu verstehen, implementieren und performant ist.

Es werden gerne Octrees verwendet, weil sie recht einfach sind und flexibel, auch gut optimierbar aber Quadtree können durchaus viel besser sein, so nutzte WOW früher Quadtrees und Raycasts, ob sich das verändert hat weiß ich ned.

In der Regel geht man vom einfachsten bis zum komplexesten Test, für Kollisionserkennung. Spatial Systems sind die einfachsten, da sie ganze Objektgruppen mit einem Test ausschließen können.
Danach kommt es drauf an, Sphere Tests sind die nächst einfachen aber können abhängig von Mittelpunkt und Radius schnell Zuviel Raum einnehmen und den Test bestehen obwohl sie nicht drin wären und eine bessere Wahl des Mittelpunkt dies verhindert hätte. Also sollte man gucken hier vorab eine Boundingsphere zu berechnen und mit zu liefern.
Die Bounding Box oder gar eine Hull sind schon recht komplex aber können mit Parallelisierung auch recht effizient berechnet werden. Dabei muss man nur beim Code drauf achten, dass dieser möglichst wenig Instruktionen hat und gut zerlegt ist. Dann tut die CPU die Berechnungen nebeneinander ausführen und bis die Ergebnisse gebraucht werden. SIMD und als letzter Notnagel helfen Threads aber das bringt nicht mehr soviel, wie so mancher glaubt.
Die Wahl des Richtigen Algorithmus ist meistens der Entscheidende Faktor.

Für Software Occlussion culling, was in AAA Games oft genutzt wird, benutzt man auch oft das Physik mesh zum rendern und für einige Fälle wird noch weiter Triangles eingespart, damit das fix durch läuft.

Zum Thema Algorithmus. Man braucht nur Objekte sich angucken, die sich auch ändern können. Also 2 Dynamische Objekte, deren Kräfte auf 0 gefallen sind brauchen nicht mehr in der Physik berechnet werden. Also eine Prüfung macht kein Sinn, da man einfach den letzten Stand cachen und abfragen kann. Erst wenn wieder Kräfte zugewiesen werden, sollten sie geprüft werden. Ein Bool zu prüfen ist halt einfacher als ein Sphere Test. Man kann mit AVX512 z.B. pro Operation 512 Objekte parallel Prüfen, ob sie berechnet werden sollen. Davon kann man mehrere Operationen Gleichzeit ausführen. Also macht es Sinn so ein Cache auf ein größeren Bereich zu verwenden, da haben wir bereits ein Spatial Partitioning System z.B. Octree und dort hinterlegt man ein Bit-Array, wo jedes Objekt im Node einem Bit entspricht. Selbst eine einfache Schleife über das Bit-Array wird vom Compiler und CPU schon gut optimiert.

Bei Bullet Physik gibt es im Wiki eine recht gute Doku wie die Engine funktioniert und welche Phasen was machen und wieso.
AABB sind praktisch bei der Kollisionsberechnung aber können viel Arbeit machen, diese zu bauen.
Ich empfehle diese aus der Boundingsphere zu bauen und die Boundingsphere etwas aufwändiger vor zu berechnen.
Such einfach den Minimum und Maximum aus dem Mesh, wie bei einer Boundingbox, berechne die länge, teile sie durch 2 und du hast den radius und dann berechnest du den Mittelpunkt, in dem du Minimum + Radius ausrechnest.
Maximum und Minimum für die AABB bekommst du mit Boundingsphere Position + Radius = MAximum und Boundingsphere Position - Radius = Minimum. Aus diesen kannst du alle Eckpunkte, ableiten. Es gibt sehr wahrscheinlich eine kompaktere AABB für das Model aber dann müsste man die Transformation auf die Vertices anwenden und jeden einzelnen Vertex verarbeiten.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 3 Beiträge ] 
Foren-Übersicht » Programmierung » Allgemein


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
cron
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.032s | 15 Queries | GZIP : On ]