空间数据结构和碰撞检测
空间数据结构的组织通常是分层级的，这意味着，最高层包含一些子层，每个子层定义自己的空间体积，而这些空间又包含自己的子层，因此，该结构是嵌套的，具有递归性质，这个层次结构中的一些元素引用了几何体。使用层次结构的主要原因是,对不同类型的查询会更快,通常一个能够从O (n)提升到 O (log n)。也就是说,与其搜索所有n对象,我们只需要访问一小部分再执行操作,比如在一个给定的方向寻找最接近的对象。
虽然查找变快了，但是，空间数据结构的构造却可能需要花费时间。并且这取决于其内部几何形状的数量和所需的数据结构的质量，然而，该领域的重大进展大大减少了构造时间，在某些情况下甚至可以实时完成。使用lazy计算和增量更新，可以进一步减少构建时间。
参考：https://zhuanlan.zhihu.com/p/403554758?utm_id=0
>>SceneGraph(场景图)：
>>层次包围盒(BVH)树：https://www.codetd.com/article/14793027（物体->包围盒->重叠时的分配问题）
练习6(games101)：在之前的编程练习中，我们实现了基础的光线追踪算法，具体而言是光线传输、光线与三角形求交。我们采用了这样的方法寻找光线与场景的交点：遍历场景中的所有物体，判断光线是否与它相交。在场景中的物体数量不大时，该做法可以取得良好的结果，但当物体数量增多、模型变得更加复杂，该做法将会变得非常低效。因此，我们需要加速结构来加速求交过程。在本次练习中，我们重点关注物体划分算法 Bounding Volume Hierarchy (BVH)。
第一步：求每个物体的包围盒。
第二步：建立BVH树。从Root->(AB)+(C)->A-B+C。分别为一级节点-二级节点-三级节点。
根据每个多边形的面积大小来定义它属于哪个层级吗？
四叉树的缺点：上面提到的四叉树模型是个理想概念。实际问题中是不会有完美的点，对象都是有一定大小的，比如我们的方块。当方块与多个节点区域相交时怎么办？这里就有两种方案来处理这种情况。下面例子中最大对象数设置为2。（假如更极端一点：物体彼此紧挨着呢？根本无法分割。那么只能分一级，只有一个root。只有一个0级root节点了。）
