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

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:

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):

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.

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;
}

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;
}

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;
}

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.