在 2D 网格中查找包含点的多边形
我有一个 3D 多边形网格和相应的 2D 多边形网格（实际上来自 UV 贴图）我用来将几何图形映射到二维平面上。给定平面上的一个点，如何有效地找到它所在的多边形，以便将该 2D 点映射回 3D？
我能想到的最好的方法是将多边形存储在二维区间树中，并使用它来获取候选多边形。有没有更简单的方法？
澄清一下，这不适用于着色器。我实际上正在进行 2D 物理模拟并将其渲染在 3D 网格周围。为了绘制每个对象，我需要找出 3D 中的哪个点对应于其真实的 2D 位置。*
I have a 3D polygon mesh and a corresponding 2D polygon mesh (actually from a UV map) which I'm using to map the geometry onto a 2D plane. Given a point on the plane, how can I efficiently find the polygon on which it's resting in order to map that 2D point back into 3D?
The best approach I can think of is to store the polygons in a 2D interval tree, and use that to get candidate polygons. Is there a simpler approach?
To clarify, this is not for a shader. I'm actually taking a 2D physical simulation and rendering it wrapped around a 3D mesh. For drawing each object, I need to figure out what point in 3D corresponds to its real 2D position.*
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我见过的三角形网格的一种方法如下：选择一个三角形，并想象每条边都定义一个半空间。对于给定的边，半空间边界是包含该边的线，并且半空间不包含三角形。选择一条边，其对应的半空间包含您的目标点。然后选择边另一侧的三角形，并重复该过程。
使用此方法，您最终将到达包含目标点的三角形。
这种方法可以说比实现 2D 区间树更简单，尽管搜索效率较低（如果
n是三角形的数量，则为 O(√n) 而不是 O(log n)。此外，它应该适用于多边形网格，只要多边形是凸的。One approach I've seen for triangle meshes goes as follows: choose a triangle, and imagine that each of the sides defines a half space. For a given edge, the half space boundary is the line containing the edge, and the half space does not contain the triangle. Choose an edge whose corresponding half space contains your target point. Then select the triangle on the other side of edge, and repeat the process.
Using this method, you will eventually end up at the triangle that contains your target point.
This method is arguable simpler than implementing a 2D interval tree, although the search is less efficient (if
nis the number of triangles, it is O(√n) rather than O(log n). Also, it should work for a polygon mesh, as long as the polygons are convex.所以，如果我试图实现这个东西，我可能会从所有三角形的全局搜索开始 - 计算每个三角形的 2d 点的重心坐标，找到重心坐标均为正的三角形，并且然后使用它们映射到 3d（将 Stu 位置乘以 3d 点）。我会先这样做，只有当它不够快时我才会尝试更复杂的东西。
如果可以通过三角形而不是二维点进行迭代，那么重心方法可能会足够快。但似乎您在需要映射的任意位置都有一堆二维点，并且这些点在帧与帧之间改变位置？
如果您遇到这种情况，您可能可以通过每帧实施本地更新来获得很大的加速。每个二维点都会记住它在哪个三角形内。将其设置为当前三角形。测试新位置是否在当前三角形内。如果没有，那么您需要将网格移动到最接近目标 2d 点的相邻三角形。每个与边相邻的三角形都由边上的两个公共点加上另一个点组成。找到哪个边相邻三角形的另一个点最接近目标，并将其设置为当前点。然后迭代 - 看起来应该很快就能找到它？您还可以缓存每个三角形的最大大小，因此，如果该点移动了很多，您可以迭代到下一个邻居，而不进行重心计算（最大大小需要是这样的距离，如果您比该距离更远）距任何三角形点的距离都不可能位于三角形内部（这是最大边的长度）。
但正如您在评论中提到的，您可能会遇到具有凹面、孔或单独连接组件的网格的问题，在这些情况下您可能会陷入局部最小值。有几种方法可以解决这个问题。我认为最简单的是保留所有访问过的三角形的列表（可能作为三角形上的标志，向量或设置<三角形索引>）并拒绝重新访问三角形。如果您发现您已经访问了当前三角形的所有邻居，则返回到全局搜索。此类失败可能并不常见，因此不会对您的表现造成太大影响。
这种每帧更新可以非常快，甚至可能是计算初始包含三角形的一种不错的方法 - 只需选择一个随机三角形并从那里开始（从检查所有 n 个三角形更改为仅检查那些大约在一个三角形中的三角形）直线到达目标）。如果速度不够快，您可以做的是保留二维网格点的 kd 树（或类似的东西）以及每个网格点的单个接触三角形索引。要为迭代提供种子，请在 kd 树中找到距离目标 2d 点最近的点，将相邻三角形设置为当前三角形，然后进行迭代。
So, if I were trying to just get the thing implemented, I'd probably start with a global search of all triangles - compute the barycentric coordinates of that 2d point for each triangle, find the triangle where the barycentric coordinates are all positive, and then use those to map to 3d (multiply the stu position by the 3d points). I'd do this first, and only if it's not fast enough would I try something more complex.
If it's possible to iterate by triangle rather than by 2d points, then the barycentric method would probably be fast enough. But it seems like you've got a bunch of 2d points at arbitrary positions that need to be mapped, and the points change position from frame to frame?
If you've got this kind of situation, you could probably get a big speedup by implementing a local update per frame. Each 2d point would remember which triangle it was within. Set that as the current triangle. Test if the new position is within the current triangle. If not, then you want to walk the mesh to the adjacent triangle which is closest to the target 2d point. Each edge-adjacent triangle is composed of the two common points on the edge, plus another point. Find which edge-adjacent triangle's other point is closest to the target, and set that as current. Then iterate - seems like it should find it pretty quickly? You could also cache a max size for each triangle, so if the point has moved a lot you can just iterate to the next neighbor without doing the barycentric computation (the max size would need to be the distance such that if you are farther than that distance from any triangle point there is no chance you're inside the triangle. This is the length of the largest edge).
But as you mention in your comments, you can run into problems with meshes that have concavities, holes, or separate connected components, where you may fall into a local minimum. There are a couple of ways to deal with this. I think the simplest is to keep a list of all visited triangles (maybe as a flag on the triangle, vector< bool > or set< triangle index >) and refuse to revisit a triangle. If you find that you've visited all the neighbors of your current triangle, then fall back to a global search. Such failures are likely to be uncommon, so it shouldn't hurt your performance too much.
This kind of per-frame updating can be very fast, and might even be a decent approach for computing the initial containing triangles - just choose a random triangle and walk from there (changes from checking all n triangles to only those that are in roughly a straight line to the target). If it's not fast enough, what you could do is keep a k-d tree (or something similar) of the 2d mesh points as well as a single touching triangle index for each mesh point. To seed the iteration, find the closest point to the target 2d point in the k-d tree, set the adjacent triangle to be current, and then iterate.