地形系统思路来自 ProjectS中的GPU Driven

架构

首先明确ProjectS的世界大小,目前暂定整个世界面积为 20.48km * 20.48km ,实际上可以再大很多,但考虑到资源量级以及对于世界内容的填充需要颇费心思,暂定这么大了

既然地形分了LOD,那么纹理自然也要根据LOD进行区分

  • LOD0的Node对应的纹理信息(高度纹理,Material Id纹理等)分辨率为128*128,覆盖区域为64m*64m即一个纹素对应0.5m,已经很可以了,再高点画质就要比原神好了
  • LOD1的Node纹理分辨率为128*128,但覆盖区域为128m*128m
  • LOD2的Node纹理分辨率为128*128,覆盖区域为256m*256m
  • LOD3的Node纹理分辨率为128*128,覆盖区域为512m*512m
  • LOD4的Node纹理分辨率为128*128,覆盖区域为1024m*1024m
  • LOD5的Node纹理分辨率为128*128,覆盖区域为2048m*2048m

这也就意味着我们需要对整个世界做六种不同覆盖区域的纹理,可以理解为Mipmap,不同的LOD Node采样不同覆盖区域面积的纹理,如图所示

不同颜色代表不同LOD等级,但每个LOD都是使用的128*128分辨率的高度图纹理进行渲染的,这里以原分辨率8192纹理为例,需要额外再导出4096,2048,1024,512,256的贴图,才能满足所有LOD层级的渲染需求。

需要注意的是,由于我们所有纹理都是分块流式加载的,每张纹理仅仅是128*128的,没有全分辨率的纹理,所以类似SampleLevel这种指定mip等级的API是用不了的,只能自己将相应的LOD对应纹理加载进来,由于纹理数量较多,且分辨率相同,使用Unity的TextureArray作为管理器是一个很好的选择,可以有效减少bind消耗

明确了基础的世界组成架构,接下来需要确定整个地形渲染系统的运作流程

CPU

四叉树构造

值得注意的是,如果没有流式加载的需求,其实是不需要标准化的四叉树的,只需要将所有需要细分的节点进行4次细分即可,完全可以将四叉树的构建和剔除放在GPU加速

而如果需要流式加载,则需要构建标准四叉树,并借助四叉树的快速区域查找特性来进行卸载和加载节点,因为涉及相对复杂的数据结构和数据异步交互,放在CPU中进行

四叉树基础知识

由于我们无法保证四叉树一定是一颗完全树,所以没法用数组的形式来保存节点信息,另外我们需要动态更新四叉树,所以采用指针引用的形式进行节点存储

四叉树节点中包含的数据就是我们地形渲染中的Node:

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
57
58
59
60
61
62
63
public class QuadTreeNode : IReference
{
/// <summary>
/// 四叉树中的深度
/// </summary>
public int depth;
/// <summary>
/// 在兄弟节点中的排序,顺序为左下,右下,左上,右上,分别对应0,1,2,3
/// </summary>
public uint index;
/// <summary>
/// 节点的正方形信息,坐标系为世界坐标
/// 且左下角为坐标原点,x往右递增,y往上递增
/// </summary>
public Rect rectInfo = Rect.zero;
/// <summary>
/// 子节点,限定数量为4
/// </summary>
public List<QuadTreeNode> children = new List<QuadTreeNode>(4);
public QuadTreeNode parent;
public bool isLeafNode => children.Count == 0;
/// <summary>
/// 包含的对象,这里只用id索引,便于进行碰撞检测,这里的对象一定是自己完全包含的,不存在压线的情况
/// </summary>
public HashSet<QuadTreeNodeContent> containObject = new HashSet<QuadTreeNodeContent>();
public void Clear()
{
foreach (var child in children)
{
ReferencePool.Release(child);
}
depth = 0;
index = 0;
rectInfo = Rect.zero;
parent = null;
containObject.Clear();
// 不在此处release,因为数据可能会被其余节点引用
/*foreach (var content in containObject)
{
ReferencePool.Release(content);
}*/
children.Clear();
}
}

