UE松散八叉树分析

本文最后更新于：2025年11月6日 晚上

前言

朴素的八叉树

1
2
3
4
5
6
7
8
9
10
11
class FOTreeNode{
    public:
    	TUniquePtr<FOTreeNode> Childs[8];
    	TUniquePtr<FOTreeNode> Parent;
    	
    	FVector Origin = FVector:ZeroVector;
    	FVector Extent = FVector:ZeroVector;
    
    	Tarray<AActor*> Actors;
    	bool bLeaf = true;
};

Origin（原点）

  • 表示节点的中心点坐标

  • 是该节点代表的3D空间盒子的中心位置

  • 类型：FVector（X, Y, Z 坐标）

Extent（范围）

  • 表示从中心点到边界的半径距离

  • 定义了该节点空间的大小

  • 类型：FVector（X轴半径、Y轴半径、Z轴半径）

如何优化？

  • 8个子节点都用TUniqePtr，有点内存浪费
  • 八个子节点的Parent都相同，没必要每个子节点都存一份Parent
  • 每个节点不需要自己存Origin和Extent，只要知道父节点的数据，以及自己多少层即可
  • bLeaf也不用单独存

UE八叉树节点定义

1
2
3
4
5
6
7
8
9
10
11
12
13
struct FNode
{
	FNodeIndex ChildNodes = INDEX_NONE;
	uint32 InclusiveNumElements = 0;

	bool IsLeaf() const
	{
		return ChildNodes == INDEX_NONE;
	}
};

TArray<FNode> TreeNodes;
TArray<FNodeIndex> ParentLinks;

UE八叉树的一个约定是，一个节点包含的所有元素，其Bounds也在这个节点边界内。那么即使待插入元素的Center在某个子树中，但Bounds超出了子树边界，也不能强行把他加入到子树中去。UE做法是直接把元素插入到父节点的TreeElements数组即可。

比如下面那个跨越边界的节点，会被直接插入到父节点的元素数组中

img

但是这么操作，Bounds稍微超过子节点，元素就会存到父节点，父节点存了太多元素怎么办，这又会影响后续查询效率。UE做法是把子树边界适当放宽 1/16 的大小，缓解一下，目的是让一些处于子树边界上的元素，如果Bounds不大，就还是存在子树里，这个细节看下面的node有分析。

UE4源码分析

主要看了一下这个文件：GenericOctree.h

碰撞盒

碰撞盒检测数学原理

1
2
// 两个盒子相交，当且仅当在所有轴上都相交
|CenterA - CenterB| <= ExtentA + ExtentB  (对于 X, Y, Z 轴)

SIMD

有啥好处？

SIMD = Single Instruction, Multiple Data（单指令多数据）

传统 CPU 指令：

1
2
一次只能处理一个数据
ADD 寄存器A, 寄存器B  → 计算 A + B

SIMD

1
2
一次处理多个数据（通常4个或8个）
VADD 向量寄存器A, 向量寄存器B  → 同时计算 [A0+B0, A1+B1, A2+B2, A3+B3]

看源码

1
2
3
4
5
6
7
8
9
10
11
12
friend FORCEINLINE bool Intersect(const FBoxCenterAndExtent& A, const FBoxCenterAndExtent& B)
{
    // CenterDifference is the vector between the centers of the bounding boxes.
    const VectorRegister CenterDifference = VectorAbs(VectorSubtract(VectorLoadAligned(&A.Center), VectorLoadAligned(&B.Center)));

    // CompositeExtent is the extent of the bounding box which is the convolution of A with B.
    const VectorRegister CompositeExtent = VectorAdd(VectorLoadAligned(&A.Extent), VectorLoadAligned(&B.Extent));

    // For each axis, the boxes intersect on that axis if the projected distance between their centers is less than the sum of their
    // extents.  If the boxes don't intersect on any of the axes, they don't intersect.
    return VectorAnyGreaterThan(CenterDifference, CompositeExtent) == false;
}

假如是传统写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool Intersect_Slow(const FBoxCenterAndExtent& A, const FBoxCenterAndExtent& B)
{
    // 需要9次浮点运算
    float DiffX = abs(A.Center.X - B.Center.X);  // 2次运算
    float DiffY = abs(A.Center.Y - B.Center.Y);  // 2次运算
    float DiffZ = abs(A.Center.Z - B.Center.Z);  // 2次运算
    
    float SumExtentX = A.Extent.X + B.Extent.X;  // 1次运算
    float SumExtentY = A.Extent.Y + B.Extent.Y;  // 1次运算
    float SumExtentZ = A.Extent.Z + B.Extent.Z;  // 1次运算
    
    // 3次比较
    return (DiffX <= SumExtentX) && (DiffY <= SumExtentY) && (DiffZ <= SumExtentZ);
}

