hga039皇冠安卓版 hga039皇冠安卓版 hga039皇冠安卓版

空间数据结构(四叉树/八叉树/BVH树/BSP树/kd树)

资源:

1 四叉树/八叉树(Quadtree/Octree)

在这里插入图片描述

四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间划分为四个相等的子空间球体结构图,如此递归,直到树的层次达到一定深度或满足一定要求时停止分裂。

在这里插入图片描述

// 示例:一个四叉树节点的简单结构
struct QuadtreeNode {
  Data data;
  QuadtreeNode* children[2][2];
  int divide;  //表示这个区域的划分长度
};

// 示例:找到x,y位置对应的四叉树节点
QuadTreeNode* findNode(int x,int y,QuadtreeNode * root){
  if(!root)return;
  QuadtreeNode* node = root;
  
  for(int i = 0; i < N && n; ++i){
  	// 通过diliver来将x,y归纳为0或1的值,从而索引到对应的子节点。
  	int divide = node->divide;
    int divideX = x / divide;
    int divideY = y / divide;
    
    QuadtreeNode* temp = node->children[divideX][divideY];
    if(!temp){break;}
  	node = temp;
    
  	// 如果归纳为1的值,还需要减去该划分长度,以便进一步划分
    x -= (divideX == 1 ? divide : 0);
  	y -= (divideY == 1 ? divide : 0);
  }
  
  return node;
}

四叉树结构在空间数据对象均匀分布时,具有较高的空间数据插入和查询效率(复杂度O(logN))。

在这里插入图片描述

八叉树的结构与四叉树基本相似,都是8个节点(三维2元数组),其构造方法和查询方法也类似,就不多描述了。

1.1 松散四叉树/八叉树:减少边界问题

四叉树/八叉树的一个问题是对象有可能跨越边界来回移动,导致对象总是切换节点,从而不得不更新四叉树/八叉树。松散四叉树/八叉树只是解决这个边界问题的一种方法:首先,它定义了一个具有内边界和外边界的节点。那么如何判断一个对象现在在哪个节点呢?

如果对象还没有加入到四叉树/八叉树中,则检测当前哪个节点位于入口边界内;如果对象之前已经存在于某个节点中,首先检测它现在是否超出了该节点的出口边界,如果超过则检查哪个节点在该节点的入口边界内。

在非松散四叉树/八叉树中,入口边界与出口边界相同。loose quadtree/octree的松散是指出口边界比入口边界略宽(每个节点的出口边界也会部分重叠,松散更符合这个描述),使得节点不易于跨越出口边界,减少对象切换节点的次数。

在这里插入图片描述

后续的问题是如何定义出口边界的长度。因为太短会退化成普通的四叉树/八叉树,太长可能会导致节点存储冗余对象。在一篇关于松散四叉树/八叉树的论文中,实验表明,出口边界的长度是入口边界的两倍,性能良好。

1.2 四叉树/八叉树的应用

与网格相比,四叉树/八叉树主要是层数更多。他们可以将区域划分成更大的区域,然后按区域进行各种检测算法的剪枝/过滤。下面介绍几个应用(实际应用很广):

1.3 参考文献

【1】《游戏编程宝典2》Mark A. Deloura [2003-12]

【2】松散八叉树| 云端草原

[3] 一篇论文:Loose octree: a data structure for simulation of polydisperse particle packings

2 基于树的包围体层次结构

分层边界框树(BVH 树)是一种用于存储边界框形状的多叉树。它的根节点代表一个最大的边界框,它的多个子节点代表多个子边界框。另外,为了统一分级bounding box树的shape,只能存储相同的bounding box shape(电脑的bounding box shape有sphere/AABB/OBB/k-DOP,不清楚的话这些形状术语,你可以自己搜索)。常用的层次边界框树有AABB层次边界框树和球体树。

2.1 AABB包围盒树

下图显示了分层的 AABB 边界框树。用AABB形状粗略包围不同的形状作为一个AABB形状(为了统一形状),然后构建层次化的AABB边界框树。

在这里插入图片描述

