FJBQ
0%

【Games 101】Lec 14：光线追踪 2（加速光线追踪 和 辐射度量学）

发表于 更新于 分类于 ，

Lecture 14：Ray Tracing 2 (Acceleration & Radiometry)

概述

这节课讲了 光线追踪的加速 和 辐射度量学；

这篇文章写的是光线追踪的加速，辐射度量学一起放在下一篇文章；

上篇文章讲了包围盒，这节课前面讲的是如何用包围盒加速光线追踪；

均匀空间划分 Uniform Spatial Partitions （Grids）

预处理 – 建立加速格子

  • 找到包围盒
  • 创建格子
  • 标记出和物体相交的格子

光线与场景求交点

  • 依次遍历光线穿过的格子
  • 如果这个格子被标记，则说明这个格子里面有物体，那么就计算光线是否和这个格子里面的物体相交

均匀空间划分的结果

格子太多和格子太少都是不好的。

  • 只有一个格子：没有加速效果。
  • 格子特别密集：需要做很多光线与格子求交，加大开销。
  • 下面是划分方式的经验之谈：

格子划分法适用于大小和空间均匀分布的大型对象集合（如下图所示）。

但是此方法不适合于有很多空旷区域的场景（如下图所示），下面又称为 “teapot in stadium” 问题。（其实就是分布不均的场景，有的地方物体很密，有的地方物体很稀疏）

空间划分（Spatial Partitions）

空间划分的方式

  • Oct-Tree 八叉树 把场景包起来，然后把正方体切成八份（三维的就是8份，xyz各切一刀，但是上面的图是4份，因为是2维的，所以看起来是2^2）。不断的对子节点递归进行此过程，放格子里面是空的或者物体足够少就停下来。（但是有个严重的问题，随着维度的升高，节点数量指数型增长）
  • KD-Tree 与八叉树几乎相同，但是对每次划分的格子，总是沿着某一个轴切割（通常是交替的），且对每个格子仅切割一次。（好处是相比于八叉树，节点数量的复杂度不会随着维度指数型增长。）（而且不用等分，看下面的例子好理解）
  • BSP-Tree 对空间二分，每次划分时选择一个方向，与KD-Tree的区别在于它的切割不一定是与轴平行的。（存在的问题是在维度高的时候不好计算，切割的几何体从点到线到面到超平面。）

KD-Tree

KD-Tree 的基本结构

本质上是一颗二叉树，如下图所示（为了简化没画全，实际上1、2等节点都有子节点）。

  • 对于非叶子节点
    • 划分的轴：x、y或z轴。
    • 划分的位置：分割的平面沿轴的坐标。
    • 子节点：一定有两个子节点。
    • 在非叶子节点不会存储物体。
  • 对于叶子节点
    • 存储物体列表。

还是有点抽象？没事，看一下下面的应用：（最好看一下原视频）

计算光线与物体交点的步骤

  • 如果走到非叶子节点，则探一下它的两个子节点（递归）
  • 如果走到叶子节点，则：
    • 如果包围盒里面没有物体，则跳过就行了；
    • 如果有物体，则判断光线是否和物体相交；

KD-Tree的问题

  • 很难判断物体的三角形和AABB包围盒是否有交集。（比如一个包围盒很小，整个嵌在了三角形的面里面，这个要怎么判断？）
  • 一个物体可能会与很多AABB包围盒有交集。也即一个物体可能存储在多个叶子节点里。（计算起来比较废）

物体划分与BVH加速结构（Object Partition & Bounding Volume Hierarchy）

换一种思想，既然对空间划分这么麻烦，那么就直接划分物体；

思想和步骤

  • 首先找到一个包围盒（这个简单啊，所有三角形坐标求min，max就行）
  • 递归的把物体集合划分成两个子集；
  • 重新计算子集的包围盒；
  • 当满足一定要求的时候停止（比如规定一个包围盒里面只有五个三角形的时候）；
  • 在每个叶子节点里存储所有物体；

下面是图解：

BVH 优点和缺点

BVH避免了KD-Tree的问题，具有如下优点。

  • 一个物体只能出现在一个格子里。
  • 不涉及三角形和包围盒求交的问题。

缺点：

  • BVH并没有把空间严格的划分开（包围盒有可能相交）。

BVH 的细节问题

如何划分节点？

每次都需要选择一个维度来分割（经验上有下面两种做法）。

  • 选择节点中最长的轴。
  • 取中间的物体的位置来划分节点。

如何存储 BVH 树？

  • 中间节点存储包围盒和子节点的指针。
  • 叶子节点存储包围盒和物体列表。
  • 节点代表场景中图元（primitives）的子集，所有物体都在子树中。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
-- 参考的是课件里面的
Intersect(Ray ray, BVH node) 
{
    if (ray misses node.bbox) return;
    
    if (node is a leaf node)
        test intersection with all objs;
    	return closest intersection;
    
    hit1 = Intersect(ray, node.child1);
    hit2 = Intersect(ray, node.child2);
    return the closer of hit1, hit2;
}

空间划分和物体划分

空间划分（如KD-tree）

  • 把空间划分成不重叠的区域。
  • 一个物体可能被包含在多个区域中。

物体划分（如BVH）

  • 把物体划分成不相交的子集。
  • 每个子集的包围盒在空间上可能是重叠的。

参考

图形学笔记（十二）光线追踪2——使用AABB包围盒加速光线追踪、空间划分（八叉树、KD树、BSP树）、物体划分（BVH加速结构）、光线与物体求交_光线追踪算法遍历八叉树-CSDN博客

AI孙燕姿 真好听 hhh

等哪天闲了也来研究研究这东西。

欢迎关注我的其它发布渠道