Rutas en una superficie de esfera - ¿Encontrar geodésicas?

8

Estoy trabajando con algunos amigos en un juego basado en navegador donde las personas pueden moverse en un mapa 2D. Han pasado casi 7 años y todavía la gente juega a este juego, así que estamos pensando en una forma de darles algo nuevo. Desde entonces, el mapa del juego era un plano limitado y la gente podía moverse de (0, 0) a (MAX_X, MAX_Y) en incrementos cuantificados de X e Y (imagínelo como un gran tablero de ajedrez).
Creemos que es hora de darle otra dimensión, así que, hace solo un par de semanas, comenzamos a preguntarnos cómo podría verse el juego con otras asignaciones:

  • Avión ilimitado con movimiento continuo: esto podría ser un paso adelante, pero todavía no estoy convencido.
  • Mundo toroidal (movimiento continuo o cuantificado): sinceramente trabajé con torus antes pero esta vez quiero algo más ...
  • Mundo esférico con movimiento continuo: ¡esto sería genial!

Lo que queremos Los navegadores de los usuarios reciben una lista de coordenadas como (latitud, longitud) para cada objeto en el mapa de superficie esférico; los navegadores deben mostrar esto en la pantalla del usuario y mostrarlos dentro de un elemento web (¿lienzo quizás? esto no es un problema). Cuando las personas hacen clic en el avión, convertimos (mouseX, mouseY) a (lat, lng) y lo enviamos al servidor que tiene que calcular una ruta entre la posición actual del usuario hasta el punto en el que se hizo clic.

Lo que tenemos Comenzamos a escribir una biblioteca Java con muchas matemáticas útiles para trabajar con Matrices de rotación, Cuaterniones, Ángulos de Euler, Traducciones, etc. Lo reunimos todo y creamos un programa que genera puntos de esfera, los representa y se los muestra al usuario dentro de un JPanel. Logramos captar clics y traducirlos a coordenadas esféricas y proporcionar algunas otras funciones útiles como rotación de vista, escala, traducción, etc. Lo que tenemos ahora es como un pequeño motor (muy poco) que simula la interacción del cliente y el servidor. El lado del cliente muestra puntos en la pantalla y capta otras interacciones, el lado del servidor presenta la vista y realiza otros cálculos, como interpolar la ruta entre la posición actual y el punto en el que se hizo clic.

¿Dónde está el problema? Obviamente queremos tener el camino más corto para interpolar entre los dos puntos de ruta . Usamos cuaterniones para interpolar entre dos puntos en la superficie de la esfera y esto pareció funcionar bien hasta que noté que no estábamos obteniendo el camino más corto en la superficie de la esfera:

Círculo equivocado

Pensamos que el problema era que la ruta se calcula como la suma de dos rotaciones sobre los ejes X e Y. Así que cambiamos la forma en que calculamos el cuaternión de destino: obtenemos el tercer ángulo (el primero es la latitud, el segundo es la longitud, el tercero es la rotación sobre el vector que apunta hacia nuestra posición actual) que llamamos orientación. Ahora que tenemos el ángulo de "orientación", giramos el eje Z y luego usamos el vector de resultados como eje de rotación para el cuaternión de destino (puede ver el eje de rotación en gris):

Ruta correcta a partir de 0, 0

Lo que obtuvimos es la ruta correcta (puede ver que se encuentra en un gran círculo), pero llegamos a esto SOLO si el punto de ruta de inicio está en la latitud, longitud (0, 0), lo que significa que el vector de inicio es (sphereRadius, 0 , 0). Con la versión anterior (imagen 1) no obtenemos un buen resultado incluso cuando el punto de inicio es 0, 0, por lo que creo que estamos avanzando hacia una solución, pero el procedimiento que seguimos para obtener esta ruta es un poco "extraño " ¿tal vez?

En la siguiente imagen puede ver el problema que tenemos cuando el punto de partida no es (0, 0), ya que puede ver que el punto de partida no es el vector (esferaRadio, 0, 0), y como puede ver el punto de destino (que se dibuja correctamente) no está en la ruta.

¡La ruta es incorrecta!

El punto magenta (el que se encuentra en la ruta) es el punto final de la ruta girado sobre el centro de la esfera de (-startLatitude, 0, -startLongitude). Esto significa que si calculo una matriz de rotación y la aplico a cada punto de la ruta, tal vez obtenga la ruta real, pero empiezo a pensar que hay una mejor manera de hacerlo.

¿Quizás debería tratar de hacer que el avión atraviese el centro de la esfera y los puntos de ruta, intersecarlo con la esfera y obtener la geodésica? ¿Pero cómo?

