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

8

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:

Mauvais cercle

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

Itinéraire correct à partir de 0, 0

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.

L'itinéraire est incorrect!

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;
}
CaNNaDaRk
la source
1
Veuillez montrer votre code de slerp / interpolation quaternion.
Maik Semder
1
Soit dit en passant: même les livres peuvent contenir des erreurs non observées mais désastreuses. Avant de copier quoi que ce soit, assurez-vous de le comprendre vous-même ... c'est seulement alors que vous pouvez le considérer comme valide (enfin, sauf si vous l'avez mal compris vous-même - mais c'est beaucoup moins probable).
teodron
@MaikSemder a ajouté la fonction où le RotationMatrix est compilé à partir de la classe Quaternion
CaNNaDaRk
Peut-être que le problème est à l'intérieur de setRouteDest (double lat, double lng) et setRouteStart (double lat, double lng). Je pense qu'il me manque un angle lorsque je crée l'objet EulerAngles comme ceci: EulerAngles tmp = new EulerAngles (Math.toRadians (lat), ???, -Math.toRadians (lng))
CaNNaDaRk
Je ne vois pas où vous utilisez "RotationMatrix" pour créer le point pivoté "p" renvoyé par "interpoler". Vous venez de définir "RotationMatrix" à partir du quaternion interpolé, mais vous ne l'utilisez pas
Maik Semder

Réponses:

5

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;
}
sam hocevar
la source
Oui! C'est ce que je recherche, c'est mon vrai problème, je dois travailler sur l'avion croisant C, destination et source! Le seul problème est que je ne peux toujours pas le faire fonctionner ... Je vais coller le code et les résultats que j'ai obtenus de votre code!
CaNNaDaRk
édité la question. Il y a un problème ... j'ai peut-être mal traduit le code ???
CaNNaDaRk
@CaNNaDaRk Je ne vois pas ce qui peut mal se passer. Les utilisations de normalize (), subtract (), scale () etc. sont-elles correctes en ce qui concerne les effets secondaires? Et tatteint-il totalTime? De plus, si vous souhaitez obtenir le cercle complet, définissez la tvaleur maximale 2 * pi / angle * totalTimeau lieu de simplement totalTime.
sam hocevar
Parfait! Là, j'ai ajouté une erreur stupide à la fonction de normalisation et j'ai donc obtenu une mauvaise amplitude dans le vecteur "v". Maintenant, tout fonctionne bien! Merci encore;)
CaNNaDaRk
3

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;
}
Maik Semder
la source
J'ai essayé votre code mais j'obtiens les mêmes résultats. En mode débogage, je surveille le produit scalaire et je suis sûr que les deux quaternions sont sur le même hémisphère sur l'hypersphère. Désolé, ma question n'est peut-être pas assez claire?
CaNNaDaRk
Que voulez-vous dire "vous êtes sûr qu'ils sont sur le même hémisphère"? si dot> = 0 alors ils le sont, sinon non.
Maik Semder
Il ne s'agit pas de l'hémisphère de votre sphère normale, il s'agit de l'hémisphère dans l'hypersphère, l'espace 4D du quaternion. Prenez le temps de lire le lien, c'est difficile à expliquer dans une boîte de commentaire.
Maik Semder
C'est ce que je dis, j'ai mis votre code et calculé le point. Même quand c'est> = 0 (donc je suis sûr qu'ils sont sur le même hémisphère) le problème est toujours le même: l'itinéraire que je reçois n'est pas sur un grand cercle. Je pense que le problème est ailleurs ..? Je devrais peut-être ajouter du code à la question ...? Edit: j'ai lu votre lien, je ne pense toujours pas que le problème soit là. J'ai également essayé le code que vous m'avez donné mais je reçois toujours un itinéraire sur un petit cercle.
CaNNaDaRk
Veuillez montrer votre code d'interpolation
Maik Semder
0

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.

Peter Taylor
la source