网格切割

　　接下来要解决难点二，如何产生完全贴合骨骼模型表面的网格面片。

　　夏旸师兄采用的方法是：利用多边形分割得到的凸多边形轮廓点集，延视线方向做一柱面网格模型，并用该模型切割骨骼模型，得到骨骼模型上的一组切割线，切割线所包围的网格面片即是钢板的网格面片。

　　切割柱面的生成是利用两组多边形轮廓点集得到的，其中第一组轮廓点集就是用户输入和凸分解得到的，第二组轮廓点集由第一组轮廓点集延视线方向平移得到（每个点的平移距离可能不同）。切割柱面保证每一对轮廓点都能切割到骨骼模型的外表面。

　　有了切割网格，需要进行网格的切割判断。由于网格是由三角面片构成的，判断两个网格是否有相交线其实就是判断两个空间三角形是否相交。这里，三角面片的精确求交运算参照了Tomasmuller提出的两两三角形求交线算法，步骤如下：

　　1. 设两三角形为T1、T2，分别求T1和T2所处平面的法向量，记为N1、N2。计算N1和N2的叉积长度，如果等于0或小于接近0的正数，则两三角形平行或重合。

　　2. 设T1三个顶点为(V1,i)(i=1,2,3)，T2三个顶点为(V2,i)(i=1,2,3)，计算V1三个点到T2平面的有符号距离(D1,i)(i=1,2,3)，和V2三个点到T1平面的有符号距离(D2,i)(i=1,2,3)。如果D1同号或D2同号，表示三角形T1、T2没有交点。如果有异号的顶点，记录下两端点异号的三角形边(E1,j)(j=1,2)和(E2,j)(j=1,2)。

　　3. 如上图，(E1,1)与平面T2交于点(P1,1)，(E1,2)与平面T2交于点(P1,2)，(E2,1)与平面T1交于点(P2,1)，(E2,2)与平面T1交于点(P2,2)。连接线段(P1,1)(P1,2)记为L1，线段(P2,1)(P2,2)记为L2。L1、L2必然共线，判断L1、L2间是否有重叠部分。如果有，则三角形T1、T2相交，并且相交线即为重叠部分，反之不相交。

　　利用三角面片求交算法，我们可以得到切割网格和骨骼网格的所有相交线，这些相交线首尾相连形成闭合回路：

　　接下来是要想办法将相交线内的网格面片剖离出来。相交线将构成骨骼网格的三角形分割成了3组：(1) 完全位于相交线内的三角形。(2) 完全位于相交线外的三角形。(3) 有一部分在线内，一部分在线外的三角形。

　　上图为骨骼网格切割结果的平面样例图，其中绿色的节点代表网格切割的切割点，绿色节点连线为相交线，红色区域表示完全处于相交线内的三角形(1)，蓝色区域表示完全处于相交线外的三角形(2)，绿色区域表示处于相交线边缘的三角形(3)。

　　事实上，我们只关心相交线内部和边缘的三角形，所以蓝色区域的三角形不予考虑。由于在计算相交线的时候，需要知道两个相交三角形的顶点，因此在计算时就可以对相交的骨骼网格三角形的三个顶点进行标记。红色的点表示处于切割网格内部的顶点，蓝色的点表示处于切割网格外部的顶点：

　　位于绿色区域的三角形需要做进一步的分割，首先将三角形沿着视线的方向投影到二维平面上，然后进行Delauny三角剖分，将原来的三角形变换成若干三角形的组合，最后再将这一组新的三角形逆向转换到三维空间中来。

　　接着，要找出所有相交线内部的三角形，这里使用的是深度搜索算法。该算法可行的前提是，相交线必须是闭合的。步骤如下：

　　1. 选取一个内部点(红点)作为起点，标记为已访问，寻找它的相邻三角形的顶点，压入栈中。

　　2. 取出栈中的点，此时有3种情况

　　　　(1) 该点为红点，不做任何处理，标记为已访问，将其相邻三角形顶点压入栈中。

　　　　(2) 该点为绿点，不做任何处理，标记为已访问。

　　　　(3) 该点无标注，标记该点为红点，标记为已访问，将其相邻三角形顶点压入栈中。

　　3. 重复步骤2至栈为空。

　　于是可以获得所有位于相交线内的三角形顶点：

　　也就获得了所有位于相交线内的三角形：

　　结合相交线细分割的三角形就得到了完全贴合骨骼模型表面的网格面片：

　　利用骨骼表面模型的顶点和三角形生成面片模型，结合凸分解的各个多边形最终组合成钢板的底部模型。钢板顶部面片模型由底部复制得到，延视线反方向平移一段距离，再利用两面片的外轮廓顶点生成侧面，最终形成闭合的钢板模型。