NOTE

关于光线追踪，可以考虑光线追踪一个周末、一周、一辈子三部曲.

渲染方程#

Whitted风格的光线追踪并非完全物理正确。它每次只考虑反射：当光线遇到反射面的时候，才反射光线，并且应该是完全反射，或者可能是根据材质的漫反射和反射的比率去反射光线，并且反射出去的光线一定是理想反射，颜色叠加形成结果，思路非常简单。

ray_tracing(origin, dir):  
	// 这条光线的颜色.  
	Ray ray(origin, dir);  
	if ray hit some object at point p:  
		if p is a diffuse surface:  
			color = computeDiffuseColor(p);  
		elif p is a specular surface:  
			color = diffuse_rate * computeDiffuseColor(p) +specular_rate * ray_tracing(p, specular_dir(dir, normal));  
	else:  
		color = computeEnvironmentColor(dir);  
	return color;  
  
whitted_style:  
	foreach pixel p in rendertarget:  
		p.color = ray_tracing(camerapos, dir);  

加速结构#

光线追踪的思路非常简单，但想要高效地做并不简单。下面是一些基本的加速结构。

包围盒#

光线追踪实现的核心问题之一就是 直线与物体求交，如何判断一根光线打到一个物体。简单的几何体，如正方体、球体等（有简单的显式表达式）很容易计算，但绝大多数模型毕竟不是这些简单的东西，而是千奇百怪的Mesh，所以计算交点是个挺困难的问题。

对于任意Mesh，计算交点的简单思路就是暴力遍历，遍历所有面。计算平面（Mesh一直每个面的法向和顶点，显然知道平面方程）和直线的交点比较简单，而算出这个点之后可以转化为三角形顶点坐标判断它是否在三角形内部。但是直接在整个场景多个Mesh中这样求解碰撞显然不现实。所以引入了“多级”判断的思路：首先判断这个光线是否打到了某个物体的附近。

而界定了一个模型“附近”的东西就是包围盒：一个便于计算的最小的包围了这个Mesh的简单几何体。为了便于计算，这个包围盒一般是三对面分别与xyz平面平行的立方体盒子。这样，计算直线与每个面的交点就只用代入x,y,z某个轴的坐标值即可。这样的包围盒成为 AABBs.

而如何确定，一根光线是否穿过了一个包围盒，这可以通过判断直线和包围盒交点数量来判断。两个是穿过，一个是发射点在内部。

在计算了光线穿过哪些AABB包围盒之后，才遍历包围盒中的模型的面。

空间划分形成树#

对于每个光线，首先和所有物体的包围盒计算交点也是我们所不希望的。我们提前把环境做某种划分，形成规模从大到小的层次，如果大层次的盒子都不和光线相交，就没必要计算其下更小层次的了。这样，一次求交判断就能筛去多个包围盒，是一种更高效的做法。

一个简单的想法是基于空间做划分。

八叉树#

直接把空间划分为八叉树，不断划分，直到每个叶子中的物体数量足够少。

KD树#

不像八叉树那样每次都均匀分，而是每次划分的时候尽可能使得划分出来的空间都有完整模型（不分到模型中间，这并不容易）。KDt树对于n维（图形中是三维）数据，选择n-1维平面对于空间进行划分，这个平面应该尽可能使划分出来之后物体均匀的分布在两个子空间中。一般来说，每次划分的维度是在物体分布最多的那个维度。

最后是一个二叉树。

BSP树#

即二叉空间划分。不过不对划分方式做规定，允许奇奇怪怪的划分（比如斜的，不与轴平面平行的平面去划分），来获取可能的更优的划分结果。但是这样的划分既不容易求也不方便后续计算，反而更低效。

物体划分BVH#

基于空间的划分无论如何都有一种问题：一个物体被“割断”了。基于物体的划分能完全避免这种问题，它划分物体而不划分空间。对于要被划分在一起的若干物体，计算这些物体的总的AABB包围盒：这非常简单（所有AABB盒的最大/最小，很好算）。

但这同样有个问题，无法保证划分到一起的物体形成的划分空间小。有可能划分到一起的物体离得远，总的包围盒很大，从求交意义上来讲，这一步和这个大空间求交是不划算的。

实践上，一般尽量把物体左右均分来划分，即划分后，某个轴向上左右两个子物体集的数量相同。

碰撞检测话题#

以下是关于碰撞检测的一些话题，和上面的光线与物体求交有相似之处，也有不同的地方。

模型越来越复杂，很多时候即使是遍历一个模型的面也不现实。这时候还有更进一步的划分：把模型也拆为多个部分、层次，给每个部分、层次一个包围盒，以到达通过层次包围盒一次筛去多个面或顶点的作用。同时，问题也会被简化成按顶点进行近似碰撞检测。在医学仿真等要求较高的仿真需要往往用到这个。

对于游戏来说，碰撞检测可以简单的多：很多时候游戏只关心是否发生了碰撞而不关心具体碰撞位置。所以直接用碰撞箱来做。

另一个做碰撞检测的非常精妙的思路是基于 AABB 包围盒的思路，它可以做大规模碰撞检测。它基于一个基本的观察：如果两个模型碰撞则其 AABB 包围盒一定相交，而AABB包围盒有相交则这些包围盒在 xyz平面上的投影都有交集。其实现可以更加简化，在xyz分量上分别对这些包围盒做排序，只有排序关系发生变化的时候才可能发生碰撞或者碰撞分离。