19

我有一个 3D 实体，表示为一组多面体凸包的并集。（或单个凸面，如果这会使事情变得更容易。）我想将该实体近似为一组球体的并集，以最小化集合中的球体数量和近似误差的方式。（后一个目标故意含糊不清：任何合理的误差度量都可以。同样，目标组合的方式也悬而未决；可以限制球体的数量或误差度量，或者两者的某些功能可以最小化。我不想把自己指定到角落里。）

近似值不需要完全包含或完全包含在原始集合中。每个球体可以具有任意半径。

这感觉就像是 NP 完全问题，并且在任何情况下都不太可能使用精确的方法，所以我假设解决方案在于随机优化领域。感觉 k-means 的某些变体可能适合（将未覆盖的位置分配给它们最近的球体，并改进球体以覆盖其中的一些），但我不确定如何处理多重覆盖的位置，或者如何找到局部的，不一定覆盖所有内容，即使对于单个球体也是最佳的。此外，对于迭代方法而言，效率很重要，而进行 3D 布尔运算不会是高效的。

4

4 回答 4

8

问题不简单，之前已经研究过了。中心概念是中轴，它可以被看作是由球的无限结合来表示一个对象。解决您的问题的关键论文是：

“权力外壳、球的结合和中轴变换。” 妮娜·阿门塔、崔成熙、拉维·克里希纳·科鲁里。计算几何。第 19 卷，第 2-3 期，2001 年 7 月，第 127-153 页。（期刊链接。）

足球   贝壳球
（图片来源：从点云到电力地壳。）

第二篇论文是

Cazals、Frédéric 等人。“用于收集球的贪婪几何算法，以及在几何近似和分子粗粒度中的应用。” 计算机图形学论坛。卷。33. No. 6. 2014. ( PDF下载.)

他的第一句话是“选择最接近 3D 对象的球是一个不平凡的问题。”！它们的主要应用是分子模型，这可能与您的兴趣相去甚远。

于 2015-05-27T23:05:21.423 回答
3

嗯，到目前为止，我最好的想法涉及支持向量机。将您的对象变成对象内部和对象表面上的一大堆（可能是均匀间隔的）点。使用线性内核训练 SVDD 模型（有关 SVDD 实现，请参见libsvm ）。然后，模型的决策函数表示由模型（和 rho）的支持向量定义的隐式曲面。降低成本会给你更多的支持向量，提高成本会让你更少。

不幸的是，SVM 的本质是附近的支持向量所覆盖的区域会，呃，“blob”在一起，有点像这样：

在此处输入图像描述

（对不起，我对 SVM 的直觉完全是几何/视觉的。）

现在，您没有漂亮的清晰球体，但是（大量挥手！）希望算法为球体选择了有用的中心分布。

最后，您可以构造一个函数，将误差计算为所有这些点上球心半径的函数。然后只需将其输入非线性优化器并告诉它最小化。巴姆。

如果您愿意投入更多的 CPU 能力，您可以在该层之上运行另一层错误最小化，该层针对不同的支持向量成本重新运行上述整个过程，试图最小化错误和成本的某种组合。（也许error/cost。）

于 2015-05-20T05:21:45.823 回答
1

这就是我想出的。这种方法更像是一种迭代的 3D 布尔运算，因此它可能不是您想要的。表面似乎更难，所以我集中精力。

概述

