Hallo!

Weis jemand von euch, wie man zwei konkave Polygone in 2D auf eine Kollision hin testen kann? Ich hab schon google bemüht usw. aber nicht wirklich was gefunden... *helpless*

Danke, ihr seid meine Rettung!

thx, cu, MfG the_viking

(( My =]=H=O=M=E=> Page! ))
Coder bei Brainshock-Interactive und bei Z-Software
My ICQ: #160959446

Schau in dein Tafelwerk. Da sollte drinn stehen wie man berechnet ob ein Vektor eine Fläche schneidet. Wenn das passiert ist es schon zu spät, also sind die zwei Polygone ein Frame (oder so) vorher kollidiert. Das wäre mein Ansatz, in deine Programmier, welche auch immer, musst du es selbst kriegen.
Was soll das eigentlich mit konkanve Polys? Für gewöhnlich arbeitet man jedes Triangle einzeln ab und diese sind bekanntlich so flach wie eine Flunder.

Die Lösung aller Eurer Probleme:
||Die Liste aller Compilier Fehler.|Der ultimative Compile Log Anaylizer||
||How to: Fragen stellen.||
||Sieben Wege LEAKs zu finden.||
||Die letzten wirklich bug-freien Compiler (Juli)||

Wieso ist es dann schon zu spät? Ich würde sagen, wenn ein Vektor eine Fläche schneidet wird der Punkt im nächsten Frame innerhalb der Fläche liegen.

Matze

BattleTech-MOD:
http://bthl.unitedgaming.net/

Wenn man die Kanten der Fläche als Vektoren betrachtet und diese dann die andere Fläche schneiden, passierte die wirkliche Kollsion etwa ein Frame vorher. Ist doch logisch. Denn in dem Moment in dem sie die Fläche schneiden, passiert das was man verhindern will, nämlich dass sie nicht kollidieren.

Die Lösung aller Eurer Probleme:
||Die Liste aller Compilier Fehler.|Der ultimative Compile Log Anaylizer||
||How to: Fragen stellen.||
||Sieben Wege LEAKs zu finden.||
||Die letzten wirklich bug-freien Compiler (Juli)||

Du betrachtest die Kanten als Vektoren? Ich betrachte den Richtungsvektor jedes einzelnen Punktes als Vektor, der dann auf Kollision getestet wird. Das geht natürlich nur bei sich bewegenden Objekten.

BattleTech-MOD:
http://bthl.unitedgaming.net/

Ah, daher rührt das Missverständnis. Deine Methode funzt anders als meine. Ich überprüfe ob die poly ineinander stecken, du hingegen schaust nach ob das passieren würde. Der Nachteil bei deiner Methode ist, dass nur dann eine kollision festgestellt wird wenn auch einer der Punkte das Tri erwischt. Wenn alle daran vorbei gehen können die Kante aber immer das Tri schneiden.

Die Lösung aller Eurer Probleme:
||Die Liste aller Compilier Fehler.|Der ultimative Compile Log Anaylizer||
||How to: Fragen stellen.||
||Sieben Wege LEAKs zu finden.||
||Die letzten wirklich bug-freien Compiler (Juli)||

Wenn du den Schnitt von zwei konkaven Polygonen berechnen willst, funktioniert das folgendermaßen: Du nimmst je Kante beider Polygone und testet ob sie sich schneiden. Das machst du mit allen Kantenpaaren. Falls es kein Paar von Kanten gibt welche sich schneiden, so kollidieren die Polygone nicht.

www.d3opencoop.com - A Doom3 Cooperative Mod

Nee. Es müssen sich doch nicht unbedingt die Kanten untereinander schneiden. Es kann auch sein, dass die Kanten einfach durch die Mitte des anderen Poly durchgehen.

Die Lösung aller Eurer Probleme:
||Die Liste aller Compilier Fehler.|Der ultimative Compile Log Anaylizer||
||How to: Fragen stellen.||
||Sieben Wege LEAKs zu finden.||
||Die letzten wirklich bug-freien Compiler (Juli)||

