Abstand zweier Dreiecke

Fragen zu mathematischen Problemen
Antworten
Empire
Beiträge: 272
Registriert: Mo Jan 26, 2009 5:36 pm

Abstand zweier Dreiecke

Beitrag von Empire » Mo Mai 07, 2012 4:40 pm

Hallo zusammen,

ich wüsste gerne wie man wie man die kürzeste Distanz zwischen zwei Dreiecken im dreidimensionalen Raum berechnet.
Ich hab mir das ganze Wochenende den Kopf zerbrochen, bin aber auf keine wirkliche Lösung gekommen.
Das was am nächsten an einen Akzeptable Lösung rankommt, wäre sie auf drei Ebenen zu projezieren
(am einfachsten durch weglassen einer Kordinate) dann im zweidimensionalen den Abstand berechnen und dann .....
den durchschnitt errechnen?(Da bin ich mir noch nicht sicher, versuchs grade noch an einem BSP herauszubekommen)

Hat jemand eine Idee wie es besser Funktioniert?

mfg
Empire

EDIT: Ich hab grade gesehen es gibt doch ein Mathe Thread. Kann es bitte jemand verschieben?

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8470
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Abstand zweier Dreiecke

Beitrag von Xin » Mo Mai 07, 2012 4:49 pm

Schönes Problem, reichlich zu überprüfende Fälle.

Darf ich erst mal fragen, was Du vorhast?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3079
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Abstand zweier Dreiecke

Beitrag von cloidnerux » Mo Mai 07, 2012 4:58 pm

Ich würde es mit folgendem Ansatz versuchen:
Ein Dreieck ist vollständig durch eine Ecke v(OA) und den Verbindungsvektoren zwischen den beiden anderen Punkten v(AB) und v(AC) durch folgende Verbindung beschrieben:
v(x) = v(OA) + s*v(AB) + t*v(AC) s und t Element R [0, 1] <-- Ebenengleichung
Die Differenz der beiden Ebenengleichungen v(x1) - v(x2) ergibt einen Verbindungsvektor v(x1x2), dessen Betrag die Länge der Verbindung angibt.
Nun soll diese Verbindung minimal werden(Extremwertaufgabe)
Da nun der Betrag eines Vektors die Summer der Quadrate seiner Komponenten gewurzelt entspricht, hat man nun eine Funktion, die von den 4 Parametern s1, s2, t1 und t2 abhängt. Diese muss man nun Differntieren um die erste Ableitung zu erhalten und dann muss man nach Nullstellen suchen.
Ich würde zwar jetzt kurz versuchen das komplett durchzurechnen, leider fehlt mir dazu aber die Zeit.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8470
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Abstand zweier Dreiecke

Beitrag von Xin » Mo Mai 07, 2012 5:20 pm

cloidnerux hat geschrieben:Ich würde es mit folgendem Ansatz versuchen:
Ein Dreieck ist vollständig durch eine Ecke v(OA) und den Verbindungsvektoren zwischen den beiden anderen Punkten v(AB) und v(AC) durch folgende Verbindung beschrieben:
Falls es keins der Dreiecke entartet ist.
cloidnerux hat geschrieben:v(x) = v(OA) + s*v(AB) + t*v(AC) s und t Element R [0, 1] <-- Ebenengleichung
Die Differenz der beiden Ebenengleichungen v(x1) - v(x2) ergibt einen Verbindungsvektor v(x1x2), dessen Betrag die Länge der Verbindung angibt.
Wenn beide Dreiecke auf der gleichen Ebene liegen, dann wird der Verbindungsvektor ziemlich platt.


Deswegen frage ich nach dem zu lösenden Problem. Ansonsten muss man nämlich erstmal viele Fragen stellen. ^^
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Empire
Beiträge: 272
Registriert: Mo Jan 26, 2009 5:36 pm

Re: Abstand zweier Dreiecke

Beitrag von Empire » Mo Mai 07, 2012 5:53 pm

1. Danke fürs Verschieben.
2. Ich will eine kleine Physik-Engine schreiben, und dafür muss ich wissen wenn Objekte aufeinander Treffen. Da es nie der Fall sein wird das sie sich exact berühren und ich es doof finde immer erst zu reagieren wenn sie ineinander hängen, brauche ich den Abstand zueinander.
(Nebenfrage: Weis jemand wie das in Richtigen Spielen gehandhabt wird?)

mfg
Empire

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3079
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Abstand zweier Dreiecke

Beitrag von cloidnerux » Mo Mai 07, 2012 6:02 pm

(Nebenfrage: Weis jemand wie das in Richtigen Spielen gehandhabt wird?)
Normalerweise mit Boundingboxen.
Du erstellst ein Rechteck um dein Objekt. Dann prüfst du ob etwas in dieses Rechteck eintrifft.
Um das zu verfeinern, unterteilt man die Box in kleinere Boxen, kann dann Prüfen ob es leere Boxen gibt, also Bereiche wo dein Objekt gar nicht hineinragt und verknüpft die in einer Baumstruktur. Dann geht man einfach von oben nach unten, und prüft immer weiter bis zu einem Gewissen grad.