基本上在形状内部的位置添加球体，以最大限度地覆盖表面。我们将球体转换为有符号字节值的 3D 数组。这些值是点，将被球体吞噬。我们在对象内部一次添加一个球体，然后在不同方向上扩大/缩小它以“吃”尽可能多的点。目标是在每个球体上获得尽可能多的积分。积分是通过将球体区域中的积分相加来获得的。通过添加每个球体，我们计算然后将该区域计算为已使用并将数组值设置为 0。

  (A)       (B) ZZZZZZ   (C) ZZZZZZ   (D) ZZZZZZ   (E) ZZZZZZ   (F) ZZZZZZ   
     /\         ZX33XZ       ZX33XZ       ZX33XZ       ZX33XZ       ZX33XZ   
    /  \       ZX3223XZ     ZX3223XZ     ZX##23XZ     ZX  ##XZ     ZX    XZ  
   /    \     ZX321123XZ   ZX321123XZ   ZX####23XZ   ZX  ####XZ   ZX      XZ 
  |      |   ZX32111123XZ ZX32111123XZ ZX######23XZ ZX  ######XZ ZX        XZ
  |      |   ZX32111133XZ ZX32111133XZ ZX######23XZ ZX  ######XZ ZX        XZ
  |      |   ZX32222223XZ ZX##222223XZ ZX3####223XZ ZX3  ####3XZ ZX3     ##XZ
  |------|   ZX33333333XZ ZX##333333XZ ZX33##3333XZ ZX33  ##33XZ ZX33    ##XZ
   X= -1     ZXXXXXXXXXXZ ZXXXXXXXXXXZ ZXXXXXXXXXXZ ZXXXXXXXXXXZ ZXXXXXXXXXXZ
   Y= -2     ZZZZZZZZZZZZ ZZZZZZZZZZZZ ZZZZZZZZZZZZ ZZZZZZZZZZZZ ZZZZZZZZZZZZ

(A) 我们要填充的形状。（此处使用 2D，但 3D 类似）

(B) 在点的 3D 网格中转换形状。表面获得最大的数字，当你工作到中心时，数字会落在低正数上（比如 1）；形状外得到负数；深层内部得到 1

(C) 添加一个小球体。（我们会种植它）

(D) 扩大球体，直到我们吞噬最大点数

(E) 添加下一个球体并使其生长。

(F) 添加另一个球体。这个很小。

过程

5）首先将形状分解为 3D 块分辨率。

10）然后给表面周围的块最多的“点”。当您向内或向外移动时，块实际接触表面的高点和低点。当你向外走时，这些点应该很快变成负数，因为这将防止突出的球体。当您从表面向内移动时，这些点应该设置为 1，以便中心区域全为 1。这些点可以以不同的方式设置以产生不同的结果。

15) 在球体外部的形状内边缘上找到一个位置。虽然不需要靠近边缘，但它确实最小化了搜索区域。如果找不到位置，请转到 80。如果找不到附近的位置

20）在未被覆盖的形状内绘制一个半径为零的球体

25）向上/向下移动球体直到点最大化（模拟退火）

26）将球体移入/移出，直到点最大化

27）向左/向右移动球体，直到点最大化

28）向上/向下移动球体的顶部，直到点最大化（模拟退火/爬山）

29）向上/向下移动球体的底部，直到点最大化

30）将球体的左侧移入/移出，直到点最大化

31）将球体的右侧移入/移出，直到点最大化

32）将球体的前部移入/移出，直到点最大化

50) 如果 25-32 有任何变化，请重复 (转到 25)

70) 从最后添加的球体中减去点。将内部值（正数）的所有值设置为零，不要调整外部值（负数）。转到 15。

80）（可选）填补内部空白。基本上访问每个元素以确保它小于或等于 0。如果为正，则使用该元素转到 20。否则，如果没有找到，则转到 85。注意：所有外部值都应该是负数，而球体中的所有内部值都应该是 0。

85) 完成

笔记

  • 由于会有一个值网格，因此 1000x1000x1000 的工作空间将消耗 1GB。
  • 不是一个精确的解决方案
  • 可能需要大量计算才能获得更高的分辨率。
  • 为了提高效率，较小的球体可以预先记录它们的像素范围，这样就不需要为每次迭代计算球体。
  • 可以先完成较低分辨率（即 500x500x500）的版本，然后将球体的位置和大小应用到更大的 1000x1000x1000。也可以解决非常大的形状子部分。
于 2015-06-03T15:34:53.050 回答
0

一个好的开始是开发一种算法来：

1) 求内接球体的最大半径。

2）然后考虑减量

3) 用多面体近似减去体积。

4) 将该多面体细分为更小（更精细）的多面体。

5) 重做步骤 1。

可能会有一些变化，但它似乎回答了你的问题。如您所见，误差函数随着球体数量的增加而减小，因此您不能同时最小化两者：这是一种权衡。但是您可以修复一个并尝试优化另一个，例如将误差函数修复为可接受的容差，并最大限度地减少球体的数量，反之亦然。

于 2015-05-19T20:48:57.837 回答