Itinéraires sur une surface de sphère - Trouver la géodésique?

Je travaille avec des amis sur un jeu basé sur un navigateur où les gens peuvent se déplacer sur une carte 2D. Cela fait presque 7 ans et les gens jouent encore à ce jeu, nous réfléchissons donc à un moyen de leur donner quelque chose de nouveau. Depuis lors, la carte du jeu était un avion limité et les gens pouvaient passer de (0, 0) à (MAX_X, MAX_Y) par incréments quantifiés X et Y (imaginez-le simplement comme un gros échiquier).
Nous pensons qu'il est temps de lui donner une autre dimension donc, il y a quelques semaines à peine, nous avons commencé à nous demander à quoi le jeu pourrait ressembler avec d'autres mappings:

• Avion illimité avec mouvement continu: cela pourrait être un pas en avant mais je ne suis toujours pas convaincu.
• Toroidal World (mouvement continu ou quantifié): sincèrement j'ai déjà travaillé avec torus mais cette fois je veux quelque chose de plus ...
• Monde sphérique avec mouvement continu: ce serait génial!

Ce que nous voulons Les navigateurs utilisateurs reçoivent une liste de coordonnées comme (latitude, longitude) pour chaque objet sur la carte de surface sphérique; les navigateurs doivent ensuite afficher cela dans l'écran de l'utilisateur en les rendant dans un élément Web (toile peut-être? ce n'est pas un problème). Lorsque les gens cliquent sur le plan, nous convertissons le (mouseX, mouseY) en (lat, lng) et l'envoyons au serveur qui doit calculer un itinéraire entre la position actuelle de l'utilisateur au point cliqué.

Ce que nous avons Nous avons commencé à écrire une bibliothèque Java avec de nombreuses mathématiques utiles pour travailler avec les matrices de rotation, les quaternions, les angles d'Euler, les traductions, etc. à l'intérieur d'un JPanel. Nous avons réussi à capturer des clics et à les traduire en cordes sphériques et à fournir d'autres fonctionnalités utiles telles que la rotation de la vue, l'échelle, la traduction, etc. Le côté client affiche les points à l'écran et capture d'autres interactions, le côté serveur rend la vue et effectue d'autres calculs comme l'interpolation de l'itinéraire entre la position actuelle et le point cliqué.

Où est le problème? Nous voulons évidemment avoir le chemin le plus court pour interpoler entre les deux points de route . Nous utilisons des quaternions pour interpoler entre deux points sur la surface de la sphère et cela a semblé fonctionner correctement jusqu'à ce que je remarque que nous n'obtenions pas le chemin le plus court sur la surface de la sphère:

Nous pensions que le problème était que l'itinéraire est calculé comme la somme de deux rotations autour des axes X et Y. Nous avons donc changé la façon dont nous calculons le quaternion de destination: nous obtenons le troisième angle (le premier est la latitude, le second est la longitude, le troisième est la rotation autour du vecteur qui pointe vers notre position actuelle) que nous avons appelé orientation. Maintenant que nous avons l'angle "d'orientation", nous faisons pivoter l'axe Z puis utilisons le vecteur de résultat comme axe de rotation pour le quaternion de destination (vous pouvez voir l'axe de rotation en gris):

Ce que nous avons obtenu est le bon itinéraire (vous pouvez le voir sur un grand cercle), mais nous n'y arrivons que si le point de départ est à la latitude, la longitude (0, 0), ce qui signifie que le vecteur de départ est (sphèreRadius, 0 , 0). Avec la version précédente (image 1), nous n'obtenons pas un bon résultat même lorsque le point de départ est 0, 0, donc je pense que nous nous dirigeons vers une solution, mais la procédure que nous suivons pour obtenir cet itinéraire est un peu "étrange" " peut être?

Dans l'image suivante, vous obtenez une vue du problème que nous obtenons lorsque le point de départ n'est pas (0, 0), car vous pouvez voir que le point de départ n'est pas le vecteur (sphereRadius, 0, 0) et que vous pouvez voir le point de destination (qui est correctement dessiné!) n'est pas sur l'itinéraire.

Le point magenta (celui qui se trouve sur l'itinéraire) est le point d'arrivée de l'itinéraire tourné autour du centre de la sphère de (-startLatitude, 0, -startLongitude). Cela signifie que si je calcule une matrice de rotation et l'applique à chaque point de l'itinéraire, j'obtiendrai peut-être la route réelle, mais je commence à penser qu'il existe une meilleure façon de procéder.

Peut-être que je devrais essayer de faire passer l'avion par le centre de la sphère et les points de route, l'intersecter avec la sphère et obtenir la géodésique? Mais comment?

Désolé d'être trop verbeux et peut-être pour un anglais incorrect mais cette chose me souffle!

EDIT: Le code ci-dessous fonctionne très bien! Merci à tout le monde:

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

Votre problème est purement bidimensionnel, dans le plan formé par le centre de la sphère et vos points source et destination. L'utilisation de quaternions rend en fait les choses plus complexes, car en plus d'une position sur une sphère 3D, un quaternion code une orientation.

Vous avez peut-être déjà quelque chose à interpoler sur un cercle, mais juste au cas où, voici un code qui devrait fonctionner.

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

Assurez-vous que les deux quaternions sont sur le même hémisphère sur l'hypersphère. Si leur produit scalaire est inférieur à 0, ils ne le sont pas. Dans ce cas, annulez l'un d'eux (annulez chacun de ses numéros), ils sont donc sur le même hémisphère et vous donneront le chemin le plus court. 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

Ma réponse explique ici en détail ce que la négation de chaque terme du quaternion fait et pourquoi c'est toujours la même orientation, juste de l'autre côté de l'hypersphère.

EDITER la fonction d'interpolation devrait ressembler à ceci:

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

Puisque vous voulez un V3Dretour de votre interpolateur, l'approche la plus simple consiste à ignorer complètement les quaternions. Convertissez les points de début et de fin V3Det inversez-les.

Si vous insistez sur l' utilisation escouades alors le quaternion représentant la rotation de Pla Qa direction P x Qet wde P . Q.