在物理引擎中,由于物理模拟,大部分形状都是动态更新的,例如位移/旋转都会改变形状。于是又出现了一种支持动态更新的hierarchical bounding box tree,称为dynamic hierarchical bounding box tree。其算法核心大致是:形状的位移/旋转/拉伸更新相应的叶子节点,然后逐层更新上层节点,使其包围体包围子节点。

2.2 球体包围盒树

球体是最容易计算的bounding box类型,球体树的构建速度可以很快,所以球体树可以作为一种粗糙松散但快速的空间划分结构。快速构建松散球体树的步骤(以三角形物体为例):

计算包围所有三角形边顶点的最小球体边界框,作为根节点;以球心为坐标系原点,将坐标系的X轴分成X轴左右两边的三角形,分别放入左子节点,右子节点中子节点;重复步骤1和2,最后得到一棵球体树。

在step 2中,也可以按照X轴、Y轴、Z轴的顺序依次划分,即X轴用于第一步2划分,Y轴用于第二步2师...

在这里插入图片描述

在这里插入图片描述

这样生成的球体树比较粗糙,但是平衡效果还不错,最重要的是它的构建时间复杂度仅为O(NlogN)。

2.3 Hierarchical Bounding Box Tree的应用 2.4 参考

【1】游戏物理:Broadphase——动态AABB树| Ming-Lun “Allen” Chou | 周明伦

【2】《游戏编程宝典5》Kim.Pallister [2007-9]

【3】动态虚拟环境的实时碰撞检测

3 BSP树(Binary Space Partitioning Tree)

BSP树是二叉树,中文译为二维空间划分树。算是游戏界的老英雄了。1993年首次用于商业游戏《DOOM》,但随着渲染硬件的进步,基于BSP树的Rendering正在慢慢被淘汰。但即使在今天,BSP 仍然是其他分支(引擎编辑器)中不可或缺的重要数据结构。

BSP树的每个节点代表3D空间中的一个平面,它所代表的平面将当前空间分为前向和后向两个子空间,分别对应左儿子和右儿子。

在二维空间中,BSP树的每个节点代表一条边,二维空间也可以分为两部分。

在这里插入图片描述

// BSP tree节点结构示例
class BSPTreeNode {
	Plane plane;				  // 平面
	BSPTreeNode* front;           // 前向的节点
	BSPTreeNode* back;            // 后向的节点
	//Data data;                  // 数据
};

3.1 BSP树的构建

为了在3D空间构造一个更平衡的BSP树,需要在每次划分节点时,使左子树的节点数和右子树的节点数尽可能相似:

在一组平面形状中,使用其中一个平面构造BSP树节点时,其前面的平面形状数量与后面的平面形状数量之差必须小于一定的阈值;如果超过阈值,则尝试使用下一个形状来构造。一个麻烦的问题是当两个平面形状相交时,即平面形状可以在前面也可以在后面。这时候就需要把形状切割成两个子形状,这样可以在前面加一个,在后面加一个,避免冲突。构造一个节点后,去掉对应的平面,将节点前面的平面形状和节点后面的平面形状作为两组子平面形状。对这两个子集合重复步骤1和2,继续构造两个子节点,并将它们作为该节点的左右儿子。最后用所有的平面形状构造节点,形成BSP树。

由于需要进行N次划分,每次划分后,必须在子集中逐一选择合适的平面(需要logN次遍历),为了评估是否合适,需要将前后位置与所有其他平面进行比较shapes in the subset (requires logN comparisons) ),所以可以知道BSP树构建的平均时间复杂度是O(Nlog²N)

平面算法前后的判断点:平面的法向量为(A,B,C),则平面方程为:Ax+By+Cz+D=0

将点(x0,y0,z0)代入方程得到距离=Ax0+By0+Cz0+D

如果 distance 如果 distance=0,则在平面内;

如果 distance>0,它在飞机的前面。

3.2 球体树法加速BSP树的构建

由于BSP树构建的平均时间复杂度为O(Nlog²N),因此往往更适合静态对象的离线构建(预处理)。然而,每次对关卡进行细微的改动,设计师都可能需要等待几分钟。这个时间虽然不影响程序的效率,但是却耽误了开发效率。更好的方法是快速构建一个粗糙的球体树,利用这种结构可以更快地构建BSP树。

