光线跟踪算法思想
一、概述
本试验完成了基本光线跟踪、高级光线跟踪（反射、折射、透明、阴影）、光线跟踪加速算法等三个与光线跟踪有关的内容。
二、算法简述
1．面片求交
面片求交采用了先求交后判断的方法。
现将光线的方程代入平面方程中求出交点。
然后将该面片与交点都投影到同一个平面中如XOY平面。
投影时需要判断投影结果是否会退化为一条直线，如果发生这种情况则要投影到另一平面内。
投影后，将交点坐标代入到面的边线方程中（要保证线的方向一致），并判断符号，如果符号始终相同，则表示点在面内。
2．球体求交
球体求交也采用了将光线方程代入球体方程的方式。
如果方程无解表示没有交点。
如果有两个大于0的解，则取较小的一个；如果一个大于0，一个小于0的解，则取大于零的解。
如果没有大于零的解则仍判定为不相交。
3．光线跟踪算法
设定视点和画布
for 画布上的每一行
{
for 每一行上的每个像素
{
生成一条从视点到像素点的光线ray
LT[i,j] = ray.RayTrace(物体数组，光源数组，1)
}
}
//计算光线与物体的交点，并计算光强
V oid RayTrace(物体数组，光源数组，递归深度)
{
for 每个物体
{
计算光线与该物体的交点
if 光线起点到交点的距离小于已记录的最短距离且大于0
{
将最短距离设置为该距离
在这条光线对象中记录交点坐标，平面法向量，透明度，物体序号等
}
}
对于距光线起点最近的那个点，执行
ComputeIntensity（物体数组，交点数组序号，光源数组，递归深度）
}
V oid ComputeIntensity(物体数组，交点数组序号，光源数组，递归深度)
{
给物体加上环境光强
for (每个光源)
{
生成一条从光源指向交点的光线
判断该光线是否与其他不透明的物体相交
if （不相交）
将该光线光强乘以满反射系数和镜面反射系数加到被跟踪光线的光强中
}
if （递归深度< 设定深度）
{
if （需要反射）
{
生成一条以交点为起点的反射光线reflectRay
reflectRay.RayTrace(物体数组，光源数组，递归深度+1)
将reflectRay的光强与镜面反射系数相乘，加到原被跟踪光线光强中}
if （需要折射）
{
生成一条以交点为起点的折射光线refractRay
refractRay.RayTrace(物体数组，光源数组，递归深度+1)
将refractRay的光强与透明系数相乘，加到原被跟踪光线光强中}
}
}
4．光线跟踪加速算法（层次包围球）
本作业选择了包围球而不是包围和来实现加速。
这是基于光线与包围球求交比与包围盒求交速度快的考虑。
虽然包围盒比包围球能更紧密地包围住物体，但与包围盒求交时需要处理所有可见面片并且对求出的交点还要判断是否在面片内，这样，当物体数量较少时反而起不到加速的作用。
因此我觉得包围盒更适合于规模很大的光线跟踪计算。
4.1包围球的生成
包围球的圆心坐标 X = (Xmax + Xmin)/2 Y = (Ymax + Ymin)/2 Z = (Zmax + Zmin)/2
Xmax表示物体中所有点坐标中的最大的X值，Xmin表示物体中所有点坐标中的最小的X值。
对Y，Z也是同样的含义。
包围球的半径R = Sqrt( (xl - X)^2 + (yl - Y)^2 + (zl - Z)^2 其中
xl = Max(Abs(xmax),Abs(xmin));
yl = Max(Abs(xmax), Abs(xmin));
zl = Max(Abs(xmax), Abs(xmin))
4.2包围球二叉树的建立
包围球丛的建立对效率会有较大的影响，有许多特别的用于提高包围球丛的算法。
本作业采用了一种简洁而又兼顾效率的建立方法。
对所有的物体按Y坐标的大小排序，先对每个物体计算一个包围球，然后将两个相邻的包围球放入一个更大的包围球中，如此递归地进行，直至生成一颗完整的二叉树。
4.3对光线跟踪算法的改进
层次包围球算法对光线跟踪算法的改进之处在于减少求交的次数，对于一根光线，先计算光线与根结点包围球的相交情况，如果相交则继续计算其子结点，如此递归下去，直到找到交点，将起点到交点的距离记录下来，继续搜索，直到不再有交点，返回距起点最近的交点，或判定没有交点。
5．对透明物体的一些特别处理
透明物体对于光线跟踪算法的影响在于光线可以进入物体的内部，这样，一些后向面也会变成可见面，不能简单地将后项面排除在求交范围之外。
而且，在光线穿出物体之前可能与其他的物体相交，因此也不能简单地将连算两次折射。
本作业的处理方式是给每根光线增加一个InStyleIndex属性，用来记录光线在那个物体内，-1代表在空气中。
如果碰到InStyleIndex等于物体的序号，则对这个物体才计算后向面的交点，对其他物体仍按原样处理。
6．关于计算精度问题的一些处理
由于在与球体求交的时候会用到开根这样会造成一些精度问题的操作，有时误差会对其他操作产生影响，比如在对球进行渲染时会产生“麻脸”的情况。
对这一问题本作业采用了两种处理方法：一是设置一个常量EPSILON用来表示小量，在一些地方用它代替0。
另一种方法是将对精度要求比较明确数以乘以10的N次方的形式储存。
079组李丰
2005/02/21。