Dreieck-Dreieck Kollision (triangle-triangle intersection)

mariane

Mitglied
rumliegen, ... mal schauen, .., nö.

Wenn ich das richtig verstehe, ist gefragt ob sich zwei Dreiecke schneiden.
Dann wäre meine Antwort, sie schneiden sich wenn ein Punkt (des ersten Dreiecks) innerhalb eines (des zweiten) Dreieck liegt. Also ganz allg. gesagt: ist ein Punkt innerhalb oder außerhalb eines beliebig geformeten geschlossenen Polygonzuges.
Dazu zieht man Linien von Eckpunkt zu Eckpunkt und schaut, wieviele dieser Linien von einer Linie geschnitten werden, die in eine beliebige Richtung am Punkt beginnend fortläuft. Ungerade Anzahl an geschnittenen Linen heißt innerhalb, gerade bzw. kein schneiden außerhalb der vom Polygon gebildeten Fläche. Das geht natürlich auch bei Dreiecken.
 

Rubber

Aktives Mitglied
Hey,
danke schonmal für deine Antwort.
Hauptsächlich ist meine Frage aber tatsächlich ob das jemand schon fertig hat :)
(Gerade im Bereich Simulation und Spiel kommt das ja häufiger mal vor, so dass ich dachte es hat vielleicht jemand schon mal gemacht und ich spare es mir das rad neu zu erfinden. Zumal in c diverse snippets existieren und es mich wundert, dass ich nichts in java finde)

Was ich noch vergessen hatte zu erwähnen ist, dass es mir um den 3 Dimensionalen Raum geht.
Wenn sich keiner meldet, der es zufällig rum liegen hat, werde ich es wohl nach http://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/pubs/tritri.pdf selber machen.
 

JCODA

Top Contributor
Wenn ich das richtig verstehe, ist gefragt ob sich zwei Dreiecke schneiden.
Dann wäre meine Antwort, sie schneiden sich wenn ein Punkt (des ersten Dreiecks) innerhalb eines (des zweiten) Dreieck liegt. Also ganz allg. gesagt: ist ein Punkt innerhalb oder außerhalb eines beliebig geformeten geschlossenen Polygonzuges.

Das stimmt leider nicht:
https://puu.sh/sO8l5/33a0d26aa8.png
Ich alte mich bei sowas meistens an folgendes: einmal implementieren, testen, verstehen, danach Library verwenden, die machen das meist viel effizienter. Speziell für dieses Problem hab ich aber keinen Library in der Hinterhand.
 

Tobse

Top Contributor
Wo ich so drüber nachdenke ist das glaub echt keine einfache Aufgabe... ich sehe gerade nur die Möglichkeit, aus den Punkten des 1. Dreiecks Eine Ebene abzuleiten, die Drei Strecken des 2. Dreiecks damit zu schneiden und irgendwie noch >= <= operationen mit den Koordinaten der Schnittpunkte zu rechnen ... die Lösung muss einfacher sein :O :D
 

Rubber

Aktives Mitglied
Gerade für den Anfang würde ich dir empfehlen sowas erst recht selber zu machen, allein schon um mehr Übung zu haben.
Das Problem ist, dass es leider nicht so einfach ist, wie man denken mag.
Allerdings gibt es schon diverse Algorithmen. (wie von mir zb verlinkt)
Meine Internet recherchen haben ergeben, dass sich schon viele damit auseinander gesetzt haben.
Was mich nur wunderte ist, dass ich in c diverse snippets fand, aber kein einziges in Java.
Dachte also, bevor ich jetzt mir die mühe mache und einen der (fertigen) Allgorihtmen selber in Java implementiere, oder von c "abschreibe", dass es doch bestimmt schon der ein oder andere gemacht hat.
 

Thallius

Top Contributor
Könnte daran liegen, dass für solche Rechenzeit intensiven Algorithmen C einfach besser geeignet ist als Java. Wer schreibt schon eine 3D Lib in Java?

Gruß

Claus
 

stg

Top Contributor
Spaß beiseite, ein Dreieck ist einfach durch drei Eckpunkte definiert, ob diese punkte nun 2D oder 3D sind ist egal.

Ja, schon, aber sind dann nur die Ecken gemeint, oder das durch die Ecken definierte 1-Polytop, oder das 2-Polytop? Für solch einen Kollisionstest ist das ja nicht unwichtig :)
Aber ich hätte vermutlich einfach mal in die verlinkten Dokumente schauen müssen...

Das Problem ist, dass es leider nicht so einfach ist, wie man denken mag.
Nunja, das eigentliche Problem ist ja recht einfach lösbar. Schwierig wird es ja erst, wenn man es besonders raffiniert/effizient machen will. Ist einem das mehr oder weniger egal, dann reduziert sich das Problem doch auf 6 einfache Intersection-Tests (Wenn die zwei Dreiecke sich schneiden, dann schneidet mindestens eine Seite eines der Dreiecke die Grundfläche des zweiten. Bei 2 Dreiecken mit je 3 Seiten also maximal drei Tests.)

Und zur eigentlichen Frage: Nö, hab ich hier auch nicht rumfliegen.
 

Ähnliche Java Themen

Neue Themen


Oben