BSP二叉分割树

用超平面分割初始的空间，分割后两个空间保存为左孩子和右孩子，并将分割后的多边形村住在List中；取出存住List中的多边形，通过迭代或者递归，产生新的节点并加在父节点上。

BSP二叉分割树

• 算法内容
  • 通过二叉树的左子树右子树来区分分割平面的前后
  • 节点表示分割平面
  • 叶子表示被分割的空间
  • 通过树逻辑来快速判断物体的遮挡关系
• BSP生成步骤
  • 首先，选择一个超平面和根节点。我们2D选择的是一条线分割空间，3d就是用面来分割空间。
  • 用超平面分割初始的空间，分割后两个空间保存为左孩子和右孩子，并将分割后的多边形村住在List中。
  • 取出存住List中的多边形，通过迭代或者递归，产生新的节点并加在父节点上。
• BSP树的实现
  • 分析每个node要做什么，由什么组成·
  • 分析树要做什么，basecase是什么
• 优点
  • 算法简单高效，提升游戏关卡渲染速度
  • 在给定观察点快速确定物体遮挡关系，提高计算效率
  • 高效碰撞检测
• BSP分割
  • 遍历当前节点的所有备选平面，寻找一个合适的分割平面。
  • 如果找不到合适的分割平面，这个节点是一个叶子，Return。
  • 如果找到了，Mark这个平面已经被使用过
  • New两个新节点，一个为正向节点，一个为负向节点，挂接到本节点下。
  • 遍历所有结构化面
  • 如果结构化面在分割平面的：
    • 正向：将这个结构化面和结构化面所对应的平面放入到正向节点。
    • 负向：放入到负向节点。
    • 如果结构化面被分割平面分割，则分割此三角形，并将分割后的结果放入相应的子节点。
  • 遍历所有细节面。
  • 遍历完毕，节点所需保留的数据只需要是分割平面和两个下级节点的指针即可。
  • 对两个子节点，分别从1开始递归执行。