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?
Abstand zweier Dreiecke
- Xin
- nur zu Besuch hier
- Beiträge: 8859
- Registriert: Fr Jul 04, 2008 11:10 pm
- Wohnort: /home/xin
- Kontaktdaten:
Re: Abstand zweier Dreiecke
Schönes Problem, reichlich zu überprüfende Fälle.
Darf ich erst mal fragen, was Du vorhast?
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.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
- cloidnerux
- Moderator
- Beiträge: 3123
- Registriert: Fr Sep 26, 2008 4:37 pm
- Wohnort: Ram (Gibts wirklich)
Re: Abstand zweier Dreiecke
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.
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
quod erat expectandum
- Xin
- nur zu Besuch hier
- Beiträge: 8859
- Registriert: Fr Jul 04, 2008 11:10 pm
- Wohnort: /home/xin
- Kontaktdaten:
Re: Abstand zweier Dreiecke
Falls es keins der Dreiecke entartet ist.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:
Wenn beide Dreiecke auf der gleichen Ebene liegen, dann wird der Verbindungsvektor ziemlich platt.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.
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.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
Re: Abstand zweier Dreiecke
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
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
- cloidnerux
- Moderator
- Beiträge: 3123
- Registriert: Fr Sep 26, 2008 4:37 pm
- Wohnort: Ram (Gibts wirklich)
Re: Abstand zweier Dreiecke
Normalerweise mit Boundingboxen.(Nebenfrage: Weis jemand wie das in Richtigen Spielen gehandhabt wird?)
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
quod erat expectandum
- Xin
- nur zu Besuch hier
- Beiträge: 8859
- Registriert: Fr Jul 04, 2008 11:10 pm
- Wohnort: /home/xin
- Kontaktdaten:
Re: Abstand zweier Dreiecke
Deine Antwort ist ambivalent. Physik-Engine klingt hochgradig genau, Spiel eher weniger.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.
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).
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.Empire hat geschrieben:(Nebenfrage: Weis jemand wie das in Richtigen Spielen gehandhabt wird?)
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.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
Re: Abstand zweier Dreiecke
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.
Das müsste die Engine auch erkennen.
Danke ihr habt mir sehr weitergeholfen.
mfg
Empire
Vermutlich ist es aber trotzdem die beste Lösung.
Weil es eben die kleinsten Teile sind und es damit am genauesten wäre.Warum gerade Dreiecke?
Wenn wenn der Abstand so klein wird dass das Programm es als "Kolison" sieht, sieht es für den Spieler wie entlang schrammen aus.Zudem berücksichtigst du mit deiner Abstandslösung nicht den Fall, das 2 Dreieck sehr dicht passieren Könnten
Das müsste die Engine auch erkennen.
Danke ihr habt mir sehr weitergeholfen.
mfg
Empire
- Xin
- nur zu Besuch hier
- Beiträge: 8859
- Registriert: Fr Jul 04, 2008 11:10 pm
- Wohnort: /home/xin
- Kontaktdaten:
Re: Abstand zweier Dreiecke
Es ist die beste Lösung, wenn Du in Echtzeit arbeiten willst.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.
Wie ich an der Kugel zeigte, ist die Kugel eigentlich genauer.Empire hat geschrieben:Weil es eben die kleinsten Teile sind und es damit am genauesten wäre.Warum gerade Dreiecke?
Wenn Du die Genauigkeit an die Darstellung legen willst, sind Dreiecke genauer, führen aber wahrscheinlich zu unphysikalischen Effekten.
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.Empire hat geschrieben:Wenn wenn der Abstand so klein wird dass das Programm es als "Kolison" sieht, sieht es für den Spieler wie entlang schrammen aus.Zudem berücksichtigst du mit deiner Abstandslösung nicht den Fall, das 2 Dreieck sehr dicht passieren Könnten
Das müsste die Engine auch erkennen.
![Smile :-)](./images/smilies/icon_e_smile.gif)
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.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.