我们可以先为所有的平面形状构建一个球体树,同时每个节点需要额外记录它拥有的形状数量(它和它所有的子边界框代表的形状)。整个过程的时间复杂度为O(NlogN)。(如何快速构建球体树在BVH的球体树部分已经有讲解)那么我们按照正常构建BSP树的方法,每次划分选择一个平面形状,但是判断个数的时候不要判断每个形状前面的shapes和后面的shapes个数 平面前后,判断球体的bounding box在平面前后。只要一个球体边界框完全在平面的前面或后面,那么它所代表的形状和它的所有子边界框都必须在平面的前面或后面;如果球体包围盒与平面相交,则需要将其分解为其所有子球体包围盒,然后将这些球体包围盒与前后平面进行比较。由于sphere bounding box节点记录的是shape的个数,所以很容易判断sphere与平面的关系,获取选中某个平面前后的shape个数。最后,我们构建了一个 BSP 树。

虽然这种方法生成的粗略的 BSP 树可能不是最平衡的,但它只需要 O(nlogn) 的时间复杂度。每次对关卡进行更改,可能只需要几秒钟,这对设计者是有利的。这是一个理想的等待时间。

3.3 BSP树的应用

大型室内场景游戏引擎基本上都离不开传送门系统:

门户系统可以在运行时进行额外的视野剔除,过滤掉很多被遮挡的物体渲染,有效优化室内渲染。Portal系统还可以离线构建PVS(Potentially Visible Set),计算出某个划分的区域中还有哪些区域是潜在可见的,并将这些数据存储为一个Potentially Visible Set;运行时根据集合Area实时加载潜在的可见集合。

但是对于关卡编辑来说,手动为每个房间/大厅/走廊/门放置每个传送门无疑是一个巨大的工作量。于是就有了一种方法,就是利用BSP树自动生成一个入口。一般的做法是:

首先,将需要渲染的墙壁/门/柱子等较大的室内物体所代表的边作为需要处理的平面,然后根据这些平面构建BSP树。与BSP树节点相连的左节点被视为儿子,右节点被视为邻居。与BSP树节点相连的左节点被视为儿子,右节点被视为邻居。所有相连的父节点和子节点所代表的平面构成了一个凸多边形房间。计算每个相邻房间之间的连接点,称为入口点。

建议结合图片理解,一个例子:

在这里插入图片描述

根据定义,在 BSP 树中找到 3 个凸多边形房间。

在这里插入图片描述

在相邻房间之间创建入口点对(2 个绿点,绿线代表入口平面):

在这里插入图片描述

根据门户系统计算得到的视野(去掉了两个额外的视野):

在这里插入图片描述

传送门系统其实很复杂,但是很有价值(优化好的室内FPS游戏基本不缺)。因为适合离线构建,所以这个系统经常被编辑程序员使用。这里我们只能点击自动生成传送门的皮毛。有关更具体的详细信息,请参阅本节。

从far到eyeNode的遍历顺序:

第一次遍历,按照左中右的顺序,从根节点开始,直到eyeNode停止;

第二次遍历,右中左顺序,从根节点开始,直到eyeNode停止。

BSP树节点代表的数据应该是三角形(渲染的基本图元),因为三角形也是平面形状,所以BSP树节点代表的平面也是数据本身。

今天,对于现代渲染硬件来说,虽然BSP树的从近到远渲染(从相机位置到远)对象可以减少overdraw(即重复覆盖像素)的开销,但不实用和成本昂贵的CPU成本。换取少量的GPU优化。

3.4 参考文献

【1】BSPTreesGameEngines-1

【2】BSPTreesGameEngines-2

【3】Quake3BSPRendering

【4】Real-Time Rendering SPEEDING UP RENDERING Lecture 04 Marina Gavrilova。- ppt下载

【5】

【6】BSP技术详解2 - 梦想 - 博客园

【7】BSP技术详解3 - 梦想 - 博客园

[8] BSP技术详解(补充)-pvs算法-梦想-博客园

【9】场景管理-BSP-bitbit-博客园

