理解Bounding Volume Hierarchies(BVH)的方法
BVH基本结构
如上图所示,蓝色圆形代表内部节点,虚线带shape的代表叶子节点。
BVH和Kdtree的比较
BVH | KDtree | |
构建时间 | 快点 | 慢点 |
intersection效率 | 慢点 | 快点 |
数值准确度 | 好点 | 差点 |
bvh树的生成过程
如上图所示:红色是叶子节点,放Primivitive,黑色是node节点,蓝色是划分的界线。
如何划分子树?
第一步,沿着x y z选一个轴。
如上图所示,遍历当前要划分的所有primitive,计算出它们中心投影到xyz轴,所有投影点的集合的最远距离,选择最大值那个作为划分的轴。
简单来说就是把所有primitives的中心点构建新的bounds,求出这个bounds的最大轴。
上图dy > dx,所以选y轴做划分。
第二步,延着选好的轴划分节点。
pbrt中介绍了4种划分方法,
SAH, HLBVH,Middle,EqualCounts。
这里我只介绍SAH(Surface Area Heuristic)。
划分原则:
根据对每个节点的intersection test估计的消耗时间来划分。
时间消耗的计算:
上面公式的各符号的解释如下(pbrbook截图):
消耗时间最小的,可以考虑成为leafnode,否则继续划分成子节点。
给一个相对值1/8,也是一个相对值1,假设所有primitive的检测时间一样。
和分别是ray和A、B节点的primitives命中的概率。
这个概率等于A的bounds的面积和父节点的bounds的面积的比例。
如上图,A是父节点面积,B,C是两个节点面积,那么概率分别是和。
接下来是最关键的步骤了!
1.把场景划分按选好的轴的方向划分成多个bucket。
2.把中心点在bucket的bounds内的primitive加到bucket内,并更新bucket的bounds。
3.bucket按顺序分两组进行消耗时间的估计,求出最小时间的那组。
4.生成节点。
bucket的分组算法如下图所示:
如图,按buckets数值遍历,每次分成两个节点A和B,然后计算出每次分组的时间消耗cost。
cost最小的划分就是进行分组。
例如,有12个buckets,全部分组计算完后,i = 4时(前4个bucket一个节点后8个一个节点)的cost值最小,那么就按这组生成子节点。
最后递归结束,BVH树就生成完毕。
BVH的碰撞检测
BVH节点生成后,必须按一定规则放到数组里以用于做碰撞检测。
排列按深度优先顺序规则,
第一个子节点放着当前节点的下一个位置,第二个子节点的位置要记录下来。
如图所示:
下面是碰撞检测的过程:
遍历经过深度优先排列的node的数组,假设node在碰撞检测成功后,分两种情况:
1.node是叶子节点
遍历所有primitive并做碰撞检测,每次检测都修改ray的tMax参数,tMax参数修改后,距离ray的orig远的就不一定可以检测的到,提升了效率。
遍历完primitives后,检测在之前把node放进了盏里的其他node。
2.node是非叶子节点
前面介绍了tMax的修改可以提升效率,所以在遍历非叶子节点时,要考虑轴的划分方向和ray的方向:
如图,如果ray和axis方向是正数时,就按child1->child2的顺序遍历,否则按child2->child1的顺序。
if (dirIsNeg[node->axis])
{
nodesToVisit[toVisitOffset++] = currentNodeIndex + 1;
currentNodeIndex = node->secondChildOffset;
}
else
{
nodesToVisit[toVisitOffset++] = node->secondChildOffset;
currentNodeIndex = currentNodeIndex + 1;
}
参考:
pbrbook 4.3