Blitzschnelle Volumenberechnung mit dem Divergenzsatz
Hilariously Fast Volume Computation with the Divergence Theorem
Ein überraschend einfacher Algorithmus berechnet das Volumen eines geschlossenen, triangulierten 3D-Meshs in linearer Zeit. Die Methode nutzt den Divergenzsatz, um das Volumenintegral in ein Oberflächenintegral umzuwandeln, das sich für jedes Dreieck geschlossen lösen lässt. Das Ergebnis: nur ein einziger Schleifendurchlauf über die Dreiecke, mit nur 11 Gleitkommaoperationen pro Dreieck. Damit lassen sich selbst auf einem Raspberry Pi 3 rund 30 Millionen Dreiecke pro Frame bei 60 fps verarbeiten – ganz ohne GPU.
Für eine grobe Zahl: Wenn das Volumen in einer Hochleistungsanwendung mit 60 Bildern pro Sekunde jedes Bild berechnet werden muss, ohne GPU, nur mit der CPU eines 35-Dollar-Raspberry-Pi, könnten etwa 30 Millionen Dreiecke pro Bild gemessen werden.
- physicsguy
Das ist einer dieser Momente, in denen man je nach Hintergrund denkt: „Huch, das ist erstaunlich!“ oder „Huch, ich dachte, dieser Trick wäre allgemein bekannt!“ ;)
Hier ist eine ähnliche Implementierung von 1980, geschrieben in Fortran, die auch andere Eigenschaften wie den Schwerpunkt berechnet:
Algorithmus 550: Solid Polyhedron Measures
A. M. Messner und G. Q. Taylor
ACM Trans. Math. Softw., 6(1), März 1980, S. 121–130
Schlüsselwörter: Polyeder, Grafik, numerische Integration
Sprache: Fortran 66/77; Shar-Index: Z; Gams: P
Dateigröße: 19,1 KB;
Aber Messner veröffentlichte es zuerst in:
A. M. Messner, „A surface Integral method for computer calculation of mass properties“, Paper Nr. 852, 29. JAHRESKONFERENZ DER SOCIETY OF AERONAUTICAL WEIGHT ENGINEERS, Washington, D.C., Mai 1970.
Ich denke.
- eterevsky
Ist das nicht dasselbe wie einfach jedes Dreieck aus dem Mesh zu nehmen, das Volumen eines prismenartigen Polytops zwischen ihm und seiner Projektion auf eine der Ebenen zu berechnen und es dann mit einem Pluszeichen zu versehen, wenn seine Projektion in die eine Richtung orientiert ist, und mit einem Minuszeichen, wenn sie in die andere orientiert ist? Diese Art von Formel funktioniert auf der Grundlage der elementaren Geometrie.
- srean
Andererseits: Wenn man die Fläche eines Polygons berechnen möchte, dessen Ecken auf Gitterpunkten liegen, kann man die Anzahl der inneren Punkte I und die Anzahl der Randpunkte B zählen. Dann ist die Fläche A
A = I + B/2 - 1
Das ist der Satz von Pick
https://de.wikipedia.org/wiki/Satz_von_Pick
eines meiner Lieblingsergebnisse. Leider lässt es sich nicht so schön auf höhere Dimensionen verallgemeinern.
Wenn man – wie im Beitrag – das Volumen eines Polyeders möchte, kann man das dreidimensionale Analogon der Schnürsenkelformel verwenden (im Wesentlichen äquivalent).
Seien Va, Vb und Vc die Eckpunkte eines Dreiecks ∆ einer Triangulierung der Oberfläche. Man muss die Eckpunkte in einer konsistenten Reihenfolge/Orientierung bezüglich des Ursprungs benennen.
Dann ist das Volumen V die Summe über alle solche Dreiecke der vorzeichenbehafteten Volumina
V_∆ = 1/6 Va ^ Vb ^ Vc.
Das ist die Schönheit von vorzeichenbehafteten Flächen und Volumina, Determinanten und äußerer Algebra.
Um zu verstehen, warum das so ist, gibt es dieses wunderschöne kurze Video
- elikoga
Mein Bauchgefühl sagt mir, dass die naive Formel die Summe der Pyramidenvolumina zum Ursprung mit Vorzeichen entsprechend der Orientierung ist. Es sieht so aus, als hätten sie das hergeleitet. Das ist eine Verallgemeinerung der 2D-Polygonflächenberechnung, bei der man die Dreiecksflächen für jede Kante summiert. Das habe ich in einem Mathe-Camp gelernt, wo wir Kartenpolygonflächen mit GIS-Daten berechnet haben. Ich erinnere mich, dass mathematisches Wissen in der Zeit vor der KI-Ära schwer zu bekommen war, aber ich erinnere mich nicht, dass es so schwer war.
Keine Ahnung, was der Autor mit „die äquivalent zum Rendern des Meshes und anschließendem Abtasten des Renderings sind“ meint.
- ahaferburg
Die Betonung liegt hier darauf, dass das Mesh einfach und geschlossen ist. Stelle sicher, dass diese Voraussetzungen validiert werden, bevor du dich auf die Ausgabe verlässt.
Ähnliche Formeln existieren für Momente, um die Trägheitsmatrix eines starren Körpers zu berechnen.