Routen auf einer Kugeloberfläche - Geodätisch finden?

8

Ich arbeite mit einigen Freunden an einem browserbasierten Spiel, in dem sich Leute auf einer 2D-Karte bewegen können. Es ist fast 7 Jahre her und immer noch spielen die Leute dieses Spiel, also überlegen wir uns, wie wir ihnen etwas Neues geben können. Seitdem war die Spielkarte eine begrenzte Ebene und die Leute konnten sich in quantisierten X- und Y-Schritten von (0, 0) nach (MAX_X, MAX_Y) bewegen (stellen Sie sich das als großes Schachbrett vor).
Wir glauben, dass es Zeit ist, ihm eine andere Dimension zu geben. Vor ein paar Wochen haben wir uns gefragt, wie das Spiel mit anderen Mappings aussehen könnte:

  • Unbegrenztes Flugzeug mit kontinuierlicher Bewegung: Dies könnte ein Schritt nach vorne sein, aber ich bin immer noch nicht überzeugt.
  • Toroidal World (kontinuierliche oder quantisierte Bewegung): Mit freundlichen Grüßen habe ich schon früher mit Torus gearbeitet, aber dieses Mal möchte ich etwas mehr ...
  • Sphärische Welt mit kontinuierlicher Bewegung: Das wäre großartig!

Was wir wollen Benutzer Browser erhalten eine Liste von Koordinaten wie (Breite, Länge) für jedes Objekt auf der sphärischen Oberflächenkarte; Browser müssen dies dann auf dem Bildschirm des Benutzers anzeigen und sie in einem Webelement rendern (Leinwand vielleicht? Dies ist kein Problem). Wenn Leute auf die Ebene klicken, konvertieren wir (mouseX, mouseY) in (lat, lng) und senden es an den Server, der eine Route zwischen der Position des aktuellen Benutzers und dem angeklickten Punkt berechnen muss.

Was wir haben Wir haben begonnen, eine Java-Bibliothek mit vielen nützlichen Mathematikfunktionen für Rotationsmatrizen, Quaternionen, Euler-Winkel, Übersetzungen usw. zu schreiben. Wir haben alles zusammengestellt und ein Programm erstellt, das Kugelpunkte generiert, sie rendert und dem Benutzer zeigt in einem JPanel. Wir haben es geschafft, Klicks zu fangen und sie in sphärische Koordinaten zu übersetzen und einige andere nützliche Funktionen wie Ansichtsrotation, Skalierung, Übersetzung usw. bereitzustellen. Was wir jetzt haben, ist wie eine kleine (in der Tat sehr kleine) Engine, die die Client- und Server-Interaktion simuliert. Die Clientseite zeigt Punkte auf dem Bildschirm an und erfasst andere Interaktionen. Die Serverseite rendert die Ansicht und führt andere Berechnungen wie das Interpolieren der Route zwischen der aktuellen Position und dem angeklickten Punkt durch.

Wo ist das Problem? Offensichtlich möchten wir den kürzesten Weg haben, um zwischen den beiden Routenpunkten zu interpolieren . Wir verwenden Quaternionen, um zwischen zwei Punkten auf der Oberfläche der Kugel zu interpolieren, und dies schien gut zu funktionieren, bis ich bemerkte, dass wir nicht den kürzesten Weg auf der Kugeloberfläche hatten:

Falscher Kreis

Wir hatten jedoch das Problem, dass die Route als die Summe von zwei Umdrehungen um die X- und Y-Achse berechnet wird. Also haben wir die Art und Weise geändert, wie wir die Zielquaternion berechnen: Wir erhalten den dritten Winkel (der erste ist der Breitengrad, der zweite ist der Längengrad, der dritte ist die Drehung um den Vektor, der auf unsere aktuelle Position zeigt), den wir Orientierung nannten. Nachdem wir den "Orientierungs" -Winkel haben, drehen wir die Z-Achse und verwenden dann den Ergebnisvektor als Rotationsachse für die Zielquaternion (Sie können die Rotationsachse grau sehen):

Richtige Route ab 0, 0

Was wir haben, ist die richtige Route (Sie können sehen, dass sie auf einem großen Kreis liegt), aber wir kommen NUR dazu, wenn der Startroutenpunkt bei Breite, Länge (0, 0) liegt, was bedeutet, dass der Startvektor (SphereRadius, 0) ist , 0). Mit der vorherigen Version (Bild 1) erhalten wir kein gutes Ergebnis, selbst wenn der Startpunkt 0, 0 ist. Ich denke, wir bewegen uns in Richtung einer Lösung, aber das Verfahren, das wir befolgen, um diese Route zu erhalten, ist ein wenig "seltsam" " könnte sein?

In der folgenden Abbildung erhalten Sie einen Überblick über das Problem, das auftritt, wenn der Startpunkt nicht (0, 0) ist, da der Startpunkt nicht der Vektor (pherRadius, 0, 0) ist und der Zielpunkt angezeigt wird (was richtig gezeichnet ist!) ist nicht auf der Route.

Route ist falsch!

