光线跟踪算法的研究与实现论文.doc

光线跟踪算法的研究与实现论文.doc

《光线跟踪算法的研究与实现论文.doc》由会员分享，可在线阅读，更多相关《光线跟踪算法的研究与实现论文.doc（35页珍藏版）》请在冰点文库上搜索。

毕业论文第35页

1引言

1.1课题研究的背景及意义

计算机图形学主要是研究利用计算机及其相关图形设备输入、表示、生成、存储、处理和输出图形的理论、算法、技术，以及系统的一门科学。

它可以生成现实世界中已经存在的物体图形，也可以生成虚构物体图形。

自20世纪60年代诞生以来，计算机图形学的应用就十分广泛，涉及的领域遍及科学、工业、工程、航空、航天、商业、政府部门、医学、教育和培训、艺术、广告以及娱乐行业等。

如今，计算机图形学的理论、方法和技术都已很成熟。

真实感绘制技术是当前计算机图形学研究的一个热点问题，同时也是计算机图形学的一个重要分支。

真实感绘制的目标是：

根据实际场景的情况，在计算机中制造模拟场景，如场景内物体的造型与摆放、物体的材质，以及场景内各光源的颜色和分布等，这些因素共同作用，形成一个在视觉效果上和真实场景非常相似的虚拟环境或图像，使观察者具有身临其境的感觉。

随着硬件技术和计算机图形学的高速发展，真实感图形绘制技术也取得了举世瞩目的成就，并且已广泛应用于CAD/CAM、计算机动画、虚拟现实、科学计算可视化等众多领域。

光线跟踪算法是真实感图形技术中的重要算法之一。

要在计算机中显示出具有真实性的图像，则需要在可见面判别、明暗、透明、多光源照明等多个方面进行考虑，光线跟踪算法则提供了一种实现真实感的方法。

本课题希望能通过对计算机图形学真实感绘制技术中的光线跟踪算法思想进行研究，掌握其算法核心思想，并编写一个小型演示系统来实现最基本的光线跟踪算法，以达到学习的目的

1.2国内外研究现状

目前，国外对于光线跟踪算法的研究水平、研究进度均领先于国内。

国内的研究绝大部分都是直接翻译国外的、已经写好的论文资料，自己加以改编，并没有比较高层次的创新。

目前，国内外对于光线跟踪算法的研究大致在两个方面：

一方面是针对光线跟踪算法的加速，主要集中于光线跟踪中涉及的空间求交问题。

2003年，古春生和蔡勇在《β-样条曲面的光线跟踪算法研究》中，提出了一种光线跟踪与β-样条曲面的快速求交算法[1]。

2001年，葛明和葛研军发表了《光线跟踪长方体求交高效算法》，基于Cyrus-Beck算法及长方体面上点的约束条件，提出光线跟踪中射线与长方体求交测试和运算法的高效算法，显著改善了光线跟踪条件下数控车削加工仿真图形生成速度，该算法还具有一定的通用性，适用于射线与任意凸多面体的求交测试与运算[2]。

2004年，高军风等人发表了《一个基于包围盒技术提高光线与物体求交效率的算法》，介绍了用于光线与物体求取交点的内包围盒技术，并针对这一算法仍存在大量面片需要与光线求交的不足之处提出了改进方法[3]。

另一方面是对于工业生产和科学研究中涉及到的光线跟踪算法的研究。

2006年，牛翠霞等人联合发表了《医学体绘制的一种快速光线投射算法》，针对医学体数据场的直接体绘制（DVR），讨论了基于体绘制的多种加速技术，利用格雷厄姆求凸壳算法和与平面簇求交算法对体数据场和投射光线进行裁剪，结合多边形的扫描线转换和投射光线的离散化、体素化，改进了光线投射算法[4]。

2006年，刘文杰等人发表了《光线跟踪算法在高质量三维分子模型设计的应用》，文中分析了显示分子三维结构的光线跟踪算法，并且介绍了POV-RAY开放源代码软件的用法及其脚本语言，可直接应用于分子化学领域，为工业生产带来间接的效益[5]。

如今的光线跟踪正结合到诸如物理、化学、生物等学科领域，逐渐走向了分子化、原子化模型，扩大了其应用领域。

