Moin,

habe mal eine Frage zur Kollisionsprüfung und damit meine ich nicht zu prüfen ob jemand gegen eine Wand läuft, sondern ob ein Objekt ein anderes trifft. Das Objekt ist hier eine Kugel, ihr Durchmesser wird außer beim Zeichnen einfach vernachlässigt.
Abgesehen von Lebewesen (kommt später noch, sollte man im Hinterkopf behalten) gibt es nichts weiter als simple Ebenen, welche einfache Quader sind. Wenn man auf diese eine Kugel ballert, soll das registriert werden. Intern hat eine Kugel die beiden Werte Richtung und Position. Die Kugel wird pro Frame ein Stück weiterbewegt, wobei der Betrag des Vektors der Kugel so angepasst ist, dass eine Addition der Position der Kugel mit dem Richtungs-Vektor die komplette Bewegung pro Frame durchführt.
Das heißt dass die Kugel nicht jeden Ort auf der Flugbahn besucht, da sie nicht lahm genug bewegt wird pro Frame, so dass das der Fall wäre. Also kann man nicht einfach sagen, okay ich prüf in jedem Frame ob die aktuelle Position eine Kollision darstellt, also in einer Menge von Kollisions-Werten enthalten ist. Außerdem klingt diese Idee nicht sehr performant, wenn sie möglich wäre. Man benötigt also andere Methoden. Ich schildere hier erstmal meine Überlegungen, ist sicher nicht alles Unfug:

• Möchte man prüfen ob die Kugel exakt einen Punkt nicht trifft, dann kann man bei jeder Bewegung der Kugel den Punkt A vor der Verschiebung der Kugel und den Punkt B nach der Verschiebung nehmen und dann zusammen mit dem zu überprüfenden Punkt P ein Dreieck aufspannen - falls der Punkt jedoch getroffen wird, gibt es kein Dreieck sondern eine Gerade oder anders: Wenn P der zu überprüfende Punkt ist, A Start- und B-Endpunkt der Verschiebung ist, dann wären die Vektoren AP und AB kollinear. Kollinearität lässt sich schön prüfen, denke wäre performant genug. Problem ist nur, dass man nicht nur einen Punkt überprüfen will, sondern eine Ebene eingeschränkt auf einen Bereich. Daher funktioniert dieses Verfahren eher nicht, aber finde es doch recht interessant, da Kollinearitätsprüfung überhaupt nicht rechenaufwendig und schwierig zu implementieren ist.
• Man könnte den Abstand der Kugel zum zu überprüfenden Objekt bei jeder Verschiebung pro Frame überprüfen und wenn der Abstand nicht mehr kleiner wird, muss man die Punkte zwischen dem Startpunkt A und Endpunkt B der Verschiebung genauer betrachten, falls die Distanz irgendwann 0 wird, wäre es ein Treffer, falls die Distanz auch da ab gewisser Rekursionstiefe nicht 0 wird, sondern wieder größer wird, wäre es kein Treffer. Das war aber nur so dahingesponnen, ich stelle es mir insgesamt recht umständlich und problematisch vor, kann mir unmöglich vorstellen dass das der richtige Weg ist.
• Da es hier um Ebenen geht (zwar "begrenzte", aber Prinzip ist das gleiche), ließe sich eine Ebenengleichung dieser aufstellen, der Normalenvektor bestimmen und wenn der Normalenvektor und der Richtungsvektor der Kugel senkrecht aufeinander stehen, also Skalarprodukt der beiden gleich 0 ist, dann wird der Vektor irgendwann die Ebene treffen. Nun könnte man ermitteln, wo dieser Schnittpunkt ist und wenn dieser im Bereich der begrenzten Ebene liegt, ist es eine Kollision, sonst nicht (zu beachten ist noch, dass der Schnittpunkt nicht hinter dem Abschusspunkt liegt, denn auch wenn man in den Himmel schießt hat man einen Schnittpunkt mit der Ebene, bloß ist dieser hinter einem und irrelevant). Aber wie ermittelt man den Schnittpunkt ? Ich habe im Grunde keine Informationen außer dass ich weiß wo meine Kugel ist, wohin sie fliegt, dass sie die Ebene trifft und die Ebene selbst.

