BSP（⼆叉空间分割）树（做模型分割的时候碰到这个算法了转载⼀下做个笔
记）
BSP（⼆叉空间分割）树是另⼀种类型的空间分割技术，其已经在游戏⼯业上应⽤了许多年（Doom是第⼀个使⽤BSP树的商业游戏）。尽管在今天BSP树已经没像过去那么受欢迎了，但现在仍在⼴泛地采⽤这项技术。
当你看⼀下BSP在碰撞检测⽅⾯那极度⼲净漂亮和⾼速的效率，⽴刻能让你眼前⼀亮。不但BSP树在多边形剪切⽅⾯表现出⾊，⽽且还能让我们有效地⾃由运⽤world-object式的碰撞检测。BSP树的遍历是使⽤BSP的⼀个基本技术。碰撞检测本质上减少了树的遍历或搜索。这种⽅法很有⽤因为它能在早期排除⼤量的多边形，所以在最后我们仅仅是对少数⾯进⾏碰撞检测。正如我前⾯所说的，⽤出两个物体间的分隔⾯的⽅法适合于判断两个物体是否相交。如果分隔⾯存在，就没有发⽣碰撞。因此我们递归地遍历world树并判断分割⾯是否和包围球或包围盒相交。我们还可以通过检测每⼀个物体的多边形来提⾼精确度。进⾏这种检测最简单的⼀个⽅法是测试看看物体的所有部分是否都在分割⾯的⼀侧。这种运算真的很简单，我们⽤迪卡尔平⾯等式 ax + by + cz + d = 0 去判断点位于平⾯的哪⼀侧。如果满⾜等式，点在平⾯上；如果ax + by + cz + d > 0那么点在平⾯的正⾯；如果ax + by + cz + d < 0点在平⾯的背⾯。
在碰撞没发⽣的时候有⼀个重要的事情需要注意，就是⼀个物体（或它的包围盒）必须在分割⾯的正⾯或
背⾯。如果在平⾯的正⾯和背⾯都有顶点，说明物体与这个平⾯相交了。（以上载选⾃百度百科）
Bsp分割算法简述
Preview
BSP分割算法也是有不少⽂章可以借鉴的，就我⽬前能掌握的资料来看，泛泛⽽谈者⼤有⼈在，实际去作的时候却总是抓瞎。知道是什么永远不如知道怎么做，BSP分割是BSP分析的基础，虽然它很简单，但是，如果连简单的都不会做，⼜怎么能胜任复杂的⼯作呢？
趁这段时间有空，遂埋头钻研BSP，⼀周之后，分割和⾃动Portal⽣成均已解决，遂做此⽂，希望能对初学者有所帮助，亦希望能抛砖引⽟，众位⾼⼿能不吝赐教。
本⽂先就BSP中相对简单的分割部分做⼀个简单的介绍，⾃动Portal⽣成的资料正在整理，希望能尽快放出。
BSP的基本原理
试想我们⽣活的空间，肯定是由为数众多的天花板、墙壁和地板组成，对于每⼀个“板”，都将空间分为“板前”和“板后”两个部分。已知⼈的位置，就可根据⼈在“板前”还是在“板后”，知道⼈所能看到的物体的遮挡顺序（e.g.如果⼈在板前，则板前的物体遮挡所有板后的物体）。
BSP者，原理很简单：它试图将所有的板（在BSP中叫做平⾯）组织成⼀棵树，每个平⾯均将它所在的空间分割为前后两个部分，这两个部分⼜分别被另外的平⾯分割成更⼩的空间……直到最后，按照前⾯所说的算法，确定每⼀个房间（在BSP中叫做叶⼦）相对于眼睛的遮挡顺序。
这是⼀个⾮常标准的⼆分法，仅按照“前”和“后”两个逻辑上的概念来切分空间，这使得它在以“房间”为单位组成的室内场景⾥是不⼆之选。为什么？请接着看：
在判断遮挡顺序的时候，BSP空间的算法极为简单：只需要从树根开始，简单判断⼈的位置与所有平⾯的前后关系：前则正⼦树（在平
⾯“前”⽅的空间）在前，负⼦树（在平⾯“后”⽅的空间）在后；后则正⼦树在后，负⼦树在前。以此递归到叶⼦（叶⼦总是⼀个房间），就可以确定⼈处于哪⼀个房间之中、其他房间的遮挡关系如何。
这个其实很简单：因为所有的平⾯均将其所处的空间分为前后两个部分，所以，每⼀个房间，均是由若⼲平⾯的“前”“后”来决定的，通过⼈与这些平⾯前后关系的判断，⾃然⽽然就可以直接定位到所需的房间之中了。这就是BSP算法的特别之处。
如图：空间ABC由A、B、C三个独⽴的房间组成，⾸先，分割平⾯1将空间分成了平⾯正向的A房间和平⾯负向的BC空间，BC空间被2紧接着分割为平⾯2正向的C房间和负向的B房间。注意这⾥平⾯的⽅向⼀般由墙壁⾯向的⽅向⽽定。
如果有⼀个⼈处于C房间内，那么如何判断所有房间的遮挡顺序呢？从树根开始，由于⼈处于平⾯1的“后”⾯，所以，BC空间应该先于A 房间（后：先负后正），然后，由于⼈处于分割平⾯2的“前”⾯，所以，C房间应该先于B房间（前：先正后负）。这样，整个房间离⼈由近到远的顺序就可以确定了：C－B－A。仅需要通过两次平⾯的前后判断（总共六次乘法、两次加法、两次⼤⼩判断），就可以确定空间的先后顺序，算法的威⼒可见⼀斑！
BSP分割的⽬标是将空间划分为⼀个个叶凸体，也就是⼀个凸⾯体。⼀个个凸⾯体才有排序的可能，很难想象⼀个⾮凸⾯体在空间中如何排序。如图左：从箭头⽅向看过去，到底凹多⾯体A是在B的前⾯？还是B在凹多⾯体A的前⾯？⽽如果是右边的，两个凸多⾯体，情况就不⼀样了，A和B⽅向的前后，根据视点的位置永远是唯⼀的。这就是BSP的优势，只需要知道视点的位置，空间所有凸体的位置顺序都可以马上确定，但如果是凹体，对不起，那就确定不了了，所以，BSP划分空间结构化⾯的结果必然是⼀个个凸⾯体。
这⾥⾯唯⼀想强调的⼀点是，如果您分析过Quake3的BSP格式，那么您会发现过去有时候⼀个房间会被⼏个柱⼦分割得乱七⼋糟，只是为了少渲染⼏个⾯。现在⼤不必这么兴师动众，⼀个房间就留外⾯的6个结构化⾯，柱⼦什么的只算作细节Mesh，不参与分割，这样产⽣的结果，与Portal筛选结合之后，效率未必就差。⽽且，结构更符合逻辑，在以后⾃动路点和路径计算的时候，会有⼀些优势。想想看，被⼀个很不规则的柱⼦（或箱⼦等其他物体）划分得乱七⼋糟的空间，⼀个房间就有很多个叶⼦，到底
哪些叶⼦是⼈能⾛到的？哪些叶⼦是⼈⾛不到的？哪些叶⼦需要在AI中被考虑？哪些叶⼦可以排除？⼀个不以逻辑构成的空间，必然在逻辑的处理上要处处碰壁。所以，最好还是⼀个叶⼦就是⼀个房间、或者⼀个⾛廊；柱⼦、箱⼦啊什么的全都⽤细节Mesh，就可以了。
注意，BSP划分出的凸体其实主要是为了后⾯BSP分析⽽进⾏的，⽽不是渲染。早先的时候硬件很糟糕，没有Z缓冲，那时候省⼀个三⾓形⽐现在重要得多。现在？有时候宁可多画⼀堆三⾓形也不会去浪费那个CPU资源进⾏三⾓形的逐个筛选。所以，尽量减少结构化⾯，使结构化⾯的房间组成凸体，但细节⾯把房间装点成什么样，那就⽆所谓了，即便细节⾯将这个空间⼜变成了⼀个凹体，也是⽆所谓的，如图：
由于是⼀个⽼算法了，因此BSP分割算法早已经不是什么神秘的东西，这个算法有很多例⼦，推荐《BSP技术详解》（翻译后的名称如此），唯⼀的遗憾是这篇⽂章的伪代码需要花点⼼思。另外，《3D游戏 卷2 动画与⾼级实时渲染技术》所带的FLY 3D引擎也有很完整的代码，虽然整个看下来⽐伪代码还难懂，但是每个函数基本上都还算清晰，也是⼀个难得的备选资料。
当然，可能⼤部分⼈还是倾向于去看Quake和HL2的代码。为了使⾃⼰加深印象，我所选择的是⾃⼰从零开始，仅按照资料上的观点和流程进⾏DIY，⽽没有参考代码。因为经常参考着、参考着就“拿来主义”了，虽然开发效率保证了，但是记性不清，⼀旦扩展起来，基本抓瞎^_^b。所以这次狠狠⼼，决定享受⼀次DIY的乐趣。
准备⼯作：场景数据
进⼊⼯作状态，第⼀个问题是场景数据的配置。BSP的难度⼀定程度上不是算法本⾝带来的，BSP算法很简单也很明确，并没有太多复杂的东西在⾥⾯。复杂的是⼤凡好的BSP都需要和编辑器结合起来，以进⾏Portal、Brush、Entity和Path Point诸如此类的定制，直接从3D Max导出⼀个Mesh然后就进⾏分析，这个从实践上限制太多、意义不⼤，所以，与其说BSP分割很难，倒不如说是BSP的编辑器难做。记得⼀本⽼书上曾经说过，BSP编辑器的代码是BSP分割算法的10倍有余，仔细想想，确实如此，⽽且只会有过之⽽⽆不及。
在实践中，我采⽤了《3D游戏》的⽅法，这个⽅法是，通过在3D Max中物体的名称来区分⼀个物体的这些⾯是属于“结构化⾯”（分割平⾯）、“细节⾯”（不参与分割的⾯）还是Entity。由于3D Max Script⽀持使⽤前缀将⼀组物体放⼊⼀个Array中，所以，使⽤⼀个简单⽽明确的前缀是⼀个很好的思路，《3D游戏》使⽤了*、&这些符号，⽽我则使⽤了S（Split）、D（Detail）、E（Entity）。例如
SBox01说明这个Box01的所有⾯均是结构化⾯，要参与BSP分割和分析，⽽DSphere01则说明这个Sphere01在BSP的分割和分析中将会被忽略。这中间的主要⼯作集中在3DMAX Script的撰写（或者插件的撰写），所以就不再多说了，对这个技术还⽐较⽣疏的，可以参考⽹上相关的内容。
从3DMAX中读出来Object后，其所有的顶点和⾯索引都已知了，将所有顶点组织成⼀个顶点表，所有的
结构化三⾓形组织成⼀个结构化三⾓形表（这⾥的三⾓形是指顶点索引），这个⽐较简单，应该不是问题。
数据进⼊我们的程序，第⼀件事情就是要⾸先计算出所有的平⾯，因为不同的结构化⾯可能共⽤⼀个平⾯，所以，这⾥先需要计算出所有的平⾯并在平⾯和结构化⾯中建⽴关系，以防⽌同⼀个平⾯被两次以上使⽤，影响BSP⼆分逻辑的正确性。D3DX给出了专门的函数
D3DXPlaneFromPoints，可以很⽅便地从⼀个三⾓形产⽣出⼀个平⾯来。⼀个新的平⾯算出来后，检查⼀下这个平⾯是否已经⽣成过了，如果没有，就算作⼀个新平⾯并记录其ID，否则就要舍弃这个新平⾯，转⽽采⽤原有平⾯的ID。直到最后，为所有的结构化三⾓形给出其对应的平⾯ID。这中间注意⼀下D3DX的平⾯公式是ax+by+cz+d=0，⽤的是+d，不是-d，在之后的计算中需要注意。
准备好顶点表、结构化三⾓形表和平⾯表之后，分割就可以正式开始了。相对于3DMax Script和插件⽽⾔，BSP分割的算法本⾝容易得让⼈崩溃，不多说了，下⾯开始！
BSP分割
⾸先，⾃然是要先产⽣⼀个根节点，并把所有的顶点表、结构化三⾓形表和平⾯表⼀股脑塞进这个根节点中咯。
然后，分割的流程⼤抵如下：
1 遍历当前节点的所有备选平⾯，寻⼀个合适的分割平⾯。
2 如果不到合适的分割平⾯，这个节点是⼀个叶⼦，Return。
3 如果到了，Mark这个平⾯已经被使⽤过。
4 New两个新节点，⼀个为正向节点，⼀个为负向节点，挂接到本节点下。
5 遍历所有结构化⾯。
6 如果结构化⾯在分割平⾯的：
正向：将这个结构化⾯和结构化⾯所对应的平⾯放⼊到正向节点。
负向，放⼊到负向节点。
如果结构化⾯被分割平⾯分割，则分割此三⾓形，并将分割后的结果放⼊相应的⼦节点。
（注意，这⼀步当发现结构化⾯所对应的平⾯已经被Mark的时候，就只放结构化⾯，不放分割平⾯了，以防⽌同⼀个平⾯⽤于分割两个以上空间，违反BSP空间⼆分逻辑的唯⼀性）
7 遍历所有细节⾯。细节⾯的处理与结构化⾯类似，只不过这⾥不⽤考虑到细节⾯对应的平⾯问题，更简单。
8 遍历完毕，由于所有的结构化三⾓形、平⾯和细节⾯已经转移到两个⼦节点中了，因此从本节点中解掉所有的结构化三⾓形、平⾯和细节⾯的引⽤。节点所需保留的数据只需要是分割平⾯和两个下级节点的指针即可。
9 对两个⼦节点，分别从1开始递归执⾏。
这样，等⼀切结束的时候，就是⼀棵完整的BSP树了，所有的节点中仅保留有节点的分割平⾯和两个下级节点，⽽渲染严重相关的结构化三⾓形和细节⾯则全都在叶⼦⾥。最后，只需要顺根递归，将所有的节点组织成节点表就可以了。我在这⾥分别是将节点组织成了节点表，将叶⼦组织成了叶⼦表。您也可以通过为节点加⼀个Is Leaf属性来将它们统⼀放到⼀个节点表⾥。
现在，⾯临最主要的问题是，在所有的结构化⾯中，如何寻⼀个分割平⾯？
⾸先，分割平⾯必须是对于凹多⾯体⽽⾔的，已经形成了凸多⾯体的空间就不必要分割了。对于⼀个凹体⽽⾔，分割平⾯必须在平⾯的正负⽅向均出现三⾓形。如此递归分割下去，就能保证将空间最终分割成⼤量凸多⾯体集合。如下图左，1、4在平⾯的⼀⽅没有出现三⾓形，应被舍弃，2、3均可以作为备选的分割平⾯：
分割平⾯的选取是⼀个⽐较“笨”的办法，可偷懒的机会不多，只能是for each的判断。对于每⼀个平⾯，算出⼀个⽤于判断的值，在所有值中最⼤（或者最⼩，视算法⽽定）的那个平⾯就是最佳分割平⾯。最简单的，永远只选取第⼀个结构化三⾓形的平⾯分割，但是这样分割下来的空间会惨不忍睹。分割出来的结果最好是让⼀棵树平衡的那个做法。因为平衡⼆叉树的操作⽐不平衡⼆叉树要快，冗余度要⼩很多。
计算出最优平衡⼆叉树⼏乎是不可能的，但在近似层⾯上保证⼆叉树尽可能平衡的算法很多，《3D游戏》采⽤的是：
P=分割后处于正向的三⾓形数
N=分割后处于负向的三⾓形数
S=被从中切开的三⾓形数
Value = P – N + 8 × S
这个值最⼩的那个就是最好的平⾯。也就是说，正负向三⾓形数量最接近、且切开三⾓形最少的那个平⾯就是最好的分割平⾯。
如上图右，7、3、5均可以作为分割平⾯，但是，⾮常明显：3就⽐7和5要好得多，因为其正负⽅向的三⾓形数最接近，且没有切割任何三⾓形。
这个算法在实际使⽤上，并不⼀定能⽣成最优树，但它简单⽽且直观。没有最好的算法，只有最适合的算法，算法的选择不是唯⼀的，基本上应该根据空间的特点进⾏，所以这⾥就不再多说了。总之，能尽量分割出平衡⼆叉树的⽅法就是好的⽅法。
BSP分割完后，产⽣出来的节点表和叶⼦表，其中，节点表构成了BSP树的树⼲，叶⼦表存有所有的结构化三⾓形和细节Mesh，将被⽤作之后分析的基本数据源。⽽在所有的分析中，⾸先应该进⾏的就是Portal的分析，Portal分析完毕后，PVS等分析才有可能。⽽Portal和PVS，则是BSP空间分割最有魅⼒的两个部分，在最新的商业引擎中，仍能看到他们的影⼦，⽽且，⽐起90年代初，只会有过之⽽⽆不及……
补充和校正
关于分割⼀个三⾓形
上篇⽂档写完后，做了⼀个⽐较复杂的场景，进⾏分割后发现原算法的⼀些问题，在此做⼀个补充。根据此补充，原⽂档将被删掉重新修改完后再发，对各位读者造成的不便，希望⼤家能够见谅。
在上篇⽂章⾥谈到的分割算法⾥有关被分割⾯的处理，采取的是直接将被分割⾯正负都放的策略。当时认为这只会对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分割的⽅式也并不唯⼀⼀样，关键还是选择对⾃⼰最容易掌握，最有利的算法。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。