wenns durch die mitte geht, gehts auch durch ein kantenpaar.

\o tanz den naziprau! o/

And more than ever, I hope to never fall,
Where enough is not the same it was before

Nein! Wie kommts du denn auf die Idee? Ich versuch's mal anschaulich.
Man nehme zwei CD-Hüllen. Nun stellt man die eine mit einer Ecke senkrecht auf die andere. Jetzt stellt man sich vor dass die aufgestellte Hülle noch ein wenig in die andere hinein rutscht. Und dann sage mir bitte wo sich die Kanten der Hüllen berühren.

Mist, ich hab versuch das mit ASCII darzustellen aber ThW löscht die Leerzeichen.

Die Lösung aller Eurer Probleme:
||Die Liste aller Compilier Fehler.|Der ultimative Compile Log Anaylizer||
||How to: Fragen stellen.||
||Sieben Wege LEAKs zu finden.||
||Die letzten wirklich bug-freien Compiler (Juli)||

Mensch, macht mal einer ne Zeichnung, ich kann mir immer noch nicht so recht 2 konkave polygone in 2D vostellen, meinste so Halbmonde oder ähnliches?

Sig as a brick ┴┬┴┬┴┬┴┬┴┬┴┬┴
WW

Ich schätze mal, dass der Autor uns sein Problem nicht mehr erläutern wird, da er letztes Jahr diesen Thread erstellte. Belassen wir es dabei.

Die Lösung aller Eurer Probleme:
||Die Liste aller Compilier Fehler.|Der ultimative Compile Log Anaylizer||
||How to: Fragen stellen.||
||Sieben Wege LEAKs zu finden.||
||Die letzten wirklich bug-freien Compiler (Juli)||

http://marvin.sn.schule.de/~inftreff/modul8/bild1.gif
Bild 1: Ebenes n-Eck
(a) konvex, (b) konkav

Google, Warewolf :P

Was die Zahnarzt meint ist eine 3D kollision von 2 2D Polies, aber das wird glaubich nicht der Fall sein.

"[...] you're going to burn in a very special level of Hell. A level they reserve for child molesters and people who talk at the theater." - Book

Ok, ich hatte einen Fall übersehen. Ein Polygon kann die Teilmenge eines Anderen sein. Dann halt anders. Du testet für jeden Eckpunkt eines der Polygone ob er in dem Anderen liegt oder draußen.

Das kannst du folgendermaßen machen: Mt dem Punkt konstruierst du parallel zu Koordinatenachse eine Halbeachse. Dann zählst du die Schnitte dieser Halbachse mit dem anderen Polygon. Ist die Anzahl der Schnitte ungerade, so liegt der Punkt drinnen. Ist sie gerade, so liegt der Punkt draußen. Das machst du für jeden Punkt und entscheidest somit, ob sich die Polygone schneiden.

www.d3opencoop.com - A Doom3 Cooperative Mod

@khan: Stimmt ich meinte 3d Kollision.
Allerdings ist das mit der 2d Kollision auch nicht so einfach, von wegen Punkte drinnen oder nicht. Angenommen zwei recht spitze Ecken der Polys "stechen" genau durch das andere durch, dann liegen alle Punkte draußen und trotzdem kollidieren sie. Ich hab jetzt nicht die Zeit ein Bild zu suchen oder selbstzumalen. Eventuell morgen, falls nicht klar ist was ich meine. Jedenfalls kommt man um die Kanten-Schnittberechnung nicht herum.

Die Lösung aller Eurer Probleme:
||Die Liste aller Compilier Fehler.|Der ultimative Compile Log Anaylizer||
||How to: Fragen stellen.||
||Sieben Wege LEAKs zu finden.||
||Die letzten wirklich bug-freien Compiler (Juli)||

