ESC
科技 1 分钟阅读

用散度定理实现快得离谱的体积计算

本文介绍如何用散度定理将三维网格的体积计算转化为对表面的积分。通过把每个三角形参数化,可将体积公式化为只依赖顶点坐标的求和:V = 1/6 Σ (Δ_{i1} × Δ_{i2})_x (T_{i0x}+T_{i1x}+T_{i2x}),计算极快。

来源:Hacker News

V = ∭_R 1 dV = ∭_R div F(x,y,z) dV

根据散度定理,这等于曲面积分:

V = ∬_S F(x,y,z) · dS

这个曲面积分定义在三维网格的表面 S 上,等于其逐三角形部分之和。令 T_i 表示网格中第 i 个三角形的表面。那么,

V = ∑i ∬{T_i} F(x,y,z) · dS

令 T_{in} 表示第 i 个三角形的第 n 个顶点。设 Δ_1 等于 T_{i1} 与 T_{i0} 之间的向量差,Δ_2 同样等于 T_{i2} - T_{i0}。于是每个单独的三角形 T_i 可以参数化为:

r(u,v) = T_{i0} + uΔ_1 + vΔ_2

r_u = Δ_1 r_v = Δ_2

r_u × r_v = Δ_1 × Δ_2

因此,利用该参数化,并按需代入 F 的定义,曲面积分可改写为:

V = ∑i ∬{T_i} F(x,y,z) · (r_u × r_v) dA = ∑i ∬{T_i} F(x,y,z) · (Δ_{i1} × Δ_{i2}) dA = ∑i ∬{T_i} ⟨x,0,0⟩ · (Δ_{i1} × Δ_{i2}) dA

这个叉积在三角形内是常量,并且很容易由顶点数据计算出来。由于与 F 的零分量做点积,只需要计算叉积的 X 分量;其余分量都等于零。于是 V 可以改写为:

V = ∑i (Δ{i1} × Δ_{i2})x ∬{T_i} x dA

现在关注曲面积分 ∬_{T_i} x dA。用参数化展开得到:

∬_{T_i} x dA = ∫_0^1 ∫0^u x dv du = ∫0^1 ∫0^u (T{i0x} + u Δ{i1x} + v Δ{i2x}) dv du

这个积分可以直接求值,将顶点数据视为常量:

∫0^1 ∫0^{1-u} (T{i0x} + u Δ{i1x} + v Δ_{i2x}) dv du = T_{i0x} ∫0^1 ∫0^{1-u} dv du + Δ{i1x} ∫0^1 ∫0^{1-u} u dv du + Δ{i2x} ∫0^1 ∫0^{1-u} v dv du = T{i0x} (1/2) + Δ{i1x} (1/6) + Δ{i2x} (1/6) = T{i0x} (1/2) + (T_{i1x} - T_{i0x}) (1/6) + (T_{i2x} - T_{i0x}) (1/6) = T_{i0x} (1/6) + T_{i1x} (1/6) + T_{i2x} (1/6) = (1/6) (T_{i0x} + T_{i1x} + T_{i2x})