[胡言乱语]动态场景的数据结构[欢迎讨论]

sjinny

[胡言乱语]动态场景的数据结构


考虑在3D游戏中，对有大量运动物体的场景的组织。
使用一个SpaceNode来表示一块立方体形的空间区域，所有在里面的物体都作为子节点挂在这个SpaceNode下。
想象一块长方体形的很大的空间，这是整个场景范围，通过平行于XY、YZ、ZX的平面把它划分为(n^3)个边长相等的立方体区域，每个立方体区域可用一个SpaceNode来表示。当然对于其中没有任何物体的空间区域，就不必创建相应的SpaceNode。所以这些SpaeNode在内存中的组织形式不是数组而是链表。对于一个SpaceNode，它同时存在于三个双向链表中，从这个SpaceNode所代表空间的中心出发做一条平行于X轴的直线，与这条直线相交的所有空间区域的相应的SpaceNode按照它们的空间顺序依次组成一个双向链表，称为X轴链表。同样还有Y轴链表和Z轴链表。所以一个SpaceNode共需6个指针来保存它与相邻空间节点之间的关联。另外还需要6个标志位用来标示它的某个相邻节点是否在空间上与它紧密相接（比如它在X轴链表中的后继节点是否是与它在空间上紧邻的一个节点）。
一个场景中有三个SpaceNode链表，分别是X、Y、Z三个轴方向上的索引链表。
具体的细节可以参看“十字交叉链表”的结构。
http://www.baidu.com/s?wd=%CA%AE%D7%D6%BD%BB%B2%E6%C1%B4%B1%ED&cl=3

[code:1]
class SpaceNode
{
        int x, y, z;//一个SpaceNode所代表的立方体形空间区域的中心的座标（或空间矩阵中相应空间区域的下标）
        Object *objs;
        SpaceNode* around[6];
        char status;
        static int 半径;//一个SpaceNode所代表的立方体形空间区域的边长的一半
};

calss Space
{
        SpaceNode 轴s[3];//X、Y、Z三个轴的索引链表的原点节点（这里的节点只是作为坐标轴里的原点节点，所以它的左边或右边都可能有节点，所以它可能不是链表的头节点）
};
[/code:1]


1.运行过程中对场景数据结构的维持和维护
1.1相关的判断：
1.2相关的节点操作：
节点的增加、删除、合并、搜索等

2.相关的碰撞检测算法
由于有一个基本的假设：
“在一个场景更新周期内，一个物体的运动不可能一下子穿过3个紧邻的空间区域”，也就是物体的速度不会太快，每次更新物体位置时，它最多只会移动到这个空间区域周围的3*3*3-1=26个紧邻的空间区域中。
所以，这就意味着当物体的速度出于系统所能处理的速度范围以内时，每次更新物体位置时只需要检测它周围的26个紧邻的空间区域中是否有物体与它发生碰撞就可以了，当然实际过程中要先检测status，然后只对那些存在SpaceNode实例的空间区域（也就是其中有物体的空间区域）进行检测。另一方面，由于在设计游戏时要求一个SpaceNode的尺寸使其中可以存在的物体数目不会很多，所以可以采用“碰撞球－三角形检测”的两步检测方法进行检测。

3.相关的范围检测算法
似乎只是简单的沿着三个链表进行搜索的过程。

4.相关的RayTrace算法
似乎类似于碰撞检测算法。

antijp

光线追踪都出来了……

sjinny

  

笑

不懂。

lanche

sjinny 是一直想写太空游戏是吧，看看老外的例子： http://www.parsec.org/

sjinny

……………………………………
那家伙写的文档我看不下去………………

sjinny

下载了一个windows版的运行了一下……发现它对物理运动的模拟不完全……

背后的小刀

这种结构是最原始的结构了，采用一维结构来存储空间对象很烦琐。

更好一点的是R-tree系列的动态空间结构，目前多用于空间数据库中，但在内存中使用，效果也是很好的。不知道什么缘故，可能是学科障碍吧。动态空间数据结构的研究在ＧＩＳ，空间数据库等领域中被研究了已有３０年了，但在图形学中却鲜有人使用。有的书里高级一点，用了空间八叉树结构，但太浪费内存了，又弄出一种线性八叉树结构。这都是７，８０年代的技术了。

现在好一点的空间结构是Ｒ－tree的变种。国外的研究已经很深入了，空间层次表达的越来越准确。但国内的相关研究还是空头，高校里的那些所谓研究人员还尖着脑袋google国外的文献，剪贴到自己的论文里。

