Real-Rime Rendering (8) - 光线求交（Ray intersection）

提要

       光线在图形学中可以简单地用向量来表示：r(t) =  o +td, o表示光线的出发点，d表示光线的方向，通常是单位向量，r表示光线在t时刻的位置。

       光线求交在图形学中有着非常重要的应用，比如Global Illumination,collision detect，更是Ray tracing算法的核心。

包围体 Bunding Volume

       首先要提一下包围体的一些基本概念。

      在计算机图形学与计算几何领域，一组物体的包围体就是将物体组合完全包容起来的一个封闭空间。将复杂物体封装在简单的包围体中，就可以提高几何运算的效率。通常简单的物体比较容易检查相互之间的重叠。
一组物体的包围体也是包含一个物体及周围相关环境的封闭空间，因此可以用它来表示一个非空、有限的单一物体。

       AABB

       AABB的全称是axis aligned bounding box，就是我们常常提到的包围盒子，这个盒子的边是平行于x/y/z轴的。 所有的2d和3d物体都是由点组成的，所以只要找出这些物体的最大值点和最小值点，那么就可以使用这两个点表示该物体的AABB包围盒了。
       检测碰撞的时候我们只需要检测这些物体的AABB（即他们的最大值点和最小值点）是否相交，就可以判断是否碰撞了。因为AABB总是与坐标轴平行，不能在旋转物体时简单地旋转AABB，而是应该在每一帧都重新计算。如果知道每个对象的内容，这个计算就不算困难，也不会降低游戏的速度。然而，还面临着精度的问题。

        k-DOP

        DOP是Discrete orientation polyhedron的缩写，指的是离散方向多面体，是一般化的 AABB。DOP 是一个包含物体的二维空间的凸多边形或者三维空间的凸多面体，它是一组无限远的定向平面移动到与物体相交而得到，于是 DOP 就是这些平面相交平面所生成的凸多面体。三维图形中构建 DOP 的流行方法有从 6 个按照坐标轴排列的平面得到的按坐标轴排列的包围盒，以及 10 （竖直边上取斜面）、18（所有边取斜面）或者 26 个平面（所有边及定点上取斜面）得到的斜面包围盒。从 k 个平面构建的 DOP 称为 k-DOP；但是由于一些表面可能会缩减到一条边或者一个定点，所以实际的表面数目可能会少于 k。 凸包是包容物体的最小凸体。如果物体是有限个点的集合，那么凸包就是一个多面体，实际上它是包容多面体的最小立体。

Bounding Sphere 

      包围球是一个包容物体的球面。在二维图形中，这是一个圆，包围球就用圆心及半径进行表示。包围球的碰撞检测速度非常快：当两个球心距离不超过半径之和时就会相交。这样包围球就可以用于物体可以向任意方向移动的场合。

      包围球的创建有很多种,有着各自的质量和速度的权衡(人生就是一场Trade Off 啊!).最快的方式就是创建一个AABB,找到中心,然后以对角线为直径画一个球就可以了.然而这种方式找到的球并不是最合适的,一种改进的方法是还将AABB的中心当作球心,然后遍历整个模型的顶点,找到离球心最远的顶点(计算的时候用半径的平方来比较可提高运算速度),那这个球就是最合适的Bounding Sphere 了.

OBB

     方向包围盒（Oriented bounding box），简称OBB。方向包围盒类似于AABB，但是具有方向性、可以旋转，AABB不能旋转.

     碰撞判定条件:两个多边形在所有轴上的投影都发生重叠，则判定为碰撞；否则，没有发生碰撞。

       OBB这种方法是根据物体本身的几何形状来决定盒子的大小和方向，盒子无须和坐标轴垂直。这样就可以选择最合适的最紧凑的包容盒子。OBB盒子的生成比较复杂。一般是考虑物体所有的顶点在空间的分布，通过一定的算法找到最好的方向(OBB盒子的几个轴).

光线与球相交 Ray/Sphere Intersection

        空间中的一个球只需要一个点和一个半径值就可以定义了，用隐式的方法定义为：

||x-c||=r

p表示球体上面的点，只要把x=r(t)带入，求解即可得交点。具体的运算过程如下（令v=o-c）。

