球体表面的路线 – find测地线?

我正在和一些基于浏览器的游戏的朋友一起工作,人们可以在2D地图上移动。 已经差不多7年了,人们仍然玩这个游戏,所以我们正在想办法给他们一些新的东西。 从那时起,游戏地图是一个有限的平面,人们可以从(0,0)移动到(MAX_X,MAX_Y)量化的X和Y增量(想象它是一个大棋盘)。
我们相信现在是时候给它另一个维度,就在几个星期前,我们开始怀疑游戏如何与其他映射看起来:

  • 持续运动的无限飞机:这可能是一个进步,但我仍然不相信。
  • 环形世界(连续的或量化的运动):真诚的我曾与环面,但这次我想要更多的东西…
  • 连续运动的球形世界:这将是伟大的!

我们想要的东西用户浏览器给出了球面曲线图上每个对象的坐标列表(纬度,经度) 浏览器必须在用户的屏幕上显示出来,并将它们放在一个web元素中(canvas可能不是问题)。 当人们点击飞机时,我们将(mouseX,mouseY)转换为(lat,lng)并将其发送到服务器,该服务器必须计算当前用户位置到点击点之间的路线。

我们有什么我们开始编写一个有许多有用math的Java库来处理旋转matrix,四元数,欧拉角,翻译等等。我们把它们放在一起,创建一个生成球点的程序,渲染它们并将它们展示给用户在一个JPanel里面。 我们设法捕捉点击并将它们翻译成球形的坐标,并提供一些其他有用的function,如视图旋转,缩放,翻译等等。我们现在所拥有的就像是一个模拟客户端和服务器交互的引擎。 客户端在屏幕上显示点并捕获其他交互,服务器端呈现视图并执行其他演算,如插入当前位置和点击点之间的路线。

哪里有问题? 显然我们想要在两个路由点之间插入 最短path 。 我们使用四元数来插入球体表面上的两点之间,这似乎工作正常,直到我注意到我们没有得到球体表面上的最短path:

错误的圈子

我们虽然问题是路线计算为绕X轴和Y轴的两个旋转之和。 所以我们改变了计算目标四元数的方式:我们得到第三个角度(第一个是纬度,第二个是经度,第三个是关于指向我们当前位置的向量的旋转),我们称之为方向。 现在我们有了“方向”角度,我们旋转Z轴,然后使用结果vector作为目标四元数的旋转轴(您可以看到旋转轴为灰色):

正确的路线从0,0开始

我们得到的是正确的路线(你可以看到它放在一个大圆圈内),但是如果起始路线点在纬度,经度(0,0),这意味着起始vector是(sphereRadius,0 ,0)。 对于之前的版本(图1),即使启动点是0,0,我们也没有得到一个好的结果,所以我认为我们正在朝着一个解决scheme迈进,但是我们遵循的过程是有点“奇怪的“ 也许?

在下图中,当起点不是(0,0)时,您可以看到我们得到的问题,您可以看到起点不是(sphereRadius,0,0)vector,并且您可以看到目标点(正确绘制!)不在路线上。

路线不正确!

洋红色点(放置在路线上的点)是围绕(-startLatitude,0,-startLongitude)球体中心旋转的路线终点。 这意味着如果我计算一个旋转matrix,并将其应用到路线上的每一个点,也许我会得到真正的路线,但我开始认为有一个更好的方法来做到这一点。

也许我应该试图让飞机通过球体的中心和路线点,与球体相交并获得测地线? 但是,如何?

对不起,因为方式太冗长,也许是不正确的英语,但这东西正在吹我的脑海!

编辑:下面的代码工作得很好! 感谢大家:

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); px = cosLat*Math.cos(radLng); py = cosLat*Math.sin(radLng); pz = 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,那么他们不是。 在这种情况下,否定其中的一个(否定每个数字),所以它们在同一个半球上,并且会给你最短的path。 伪代码:

 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和slerp。

如果你坚持使用四元数,那么表示从PQ的旋转的四元数的方向是P x QwP . Q P . Q