用散度定理极速计算 3D 体积
Hilariously Fast Volume Computation with the Divergence Theorem
为了备战向量微积分考试，我推导出了一个计算简单封闭三角网格体积的超快算法。利用散度定理，我们将体积的三重积分转化为表面积分，最终简化为对每个三角形顶点的线性运算。该算法时间复杂度仅为 O(n)，无需数值积分或微分，每帧仅需约 11n 次浮点运算。这意味着即便在树莓派上，也能轻松实现每秒 60 帧处理 3000 万个三角形的体积计算。虽然事后发现 Cha Zheng 和 Tsuhan Chen 的论文已描述过类似方法，但重新推导的过程依然充满乐趣。
对于包含 n 个三角形的网格，该算法仅需 8n 减 1 次加法和 3n 加 1 次乘法，也就是 11n 次浮点运算，速度极快。
HN 评论区
60- physicsguy
这属于那种看完让你感叹“哇，太神奇了！”或者“咦，我以为这招早就人尽皆知了！”的帖子，具体取决于你的背景 ;)
这里有一个类似的 1980 年用 Fortran 写的实现，它还能计算质心等其他属性：
Algorithm 550: Solid Polyhedron Measures
A. M. Messner and G. Q. Taylor
ACM Trans. Math. Softw., 6(1), Mar 1980, pp.121--130
Keywords: polyhedron, graphics, numerical integration
Language: Fortran 66/77; Shar Index: Z; Gams: P
File size: 19.1 KB;
不过 Messner 最早是在下面这篇论文中发表的：
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., May 1970.
我觉得
- eterevsky
这不就是遍历网格中的每个三角形，计算它与某个平面投影之间形成的棱柱状多面体的体积，然后根据投影的朝向加上正号或负号吗？这类公式是基于基础几何原理的。
- srean
另一方面，如果你想计算顶点位于格点上的多边形面积，可以数一下内部格点数 I 和边界格点数 B。那么面积 A 就是
A = I + B/2 - 1
这就是 Pick 定理
https://en.wikipedia.org/wiki/Pick's_theorem
是我最喜欢的结果之一。不幸的是，它无法如此优雅地推广到高维空间。
如果你像这篇帖子那样想要计算多面体的体积，可以使用鞋带公式的三维类比（本质上等价）。
设 Va、Vb 和 Vc 是表面三角剖分中三角形 ∆ 的顶点。你需要相对于原点以一致的顺序/朝向来命名这些顶点。
那么体积 V 就是所有这些三角形的有向体积之和
V_∆ = 1/6 Va ^ Vb ^ Vc。
这就是有向面积和体积、行列式以及外代数的魅力所在。
想了解为什么是这样，可以看这个很棒的短视频
- elikoga
我的直觉告诉我，朴素公式就是把三角形金字塔的体积（相对于原点）按朝向的符号加起来。看起来他们推导出的就是这个。这是二维多边形面积计算的推广，即对每条边求三角形面积之和。我在一个数学夏令营学过这个，当时我们用它计算 GIS 数据中的地图多边形面积。我记得在 AI 时代之前获取数学知识很难，但我没记错它会有这么难。
完全不知道作者说的“等同于渲染网格然后对渲染结果进行采样”是什么意思。
- ahaferburg
这里的重点在于网格必须是简单且封闭的。在依赖输出结果之前，请务必验证这些前提条件。
类似的公式也存在于力矩计算中，用于计算刚体的惯性矩阵。