查找包含点的2D网格中的多边形

Question

我有一个3D多边形网格和相应的2D多边形网格（实际上来自UV map），我正用它来将几何图形映射到2D平面上。考虑到飞机上的一个点，我怎样才能有效地找到它所在的多边形，以便将该2D点映射回3D？

我能想到的最佳方法是将多边形存储在2D区间树中，并使用它来获取候选多边形。有一个更简单的方法吗？

为了澄清，这不是着色器。我实际上正在进行2D物理模拟并将其渲染为3D网格。对于绘制每个对象，我需要弄清楚3D中的哪个点对应于它的真实2D位置。*

Answer 1

我看过的三角形网格的一种方法如下：选择一个三角形，想象每个边定义了一半的空间。对于给定的边，半空间边界是包含边的线，半空间不包含三角形。选择一个边缘，其相应的半空间包含您的目标点。然后选择边缘另一侧的三角形，然后重复该过程。

使用这种方法，您最终会到达包含您的目标点的三角形。

这种方法比实现2D间隔树有争议简单，尽管搜索的效率较低（如果n是三角形的数量，它是O（√ N），而不是O（log n）的，另外，它应该只要多边形凸出来就可以工作

Answer 2

所以，如果我试图刚刚实现的东西，我可能会开始全局搜索所有三角形 - 计算重心的坐标每个三角形的2d点，找出重心坐标都为正的三角形，然后用它们映射到3d（把3d位置乘以stu位置），我会先做，并且只有在速度不够快我会尝试更复杂的东西吗？

如果可以通过三角形而不是2d点进行迭代，那么重心方法可能会足够快。但是似乎你在任意位置有一堆需要被映射的2d点，并且这些点会在帧之间改变位置？

如果你有这种情况，你可能会通过实现每帧本地更新大大加速。每个2d点都会记住它所在的三角形。将其设置为当前三角形。测试新位置是否在当前三角形内。如果不是，那么你需要将网格移动到最接近目标2d点的相邻三角形。每个边缘相邻的三角形由边上的两个公共点和另一个点组成。查找哪个边缘相邻三角形的其他点最接近目标，并将其设置为当前。然后迭代 - 似乎它应该很快找到它？你也可以为每个三角形缓存一个最大尺寸，所以如果这个点已经移动了很多，你可以迭代到下一个邻居而不进行重心计算（最大尺寸需要是这样的距离，如果你比那更远距离任何三角点的距离都不可能在三角形内部，这是最大边缘的长度）。

但正如您在评论中提到的那样，您可能会遇到具有凹陷，孔洞或单独连接组件的网格问题，您可能会陷入局部最小值。有几种方法可以解决这个问题。我认为最简单的方法是保留所有访问过的三角形列表（可能是三角形上的一个标记，或者设置<三角形索引>），并拒绝重新访问三角形。如果您发现您访问了当前三角形的所有邻居，则可以返回到全局搜索。这种失败可能不常见，因此它不应该太多地损害你的表现。

这种每帧更新可以非常快，甚至可能是一个体面的方法来计算初始包含三角形 - 只需选择一个随机的三角形并从那里走（从检查所有n个三角形到只有那些与目标大致成直线）。如果速度不够快，你可以做的是保持2D网格点的k-d树（或类似物）以及每个网格点的单个触摸三角形索引。要对迭代进行种子处理，请在k-d树中找到距离目标2d点最近的点，将相邻三角形设置为当前值，然后进行迭代。