例如，国外有人把光线跟踪和物理学中的相对论结合起来，提出了一种新的理念，国内也有相应的研究[6]；在地理学中，对于地层的绘图也可以结合光线跟踪方法。

1.3本文的研究内容

本文对光线跟踪算法的基本原理进行了研究，从最基本的计算机如何显示图像开始，逐步涉及到光线的传播原理、计算机模拟光照的数学模型、光线跟踪的原理，结合图片和一系列的伪代码，阐述了光线跟踪算法的每一个细节过程。

最后本文还在光线跟踪基本算法的基础上，结合光线跟踪理论，在C++环境下运用windowsGDI实现了一个小型算法演示系统。

该系统建立了一个空间场景，并在场景中施放若干物体，同时放置一个坐标可变动的光源，模拟光照效果，应用光线跟踪算法确定场景中物体表面所有投影像素点的光强度，然后渲染其阴影效果，达到生成真实感图形的目的。

1.4本文的内容结构

本文共分为五章：

第一章，引言部分，详细地介绍了光线跟踪算法的研究背景，以及国内外研究的现状等等。

第二章主要介绍理解光线跟踪算法所需要的基础知识，包括物理学、几何光学的基本常识，以及在计算机中如何模拟光线、光照模型等基本知识。

本章主要是为下一章系统地介绍光线跟踪算法的原理和过程打基础的。

第三章是本论文的重点章节，根据第二章的基本知识，由浅入深、系统地讲解光线跟踪算法的背景原理，以及基本光线跟踪的整个过程。

章节中运用了伪代码来帮助理解，并给出了本文对光线跟踪算法简单实现的思想，列举了两个重要类，以及一系列重要的函数以及相应的伪代码。

第四章是对光线跟踪算法的重要部分——求交计算的研究，也是本文的重点章节。

本章介绍了对几种简单的图形的求交方法，并给出求交的公式。

第五章是对全文的总结，以及提出论文的后续深层的研究方向。

2相关基础知识

2.1几何光学基础知识

在几何光学中，光的传播方向用一条几何线来表示，这条线称为光线。

几何光学是以下列三个实验定律为基础建立起来的，它是各种光学仪器设计的理论根据，借助光线的概念，几何光学基本定律可表述如下[7]：

1、光的直线传播定律：

光在均匀媒质里沿直线传播。

即在均匀媒质中，光线为一直线。

2、光的独立传播定律：

自不同方向或由不同物体发出的光线相交，对每一光线的独立传播不发生影响，即它们的传播互不干扰。

3、光的反射和折射定律：

如图2.1所示，设媒质1、2都是透明的，均匀和各向同性的，且它们的分界面是平面（如果分界面不是平面，但曲率不太大时以下结论仍适用）。

当光线由媒质1射到分界面上时，在一般情况下被分为反射光线和折射光线，入射光线与分界面的法线构成的平面称为入射面。

分界面的法线与入射光线、反射光线、折射光线所构成的角、、分别叫做入射角、反射角和折射角，实验表明：

（1）反射线和入射线都在入射面内。

（2）入射角等于反射角：

=。

（3）入射角与折射角正弦之比与入射角无关，是一个与媒质和光的波长有关的常数，即=。

其中，比例常数称为媒质2相对与媒质1的折射率。

上式也可称为斯涅耳定律。

任何媒质相对与真空的折射率称为该媒质的绝对折射率。

它等于光在真空中的速度c与光在媒质中的速度v之比，即，其中n是媒质的绝对折射率。

实验表明，两种媒质1、2的相对折射率等于他们各自的绝对折射率与之比，即：

=/，从而斯涅耳定律还可以表示为：

=。

图2.1光线的入射、反射以及折射

4、光的可逆性原理：

从几何光学的基本定律不难看出，如果光线逆着反射线方向入射，则这时的反射线将逆着原来的入射方向传播；如果光线逆着折射线方向由媒质2入射，则射入媒质1的折射光线也将逆着原来的入射线方向传播，也就是说当光线的方向返转时，光将逆着同一路径传播。

2.2光线跟踪相关基础知识

2.2.1光源

光源可以发射出数条光线。

