场景加速结构
在游戏引擎中，如何高效的管理游戏场景物体是一个非常重要的话题，在执行碰撞检测或者光线追踪求交时，如果我们每帧都要进行暴力检测的话，毫无疑问或造成非常多的计算资源浪费。于是为了解决这些问题，我们在构建世界的时候，往往会利用一些场景加速结构(Acceleration Structure)来管理。
常规的场景加速机构的主要思路是，我们利用一些空间信息或者物体位置来对物体进行树形划分，每个子节点管理一批物体，这样的话在查询的时候，我们就不用遍历整个场景，而是可以做到亚线性(Sublinear)的速度。
总的来看，场景划分的方法可以分为两大类，一种是基于空间的算法(Spatial Partition)，一种是基于物体的划分(Object Partition)。
Spatial Partition
- Oct-Tree: 通常成为八叉树，和二叉树其实本质上并不区别，每次将空间划分为8个区域，并且在有物体的地方继续进行递归。
- KD-Tree: KDTree和八叉树的区别是在于KDTree交替选择空间的三个轴进行切分，然后分成两块，而不是像八叉树沿着三个轴划分为8份。
- BSP-Tree: 和KD-Tree有点像，区别在于并不会交替的选择轴，而是真的随机将空间的划分为正半空间以及负半空间，这种方法很容易将空间划分出斜的空间，这种空间不太方便计算交点，所以目前用的很少。
在虚幻引擎中，我们可以Engine\Source\Runtime\Engine\Public\GenericOctree.h找到对应的八叉树实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
template<typename ElementType,typename OctreeSemantics>
class TOctree
{
public:
typedef TArray<ElementType, typename OctreeSemantics::ElementAllocator> ElementArrayType;
typedef typename ElementArrayType::TConstIterator ElementConstIt;
class FNode
{
public:
friend class TOctree;
explicit FNode(const FNode* InParent);
~FNode();
private:
mutable ElementArrayType Elements;
const FNode* Parent;
mutable FNode* Children[8];
mutable uint32 InclusiveNumElements : 31;
mutable uint32 bIsLeaf : 1;
};
template<typename StackAllocator = DefaultStackAllocator>
class TConstIterator
{
public:
void PushChild(FOctreeChildNodeRef ChildRef);
void Advance();
bool HasPendingNodes() const;
FNodeReference CurrentNode;
TArray<FNodeReference,StackAllocator> NodeStack;
};
void AddElement(typename TTypeTraits<ElementType>::ConstInitType Element);
void RemoveElement(FOctreeElementId ElementId);
TOctree(const FVector& InOrigin,float InExtent);
private:
FNode RootNode;
FOctreeNodeContext RootNodeContext;
float MinLeafExtent;
void AddElementToNode(
typename TTypeTraits<ElementType>::ConstInitType Element,
const FNode& InNode,
const FOctreeNodeContext& InContext
);
};
|
Object Partition
在基于物体的划分中，其实主要就是讨论BVH(Bounding Volume Hierarchy), 我的RayTracer中也实现了这个算法，确实是一个简单优秀的加速结构。
这种划分正如名字所说，将物体作为划分依据，这种划分算法的执行流程是按照物体的某个轴进行排序，然后将一定数量的物体归为一个组，然后在不断的递归下去，我的实现是如下所示。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| std::shared_ptr<BvhNode> Scene::BuildBVH(int start, int end) {
int axis = Random::UInt() % 3;
auto compareFunc = (axis == 0) ? BoxCompareX : (axis == 1) ? BoxCompareY : BoxCompareZ;
std::unique_ptr<BvhNode> root;
int len = end - start;
if(len == 1) {
root->left = m_objects[start];
root->right = m_objects[end];
}
else if(len == 2) {
if(compareFunc(m_objects[start], m_objects[start + 1])) {
root->left = m_objects[start];
root->right = m_objects[start + 1];
} else {
root->left = m_objects[start + 1];
root->right = m_objects[start];
}
}
else {
std::sort(m_objects.begin() + start, m_objects.begin() + end, compareFunc);
int mid = start + len / 2;
root->left = BuildBVH(start, mid);
root->right = BuildBVH(mid, end);
}
AABB leftBox, rightBox;
auto left = root->left, right = root->right;
if(!left->BoundingBox(0, 0, leftBox) || !right->BoundingBox(0, 0, rightBox)) {
std::cerr << "Bounding box failed!\n";
}
root->box = SurroundingBox(leftBox, rightBox);
return root;
}
|
这种方法的好处是物体的划分的非常紧凑，相比于空间划分的方法更利于物体与光线的求交, 而且我个人是觉得也更好实现。
引用
GAMES101-现代计算机图形学入门