Perdón por ser demasiado detallado y tal vez por un inglés incorrecto, ¡pero esto me está volviendo loco!

EDITAR: ¡El código a continuación funciona bien! Gracias a todos:

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
fuente
1
Muestre su código de interpolación / slerp quaternion.
Maik Semder
1
En una nota al margen: incluso los libros pueden contener errores no observados, pero desastrosos. Antes de copiar algo, asegúrese de comprenderlo usted mismo ... solo entonces podrá contar con que sea válido (bueno, a menos que lo haya entendido mal, pero esto es mucho menos probable).
teodron
@MaikSemder agregó la función donde se compila RotationMatrix a partir de la clase Quaternion
CaNNaDaRk
Tal vez el problema está dentro de setRouteDest (doble lat, doble lng) y setRouteStart (doble lat, doble lng). Creo que me falta un ángulo cuando creo el objeto EulerAngles así: EulerAngles tmp = new EulerAngles (Math.toRadians (lat), ???, -Math.toRadians (lng))
CaNNaDaRk
No veo dónde usa "RotationMatrix" para crear el punto girado "p" devuelto por "interpolar". Acabas de configurar "RotationMatrix" desde el cuaternión interpolado, pero no lo usas
Maik Semder

Respuestas:

5

Su problema es puramente bidimensional, en el plano formado por el centro de la esfera y sus puntos de origen y destino. El uso de quaternions en realidad está haciendo las cosas más complejas, porque además de una posición en una esfera 3D, un quaternion codifica una orientación.

Es posible que ya tenga algo para interpolar en un círculo, pero por si acaso, aquí hay un código que debería funcionar.

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
fuente
¡Si! Eso es lo que estoy buscando, este es mi verdadero problema, ¡debo trabajar en el avión que cruza C, destino y fuente! El único problema es que todavía no puedo hacer que funcione ... ¡Pegaré el código y los resultados que obtuve de tu código!
CaNNaDaRk
editado la pregunta. Hay un problema ... ¿quizás traduje mal el código?
CaNNaDaRk
@CaNNaDaRk No veo qué puede estar mal. ¿Son correctos los usos de normalizar (), restar (), escala (), etc. con respecto a los efectos secundarios? ¿Y tllega totalTime? Además, si desea obtener el círculo completo, establezca el tvalor máximo en 2 * pi / angle * totalTimelugar de solo totalTime.
sam hocevar
¡Perfecto! Allí agregué un error estúpido a la función normalizar y, por lo tanto, obtuve una magnitud incorrecta en el vector "v". ¡Ahora todo funciona bien! Gracias de nuevo;)
CaNNaDaRk
3

Asegúrese de que ambos cuaterniones estén en el mismo hemisferio en la hiperesfera. Si su producto punto es menor que 0, entonces no lo son. En ese caso, niega uno de ellos (niega cada uno de sus números), por lo que están en el mismo hemisferio y te darán el camino más corto. Pseudocódigo:

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

Mi respuesta aquí explica en detalle qué niega cada término del cuaternión y por qué sigue siendo la misma orientación, justo al otro lado de la hiperesfera.


EDITAR la función de interpolación debería verse así:

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
fuente
Intenté su código pero obtengo los mismos resultados. En modo de depuración miro por el producto de puntos y estoy seguro de que los dos cuaterniones están en el mismo hemisferio en la hiperesfera. Lo siento, ¿tal vez mi pregunta no es lo suficientemente clara?
CaNNaDaRk
¿Qué quieres decir con "estás seguro de que están en el mismo hemisferio"? si dot> = 0 entonces lo son, de lo contrario no.
Maik Semder
No se trata del hemisferio de su esfera normal, se trata del hemisferio en la hiperesfera, el espacio 4D de quaternion. Tómese el tiempo para leer el enlace, es difícil de explicar en un cuadro de comentarios.
Maik Semder
Eso es lo que digo, puse tu código y calculé el punto. Incluso cuando es> = 0 (así que estoy seguro de que están en el mismo hemisferio) el problema es siempre el mismo: la ruta que obtengo no está en un gran círculo. Creo que el problema está en otro lugar ...? ¿Tal vez debería agregar algún código a la pregunta ...? Editar: leí tu enlace, todavía no creo que el problema esté ahí. También probé el código que me diste, pero aún así obtengo una ruta en un círculo menor.
CaNNaDaRk
Muestre
0

Dado que desea un V3Drespaldo de su interpolador, el enfoque más simple es omitir los cuaterniones por completo. Convierte los puntos de inicio y fin V3Dy slerp entre ellos.

Si insiste en usar quaternions, entonces el quaternion que representa la rotación de Pa Qtiene dirección P x Qy wde P . Q.

Peter Taylor
fuente