在一个三维地形，鉴于3D线，寻找交叉点处的行和地形之间 [英] On a 3D Terrain, Given a 3D Line, Find the Intersection Point Between the Line and the Terrain

问题描述

我有三维地形的网格，每个坐标（X，Y，Z）每个网格是众所周知的。现在，我有一个单调递增/递减线，它的起点也是已知的。我想找到的地步地形和线路满足。该算法做什么？

I have a grid of 3D terrain, where each of the coordinate (x,y,z) of each grid are known. Now, I have a monotonously increasing/ decreasing line, which its start point is also known. I want to find the point where the terrain and the line meets. What is the algorithm to do it?

我能想到的是存储在三维地形的协调 n×n个矩阵。然后，我会segmentize根据地形网格线。然后我会说是最接近线网格开始，然后尝试计算该飞机是否与线相交，如果是，那么得到的坐标和出口。如果没有，那么我会继续到下一段。

What I can think of is to store the coordinate of the 3D terrain in a nxn matrix. And then I would segmentize the line based on the grid in the terrain. I would then start with the grid that is the nearest to the line, and then try to compute whether that plane intersects with the line, if yes, then get the coordinate and exit. If no, then I would proceed to the next segment.

不过是我的算法是最好的，或者最优化的解决方案？或者是有一个已经做到这一点的任何现有的库

But is my algorithm the best, or the most optimum solution? Or is there any existing libraries that already do this?

推荐答案

不直接和优化，只是一些提示：

Not directly and optimisation, just a few hints:

如果您的网格是很大，它可能是值得的建设的八叉树从地形节点上，您必须检查你对线。这可以是因为只有您的射线在穿过必须考虑的叶节点在一个巨大的网格（像512 * 512 ndoes）更有效。

If your grid is large, it might be worthwhile to build an octree from your terrain in order to quickly reduce the number of grid nodes you have to check your line against. This can be more efficient in a huge grid( like 512*512 ndoes) since only the leafnodes your ray is passing through have to be considered.

此外，八叉树可以被用作一种手段，以决定网格的至极部件是可见的，因此具有要被绘制，通过检查该离开节点都在视锥

Additionally, the Octree can be used as a means to decide wich parts of your grid are visible and therefore have to be drawn, by checking which leave-nodes are in the viewing frustum.

有是一个catch，虽然：构建八叉树已经提前完成，服用一段时间后，和树是静态的。它不能easyly修改后，它一直constructes，因为在一个节点的修改可能会影响其他几个节点，不一定是相邻的。

There is a catch, though: building the Octree has to be done in advance, taking some time, and the tree is static. It can not be easyly modified after it has been constructes, since a modification in one node might affect several other nodes, not necessarily adjacent ones.

不过，如果你不这样做计划改造的电网一旦建立八叉树会有所帮助。

However, if you do not plan to modify your grid once it is created an octree will be helpful.

更新

现在，我明白你计划如何存储你的网格，我相信空间分割会找到交线的近邻的efficent方式。

Now that i understand how you are planning to store your grid, i believe space partitioning will be an efficent way to find the nearest neighbour of the intersection line.

线性查找最近的邻居有O（N）的运行复杂性，同时空间分区appoaches有一个平均运行的复杂性，如果为O（log N）。

Finding the nearest Neighbour linearly has a runtime complexity of O(N), while space-partitioning appoaches have an average runtime complexity if O(log N).

这篇关于在一个三维地形，鉴于3D线，寻找交叉点处的行和地形之间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！