基于Unity3d 的mesh 切割及优化

文/刘柯壮 贺体刚

1 问题分析

在VR 项目中，玩家需要用模拟的刀将飞过来的三维模型切开，被切到的模型应精确的沿切面分成两个模型，并且生成的模型碎片也要允许切割。

由于每次挥刀的角度、方向和切割次数都是不确定的，所以无法用固定的几个动画来达到准确的切割效果。经过考虑，最终将问题的解决方向定在了模型的mesh 切割上。

对于模型的mesh 切割，首先确定以下两个前提：

（1）被切割的模型面数较低。

（2）被切割物体为凸多面体。

为了将问题简化，我们可以先假设这样一个需求：空间中有一个立方体，目的是要以任意一个角度将模型分为两半。

2 解决方案

在Unity 创建的cube 中，如果被切割源从中间分为两半后，在切面处将会产生新的顶点和三角面，问题的关键就在于如何确定新生成的顶点和三角面、如何补全剖面以及如何优化。

2.1 确定切割源

即立方体在什么位置以什么角度被切开，这里我们可以把切割源想成一个平面，将立方体分为两半。这里采用平面的点法式来确定这一平面，即需要获取平面上一点和平面的法向量。

2.2 顶点分组

将一个立方体分为两半，先要把立方体是的顶点分为两组，分组依据是顶点是否在切割源的同一侧。利用切割源点到各个顶点的向量与切割源的法向量的点乘的正负性来判断，将结果存入一个bool 类型的数组中，数组名为above，供后面使用。

2.3 构建三角形索引数组与创建剖面点

以mesh 三角形索引的顺序依次访问3 个顶点对应的above 值。如果这三个above 值相同，则表示整个三角面都在切割源的一侧，不需要做任何修改。如果三个顶点的above 值不相同，则表示该三角面将会被切割源分为两半。这时三角面的两条边必然都与切割源所在平面交于一点，这两个点就是切割之后要生成的剖面点。将计算剖面点坐标转化为以下数学问题：

已知：平面的法向量（切割源法向量），平面经过一点的坐标（切割源经过的一点），直线经过两点的坐标（三角面一条边的两个顶点）。求：平面与直线的交点。

设：平面的一点为n（n1,n2,n3），平面法向量为Vp（Vp1,Vp2,Vp3），直线经过一点为m（m1,m2,m3），直线方向向量为V（V1,V2,V3）。

可求得焦点坐标O：O=m+V*t

将两个剖面点计算出来后，将一个三角面拆分为3 个三角面加入相应的三角形索引集合中。重复经过以上步骤，便可以将所有的剖面点分配到相应的集合中。整个立方体已经被切割源分到了两边，但被切开的剖面处是不闭合的。

2.4 连接剖面三角形

首先，剖面顶点集合是无序的，导致无法立即确定要连接的剖面三角形索引。但是，在以上方法生成剖面点的时候，可以发现两个特点：

（1）剖面点列表中按索引第i（偶数）个点与第i+1 个点是相连的，一定构成三角面的一条边。

（2）每个剖面点处其实都被重复生成了两次，这两个重合点连接着其他不同的剖面点。

选定剖面顶点中第一个点作为定点，定点之后的两个点作为活动点（i 和i+1），以逆时针的顺序旋转一周，遍历完所有顶点，该过程中两活动点每次都与定点连接一次，通过切面的法线确定三个点的连接顺序。最后会得到一个以定点向其他各点“发散”的结构。

根据第一个特点，我们可以确定一个剖面三角形的两个顶点，一个作为定点，另一个为活动点，再根据第二个特点确定第三个顶点，构成三角形。方法是先找到两个顶点的其中一个的重合点(可以根据遍历剖面点列表，根据两点的距离小于极小值确定重合点)，再找到该重合点所连接的点，这个点就是需要找的剖面三角形的第三个顶点。连接这个三角形之后，将第三个顶点作为活动点，以上述同样的方法寻找第三个顶点。

以此方法旋转一周，剖面连接完成。

2.5 对剖面点进行优化

虽然程序运行起来，模型可以切割了，但遗憾的是切割物体产生的速度太慢，多次切割很容易卡死，在剖面处会经常出现“破面”情况。

观察上述的第五步，可以感觉到那里的运算和复杂，并且不够精确，多次切割很容易产生密集的三角形，剖面点也会在一个很小的区域内集中，这样通过距离计算的重合点就很容易找错，造成后续的崩溃和“破面”。为了方便剖面的顶点的连接，我们必须要确定连接各顶点的依据，并将它们以一定顺序排列。

由于剖面点是依据三角面的边生成的，而mesh 上的三角面是两两相连的，即每条边都是两个三角面的公共边，这就导致给个位置剖面点其实是重复生成了两次。这种情况的危害是占用不必要的资源，如果不做优化的话运行效果是不能让人满意的。

下面我们仅对切面是凸多边形的情况进行考虑。

优化方法：

（1）确定任意一条边的两个顶点，以此确定为原点和基边。

（2）对边缘点列表进行排序，可按照以下依据：以某一点和原点的连线与基边的夹角按从小到大的顺序。

（3）遍历剖面顶点，标记出重合点，可以按照以下依据：两点的距离的平方<极小值（极小值设置为1e-6）。

（4）复制出新的无重合点的剖面集合。

（5）排除共线的无效点。①生成剖面时，有出现许多剖面点共线的情况，其实在这些点中，除了两个端点需要保留外，中间的共线点都是不必要的，为了减少生成三角面的数量，提高运行的效率，尽量的减少无效的顶点是必要的。②排除共线无效点的依据：a=第i 个顶点与第i-1 个顶点的向量；b=第i+1 个顶点与第i 个顶点的向量；如果a 与b 夹角的绝对值<极小值，则表示三点共线，排除第i 个点。

经过这样的优化后，顶点集合的大小就小多了，尤其是在连续切割下，剖面的三角面数量会以指数形式增长，该方法通过大量减小基底来避免三角面数过高。

之后的连接剖面三角形，只需要选定剖面顶点中第一个点作为定点，定点之后的两个点作为活动点（i 和i+1），以逆时针的顺序旋转一周便可以连接完成。

3 运行效果

将经过优化的程序运行，运行效果有了相当大的改善，对于一个立方体，可以连续切割十次左右而不卡顿，崩溃的情况解决了，“剖面”极少发生。对于“球体”这样的较高面模型也能应对。