Die letzte Variante scheint recht effizient zu sein. Man muss halt während den Verschiebungen immer prüfen ob es gekracht hat, das heißt ich kann nicht im Voraus den Schnittpunkt berechnen. Das ginge zwar bei den Ebenen selbst gut, aber bei beweglichen Objekten haut das nicht hin, da diese sich noch wegbewegen könnte.
Wenn ich nun ein menschenartiges Lebewesen reinlade, dann müsste ich dieses bei der Trefferüberprüfung wohl in eine verzerrte Kugel packen. Doch da kann ich die Überlegungen an Ebenen oben nicht mehr anwenden wenn ich mich nicht täusche. Man könnte natürlich das Modell des Spielers in einzelne Teile zerlegen und diese wären näherungsweise wieder Ebenen, aber das ist doch wohl kaum der richtige Weg ? Supereffizient klingt es jedenfalls nicht, außer man prüft bei jeder Schussbewegung, welcher Bereich des Gegnerkörpers in Frage kommt und unterteilt diesen immer weiter, bis man eine ausreichend genäherte Ebene hätte. Das müsste dann hinhauen, da pro Schritt immer große Teile aus der Betrachtung fallen.

Das sind meine Überlegungen dazu. Ich habe mir die Kollisions-Tutorials hier angeschaut und auch den Quellcode von quelloffenen Ballerspielen. Doch so recht zum Ziel komme ich mit dem Wissen noch nicht. Ist die dritte Variante eine gute Idee und wenn ja, wie berechne ich den Schnittpunkt effektiv (meine Kenntnisse auf dem Gebiet würden zu einem Gleichungssystem führen, das wäre sicher nicht optimal). Gibt es abgesehen von diesen Überlegungen noch weitere sinnvolle Verfahren ?

Gruß,
Nils

_________________
Meine Musik: spiker-music.net

Mit dem letzten bist du schon einmal auf dem richtigen Weg. Deine Normalen konstruierst dabei so das sie stehts nach außen zeigen. Ist das Punktprodukt aus Normale und deinen Punkt für alle Ebenen <= 0 dann liegt der Punkt im Objekt. Bei einen Strahl trifft das zu wenn der Schnittpunkt T mit den Ebenen für Tnah kleiner als Tfern ist.

Dies gilt für alle Polyeder.

_________________
Meine Homepage

Schau dir mal CoolMath an. Die Klasse Plane hat eine Methode rayIntersect.

Was du aber wahrscheinlich willst ist nicht Ebene/Strahl sondern ein Test für Dreieck/Strahl. Das ist etwas komplexer, das Problem sind eben die Spezialfälle. Als ich das damals brauchte hatte ich mir was aus dem Internet zusammengesucht. Das folgende ist relativ flott, geht aber sicher effizienter.

_________________
Yeah!

Wenn ich das richtig gelsesn habe, dann willst du eine solide kollisions erkennung der kuhel und die kann man über eine entsprechend hohe abtastfrequenz erreichen.
In physiksystemen wird eigentlich die höchste geschwindigkeit genommen, die möglich sein soll, erfasst das kleinst mögliche objekt und berechnet die frequenz daraus, bei der noch eine kollision erfasst werden würde.
Die physik läuft genau aus diesem grund sehr selten mit der gleichen frequenz, wie der renderer.

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

Projekte: https://github.com/tak2004

dann reicht es also wenn



hach ich liebe es wenn dinge einfacher werden

_________________
Meine Homepage

