2基本光线跟踪算法

《2基本光线跟踪算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2基本光线跟踪算法ERICHAINES1简介任何光线跟踪程序包的核心都是光线相交过程设置。不论何种光照模型，纹理映射，空间细分技术，反走样方案，还是其它光线跟踪算法技巧，都需要找到物体与光线的交点。一旦光线进入模拟环境，很少有各种关于光线的问题。所有需要的信息依赖于光线的目的。当一个光线从眼睛发出，对象交点必须返回最近交点和表面法向量。当光射向光源，需要知道是否交点比光源更近，如果是，则遮挡或者过滤光源。根据遮挡模式，滤波可能需要进一步的信息。对于包围盒测试，有时只需要一个简单的碰撞与否的判断。然而，更高效的光线跟踪器还将利用光线的距离。光

2、线跟踪中另一类有用的信息就是与表面参考坐标系相关的焦点位置。这类位置信息一般用于纹理映射，以找到相应点的表面属性。[7]中有关于纹理映射的较好综述。想要编写光线跟踪程序，光线/对象（相交）算法通常需要手工编写。由于过程的教育性，许多程序员并不介意。另外，随着针对不良算法的优秀数学成果也使得算法效率不断进化。本文概述基本算法，用于执行各种光线相交测试和重要数据检索。除了抽象的方程式，还通过其后的例程展示细节。主旨在于提出高效的算法。本文仅涉及通过简单数学方法可以得到的相交算法的对象。这限制了对二次曲面的讨论，但平面和球体除外。因为球体是最简单

3、常用的图元，将被首先讨论。随后讨论平面，并附带多边形相关算法。然后提出绑定盒相交算法。最后讨论二次曲面。并谈及关于反映射技术及其它主题。虽然用到的算法对其它渲染方案和交互图形进程也有用，比如hit-testing，但描述的重点在于光线跟踪的研究。Raytracingshadowsoftransmitters,CSG树，以及一些其他的应用都需要找到光线的所有交点。算法的扩展在文中直接说明，因此常识将不被讨论。另一个没被提及的光线跟踪子集是有限长度光线跟踪，用于动态测试，比如阴影测试中，光线的长度不能超过到达光源的距离。1.1符号以下约定将被使

4、用：*乘法abs(y)绝对值·点乘Accros(y)反余弦差乘XmodyX/y取余相等Sin(y)正弦加减Sqrt(y)平方根V矢量3.1415926M矩阵所有的角度都以弧度计算。大写字母一般表示参数，小写字母则表示值。例如：是一个带下标的标量=[1248]，是一个带下标的四维向量是一个带下标的矩阵2光线/球体相交及映射球体是光线跟踪中最常用到的图元。在测试与光线相交时的易用性使它成为一个有用的包围盒。因此，对其进行了深入的研究。首先得到直接的代数解，然后检查问题的特殊情况，得到更为有效的几何结论。分析结果的比较显示了两种算法深层次的等价性

5、。对一个光线跟踪中普通故障的研究得出一些结论。球体最普通的反向映射算法作为这一章的结束。2.1球体交点的代数结论定义一个光线：Where（i.e.noamalized）定义一个光线：直线上点的设置wheret>0(A1)当t<0时，直线上的点在光源后面。“精度问题”章节解释了为什么当t=0时的点不包含在光线中。注意，光线的方向在这些计算中不必归一化。但是推荐归一化，否则t将代表方向向量中长度专业名词中的距离。在相交测试前将光线方向向量归一化可确保t在世界坐标中与到光源的距离相等。等式（1）是参数式或显式的光线方程。这意味着光线上所有的点可以

6、通过变换t的值得到。球的定义如下：（A2）。球表面用一个隐式方程表达。以这种方式，球面上的点不能直接得到。每个点能够通过隐式方程检验；如果满足方程条件，点就在球面。为了解决相交问题，光线方程被代入球面方程以得到t。光线方程（A1）用含t的方程组表示一个点：（A3）将方程组代入球面方程变量，我们得到：（A4）依据t，方程简化成：（A5）其中系数A永远等于1，因为光线的方向向量已经归一化。在球面方程中，被事先计算。当A=1时，这是一个二次方程，t的解是：（A6）当判别式为负时，光线与球体不想交。更精确的公式可以得到和，见5.5[11].由于t>

7、0是光线定义的一部分，根和被检验。较小的正实根是光线上距离最近的交点。如果没有这样的跟，光线与球面不交。通过计算，一些计算能够避免，检测它是否大于0，如果否，则计算。一旦找到距离t，实际的交点是：（A7）球面单位法向量简化为：（A8）如果光线起源于球体内部（因此交于内壁），将是负值，因此它反向指向光源。预先将乘以是合理的，因为除法比乘法更容易出错。总结算法步骤如下：Step1：计算二次方程系数A,B,CStep2：计算判别式Step3：计算并比较Step4：可能计算并比较Step5：交点计算Step6：交点法向量计算假设最多的预算常量（比如

8、）和中间结果，每步的计算量如下：Step1：8次加或代入7次乘Step2：1次代入，2次乘，1次比较Step3：1次代入，1次乘，1次比较，1次平方根Step4：1次代入，1次乘