6

给定两个 3d 对象，我怎样才能找到一个是否适合第二个（并找到对象在容器中的位置）。

对象应平移和旋转以适合容器 - 但不得进行其他修改。

其他并发症：

  1. 相同的情况 - 但要寻找最合适的解决方案，即使它不是适当的匹配（最小化不适合容器的对象的体积）

  2. 支持弹性物体 - 找到最佳配合，同时最大限度地减少物体中的“扭曲”

这是一个非常普遍的问题——我不希望有一个完整的解决方案。任何指向相关论文\文章\图书馆\工具的指针都会很有用

4

5 回答 5

0

考虑目标对象中的一个多边形（三角形）。对于这个多边形，在另一个几何（源）中找到等效的多边形，即。边长、边角、面积都应该相同。如果只有一个匹配项，请找到以这种方式改变顶点的刚性变换矩阵：X' = M*X。由于X'ANDX对于匹配多边形上的所有点都是已知的，因此这应该可以通过线性代数实现。

如果要在多边形的顶点之间进行一对一映射，请以相同的顺序遍历多边形的边缘，并制作一个查找表，将每个顶点一个一个多边形映射到另一个多边形的一个顶点。如果您有 3d 对象的半边数据结构，这将大大简化此过程。

如果找到多个匹配的多边形，则从这两个点遍历源多边形，并继续将它们的相邻多边形与目标多边形匹配。继续直到其中一个中断，之后您可以执行与单匹配版本相同的步骤。

这里列出了更严肃的解决方案，但我认为上面的方法也可以。

于 2014-02-03T23:08:25.743 回答
0

这似乎是一个相当困难的问题。可能的方法是采用一些启发式方法来建议转换，然后检查它是否好。如果转换仅将对象稍微移出内部（例如在一个部分），则稍微调整以适应转换并对其进行测试。如果对象“大量”出局（例如，在同一/两侧的所有轴上），则进行新的启发式猜测。

只是启发式的一般想法。对具有相同像素大小的对象进行光栅化。它可以是对象体积的八叉树。制作像素之间的连接图。检查图之间的子图同构。如果有子图，则该位置用于测试。

这种方法还支持 90 度旋转。

甚至可以在图表上进行一些测试。如果子图的所有体积邻居都在更大的图中，则对象在其中。

一般来说，这是“改进的”边界框方法。

于 2013-01-13T13:21:04.103 回答
0

这是一种可能不太理想的方法。

您可以尝试固定 1 个形状的位置（在 3D 空间中）。将另一个形状放在该形状的顶部。然后创建将形状中的一个点连接到另一个形状中的点的链接。然后模拟当链接同样拉紧时会发生什么。使不固定的点旋转并平移，直到它稳定为止。

如果配合足够松，您可以只使用 3 个链接（3D 链接的最低数量）并尝试所有可能的组合。但是，为了更紧密地配合，您需要更多的链接，也许足以将它们放置在形状的每个点上，并且点数最少。这意味着您将有一些方法来确定如何放置链接，这并非易事。

于 2013-01-13T00:07:18.550 回答
0

另一种解决方案是在两个对象上投影相同数量的点，并在点集上进行最小二乘最佳拟合。点集的排序可能不会相同，因此在最适合的最小二乘和点的重新排序之间进行迭代，以便两个对象上的点接近相同的顺序。这个方程的发展是很多代数，但在概念上并不复杂。

于 2014-02-03T19:24:50.820 回答
0

多汁的问题！正如计算几何中的典型情况一样，这个问题可能非常复杂，因为几何抽象不匹配。对于各种 if-else 案例等。但是选择正确的抽象，解决方案变得微不足道，只有很少的子案例。

计算你的形状的距离变换，瞧！您的解决方案是微不足道的。请允许我详细说明。

网格（像素）上形状的距离图编码形状边界上最近点到该像素的距离。它可以在两个方向向外或向内计算到形状中。在这个问题中，向外的距离图就足够了。

  • 步骤 1：计算两个形状 D_S1、D_S2 的距离图
  • 第 2 步：减去距离图。差异 = D_S1-D_S2
  • 第 3 步：如果 Diff 只有正值。然后您的形状可以相互包含（+ve => S1 大于 S2 -ve => S2 大于 S1）如果 Diff 具有正值和负值，则形状相交。

你有它。享受 ！

于 2019-01-29T01:51:08.673 回答