图形学笔记（十一）光线追踪——Shadow Mapping、光线追踪、光线投射、软硬阴影、光线与物体交点、AABB包围盒
图形学笔记（十三）光线追踪3——双向反射分布函数BRDF（反射方程、递归方程）、辐射度量学基础radiometry、立体角、Radiant Energy、Flux、Irrdiance、Radiance

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

1.1 预处理——建立加速格子

1. 找到包围盒
2. 创建格子
3. 标记与物体相交的格子

1.2 光线与场景求交点

1. 按照光线穿梭的顺序遍历格子
2. 对于每个格子，计算存储在格子里的所有物体是否与光线有交点。

1.3 加速效果

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

• 只有一个格子：没有加速效果。
• 格子特别密集：需要做很多光线与格子求交，加大开销。

即想要获得比较好的加速效果，格子不能太稀疏，也不能太密集。下面是人们经验得到的规律。

• #cells = C*#objs
• C=27 in 3D

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

但是此方法不适合于有很多空旷区域的场景（如下图所示），下面又称为“teapot in stadium”问题。

2 空间划分（Spatial Partitions）

2.1 空间划分的例子

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

2.2 KD-Tree

1> KD-Tree 的基本结构

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

对于非叶子节点：

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

对于叶子节点：

• 存储物体列表。

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

找到叶子节点1，与区域内的所有物体求交。

以此类推，找到与光线有交点的格子内的物体，然后与格子里面的所有物体求交。

3> KD-Tree的问题

1. 很难判断物体的三角形和AABB包围盒是否有交集。
2. 一个物体可能会与很多AABB包围盒有交集。也即一个物体可能存储在多个叶子节点里。

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

3.1 建立过程

• 找到包围盒
• 递归的把物体集合划分成两个子集
• 重新计算子集的包围盒
• 当满足一定要求的时候停止
• 在每个叶子节点里存储所有物体

以下是图解：

首先对于所有物体找到包围盒，形成根节点。

然后把物体分成两部分，并重新计算包围盒，形成根节点的子节点。

不断的递归重复这个过程，知道满足一定的条件后停止，最后在叶子节点存储物体列表。

3.2 BVH的优缺点

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

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

缺点：

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

3.3 建立中的细节问题

1> 如何划分节点？

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

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

2> 划分终止条件？

当节点包含少于特定元素时停止（比如5）。

3>BVH树的存储结构?

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

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

4 空间划分与物体划分

空间划分（如KD-tree）

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

物体划分（如BVH）

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