Ansonsten kannst du einfach den Schwerpunkt eines Dreiecks nehmen und über den Außenradius prüfen, ob etwas einem Kugelbereich um das Dreieck liegt. Du kannst aber auch die Bewegungsrichtung eines Körpers als Vektor nehmen und prüfen, ob eine Gerade mit einem bestimmten Aufpunkt und dem Richtungsvektor ein Dreieck schneiden wird, wobei das Ziemlich aufwendig ist, genauso wie jedes Dreieck einzeln zu prüfen, denn hast du erstmal > 1Millionen davon, hast du keine Zeit mehr dafür, dann bleibt dir nur so etwas wie ne Bounding-Box.

Zudem berücksichtigst du mit deiner Abstandslösung nicht den Fall, das 2 Dreieck sehr dicht passieren Könnten
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8470
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Abstand zweier Dreiecke

Beitrag von Xin » Mo Mai 07, 2012 6:22 pm

Empire hat geschrieben:Ich will eine kleine Physik-Engine schreiben, und dafür muss ich wissen wenn Objekte aufeinander Treffen. Da es nie der Fall sein wird das sie sich exact berühren und ich es doof finde immer erst zu reagieren wenn sie ineinander hängen, brauche ich den Abstand zueinander.
Deine Antwort ist ambivalent. Physik-Engine klingt hochgradig genau, Spiel eher weniger.

Warum gerade Dreiecke? Dreiecke entstehen meist erst, nachdem Körper tesselliert wurden. Sie treten in der Realität eher weniger auf - selbst ein Geodreieck hätte ja eine Dicke und wäre damit ein Körper, der aus mindestens 5 Flächen besteht (via Bounding Representation).
Empire hat geschrieben:(Nebenfrage: Weis jemand wie das in Richtigen Spielen gehandhabt wird?)
Es gibt mehrere Möglichkeiten. Du könntest mit OpenGL das Szenario zeichnen lassen und Dir anschließend die Grafik angucken, ob Dein Dreieck vor oder hinter dem anderen Dreieck gezeichnet wurde, bzw. in welcher Entfernung sie zueinander stehen.
Oder eben analytisch: Du rechnest das Ganze aus. Das kostet aber Zeit und ist eine größere Fallunterscheidung.

Da Du vermutlich keine (Rechen-)Zeit hast, kämen wir zur cloidnerux Vorschlag: die Bounding Box. Hier würde ich den ganzen Körper in eine Box packen und gucken, ob diese die Bounding Box des anderen Körpers schneidet. Das ist eine vergleichsweise recht preiswerte Operation und bei aufwendigen Körpern deutlich effizienter.
Das siehst Du beispielsweise bei Spielfiguren, die vor der Wand stehen und nicht weitergehen: Die (unsichtbare) Bounding Box berührt die Wand, also geht die Figur nicht weiter.

Dreiecke sind das kleinste Element, das man an die Grafikkarte schickt. Während die Distanz einer Kugel zu einer anderen Kugel analytisch sehr einfach zu berechnen ist, wird das ganze sehr aufwendig, wenn die Kugeln tesselliert sind (also in Dreiecke zerlegt) und nun herausgefunden werden muss, welche Dreiecke am nächsten aneinander liegen.

Deswegen frage ich so deutlich nach, was Du brauchst.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Empire
Beiträge: 272
Registriert: Mo Jan 26, 2009 5:36 pm

Re: Abstand zweier Dreiecke

Beitrag von Empire » Mo Mai 07, 2012 6:58 pm

Bei Boundingboxen ist es aber extrem ungenau oder man braucht (wenn die Objekte nicht gerade von Minecraft stammen) verdammt viele.
Vermutlich ist es aber trotzdem die beste Lösung.
Warum gerade Dreiecke?
Weil es eben die kleinsten Teile sind und es damit am genauesten wäre.
Zudem berücksichtigst du mit deiner Abstandslösung nicht den Fall, das 2 Dreieck sehr dicht passieren Könnten
Wenn wenn der Abstand so klein wird dass das Programm es als "Kolison" sieht, sieht es für den Spieler wie entlang schrammen aus.
Das müsste die Engine auch erkennen.

Danke ihr habt mir sehr weitergeholfen.

mfg
Empire

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8470
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Abstand zweier Dreiecke

Beitrag von Xin » Mo Mai 07, 2012 9:31 pm

Empire hat geschrieben:Bei Boundingboxen ist es aber extrem ungenau oder man braucht (wenn die Objekte nicht gerade von Minecraft stammen) verdammt viele.
Vermutlich ist es aber trotzdem die beste Lösung.
Es ist die beste Lösung, wenn Du in Echtzeit arbeiten willst.
Empire hat geschrieben:
Warum gerade Dreiecke?
Weil es eben die kleinsten Teile sind und es damit am genauesten wäre.
Wie ich an der Kugel zeigte, ist die Kugel eigentlich genauer.
Wenn Du die Genauigkeit an die Darstellung legen willst, sind Dreiecke genauer, führen aber wahrscheinlich zu unphysikalischen Effekten.
Empire hat geschrieben:
Zudem berücksichtigst du mit deiner Abstandslösung nicht den Fall, das 2 Dreieck sehr dicht passieren Könnten
Wenn wenn der Abstand so klein wird dass das Programm es als "Kolison" sieht, sieht es für den Spieler wie entlang schrammen aus.
Das müsste die Engine auch erkennen.
Exakt wird nur, wenn Du es analytisch machst. Solange Du es nur zeichnest, solltest Du keine großen Probleme haben. Du wirst Dich aber mit Numerik auseinander setzen müssen und Du wirst sehr laut fluchen. :-)
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Antworten