当人们观察一个不透明而且不发光的物体时，可以从物体表面看到反射光，这是由场景中的光源和其他物体表面的反射所共同产生的。

只要一个物体周围获得光照，即使其自身不直接暴露于光源之下，物体的表面也可能是可见的。

有时候将光源称之为发光体，而反射表面（如房屋的墙壁）则称之为反射光源。

可以利用光源来表示所有发出辐射能量的物体，如太阳。

在所有的光线跟踪的场景中都是基于这样的原理，于是没有光源便不能发出光线，没有光线便就没有光线追踪！

通常一个发光物体可能既是光源又是反射体。

例如在一个塑料球内放置一个灯泡，这样在球表面上既发光也反射光，从球面发出的光还可以照亮附近其他物体。

点光源是发光体的最简单的模型，光线由光源出发，向四周发散，如图2.2所示。

本文中的光源都是有一定坐标位置和强度的点光源。

图2.2点光源

2.2.2环境光

环境光是指光源间接对物体的影响，是在物体和环境之间多次反射，最终达到平衡时的一种光。

可以近似地认为，在同一环境下，其环境光的光强分布是均匀的，即在任何一个方向上的分布都相同。

例如，透过厚厚云层的阳光就可以称为环境光。

环境光没有空间或者方向上的特征，在所有方向上和所有物体表面投射的环境光的数量是恒定不变的，这样每个物体都得到同样的光照，并且相对于该物体表面反射光也是个常数，即反射光与观察方向和物体表面的朝向无关。

然而各个物体表面上反射光强度却不一定相同，这取决于各个表面的光学属性，即反射多少入射光，吸收多少入射光。

在简单光照明模型中，用一个常数来模拟环境光，如公式2.1：

（2.1）

其中：

参数表示场景中光亮度的大小，为环境光的光亮度，为物体对环境光的漫反射系数，如图2.3所示。

图2.3具有不同环境光反射系数的两个球

2.2.3漫反射

当光源来自一个方向时，漫反射光均匀向各方向传播，与视点无关，它是由表面的粗糙不平引起的[8]，因而漫反射光的空间分布是均匀的，如图2.4所示。

图2.4光的漫反射图示

设入射光强为Ip，物体表面上点P的法向为N，从点P指向光源的向量为L，两者间的夹角为theta，由Lambert余弦定律，则漫反射光强为：

（2.2）

其中，是与物体有关的漫反射系数,0<<1。

当L、N为单位向量时，公式2.2也可用如下形式表达：

（2.3）

可以任意调整物体表面的反射属性，只须为Kd设置一个0与1之间的常数。

如果希望反射率较高，则Kd的值接近1，这样就可能得到与入射光强度接近的反射光。

若模拟一个能吸收大部分入射光的物体表面，则只须将反射率的值设为接近0。

在有多个光源的情况下，可以有如下的表示：

（2.4）

在RGB颜色模型下，漫反射系数有三个分量，即，分别代表R、G、B三原色的漫反射系数，它们是反映物体颜色的，通过调整它们，可以改变物体的颜色。

同样，我们也可以把入射光强I设为三个分量Ir、Ig、Ib，通过这些分量的值来调整光源的颜色。

2.2.4镜面反射光

对于理想镜面，反射光集中在一个方向，并遵守反射定律[9]。

如图2.5所示，对一般的光滑表面，反射光集中在一个范围内，且由反射定律决定的反射方向光强最大。

因此，对于同一点来说，从不同位置所观察到的镜面反射光强是不同的。

图2.5理想镜面反射

镜面反射光强可表示为公式2.5：

（2.5）

其中Ks是与物体有关的镜面反射系数，a为视线方向V与反射方向R的夹角，n为反射指数，反映了物体表面的光泽程度，一般为1～2000，数目越大物体表面越光滑。

镜面反射光将会在反射方向附近形成很亮的光斑，称为高光现象。

同样，将V和R都格式化为单位向量，镜面反射光强可表示为：

（2.6）

其中，R可由计算。

对多个光源的情形，镜面反射光强可表示为：

（2.7）

镜面反射光产生的高光区域只反映光源的颜色，如在红光的照射下，一个物体的高光域是红光，镜面反射系数Ks是一个与物体的颜色无关的参数。

