最近一段时间关于空间数据的学习心得,希望能得到指导.

Mao!

空间数据结构

空间数据结构往往是层次体，就是最高层次包含它下面的层次，依次类推。虽然这种数据结构建造的开销比较巨大，但就游戏来讲，可以做为一个预处理处理过程来完成。而且这样可以明显的提高各种类型的查询速度。

现在流行的空间数据结构大致有这么几种：

1.二元空间分割 （BSP）
2.四叉树 （Quad Trees）   
3.八叉树 （Octrees）
4.包围层次体 (BVH )

BSP、Quad Trees、Octrees都是进行空间细分的数据结构

他们有一个比较明显的特点就是，所有叶子节点的空间集合等于整个场景空间，而且叶节点互相不会产生重叠。（一些新的方法比如松散树（Loose Tree）除外）

虽然这种方式的均匀性限制比较大，但是却可以有效的提高效率。

这种依靠递归分解的数据结构，往往需要具备以下两种性质。
1.为了使该分割可用于任意大小的图象,它应该采用无限重复的模式.
2.可以从该无穷分解中得到更多,更好的模式.

包围层次体不是空间细分结构，它只是将物体周围的空间包围起来，而不需要包围所有的空间。

二元空间分割树（BSP）
BSP一般来讲分为两类，轴对齐BSP和物件对齐BSP。前一种方式个人认为用处不大，重点介绍后一种。

物件对齐BSP，先选取一个物件的边作为分割物，对空间进行平分。然后再于每个半空间中选取另外一个边进行分割，直到所有的多边形都处于BSP树中。虽然非常耗时，但通常只需要计算一次，可以储存起来进行重用。

使用BSP的主要原因是因为它可以对空间中的图元进行排序来保证渲染图元的顺序是按照由后至前进行的，它可以解决比如画家算法的一些缺点：
1.如果一个物体从另一个物体中穿过时它不能被正确的渲染；
2.在每一帧对被渲染的物体进行排序是非常困难的，同时运算的代价非常大；
3.它无法管理循环覆盖的情况

有两个很好的文章非常棒，这里就不累述了。
Dreams大大的《BSP技术详解》.noslopforever大大的BSP分割算法简述.
                                                                     07.7.13 待续