Algorithm for partially filling a polygonal mesh

问题:

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.

• The water is distributed evenly from above when poured
• No fluid simulation, the water is poured very slowly
• It needs to be fast

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.

回答1:

Just an idea:

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.

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.

回答2:

A simple solution comes to mind: binary-search your way through different heights of water, computing the volume of water contained. i.e. Start with an upper-estimate for the water's height of the depth D of the sandbox. Note that since sand is porous, the maximum volume will be with the box filled to the brim with water; Any more water would just pout back out into the grass in our hypothetical back-yard. Also note, that this means that you don't need to worry about saddle points, or multiple water levels in your solution; Again, we're assuming regular porous sand here, not mountains made out of rock. Compute the volume of water contained by height D. If it is within your approximation threshold, quit. Otherwise, adjust your estimate with a different height, and repeat.

Note that computing the volume of water above the surface of the sand for any given triangular piece of the sand is easy. It's the volume of a triangular prizm plus the volume of the tetrahedron which is in contact with the sand:

Note that the volume of water below the sandline would be calculated similarly, but the volume would be less, since part of it would be occupied by the sand. I suggest internet-searching for typical air-void contents of sand, or water-holding capacity. Or whatever phrases would return a sane result. Also note, that some triangles may have zero water above the sand, if the sand is above the water-line.

Once you have the volume of water both above and below the sand-line for a single triangle of your mesh, you just loop over all of the triangles to get the total volume for your entire sandbox, for the given height.

Note that this is a pretty dumb algorithm, but I suspect it will have decent performance compared to a fancy-schmancier algorithm which would try to do anything more clever. Remember that this is just a handful of multiplications and summations for each triangle, and that blind loops with few if statements or other flow-control tend to execute quickly, since the processor can pipeline it well.

This method may be parallelized easily instead of looping over each triangle, if you have a highly-detailed mesh of a sandbox, and want to shove the calculations into multiple cores. Or keep the loops, and shove different heights into each core. Or something else; I leave parallelization and speeding up as an exercise for the reader.