若根号内为负数，即相交不发生。另外，由于这里只需要取最近的交点，因此正负号只需取负号。

        对于其他的类似的二次曲面，比如圆柱，圆锥，圆环，求解的方式和圆球的类似，都很直接。首先是写出二次曲面的隐式表达式，然后将光线的表达式带入，最后求解，通过方程的根的情况来判断相交的情况。

优化

       上面的算法只是最粗暴的算法，很多情况下有些计算不是必要的，有很多优化的空间。

        首先我们计算一个向量 l = c - o，o是光线的出发点。

        第一个判断是求出l的长度，和球的半径相比，如果有 l^2<r^2 ，则光线的源头就在球体内部，光线肯定和球体相交，如最右边的图否则再进行第二次判断.

        计算 l 和 d 的点乘， s = ld ,若s<0,则说明球体在光线的后面，肯定不相交，如中间图。

        接下来还要进行一次判断，通过求解 m^2 = l^2 - s^2（Pythagorean theorem），得到球心到直线的垂直距离，若m^2>r^2, 光线不与球相交，否则光线与球相交，这种情况下再求解交点。

          交点的求解还需要一点功夫。首先计算 q^2 = r^2-m^2，这里q>=0，再计算t1=s-q,t2=s+q，带入光线的方程，得到光线和球相交远近端的位置。

伪代码

         优化了的算法将计算尽量推迟，算是Lazy Evaluation 策略，免去了很多不必要的计算。

光线与平面相交 Ray/Plane  Intersection

        平面在空间几何中可以用一个向量（法向量）和平面中的一点P0来表示。

平面就是满足下式的点集：n.（P-P0）= 0

得到：n.P=d; d=n.P0;

给定射线r(t) =  o +td,平面方程为n.p+d=0,将p(t)带入到平面方程，最后求得t：

 t = (-d-(n.p0))/(n.d)

光线与Box相交  Ray/Box Intersection

        这里的Box用OBB来代替。需要求的的结果还是t，光线运行的距离。

        这里将OBB看作是由三个夹板（slab）组成的Box， 问题就转化为求解光线和OBB的每个面的的t值的问题。对于每一组夹层，光线都可以得到两个t值，tmin和tmax，计算下面的式子：

上图表示的是二维的情况。

        接下来是见证奇迹的时刻：如果tmin<tmax，那么光线和OBB相交，反之，不相交，不相信的画看上面的图。

        伪代码如下：

ac是是OBB的中心，au，av，aw分别是三组面的法向量。

光线三角形相交  Ray/Triangle Intersection

最先想到的是 首先判断射线是否与三角形所在的平面相交，如果相交，再判断交点是否在三角形内。
判断射线是否与平面相交
判断点是否在三角形内
但是，上面的方法效率并不很高，因为需要一个额外的计算，那就是计算出三角形所在的平面，而下面要介绍的方法则可以省去这个计算。

首先要介绍的三角形的重心坐标。

在三角形情形中，重心坐标也叫面积坐标，因为 P 点关于三角形 ABC 的重心坐标和三角形 PBC, PCA 及 PAB 的（有向）面积成比例，为,则P的重心坐标就是.

三角行中的一点，隐式表达式为：

这里的u，v，(1-u-v)其实就是重心坐标。

还是和前面一样，将光线的表达式带入

写成矩阵的形式，最左边的矩阵记为M。

求解这个线性方程组，就可以得到t,u,v。记e1 =p1-p0, e2=p2-p0 , s=o-p0.由于克莱默法则得到：

由行列式的定义知：det(a,b,c)=|a,b,c|=-(axc).b=-(cxb).a.

记q = dxe，r=sxe，式子可以化为：

到这里，就可以求t，u，v了。

之所以在计算中用了很多中间量，是因为这样可以加速运算。

最后给出伪代码.

第四行求的a是M的行列式。第五行是判断行列式不能为0.

参考

包围体 - http://zh.wikipedia.org/wiki/%E5%8C%85%E5%9B%B4%E4%BD%93

码农干货系列【1】--方向包围盒(OBB)碰撞检测 - http://www.cnblogs.com/iamzhanglei/archive/2012/06/07/2539751.html

wiki重心坐标 - http://zh.wikipedia.org/wiki/%E9%87%8D%E5%BF%83%E5%9D%90%E6%A0%87

Real time rendering 3rd