图形学笔记 - 5. 光线追踪2 - 加速结构

目录

使用AABB加速光线追踪

Uniform Spatial Partitions (Grids) 均匀空间划分

空间划分

KD树预处理

KD-Tree数据结构

遍历kd树

对象划分 & Bounding Volume Hierarchy 层次包围盒 BVH

BVH遍历

空间划分与物体划分呢

---

GTC news: DLSS、RTXGI 实时光线追踪

使用AABB加速光线追踪

• Uniform grids 均匀网格

• Spatial partitions 空间划分

Uniform Spatial Partitions (Grids) 均匀空间划分

预处理-构建加速网格

1.找出边界盒 2.创建网格 3.将每个对象存储在重叠的单元格中

Ray-Scene相交 以射线遍历顺序步进网格 ray traversal order 对于每个网格单元 -使用存储在该单元格中的所有对象测试交叉 光栅化一条线

Grid Resolution网格解析度，栅格分辨率 单个单元：没有加速

太多单元：由于不必要的网格遍历而导致的效率低下

Heuristic启发式 #cell = C * #objs C = 27 in 3D

表现好的情况： 网格在大小和空间均匀分布的大型对象集合上工作得很好

“Teapot in a stadium”问题

空间划分

Oct-Tree：八叉树 KD-Tree: 每次分一块

KD树预处理

KD-Tree数据结构

中间节点存储

• 划分轴：x-, y-, or z-

• 划分位置：分割平面沿轴的坐标

• children：指向子节点的指针

• 内部节点中不存储任何对象 叶节点存储

• 对象列表

遍历kd树

内部节点：分裂

缺点： KDtree 物体与包围盒相交难以判断 一个物体可能存在多个节点

对象划分 & Bounding Volume Hierarchy 层次包围盒 BVH

分成两堆三角形

• 寻找边界盒

• 递归地将一组对象分成两个子集

• 重新计算子集的边界框

• 必要时停止

• 在每个叶节点中存储对象 确保一个物体只可能出现在一个格子

如何细分节点？

• 选择要分割的维度

• 启发#1：始终选择节点中最长的轴

• 启发#2：在中值对象的位置分割节点 终止条件

• 启发式：当节点包含少量元素时停止（如5个） BVHs的数据结构 内部(internal)节点存储

• 包围盒

• children指向子节点的指针 叶子节点

• 包围盒

• 物体的列表 节点表示场景中原语的子集

• 子树中的所有对象

BVH遍历

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;
}

空间划分与物体划分

空间划分

• 将空间划分为不重叠的区域

• 一个对象可以包含在多个区域中 物体划分

• 将一组对象划分为不相交的子集

• 每个集合的边界框可能在空间上重叠