algorithm - 部分填充多边形网格的算法

Question

概述：
我有一个由 3D 多边形网格表示的简单塑料沙箱。在将特定量的水倒入沙箱后，我需要能够确定水位。

• 倒水时，水从上方均匀分布
• 没有流体模拟，水倒得很慢
• 它需要快速

问题：
我可以使用什么样的技术/算法来解决这个问题？

我不是在寻找可以执行此操作的程序或类似程序，只是算法-我将执行此操作。

Answer 1

只是一个想法：

首先，您计算所有鞍点。离散莫尔斯理论或拓扑持久性等工具可能在这里很有用，但我对它们知之甚少，无法确定。接下来，您迭代所有鞍点，从最低点开始，并计算水开始穿过该点的时间点。这是两个相邻盆地的较浅盆地（就体积与表面积而言）达到与该鞍点高度相匹配的水平的时间。从那时起，倾倒在该表面上的水将流向另一个盆地，并改为增加其水位，直到两个盆地达到相等的水位。之后，它们将被视为一个单独的盆地。在此过程中，您可能必须更正到达其他鞍点的时间，因为与盆地相关的区域会发生变化。您按时间增加的顺序进行迭代，而不是增加高度（例如 使用带有减少键操作的堆）。一旦最后一对盆的高度相等，就完成了；之后只剩下一个盆地。

总体而言，这为您提供了一系列“有趣”的时间，其中事情发生了根本性的变化。在这两者之间，问题将更加局部，因为您只需考虑单个盆地的形状即可计算其水位。在这个局部问题中，您知道该盆地中包含的水量，因此您可以例如使用二分法来找到合适的水位。相邻的“有趣”时间可能会为您的二等分提供有用的终点。

要计算三角形多面体的体积，可以使用 3D 版本的鞋带公式：对于每个三角形，取其三个顶点并计算它们的行列式。将它们加起来除以 6，就得到了封闭空间的体积。确保所有三角形的方向一致，即全部从内部看或全部从外面看。选择决定整体标志，试试看哪个是哪个。

请注意，您的问题可能需要细化：当盆地中的水位达到完全相同高度的两个鞍点时，水流向哪里？我猜，如果没有流体模拟，这并没有很好的定义。你可以争辩说它应该在所有相邻的盆地之间平均分配。您可能会争辩说，这种情况不太可能发生在真实数据中，因此可以任意选择一个邻居，这意味着这个鞍点的高度比其他鞍点的高度要小得多。或者你可以想出一些其他的解决方案。如果您对此案例感兴趣，那么您可能需要澄清您的期望。

Answer 2

一个简单的解决方案浮现在脑海中：通过不同高度的水进行二进制搜索，计算所含水的体积。即从沙箱深度D的水高度的上估计开始。请注意，由于沙子是多孔的，因此最大体积将是装满水的盒子；在我们假设的后院里，任何更多的水都会喷回到草丛中。另请注意，这意味着您无需担心解决方案中的鞍点或多个水位；同样，我们假设这里是普通的多孔沙子，而不是由岩石构成的山脉。计算高度 D 所含的水量。如果它在您的近似阈值内，则退出。否则，用不同的高度调整你的估计，然后重复。

请注意，对于任何给定的三角形沙子，计算沙子表面上方的水量很容易。它是三棱柱的体积加上与沙子接触的四面体的体积：

请注意，沙线以下的水量将类似地计算，但体积会更小，因为它的一部分将被沙子占据。我建议在互联网上搜索典型的沙子含气量或持水量。或者任何短语都会返回一个理智的结果。另请注意，如果沙子高于吃水线，则某些三角形的沙子上方的水可能为零。

一旦您获得了网格的单个三角形的沙线上方和下方的水量，您只需遍历所有三角形以获得给定高度下整个沙箱的总体积。

请注意，这是一个非常愚蠢的算法，但我怀疑与试图做任何更聪明的花哨的 schmancier 算法相比，它会有不错的性能。请记住，这只是每个三角形的少量乘法和求和，并且带有少量if语句或其他流控制的盲循环往往会快速执行，因为处理器可以很好地流水线化。

如果您有一个高度详细的沙箱网格，并且希望将计算推入多个核心，则此方法可以轻松并行化，而不是在每个三角形上循环。或者保留循环，并将不同的高度推入每个核心。或者是其他东西; 我将并行化和加速作为练习留给读者。