(论文)[2011] RTSAH Traversal Order for Occlusion Rays

Posted on Edited on In Views:
RTSAH 进行 occlusion rays 的加速

RTSAH Traversal Order for Occlusion Rays

简要说明

  • 在 SAH 的基础上，加上一个可见性函数 V，进行对于 occlusion rays 的判定优化

1. Introduction

  • RTSAH
    • ray termination surface area heuristic
  • 能够加速树结构中具体遮挡结点的寻找
    • 启发式的展开某个子结点，而不是传统的先展开近的子结点
    • 可以扩展到半透明的介质（避免了和半透明物体的再次求交）
  • 2x speedups
  • Unlike radiance rays where we are interested in the closest hit object, for occlusion rays, we are interested in whether any hit occurs.
  • 一些定义
    • occlusion rays：只返回可见性，而且不能改变方向
    • radiance rays：scattering, reflection, refraction, ...
  • 对于 occlusion rays 我们只关心是否相交，因此遍历子结点的顺序可以不从近到远

2. background

Surface area heuristic

  • 表面积启发式算法
  • SAH 的基本假设
    • 所有的光线在整个场景中均匀分布
    • 光线不会被遮挡（击中一个物体后继续传播）
  • 有如下概率公式

\[ P(\mathrm{child\ hit|parent\ hit})=\dfrac{\mathrm{SurfaceArea(child)}}{\mathrm{SurfaceArea(parent)}} \]

  • 我们进行如下定义