正如前面已经提到的，在简单光照明模型中，只能通过改变物体的漫反射系数来控制物体的颜色。

2.2.5Phong光照明模型

1975年，Phong在Comm.ACM上发表论文，提出图形学中第一个有影响的光照明模型[10]。

Phong模型虽然只是一个经验模型，但是其实现的真实感已达到人们可以满意的程度。

光照到物体表面时，物体对光会发生反射、透射、吸收、衍射、折射和干涉。

简单光照明模型模拟物体表面对光的反射作用，光源被假定为点光源，反射作用被细分为镜面反射和漫反射。

简单光照明模型只考虑物体对直接光照的反射作用，而物体间的光反射作用，只用环境光来表示，Phong光照明模型就是这样的一种模型。

1、Phong光照明模型的建立：

综合上面介绍的光反射作用的各个部分，Phong光照明模型有这样的一个表述[14]：

由物体表面上一点P反射到视点的光强I为环境光的反射光强Ie、理想漫反射光强Id和镜面反射光Is的总和，即公式2.8：

（2.8）

如图2.6所示：

图2.6Phong光照明模型

2、Phong光照明模型的实现：

在用Phong模型进行真实感图形计算时，对物体表面上的每个点P，均需计算光线的反射方向R，再由V计算（R·V）。

为减少计算量[11]，可以作如下假设：

（1）光源在无穷远处。

即光线方向L为常数；

（2）视点在无穷远处，即视线方向V为常数；

（3）用（H·N）近似（R·V）。

这里H为L和V的平分向量，。

在这种简化下，由于对所有的点总共只需要计算一次H的值，节省了计算时间。

结合RGB颜色模型，Phong光照明模型最终有如下的形式：

（2.9）

Phong光照明模型是真实感图形学中提出的第一个有影响的光照明模型，生成图像的真实度已经达到可以接受的程度。

但是在实际的应用中，由于它是一个经验模型，还具有以下的一些问题：

用Phong模型显示出的物体像塑料，没有质感；环境光是常量，没有考虑物体之间相互的反射光；镜面反射的颜色是光源的颜色，与物体的材料无关；镜面反射的计算在入射角很大时会产生失真等。

图2.7展示了n取不同值时候Phong光照明模型示例。

图2.7n取不同值时候的Phong光照明模型示例

2.2.6整体光照模型

根据前面的光照模型的介绍，简单光照明模型虽然可以产生物体的真实感图像，但它们都只是处理光源直接照射物体表面的光强计算，不能很好的模拟光的折射、反射和阴影等，也不能用来表示物体间的相互光照明影响；而基于简单光照明模型的光透射模型，虽然可以模拟光的折射，但是这种折射的计算范围很小，不能很好的模拟多个透明体之间的复杂光照明现象。

对于上述的这些问题，就必须要有一个更精确的光照明模型。

整体光照明模型就是这样的一种模型[12]，它是相对于局部光照明模型而言的。

在现有的整体光照明模型中，主要有光线跟踪和辐射度两种方法，它们是当今真实感图形学中最重要的两个图形绘制技术，在CAD及图形学领域得到了广泛的应用。

1980年Whitted提出的光透射模型就是一个整体光照模型[13]，并且第一次给出光线跟踪算法的范例，实现了Whitted模型。

1983年Hall在此基础上进一步给出了Hall光透射模型，考虑了漫透射和规律透射光。

Whitted光透射模型，简单点说就是在简单光照明模型的基础上，加上透射光这一项，多考虑了一层。

以图2.8为例，从视点观察到的物体A表面的亮度来源于三方面的贡献：

（1）光源直接照射到A的表面，然后被反射到人眼中的光产生的。

（2）光源或其它物体的光经A物体折射到人眼中的光产生的。

（3）物体B的表面将光反射到物体A的表面，再经物体A的表面反射到人眼中产生的。

简单局部光照明模型仅考虑了

（1）。

本论文最后实现的光线跟踪的基本场景中的模型，就是这种整体的光照模型，但是仅仅考虑了理想状况下的反射情况。

图2.8整体光照模型

3光线跟踪算法

3.1光线跟踪算法的基本原理

