我有一个 3D 多边形网格和一个相应的 2D 多边形网格（实际上来自UV 贴图），用于将几何图形映射到 2D 平面上。给定平面上的一个点，我如何有效地找到它所在的多边形，以便将该 2D 点映射回 3D？
我能想到的最好方法是将多边形存储在 2D 区间树中，并使用它来获取候选多边形。有没有更简单的方法？
澄清一下，这不适用于着色器。我实际上是在进行 2D 物理模拟并将其渲染为围绕 3D 网格。为了绘制每个对象，我需要弄清楚 3D 中的哪个点对应于它的真实 2D 位置。*
问问题
1217 次
2 回答
0
所以，如果我只是想实现这个东西，我可能会从所有三角形的全局搜索开始 - 计算每个三角形的那个 2d 点的重心坐标，找到重心坐标都是正的三角形，然后然后使用这些映射到 3d（将 stu 位置乘以 3d 点）。我会先做这个，只有当它不够快时，我才会尝试更复杂的东西。
如果可以通过三角形而不是二维点进行迭代，那么重心方法可能就足够快了。但似乎您在需要映射的任意位置有一堆 2d 点，并且这些点的位置会随着帧的变化而变化？
如果您遇到这种情况，您可能会通过实现每帧的本地更新来获得很大的加速。每个 2d 点都会记住它在哪个三角形内。将其设置为当前三角形。测试新位置是否在当前三角形内。如果不是，那么您希望将网格移动到最接近目标 2d 点的相邻三角形。每个边相邻三角形由边上的两个公共点加上另一个点组成。找出哪个边相邻三角形的另一个点最接近目标，并将其设置为当前。然后迭代 - 似乎它应该很快找到它？您还可以为每个三角形缓存一个最大尺寸，
但是正如您在评论中提到的那样，您可能会遇到具有凹面、孔或单独连接组件的网格的问题，您可能会陷入局部最小值。有几种方法可以解决这个问题。我认为最简单的方法是保留所有已访问三角形的列表（可能作为三角形上的标志，vector< bool > 或 set< triangle index >）并拒绝重新访问三角形。如果您发现您已经访问了当前三角形的所有邻居，则回退到全局搜索。这样的失败可能并不常见，所以它不应该对你的表现造成太大的伤害。
这种每帧更新可以非常快，甚至可能是计算初始包含三角形的一种不错的方法 - 只需选择一个随机三角形并从那里步行（从检查所有 n 个三角形更改为仅检查大约 a直线到目标）。如果速度不够快，您可以做的是保留 2d 网格点的 kd 树（或类似的东西）以及每个网格点的单个接触三角形索引。为迭代播种，在 kd 树中找到最接近目标 2d 点的点，将相邻三角形设置为当前，然后进行迭代。
于 2013-01-09T11:28:02.560 回答
0
我见过的三角形网格的一种方法如下：选择一个三角形，并想象每个边定义一个半空间。对于给定的边，半空间边界是包含边的线，而半空间不包含三角形。选择一条边，其对应的半空间包含您的目标点。然后选择边缘另一侧的三角形，并重复该过程。
使用此方法，您最终将到达包含目标点的三角形。
这种方法可以说比实现二维间隔树更简单，尽管搜索效率较低（如果n是三角形的数量，它是 O(√n) 而不是 O(log n)。此外，它应该适用于多边形网格，只要多边形是凸的。
于 2010-09-08T14:53:39.807 回答