Cálculo de volumen sorprendentemente rápido con el teorema de la divergencia
Hilariously Fast Volume Computation with the Divergence Theorem
Un algoritmo O(n) para calcular el volumen de una malla 3D cerrada y triangulada, derivado del teorema de la divergencia. Reduce el problema a una simple suma sobre los triángulos, con solo 11n operaciones de punto flotante. El autor demuestra la fórmula paso a paso y analiza su rendimiento, señalando que puede procesar unos 30 millones de triángulos por fotograma en una Raspberry Pi de $35. La publicación también menciona que el algoritmo ya había sido descrito en un artículo de Cha Zhang y Tsuhan Chen.
El algoritmo final no contiene integración numérica ni diferenciación; solo un bucle sobre los triángulos, lo que lo hace O(n) y extremadamente rápido.
- physicsguy
Este es uno de esos casos en los que dices "¡Vaya, esto es increíble!" o "¡Vaya, pensaba que este truco era muy conocido!", dependiendo de tu formación ;)
Aquí tienes una implementación similar de 1980 escrita en Fortran que también calcula otras propiedades como el centroide:
Algoritmo 550: Medidas de poliedros sólidos
A. M. Messner y G. Q. Taylor
ACM Trans. Math. Softw., 6(1), marzo de 1980, págs. 121-130
Palabras clave: poliedro, gráficos, integración numérica
Lenguaje: Fortran 66/77; Índice Shar: Z; Gams: P
Tamaño del archivo: 19.1 KB;
Pero Messner lo publicó primero en:
A. M. Messner, "A surface Integral method for computer calculation of mass properties", Paper No. 852, 29TH ANNUAL CONF. OF THE SOCIETY OF AERONAUTICAL WEIGHT ENGINEERS, Washington, D.C., mayo de 1970.
Creo que
- eterevsky
¿No es lo mismo que tomar cada triángulo de la malla, calcular el volumen de un poliedro tipo prisma entre él y su proyección sobre uno de los planos, y luego tomarlo con signo + si su proyección está orientada en una dirección, y con signo - si está orientada en otra? Este tipo de fórmula funciona basándose en la geometría básica.
- srean
Por otro lado, si quieres calcular el área de un polígono cuyos vértices están en puntos de la retícula, puedes contar el número de puntos interiores I y el número de puntos en el borde B. Entonces el área A es
A = I + B/2 - 1
Esto es el teorema de Pick
https://en.wikipedia.org/wiki/Pick's_theorem
uno de mis resultados favoritos. Desafortunadamente, no se generaliza tan bien a dimensiones superiores.
Si, como en el artículo, quieres el volumen de un poliedro, puedes usar el análogo tridimensional de la fórmula del cordón (esencialmente equivalente).
Sean Va, Vb y Vc los vértices de un triángulo ∆ de una triangulación de la superficie. Debes nombrar los vértices en un orden/orientación consistente con respecto al origen.
Entonces el volumen V es la suma sobre todos esos triángulos de los volúmenes con signo
V_∆ = 1/6 Va ^ Vb ^ Vc.
Esa es la belleza de las áreas y volúmenes con signo, los determinantes y el álgebra exterior.
Para entender por qué es así, hay este hermoso video corto
- elikoga
Mi instinto me dice que la fórmula ingenua es sumar los volúmenes de las pirámides triangulares hacia el origen con signo según la orientación. Parece que es lo que derivaron. Lo cual es una generalización del cálculo del área de un polígono 2D sumando las áreas de los triángulos para cada arista, me lo enseñaron en un campamento de matemáticas donde calculábamos áreas de polígonos en datos SIG. Recuerdo que el conocimiento matemático era difícil de obtener antes de la era de la IA, pero no recordaba que fuera tan difícil.
No tengo idea de qué quiere decir el autor con "que son equivalentes a renderizar la malla y luego muestrear el render".
- ahaferburg
El énfasis aquí está en que la malla sea simple y cerrada. Asegúrate de validar estas condiciones previas antes de confiar en el resultado.
Existen fórmulas similares para momentos, para calcular la matriz de inercia de un cuerpo rígido.