Algorithmus zum teilweisen Füllen eines Polygonnetzes

Übersicht:
Ich habe eine einfache Sandbox aus Kunststoff, die durch ein 3D-Polygonnetz dargestellt wird. Ich muss in der Lage sein, den Wasserstand nach dem Einfüllen einer bestimmten Menge Wasser in den Sandkasten zu bestimmen.

• Das Wasser wird gleichmäßig von oben verteilt, wenn es gegossen wird
• Keine Flüssigkeitssimulation, das Wasser wird sehr langsam gegossen
• Es muss schnell gehen

Frage:
Welche Art von Techniken / Algorithmen könnte ich für dieses Problem verwenden?

Ich bin nicht auf der Suche nach einem Programm oder ähnlichem, das dies tun kann, nur Algorithmen - ich werde die Implementierung machen.

Nur eine Idee:

Zuerst berechnen Sie alle Sattelpunkte. Werkzeuge wie diskrete Morsetheorie oder topologische Persistenz könnten hier nützlich sein, aber ich weiß zu wenig, um sicher zu sein. Als nächstes iteriere ich über alle Sattelpunkte, beginnend bei der niedrigsten, und berechne den Zeitpunkt, nach dem Wasser diesen Punkt zu überqueren beginnt. Dies ist der Zeitpunkt, zu dem die flachere (in Bezug auf das Volumen gegenüber der Oberfläche) der zwei benachbarten Becken ein Niveau erreicht hat, das der Höhe dieses Sattelpunkts entspricht. Von diesem Punkt an wird Wasser, das auf diese Oberfläche fließt, zu dem anderen Becken fließen und stattdessen zu seinem Wasserspiegel beitragen, bis die zwei Becken ein gleiches Niveau erreicht haben. Danach werden sie wie ein einziges Becken behandelt. Auf dem Weg dorthin müssen Sie möglicherweise die Zeiten korrigieren, zu denen andere Sattelpunkte erreicht werden, da sich der mit den Becken verbundene Bereich ändert. Sie iterieren in der Reihenfolge zunehmender Zeit, ohne die Höhe zu erhöhen (z. B. Verwenden eines Heaps mit der Funktion der Verkleinerungsschlüssel). Sobald das letzte Beckenpaar die gleiche Höhe erreicht hat, sind Sie fertig. danach ist nur noch ein einziges Becken übrig.

Insgesamt ergibt sich daraus eine Abfolge von "interessanten" Zeiten, in denen sich die Dinge grundlegend ändern. Dazwischen wird das Problem viel lokaler sein, da Sie nur die Form eines einzelnen Beckens berücksichtigen müssen, um seinen Wasserstand zu berechnen. Bei diesem lokalen Problem kennen Sie das Volumen des in diesem Becken enthaltenen Wassers, so dass Sie z. Verwenden Sie Halbierung, um ein geeignetes Niveau dafür zu finden. Die angrenzenden "interessanten" Zeiten können nützliche Endpunkte für Ihre Halbierung liefern.

Um die Lautstärke eines triangulierten Polytops zu berechnen, können Sie eine 3D-Version von Shoelace-Formel : Für jedes Dreieck nimmst du seine drei Ecken und berechne ihre Determinante. Summiere sie und dividiere durch 6, und du hast die Lautstärke des umschlossenen Raumes. Stellen Sie sicher, dass Sie alle Ihre Dreiecke einheitlich ausrichten, d. H. Entweder von innen oder von außen gesehen. Die Wahl entscheidet über das Gesamtzeichen, probiere es aus, um zu sehen, welches das ist.

Beachten Sie, dass Ihre Frage vielleicht verfeinert werden muss: Wenn das Niveau in einem Becken zwei Sattelpunkte bei genau der gleichen Höhe erreicht , wo fließt das Wasser? Ohne Fluidsimulation ist das nicht gut definiert, denke ich. Man könnte argumentieren, dass es gleichmäßig auf alle angrenzenden Becken verteilt sein sollte. Sie könnten argumentieren, dass solche Situationen in realen Daten unwahrscheinlich sind, und deshalb einen Nachbarn willkürlich wählen, was impliziert, dass dieser Sattelpunkt unendlich weniger Höhe hat als die anderen. Oder Sie könnten eine Reihe anderer Lösungen finden. Wenn dieser Fall für Sie von Interesse ist, müssen Sie möglicherweise klären, was Sie dort erwarten.

Eine einfache Lösung kommt mir in den Sinn: Durchsuchen Sie Ihren Weg durch verschiedene Wasserhöhen und berechnen Sie die enthaltene Wassermenge. d.h. Beginnen Sie mit einem oberen Schätzwert für die Wasserhöhe der Tiefe D des Sandkastens. Beachten Sie, dass, da Sand porös ist, das maximale Volumen bei voller Wasserfüllung der Box liegt; In unserem hypothetischen Hinterhof würde nur noch mehr Wasser ins Gras sickern. Beachten Sie auch, dass Sie sich nicht um Sattelpunkte oder mehrere Wasserstände in Ihrer Lösung kümmern müssen. Auch hier nehmen wir regelmäßig porösen Sand an, keine Berge aus Stein. Berechnen Sie das Volumen von Wasser in der Höhe D. Wenn es innerhalb Ihrer Annäherungsschwelle ist, beenden Sie. Andernfalls passen Sie Ihre Schätzung mit einer anderen Höhe an und wiederholen Sie die Eingabe.