Der Magenta-Punkt (derjenige, der auf der Route liegt) ist der Endpunkt der Route, der um den Mittelpunkt der Kugel von (-startLatitude, 0, -startLongitude) gedreht wird. Das bedeutet, wenn ich eine Rotationsmatrix berechne und sie auf jeden Punkt auf der Route anwende, erhalte ich möglicherweise die tatsächliche Route, aber ich denke, dass es einen besseren Weg gibt, dies zu tun.

Vielleicht sollte ich versuchen, das Flugzeug durch den Mittelpunkt der Kugel und die Routenpunkte zu bringen, es mit der Kugel zu schneiden und die Geodät zu erhalten? Aber wie?

Tut mir leid, dass ich viel zu ausführlich bin und vielleicht falsches Englisch, aber dieses Ding hat mich umgehauen!

EDIT: Code unten funktioniert gut! Ich danke euch allen:

public void setRouteStart(double srcLat, double srcLng, double destLat, destLng) {
    //all angles are in radians
    u = Choords.sphericalToNormalized3D(srcLat, srcLng);
    v = Choords.sphericalToNormalized3D(destLat, destLng);
    double cos = u.dotProduct(v);
    angle = Math.acos(cos);
    if (Math.abs(cos) >= 0.999999) {
        u = new V3D(Math.cos(srcLat), -Math.sin(srcLng), 0);
    } else {
        v.subtract(u.scale(cos));
        v.normalize();
    }
}

public static V3D sphericalToNormalized3D( double radLat, double radLng) {
    //angles in radians
    V3D p = new V3D();
    double cosLat = Math.cos(radLat);
    p.x = cosLat*Math.cos(radLng);
    p.y = cosLat*Math.sin(radLng);
    p.z = Math.sin(radLat);
    return p;
}

public void setRouteDest(double lat, double lng) {
    EulerAngles tmp = new AngoliEulero(
       Math.toRadians(lat), 0, -Math.toRadians(lng));
    qtEnd.setInertialToObject(tmp);
    //do other stuff like drawing dest point...
}

public V3D interpolate(double totalTime, double t) {
    double _t = angle * t/totalTime;
    double cosA = Math.cos(_t);
    double sinA = Math.sin(_t);
    V3D pR = u.scale(cosA);
    pR.sum(
       v.scale(sinA)
    );
    return pR;
}
CaNNaDaRk
quelle
1
Bitte zeigen Sie Ihren Quaternion Slerp / Interpolation Code.
Maik Semder
1
Nebenbei bemerkt: Selbst Bücher können unbeobachtete, aber katastrophale Fehler enthalten. Stellen Sie vor dem Kopieren sicher, dass Sie es selbst verstehen. Nur dann können Sie sich darauf verlassen, dass es gültig ist (es sei denn, Sie haben es selbst falsch verstanden - aber dies ist weitaus weniger wahrscheinlich).
Teodron
@ MaikSemder fügte die Funktion hinzu, in der die RotationMatrix ab der Quaternion-Klasse kompiliert wird
CaNNaDaRk
Möglicherweise liegt das Problem in setRouteDest (double lat, double lng) und setRouteStart (double lat, double lng). Ich glaube, ich vermisse einen Winkel, wenn ich das EulerAngles-Objekt wie folgt erstelle: EulerAngles tmp = new EulerAngles (Math.toRadians (lat), ???, -Math.toRadians (lng))
CaNNaDaRk
Ich sehe nicht, wo Sie "RotationMatrix" verwenden, um den gedrehten Punkt "p" zu erstellen, der von "interpolate" zurückgegeben wird. Sie haben gerade "RotationMatrix" aus der interpolierten Quaternion eingestellt, aber Sie verwenden sie nicht
Maik Semder

Antworten:

5

Ihr Problem ist rein zweidimensional in der Ebene, die vom Kugelzentrum und Ihren Quell- und Zielpunkten gebildet wird. Die Verwendung von Quaternionen macht die Dinge tatsächlich komplexer, da zusätzlich zu einer Position auf einer 3D-Kugel eine Quaternion eine Orientierung codiert.

Möglicherweise müssen Sie bereits etwas auf einem Kreis interpolieren, aber für den Fall, hier ist ein Code, der funktionieren sollte.

V3D u, v;
double angle;

public V3D geographicTo3D(double lat, double long)
{
    return V3D(sin(Math.toRadians(long)) * cos(Math.toRadians(lat)),
               cos(Math.toRadians(long)) * cos(Math.toRadians(lat)),
               sin(Math.toRadians(lat)));
}

public V3D setSourceAndDest(double srcLat, double srcLong,
                            double dstLat, double dstLong)
{
    u = geographicTo3D(srcLat, srcLong);
    V3D tmp = geographicTo3D(dstLat, dstLong);
    angle = acos(dot(u, tmp));
    /* If there are an infinite number of routes, choose
     * one arbitrarily. */
    if (abs(dot(u, tmp)) >= 0.999999)
        v = V3D(cos(srcLong), -sin(srcLong), 0);
    else
        v = normalize(tmp - dot(u, tmp) * u);
}

