部分填充多边形网格的算法 [英] Algorithm for partially filling a polygonal mesh

问题描述

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

Overview:
I have a simple plastic sandbox represented by a 3D polygonal mesh. I need to be able to determine the water level after pouring a specific amount of water into the sandbox.

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

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

Question:
What kind of techniques/algorithms could I use for this problem?

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

I'm not looking for a program or similar that can do this, just algorithms - I'll do the implementation.

推荐答案

只是一个想法:

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

First you compute all saddle points. Tools like discrete morse theory or topological persistence might be useful here, but I know too little about them to be sure. Next you iterate over all saddle points, starting at the lowest, and compute the point in time after which water starts to cross that point. This is the time at which the shallower (in terms of volume versus surface area) of the two adjacent basins has reached a level that matches the height of that saddle point. From that point onward, water pouring onto that surface will flow over to the other basin and contribute to its water level instead, until the two basins have reached an equal level. After that, they will be treated as one single basin. Along the way you might have to correct the times when other saddle points will be reached, as the area associated with basins changes. You iterate in order of increasing time, not increasing height (e.g. using a heap with decrease-key operation). Once the final pair of basins have equal height, you are done; afterwards there is only a single basin left.

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

On the whole, this gives you a sequence of "interesting" times, where things change fundamentally. In between these, the problem will be much more local, as you only have to consider the shape of a single basin to compute its water level. In this local problem, you know the volume of water contained in that basin, so you can e.g. use bisection to find a suitable level for that. The adjacent "interesting" times might provide useful end points for your bisection.

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

To compute the volume of a triangulated polytope, you can use a 3D version of the shoelace formula: for every triangle, you take its three vertices and compute their determinant. Sum them up and divide by 6, and you have the volume of the enclosed space. Make sure that you orientate all your triangles consistently, i.e. either all as seen from the inside or all as seen from the outside. The choice decides the overall sign, try it out to see which one is which.

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

Note that your question might need refinement: when the level in a basin reaches two saddle points at exactly the same height, where does the water flow? Without fluid simulation this is not well defined, I guess. You could argue that it should be distributed equally among all adjacent basins. You could argue that such situations are unlikely to occur in real data, and therefore choose one neighbour arbitrarily, implying that this saddle point has infinitesimally less height than the other ones. Or you could come up with a number of other solutions. If this case is of interest to you, then you might need to clarify what you expect there.

这篇关于部分填充多边形网格的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！