如果使用FVector4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool Intersect_Fast(const FBoxCenterAndExtent& A, const FBoxCenterAndExtent& B)
{
    // 只需要3条SIMD指令！
    const VectorRegister CenterDiff = VectorAbs(VectorSubtract(
        VectorLoadAligned(&A.Center),    // 1条：加载
        VectorLoadAligned(&B.Center)));  // 2条：减法+绝对值（同时处理X,Y,Z,W）
    
    const VectorRegister CompositeExtent = VectorAdd(
        VectorLoadAligned(&A.Extent),    // 3条：加法（同时处理X,Y,Z,W）
        VectorLoadAligned(&B.Extent));
    
    // 4条：比较（同时比较X,Y,Z,W）
    return VectorAnyGreaterThan(CenterDiff, CompositeExtent) == false;
}

使用FVector4还有一个好处是内存对齐，刚好是16个字节，FVector只有12个字节

举个例子

再说两个SIMD指令

首先VectorCompareGT，可以用SIMD指令一次性比较4对浮点数，返回结果依然是一个Vector4。对于每一对浮点数，如果大于会存0xFFFFFFFF，小于存0。

然后VectorMaskBits，又可以把4个有符号数，把符号都转化为bitmask，组成一个int数。最后把这个int数当成子节点下标即可。

两个很神的结构

FOctreeChildNodeRef

看了很久终于看懂了，其实这个就是类的关键就是，用一个index来表达该选择八个节点中的哪一个，一般来说这个需要三个参数xyz，但是ue用巧妙的位运算就可以一个index来搞定

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
/** A reference to a child of an octree node. */
class FOctreeChildNodeRef
{
public:
    int8 Index;

    /** Initialization constructor. */
    FOctreeChildNodeRef(int8 InX, int8 InY, int8 InZ)
    {
        checkSlow(InX >= 0 && InX <= 1);
        checkSlow(InY >= 0 && InY <= 1);
        checkSlow(InZ >= 0 && InZ <= 1);
        Index = int8(InX << 0) | int8(InY << 1) | int8(InZ << 2);
    }

    /** Initialized the reference with a child index. */
    FOctreeChildNodeRef(int8 InIndex = 0)
        : Index(InIndex)
    {
        checkSlow(Index < 8);
    }

    /** Advances the reference to the next child node.  If this was the last node remain, Index will be 8 which represents null. */
    FORCEINLINE void Advance()
    {
        ++Index;
    }

    /** @return true if the reference isn't set. */
    FORCEINLINE bool IsNULL() const
    {
        return Index >= 8;
    }

    FORCEINLINE void SetNULL()
    {
        Index = 8;
    }

    FORCEINLINE int32 X() const
    {
        return (Index >> 0) & 1;
    }

    FORCEINLINE int32 Y() const
    {
        return (Index >> 1) & 1;
    }

    FORCEINLINE int32 Z() const
    {
        return (Index >> 2) & 1;
    }
};

为啥要这样干呢？因为有个关键函数GetContainingChild，也就是判断一个元素是否完全被某一个子节点包含，如果是返回那个子节点索引，否则返回 NULL。

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
FORCEINLINE FOctreeChildNodeRef FOctreeNodeContext::GetContainingChild(const FBoxCenterAndExtent& QueryBounds) const
{
	FOctreeChildNodeRef Result;

	// Load the query bounding box values as VectorRegisters.
	const VectorRegister QueryBoundsCenter = VectorLoadAligned(&QueryBounds.Center);
	const VectorRegister QueryBoundsExtent = VectorLoadAligned(&QueryBounds.Extent);

	// Compute the bounds of the node's children.
	const VectorRegister BoundsCenter = VectorLoadAligned(&Bounds.Center);
	const VectorRegister ChildCenterOffsetVector = VectorLoadFloat1(&ChildCenterOffset);
	const VectorRegister NegativeCenterDifference = VectorSubtract(QueryBoundsCenter,VectorSubtract(BoundsCenter,ChildCenterOffsetVector));
	const VectorRegister PositiveCenterDifference = VectorSubtract(VectorAdd(BoundsCenter,ChildCenterOffsetVector),QueryBoundsCenter);

	// If the query bounds isn't entirely inside the bounding box of the child it's closest to, it's not contained by any of the child nodes.
	const VectorRegister MinDifference = VectorMin(PositiveCenterDifference,NegativeCenterDifference);
	if(VectorAnyGreaterThan(VectorAdd(QueryBoundsExtent,MinDifference),VectorLoadFloat1(&ChildExtent)))
	{
		Result.SetNULL();
	}
	else
	{
		// Return the child node that the query is closest to as the containing child.
		Result.Index = VectorMaskBits(VectorCompareGT(QueryBoundsCenter, BoundsCenter)) & 0x7;
	}

	return Result;
}

