计算Mesh网格的体积是一个相对简单和众所周知的问题。在这个教程中我们将介绍计算Mesh网格对象体积的一般思路、数学依据,给出JavaScript实现代码,并对大量重复对象的体积计算给出优化算法。

1、基础知识

计算Mesh网格体积的基本思路是计算网格中每个三角面对应的体积并将其加起来。一个三角形本身没有体积:它是二维的,因此我们计算从原点 (0,0,0,0) 到三角面的四面体(tetrahedron)的体积。

计算四面体的体积有简洁的方程。给定三角形的点v1,v2,v3的四角体的体积是

V = \frac16 (v_1 \times v_2) \cdot v_3

另一种解读是,如果我们有一个3×3矩阵,其中每行表示一个顶点(Vertex),体积是行列式的六分之一。除以6是因为实际上行列式表示了由三个向量形成的平行六面体(parallelpiped)的体积,你可以将6个四面体塞进平行六面体中。

但是等一下,如果我把所有这些四面体加起来得到不是一堆指向原点的重叠的体积?是的,但关键是这些体积是有符号的,因此它们可能是负的,具体取决于顶点缠绕。如果顶点指向一个方向(v1->v2->v3),就得到一个正的体积,如果指向另一个方向(v1->v3->v2),就得到一个负的体积。面向远离原点方向的的三角形对应的四面体的体积将添加到总体积中,而面向原点方向的三角形对应的四面体的体积将从总体积中减去,剩下的就是Mesh网格对象的体积。为了获得Mesh网格的总体积,我们计算每个三角面对应的四面体的有符号体积,并将其累加即可。

下面是用于计算Mesh网格体积的 javascript 代码。

var volume = 0;
var v1 = vec3.create(),
    v2 = vec3.create(),
    v3 = vec3.create();
var i,index1,index2,index3;

for(i=0;i<numIndices;) {
  index1 = indices[i++]*3;
  index2 = indices[i++]*3;
  index3 = indices[i++]*3;
  
  vec3.set(v1,vertices[index1],vertices[index1+1],vertices[index1+2]);
  vec3.set(v2,vertices[index2],vertices[index2+1],vertices[index2+2]);
  vec3.set(v3,vertices[index3],vertices[index3+1],vertices[index3+2]);
  
  vec3.cross(v1,v1,v2);
  volume += vec3.dot(v1,v3);
}

volume = Math.abs(volume/6.0);

重复元素的体积

现在我们要说精华了。如果你有一个对象,是由一堆相同但复杂的部件(至少部分)组合构成的,会发生什么情况。我不是说把图元简单混在一起, 但你可以想象像一个巴克球, 每个面都用某种复杂的形状表达出来。一种暴力的解决方法是移动和旋转形状到正确的位置,然后通过三角面计算体积。这意味着你必须计算几何体每个点的变换,然后处理每个三角面。如果你的部件有1000个三角形,你有100个部件,这将是一个很大的计算。我们可以通过计算一次形状的"一般体积",并且仅将我们的转换应用于简化的表示形式来大幅提高效率。但是这个一般体积是什么样子的呢?

旋转

这个一般体积背后的关键思想是体积是旋转不变的。这是微分几何学的基本结果之一。直观上很明显:无论在空间定向一个物体,其体积不会改变。不太直观的是,对于有符号的开放几何形状体积,这一点也适用。从数学上讲,这很容易看出,体积是矩阵的行列式,而旋转矩阵的行列式为1。一个矩阵乘以另一个矩阵的行列式是其单个行列式的乘法。因此,可以任意旋转原始图元并保持体积不变。如果只是旋转形状,那么可以计算这个几何形状的体积一次,并乘以形状的数量。

平移

再考虑平移(Translate)或者说在空间移动物体。我们可以用简化的 2D 示例来直观地查看。三角形的面积是底边长乘以高度的一半。如果将线段在 x 方向平移一定量,就会将这个量添加到我的高度。因此,平移的线的面积是:

A_t = \frac12 b (h+x) = A + \frac12 bx

计算原始面积,添加了一些量乘以x平移量。虽然这是一个非常傻的例子,我们可以做针对每个轴(x,y,z)以同样的方式处理体积。

漂亮的结果

要了解此思路如何应用于我们的体积计算,我们可以查看每个三角形的体积的扩展方程,其中

v_1 = (x_1,y_1,z_1)
V = x_1y_2z_3-x_2y_1z_3+x_3y_1z_2-x_1y_3z_2+x_2y_3z_1-x_3y_2z_1

这可能看起来像很多方程,但如果看看每个单独的术语,我们注意到,它是术语的总和,看起来像x 组件 乘以 y 组件乘以 z 组件。如果我们沿着一个轴平移,就会隔离一个任意的术语,得到的东西类似于我们简单的2d示例:

V_t = x_1y_2(z_3+z_t) = V + x_1y_2z_t

你可能会说,这只是平移一个方向,当你做一个任意的平移会发生什么?事实证明,由于术语以正对和负对的方式组织,除了一个方向示例之外,每个术语都会取消。因此,我们的一般体积成为每个轴的术语的累加的向量。每个轴术语都是不包括该轴的顶点坐标对:

V_x = y_2z_3-y_1z_3+y_1z_2-y_3z_2+y_3z_1-y_2z_1
V_y = x_1z_3-x_2z_3+x_3z_2-x_1z_2+x_2z_1-x_3z_1
V_z = x_1y_2-x_2y_1+x_3y_1-x_1y_3+x_2y_3-x_3y_2

就像我们的常规体积一样,我们可以为形状中的每个三角形添加这些体积。最终的体积计算结果为:

V_t(x_t,y_t,z_t) = V+V_xx_t+V_yy_t+V_zz_t

这太棒了,不仅因为它允许我们计算体积,而无需通过每个三角形,但我们甚至不需要知道形状的方向!这导致一些奇怪的事实,比如如果随机旋转每个形状,但把它们放在同一个地方,它有相同的体积。


原文链接:Calculating the volume of a mesh

BimAnt翻译整理,转载请标明出处