public V3D interpolate(double totalTime, double t)
{
    double a = t / totalTime * angle;
    return cos(a) * u + sin(a) * v;
}
Sam Hocevar
quelle
Ja! Das ist es, wonach ich suche, das ist mein eigentliches Problem, ich muss an der Ebene arbeiten, die C, Ziel und Quelle schneidet! Das einzige Problem ist, dass ich es immer noch nicht zum Laufen bringen kann ... Ich werde den Code und die Ergebnisse einfügen, die ich aus Ihrem Code erhalten habe!
CaNNaDaRk
hat die Frage bearbeitet. Es gibt ein Problem ... vielleicht habe ich den Code falsch übersetzt ???
CaNNaDaRk
@CaNNaDaRk Ich sehe nicht, was falsch sein kann. Sind die Verwendungen von normalize (), subtrahieren (), skalieren () usw. in Bezug auf Nebenwirkungen korrekt? Und tut tReichweite totalTime? Auch wenn Sie den vollen Kreis erhalten möchten, geben Sie den tMaximalwert 2 * pi / angle * totalTimeanstelle von nur ein totalTime.
Sam Hocevar
Perfekt! Dort habe ich der Normalisierungsfunktion einen dummen Fehler hinzugefügt und daher eine falsche Größe im "v" -Vektor erhalten. Jetzt funktioniert alles gut!
Nochmals vielen
3

Stellen Sie sicher, dass sich beide Quaternionen auf derselben Hemisphäre auf der Hypersphäre befinden. Wenn ihr Punktprodukt kleiner als 0 ist, sind sie es nicht. In diesem Fall negiere eine von ihnen (negiere jede ihrer Zahlen), so dass sie sich auf derselben Hemisphäre befinden und dir den kürzesten Weg geben. Pseudocode:

quaternion from, to;

// is "from" and "to" on the same hemisphere=
if(dot(from, to) < 0.0)
{
    // put "from" to the other hemisphere, so its on the same as "to"
    from.x = -from.x;
    from.y = -from.y;
    from.z = -from.z;
    from.w = -from.w;
}

// now simply slerp them

Meine Antwort hier erklärt im Detail, was das Negieren jedes Terms der Quaternion bewirkt und warum es immer noch dieselbe Ausrichtung hat, nur auf der anderen Seite der Hypersphäre.


BEARBEITEN Die Interpolationsfunktion sollte folgendermaßen aussehen:

public V3D interpolate(double totalTime, double t) {
    double _t = t/totalTime;    
    Quaternion tmp;
    if(dot(qtStart, qtEnd) < 0.0)
    {
        tmp.x = -qtEnd.x;
        tmp.y = -qtEnd.y;
        tmp.z = -qtEnd.z;
        tmp.w = -qtEnd.w;
    }
    else
    {
        tmp = qtEnd;
    }
    Quaternion q = Quaternion.Slerp(qtStart, tmp, _t);
    RotationMatrix.inertialQuatToIObject(q);
    V3D p = matInt.inertialToObject(V3D.Xaxis.scale(sphereRadius));
    //other stuff, like drawing point ...
    return p;
}
Maik Semder
quelle
Ich habe Ihren Code ausprobiert, aber ich erhalte die gleichen Ergebnisse. Im Debug-Modus achte ich auf das Punktprodukt und bin mir sicher, dass sich die beiden Quaternionen auf derselben Hemisphäre auf der Hypersphäre befinden. Entschuldigung, vielleicht ist meine Frage nicht klar genug?
CaNNaDaRk
Was meinst du mit "du bist sicher, dass sie sich auf derselben Hemisphäre befinden"? wenn dot> = 0, dann sind sie es, sonst nicht.
Maik Semder
Es geht nicht um die Hemisphäre Ihrer normalen Sphäre, es geht um die Hemisphäre in der Hypersphäre, den 4D-Raum des Quaternions. Nehmen Sie sich Zeit, um den Link zu lesen, es ist schwer in einem Kommentarfeld zu erklären.
Maik Semder
Das sage ich, ich habe deinen Code eingegeben und den Punkt berechnet. Selbst wenn es> = 0 ist (ich bin mir also sicher, dass sie sich auf derselben Hemisphäre befinden), ist das Problem immer dasselbe: Die Route, die ich bekomme, befindet sich nicht in einem großen Kreis. Ich denke das Problem ist woanders ..? Vielleicht sollte ich der Frage etwas Code hinzufügen ...? Bearbeiten: Ich habe Ihren Link gelesen, ich glaube immer noch nicht, dass das Problem da ist. Ich habe auch den Code ausprobiert, den Sie mir gegeben haben, aber ich bekomme trotzdem eine Route in einem kleinen Kreis.
CaNNaDaRk
Bitte zeigen Sie Ihren Interpolationscode
Maik Semder
0

Da Sie ein V3DZurück von Ihrem Interpolator wünschen , besteht der einfachste Ansatz darin, die Quaternionen vollständig zu überspringen. Konvertieren Sie die Start- und Endpunkte in V3Dund wechseln Sie zwischen ihnen.

Wenn Sie darauf bestehen, Quaternionen zu verwenden, hat die Quaternion, die die Drehung von Pnach darstellt, Qdie Richtung P x Qund wvon P . Q.

Peter Taylor
quelle