Kollisionstest Dreieck-Strahl
-
Hallo,
ich hab gerade folgendes Problem, und hoffe jemand hat eine Idee dazu:
Es geht um den quasi einfachsten Fall einer Collisions- oder besser Trefferabfrage, Dreieck-Strahl.
Mein Problem ist nun ein Grenzfall der theoretisch eintreten kann und leider auch eintritt. Teilen sich zwei Dreiecke zwei Vertices und man trifft GENAU die Kante werden bei meinem Algorithmus, je nach Implementierung, beide Dreiecke (<)oder keins (<=) getroffen.
Meine Frage wäre jetzt, ob sich das irgendwie geschickt vermeiden läßt, oder ob evtl. Algortihmen verfügbar sind, die direkt den ganzen Körper testen (mir genügt die Anzahl und die Position der Treffer auf dem Strahl).Viele Grüße,
connan.
p.s. Ich hab zwar schon einige Ideen dazu, denk aber wohl schon zu lange darüber nach
-
Teilen sich zwei Dreiecke zwei Vertices und man trifft GENAU die Kante werden bei meinem Algorithmus [...] beide Dreiecke getroffen
das ist auch korrekt. warum ist das denn ein problem fuer dich?
so aus der huefte geschossen koenntest du die gemeinsame kante genau einem dreieck zuordnen, indem das andere dreieck beim intersection-test die nicht-gemeinsamen kanten als basis-vektoren benutzt.
-
hellihjb schrieb:
warum ist das denn ein problem fuer dich?
Nun, es geht um dieses Projekt:http://www.c-plusplus.net/forum/viewtopic-var-t-is-191889-and-start-is-40.html(dritt letzter post, nicht das Spiel
)
Dabei ist entscheidend, daß jeder Strahl ein Objekt exakt 2-mal oder keinmal trifft.hellihjb schrieb:
so aus der huefte geschossen koenntest du die gemeinsame kante genau einem dreieck zuordnen, indem das andere dreieck beim intersection-test die nicht-gemeinsamen kanten als basis-vektoren benutzt.
Ich denke auch, daß das die beste Variante wäre so ne art 'Ganzkörpertest'. Nur wenn ich da genau drüber nachdenke wirds unendlich kompliziert. Wenn ich mir einen Körper vorstelle und wie ich dann durch die dreiecke iterieren müsste um...da hörts bei mir auf
Außerdem werden die Dreiecke rendundand gespeichert (1 Dreick = 3 Punkte) wodurch die Prüfung auf gemeinsame Kanten recht hässlich wird.
Was mir noch einfiele ist, daß ja die Position der Treffer auf dem Strahl für beide Dreiecke die selbe ist somit könnte ich wohl einfach einen von beiden Treffern löschen..
-
Ich würde es so machen: Kante gehört dazu (damit in diesem seltenen Spezialfall kein Problem entsteht). Wenn Hits auftreten, überprüfen, ob diese zum selben Objekt gehören (da gibt es verschiedene Methoden).
-
wolfgke schrieb:
Ich würde es so machen: Kante gehört dazu (damit in diesem seltenen Spezialfall kein Problem entsteht). Wenn Hits auftreten, überprüfen, ob diese zum selben Objekt gehören (da gibt es verschiedene Methoden).
Und genau da tritt mein Prolem auf: In deinem Bsp. wäre für ein (konvexes) Objekt auch eine Trefferzahl von 3 o. 4 (im Extremfall bis zu 6) möglich und genau dass darf nicht sein, ein (konvexes) Objekt kann von einem Strahl nur 2 mal oder nie an der OF geschnitten werden.
-
connan schrieb:
ein (konvexes) Objekt kann von einem Strahl nur 2 mal oder nie an der OF geschnitten werden.
um genauer zu sein, einmal eine vorderseite, einmal eine rueckseite.
das ist auch schon die loesung deines problems.;)[edit]
wobei, eigentlich, wenn es einen treffer gibt, gibt es doch automatisch einen zweiten, esseiden der punkt ist innerhalb. doch der test dafuer waere ja viel trivialer bei convexen gebilden.
-
Es wäre schön, wenn das so wäre. Jedoch kann zumindest bei numerisch schlechter Implementierung des Kollisions-Algorithmus es durchaus auch auftreten, dass von der einen Seite (Orientierung) eine Kollision am Rand auftritt und der anderen nicht.
Es gibt zwar recht einfache Tricks, um ein solches Szenario zu vermeiden (die gute Programmierer intuitiv verwenden), aber alleine ein Codeaudit durchzuführen, ob der Code tatsächlich diese Bedingung erfüllt, ist nicht spaßig.
Das Hauptproblem besteht darin, dass die üblichen Gleitkommaoperationen (+,
nicht assoziativ (und nebenbei nicht distributiv - das spielt hier aber keine Rolle) sind. Jedoch Kommutativität kann man voraussetzen.Beispiel:
((a-b)+b) muss, wenn man es als Gleitkommaoperation implementiert, nicht gleich a (=(a+(-b+b), wie man es nach Assoziativität erwarten würde).
Ebenso muss (Assoziativität und Kommutativität mehrfach anwenden!) nicht
((a-b)+b)==((a+b)-b)
gelten.Jetzt stelle man sich vor, b ist eine Komponente des Verbindungsvektors zwischen 2 Dreicksvertices. Bei umgekehrter Orientierung ist diese selbstverständlich -b.
Wenn der Gleitkommacode aber die Operation ((a-b)+b) besitzt (wobei a beliebig, nur ungleich 0), dann kann man nicht voraussetzen, dass dies gleich ((a+b)-b) ist - und der Mini-Unterschied kann den entscheidenden Auslöser zwischen Hit vs. Nicht-Hit geben.
Ich hoffe das Problem ist klar.
Wie ich es sauber implementieren würde, habe ich oben geschrieben (Nachverarbeitungsschritt einführen).
-
wolfgke schrieb:
@rapso
[edit]...antifullquote...[/edit]danke fuer den grundkurs, aber ich glaube ich weiss auf diesem gebiet bestens bescheid
Ich hoffe das Problem ist klar.
nein, das problem kennen wir leider nicht, wir kennen nur das problem in seinem loesungsansatz seines urspruenglichen problems (oder ich hab das ursprungsproblem ueberlesen, dann sorry).
also, was bezweckst er mit der sache? willst er nur wissen ob ein strahl durch einen convexen koerper geht, oder brauchst er wirklich die beiden schnittpunkte? will er vielleicht nur auf komplizierte weise einen point-in-convex-volume test machen ?
davon haengt stark die loesung ab. dass es z.b. ein convexer koerper ist erlaubt ihm schonmal unmengen an optimierungen die ein stabiles ergebnis erlauben.Wie ich es sauber implementieren würde, habe ich oben geschrieben (Nachverarbeitungsschritt einführen).
das ist keine saubere loesung, sondern ein hack um eine suboptimale loesung zu trimmen. damit wirst du weiterhin probleme haben, zwar viel seltener, aber eine stabile loesung ist das nicht.
-
Sorry, rapso. Dass mein Lösungsansatz nicht sauber ist, hatte ich erst nach dem Posten gemerkt (ich war in Gedanken mehr bei Numerik
).Dass du dich auch sehr gut in numerischer Mathematik auskennst, konnte ich nicht wissen - kein Grund dich beleidigt zu fühlen. In der Tat habe ich schon eine Menge Grafikcode gesehen, welcher grafiktechnisch genial (das ist eine Kompetenz, die ich dir ohne zu zögern zugestehe), aber numerisch grottig-schlecht (dass du dich hier auch gut auskennst, wusste ich nicht) ist.
Wenn ich so sehe, wie wenig viele Informatikstudenten Ahnung von Mathe haben, bin ich den Weg der Vorsicht gegangen und habe alles ein wenig ausführlicher erklärt.