(论文)[1991] Shaft Culling for Efficient Ray-Cast Radiosity

Posted on Edited on In Views:
光线投射的可见性测试，shaft culling 方法

Shaft Culling for Efficient Ray-Cast Radiosity

思路

  • 在 emitter 和 receiver 之间，我们可能会做多次光线投射的可见性测试，因此我们进行预处理
  • 首先我们生成一个尽可能小的包围盒，将 emitter 和 receiver 包含进去
  • 然后我们生成一个 list，list 里面包含可能和这个包围盒相交的 bv（可能对 emitter 和 receiver 之间的可见性又影响的 bv）
  • 之后我们对每一条光线，只需要判断它和 list 中的光线是否有交即可

说明

  • object：一个可渲染的图元
  • item：一个 object 或者多个 item
  • 算法准备工作：根据给定的 object 建立 bvh（bounding volume hierarchy）
  • reference items：the emitter and the receiver
  • candidate list：可能挡住 emitter 和 receiver 之间可见性的一组 item
  • 每次需要判断两个采样点之间的可见性时，我们遍历整个 candidate list，直至找到交点或者遍历结束
  • 怎么生成 candidate list？如下是两种比较 trivial 的方法
    • 可以使用整个场景所有 object 构成 candidate list
    • 只使用 bvh 的根节点，遍历整棵树
  • 如果我们能够在空间上定义一个 volume，它能够包含整个空间中在 reference items 之间的所有点，这样便能够形成一个比较好的 candidate list
    • 这样只需要判断 object 是否在 volume 之内即可
  • 时间花费：建立 candidate list 花费的时间和使用它节省的时间
    • 可以估计允许我们使用多少时间生成 candidate list
  • 是否生成 candidate list
    • emitter 和 receiver 相隔很远，不生成
  • 预计算潜在的在 reference items 之间的光线，如果大于预设值则生成使用 candidate list，否则不生成使用
    • 简单的测试

candidate list 算法

  • candidate list 算法有 3 个步骤
    • forming the testing volume
    • creating the candidate list by using this volume
    • accessing the candidate list for visibility determination between samples

(1) Forming the Testing Structure

  • 主要步骤如下
    • Obtain the bounding boxes for the reference items.
    • Compute the extent bounding box containing both reference items.
    • Create the plane set between the two reference items' boxes.

  • 第一步

    • 我们使用 bvh，因此可以很容易得到 reference item 的包围盒，AABB 包围盒（axis aligned）
    • \(lo.x,lo.y,lo.z,hi.x,hi.y,hi.z\)

  • 第二步

    • 直接对两个 reference item 的包围盒取边界值（大的取大，小的取小）
    • 同时找出 culled edges（扩展包包围盒中不属于 reference item 的边）

  • 第三步

    • 找到一组平面，将两个 reference item 的包围盒连接在一起

    • 形成 minimal bounding volume

    • 我们削去包围盒中和 culled edges 相邻的一块空间

      • 我们将 volume 称为 shaft

    • 同时需要记录哪一个生成扩展包围盒的时候，哪一个包围盒的顶点成为了边界值（最大最小）

      • 称为 list
      • 用于确定 culled edges

    • 两个 reference item 都需要有一个 list，每个 list 最多有 6 个 entry

    • 每一个 entry 记录类型（minimum / maximum）和方向（X / Y / Z）

      • 例如 MIN_Z

    • 如果 reference item 的最小/大值相同，则两个列表都不会出现这个 entry