Beachten Sie, dass das Berechnen der Wassermenge über der Sandoberfläche für jedes gegebene dreieckige Stück Sand einfach ist. Es ist das Volumen eines dreieckigen Prismas plus das Volumen des Tetraeders, das in Kontakt mit dem Sand steht:

Beachten Sie, dass das Wasservolumen unter der Sandlinie ähnlich berechnet würde, aber das Volumen wäre geringer, da ein Teil davon durch den Sand besetzt wäre. Ich empfehle Internet-Suche nach typischen Luft-Hohlraum-Inhalt von Sand oder Wasserspeicherkapazität. Oder welche Phrasen auch immer ein vernünftiges Ergebnis liefern würden. Beachten Sie auch, dass einige Dreiecke kein Wasser über dem Sand haben dürfen, wenn der Sand über der Wasserlinie liegt.

Sobald Sie die Wassermenge sowohl oberhalb als auch unterhalb der Sandlinie für ein einzelnes Dreieck Ihres Netzes haben, werden Sie einfach über alle Dreiecke schleifen, um das Gesamtvolumen für Ihre gesamte Sandbox für die gegebene Höhe zu erhalten / p>

Beachten Sie, dass dies ein ziemlich dummer Algorithmus ist, aber ich vermute, dass er eine ordentliche Leistung im Vergleich zu einem schicke-schicker-Algorithmus haben wird, der versuchen würde, etwas schlauer zu machen. Denken Sie daran, dass dies nur eine Handvoll Multiplikationen und Summierungen für jedes Dreieck ist, und dass Blindschleifen mit wenigen %code% -Anweisungen oder anderen Flusssteuerungen schnell ausgeführt werden, da der Prozessor sie gut pipelieren kann.

Diese Methode kann leicht parallelisiert werden, anstatt über jedes Dreieck zu schleifen, wenn Sie ein hochdetailliertes Mesh einer Sandbox haben und die Berechnungen in mehrere Kerne schieben möchten. Oder behalte die Schleifen und schiebe verschiedene Höhen in jeden Kern. Oder etwas anderes; Ich lasse Parallelisierung und Beschleunigung als Übung für den Leser.

Eine einfache Lösung kommt mir in den Sinn: Durchsuchen Sie Ihren Weg durch verschiedene Wasserhöhen und berechnen Sie die enthaltene Wassermenge. d.h. Beginnen Sie mit einem oberen Schätzwert für die Wasserhöhe der Tiefe D des Sandkastens. Beachten Sie, dass, da Sand porös ist, das maximale Volumen bei voller Wasserfüllung der Box liegt; In unserem hypothetischen Hinterhof würde nur noch mehr Wasser ins Gras sickern. Beachten Sie auch, dass Sie sich nicht um Sattelpunkte oder mehrere Wasserstände in Ihrer Lösung kümmern müssen. Auch hier nehmen wir regelmäßig porösen Sand an, keine Berge aus Stein. Berechnen Sie das Volumen von Wasser in der Höhe D. Wenn es innerhalb Ihrer Annäherungsschwelle ist, beenden Sie. Andernfalls passen Sie Ihre Schätzung mit einer anderen Höhe an und wiederholen Sie die Eingabe.

Beachten Sie, dass das Berechnen der Wassermenge über der Sandoberfläche für jedes gegebene dreieckige Stück Sand einfach ist. Es ist das Volumen eines dreieckigen Prismas plus das Volumen des Tetraeders, das in Kontakt mit dem Sand steht:

Beachten Sie, dass das Wasservolumen unter der Sandlinie ähnlich berechnet würde, aber das Volumen wäre geringer, da ein Teil davon durch den Sand besetzt wäre. Ich empfehle Internet-Suche nach typischen Luft-Hohlraum-Inhalt von Sand oder Wasserspeicherkapazität. Oder welche Phrasen auch immer ein vernünftiges Ergebnis liefern würden. Beachten Sie auch, dass einige Dreiecke kein Wasser über dem Sand haben dürfen, wenn der Sand über der Wasserlinie liegt.

Sobald Sie die Wassermenge sowohl oberhalb als auch unterhalb der Sandlinie für ein einzelnes Dreieck Ihres Netzes haben, werden Sie einfach über alle Dreiecke schleifen, um das Gesamtvolumen für Ihre gesamte Sandbox für die gegebene Höhe zu erhalten / p>

Beachten Sie, dass dies ein ziemlich dummer Algorithmus ist, aber ich vermute, dass er eine ordentliche Leistung im Vergleich zu einem schicke-schicker-Algorithmus haben wird, der versuchen würde, etwas schlauer zu machen. Denken Sie daran, dass dies nur eine Handvoll Multiplikationen und Summierungen für jedes Dreieck ist, und dass Blindschleifen mit wenigen if -Anweisungen oder anderen Flusssteuerungen schnell ausgeführt werden, da der Prozessor sie gut pipelieren kann.

Diese Methode kann leicht parallelisiert werden, anstatt über jedes Dreieck zu schleifen, wenn Sie ein hochdetailliertes Mesh einer Sandbox haben und die Berechnungen in mehrere Kerne schieben möchten. Oder behalte die Schleifen und schiebe verschiedene Höhen in jeden Kern. Oder etwas anderes; Ich lasse Parallelisierung und Beschleunigung als Übung für den Leser.