|
|
[胡言乱语]动态场景的数据结构
考虑在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
- 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三个轴的索引链表的原点节点（这里的节点只是作为坐标轴里的原点节点，所以它的左边或右边都可能有节点，所以它可能不是链表的头节点）
- };
1.运行过程中对场景数据结构的维持和维护
1.1相关的判断：
1.2相关的节点操作：
节点的增加、删除、合并、搜索等
2.相关的碰撞检测算法
由于有一个基本的假设：
“在一个场景更新周期内，一个物体的运动不可能一下子穿过3个紧邻的空间区域”，也就是物体的速度不会太快，每次更新物体位置时，它最多只会移动到这个空间区域周围的3*3*3-1=26个紧邻的空间区域中。
所以，这就意味着当物体的速度出于系统所能处理的速度范围以内时，每次更新物体位置时只需要检测它周围的26个紧邻的空间区域中是否有物体与它发生碰撞就可以了，当然实际过程中要先检测status，然后只对那些存在SpaceNode实例的空间区域（也就是其中有物体的空间区域）进行检测。另一方面，由于在设计游戏时要求一个SpaceNode的尺寸使其中可以存在的物体数目不会很多，所以可以采用“碰撞球－三角形检测”的两步检测方法进行检测。
3.相关的范围检测算法
似乎只是简单的沿着三个链表进行搜索的过程。
4.相关的RayTrace算法
似乎类似于碰撞检测算法。
|
|
发表于 2005-5-5 10:05:00
楼主