运行过程

  • 构造 list
    • emitter list：MAX_Y
    • receiver list：MIN_X，MIN_Y，MAX_X
  • 第三步构造 planes，两个 list 中的元素两两组合（去除方向匹配的边），剩下的边就是 culled edge
    • MAX_Y——MIN_X
    • MAX_Y——MIN_Y（方向匹配上了，去除）
    • MAX_Y——MAX_X

  • MAX_Y——MIN_X
    • 切去边 ：\((lo.x,hi.y,lo.z)-(lo.x,hi.y,hi.z)\) 关联的边（culled edge）
    • 生成平面的法线（就和我们平时法线的定义一致），得归一化
      • 未参与 \(Z.direction=0\)
      • \(X.direction=Receiver.hi.y-Emitter.hi.y\)
      • \(Y.direction=-Receiver.lo.x+Emitter.lo.x\)
    • 平面与原点的距离（原点指向平面，法线）
      • \(P.distance=-(X.direction\ast lo.x+Y.direction\ast hi.y)\)
      • \(lo.x,hi,y\) 使用任意 reference item 的都行，是等价的（画图即可看出来）
  • 形成的 plane 的集合保存在一个 list 中，称为 plane set
  • 可能 plane set 为空
    • 当一个 reference item 整个都在另一个 reference item 的里面时，plane set 为空
  • 其他例子

(2) Creating the Candidate List

  • 使用第一步建立的 shaft，和场景中的物体求交，生成 candidate list，具体生成方法如下

  • 首先使用 bvh 的根节点和 shaft 求交，可能出现如下的 3 种情况

    • The item is entirely outside of the shaft.（在 shaft 外面）
    • The item is entirely inside the shaft. （在 shaft 里面）
    • Else, the item overlaps the shaft. （和 shaft 部分相交）

  • 如果在 shaft 外面，直接忽略

  • 如果是在 shaft 里面或部分相交，则有多种策略

    • always open
      • 始终递归进行，直到叶子结点（不是 bounding volume）
      • candidate list 由所有不是 bv 的 object 组成
    • 非 always open 策略
      • 如果是在 shaft 里面，则将其加入到 candidate list 中
        • 如果光线 miss 则会加速（不需要和内部的 item 进行测试）
      • 如果是和 shaft 部分相交，则有多种策略

  • 和 shaft 部分相交的多种非 always open 策略

    • 叶子结点的处理
      • 如果是一个 object 而不是 bv，则加入 candidate list
    • keep closed
      • 直接将 bv 加入到 candidate list 中
    • overlap open
      • 和 always open 一样，递归展开至叶子结点
      • 当 reference item 之间的 object 比较少的时候可以使用
      • 但是可能这始终打开 bv 是一个比较耗时的操作（增加光线的测试）
    • ratio open
      • 设定一个 ratio 判定是否值得打开 bv
        • 例如 0.4
          • 如果 bv 中有超过 40% 的物体在 shaft 中或者与 shaft 相交，则不打开 bv，直接将其放入 candidate list
      • 值得注意的是，即使是满足上面 ratio 的条件，bv 也有可能被展开，bv 被保留的条件是内部的 item 比 bv 测试难得多得多
    • 多种策略

(3) Shaft Cull Testing

  • cull test：shaft 和 bv 求交
  • 被测试的 bv 被称为 test volume
  • 只考虑 sphere 包围盒和 axis aligned 包围盒
  • 判断流程如下
    • 判断 test volume 和 extent box 的位置关系：inside、outside、overlapping
    • 如果是 outside ，测试结束；否则判断 test volume 是否和 reference item 有重合部分（overlap）
    • 如果有重合部分，测试结束；否则将 test volume 和 plane set 进行位置关系的测试
    • 如果 test volume 是 outside ，测试结束；否则需要进一步测试（策略相关），判断 test volume 是否完全在 shaft 里面，或者是否展开 bv 等