上一章介绍了一些光线跟踪算法中相关联的一些基础知识，包括几何光学中的三大定律，光在传播过程中发生的漫反射，镜面反射等等，还介绍了简单光照模型和整体光照模型。

本章则在这些基础上介绍光线跟踪算法的基本原理以及光线跟踪的过程。

由光源发出的光到达物体表面后，产生反射和折射，简单光照明模型和光透射模型模拟了这两种现象。

在简单光照明模型中，反射被分为理想漫反射和镜面反射光，在简单光透射模型把透射光分为理想漫透射光和规则透射光。

由光源发出的光称为直接光，物体对直接光的反射或折射称为直接反射和直接折射，相对的，把物体表面间对光的反射和折射称为间接光，间接反射，间接折射。

这些是光线在物体之间的传播方式，是光线跟踪算法的基础。

最基本的光线跟踪算法是跟踪光线的镜面反射和折射。

从光源发出的光遇到物体的表面，发生反射和折射，光就改变方向，沿着反射方向和折射方向继续前进，直到遇到新的物体。

但是光源发出光线，经反射与折射，只有很少部分可以进入人的眼睛。

因此实际光线跟踪算法的跟踪方向与光传播的方向是相反的，是一种视线跟踪法。

由视点与象素（x，y）发出一根射线，与第一个物体相交后，在其反射与折射方向上进行跟踪。

如图3.1所示。

图3.1光线经过屏幕入射到场景中与物体相交

为了详细介绍光线跟踪算法，先给出四种射线的定义与光强的计算方法。

在光线跟踪算法中，有如下的四种光线：

视线是由视点与象素（x，y）发出的射线；阴影测试线是物体表面上点与光源的连线；以及反射光线与折射光线。

当光线V与物体表面交于点P时，点P分为三部分，把这三部分光强相加，就是该条光线V在P点处的总的光强：

由光源产生的直接的光线照射光强，是交点处局部光强，可由公式3.1计算：

（3.1）

反射方向上由其它物体引起的间接光照光强，由Is、Ks'计算，Is通过对反射光线的递归跟踪得到；折射方向上由其它物体引起的间接光照光强，由It、Kt'计算，It通过对折射光线的递归跟踪得到。

将对一个由两个透明球和一个非透明物体组成的场景进行光线跟踪。

通过这个例子，可以把光线跟踪的基本过程解释清楚。

如图3.2所示。

图3.2光线跟踪示意图

在场景中，有一个点光源L，两个透明的球体O1与O2，一个不透明的物体O3。

首先，从视点出发经过视屏一个象素点的视线E传播到达球体O1，与其交点为P1。

从P1向光源L作一条阴影测试线S1，很容易发现其间没有遮挡的物体，那么就用局部光照明模型计算光源对P1在其视线E的方向上的光强，作为该点的局部光强。

同时还要跟踪该点处反射光线R1和折射光线T1，它们也对P1点的光强有贡献。

在反射光线R1方向上，没有再与其他物体相交，那么就设该方向的光强为零，并结束这光线方向的跟踪。

然后对折射光线T1方向进行跟踪，来计算该光线的光强贡献。

折射光线T1在物体O1内部传播，与O1相交于点P2，由于该点在物体内部，假设它的局部光强为零，同时，产生了反射光线R2和折射光线T2，在反射光线R2方向，可以继续递归跟踪下去计算它的光强，在这里就不再继续下去了。

将继续对折射光线T2进行跟踪。

T2与物体O3交于点P3，作P3与光源L的阴影测试线S3，没有物体遮挡，那么计算该处的局部光强，由于该物体是非透明的，那么可以继续跟踪反射光线R3方向的光强，结合局部光强，来得到P3处的光强。

反射光线R3的跟踪与前面的过程类似，算法可以递归的进行下去。

重复上面的过程，直到光线满足跟踪终止条件。

这样就可以得到视屏上的一个象素点的光强，也就是它相应的颜色值。

上面的例子就是光线跟踪算法的基本过程，可以看出，光线跟踪算法实际上是光照明物理过程的近似逆过程，这一过程可以跟踪物体间的镜面反射光线和规则透射，模拟了理想表面的光的传播。

虽然在理想情况下，光线可以在物体之间进行无限的反射和折射，但是在实际的算法进行过程中，不可能进行无穷的光线跟踪，因而需要给出一些跟踪的终止条件。