这里面用了很多SIMD操作，全都是向量操作

这个函数是在插入节点的时候用的AddElementInternal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
else
{
    const FOctreeChildNodeRef ChildRef = NodeContext.GetContainingChild(ElementBounds);
    if (ChildRef.IsNULL())
    {
        int ElementIndex = TreeElements[CurrentNodeIndex].Emplace(Element);
        SetElementId(Element, FOctreeElementId2(CurrentNodeIndex, ElementIndex));
        return;
    }
    else
    {
        FNodeIndex ChildNodeIndex           = TreeNodes[CurrentNodeIndex].ChildNodes + ChildRef.Index;
        FOctreeNodeContext ChildNodeContext = NodeContext.GetChildContext(ChildRef);
        AddElementInternal(ChildNodeIndex, ChildNodeContext, ElementBounds, Element, TempElementStorage);
        return;
    }
}

FOctreeChildNodeSubset

node

ue5的子node不存储控件信息，而是在遍历的时候动态生成，因为子节点的空间信息完全由父节点决定

1
2
3
4
5
6
7
8
9
/** Child node initialization constructor. */
inline FOctreeNodeContext GetChildContext(FOctreeChildNodeRef ChildRef) const
{
    FBoxCenterAndExtent LocalBounds;
    VectorRegister ZeroW = MakeVectorRegister(1.0f, 1.0f, 1.0f, 0.0f);
    VectorStoreAligned(VectorMultiply(ZeroW, VectorAdd(VectorLoadAligned(&Bounds.Center), GetChildOffsetVec(ChildRef.Index))), &LocalBounds.Center);
    VectorStoreAligned(VectorMultiply(ZeroW, VectorSetFloat1(ChildExtent)), &LocalBounds.Extent);
    return FOctreeNodeContext(LocalBounds);
}

这段等价于

1
2
3
4
5
6
7
8
9
10
11
12
13
// 第 302-308 行
FOctreeNodeContext GetChildContext(FOctreeChildNodeRef ChildRef) const
{
    FBoxCenterAndExtent LocalBounds;
    
    // 子节点中心 = 父节点中心 + 偏移向量
    LocalBounds.Center = Bounds.Center + GetChildOffsetVec(ChildRef.Index);
    
    // 子节点范围 = ChildExtent（父节点已经预计算好）
    LocalBounds.Extent = ChildExtent;
    
    return FOctreeNodeContext(LocalBounds);
}

而且ue的八叉树的节点不是紧密排列的，节点之间有碰撞，可以看这个初始化方法

1
2
3
4
5
6
7
8
9
10
FOctreeNodeContext(const FBoxCenterAndExtent& InBounds, uint32 InInCullBits, uint32 InOutCullBits)
    : Bounds(InBounds), InCullBits(InInCullBits), OutCullBits(InOutCullBits)
{
    // A child node's tight extents are half its parent's extents, and its loose extents are expanded by 1/LoosenessDenominator.
    const float TightChildExtent = Bounds.Extent.X * 0.5f;
    const float LooseChildExtent = TightChildExtent * (1.0f + 1.0f / (float)LoosenessDenominator);

    ChildExtent                  = LooseChildExtent;
    ChildCenterOffset            = Bounds.Extent.X - LooseChildExtent;
}

这种有重叠的好处跨越边界的时候不会频繁改动，在重叠区比较稳定，重叠比例是1/16，应该是epic的黑科技，这样做的目的

参考笔记

UE5的八叉树实现 - 南京周润发的文章 - 知乎

UE5的八叉树实现 - 南京周润发的文章 - 知乎

游戏杂货铺
UE松散八叉树分析
https://rorschachandbat.github.io/游戏杂货铺/UE松散八叉树分析/
作者
R
发布于
2025年11月5日
许可协议