Früher, wo noch die CPU ein Bottleneck war, hat man Sonderbehandlungen gehabt.
Ich habe ein paar mal gelesen, dass einige Physiksysteme dynamische Abtastfrequenzen für einzelne Objekte verwendet haben.
Sehr schnelle Objekte haben dann innerhalb eines Update mehrere Updates gemacht.
Dies sorgt aber für instabile Simulationen, da ja die anderen Objekte nicht mit der gleichen Frequenz abgetastet wurden und Kollisionen unter den dynamischen Objekten aus bleiben konnten.
Ein weiterer hack sind raycasts, die zwischen den aktuellen und der nächsten position geschossen werden, hat das gleiche Problem wie der Hack zuvor.
Noch ein hack ist das raycasten, abhängig von der Geschwindigkeit, in die Umgebung und das prüfen, ob der erste Treffer innerhalb des Tolleranzbereiches liegt. Sowas sollte man heute eigentlich nur noch für die AI machen, da es bei zu spitzen Winkeln versagt(muss da leider aus Persönlicher Erfahrung sprechen :\ ).

Seit vielen Jahren langweilen sich die CPU's und man tendiert zu stabilen Physiksystemen, die einfach und möglichst keine Ausnahmenbehandlung machen. Also werden einfach alle Objekte mit höherer frequenz simuliert. Das Spiele mehrere hundert bis tausend Hz für die Physik haben ist je nach Gengre üblich. Damit hat sich das design von CPU auf Speicher optimierung umgestellt.

Ganz wichtig, der Input sollte nie Zufällig sein, also kein echtes Random, sondern eher sowas, mit fixen Seed. Dann hat man weniger sorgen, wenn man Physikabhängige Bugs sucht(auch eine Erfahrung, die ich gemacht hab).

1x1, der Optimierung, für eigene Physik :
-Software optimierungen
-Sphere-Sphere intersection sollte immer der erste Test sein(der schnellst mögliche Test)
-weitere Tests sind Objektspezifisch, z.B. Box, Plane
-verwenden von Spatial systems(z.B. Octree um die Anzahl der Tests zu reduzieren)
-Hardware optimierungen
-Parallel processing(SIMD, Threads)
-data driven design(ist einfacher und bringt mehr als alle anderen optimierungen)
-batching(dynamics, kollision, korrektur sollte nicht von den Objekten gemacht werden sondern von der physik -> Cache friendly und weniger function calls)

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

Projekte: https://github.com/tak2004

Die Dreiecksüberprüfung gibt mir doch jederzeit an, ob es eine Kollision gibt, egal wie weit ich weg bin ? Ich habe hier eine Umsetzung des Dreiecks-Algos in "algebraischer" Variante gefunden (weil derjenige in dem Forum da schrieb, er ersetze die "algebraische" durch die gezeigte). Weil ich mich erstmal etwas näher wohl auch mit der Syntax des obigen Codes auseinandersetzen müsste, wollte ich vorher erstmal schnell die "algebraische" Variante umsetzen, um einfach mal zu schauen was passiert. Ich habe mir ein Dreieck konstruiert, was wortwörtlich nicht zu verfehlen ist, die Überprüfung sagt mir dann, dass es einen Treffer gibt. Die Distanz habe ich mir ausgeben lassen und sie geht irgendwann gegen 0, erreicht jedoch nicht exakt 0, was etwas seltsam ist, scheint ein Rundungsfehler zu sein, oder das Dreieck ist seltsam platziert. Dreieck konstruiert heißt hier einfach, dass es der Dreiecks-Kollisionsüberprüfung übergeben wurde, mehr nicht. (Algebraisch deshalb überall in Anführungsstrichen, weil alle Methoden im Endeffekt mit algebraischen Mitteln gelöst werden mit geometrischem Hintergedanken.) Die Idee mit den Dreiecken ist, dass sich ein Modell gut in Dreiecke zerlegen lässt und das Verfahren daher allgemein gut anwendbar ist, sehe ich das richtig ?

Die andere Sache mit der hohen Frequenz: Wenn die Kiste eines Benutzers zu lahm ist, wie äußert sich das dann ? Ruckelt es nur oder versagt dann die Kollisionsabfrage ?