在算法应用的意义上，可以有以下的几种终止条件：

（1）该光线未碰到任何物体。

（2）该光线碰到了背景。

（3）光线在经过许多次反射和折射以后，就会产生衰减，光线对于视点的光强贡献很小（小于某个设定值）。

（4）光线反射或折射次数即跟踪深度大于一定值。

最后用伪码的形式给出一般光线跟踪算法的源代码[5]。

光线跟踪的方向与光传播的方向相反，从视点出发，对于视屏上的每一个象素点，从视点作一条到该象素点的射线，调用该算法函数就可以确定这个象素点的颜色。

光线跟踪算法的函数名为RayTracing（），光线的起点为start，光线的方向为direction，光线的衰减权值为weight，初始值为1，算法最后返回光线方向上的颜色值color。

对于每一个象素点，第一次调用RayTracing（）时，可以设起点start为视点，而direction为视点到该象素点的射线方向。

RayTracing（start,direction,weight,color）

{

if（weight

color = black;

else

{

计算光线与所有物体的交点中离start最近的点；

if（没有交点）color=black;

else

{

Ilocal=在交点处用局部光照模型计算出的光强；

计算反射方向R；

RayTracing（最近的交点,R,weight*Wr,Ir）;

计算折射方向T；

RayTracing（最近的交点,T,weight*Wt,It）;

color=Ilocal+KsIr+KtIt;

}}}

3.2本文算法实现的思想

在VC6.0开发环境下，应用Windows基础画图编程，创建一个MFC对话框架，此框架可以控制光源在场景中的位置，还可以开始和终止光线跟踪。

首先创建一个场景，背景色为黑色。

在场景中创建若干个不透明的实体球，以及一个可变动坐标的光源了。

为了使过程更加逼真，对球体进行旋转操作。

通过双重循环扫描，再单重循环定位，对场景中的球体进行检测是否相交，并求出最近的交点。

计算该点光强度，通过计算结果，对该球体进行阴影渲染操作，使之更具有真实感。

通过循环使大量的位图每秒以一定的帧数不停地显示，最后输出显示结果，实现在单一场景中的基于简单光照模型下的光线跟踪，进而增加场景中物体的真实感，并且给人一种连续的动态的感觉。

程序设计的两个主要的类，分别是：

1、CDib：

主要的windows底层画图类。

包括内存文件分配，基本画图工具等。

2、CRayTracerDlg：

这个类是最为主要的。

包括构造场景、构造光源、构造物体，以及最后的实现光线跟踪的过程方法，并能渲染生成单一位图、连续显示等。

程序中两个最关键的函数为：

OnDemo（）和TraceScene（）。

OnDemo（）函数是整程序的入口，负责开始演示程序到结束。

以下是OnDemo（）函数的伪代码。

OnDemo（）

{ 定义3个球体Spheres[3]

创建开始的射线数组GenerateRayDirectionTable；

//如下列形式构造3个球，其中Center为中心，Radius为半径，Color为颜色。

Spheres[1/2/3].Center.X[/Y/Z]=0;

Spheres[1/2/3].Radius=0;

Spheres[1/2/3].Color.R[/G/B]=0;

//构造视角，相当与人的眼睛的位置坐标

视角.X[Y/Z]=0;

//光线位置

光线.X[Y/Z]=100;

定义消息msg;

while（图象显示）

{ //旋转球体

for（球体个数）

{ 旋转函数（旋转参数）; }

光线跟踪函数（球,光线位置）; //场景跟踪函数

画图函数（…）;

while（当有一条开始消息）

{ if（中断信息）

{ 中止跟踪; }

}

渲染函数（）;

}

}

下面这些是函数TraceScene（）的伪代码，该函数是光线跟踪算法的核心部分：

voidTraceScene（球,向量，光线位置）

{ float相交距离;

int相交点;

TraceResult跟踪结果;

for（框架纵坐标Y的范围）

{ for（框架横坐标X的范围）

{ //设置一个不可能的大值

相交距离=无穷远;

相交点=错误位置负坐标;

//遍历所有的球寻找最近点

for（3个球）

{ //与球体相交

跟踪结果=相交的球;

if（相