利用散度定理进行超快体积计算

使用散度定理进行令人捧腹的快速体积计算 2018 年 2 月 16 日（不，不会开玩笑。）下面介绍了一种用于简单、封闭、三角化 3D 网格体积计算的快速算法。这个假设是散度定理的结果。进一步的扩展也可以推广到其他网格，尽管目前这超出了范围。我们首先将体积定义为常数 1 区域上的三重积分： V = ∭ R 1 d V V = \iiint_R 1 \mathrm{d}V 令 𝐅 \mathbf{F} 为 ℝ 3 \mathbb{R}^3 中的函数，其散度等于 1。就本文而言，我们选择： 𝐅 ( x , y , z ) = < x , 0 , 0 > \mathbf{F}(x, y, z) = 可以很容易地验证 d i v 𝐅 = ∂ F ∂ x + ∂ F ∂ y + ∂ F ∂ z = 1 + 0 + 0 = 1 \mathrm{div} \mathbf{F} = \frac{\partial F}{\partial x} + \frac{\partial F}{\partial y} + \frac{\partial F}{\partial z} = 1 + 0 + 0 = 1 因此， V = ∭ R 1 d V = ∭ R d i v 𝐅 ( x , y , z ) d V V = \iiint_R 1 dV = \iiint_R \mathrm{div} \mathbf{F}(x, y, z) \mathrm{d}V 根据散度定理，这等于曲面积分： V = ∬ S 𝐅 ( x , y , z ) d 𝐒 V = \iint_S \mathbf{F}(x, y, z) \mathrm{d}\mathbf{S} 该表面积分在 3D 网格的表面 S 上定义，等于其分段三角形部分的总和。令 T i T_i 表示网格中第 i 个三角形的表面。那么， V = Σ i = 0 ∬ T i 𝐅 ( x , y , z ) d 𝐒 V = \sum_{i = 0} \iint_{T_i} \mathbf{F}(x, y, z) \mathrm{d}\mathbf{S} 设 T i n T_{in} 表示第 i i 个三角形的第 n n 个顶点。令 Δ 1 \Delta_1 等于 Ti 1 T_{i1} 和 Ti 0 T_{i0} 之间的向量差，并且 Δ 2 \Delta_2 同样等于 Ti 2 − T i 0 T_{i2} - T{i0} 。因此，每个单独的三角形 T i T_i 可以参数化为： 𝐫 ( u , v ) = Ti 0 + u Δ 1 + v Δ 2 \mathbf{r}(u, v) = T_{i0} + u\Delta_1 + v\Delta_2 然后，简单微分得出： 𝐫 u = Δ 1 \mathbf{r}_u = \Delta_1 𝐫 v = Δ 2 \mathbf{r}_v = \Delta_2 因此， 𝐫 u × 𝐫 v = Δ 1 × Δ 2 \mathbf{r}_u \times \mathbf{r}_v = \Delta_1 \times \Delta_2 因此，表面积分可以根据此参数化重写，代入 𝐅 的定义\mathbf{F} 根据需要： V = Σ i = 0 ∬ T i 𝐅 ( x , y , z ) ( 𝐫 u × 𝐫 v ) d A V = \sum_{i = 0} \iint_{T_i} \mathbf{F}(x, y, z) (\mathbf{r}_u \times \mathbf{r}_v) dA = Σ i = 0 ∬ T i 𝐅 ( x , y , z ) ( ̇ Δ i 1 × Δ i 2 ) d A = \sum_{i = 0} \iint_{T_i} \mathbf{F}(x, y, z) \dot (\Delta_{i1} \times \Delta_{i2}) dA = Σ i = 0 ∬ T i < x , 0 , 0 > ( ̇ Δ i 1 × Δ i 2 ) d A = \sum_{i = 0} \iint_{T_i} \dot (\Delta_{i1} \times \Delta_{i2}) dA 此叉积在整个三角形中是恒定的，并且易于计算从顶点数据计算。仅应计算叉积的 X 分量；由于与 𝐅 \mathbf{F} 的零分量的点积，其他值等于 0。 V V 可以重写为： V = Σ i = 0 ( Δ i 1 × Δ i 2 ) x ∬ T i x d A V = \sum_{i = 0} (\Delta_{i1} \times \Delta_{i2})_x \iint_{T_i} x dA 现在我们关注曲面积分 ∬ T i x d A \iint_{T_i} x达。通过参数化展开得到： ∬ T i x d A = ∫ 0 1 ∫ 0 u x d v d u = ∫ 0 1 ∫ 0 u ( T i 0 x + u Δ i 1 x + v Δ i 2 x ) d v d u \iint_{T_i} x dA = \int_{0}^{1} \int_{0}^{u} x dv du = \int_{0}^{1} \int_{0}^{u} (T_{i0x} + u \Delta_{i1x} + v \Delta_{i2x}) dv du 该积分可以直接计算，将顶点数据视为常数： ∫ 0 1 ∫ 0 1 − u ( T i 0 x + u Δ i 1 x + v Δ i 2 x ) d v d u \int_{0}^{1} \int_{0}^{1-u} (T_{i0x} + u \Delta_{i1x} + v \Delta_{i2x}) dv du = T i 0 x ∫ 0 1 ∫ 0 1 − u d v d u + Δ i 1 x ∫ 0 1 ∫ 0 1 − u u d v d u + Δ i 2 x ) ∫ 0 1 ∫ 0 1 − u v d v d u = T_{i0x} \int_{0}^{1} \int_{0}^{1-u} dv du + \Delta_{i1x} \int_{0}^{1} \int_{0}^{1-u} u dv du + \Delta_{i2x}) \int_{0}^{1} \int_{0}^{1-u} v dv du = T i 0 x ( 1 2 ) + Δ i 1 x ( 1 6 ) + Δ i 2 x ( 1 6 ) = T_{i0x} (\frac{1}{2}) + \Delta_{i1x} (\frac{1}{6}) + \Delta_{i2x} (\frac{1}{6}) = Ti 0 x ( 1 2 ) + ( Ti 1 x − Ti 0 x ) ( 1 6 ) + ( Ti 2 x − Ti 0 x ) ( 1 6 ) = T_{i0x} (\frac{1}{2}) + (T_{i1x} - T_{i0x})(\frac{1}{6}) + (T_{i2x} - T_{i0x})(\frac{1}{6}) = Ti 0 x ( 1 6 ) + ( Ti 1

订阅66必读