3d - Algorithm for partially filling a polygonal mesh -

3d - Algorithm for partially filling a polygonal mesh -

overview: have simple plastic sandbox represented 3d polygonal mesh. need able determine water level after pouring specific amount of water sandbox.

the water distributed evenly above when poured no fluid simulation, water poured slowly it needs fast

question: kind of techniques/algorithms utilize problem?

i'm not looking programme or similar can this, algorithms - i'll implementation.

just idea:

first compute saddle points. tools discrete morse theory or topological persistence might useful here, know little them sure. next iterate on saddle points, starting @ lowest, , compute point in time after water starts cross point. time @ shallower (in terms of volume versus surface area) of 2 adjacent basins has reached level matches height of saddle point. point onward, water pouring onto surface flow on other basin , contribute water level instead, until 2 basins have reached equal level. after that, treated 1 single basin. along way might have right times when other saddle points reached, area associated basins changes. iterate in order of increasing time, not increasing height (e.g. using heap decrease-key operation). 1 time final pair of basins have equal height, done; afterwards there single basin left.

on whole, gives sequence of “interesting” times, things alter fundamentally. in between these, problem much more local, have consider shape of single basin compute water level. in local problem, know volume of water contained in basin, can e.g. utilize bisection find suitable level that. adjacent “interesting” times might provide useful end points bisection.

to compute volume of triangulated polytope, can utilize 3d version of shoelace formula: every triangle, take 3 vertices , compute determinant. sum them , split 6, , have volume of enclosed space. create sure orientate triangles consistently, i.e. either seen within or seen outside. selection decides overall sign, seek out see 1 which.

note question might need refinement: when level in basin reaches 2 saddle points @ exactly same height, water flow? without fluid simulation not defined, guess. argue should distributed as among adjacent basins. argue such situations unlikely occur in real data, , hence take 1 neighbour arbitrarily, implying saddle point has infinitesimally less height other ones. or come number of other solutions. if case of involvement you, might need clarify expect there.

algorithm 3d geometry simulation theory