《真实感图形学》PPT课件.ppt

第4章真实感图形学,真实感图形学研究什么？早期，计算机的速度，使人们满足于线框图 1967年，Wylie开始了用计算机生成真实感 图形的探索。21世纪，图形无所不在！,内容,颜色视觉简单光照明模型局部光照明模型光透射模型纹理及纹理映射整体光照明模型实时真实感图形学技术,41颜色视觉,分析以下的基本现象：为什么计算R、G、B三个分量就可以使人有颜色的视觉感觉？,基本概念,颜色是外来的光刺激作用于人的视觉器官而产生的主观感觉，影响的因素有：物体本身光源周围环境观察者的视觉系统,颜色的特性,颜色的三个视觉特性(心理学度量）色调(Hue)一种颜色区别于其他颜色的 因素，如：红、绿、蓝饱和度(Saturation)颜色的纯度亮度(Lightness)光给人的刺激的强度,对应的颜色物理特性主波长（Dominant Wavelength)产生颜色光的波长，对应于视觉感知的色调纯度(Purity)对应于饱和度明度(Luminance)对应于光的亮度,颜色纺锤体,颜色三特性的空间表示垂直轴线表示白黑亮度变化水平圆周上的不同角度点代表了不同色调的颜色从圆心向圆周过渡表示同一色调下饱和度的提高平面圆形上的色调和饱和度不同，而亮度相同,光的物理知识,光是人的视觉系统能够感知到的电磁波波长在400nm到700nm之间(1nm=10-9m)光可以由它的光谱能量分布 来表示各种波长的能量大致相等，为白光,各波长的能量分布不均匀，为彩色光包含一种波长的能量，其他波长都为零，是单色光,光谱能量分布定义颜色十分麻烦光谱与颜色的对应关系是多对一两种光的光谱分布不同而颜色相同的现象称为“异谱同色”必须采用其他的定义颜色的方法，使光本身与颜色一一对应,三色学说,颜色视觉及真实感图形学的生理基础，颜色科学中最基本、最重要的理论颜色具有恒常性，颜色之间的对比效应能使人区分不同颜色颜色具有混合性，牛顿在十七世纪后期用棱镜把太阳光分散成光谱上的颜色光带，证明白光由很多颜色光混合而成,十九世纪初Yaung提出某种波长的光可以通过三种不同波长的光混合而复现出来的假说红（R）、绿（G）、蓝（B）三原色把三种原色按照不同的比例混合就能准确的复现其他任何波长的光三原色等量混合产生白光 Maxwell用旋转圆盘证实了Yaung 假设。,1862年，Helmhotz在上面的基础上提出颜色视觉机制学说，即三色学说，也称为三刺激理论用三种原色能够产生各种颜色的三色原理是当今颜色科学中最重要的原理和学说,近代三色学说视网膜中存在着三种椎体细胞，对光刺激的兴奋程度不同，分别感受红、绿、蓝光。作用与颜色混合相同黄光刺激眼睛的例子三色学说是真实感图形学中RGB颜色模型提出的理论基础,CIE色度图,三色学说原理说明任何一种颜色可以用红、绿、蓝三原色按照不同比例混合来得到。还有如何使三原色按某唯一比例混合复现给定颜色的问题。颜色匹配混合光与给定光的颜色相同CIE国际照明委员会选取的标准红、绿、蓝三种光(700,546,435.8),CIE-RGB系统,光的颜色匹配式子：权值r、g、b为颜色匹配中所需要的R、G、B三色光的相对量1931年，CIE给出等能标准三原色匹配任意颜色的光谱三刺激值曲线,CIE-XYZ系统,CIE-RGB曲线一部分三刺激值是负数，表明只能在给定光上叠加曲线中负值对应的原色，去匹配另两种原色的混合计算不便，不易理解1931年CIE-XYZ系统，利用三种假想的标准原色X、Y、Z，使颜色匹配三刺激值都是正值：任何颜色都能由标准三原色混合匹配（三刺激值是正的）,色度图,复现颜色的三原色比例值是否唯一？三刺激空间用三原色的单位向量定义三维颜色空间颜色刺激表示为三刺激空间中以原点为起点的向量，向量的方向代表颜色,三刺激空间色度平面色度图,在三刺激空间上取通过（R）、（G）、（B）坐标轴单位向量的截面，截面的方程为（R）（G）（B）1。该截面与三个坐标平面的交线构成一个等边三角形，称为色度图颜色刺激向量与色度图有且仅有唯一交点，色度图可以唯一的表示三刺激空间中的所有颜色值,色度图上每一个点代表不同的颜色，对于三刺激空间中坐标为X、Y、Z的颜色刺激向量Q，它与色度图交点的坐标（x，y，z）即三刺激值也被称为色度值,CIE色度图,CIE色度图色度图投影到XY平面上马蹄形区域的边界和内部代表了所有可见光的色度值边界弯曲部分代表了光谱在某种纯度为百分之百的色光色度图与三刺激值是描述颜色的标准精确方法，应用较复杂,CIE色度图Z=1-X-Y二维表示,常用颜色模型,颜色模型是指某个三维颜色空间中的一个可见光子集，包含某个颜色域的所有颜色颜色模型的用途是在某个颜色域内方便地指定颜色,RGB颜色模型,通常使用于彩色光栅图形显示设备中真实感图形学中的主要的颜色模型采用三维直角坐标系RGB立方体,红、绿、蓝原色混合在一起可以产生复合色三原色混合效果,CMY颜色模型,以红、绿、蓝的补色青、品红、黄为原色构成的颜色模型常用于从白光中滤去某种颜色，又被称为减性原色系统，在白色中减去某种颜色来定义一种颜色用于印刷行业中,印刷硬拷贝设备的颜色处理在白纸面上涂黄色和品红色，纸面上将呈现红色白光被吸收了蓝光和绿光，只能反射红光RGB颜色模型与CMY颜色模型都是面向硬件模型,HSV颜色模型,HSV颜色模型是面向用户的对应圆柱坐标系的圆锥形子集圆锥的顶面对应于V=1色彩H由绕V轴的旋转角给定饱和度S取值从0到1，由圆心向圆周过渡,画家配色方法,HSV模型对应画家的配色的方法在一种纯色中加入白色以改变色浓，加入黑色以改变色深。同时加入不同比例的白色，黑色即可得到不同色调的颜色,RGB模型与HSV模型联系,RGB立方体从白色顶点沿着主对角线向原点方向投影，可以得到一个正六边形，该六边形是HSV圆锥顶面的一个真子集RGB空间的主对角线，对应于HSV空间的V轴,42简单光照明模型,模拟物体表面的光照明物理现象的数学模型光照明模型简单光照明模型只考虑光源对物体的直接光照,早期发展,1967年，Wylie等人第一次在显示物体时加进光照效果，认为光强与距离成反比。1970年，Bouknight提出第一个光反射模型：Lambert漫反射环境光1971年，Gouraud提出漫反射模型加插值的思想1975年，Phong提出图形学中第一个有影响的光照明模型,相关物理知识,光的传播反射定律：入射角等于反射角，而且反射光线、入射光线与法向量在同一平面上,折射定律,折射定律：折射线在入射线与法线构成的平面上，折射角与入射角满足,能量关系,在光的反射和折射现象中的能量分布：下标为i,d,s,t,v的能量项分别表示为入射光强，漫反射光强，镜面反射光强，透射光强，吸收光强能量是守恒的,光的度量,立体角：面元ds向点光源P所张的立体角为点发光强度单位时间内通过面元ds的光能量为光通量dF点发光强度为某个方向上单位立体角的内的光通量,Phong光照明模型,简单光照明模型模拟物体表面对光的反射作用光源为点光源反射作用分为镜面反射(Specular Reflection)漫反射(Diffuse Reflection)物体间作用用环境光(Ambient Light)表示,Phong模型几何,Phong模型的表示,理想漫反射漫反射光均匀向各方向传播，与视点无关由Lambert余弦定律，漫反射光强为 是与物体有关的漫反射系数，漫反射系数 有三个分量，分别代表RGB三原色的漫反射系数，通过调整它们来设定物体的颜色,镜面反射光,对一般的光滑表面，反射光集中在一个范围内，且由反射定律决定的反射方向光强最大镜面反射光强可表示为 是与物体有关的镜面反射系数，n为反射指数，反映物体表面的光泽程度，数目越大物体表面越光滑,反射方向计算镜面反射光将会在反射方向附近形成很亮的光斑，称为高光现象镜面反射光产生的高光区域只反映光源的颜色镜面反射系数 是一个与物体的颜色无关的参数,环境光,环境光是指光源间接对物体的影响光在物体和环境之间多次反射，最终达到平衡同一环境下的环境光光强分布均匀近似表示：为物体对环境光的反射系数,Phong光照明模型,Phong光照明模型的综合表述：由物体表面上一点P反射到视点的光强I为环境光的反射光强、理想漫反射光强、和镜面反射光 的总和。,Phong模型的实现,对物体表面上的每个点P，均需计算光线的反射方向。为了减少计算量，假设：光源在无穷远处，L为常向量视点在无穷远处，V为常向量（HN）近似（RV），H为L与V的平分向量对所有的点总共只需计算一次H的值，节省了计算时间,Phong光照明模型的RGB颜色模型形式:,Phong光照明模型的不足,Phong光照明模型是真实感图形学中提出的第一个有影响的光照明模型经验模型，Phong模型存在不足：显示出的物体象塑料，无质感变化没有考虑物体间相互反射光镜面反射颜色与材质无关镜面反射大入射角失真现象,Phong模型示例_1,理想漫反射,=,Phong模型示例_2,增量式光照明模型,Phong模型光强计算公式是物体表面法向量的函数多边形内部的象素颜色相同不同法向的多边形邻接处有光强突变及马赫带效应保证多边形之间的颜色光滑过渡增量式光照明模型,基本思想,在每个多边形顶点处计算光照明强度或参数，然后在各个多边形内部进行双线性插值，得到多边形光滑均匀颜色分布两个主要算法双线性光强插值、Gouraud明暗处理双线性法向插值、Phong明暗处理,Gouraud双线性光强插值,Gouraud于1971年提出，又被称为Gouraud明暗处理计算多边形各顶点的光强，再用双线性插值，求出多边形内部各点的光强,算法描述,算法步骤的基本描述：计算多边形顶点的平均法向用简单光照明模型计算顶点的平均光强插值计算离散多边形边上的各点光强插值计算多边形内域中各点的光强。,与某个顶点相邻的所有多边形的法向平均值近似作为该顶点的近似法向量顶点A相邻的多边形有k个，它的法向量计算为：计算出的平均法向一般与该多边形物体近似曲面的切平面比较接近,顶点法向计算,顶点平均光强计算,用Phong光照明模型及平均法向量计算在顶点A处的光强Gouraud提出明暗处理方法时，Phong模型还没有出现，采用：,光强插值,双线性光强插值由顶点的光强插值计算各边的光强，然后由各边的光强插值计算出多边形内部点的光强,增量算法,扫描线由j变成j+1,新扫描线上边点光强：扫描线内部，横坐标由i增为i+1，扫描线上象素点的光强：,Phong双线性法向插值,双线性光强插值解决了相邻多边形之间的颜色突变问题，镜面反射效果不太理想，相邻多边形的边界处的马赫带效应不能完全消除改进Phong提出双线性法向插值，以时间为代价，引入镜面反射，解决高光问题,算法特点,保留双线性插值，对多边形边上的点和内域各点，采用增量法。对顶点的法向量进行插值，而原顶点的法向量，仍用相邻多边形的法向作平均由插值得到法向，来计算多边形每个象素的光强度假定光源与视点均在无穷远处，光强只是法向量的函数。,法向插值方法,方法与光强插值类似，其中的光强项用法向量项来代替。基本公式：增量插值计算也类似，用法向代替光强,增量式光照明模型评价,双线性光强插值能有效的显示漫反射曲面，计算量小双线性法向插值可以产生正确的高光区域，但是计算量要大的多增量式光照明模型的不足物体边缘轮廓是折线段而非光滑曲线等间距扫描线会产生不均匀效果插值结果决定于插值方向,增量式模型示例,牛的三角网格模型 用简单光照明模型显示 用增量式光照明模型显示,阴影的生成,点光源产生的阴影。光源作为观察点，用传统隐藏面消除算法可求得阴影区域阴影多边形算法1978年，Atherton等人提出第一次用隐藏面消除技术来生成阴影相对光源可见的多边形被称为阴影多边形区分阴影多边形，阴影区域域减少显示光强,阴影域多面体算法光源照射不到的物体后面形成的三维多面体阴影区域为阴影域阴影域是一个以被光照面为顶面，表面的边界与光源所张的平面系列为侧面的一个半开三维区域物体的阴影域被视空间四棱椎裁剪得到的三维阴影域变成封闭多面体，为阴影域多面体包含于阴影多面体内的物体表面是阴影区域,物体与阴影多面体三维布尔交求阴影区域，涉及大量的复杂三维布尔运算，算法的计算复杂度是相当可观Crow于1977年提出基于扫描线隐藏面消除算法来生成阴影，可以有效的判定一个物体表面是否包含在阴影域多面体之内。在传统算法基础上稍加改动即可，应用广泛,其他方法,整体光照明模型如光线跟踪算法和辐射度算法都可以很好的处理阴影的生成问题，将在后面讨论,4局部光照明模型,从光电学知识和物体微平面假设出发，介绍镜面反射与物体材质有关的局部光照明模型,前 言,仅处理光源直接照射物体表面的光照明模型称为局部光照明模型可以处理物体之间光照的相互作用的模型称为整体光照明模型简单光照明模型，经验模型，不足之处镜面反射项与物体表面的材质无关本节介绍复杂、普遍的局部光照明模型,理论基础,光的电磁理论自然光反射率系数的Fresnel公式 是入射角，折射率分别为 和，那么 满足这样的一个式子：反射率与折射率有关.又由于折射率是入射光的波长的函数,是波长的函数,微平面理论,简单光照明模型假定物体表面是理想光滑的，微观情况下，物体表面粗糙不平局部光照明模型中希望反映物体表面的粗糙程度粗糙物体表面由无数微小理想镜面组成这些平面朝向各异，随机分布对于每一个微平面，只有在它的反射方向上才有反射光，理想镜面反射,微平面示意,微平面是理想镜面，反射率可用Fresnel公式计算，而粗糙表面的反射率与表面的粗糙度有关实际物体反射率：D为微平面法向的分布函数G为由于微平面的相互遮挡或屏蔽而使光产生的衰减因子,反射率的计算,微平面法向分布函数,Torrance和Sparrow采用Gauss分布函数模拟法向分布：k为常系数a为微平面的法向与平均法向的夹角，即m为微平面斜率的均方根，表示表面的粗糙程度,也可采用Berkmann分布函数模拟微平面的法向分布：微平面法向的分布函数D表示微平面的法向与平均法向的夹角为 的微平面占整个微平面的比例；m越小,表面越光滑在简单光照明模型中，也可看作一种微平面法向分布函数,衰减因子,衰减因子G在局部光照明模型中也可以反映物体表面的粗糙程度衰减因子是由于微平面的相互遮挡或屏蔽而产生的微平面相互遮挡的光衰减因子G，有三种情况：,光路没有遮挡，G1,部分反射光被遮挡,部分入射光被遮挡,实际的应用中，把上述三种情况衰减因子G的最小值作为该微平面的衰减因子,局部光照明模型,Cook和Torrance于1981年提出 表示物体对入射光的反射率系数反射光的光强单位时间内单位面积上的入射光能量,入射光能量,可用入射光的光强 和单位面积向光源所张的立体角 表示为:于是有反射光光强：,反射率系数可表示为漫反射率与镜面反射率的代数和 漫反射与镜面反射系数物体表面的漫反射率 受入射光波长的影响；物体表面的镜面反射率,局部光照明模型表示 物体表面反射光强 表示环境光的影响最后一项是考虑了物体表面性质后的反射光强度量，是该局部光照明模型的复杂性与普遍性所在,简单与局部模型比较,简单光照明模型(Phong)局部光照明模型,局部模型的优点,相对于简单光照明模型而言基于入射光能量导出的光辐射模型反映表面的粗糙度对反射光强的影响高光颜色与材料的物理性质有关改进入射角很大时的失真现象考虑了物体材质的影响，可以模拟磨光的金属光泽,44纹理及纹理映射,解决计算机生成真实感图象缺乏现实物体表面细节的问题,纹理的概述,用简单光照明模型生成真实感图象，由于表面过于光滑单调，反而显得不真实现实物体表面有各种表面细节纹理木材表面的木纹建筑物墙壁上的装饰图案桔子皮表面的皱纹,示例纹理,模型,映射,纹理,纹理是物体表面的细小结构纹理类型颜色纹理，二维纹理，物体表面花纹、图案三维纹理，木材纹理几何纹理，基于物体表面的微观几何形状法向扰动,纹理映射,纹理映射是把纹理图象值映射到三维物体的表面的技术纹理映射的问题改变物体的属性，可以产生纹理的效果，对简单光照明模型而言改变漫反射系数来改变物体的颜色改变物体表面的法向量,纹理定义方法：图象纹理：将二维纹理图案映射到三维物体表面，绘制物体表面上一点时，采用相应的纹理图案中相应点的颜色值。函数纹理：用数学函数定义简单的二维纹理图案，如方格地毯。或用数学函数定义随机高度场，生成表面粗糙纹理即几何纹理进行纹理映射建立纹理与三维物体之间的对应关系扰动法向量,原始模型,二维纹理,几何纹理,综合,三维纹理,纹理空间,纹理定义在单位正方形区域 之上，称为纹理空间纹理函数是定义在此空间上的函数纹理空间也可用其他方法定义用参数曲面的参数域作为纹理空间 2D用辅助平面、圆柱、球定义纹理空间 2D用三维直角坐标作为纹理空间 3D,二维纹理域的映射,纹理映射中最常见的纹理一个二维纹理的函数表示 纹理图象,映射方法,建立物体空间坐标(x，y，z)和纹理空间坐标(u，v)之间的对应关系对物体表面进行参数化，反求出物体表面的参数后，根据(u，v)得到该处的纹理值，并用此值取代光照明模型中的相应项，实现纹理映射,圆柱面映射圆柱面的参数方程圆柱面上一点(x，y，z)的参数即纹理坐标,球面映射球面参数方程球面上一点(x，y，z)的参数即纹理坐标,映射方式,三维纹理域的映射,二维纹理域，三维图形场景物体，二维纹理映射是一种非线性映射纹理变形不能保证纹理连续性三维物体每一个点(x,y,z)均有一个纹理值t(x,y,z)，那么物体空间就可以映射到一个三维纹理空间上了三维纹理域映射,三维纹理映射,纹理空间定义在三维空间上，与物体空间是同维的把场景中的物体变换到纹理空间的局部坐标系中去通过物体空间坐标(x,y,z)来计算纹理坐标(u,v,w),几何纹理,几何纹理方法对物体表面几何性质作微小扰动，产生凹凸不平的细节效果，给物体表面图象加上一个粗糙的外观物体表面上的每一个点P(u,v)，都沿该点处的法向量方向位移F(u,v)个单位长度，新表面位置：,通过对两个偏导数求叉积得到F相对很小，忽略不计，有,新表面法向量计算,几何纹理实现,扰动后的法向量单位化，用于计算曲面的明暗度，产生凹凸不平的几何纹理F的偏导数的计算，可以用中心差分实现几何纹理函数定义可以用统一的图案纹理记录图案中较暗的颜色对应较小F值，较亮的颜色对应较大F值，把各象素的值一个二维数组记录下来，就是几何纹理统一表示,纹理映射例子,地板与墙都是经过二维图象纹理映射后的平面,从微软考题说起,将一张图象映到一张平面上 A B,建立一个映射关系F：A B方法1：用F将A上的每个象素映射到B上。方法2：对B上的每个象素反求A上的对应象素，将其属性映射到B上。,45光透射模型,光线与透明或半透明表面相交会产生反射与折射，折射光穿过物体形成透射光。,光透射模型的研究,早期简单透射现象的模拟1980年，Whitted光透射模型，首次考虑了光线的折射现象1983年，在Whitted的基础上，Hall光透射模型，考虑了漫透射和规则透射光,透明效果的简单模拟,不考虑透明体对光的折射以及透明物体本身的厚度颜色调和法光通过物体表面不改变方向,光强计算：t是物体的透明度,在0,1之间前后两物体光强可由简单光照明模型计算可用隐藏面消除算法实现，模拟平玻璃的透明效果,Whitted光透射模型,在简单光照明模型的基础上加上透射一项，得到Whitted光透射模型 为折射方向光强，为透射系数，是01之间的常数,如果该透明体又是一个镜面反射体，加上反射光一项，得到较完整的Whitted光透射模型：为镜面反射方向的入射光强度；为镜面反射系数，为01之间的一个常数,Whitted光透射模型的折射方向和镜面反射方向都是相对于视线而言的，是使视线在折射方向和反射方向的入射光的方向，而且方向与光转播的方向相反在简单光照明模型的情况下，折射光强和镜面反射光强是折射方向上和反射方向上的环境光的光强,反射、折射方向计算,已知视线方向V，求其反射方向S与折射方向T光学几何原理视线V的反射方向SN是表面的法向方向,折射方向,V,N,T均为单位向量 是视点所在空间的介质折射率，为物体的折射率折射定律：Whitted：视线V的折射方向T其中，,Heckbert的折射方向计算方法更简单其中计算出的结果T为单位向量,Hall光透射模型,在Whitted光透射模型基础上推广而来可以处理规则透射高光，以及理想的漫透射理想漫透射透明体的粗糙表面对透射光的作用表现为漫透射，透射光的光强在各个方向均相等 为物体的漫透射系数,规则透射高光半透明的物体，视点在透射方向附近也能见到部分透射光。在折射方向周围形成高光域高光光强计算 为物体的透明系数，n为反映物体表面光泽的常数,减少计算量的假设光源在无穷远处，L方向为常量视点在无穷远处，V方向为常量用 代替 为虚拟理想透射面法向该法向使视线为光线的折射方向,使用Hall模型,注意点视点与光源透明体两侧，才能透过透明体看到透射高光不考虑光线射入透明体时的折射折射的全反射临界角现象：光线从高密介质射向低密介质、入射角大于临界角时，不再发生折射，只有内部反射临界角：,的求解,为当视线为光线折射方向时的面法向,简化、单位化：符号由折射率确定 时，取正号，否则取负号,简单光反射透射模型,综合简单光照明模型，Whitted光透射模型和Hall光透射模型：是本章前面几节的总结,46整体光照明模型,模拟复杂逼真的光照明现象在本章中主要介绍光线跟踪算法,光线跟踪算法研究,真实感图形学中的主要算法之一1968年Apple A给出光线跟踪算法的描述1979年Kay和Greenberg的研究考虑了光的折射1980年Whitted提出了第一个整体光照明Whitted模型，并给出一般性光线跟踪算法的范例,光线跟踪的基本原理,光线在物体之间的传播方式由光源发出的光到达物体表面后，产生反射和折射。由光源发出的光称为直接光，物体对直接光的反射或折射称为直接反射和直接折射，相对的，把物体表面间对光的反射和折射称为间接光，间接反射，间接折射光线跟踪算法基础,最基本的光线跟踪算法是跟踪镜面反射和折射。从光源发出的光遇到物体的表面，发生反射和折射，光就改变方向，沿着反射方向和折射方向继续前进，直到遇到新的物体光源发出光线，经反射与折射，只有很少部分可以进入人的眼睛实际光线跟踪方向与光传播的方向相反,视线跟踪-由视点与象素(x，y)发出一根射线，与第一个物体相交后，在其反射与折射方向上进行跟踪,四种光线定义,在光线跟踪算法中，有如下的四种光线视线是由视点与象素(x，y)发出的射线阴影测试线是物体表面上点与光源的连线反射光线，视线反射方向光线折射光线，视线折射方向光线,光强计算,光线V与物体表面交与点P时，光在点P对光线V方向的贡献分为三部分由光源产生的直接的光线照射光强，是交点出处的局部光强,反射方向上由其他物体引起的间接光照光强，由 计算，通过对反射光线的递归跟踪得到折射方向上由其他物体引起的间接光照光强，由 计算，通过对折射光线的递归跟踪得到把上述三部分光强相加，就是该条光线V在P点处的总的光强,光线跟踪算法,光线跟踪算法实际上是光照明物理过程的近似逆过程光线跟踪基本过程可以跟踪物体间的镜面反射光线和规则透射，模拟了理想表面的光的传播,终止条件,实际的算法进行过程中，不可能进行无穷的光线跟踪算法应用意义上的终止条件该光线未碰到任何物体该光线碰到了背景光线在经过许多次反射和折射以后，就会产生衰减，光线对于视点的光强贡献很小光线反射或折射次数即跟踪深度大于一定值,算法伪码表示,从视点出发，对于视屏上的每一个象素点，从视点作一条到该象素点的射线，调用下面的算法函数就可以确定这个象素点的颜色RayTracing(start,direction,weight,color)if(weight MinWeight)color=black;,else计算光线与所有物体的交点中离start最近的点；if(没有交点)color=black;else=在交点处用局部光照模型计算出的光强；计算反射方向 R；RayTracing(最近的交点,R,weight*,);计算折射方向 T；RayTracing(最近的交点,T,weight*,);color=+;,光线与物体求交,对于反射光线与折射光线的方向计算问题Whitted光透射模型中的计算方法光线跟踪算法中需要用到大量的求交运算，因而求交运算的效率对于整个算法的效率影响很大光线与物体的求交时光线跟踪算法的核心,光线与球的求交,球是光线跟踪算法中最常用的体素很容易进行光线与球的相交判断，球又常常用来作为复杂物体的包围盒 为光线的起点坐标，为光线的方向，已经单位化。为球心坐标，R为球的半径求交前提条件,代数解法,由起点发出的光线参数方程球面的隐式方程：代入合并有：,解方程有，光线与球无交，光线与球相切，t=B/2，光线与球有两个交点t0，交点无效t代入光线参数方程，可求得交点坐标,交点的坐标交点处的法向量代数法求交点和法向量总共需要17次加减运算、17次乘法运算、1次开方运算和3次比较操作,几何解法,几何法求交示意,基本步骤,计算光线起点到球心的距离平方 光线的起点在球内，光线与球有且仅有一个交点 光线的起点在球外，光线与球有两个交点或一个切点或没有交点,计算光线起点到光线离球心最近点A距离当光线的起点在球外，若，则球在光线的背面，光线与球无交点,计算半弦长的平方，来判定交点的个数，光线与球无交，光线与球相切，光线与球有两个交点,计算光线起点到光线与球交点的距离来计算交点的位置t代入光线的参数方程，可以得到交点的位置,交点的坐标交点处的球面法向几何法求交点和法向总共需要16次加减运算、13次乘法运算、1次开方运算和3次比较操作比代数法少1次加减运算和4次乘法运算,光线与多边形求交,光线与多边形求交分为两步计算多边形所在的平面与光线的交点判断所得的交点是否在多边形内部直线平面求交方法参见前面的章节,光线与二次曲面求交,光线与一般表示形式的二次曲面的求交方法二次曲面方程的一般形式表示矩阵形式,把光线的参数方程代入二次曲面的一般形式有解出t，有,t为实数，将t代入光线参数方程可得交点坐标交点处的法向量,光线跟踪算法的加速,基本的光线跟踪算法，每一条射线都要和所有的物体求交，处理地效率很低光线跟踪加速技术是实现光线跟踪算法的重要组成部分包括：提高求交速度、减少求交次数、减少光线条数、采用广义光线和采用并行算法等,自适应深度控制,对复杂的场景，没有必要跟踪光线到很深的深度，应根据光线所穿过的区域的性质来改变跟踪深度，来自适应的控制深度前面给出的光线跟踪算法的源代码就是可以做到自适应的控制深度的。,包围盒及层次结构,包围盒技术是加速光线跟踪的基本方法之一，由Clark于1976年提出1980年，Rubin和Whitted将它引进到光线跟踪算法之中，加速光线与景物的求交测试,基本思想,用一些形状简单的包围盒将复杂景物包围起来，求交的光线首先跟包围盒进行求交测试，若相交，则光线再与景物求交，否则光线与景物必无交利用形状简单的包围盒与光线求交的速度较快来提高算法的效率,层次结构,包围盒技术的一个重要改进是引进层次结构根据景物的分布情况，将相距较近的景物组成一组局部场景，相邻各组又组成更大的组整个景物空间组织成树状的层次结构,求交测试方法测试光线首先进入该层次的根节点，并从根节点开始，从上向下与各相关节点的包围盒进行求交测试。若一节点的包围盒与光线有交，则光线将递归地与其子节点进行求交测试，否则，该节点的所有景物均与光线无交，该节点的子树无需作求交测试,平行平面层次包围盒技术,1986年，Kay和Kajiya提出通常采用的长方体具有包裹景物不紧的特点根据景物的实际形状选取n组不同方向的平行平面包裹一个景物或一组景物来作为层次包围盒,三维DDA算法,光线跟踪算法效率不高的主要要原因是光线求交的盲目性将景物空间剖分为网格，利用空间连惯性，加速光线跟踪三维DDA算法1986年，Fujimoto等提出一个基于空间均匀网格剖分技术的快速光线跟踪算法,景物空间均匀分割成为一系列均匀的3维网格，建立辅助数据结构SEADS 确定后的SEADS结构中每一个网格可用三元组(i，j，k)精确定位，均设立其所含景物面片的指针光线跟踪的光线只须依次与其所经过的空间网格中所含景物面片进行求交测试,将直线光栅化的DDA算法推广到三维，来加速光线跟踪，称为光线的三维网格跨越算法光线的方向向量，主轴方向就是。算法先将光线垂直投影到交于主轴的两个坐标平面上，然后对两投影线分别执行二维DDA算法算法广泛的应用于各种商业动画软件中,空间八叉树剖分技术,空间非均匀网格剖分算法将含有整个场景的空间立方体按三个方向中剖面分割成八个子立方体网格，组织成一棵八叉树，若某一子立方体网格中所含景物面片数大于给定的阈值，则为该子立方体作进一步的剖分，直到面片数目小于阈值利用空间连贯性加速光线跟踪,八叉树的最大深度表示空间分割所达到的层次，称为空间分辨率八叉树的深度为N，八叉树终结节点的编码,i在0.N之间，F为异于0，17的符号由八叉树结点编码方式很容易找到空间任一点所在的空间网格单元,八叉树剖分性质,为一空间点，坐标为整数，其二进制表示为：，性质A:P所在单位立方体网格编码为,性质B,P位于一编码 为的空间网格内，则该空间网格的前左下角坐标为：其中0的个数都为Ni个,光线跟踪过程,先利用性质A求光线起点 所在单位立方体网格的八叉树编码Q位于立方体边界上的起点要根据光线前进方向R判别光线是否已射出场景。若光线已射出场景，则算法结束Q的空间线性八叉树结点表查找结果查找是否成功的布尔量T未获匹配位数B,设Q为，那么在八叉树中含结点 时，T取真值未获匹配位数B定义为八叉树终结点表中与Q获得最大程度匹配结点其编码尾部不匹配的位数。上面的B为NiT决定当前立方体是否包含景物面片，而Q和B确定当前立方体的空间位置和大小,T取真值，用光线和该立方体中所含三角形面片求交，若有交，则返回最近交点，算法结束，否则取T为假，继续向前搜索T为假的两种情况查找结果使T取假，包含起点且不包含任何景物面片的最大空间网格为，其中F的个数为B-1求交失败T为假，应跨过当前立方体网格,新的网格前左下角坐标由性质B确定跨越一空间网格后，先求出当前空间网格上的出口点坐标，重置光线起点光线和六个面求交预先计算光线在各坐标平面上投影线的截距和斜率，快速求解以新出发点重复跟踪过程，直至光线射出场景或求到交点为止,