sjinny

晕，我这连不上google，baidu里找不到R-tree的入门资料……

背后的小刀

中文资料不是很多，关于空间数据结构的，这里有一份较好的资料http://course.cug.edu.cn/space_data_struct/zhishixuexi/

下文是从Guttman的论文(1986)中摘出的，由于当时Guttman主要研究二维数据的存储，在下文中扩展为N维了，我用了一个N维矩形的概念，一个N维矩形各边是平行于坐标系的，可以使用它的两个对角顶点坐标来表示,三维矩形就是长方体。。

R-tree是动态平衡树，是B-数向高维空间的扩展，只在叶结点中存储空间对象信息，其内部结点在空间对象查询时起路径导向作用。R-tree的结点由若干个结构为(MBR,pChild)的单元组成。pChild是指向子结点的指针，如果结点是叶结点，那么pChild是指向最小空间包围体中所包含的空间对象列表。MBR是pChild所指向的所有子结点的最小N维包围矩形。
设M为结点中单元的最大数目。 为非根结点中单元公开数的下限，R-tree则有如下限定：
(1)每个叶结点所包含的单元个数介于m和M之间，除非它同时是根结点。
(2)每个叶子结点中的单元(MBR,pObject)中，MBR是包含n维空间对象的最小空间n维空间包围矩形。pObject指向空间对象。
(3)每个非叶结点的子结点数介于m和M之间，除非它同时是根结点。
(4)每个非叶结点的单元(MBR,pChild)中，MBR是包含子结点的MBR，pChild是指向子结点的指针。
(5)根结点至少有两个子结点，除非它同时是叶结点。
(6)所有的叶节点都处于树的同一层上。

3        R-tree的构造方法
R-tree是通过MBR层次嵌套而形成的树状结构。每次向树中插入空间对象时，首先在树中为之寻找合适的叶结点，将空间对象插入叶结点中，当叶结点因新对象的插入而导致溢出时，就要进行分裂，叶结点的分裂有可能会引起其父结点的分裂，这种分裂自底向上进行。最终可以得到一棵平衡树。
        R-tree的构造算法主要由寻找合适的插入位置，结点分裂及树结构调整，这三个子算法构成。
(1)        为空间对象寻找合适的插入位置，设空间对象为p。
①        初始化结点A为R-树的根结点；
②        如果A是叶结点，则返回结点A的地址，A就是要找的叶结点L；
③        如果A非叶结点，将p依次加入到结点A的各子结点中，分别计算MBR的覆盖域增量，其中覆盖域增量最小的子结点N所在的子树即为存放p的叶结点L所在的子树，如果有多个最小覆盖域增量相同的MBR，那么就选择MBR最小的。令A为N，然后重复进行上面的步骤②和③。
(2)        结点分裂
当叶结点中所能容纳的空间对象数多于最大存储量M，就要对叶结点进行分裂，叶结点的分裂可能会引发上层结点的分裂。当根结点也发生了分裂时，树的高度就有可能要增一层。
R-树结点的分裂主要研究如何将一个n维矩形域分裂为适当的两个新的n维矩形域，这两个新的矩形域所包含的对象数之和要等于原矩形域中的对象数，且都不小于R-树结点的子结点数的底限m个。Guttman在二维R-树的研究中提出以分裂后的两个矩形域MBR1和MBR2的面积之和最小作为最优分裂的判定标准，企图尽量缩小分裂后MBR1与MBR2的重迭区域达到最小，但由于寻找最优分裂的算法的时间复杂度为 ，因而Guttman给出了两种近似最优的分裂算法，时间复杂度分别为 与 ,称为平方耗费算法与线性耗费算法。
事实上，Guttman所定义的最优分裂标准只能保证局部上是最优的。对于全局最优的标准及算法，Guttman没有给出，所以后来许多研究者提出了各种全局和局部的优化标准及算法，产生了R-tree的诸多变种。由于R-tree的变种在结点分裂和最优判定标准大都比R-tree更为合理，所以本文不再详述R-tree的结点分裂算法。
(3)        R-tree的调整
当一个叶结点添加了一个空间对象后，其MBR可能要发生变化，也可能会发生分裂，当对其进行调整后，又会引起其父结点的变化。所以每当空间对象插入到R-tree后，要自叶结点向上直至根结点进行调整。实际上调整路径就是寻找插入位置时所经路径，调整算法描述如下：
①        令A为为叶结点L，AA为因新的点插入而分裂的新结点(假如有的话)。
②        如果A为根结点，停止调整，返回。
③        调整结点A的父结点P中与其相应单元的MBR，使其正好包含A结点中的所有单元
④        如果存在因结点分裂而生成的新结点AA，则在A的父结点P中加入指向该结点的单元，如果P结点中单元个数超过M，则需分裂结点P，从而生成一个新的结点PP，并令A=P旁AA=PP。从②开始重复上面步骤。