Sphere bv 测试

  • 第一步：outside 测试
    • Arvo's algorithm for box/sphere comparison [Arvo, 90].
      • 每个轴分开处理
      • 如果在某个轴上，圆心在 box 内部，则求出圆心到这个轴对应的近一点的面的距离
      • 对上面的距离求平方和，和半径的平方作比较
      • 如果比平方和大，就是 outside
  • 第二步：overlap 测试
    • 和第一步相似，将 test volume 和 reference item 进行测试
    • 如果相交，则一定和 shaft 相交
  • 第三步：plane set，outside 测试
    • T=dot_product(Plane.normal, Sphere.center) + Plane.distance
      • 画图发现就是圆心到平面的距离
    • 如果 T>Sphere.radius，说明相离（outside）
      • 如果是内部的话，计算出来会的 T 是负数
    • 如果法线对于所有 plane set 中的 plane，都是 outside 的话，说明 bv 在 shaft 的外面
    • 仍然有可能出现 bv 在 shaft 外面的情况（false positive）
      • 这不会犯错，但是会增加计算量（误将其放入 candidate list）

  • 第四步：inside 测试
    • 如果对所有的 plane set 中的 plane，都满足 T > -Sphere.radius，则在 shaft 内部
    • 否则就归类于 overlap

AABB 测试

  • boxes 的测试不需要对 plane set 中的法向进行归一化
    • sphere 需要和半径比较因此需要归一化，但是这里比较的都是和 0 比，因此 scale 无关紧要
  • 定义 the distance of a point from the plane 如下
    • T = dot_product( Plane.normal, Point) + Plane.distance
  • 平面定义了半空间（half space）
    • T>0：outside
    • T=0：on
    • T<0：inside
  • 认为距离有正负大小区分
  • 给定一个平面，总有一个顶点到平面距离最大（farthest），有一个点到平面距离最小（nearest）
    • 这个顶点是平面法线的函数
      • farthest：对于法线，如果某一个轴值为正，则使用 box 的 hi 值；0 使用 0；负使用 box 的 lo 值
      • nearest：正：lo；0：0；负：hi
    • 例如，法线：[-3, 8, 4]
      • farthest：[lo.x,hi.y,hi.z]
      • nearest：[hi.x,lo.y,lo.z]
  • 因此测试过程和 sphere 一摸一样
    • extent box
    • reference item boxes
    • each plane in the plane set
      • 使用 nearest_corner
      • If dot_product( Plane.normal, Box.near_corner) + Plane.distance > 0
        • box is outside the plane (and the shaft)
  • 如果通过了上述测试，说明 test volume 和 shaft 的位置只有 inside/overlap
  • overlap 测试（一个满足则是 overlap）
    • If dot_product( Plane.normal, Box.far_corner ) + Plane.distance > 0
      • box overlaps shaft
  • 以上的方法虽然快，但是可能会将 outside 的物体判定为 overlap
    • plane set 的测试，我们用的是整个平面，可能会误判的问题，但是这个只会增加计算量而不会导致错误

(4) Candidate List Access

  • 对于 receiver 和 emitter 上的两个采样点，我们形成一条光线，使用 candidate list 进行测试
  • 使用栈实现，对于 bv，如果相交，则将其子结点压栈
  • 最终要么相交（和一个不透明的物体相交），要么栈弹空结束

算法改进

  • 我们知道两个 reference item 之间的光线一定是起源于某个 box，终止与另外一个 box
    • 因此如果 test volume 完全将某个 reference item 包含，则光线必定相交
    • 因此可以在第一步的时候，做一下这个测试
  • 基于辐射度算法会出现如下情况：一个 emitter，对多个 receiver，如下预处理很有效
    • 对 bv 进行预求交，判断它是否完全包含 emitter 的 reference box，形成一个 candidate list
      • 如果完全包含，直接展开为子节点
    • 这样的预计算可以减少重复计算
    • 之后和上面一样，当然之后 reference item 的完全包含测试只需要测试 receiver 即可
    • 同时在预处理的时候，可以在 candidate list 中保存 emitter 的 reference item 的位置关系，如果 emitter 是 overlap 的话，则后面算法中的 outside 测试就不需要了
    • 相当这一部分的改进就是，将后面可能的重复计算提前预计算了
  • 从 emitter 的 bv 开始向上展开形成 candidate list
    • 测试其父结点的所有子结点，然后重复向上（不需要测试父结点，一定相交）
  • emitter 的出射方向有限的时候，可以将不可见的面直接剔除