3D未来争夺战 光线追踪算法浅析
光线追踪VS光栅化 谁更快速？
尽管在反射、阴影效果方面光线追踪算法有着压倒性的优势，但是光线追踪并不是完美的3D世界的解决之道。许多人游戏玩家以为，运用了光线追踪算法，就能获得类似于皮克斯动画、好莱坞大片那样的惊人效果，但事实上这样的想法是毫无道理的。
皮克斯和众多好莱坞大片，大多使用合成图片效果来构建虚拟世界。其中皮克斯使用了被称作REYES的基于光栅化原理的渲染算法。而光线追踪仅仅作为辅助渲染技术被引入到了其自家的Renderman渲染器中。一直到《Cars(汽车总动员)》这部动画，皮克斯才首次引入光线追踪算法。根据皮克斯的说法，即便是只用光线追踪算法来处理环境光吸收(ambient occlusion)等复杂计算，也让《汽车总动员》的运算量大幅增加，成本陡增不少。
在《汽车总动员》中，皮克斯使用REYES来完成大部分渲染工作，
光线追踪仅仅用于处理反射效果和环境光吸收(ambient occlusion)效果。
在光栅化算法中，终输出一个场景只要首先用像素填满3D场景中的三角形，然后再确定像素点之间的深度距离，以确定哪个像素会被显示。在这样的过程中，光栅化算法速度和复杂度只取决于场景中三角型的多少。在光线追踪算法中，渲染器首先要从观察者角度，投射出光线以确认哪个三角形距离近，然后再计算出每个三角形距离观察者(也就是显示器平面)的距离。从原理上看，光线追踪算法似乎并不因为三角形的增加而导致运算量增加和性能下降。但在实际过程中，仅仅是计算三角形是否会和光线相交就已经要把整个场景中的所有三角形计算一遍。而在光栅化算法中，所有开发者都使用BSP(Binary Space Partition)空间二叉树算法来判断哪些三角形会被显示，哪些会被丢弃。这样一来，光栅化算法就能大幅减少每个场景的三角型填充计算量，以实现比光线追踪快得多的渲染速度。
什么是BSP树
BSP树就是用来对N维空间中的元素进行排序和查找的二叉树，它被用来在空间中消除隐藏面。BSP树表示整个空间，BSP树中的任意一个结点表示一个子空间，这些结点将分成两个子空间，作为上面结点的子结点。
每个结点除了保存其两个子结点的引用以外，还可以保存一个或多个元素。上述过程是一个递归过程，直至每一子空间仅包含一个多边形为止。通过BSP树程序员可以选择性的渲染只被人们看到的多边形，而不必理会被遮挡或被覆盖的多边形。
