Kollision zweier Dreiecke in einem 3d Koordinatensystem |
| 04.02.2012, 13:52 | ph3 | Auf diesen Beitrag antworten » | ||
| Kollision zweier Dreiecke in einem 3d Koordinatensystem Ich hätte eine Frage: Ich bräuchte für meine Spiele eine Kollisionserkennung. Da die 3d Modelle aus Dreiecken bestehen, wüsste ich nun gerne, wie man sich ausrechnen kann, ob zwei Dreiecke in einem 3d Koordinatensystem kollidieren. Ich habe mir bereits sehr viele Seiten dazu durchgelesen, leider gibt es oft entweder gar keine Lösung, oder ich verstehe sie nicht 
Wenn ihr eine Lösung habt, formuliert sie bitte verständlich für einen 13 jährigen der 8. Schulstufe (ich habe leider nur Grundkenntnisse der Vektorenrechnung und kenne mich nicht wirklich mit Ebenen aus,...) Meine Ideen: Ein Lösungsansatz, der mir bereits untergekommen ist, ist, jede Seite jedes Dreiecks durchzugehen, prüfen, ob eine Kollision mit der Ebene besteht auf der das jeweils andere Dreieck liegt, wenn ja die Schnittpunktkoordinaten auf die Ebene zu übertragen und zu sehen, ob der Schnittpunkt auf der Ebene "in dem" Dreieck liegt. Leider fehlen mir noch die Kenntnisse, um dies mathematisch umzusetzen. |
||||
| 04.02.2012, 15:55 | Dopap | Auf diesen Beitrag antworten » | ||
eine erste Prüfung würde ich so ansetzen: 1.) liegen alle 3 Punkte auf derselben Seite der Ebene? wenn nein, dann 2.) wie gehabt Schnittpunkt mit der Ebene 3.) Schnittpunkt im Dreieck? der letzte Punkt erfordert aber auch noch ein Stück Arbeit. Das ganze Arbeit macht wohl nur als Computerprogramm einen Sinn. Ich denke, dass es darum geht. |
||||
| 04.02.2012, 17:20 | riwe | Auf diesen Beitrag antworten » | ||
punkt 1 macht vermutlich nur sinn, wenn kollisionen eher selten sind 
|
||||
| 05.02.2012, 03:09 | DerDepp | Auf diesen Beitrag antworten » | ||
| RE: Kollision zweier Dreiecke in einem 3d Koordinatensystem Aloah
Die Hit-Detektion macht man normalerweise nicht mit den Dreiecken selbst. Das wäre viel zu rechenintensiv. Stattdessen legt man um jedes Objekt eine Kugel mit Mittelpunkt M und Radius R. Will man nun prüfen, ob ein Objekt (M, R) ein zweites Objekt (m, r) trifft. schaut man erst, ob sich die beiden Kugeln drumherum treffen. Das ist genau dann der Fall, wenn der Abstand der Mittelpunkte kleiner ist als die Summe der Radien: So kannst du z.B. um jede Spielfigur eine Kugel legen. Wenn die Kugel der Spielfigur von einer anderen Kugel geschnitten wird, kannst du die Hit-Detection noch verfeinern. Du kannst z.B. um den Fuß, den Unterschenkel, das Knie, den Oberschenkel... weitere Kugeln legen und prüfen, ob tatsächlich ein Hit vorliegt und welches Körperteil getroffen wurde. Theoretisch könntest du sogar um jedes Dreieck aus dem Drahtmodell der Spielfigur eine Kugel legen. Du könntest z.B. für jedes Dreieck den Umkreis berechnen und den Mittelpunkt dieses Kreises als Kugelmittelpunkt und den Radius des Umkreises als Kugelradius wählen. Aber dann bleibt keine Rechenzeit mehr für das Spiel selbst übrig
|
||||
| 05.02.2012, 20:33 | pd3 | Auf diesen Beitrag antworten » | ||
Toller Ansatz! Am Anfang mit einer Kugel um das Modell zu prüfen, ob sich die Modelle überhaupt treffen können wollte ich zwar schon machen, aber um jedes Dreieck eine Kugel zu nehmen und so die Dreieckskollisionen zu berechnen, darauf wäre ich nie gekommen... muss ich unbedingt mal probieren! |
||||
| 05.02.2012, 21:45 | riwe | Auf diesen Beitrag antworten » | ||
ob da nicht würfeln besser wäre 
der aufwand im anderen fall scheint mir nur dann (eher) groß, wenn beide 3ecke in derselnen ebene liegen, man hat halt immer ein lineares gls mit 3 unbekannten zu lösen |
||||
| Anzeige | ||||
|
|
||||
| 05.02.2012, 21:52 | Airblader | Auf diesen Beitrag antworten » | ||
Je nach Objekt müssen es ja keine Kreise sein, sondern vielleicht auch Quader. Hauptsache, man verwende einfachere Strukturen, durch welche die Objekte approximiert werden. Und bei einer Kollision kann man, wie von DerDepp schon gesagt, das Raster verfeinern. Kugeln sind halt herrlich einfach zu implementieren, aber einen langen Stab mit einer Kugel zu approximieren ist ziemlich unsinnig. Auch eine Quaderkollision lässt sich vernünftig schnell erkennen. Jedes Dreieck zu überprüfen (egal ob mit einer Kugel oder direkt) ist für Spiele absolut überzogen und legt dieses lahm. Sowas wäre eher bei einer Simulation wichtig. air |
||||
| 05.02.2012, 22:38 | riwe | Auf diesen Beitrag antworten » | ||
vor der kritik sollte man vielleicht ein bißerl nachdenken. der stab ist ein dreieck "von der schmalen seite" aus gesehen. mehr dazu zu sagen erspare ich mir
ein quader ist wahrlich ein besonders eleganter ersatz für ein dreieck
|
||||
| 06.02.2012, 06:10 | Airblader | Auf diesen Beitrag antworten » | ||
Ich hatte nicht auf deinen Post Bezug genommen, sondern auf die allgemeine "Man-ersetze-einfach alles-durch-Kugeln"-Vorgehensweise. Der Stab hatte mit deinem Bild also nichts zu tun, sondern sollte ein Exemplar für ein Objekt in einem Spiel sein, bei dem eine sphärische Detektion recht unbrauchbar wäre. Edit: Wie hier ab ca. 1:05 zu sehen, finden solche Hitboxes tatsächlich Anwendung. Auch wikipedia kennt sie, ob der Begriff "Hitbox" nun aber speziell Quader meint oder allgemein Bounding Volumes bezeichnet, bleibt wohl eine Definitionsfrage. Die Quintessenz ist, dass die Welt nicht schwarz und weiß ist. Ob nun Kugel, Quader, ein Gemisch oder etwas völlig anderes angebracht ist, hängt von der Aufwandsbereitschaft, dem gewünschten Ergebnis und den konkreten Objekten ab, um die es geht. Es geht hier aber nunmal per se nicht um Dreiecke, sondern um Objekte in Spielen, die dann natürlich trianguliert gerendert werden. Jedes Dreieck dieser Triangulierung einzeln zu prüfen mag im LowPoly-Bereich noch funktionieren, legt dann aber selbst bei außerordentlich guter Implementierung schnell jedes Spiel lahm. Und um eine Kollisionsdetektion in einem Spiel geht es laut Fragesteller schließlich. Gute Programme berücksichtigen hier viele Faktoren. Bevor man überhaupt darüber nachdenkt, wie man Kollisionen prüft, sollte man sich übrigens auch fragen, für welche Objekte man dies überhaupt prüfen soll. Wer bei einem einzigen Gewehrschuss Überprüfungen für jedes Objekt in der ganzen Map durchführt, macht in der Regel etwas falsch. Ähnlich verhält es sich ja auch bei der Frage, wie man mit seinen Daten umgeht – als Beispiel nehme man Minecraft. Würde das Spiel jeden Block rendern, der innerhalb einer gewissen Sichtweite liegt, gingen die meisten Heimcomputer schon in die Knie. Stattdessen ignoriert man jeden Block, der keinen Kontakt zu einem Luftblock hat und schon spart man sich eine Fülle von Aufrufen an die Render-Engine. air |
||||
| 06.02.2012, 12:38 | riwe | Auf diesen Beitrag antworten » | ||
und ich wollte nur darauf hinweisen, dass eine approximation von dreiecken durch kugeln ziemlich problematisch sein könnte
was natürlich nix gegen kugeln sein soll. na dann haben wir halt "dasselbe" gemeint und uns gründlich mißverstanden
|
||||
| 06.02.2012, 18:50 | Airblader | Auf diesen Beitrag antworten » | ||
So sehe ich das auch.
air |
||||
| 10.02.2012, 13:53 | pd3 | Auf diesen Beitrag antworten » | ||
Meine Idee wäre jetzt, mit Umgebungskugeln um jedes Dreieck herauszufinden, ob sich zwei Dreiecke schneiden können, und wenn ja, genau nachsehen (wozu mir allerdings noch Formeln fehlen...). Ich könnte es auch nur mit Umgebungskugeln versuchen und schauen, ob es genau genug ist. |
||||
| 10.02.2012, 13:58 | Airblader | Auf diesen Beitrag antworten » | ||
Ich wiederhole es nochmal: Das exakte Überprüfen von Kollisionen wird jedes Spiel lahmlegen. Sowas findet nur bei Simulationen Anwendung, die nicht in Echtzeit ablaufen müssen (oder auf entsprechend guten Computern durchgeführt werden). Models in Spielen bestehen heutzutage in der Regel ja schon oft aus HighPoly-Strukturen mit vielen tausenden Dreiecken. Mit den Bounding Volumes bist du mehr als genug bedient, aber die beste Wahl für die umgebende Struktur hängt eben von deinen Objekten ab. Menschen lassen sich gut durch einzelne Hitboxes approximieren (für die Gliedmaßen) etc. air |
||||
| 11.02.2012, 21:43 | ph3 | Auf diesen Beitrag antworten » | ||
Okay ich habe die Lösung jetzt in meinem eingestaubten Exemplar von "3d Spiele programmieren mit DirectX und c++" von David Scherfgen gefunden. Ihr Ansatz ist, die Schnittlinie der Ebenen der beiden Dreiecke auszurechnen und dann zu prüfen, ob sich die Dreiecke auf ihr schneiden. Laut dem Verfasser kann die im Buch in c++ vorhandene Dreieckskollision auf einem AMD Athlon 1400, einem Prozessor aus dem Jahre 2002, mehrere Millionen Kollisionen pro Sekunde erkennen. Nehmen wir einmal an ein durchschnittlicher Smartphone Prozessor (wie z.b. mein htc desire mit 1.0 ghz) schafft hier nur eine knappe Million, so liegt die Zahl der maximalen Kollisionserkennungen pro Sekunde bei 30 fps bei etwa 30.000. Halbieren wir diese Zahl, damit andere Dinge (z.b. Rendern) auch noch stattfinden können, so erhalten wir 15.000. Hierbei ist noch nicht berücksichtigt, dass am Anfang mithilfe von Umgebungskugeln geprüft wird, ob die Objekte überhaupt kollidieren können, sprich, der Code wird nur aufgerufen, wenn eine Kollision (beinahe) stattfindet. Desweiteren bin ich nicht sehr talentiert im 3d- Modeling (sogar das ist eigentlich noch übertrieben), weswegen meine Modelle nicht sonderlich viele Polygone haben werden. Langes Gerede und kurz auf den Punkt gebracht: Ich denke schon, dass es performancemäßig machbar ist, wenn man auf ein paar Tricks zur Rettung der Rechenzeit zurückgreift. |
||||
| 11.02.2012, 22:31 | Airblader | Auf diesen Beitrag antworten » | ||
Ich habe ja gesagt, dass es im LowPoly-Bereich noch machbar wäre. Aber warum man ein Spiel als extrem-LowPoly konzipiert*, dann aber auf 100% exakte Kollisionsgenauigkeit besteht, mag mir irgendwie nicht in den Kopf gehen. Solche Fragen sollte man sich allerdings vor der Entwicklung stellen und letztlich ist das ja dein Bier. *) Und nebenbei ein problemloses späteres Aufstocken der Grafik somit schonmal verhindert air |
||||
|
|
