Construct BVH with Unity Job System | 用Unity JobSystem构造BVH
BVH 是一种空间存储数据结构,便于空间查询。类似的空间查找方法还有BSP,Octree等等。
BVH的构造/查询比较快,空间冗余也比较少,在实时图形学领域用的比较广泛。比如NVidia的RTX技术,就是硬件固定管线实现了BVH便于RayTracing加速
构造BVH或其它空间查询结构对于渲染剔除,物理计算,粒子/boid/swarm系统通信等等都是很重要的,ECSPhysics这个项目是实现了BVH的,不过抄完测了一下感觉这个BVH构造的不对啊。于是找到BVH有并行算法实现,非常适合用Unity JobSystem多线程构造。于是基本参考了Thinking Parallel, Part III: Tree Construction on the GPU这篇经典文章自己在Unity中实现。
构造BVH的基本流程:1. 构造Z-Order 2. 排序 3 构造子节点 4 构造内部节点 5 更新AABB

1 ZOrder Curve & Morton Code

是一种将多维数据降为一维的方法,降为一维的好处是便于排序,便于存储。用这种方法将场景物体排序后再并行构造BVH会比较方便。
其原理可以参考Morton encoding/decoding through bit interleaving这篇文章,把xyz三个维度的bit展开交织在一起。文章里面讲了loop/magic bit/LUT三种方法。magic bit比较好写,速度也比较快,一般也就采用这种方法。ECSPhysics里面照抄的Thinking Parallel, Part III: Tree Construction on the GPU的写法.

需要注意的是xyz只有10bit的空间,对大量物体是不够用的,这也会出现mortoncode相同的情况,后面会遇到这个问题。
注意CalculateMortonCode要输入一个0-1的向量,ECSPhysics似乎代码写错了
对于Y轴变化比较少的情况也可以用2D的版本,这样xz各有16bit,大大减少morton code相同的情况。

2. 排序

ECSPhysics代码里用Radix单线程排的序,Profile看这也是性能瓶颈之一,一核有难七核围观
并行排序可以考虑Bitonic Sort,时间复杂度是o(log(n)^2)。很好的是每个pass不会有data racing的。原理和双调序列的特性相关,有Batcher定理:这篇文章讲的很好,三十分钟理解:双调排序Bitonic Sort,适合并行计算的排序算法
于是笔者用Job实现了Bitonic Sort。比较麻烦的是Job好像不能递归调用,只能一个pass开一个job了

调用是在某个JobComponentSystem的OnUpdate里

Profile看确实比原来的单线程快一些,但可能有线程调用和开销,也不是很理想。猜测另一个原因是理论时间复杂度o(n*log(n)^2),GPU上n核并行才能做到o(log(n)^2),CPU上要看log(n)/core了,8核的话n小于10^8还是比quicksort快的,10000个元素估计能快一倍吧。4核估计速度就不是很显著了。

3 构造子节点

没有什么技术含量,这里就不放代码了

4 构造内部节点

Tero Karras 论文里放了伪码,Thinking Parallel, Part III: Tree Construction on the GPU里面也放了C++的代码。但是determineRange(i),这个函数代码没给出来。
其实主要划分成三步
  1. determinrange
  2. findsplit
  3. output
第一步找到split可能出现的范围,第二步binary search找split,第三步输出

其实也好实现,照抄伪码就行。这步是很神的。先binary往前找最远的range,再binary往回找最近的range。

这时会遇到一个坑,clz的计算,common leading zero。__clz是C++原生的,c#里只能面向stackoverflow

然后又会遇到一个大坑,mortoncode一样怎么办???
如果mortoncode一样的话构造bvh时,determinrange和findsplit都会出错,最后树节点上会有环,没法更新aabb了。
Tero Karras 原始论文Maximizing Parallelism in the Construction of BVHs, Octrees, and k-d Trees里第四节有讲,  大致就是如果mortoncode一样的话用index来fallback算一下。
于是就有了下面的代码

5 更新AABB

bottom-up更新,第一个到的节点退出。这里理应有一锁,避免datarace。实际应用中并不会写,用Interlock造成了unity死锁。目前这样偶尔会出错但一般问题不大,如果有谁会写请告诉我。

最后水平大概是30k物体用10ms.

profile

相关代码在我的Github项目OSMTrafficSim里,可以直接看Assets/Code/BVH这部分

参考资料

Thinking Parallel, Part III: Tree Construction on the GPU,本文的主要参考。有一些源码,解释也较为通俗。作者Tero Karras 原始论文可见Maximizing Parallelism in the Construction of BVHs, Octrees, and k-d Trees
Morton encoding/decoding through bit interleaving,有关MortonCode的计算. 作者也是libmorton的作者
ECSPhysics, 一个用ECS做物理的项目,可以看代码学习ECS,想抄它的BVH发现它可能写错了

 

 

 

 

4 thoughts on “Construct BVH with Unity Job System | 用Unity JobSystem构造BVH

  1. ChenA说道:

    TA代码玩的这么溜,厉害啊。
    是做无人驾驶测试吗?

    1. maajor说道:

      哈哈没那么高级,就是学习一下ECS

  2. ChenA说道:

    你这评论还要审核的吗?刚才的评论没显示。

    1. maajor说道:

      是的好像之前规则是默认没评论过的用户都需要审核,刚给取消掉了试试看

发表评论

电子邮件地址不会被公开。 必填项已用*标注