public class QuadTreeNodeContent : IEquatable<QuadTreeNodeContent>, IReference
{
public int instanceId;
public Rect rectInfo = Rect.zero;
public QuadTreeNode belongToQuadTreeNode;
public QuadTreeNodeContent Init(int instanceId, Rect rect)
{
this.instanceId = instanceId;
this.rectInfo = rect;
return this;
}
public void Clear()
{
this.instanceId = 0;
this.rectInfo = Rect.zero;
this.belongToQuadTreeNode = null;
}
}

可能有些抽象,画张图解释一下

然后就是老生常谈的四叉树构造,地形节点的填入了,由于四叉树算法网上已经有很多讲解和实现,此处不再表述,可以参考:Quadtree and Collision Detection

这里只说几个注意点:

  • 每个节点都可以存储对象,不论是否是叶子节点,可以加速查找
  • 当一个对象不被将要被细分的四叉树节点中的四个象限中的任意一个完全包含时,将不会进行细分
  • 当一个对象不被四叉树节点完全包含的时候,需要分配到父节点
  • 当一个对象不被四叉树节点的四个象限中的任意一个完全包含时,需要分配到四叉树节点本身
  • 四叉树需要有动态更新的能力

动态演示如下:

the-last

超大世界下的区域性四叉树

因为我们的世界是20.48km * 20.48km,且Sector为64*64m,那么如果在整个世界范围内构建四叉树的话,至少需要将四叉树的深度拉伸到9以上(即2^n >= (20480/64 = 320),n > 8 => n = 9)才能保证获取到每个Sector的LOD级数,由于四叉树深度过深,效率已经比较糟糕了

所以我们需要构建一个区域性的四叉树,尽量把四叉树深度保持在6以内,范围就是 (2^6 = 64) * 64 = 4096 ,即我们的四叉树覆盖范围为4096m*4096m,区域外的部分一律采用LOD5进行渲染

这个区域性四叉树优点如下:

  • 较小的深度,保证查询效率
  • 通过对比当前帧与前一帧的四叉树覆盖区域快速获得需要流式加载,卸载的节点
  • LOD0大小完全匹配Sector,便于后续数据准备收集工作
  • 为后续的RVT提供数据支持
  • 兼容任意大小的世界地形,同时可通过坐标偏移避免大世界浮点精度问题

当然对于这个区域性的四叉树,我们需要保证其中心落点一直位于64的整数倍上,不然每个Sector就对不准我们离线切分的纹理大小了

示例如下:

灰色为整个世界,线框部分为四叉树覆盖区域,面积为4096x4096m,其中最小的LOD(亮青色网格)为64x64m

区域性四叉树移动触发流式

当玩家进行移动时,四叉树会跟随更新,如果移动连续(即不进行传送操作),则可以求出这次移动需要加载和卸载的节点

示例如下:棕色部分为待卸载部分,绿色为复用部分,蓝色为待加载部分

具体步骤为:

  • 设当前四叉树为X
  • 当玩家移动距离相比上一次记录累计超过LOD0(64m)阈值时触发流式
  • 计算出需要加载的范围A,卸载的范围B,以及重合的范围C
  • 由于我们LOD层级较多,基本上每次移动都会触发大部分节点的重建,所以直接重建整颗四叉树得到Y
  • 将需要加载的范围A和Y做相交测试,得到覆盖的节点,以及对应的待加载资源列表a
  • 将需要卸载的范围B和Y做相交测试,得到覆盖的节点,以及对应的待卸载资源列表b
  • 将重合的范围C和X,Y做相交测试,得到相对的覆盖节点,对节点进行一一对比,如果节点的位置和四叉树层级(LOD等级)均相同,则认为此节点无需加载资源,否则此节点需要卸载引用资源,并重新加载新的对应资源,得到待加载的资源列表c,以及待卸载的资源d
  • 对a,c资源列表进行加载,对b,d资源列表进行卸载
  • PS:当然如果项目的资源管理模块做的比较吊的话,可以忽略上述复杂的加载卸载步骤,只需要无脑卸载上一帧残余资源,加载这一帧所有资源即可,由资源管理模块进行处理

区域性四叉树跟随移动表现如下:

the-last

