Маршруты на поверхности сферы - Найти геодезические?

Я работаю с некоторыми друзьями над браузерной игрой, где люди могут перемещаться по 2D-карте. Прошло уже почти 7 лет, и до сих пор люди играют в эту игру, поэтому мы думаем о том, как дать им что-то новое. С тех пор игровая карта была ограниченной плоскостью, и люди могли переходить от (0, 0) к (MAX_X, MAX_Y) с квантованными приращениями X и Y (просто представьте, что это большая шахматная доска).
Мы считаем, что пришло время дать ему другое измерение, поэтому всего пару недель назад мы начали задумываться о том, как игра может выглядеть с другими сопоставлениями:

• Неограниченная плоскость с непрерывным движением: это может быть шагом вперед, но я все еще не убежден.
• Тороидальный мир (непрерывное или квантованное движение): раньше я искренне работал с тором, но на этот раз я хочу чего-то большего ...
• Сферический мир с непрерывным движением: это было бы здорово!

Что мы хотим Пользователям браузеров предоставляется список координат, таких как (широта, долгота) для каждого объекта на карте сферической поверхности; браузеры должны затем показать это на экране пользователя, отображая их внутри веб-элемента (возможно, canvas - это не проблема). Когда люди нажимают на плоскость, мы конвертируем (mouseX, mouseY) в (lat, lng) и отправляем его на сервер, который должен вычислить маршрут между положением текущего пользователя и точкой нажатия.

Что у нас есть Мы начали писать библиотеку Java с множеством полезных математических функций для работы с матрицами вращения, кватернионами, углами Эйлера, переводами и т. Д. Мы собрали все это вместе и создали программу, которая генерирует точки сфер, отображает их и показывает их пользователю. внутри JPanel. Нам удалось поймать щелчки и преобразовать их в сферические координаты и предоставить некоторые другие полезные функции, такие как вращение представления, масштабирование, перевод и т. Д. Теперь у нас есть небольшой (действительно очень маленький) движок, который имитирует взаимодействие клиента и сервера. Клиентская сторона показывает точки на экране и отслеживает другие взаимодействия, серверная сторона отображает представление и выполняет другие вычисления, такие как интерполяция маршрута между текущей позицией и выбранной точкой.

В чем проблема? Очевидно, что мы хотим иметь кратчайший путь для интерполяции между двумя точками маршрута . Мы используем кватернионы для интерполяции между двумя точками на поверхности сферы, и это, казалось, работало нормально, пока я не заметил, что мы не получили кратчайший путь на поверхности сферы:

Мы, хотя проблема заключалась в том, что маршрут рассчитывается как сумма двух поворотов вокруг оси X и Y. Таким образом, мы изменили способ вычисления кватерниона назначения: мы получаем третий угол (первый - широта, второй - долгота, третий - поворот вокруг вектора, который указывает на нашу текущую позицию), который мы назвали ориентацией. Теперь, когда у нас есть угол «ориентации», мы поворачиваем ось Z, а затем используем вектор результата в качестве оси вращения для целевого кватерниона (ось вращения показана серым цветом):

То, что мы получили, это правильный маршрут (вы можете видеть, что он лежит на большом круге), но мы доберемся до него ТОЛЬКО если начальная точка маршрута находится на широте, долготе (0, 0), что означает, что начальный вектор - (phereRadius, 0 0). В предыдущей версии (изображение 1) мы не получаем хороший результат, даже если начальная точка равна 0, 0, поэтому я думаю, что мы движемся к решению, но процедура, которой мы следуем, чтобы получить этот маршрут, немного «странна» " может быть?

На следующем изображении вы видите проблему, которую мы получаем, когда начальная точка не равна (0, 0), поскольку вы можете видеть, что начальная точка не является вектором (phereRadius, 0, 0), и как вы можете видеть точку назначения (который правильно нарисован!) нет на маршруте.

Пурпурная точка (лежащая на маршруте) - это конечная точка маршрута, повернутая вокруг центра сферы (-startLatitude, 0, -startLongitude). Это означает, что если я вычислю матрицу вращения и применил ее к каждой точке маршрута, возможно, я получу реальный маршрут, но я начинаю думать, что есть лучший способ сделать это.

Может быть, я должен попытаться проложить самолет через центр сферы и точки маршрута, пересечь его со сферой и получить геодезическую? Но как?

Извините за то, что я слишком многословен и, возможно, за неправильный английский, но эта вещь просто поражает меня!

РЕДАКТИРОВАТЬ: Код ниже работает просто отлично! Спасибо всем:

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

Ваша проблема чисто двумерная, в плоскости, образованной центром сферы и вашими точками отправления и назначения. Использование кватернионов на самом деле усложняет ситуацию, потому что помимо положения в трехмерной сфере кватернион кодирует ориентацию.

Возможно, вам уже есть, что интерполировать по кругу, но на всякий случай вот код, который должен работать.

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

Убедитесь, что оба кватерниона находятся в одном полушарии на гиперсфере. Если их скалярное произведение меньше 0, то это не так. В этом случае отрицание одного из них (отрицание каждого из его чисел), так что они находятся в одном полушарии и даст вам кратчайший путь. псевдокод:

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

Мой ответ здесь подробно объясняет, что делает отрицание каждого члена кватерниона и почему он все еще имеет ту же ориентацию, просто на другой стороне гиперсферы.

РЕДАКТИРОВАТЬ интерполяционная функция должна выглядеть так:

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

Поскольку вы хотите получить V3Dответ от своего интерполятора, самый простой подход - полностью пропустить кватернионы. Конвертируйте начальную и конечную точки V3Dи выполняйте переход между ними.

Если вы настаиваете на использовании кватернионов , то кватернион , представляющий вращение от Pк Qимеет направление P x Qи wиз P . Q.