Ich hab nochmal drüber nachgedacht. Am besten ist es wenn man, wie mazze meinte, die Geschwindigkeitsvektoren jedes einzelnen Punktes betrachtet. Wenn mindestens einer dieser Vektoren einen der anderen Fläche (Kante oder Geschwindigkeit) schneidet, so werden sie kollidieren. Mit dieser Methode schließt man auch Fehler bei niedrigen Framerates aus. Bei 3d Kollision müsste man für jede Kante eine "Geschwindigkeitsfläche" betrachtet. Zwischen der aktuellen Position der Kante und der des nächsten Frames entsteht eine, eventuell aus zwei Dreiecken bestehende Fläche. Wenn ein Vektor eines Polys irgendeine Fläche des anderen schneidet, findet eine Kollision statt.
Ich beschäftige mich nicht oft mit sowas, deshalb wäre es nett, wenn jemand der davon viel Ahnung hat mal erklärt wie es denn nun tatsächlich in Spielen und so gemacht wird.

Die Lösung aller Eurer Probleme:
||Die Liste aller Compilier Fehler.|Der ultimative Compile Log Anaylizer||
||How to: Fragen stellen.||
||Sieben Wege LEAKs zu finden.||
||Die letzten wirklich bug-freien Compiler (Juli)||

Soso...jetzt hab ich doch recht :p

Da gibts doch sicher massenweise tutorials auf diversen gamedev seiten.

Matze

BattleTech-MOD:
http://bthl.unitedgaming.net/

Hattest du vorher auch, wenn man davon ausgeht dass 2d kollidiert wird. Ich dachte nur, dass meine Methode ein ebenso zuverlässiges Ergebnis bringt wie deine.
Wegen den Tuts: Ich brauch's nicht wirklich, ich wollt's nur mal so aus Interesse wissen. :)

Die Lösung aller Eurer Probleme:
||Die Liste aller Compilier Fehler.|Der ultimative Compile Log Anaylizer||
||How to: Fragen stellen.||
||Sieben Wege LEAKs zu finden.||
||Die letzten wirklich bug-freien Compiler (Juli)||

Ach ja, und was machst du wenn ein Polygon das Andere komplett umschließt, so das sich gar keine Kanten überschneiden ?

www.d3opencoop.com - A Doom3 Cooperative Mod

..dann hat die Kollision sicherlich vorher schon stattgefunden...und wurde erkannt.

Sig as a brick ┴┬┴┬┴┬┴┬┴┬┴┬┴
WW

Es war nie von sich bewegenden Polygonen die Rede...

www.d3opencoop.com - A Doom3 Cooperative Mod

Ich hab schon vor 16 Posts gesagt, dass das nur bei sich bewegenden Objekten funktioniert...

Wir wissen nicht, ob sich die Objekte bewegen, da die Frage uralt ist.

cu

BattleTech-MOD:
http://bthl.unitedgaming.net/

Zitat:

WareWolf postete
..dann hat die Kollision sicherlich vorher schon stattgefunden...und wurde erkannt.

Das musst du mir jetzt aber aufzeichnen...

cu

BattleTech-MOD:
http://bthl.unitedgaming.net/

Ich habe mir über solche Probleme leider noch nie wirklich ernsthaft den Kopf zerbrochen. Aber so spontan würde ich einen Lösungsansatz vorschlagen, der dem Rasterizing beim Rendern von Polygonen entlehnt ist.

Dazu werden zunächst die Punkte beider Polygone, und die mit ihnen verbundenen Kanten, in eine gemeinsame Liste geschrieben und entlang einer Koordinatenachse (sagen wir z.B. entlang der Y-Achse) sortiert.

Dann gehen wir diese Liste Punkt für Punkt durch, wobei wir jederzeit eine Liste der "aktiven Kanten" im Speicher behalten.

Die Liste der aktiven Kanten ist einfach die Liste aller Kanten, die man erhält, wenn man eine Gerade y = n (d.h. eine Horizontale) legt und alle Kanten aufzählt, die sie schneidet.