Und damit ganz klar ist, was Sache ist: Das Ziel ist, dass jemand korrekt schießen kann, also die Kugeln nicht durch Ebenen hindurchfliegen und Gegner sollen getroffen werden können - ausreichend genau, ist immer doof wenn jemand oder etwas (Gegenstände) getroffen wird obwohl er/es nicht getroffen wurde und ist genauso doof wenn einer getroffen wird, aber nicht getroffen wird im Spiel (gut für ihn, doof für den anderen).

_________________
Meine Musik: spiker-music.net

Es ruckelt, weil ja die CPU weder Physik noch Renderer ausreichend schnell ausführen kann.

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

Projekte: https://github.com/tak2004

Ich verschiebe derzeit durch Vektoraddition die Kugel immer weiter und prüfe ob es einen Treffer gibt. Das ganze läuft außerhalb des Rendervorgangs, eben um eine erhöhte Genauigkeit zu erzielen. Das Problem ist jedoch, dass die Werte nie gerade sind, ich habe immer hässlich krumme reelle Zahlen und muss die Toleranzen so ausdehnen, dass insgesamt die Kugeln oft korrekt als Treffer interpretiert werden, jedoch dann wegen der Toleranzen nicht ohne zusätzlichen Aufwand an die richtige Stelle geschoben werden können. Was ich aber positiv finde: Je größer der Abstand, desto größer der Fehler. Das heißt je weiter der Schütze wegsteht desto mehr schießt er daneben - das ist in der Tat ein schöner Nebeneffekt, den ich sonst anders einbauen müsste.
Aber zurück zum Problem: Ich müsste mir ausdenken, wie ich den Vektor auf den aktuellen Punkt addieren könnte um möglichst genaue Werte zum Überprüfen zu erhalten, denn ich sollte die Genauigkeit nicht erhöhen, bei Dauerfeuer packt das mein i7, auch ein Dual-Core kommt damit aus - hatte es mal erhöht und es fing an leicht Ärger zu geben. Genauere Tests muss ich noch durchführen, aber rein von der Performance her wäre es so aktuell wohl in Ordnung, wenn ich jedoch die Genauigkeit in einen tragbaren Bereich runterkriege. Derzeit verteilen sich die Kugeln etwas ungünstig im Raum, ich habe sie testweise einfach angehalten, sobald sie angeblich den Boden berühren, sieht man dann meist sehr deutlich, dass sie nicht vernachlässigbare Höhenunterschiede haben. Meine Frage hier ist daher: Gibt es da irgendwelche Tricks, die Zahlen möglichst genau zu kriegen ? Ich habe halt einen beliebigen Richtungsvektor und wenn ich mit dem von einem Punkt weggehe, kommen zu ungenaue Zahlen raus.


Welchen Punkt meinst Du ? Die einzigen Punkte die ich habe sind der Start- und Endpunkt des Kugel-Vektors.

_________________
Meine Musik: spiker-music.net

Das ist lediglich die Grundlage für die Intersectiontests. Willst du das ganze für einen Strahl von Punkt A nach Punkt B umstellen dann:

_________________
Meine Homepage

Was für einen Abstand stellt planes[i].dist dar ?

_________________
Meine Musik: spiker-music.net

Die Ebene ist schlicht und einfach in der Normalform.
dist = Normal * (Zero - PlanePoint) = - Normal * PlanePoint

_________________
Meine Homepage

Hm und welchen Punkt stellt PlanePoint dann dar ? Ich zerbreche mir darüber schon lange den Kopf, habe vermutlich nur ein Brett vorm Kopf, weil eigentlich denke ich müsste es offensichtlich sein, was das für ein Punkt ist.

_________________
Meine Musik: spiker-music.net

PlanePoint ist ein Ortsvektor der Ebene. Hier mal ein vollständiger Konstruktor für eine Ebene aus 3 Punkten.

_________________
Meine Homepage