调整算法返回后，如果根结点中的单元数超过M，则需将根结点分裂成两个结点，并再生成一个新结点作为R-树的根结点，而原根结点分裂成的两个结点作为其子结点。此时R-树增加一层。

关于R树的相关算法有许多，譬如近邻查询，范围查询，点查询等。另外对R-tree进行优化，产生了各种R-树的变种，再后来，有人干脆不用N维矩形作为包围体了，改用了球。还有人在结点分裂时采用了聚类分析方法。

背后的小刀

用R树最大的好处就是你的全部空间对象在建立结构时可以是未知的。

就好比给一群人盖房子，采用sjinny在首帖中的方式，就等于不用考虑有多少人，先划出一块地皮，然后在这快地皮上都盖满一样规格的房子，最后再为这群人分发房间。可能人很少，这样就浪费了许多空房子。而且有的人个头太高，住在那样的房间里憋屈。

而如果采用R树这样的结构，就变成了有多少人就盖多少房子，有多高个头的人，就为它盖多大的房子。

但正由于R树对数据的未知性，导致了空间对象不同的插入次序会生成不同的R树结构。这种思想是好的，但需要更高技能的优化，同时这也反映了R树深具发展空间的。

sjinny

恩……我今天数学课上又开小差想了会，现在对我的想法更新如下：

考虑一个立方体形的空间，尺寸为：width*height*length
若把它划分为N若干个一样大小的立方体，则可得i*j*k大小的立方体矩阵
设想一个数组：
Object* objs[j][k];
那么objs[x][y][z]就可以代表一个这个空间内的某个“格子”，而这个指针所指向的对象集合则表示了“占据”了这个格子的所有对象。
有一点要说明一下，那就是“占据”意味着一个物体可能同时占据不只一个格子，所以这个指针所指向的可能是一些Object对象的地址的列表（为了叙述方便这里全部用对象链表来表达），而同时每个对象里都要维护它所占据的所有格子的地址。所以即使物体比格子大也没关系。

再考虑另一种情况：
给出一个类：
[code:1]
class SpaceNode
{
        int x, y, z;
        SpaceNode* nears[3][3][3];
        Object* objs;
};
[/code:1]
这个类显示出这里的一个SpaceNode除了要维护占据了自己这个格子的对象列表外，还需要维护自己与周围的SpaceNode之间的关联。设想一个立方体空间被划分成3*3*3个小立方体时的情形，观察最中间的那个立方体，可以发现对于空间中的一个立方体，它需要维护它和周围的3*3*3-1=26个立方体之间的关联。这样一个立方体会同时存在于13个双向链表中，在每个链表中，若有格子里没有任何对象则可以把它删除，链表从这个格子这里跳过去。这样可以节省空间，相比于上面一种方法，同样的存储空间可以用来表示更大范围的空间，这里的SpaceNode可以看成一个容器。但是问题是，在程序运行过程中，由于会有很多物体是在不断运动的，所以会因为维护大量的链表而是效率降低。

所以我考虑的是，应该把两种方法结合起来以达到时间和空间的平衡。
所以初步设想是这样的：
一个场景中，有多个用第一种方法组织的空间区域，然后在这些空间区域之间建立联系，当物体在这些空间里的时候，管理它们所用的空间节点其实其实数组里的一个元素，当物体离开这些空间时就要为其创建一个新的小的容器（当然大小还是和其他格子一样的，只是如果一个格子不够可以用多个格子），并在容器和其他的空间区域之间建立关联。
对于一个典型的场景，其中有一定数量的运动物体和一定数量的静止物体。
所以的静止物体都是保存在一个场景文件中的，这个文件里还保存了针对这个场景优化的场景组织数据，主要是把场景的静态部分划分为若干个大小尺寸不等的空间区域（使用第一种方法对这些空间区域的内部进行组织），并在这些区域之间建立关联。动态物体在场景文件被读取后再按照第二种方法加入场景。