Es ist sinnvoll, auch die Liste der aktiven Kanten sortiert zu lassen - natürlich entlang der anderen Achse (X-Achse).
Dann ergibt sich nämlich eine interessante Eigenschaft dieser Liste. Die Kanten in der Liste können paarweise betrachtet werden [3]. Zwischen den einzelnen Kanten solcher Paare befindet sich der von einem Polygon ausgefüllte Raum. Zwischen den Kantenpaaren befindet sich dagegen leerer Raum. [1]
Gewissermassen bildet jedes Kantenpaar auf einem infinitesimal kleinen vertikalen Abschnitt ein Trapez.

Jedes Mal, wenn wir einen Punkt abarbeiten, ergeben sich drei "Aktionsmöglichkeiten": [2]
1. Zwei neue Kanten werden eingefügt (die obere Spitze eines Polygons)
2. Zwei bestehende Kanten werden entfernt (die untere Spitze eines Polygons)
3. Eine Kante wird durch eine andere ersetzt

Der eigentliche Kollisionscheck erfolgt nur in den Fällen 1 und 3. In diesen Fällen werden neue Kanten eingefügt, und muss die Sortierung der Liste der aktiven Kanten aufrecht erhalten werden.

Nun sollte beim Sortieren sowohl der Anfangs- als auch der Endpunkt der beteiligten Kanten berücksichtigt werden.

Wenn beide Punkte jeder Kante berücksichtigt werden, so ist es nicht immer eindeutig möglich, eine Kante vor eine andere Kante zu sortieren. Genau in diesem Fall der Unentscheidbarkeit schneiden sich die Kanten, und eine Kollision zwischen den Polygonen liegt vor.

Ein beliebter Problemfall von Kollisionsalgorithmen ist der, dass eins der Polygone vollständig im anderen enthalten ist. Auch mein bisher gezeigter Algorithmus kommt mit diesem Fall noch nicht zurecht.

Es gibt nun zwei Möglichkeiten:
1. Polygone mit Löchern werden nicht unterstützt.
Mit einem kurzem Blick auf [1] wird klar, dass eine Kollision vorliegt, wenn ein Punkt zwei neue Kanten einfügen würde, die ein bestehendes Kantenpaar auftrennen.

2. Polygone mit Löchern werden unterstützt.
In diesem Fall wäre mein Lösungsvorschlag, jeder Kante ein zusätzliches Flag mitzugeben. Dieses Flag zeigt an, ob eine Kante "nach links gerichtet", oder "nach rechts gerichtet" ist. Nach links gerichtet bedeutet dabei, dass sich unmittelbar links von der Kante leerer Raum befindet, während der Raum unmittelbar rechts von der Kante ein Teil des Polygons ist.

Ein Kantenpaar in der Liste der aktiven Kanten muss dann immer aus einer nach links, und einer nach rechts gerichteten Kante bestehen.

Sobald diese Regel verletzt wird, liegt eine Kollision vor.

Damit müssten alle Fälle abgedeckt sein. Allerdings habe ich diesen Algorithmus noch nie gesehen und noch nie ausprobiert. Deshalb ist eine Prise Salz hiermit Bestandteil des Lieferumfangs.

cu,
Prefect

[1] Diese Eigenschaft einer sortierten Kantenliste ist auch dann gültig, wenn Polygone Löcher enthalten. Allerdings können Kantenpaare in diesem Fall durch Punkte aufgeteilt und neu zusammengefügt werden.

[2] Ein etwas unangenehmer Sonderfall sind in meinem Algorithmus leider horizontale Kanten.
Mein Vorschlag zu deren Lösung: Horizontale Kanten werden verworfen; beim Erstellen der Liste aller Punkte wird der Begriff "Punkt" nicht allzu eng vom euklidschen Begriff des "Punktes" abhängig gemacht, und die beiden Endpunkte der horizontalen Kante werden zu einem einzigen Punkt vereint.

[3] Die Positionen der Paare sind fest. Das heißt, die aktive Kante an Position 0 in der Liste bildet ein Paar mit aktiver Kante 1; aktive Kante 2 bildet ein Paar mit aktiver Kante 3. Im Gegensatz dazu bilden die Kanten 1 und 2 *kein* Kantenpaar.

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.