GPGPU Voxel Engine (2)

恕我直言,当ky会装…的时候…emm……
拜托你们收敛一点好吗,不要再丢人了(
(萌新在瑟瑟发抖.gif)


Demo video

早ww!取得了一些比较大的进展(大概)所以我来码第二篇了ww

大概的内容如上图所示ww(?)虽然大概并看不懂23333

简单说一下的话就是一个LOD,系统会根据chunk距离玩家的远近来选择不同的清晰度进行加载,如上面红色、黄色、绿色、青色、蓝色、黑色(其实是紫色但是全被染上了波谷的黑色)所示区域。在这个基础上也加入了多线程的支持,地图的加载是在后台独立完成的(不完全是,但不会阻塞当前渲染线程),不会对体验产生较大的影响。

https://github.com/linkzeldagg/GLPlayground

那么直接进入正文吧ww一步一步的来x

关于渲染方法的选择

在上一篇中,提到了使用的渲染方法是使用批量渲染来一次渲染很多方块。也提到了可能直接生成chunk网格的效率会比较快,但是还没有进行实验。

Chunk:按区块保存着地图数据的结构。在这里,最小的(没有LOD时)chunk大小为32x32x32。

既然这是第二篇,所以…测试结果如下(320x320x32,每帧更新地图数据):

(@GTX Titan X + i7-5960X / 32GB)

所用方法平均帧率(FPS)计算所需时间(us)渲染所需时间(us)
批量渲染方块11735.618299.112
批量渲染 + 面剔除12337.025284.200
直接生成网格13887.65052.642

(时间的统计有着较大的误差)

直接生成网格的完胜www虽然在计算上,使用批量渲染的速度更快(因为只需要每个方块的位置信息,不需要计算全部的网格),但是渲染开销可谓天差地别(我之前也没想到批量渲染有这么大的性能开销),导致了生成网格的综合性能更好。同时,在一般的游戏过程中,很少出现频繁大量的进行网格的更新,更多的是渲染。毫无疑问,应该使用直接生成网格的方法。

LOD

随着可视距离的增加,需要加载的chunk数量会以平方(立方?)关系随之增加。为了应对极高的可视距离(不然的话有什么意义呢hhh(x)),有必要使用LOD来减少远景的细节,减轻一定的性能负担。(没有远景 vs 有但是清晰度有所下降的远景)

让我们先实现一个最简单的想法 —— 将8个1x1x1的方块表示成1个2x2x2的方块,以此类推。尽管这种方法存在一些问题,但这是最朴素也是最直接的方法,并且效果也不算差。

之后可能会为每一个方块加入一个AABB(Axis Aligned Bounding Box?好像是x就是一个与轴对齐(不会旋转)的方盒子)数据,来代表这个方块的范围(主要是为了LOD),比如一个32x32x32的方块可能会被渲染成只有32x16x10的大小,来增加远景的真实感。

AABB可以用2个坐标来表示(min, max),每个坐标点有xyz三个分量,每个分量的取值范围是0~32内的整数(LOD最远也只能到32x32x32)。这样的话共6个0~32范围内的整数,可以被塞到一个int类型中:每5个bit表示一个分量(0~31,1~32),6个分量共30个bit(int有32个bit)

既然方块变大了,那么chunk的大小也需要随之增加,否则DrawCall(一个chunk一个Drawcall)的数量不减,性能还会面临严重的问题。这意味着,我们需要时不时将8个chunk合并成一个大chunk,或是将1个chunk拆成8个小chunk,等等。

让我们先把这个过程,比如合并,理解成舍弃掉8个chunk的数据,并重建1个大chunk的数据,这样比较简单。

Octree

老朋友八叉树w(误

其实碰到这种问题,大概八叉树是免不了的吧23333

简单介绍一下w

octree_2x_d5ec086e-6563-4f2b-99a2-4e1762919c72



(图片来自Apple Developer)(求版权斗士放过一马

感觉八叉树还是比较容易理解的ww?

如上图所示,八叉树中一个节点对应一个立方体空间,而每个节点的八个子节点则分别对应了其中的八个小立方体。可以理解为三维的线段树(如果知道什么是线段树的话x)

在这个问题上,可以把每个节点理解成一个chunk。在使用的时候,我们把八叉树按照一定的条件更新(在离玩家近的地方节点展开的多一些,更细;在离玩家远的地方比较粗糙),那么这棵树的所有叶子结点就是所有我们需要渲染的chunk。

八叉树的另一个优点是,chunk的位置是固定的(尤其是对大的chunk来讲)。即使玩家移动,大chunk的位置也不会随之移动,进而不需要进行数据的更新。这也节省了很多的性能开销。

那么接下来的问题是,怎么快速的遍历叶子结点。在很久之前(久吗)我曾经写过那个分形树的东西(x)(大概历史消息里还有),里面就用到了遍历叶子节点的方法。也很简单,大概是维护一个穿过所有叶子结点的链表,然后需要遍历的时候遍历这个链表就可以了。如下:

TreeLinkList



(灵魂示意图x

图(a)是一个示意,橙色代表我们需要维护的链表。在最开始,整棵树只有一个根节点,链表的头指针直接指向根节点(唯一的叶子结点)。随后,每当这棵树产生变化的时候,链表也随之变化:

(b) – 叶子结点展开成一棵子树。让链表中指向该节点的元素的后继(node->prev->next)变为这棵子树中最左的节点,链表中该节点指向的元素的前驱变为子树中最右的节点。同时,子树中所有节点之间从左到右相连。

(c) – 子树坍缩为一个节点。同(b),按图示更改链表的结构即可。

注意所有操作都是递归进行的,所以就算一个节点一次性展开成了类似图(a)的结构时,链表的结构也不会被破坏。

那么,如何渲染Chunk呢?

八叉树中每个节点代表一个chunk,渲染整张地图时遍历叶子结点,渲染每个节点对应的chunk即可。节点中有一个指向chunk结构的指针,调用其渲染函数即可。

需要注意的是,每次当节点成为叶子结点时,都需要构建与其对应的chunk结构(申请内存,计算网格等),这样才能进行渲染。同理,当结点不再是叶子结点时,为了节省内存,需要销毁它对应的chunk结构。这时,它便只是一个虚构的chunk节点,只代表一块区域,并不包含真正的数据。(可以通过某些GC机制进行复用,提高效率)

最后LOD的样子如下:

LOD

多线程

由于还要不断的构建chunk,这棵树更新起来可以说是很费劲了(尽管构建chunk网格是用GPU完成的)。我们当然不希望在这棵树更新的时候,造成游戏的卡顿。为此,我们想要在一个新的线程中更新这棵树,这样它就不会阻塞住主线程的渲染工作。

另一方面,为了加快这棵树的更新效率,我们还想让这棵树在更新时(生成Chunk数据时)使用多个线程一起工作,以最大化CPU的利用率。

当然,如果移动速度不高(<5m/s)的时候,就现在这个样子也没什么大问题

那么分两部分来说w

并行生成Chunk数据

现在,生成Chunk数据的过程是放在八叉树的更新过程中的,这样(大概)很难以并行化。为此,我们要把生成Chunk数据的过程单独拿出来,组成一个workList,使用多个线程去完成。

为了保证渲染时不出错,在Chunk数据生成完之前,我们应保留更新前Chunk的数据,且不更新链表(一个不完整的Chunk没有办法渲染,比如还没有申请VBO,还在计算网格,等等),让渲染器使用更新前的链表再撑一段时间ww(?),直到我们处理完了所有数据。

我们需要保证链表时时刻刻都是可用的。

同时,由于某些原因(后面会说),我们还需要单独将销毁Chunk数据释放内存的过程也独立出来。我们把销毁某个Chunk的任务也一起放入workList。

所以,我们把这棵树的更新过程拆成三个部分 —— PreUpdate, DoWork, PostUpdate:

  • 在PreUpdate阶段中,我们创建新的节点,把所有即将成为叶子的节点加入workList,并做好标记(为了之后链表的更新)。
  • 在DoWork阶段中,使用多个线程完成workList的内容。workList中包含这次PreUpdate中所有需要构建的Chunk,以及上一次更新中需要销毁的Chunk(见下)。
  • 在PostUpdate阶段中,我们完成对链表的更新,将所有需要销毁的节点放入workList,在下一次更新时将其销毁释放资源。

上图:

TreeLinkList_MT

使用独立线程进行更新

上文提到,为了不让八叉树的更新阻塞住(影响到)主线程的渲染工作,我们想要独立出一个线程进行八叉树的更新。然而有一个很严重(坑)的问题:

独立出的线程仍然需要GPU资源来完成Chunk网格的计算。如果你使用OpenGL,你需要为独立出的线程再建立(或是使用主线程的?)glContext。同时,由于GPU一般只有一个,很有可能在GPU上你的所有操作仍然是串行的(有待考证,网上一些聚聚是这么说的)。

让两个线程使用同一个glContext…总之我放弃了这一条路,选择让DoWork阶段等待主线程帮忙执行workList中的GPU工作。在主线程完成工作前,八叉树线程(?)处于阻塞状态。

另外还有一个问题(此处准确性依旧存疑),Windows下在一个线程中申请的内存无法在另一个线程中释放。同样地(大概是因为我没有设置正确的glContext),在一个线程中申请的glBuffer(可以理解为内存空间,用来存放GPU计算、渲染所需的数据,如网格等)无法在另一个线程中释放,并且除非你主动询问否则GL不会报任何错。

这也就是为什么我们需要把销毁Chunk的过程也独立出来。因为我们使用了主线程完成了GPU工作,glBuffer是使用主线程创建的,所以这些空间的释放也得需要主线程来完成,在完成前需要等待。(这块坑了我好久…orz

所以最后DoWork阶段大概是这样的:

  1. 创建所有的Chunk结构(这里没开新线程,否则之后比较难回收)。
  2. 并行构建每个Chunk的数据,并把构建完成的Chunk放入GPUworkList(需要销毁的也一起)。
  3. 等待主线程清空GPUworkList中的内容。(到这里,构建Chunk的过程就结束了)
  4. 销毁所有需要销毁的Chunk。

而主线程这边,为了减少对渲染工作的影响,每次更新(每帧)完成的GPUwork数量有一个上限(可以根据工作效率实时调整,尽量利用目标帧数之上剩余的时间,但不应过低)。如果完成的GPUwork数量超过上限,则跳出循环进入渲染,等下一帧再继续完成。这期间,DoWork一直被阻塞。

大概这样(这图好像没啥用):

Threads

暂时设置每帧最多处理128个GPUwork。

结果

我们可以撒欢的跑啦!(

bandicam 2017-11-19 22-55-59-991_20171119230546
bandicam 2017-11-19 22-55-59-991_20171119230644

(好像有点魔性hhh

视频在顶端w

下一步?

其实我还把渲染管线改了,改成了Deferred shading并且加了个没有blur的SSAO(x

但是这些大概留到下次再说吧ww

接下来剩下的事情:

  1. 阿罗拉!
  2. 期末考试和大作业(
  3. 文件读写
  4. 渲染管线(各种特效、光影、天空等)
  5. 世界生成(终于可以做了ww)
  6. 动态VBO大小(这个有点不知道该怎么弄x)(每个chunk生成的网格需要一块buffer来存放,现在这块buffer的大小是固定的,所以存在很大的浪费。)
  7. ……(热传导?要不要试着烧壶水什么的x)撒(

以上ww~(kira


今天的数字是…900♡!

おめでとう~~~!(撒花

ありがとうwwwww

(诶嘿~

发表评论

电子邮件地址不会被公开。