【文章标题】：Hilariously Fast Volume Computation with the Divergence Theorem 【文章标题】：用散度定理实现令人发笑的快速体积计算
【文章正文】： 16 Feb 2018 2018年2月16日 (No, there won’t be jokes.) （本文不会出现任何笑话）
The following presents a fast algorithm for volume computation of a simple, closed, triangulated 3D mesh. This assumption is a consequence of the divergence theorem. Further extensions may generalise to other meshes as well, although that is presently out of scope. 以下介绍一种针对简单闭合三角化三维网格的快速体积计算算法。该假设源于散度定理的推论。虽然当前研究范围有限，但进一步扩展可能适用于其他类型网格。
We begin with the definition of volume as the triple integral over a region of the constant one: 我们首先将体积定义为常数1在区域上的三重积分：
Let be a function in such that its divergence is equal to one. For the purposes of this paper, we choose: 设存在某函数使其散度等于1。本文选择：
It can easily be verified that 容易验证：
Therefore, 因此，
By the Divergence Theorem, this is equal to the surface integral: 根据散度定理，这等价于曲面积分：
This surface integral, defined over the surface S of the 3D mesh, is equal to the sum of its piecewise triangle parts. Let denote the surface of the ’th triangle in the mesh. Then, 该曲面积分定义在三维网格表面S上，等于其分片三角形部分之和。设表示网格中第i个三角形表面，则：
Let represent the ’th vertex of the ’th triangle. Let equal the vector difference between and , and likewise equal to . Each individual triangle may thus be parametrised as: 设表示第i个三角形的第j个顶点。令等于与的向量差，同理等于。因此每个三角形可参数化为：
Then, simple differentiation yields: 通过简单微分可得：
Thus, the surface integral can be rewritten in terms of this parametrisation, substituting in the definition of as needed: 因此，曲面积分可根据此参数化重写，并按需代入的定义：
This cross product is constant throughout the triangle and easy to calculate from the vertex data. Only the X component of the cross product should be calculated; the others are equal to zero due to the dot product with the zero components of . can be thus be rewritten as: 该叉积在整个三角形上为常量，且易于从顶点数据计算。由于与的零分量点积，只需计算叉积的X分量，其他分量为零。因此可重写为：
We now focus on the surface integral . Expanding with the parametrisation yields: 现在我们关注曲面积分。通过参数化展开可得：
This integral can be directly evaluated, treating vertex data as constants: 该积分可直接求值，将顶点数据视为常量：
Substituting into the original sum and pulling out a constant factor of to avoid the inner loop division, this yields the following compact formula for the volume: 代入原始求和式并提取常数因子以避免内循环除法，最终得到体积计算的简洁公式：
The final algorithm contains no numerical integration nor differentiation. In contrast to common naive algorithms for volume, which are equivalent to rendering the mesh and then sampling the render, an expensive operation, there is only a single loop in this algorithm, over the triangles. Thus, this algorithm for volume computation is O(n) to the number of the triangles. Furthermore, the per-triangle calculation is similarly efficient: given the natural expansion of the cross product, the inner part contains seven additions and three multiplications. On the outside of the loop is only a single multiplication. Thus, for a mesh of triangles, the algorithm requires additions and multiplications, or floating point operations. This is very fast. 最终算法不包含数值积分或微分。与常见的朴素体积算法（相当于渲染网格后对渲染结果采样这种昂贵操作）不同，本算法仅需对三角形进行单次循环。因此该体积计算算法的时间复杂度为三角形数量的O(n)。此外，单三角形计算同样高效：根据叉积的自然展开，内部计算包含7次加法和3次乘法，循环外部仅需1次乘法。因此对于n个三角形的网格，算法需要次加法和次乘法，即次浮点运算，速度极快。
For a ballpark number, if volume needs to be calculated every frame in a high-performance 60 frames per second application, without the aid of a GPU, only using the CPU capabilities of a $35 Raspberry Pi, around 30 million triangles could be measured every frame. 粗略估算，若需在每秒60帧的高性能应用中每帧计算体积（不借助GPU，仅使用35美元树莓派的CPU能力），每帧可处理约3000万个三角形。
The vector calculus exam is soon, and I need to study. Plus, who doesn’t love 3D graphics?！ 向量微积分考试临近，我得去复习了。再说，谁不爱3D图形学呢？！
I would be (pleasantly) surprised if the algorithm is novel. Further research after posting reveals the paper Efficient Feature Extraction for 2D/3D Objects in Mesh Representation by Cha Zheng and Tsuhan Chen, which appears to describe the same algorithm, although the derivation is different. It was fun while it lasted! 若该算法具有创新性，我会（愉快地）感到惊讶。发文后的进一步研究发现郑查和陈祖翰的论文《网格表示中2D/3D对象的高效特征提取》似乎描述了相同算法，尽管推导过程不同。至少这个过程很有趣！