\[ P_x=P(\mathrm{node\ x\ hit|x'parent\ hit}) \]

  • 我们假设每一次求交（intersection test）和结点遍历（node traversal step）的代价是一个固定值，\(T_{\mathrm{intersection}},T_{\mathrm{step}}\)
  • 结点遍历代价如下（递归定义）
    • \(N_x\) 表示结点 \(x\) 中的 object 个数
    • \(l,r\) 表示左子树与右子树

\[ C_{\mathrm{node}}=\left\{ \begin{array}{**ll**} P_lC_l+P_rC_r+T_{\mathrm{step}} & \mathrm{if\ an\ inner\ node,}\\ N_{\mathrm{parent}}T_{\mathrm{intersection}}+T_{\mathrm{step}} & \mathrm{if\ a\ leaf.} \\ \end{array} \right. \]

  • 在实际进行估计的时候，计算 \(C_{\mathrm{cost}}\) 的时候可以把 \(C_l,C_r\) 当作叶子结点处理
    • WALD I., HAVRAN V.: On building fast kd-trees for ray tracing, and on doing that in O(N logN). In Symposium on Interactive Ray Tracing (2006), pp. 61–70.
  • BSP vs BVH
    • BSP(binary space partitioning)、BVH(bounding volume hierarchy)
    • BSP：没有重叠，按照从近到远的顺序找到的第一个交点就是结果
    • BVH：可能有重叠，找到第一个交点之后可能还需要进一步判断
      • 判断能否提前停止树上的查找就是一个比较强的优化（SAH 不考虑这个）
      • SAH 加入这个判断反而可能变慢
        • HAVRAN V.: Heuristic Ray Shooting Algorithms. PhD thesis, Faculty of Electrical Engineering, Czech Technical University in Prague, 2001. 2

3. RTSAH

  • 我们扩展了 SAH 算法，认为每一个结点都有一个连续的可见性函数 \(V\)
  • 简单化，我们认为非空的叶子结点（leaf）是完全不透明的（\(V=0\)）,空的叶子结点是完全透明的（\(V=1\)）
    • 内部节点（interior node）由一些空的和非空的结点组成，\(V\) 介于零一之间
    • 具体定义在下面
  • 在树中只要找到了一个结点相交，那么立即停止遍历
    • 因此如果遍历的时候进入了其中一个子结点，那么一定不会进入另一个子结点
  • \(P_{lr}\) 表示光线同时穿过左右两个子结点的概率
    • \(P_{jl}=P_l-P_{lr}\)：只穿过左子结点，不穿过右子结点的概率
    • \(P_{jr}=P_r-P_{lr}\)：只穿过左子结点，不穿过右子结点的概率
    • \(P_e=1-(P_{jl}+P_{jr}+P_{lr})\)：都未击中的概率
  • 步骤（packetized ranged traversal）
    • 我们先进入左子结点，看看是否存在光线和这个结点相交
    • 如果所有的光线都和这个结点相交，那么就不需要进行和另外一个结点的相交测试（intersection test）
    • 如果只有部分光线或者没有光线和这个结点相交，那么就需要继续对另外一个结点进行相交测试
  • 我们可以得到优先遍历左子结点的代价函数
    • \(T_{\mathrm{step}}\)：left bounding box
    • \(P_lC_l\)：遍历左子结点的代价（概率 \(\times\) 代价）
    • \((P_{jr}+P_{lr}V_l+P_e)T_{\mathrm{step}}\)：right bounding box
      • \(P_{jr}\)：没有光线和左结点（的包围盒）相交
      • \(P_{lr}V_l\)：和左结点（的包围盒）相交，但是没有和左结点中的物体相交
    • \((P_{jr}+P_{lr}V_l)C_{r}\)：遍历右子结点的代价

\[ leftFirst=T_{\mathrm{step}}+P_lC_l+(P_{jr}+P_{lr}V_l)(T_{\mathrm{step}}+C_r)+P_eT_{\mathrm{step}} \]

  • 右子结点优先

\[ rightFirst=T_{\mathrm{step}}+P_rC_r+(P_{jl}+P_{lr}V_r)(T_{\mathrm{step}}+C_l)+P_eT_{\mathrm{step}} \]

  • 对于 radiance rays，我们希望优先进入距离光线起点比较近的子结点
    • 我们假定光线是随机的、相互独立的
    • 我们假定每次都优先遍历比较近的子结点，代价如下

\[ C_{\mathrm{node}}=\dfrac{1}{2}(leftFirst+rightFirst) \]

  • 对于 occlusion rays，我们希望优先进入的结点导致的结果是代价较小的（代价与光线无关）

\[ C_{\mathrm{node}}=\min(leftFirst+rightFirst) \]

  • 叶子节点的代价和上面相同

\[ C_{\mathrm{leaf\ node}}=N_{\mathrm{parent}}T_{\mathrm{intersection}}+T_{\mathrm{step}} \]

  • 可见性函数 \(V\) 的定义如下

\[ V_{\mathrm{node}}=\left\{ \begin{array}{**ll**} P_{jl}V_l+P_{jr}V_r+P_{lr}V_lV_r+P_e & \mathrm{if\ an\ inner\ node,}\\ 0 & \mathrm{if\ a\ nonempty\ leaf,} \\ 1 & \mathrm{if\ a\ empty\ leaf.} \\ \end{array} \right. \]

  • \(\dfrac{P_{lr}}{P_{l}}\) 可以看成是从左子结点离开到右子结点的一个 rays（energy）的一个辐射因子
    • 我么可以通过 SAH 的方式计算 \(P_l,P_r\)，因此只需要找到上面说的辐射因子，便能够计算出 \(P_{lr}\)
    • 接着也能够计算出其他剩余的量：\(P_{jl}=P_l-P_{lr}\) 等
  • 如何计算辐射因子？
    • 论文：Practical applications of form factor computation in lighting calculations
    • 方法如下
      • decompose the node bounding boxes into their rectangular faces and then analytically compute the form factors between all valid face pairs and for the overlapped region (see [Cho02] for a good survey of the relevant equations).
      • TODO

BSP

  • 对于 BSP 结构，代价函数是类似的
  • \(P_e=0\)，恰好把整个父节点的空间划分给了子结点
  • \(P_{lr}\ne0\)，可能出现光线斜穿的情况
  • BSP 不需要上面的辐射因子就能够计算 \(P_{lr}\)：\(P_{lr}=P_l+P_r-1\)
  • occlusion rays
    • \(P_e=0\)
    • 我们不需要进行对另外一个子结点的包围盒求交测试（不和第一个相交，一定和第二个相交）

\[ \begin{aligned} leftFirst &=T_{\mathrm{step}}+P_lC_l+(P_{jr}+P_{lr}V_l)C_{r}\\ &=T_{\mathrm{step}}+(P_{jl}C_l+P_{lr}C_l)+(P_{jr}C_r+P_{lr}V_lC_r)\\ &=T_{\mathrm{step}}+P_{jl}C_l+P_{jr}C_r+P_{lr}(C_l+V_lC_r)\\ \end{aligned} \]

\[ C_{\mathrm{cost}}=T_{\mathrm{step}}+P_{jl}C_l+P_{jr}C_r+P_{lr}\min\left\{C_l+V_lC_r,C_r+V_rC_l\right\} \]

Approximate BVH RTSAH

  • The BVH preprocess cost can be lowered at the expense of rendering performance by approximating the probabilities instead of finding them by sampling.
    • 感觉是在说辐射因子的估计
  • 在实时渲染中，我们可以假设 \(P_e=0\)，可以起到一个加速的效果

4. Choosing Traversal Order of Occlusion Rays

  • 按照上面说的方式比较即可，对于 BSP 树，可以优化（上面提到了）

Storage overhead

  • 我们只需要知道优先遍历那一个结点即可，而不在意具体的代价值的大小，因此只需要使用一个布尔变量记录即可（可以压缩到其他变量的某一个 bit 中）

Attenuated occlusion rays

  • 半透明材质只是会使得光线有所衰减，而不会让它停止
  • 我们在判断 occlusion rays 的时候，只需要将上面的定义的函数 \(V\) 修改一下
    • 如果叶子结点包含的所有物体都是透明材质的，我们让它的 \(V=1\)
  • 对于只报告可见性的 occlusion rays，不按照从前往后的顺序去遍历，不会导致半透明物体的不正确渲染
  • 一个标准的从前向后处理半透明物体的 ray tracer，在加速结构中就应该处理好了半透明物体
    • 击中半透明物体之后，应该投射出一条新的光线，继续和加速结构求交
    • 这样我们就不需要对其进行特殊处理
  • 如果加速结构中没有实现，那么即使是从前向后遍历也可能会出现乱序的问题
    • 一个结点内部的物体是没有顺序的，一个物体可能跨越多个结点
    • 一个简单的解决方案可以是，记录所有的交点，直到找到新的交点之后再进行着色处理

8. conclusion

  • We presented an improved version of the SAH, which we call the RTSAH, that takes into account ray termination and gives the expected traversal cost of radiance and occlusion rays through a tree. We then showed how the RTSAH can be used to guide the traversal of occlusion rays through a tree so that an intersection can be more efficiently located. The RTSAH traversal can try to avoid attenuating materials for a further improvement in traversal efficiency. The RTSAH can be computed faster than the tree can be built and there is practically no storage or rendering overhead for using it. For scenes that comprise mostly of occluded rays, the RTSAH traversal can give a substantial performance increase.