Kollisionsprüfung ohne hitTest

[Samuel]

Im Grunde richtet sich die Frage an André, weil ich sein Vortrag über Physik gesehen habe. das ganze Zeug mit Intersection und Ressolvers.
Was ich mich aber gefragt habe, da ich ein workaholic bin , ist die Methode wie er simple mathematische Objekte auf Kollision prüft.
Mathematisch beschrieben ist das äußerst simpel, man sucht sich bei nem Viereck einfach die Koordinaten plus Breite und Höhe und schon hat man die Menge der Punkte am Rand und innen, bei anderen Figuren gehts genauso, nur n wenig komplexer.
Gut aber wie prüft man nun auf Kollision und wird nur der Rand geprüft, oder das komplette Objekte (im Grunde macht komplettes Objekt einen Sinn wenn man vorher das tunneln abgefangen hat)
Aber egal, im Grunde gilt keine Kollision von zwei Objekten, wenn {Menge der Punkte von Objekt A} geschnitten mit {Menge der Punkte von Objekt B} = {} ergibt, also eine leere Menge, das ist jedoch in der Umsetzung n Heidenaufwand, denke ich mir, weil man ja im Grunde jeden Pixel mit jedem gegnen prüfen will.
Mit den Inhalten gibts ne Menge punkte und ohne eigentlich auch.
Wird das praktisch so gelöst? Nach dem das tunneln ausgeschlossen wird?
Ich will hier im Grunde kein Code, nur n bisschen darüber diskutieren.

(Warum fragst du ihn nicht selbst zieht nicht, hab ich schon )

[hgseib]

da dir André offensichtlich nicht geantwortet hat .. keine zeit oder so ...?
erlaube ich mir, in diese diskussion einzusteigen. ich kenne die veröffentlichten programme von André bezüglich rigidbody. auch wenn ich mir den code aus zeitgründen (bzw. bisher noch nicht benötigt) nicht angesehen habe.
da geht es immer um konvexe polygone. somit im kern 'nur' um den schnittpunkt linie-line.
der kollisionspunkt sich bewegender polygone wird z.b. iterativ angenähert.
komprexere geometrien wären in konvexe polygone aufzuteilen.

andere methode einen punkt in einer fläche zu testen ist mit dem kreuzpodukt.

[Samuel]

Ich mein dieses Ding: http://lab.andre-michelle.com/physics-engine
Das mit konvexen Polygonen ist klar, aber ich mein allgemein, wie prüft man ein mathematisch beschriebenes Modell, kreis, rechteck oder sonst was auf Kollision?
Die Annäherung ist ja, wie dort beschrieben nicht prüfen auf intersection sondern detectionaber wie wird dann die Kollision festgestellt? Durchläuft man die Randlinien von jedem möglichen Kollisionsobjekt?


(Notiz an mich: Wenn das geklärt ist, noch etwas bezüglich den Unterteilungen der Annäherung fragen ) <- ignoriert das erstmal

[hgseib]

erweitere linie-linie um linie-kreis

"..Durchläuft man die Randlinien von jedem möglichen Kollisionsobjekt?.."
da der computer sich das szenario nicht ansehen kann um mögliche kollisionen vorraus zu ahnen, sondern stur nach schema-F arbeiten muss: immer schön alle kanten miteinander testen

mir ist nicht bekannt, das es dafür eine gesamtlösung gibt, so wie z.b. bei FEM alles in eine matrix reinpacken.

bin jetzt aber nicht der ganz grosse 'wisser' zu diesem thema ;-) da sich die objekte zu jeder zeit gegenseitig beeinflussen können wird's keine mathematik geben, die eine exakte kollision berechnen kann? aber es wird 10.000 tricks geben, den rechenaufwand zu minimieren (dafür kann man sich dann alle möglichen bezeichnungen für ausdenken ;-)

[Samuel]

Daher hab ich ja auch André gefragt, naja er antwortet noch bestimmt

[double-stroke]

Hallo,

ich bin auch nicht André, habe diese Diskussion verfolgt und nun, nach einigen Monaten selbst Lösungen gefunden. Ich habe vor längerer Zeit mal ein Billard gemacht und das komplett überarbeitet. Tunneln ist nicht mehr möglich, somit hohe geschwindigkeiten, korrektes "herausziehen" von Objekten aus Hindernissen, sodaß es zu keinen Verspringern kommt, usw...

Die Mathematik wurde schnell recht komplex, und um sie in den Griff zu bekommen (bei 10 Kugeln, 18 Wänden, 12 Ecken und 6 Löchern, also eigentlich 400 Prüfugnen pro Frame) habe ich mir was einfallen lassen müssen. Die Lösung sieht so aus. Die Kugeln untereinander werden nur dann geprüft, wenn der x- und der y-Abstand jeweils kleiner als die Maximalgeschwindigkeit plus dem Radius ist. Der Tisch wurde weiterhin in Zonen aufgeteilt. Jede Zone ist ein Array und enthält alle Objekte, die in ihr relevant sind. Jede Kugel durchläuft also erst mal den "zonenfinder()" und arbeitet dann die potenziallen Hindernisse dieser Zone ab. Die Zonen in den Ecken enthalten nur noch 4 Linien, 2 Ecken und 1 Loch; die Zonen an den Rändern nur 1 Linie und die Zonen in der Mitte enthalten nichts. Dadurch konnte ich die Berechnungen pro Ball auf durchschnittlich 1,7 (plus zonenfinder, der aber einfach ist, nur > oder < als x und y) reduzieren, selten kommt es zu mehr als 20 Prüfungen pro Frame. das klappt (fast) immer, sodaß ich mir sogar den Zeit-Multiplikator auf den Vektoren sparen konnte.

Probiers mal aus:

www.dazine.de/Solid.html

Wenn Du näheres wissen willst, kein Problem. Ich plane daraus mglicherweise ein Tutorial zu machen. Mal sehen. Tutorials zu den alten Versionen, in denen ich eine ähnliche Technik verwendet hatte, findest Du auf meiner Website ebenfalls (nur www.dazine.de).

Bis dann
Dirk

[Samuel]

Danke für die Info, auch wenn es zuspät ist, die Engine ist ist seit Februar fertig, kein Tunneln. 30 Frames auf nem alten Notebook und der Rest funzt gut.
Ich hab keine Ahnung wie gut deine Kollisionsprüfung wäre, wenn du Gravitation hättest, so wie ich. Da ich einen Boden haben, wäre hier eine pausenlose Kollision eingetreten, was uns kopfschmerzen bereitet hat, aber dass ist wie gesagt passé