BSP分割算法补充——关于分割一个三角形

BSP分割算法补充——关于分割一个三角形

上篇文档写完后，做了一个比较复杂的场景，进行分割后发现原算法的一些问题，在此做一个补充。根据此补充，原文档将被删掉重新修改完后再发，对各位读者造成的不便，希望大家能够见谅。

在上篇文章里谈到的分割算法里有关被分割面的处理，采取的是直接将被分割面正负都放的策略。当时认为这只会对AABB的计算产生影响，所以也就堂而皇之这么写上去了。这个算法虽然简单，但是在之后的Portal处理时会面临很多困难，这一点也是我开始没有考虑到的。

在将场景变得复杂之后，这个问题就越发显现出来：在有些叶子，将会仅包括若干被分割的共享三角形，且这些三角形根本无法构成封闭空间。然而，这些叶子却被送入了Portal计算，最后出来的Portal非常诡异，甚至包括了在同一面上的若干个Portal。

用更多的思路更改Portal算法，倒不如从根本上将空间分割得更为合理，也就是采取标准的做法：将被分割三角形分割开，分割为多个三角形，分别放入相应空间。

其实这个算法很简单，一个三角形如果被一个平面分割，直观上看，有且只有两种情况：一种是在正负各生成一个三角形；另一个是在一侧有一个三角形，另一侧有两个三角形。直观上说，无论哪种情况，关键算法流程都是：

顺序访问原三角形的边，设边的第一个顶点是v0，第二个顶点是v1。

如果这个边的两个顶点均在平面一侧，则两个顶点算入平面相应一侧的新多边形。

如果有一个点在平面上，则这个点如果是这个边的第一个顶点，应该在平面两侧的新多边形中都要放。如果是第二个顶点，则需要判断第一个顶点在平面的哪一侧，并将之放入相应空间（只放一次）。可参考下图（左）来进行理解。

如果这个边被平面切割，则：首先算出来切割后的顶点vip，注意这里需要根据顶点格式分割，法线、纹理坐标均应分割。这时，同样是判断第一个顶点在平面哪一侧，根据此，把v0、vip、v1按照相应顺序组合，分别放到两侧的多边形中（在这过程中，vip会两侧都放）。

这个算法有几个需要注意的地方：

首先，为了生成顶点顺序与原三角形一致的三角形（即顺时针三角形生成后仍是顺时针，逆时针三角形生成后仍是逆时针），我们必须要按照相应的顺序遍历原三角形的边：v0-v1、v1-v2、v2-v0，只有顺序访问原三角形的边才能保证生成后的三角形的顺序。如果一开始的顺序就很诡异，那么最后生成出来的三角形顺序将很难保证，代码也会很不直观。

第二，分割出来两侧的是多边形而不是三角形，这需要分开判断，如果多边形的顶点数量是3，说明这一侧生成的是一个三角形，那么就好办了，直接使用这个三角形即可。如果是4，说明是一个四边形。如果设四边形顶点顺序是v0 v1 v2 v3那么，组成这个四边形的两个三角形分别应该是v0-v1-v2和v0-v2-v3。具体的推导过程就不说了，如果觉得难于理解，可以参考下面的图，就容易明白了。其中，OV是指原始三角形的三个顶点，V是分割后的这个四边形的四个顶点，请注意顺序。

第三，注意法线的切分，如果两个顶点的法线方向正好相反（当然，这是特殊情况），那么最后生成的新顶点的法线会是0！在这种情况下，法线需要单独作一下处理，我的处理是将整个面的法线赋给这个顶点，当然，您也可能有更好的方式。

第四，在分割中会生成新的顶点和面，所以最后BSP的顶点数和面数经常会超过在模型原始数据里的顶点数和面数。但现在由于没有被两个叶子共同共享的三角形了，所以，一个叶子中的三角形可以统一建一张IB，一次渲染了，速度当然会比使用共享面要快。

切分算法并不是唯一的，正如BSP分割的方式也并不唯一一样，关键还是选择对自己最容易掌握，最有利的算法。