【10】《游戏编程宝典5》Kim.Pallister [2007-9]

【11】《游戏编程宝典6》Michael Dickheiser [2007-11]

4 kd树(k维树)

kd树是一棵二叉树,每个节点代表一个k维坐标点:

事实上,kd树是BSP树(axis-aligned BSP tree)的一种特殊形式。

// 一种实现方式示例:二维k-d树节点
class KdTreeNode{
  Vector2 position;         // 位置
  int dimension;            // 当前所属层的维度
  KdTreeNode* children[2];  // 两个子树
  //Data data;              // 数据
};

比如一棵kd树(k=2)的结构如下:

在这里插入图片描述

按照第一层,维度为X,第二层为Y,第三层为X,所以kd树(k=2)对应代表划分的空间,应该是这样的:

在这里插入图片描述

4.1 kd tree的应用 4.2 参考

[1] kd树算法原理与实现 – Upright Blog

5 个自定义区域

自定义区域一般是一个凸多边形,然后可以通过一些编辑器手动设置其顶点的位置,最后手动划分出一个凸多边形区域。3D凸多面体一般很少用到,即使是3D世界要求划分区域属于同一个XOZ平面但高度不同,考虑到性能,使用凸多边形+高度来划分区域可能更合适。

另外,如果能用凹多边形,就不需要了。因为许多程序算法可以应用于凸多边形,它可能不起作用或需要较低效率的算法才能应用于凹多边形

为了实现自定义区域之间的无缝连接,游戏程序常常使用图(或树)结构来存储这些自定义区域,以表示它们之间的连接。

// 自定义区块示例
class Chunk{
  Data data;                      // 区域数据
  std::vector<Vector2> vertexs;   // 区域凸多边形顶点
  std::vector<Chunk*> neighbors;  // 邻近区域
};

5.1 判断目标点是否在凸多边形区域的算法

既然用到了凸多边形区域球体结构图,那我就说说如何判断目标点是否在凸多边形区域内,其实也不难:

在这里插入图片描述

在目标点p和凸多边形的每个顶点之间建立一个向量vec(如:v1-p),该向量与对应顶点的边edge(如:v2-v1)交叉相乘得到获得叉积值。如果每个叉积值的符号相同(均为正数/均为负数),则证明该点在凸多边形内部。否则证明该点已不在凸多边形内。

例如:

在这里插入图片描述

因为sign((v4−p)×(v5−v4))≠sign((v2−p)×(v3−v2)),可以看出目标点不在凸多边形内。

bool Chunk::inChunk(Vector2 p){
  int size = vertexs.size();
  for(int i = 0; i < size; ++i){
    // 假设凸多边形的边edge都是逆时针方向
    Vector2 edge = vertex[(i+1)%size]-vertex[i];
    Vector2 vec = vertex[i] - p;
    int result = cross(edge,vec);
    // 若点在凸多边形内,得到的叉积值应都是正数
    if(sign(result) == 0)return false;
  }
  return true;
}

显然,该算法的时间复杂度为O(|V|),其中V为凸多边形的顶点数。

5.2 自定义区域划分的应用

自定义区域非常灵活,通常可以应用于任何游戏,尤其是世界不规则的游戏。

在这里插入图片描述

这样就可以实现一些基本的地图加载连接,把应该在远处看到的地图块渲染到对应的Chunk中。

6结语

一般来说,游戏开发最常用的空间数据结构是quad/octree和BVH tree,而BSP tree基本上只能应用于编辑器,kd tree几乎没有应用。下表简单整理:

适用数据结构n的数量级构造所需时间是否可以动态更新占用空间

四叉树

场景管理(基于地形或无高度)、渲染

对象数量

O(n*logn)

是的

大(取决于区域大小和对象数量)

八叉树

场景管理,渲染

对象数量

O(n*logn)

是的

大(取决于区域大小和对象数量)

BVH树

任何情况(包括物理、渲染)

对象数量

O(n*logn)

是的

中(取决于对象的数量)

BSP树

编辑,复杂的室内场景

架数

O(n*log²n)

大(取决于飞机数量)

kd树

-

对象数量

O(knlogn)

中(取决于对象的数量)