当然,仅仅是这样是有问题的,因为我们是依据LOD0的阈值来重建整颗四叉树,这样会导致其余LOD等级的对应资源无法被正确加载,例如LOD1覆盖区域为128x128m,在离线切分纹理的时候每个tile是固定的,即x轴间隔0,128,256三张纹理,那么x为64的时候,是没有对应纹理的,只能继续复用x为0时的纹理。

综上,我们只有在四叉树中最高等级的LOD发生变动的时候才会移动整颗四叉树,否则以各个LOD等级贴图切分规格进行流式加载和卸载,示例如下:

the-last

世界原点与Node布局

为了最大限度利用浮点精度范围,我们把世界中心点设置在世界坐标原点处

为了和四叉树统一排列算法,世界左下角为tile0,从左到右,从下到上进行排列,就像这样:

Node内容

对于地形高度渲染,每个Node至少需要有以下数据

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
public class TerrianNode : IReference
{
/// <summary>
/// 引用的四叉树节点Id,四叉树节点自身拥有世界空间坐标,大小等数据
/// </summary>
public long instanceId;
/// <summary>
/// LOD等级
/// </summary>
public int lodLevel;

/// <summary>
/// 对应lod下的x,y索引
/// </summary>
public Vector2Int indexer;
/// <summary>
/// 引用的textureArray中的纹理索引
/// </summary>
public int refHeightFieldTextureArrayIndex;
public void Clear()
{
instanceId = 0;
indexer = Vector2Int.zero;
refHeightFieldTextureArrayIndex = 0;
}
}

资源准备

Patch

首先是最基础的Patch,直接在houdini拉一个8x8m,分辨率为16的grid导出fbx即可,记得在fbx的rop节点恢复原生比例(勾选Convert Units),不然导入到unity还得放大100倍

image-20230909191839630

四叉树剔除

借助四叉树的结构特性,可以实现较为高效的剔除

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
/// <summary>
/// 遍历整颗四叉树
/// </summary>
/// <param name="trigger">判定某个rect是否在检测范围内,用于减少遍历次数</param>
/// <param name="traverseCallback"></param>
public void TraverseTree(Func<Rect, bool> trigger, Action<QuadTreeNode> traverseCallback)
{
TraverseTreeInternal(trigger, root, traverseCallback);
}

private void TraverseTreeInternal(Func<Rect, bool> trigger, QuadTreeNode quadTreeNode,
Action<QuadTreeNode> traverseCallback)
{
// 如果节点判断失败,则直接终止
if (trigger != null && !trigger.Invoke(quadTreeNode.rectInfo))
{
return;
}

traverseCallback?.Invoke(quadTreeNode);
foreach (var child in quadTreeNode.children)
{
TraverseTreeInternal(trigger, child, traverseCallback);
}
}

碰撞检测基于相机的视锥体进行,剔除代码和debug代码如下:

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
Camera cam = Camera.main;
GeometryUtility.CalculateFrustumPlanes(cam, cameraFrustumPlanes); //Ordering: [0] = Left, [1] = Right, [2] = Down, [3] = Up, [4] = Near, [5] = Far

PoolableList<QuadTreeNode> result = ReferencePool.Acquire<PoolableList<QuadTreeNode>>();
{
m_quadTree.TraverseTree((x) =>
{
Bounds cellBound = new Bounds(new Vector3(x.center.x, 0, x.center.y),
new Vector3(x.size.x, 0, x.size.y));
return GeometryUtility.TestPlanesAABB(cameraFrustumPlanes, cellBound);
}, (x) => { result.value.Add(x); });
}

foreach (var quadTreeNode in result.value)
{
// 绘制所有通过测试的节点
foreach (var content in quadTreeNode.containObject)
{
Popcron.Gizmos.Cube(new Vector3(content.rectInfo.center.x, 0, content.rectInfo.center.y),
Quaternion.identity, new Vector3(content.rectInfo.size.x, 100, content.rectInfo.size.y),
Color.green);
}
}

ReferencePool.Release(result);

效果如下:

the-last

TODO

流式传输

TODO

GPU

参考

TextureArray用法

Quadtree and Collision Detection