计算机图形学ppt课件第七章真实感图形显.ppt

《计算机图形学ppt课件第七章真实感图形显.ppt》由会员分享，可在线阅读，更多相关《计算机图形学ppt课件第七章真实感图形显.ppt（145页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章第七章 真实感图形显示真实感图形显示n n消隐n n光照n n图案与纹理n n颜色空间消消隐n n消隐的分类n n消除隐藏线n n消除隐藏面消消隐投影变换失去了深度信息，往往导致图形的二义性要消除二义性，就必须在绘制时消除被遮挡的不可见的线或面，习惯上称作消除隐藏线和隐藏面，简称为消隐。经过消隐得到的投影图称为物体的真实图形。长方体线框投影图的二义性消消隐消隐的对象是三维物体。三维体的表示主要有边界表示和CSG表示等。消隐结果与观察物体有关，也与视点有关。线框图 消隐图 真实感图形消消隐的分的分类n按消隐对象分类n n线消隐n n消隐对象是物体上的边，消除的是物体上不可见的边。n n面消

2、隐 n n消隐对象是物体上的面，消除的是物体上不可见的面。消除消除隐藏藏线n n对造型的要求n n在在线线框框显显示模型中示模型中,要求造型系要求造型系统统中有面的信中有面的信息，最好有体的信息。息，最好有体的信息。n n坐标变换n n将将视视点点变换变换到到Z Z轴轴的正无的正无穷穷大大处处，视线视线方向方向变为变为Z Z轴轴的的负负方向。方向。n n最基本的运算n n判断面判断面对线对线的遮的遮挡挡关系关系.反复地反复地进进行行线线线线、线线面之面之间间的求交运算的求交运算 求交运算射线与直线求交运算射线与直线求交运算假定直线方程为射线方程为把射线方程代入直线方程得到 当 时,直线与射线平

3、行,若还有 ,则整条射线与直线重合。当 时，则当 时，二者交点为 ，当 时，无交点射线与线段求交问题射线与线段求交问题假定射线方程如上一样，线段的两端点为 ，则线段的方程为射线方程代入上式得到令 ，当 时，射线与线段平行。这时若还有 ，则线段与射线（或其反向延长线）重合。如果 ，则得到当 ，射线与线段有唯一交点。将 代入射线方程，或将代入线段方程求得。射线与平面求交问题射线与平面求交问题假设一空间射线起点为 ，方向为则该射线方程为又假设一任意平面，其方程为 。将射线方程代入平面方程得整理得显然，当 ，射线与平面平行。此时若还有 ，则整条射线落在平面上。除了这种情况外，射线（或其反向延长线）与平

4、面交于一点，参数为 当 时，交点在射线上，否则交点在射线得反向延长线上（不算交点）消除消除隐藏藏线n n凸多面体的隐藏线消除n n凹多面体的隐藏线消除面消面消隐n n面消隐算法的分类n n提高消隐算法效率的常见方法n n画家算法n nZ缓冲器算法(Z-Buffer)n n扫描线Z缓冲器算法n n区域子分算法n n光线投射算法面消面消隐算法的分算法的分类 第一第一类类（图图像空像空间间的消的消隐隐算法）：算法）：以窗口内的每个像以窗口内的每个像素素为处为处理理单单元；如元；如Z Zbufferbuffer、扫扫描描线线、WarnockWarnock算法算法 for(for(窗口内的每一个像素窗口

5、内的每一个像素)确定距确定距视视点最近的物体，以点最近的物体，以该该物体表面的物体表面的颜颜色来色来显显示像示像 素素 第二第二类类（物体空（物体空间间的消的消隐隐算法）：算法）：以以场场景中的物体景中的物体为为处处理理单单元；如光元；如光线线投射算法投射算法for(for(场场景中的每一个物体景中的每一个物体)将其与将其与场场景中的其它物体比景中的其它物体比较较，确定其表面的可，确定其表面的可见见部部 分；分；显显示示该该物体表面的可物体表面的可见见部分；部分；面消面消隐算法的分算法的分类n n第一类（图像空间的消隐算法）算法复杂度：假设场景中有k个物体，平均每个物体表面由h个多边形构成，显

6、示区域中有m x n个像素，算法的复杂度为：O(mnkh)n n第二类（物体空间的消隐算法）算法复杂度:假设场景中有k个物体，平均每个物体表面由h个多边形构成，显示区域中有m x n个像素，算法的复杂度为：O(kh)*(kh)提高消提高消隐算法效率的常算法效率的常见方法方法n n利用连贯性n n将透视投影转换成平行投影n n包围盒技术n n背面剔除n n空间分割技术n n物体分层表示方法方法1-1-利用利用连贯性性 相邻事物的属性之间有一定的连贯性，其属性值通常是平缓过渡的，如颜色值、空间位置关系等。连贯性有：u物体连贯性u面的连贯性u区域连贯性u扫描线的连贯性u深度连贯性方法方法1-1-利用

7、利用连贯性性u物体连贯性：如果物体A与物体B是完全相互分离的，则在消隐时，只需比较A、B两物体之间的遮挡关系就可以了，无须对它们的表面多边形逐一进行测试。例如，若A距视点较B远，则在测试B上的表面的可见性时，无须考虑A的表面。u面的连贯性：一张面内的各种属性值一般都是缓慢变化的，允许采用增量形式对其进行计算。u区域连贯性：区域指屏幕上一组相邻的像素，它们通常为同一个可见面所占据，可见性相同。区域连贯性表现在一条扫描线上即为扫描线上的每个区间内只有一个面可见。方法方法1-1-利用利用连贯性性u扫描线的连贯性：相邻两条扫描线上，可见面的分布情况相似。u深度连贯性：同一表面上的相邻部分深度是相近的，

8、而占据屏幕上同一区域的不同表面的深度不同。这样在判断表面间的遮挡关系时，只需取其上一点计算出深度值，比较该深度值即可得到结果。方法方法2-2-透透视投影投影转换成平行投影成平行投影消隐与透视关系密切,体现在：1）消隐必须在投影之前完成；2）物体之间的遮挡关系与投影中心（视点）的选取有关；3）物体之间的遮挡关系与投影方式有关方法方法3-3-包包围盒技盒技术包围盒概念：一个形体的包围盒指的是包围它的简单形体。一个好的包围盒要具有两个条件：包围和充分紧密包围着形体；对其的测试比较简单。方法方法3-3-包包围盒技盒技术应用避免盲目求交例如：两个空间多边形A、B在投影平面上的投影分别为A，B，因为A、B

9、的矩形包围盒不相交，则A、B不相交，无须进行遮挡测试。右下图：包围盒相交，投影也相交；包围盒相交，投影不相交。方法方法4-4-背面剔除背面剔除外法向：规定每个多边形的外法向都是指向物体外部的。前向面：若多边形的外法向与投影方向（观察方向）的夹角为钝角，称为前向面。后向面：若多边形的外法向与投影方向（观察方向）的夹角为锐角，称为后向面（背面）。剔除依据：背面总是被前向面所遮挡，从而不可见。方法方法4-4-背面剔除背面剔除前向面后向面多面体的隐藏线消除图中的JEAF、HCBG和DEABC所在的面均为后向面。其它为前向面。方法方法5-5-空空间分割技分割技术依据：场景中的物体，它们的投影在投影平面上

10、是否有重叠部分？（是否存在相互遮挡的可能？）对于根本不存在相互遮挡关系的物体，应避免这种不必要的测试。方法：将投影平面上的窗口分成若干小区域；为每个小区域建立相关物体表，表中物体的投影于该区域有相交部分；则在小区域中判断那个物体可见时，只要对该区域的相关物体表中的物体进行比较即可。方法方法6-6-物体分物体分层表示表示表示形式：模型变换中的树形表示方式原理：减少场景中物体的个数，从而降低算法复杂度。方法方法6-6-物体分物体分层表示表示方法：将父节点所代表的物体看成子节点所代表物体的包围盒，当两个父节点之间不存在遮挡关系时，就没有必要对两者的子节点做进一步测试。父节点之间的遮挡关系可以用它们之

11、间的包围盒进行预测试。画家算法（列表画家算法（列表优先算法）先算法）l由来：画家的作画顺序暗示出所画物体之间的相互遮挡关系l算法基本思想：1）先把屏幕置成背景色 2）先将场景中的物体按其距观察点的远近进行排序，结果放在一张线性表中；（线性表构造：距观察点远的称优先级低，放在表头；距观察点近的称优先级高，放在表尾。该表称为深度优先级表）3）然后按照从远到近（从表头到表尾）的顺序逐个绘制物体。关键：如何对场景中的物体按深度（远近）排序，建立深度优先级表？画家算法（列表画家算法（列表优先算法）先算法）l一种针对多边形的排序算法如下：Step 1:将场景中所有多边形存入一个线性表，记为L；Step 2

12、:如果L中仅有一个多边形，算法结束；否则根据每个多边形的Zmin对它们预排序。不妨假定多边形P落在表首，即Zmin(P)为最小。再记Q为L P(表中其余多边形）中任意一个；Step 3:判别P,Q之间的关系，有如下二种：（1）:对所有的Q，有Zmax(P)Zmin(Q),需进一步判别：画家算法（列表画家算法（列表优先算法）先算法）例子：A）若P,Q的投影P,Q的包围盒不相交（图a），则P,Q在表中的次序不重要，令L=L P,返回step 2;否则进行下一步。画家算法（列表画家算法（列表优先算法）先算法）B）若P的所有顶点位于Q所在平面的不可见的一侧(图b)，则P,Q关系正确，令L=L P,返回

13、step 2;否则进行下一步。画家算法（列表画家算法（列表优先算法）先算法）C）若Q的所有顶点位于P所在平面的可见的一侧(图c)，则P,Q关系正确，令L=L P,返回step 2;否则进行下一步。画家算法（列表画家算法（列表优先算法）先算法）D）对P,Q投影P,Q求交，若P,Q不相交(图d)，则P,Q在表中的次序不重要，令L=L P,返回step 2;否则在它们所相交的区域中任取一点，计算P,Q在该点的深度值，如果P的深度小，则P,Q关系正确，令L=L P,返回step 2;否则交换P,Q,返回step 3.画家算法（列表画家算法（列表优先算法）先算法）本算法不能处理的情况：多边形循环遮挡多边

14、形相互穿透解决办法：分割成两个Z-BufferZ-Buffer算法算法由来：帧缓冲器 保存各像素颜色值 Z缓冲器-保存各像素处物体深度值 Z缓冲器中的单元与帧缓冲器中的单元一一对应Z-BufferZ-Buffer算法算法算法思想：先将Z缓冲器中个单元的初始值置为最小值。当要改变某个像素的颜色值时，首先检查当前多边形的深度值是否大于该像素原来的深度值（保存在该像素所对应的Z缓冲器的单元中），如果大于，说明当前多边形更靠近观察点，用它的颜色替换像素原来的颜色；否则说明在当前像素处，当前多边形被前面所绘制的多边形遮挡了，是不可见的，像素的颜色值不改变。Z-BufferZ-Buffer算法算法-算法描

15、述算法描述 帧缓存全置为背景色深度缓存全置为最小Z值for(每一个多边形)for(该多边形所覆盖的每个象素(x,y)计算该多边形在该象素的深度值Z(x,y);if(Z(x,y)大于Z缓存在(x,y)的值)把Z(x,y)存入Z缓存中(x,y)处 把多边形在(x,y)处的颜色值存入帧缓存的(x,y)处 需要计算的像素深度值次数需要计算的像素深度值次数=多边形个数多边形个数*多边形平均占据的多边形平均占据的像素个数像素个数Z-BufferZ-Buffer算法算法Z缓冲器算法是所有图像空间算法中最简单的一种隐藏面消除算法。它在象素级上以近物取代远物，与形体在屏幕上的出现顺序无关。优点：1）简单稳定，利

16、于硬件实现 2）不需要整个场景的几何数据缺点:1）需要一个额外的Z缓冲器 2）在每个多边形占据的每个像素处都要计算深度值，计算量大 Z-BufferZ-Buffer算法算法-改改进算法算法只用一个深度缓存变量zb的改进算法。一般认为，Z-Buffer算法需要开一个与图象大小相等的缓存数组ZB，实际上，可以改进算法，只用一个深度缓存变量zb。Z-BufferZ-Buffer算法算法-改改进算法算法帧缓存全置为背景色帧缓存全置为背景色for(屏幕上的每个象素屏幕上的每个象素(i,j)深度缓存变量深度缓存变量zb置最小值置最小值MinValue for(多面体上的每个多边形多面体上的每个多边形Pk)

17、if(象素点象素点(i,j)在在pk的投影多边形之内的投影多边形之内)计算计算Pk在在(i,j)处的深度值处的深度值depth;if(depth大于大于zb)zb=depth;indexp=k;if(zb!=MinValue)在交点在交点(i,j)处用多边形处用多边形Pindexp的颜色显示的颜色显示 Z-BufferZ-Buffer算法算法-改改进算法算法关键问题：判断象素点(i,j)是否在多边形Pk的投影多边形之内计算多边形Pk在点（i，j）处的深度。设多边形Pk的平面方程为：扫描描线Z-bufferZ-buffer算法算法n n由来：Z缓冲器算法中所需要的Z缓冲器容量较大，为克服这个缺点

18、可以将整个绘图区域分割成若干个小区域，然后一个区域一个区域地显示，这样Z缓冲器的单元数只要等于一个区域内像素的个数就可以了。n n如果将小区域取成屏幕上的扫描线，就得到扫描线Z缓冲器算法。扫描描线Z-bufferZ-buffer算法算法n n算法思想:n n在在处处理当前理当前扫扫描描线时线时，开一个一，开一个一维维数数组组作作为为当当前前扫扫描描线线的的Z-bufferZ-buffer。首先。首先找出与当前找出与当前找出与当前找出与当前扫扫描描描描线线相关的多相关的多相关的多相关的多边边形，以及每个多形，以及每个多形，以及每个多形，以及每个多边边形中相关的形中相关的形中相关的形中相关的边对边

19、对。n n对对每一个每一个边对边对之之间间的小区的小区间间上的各象素，上的各象素，计计算算深度，并与深度，并与Z-bufferZ-buffer中的中的值值比比较较，找出各象素，找出各象素处处可可见见平面。平面。n n写写帧缓帧缓存。采用增量算法存。采用增量算法计计算深度。算深度。扫描描线Z-bufferZ-buffer算法算法for(v=0;vvmax;v+)for(u=0;u Z缓冲器的第u单元的值）置帧缓冲器的第(u,v)单元值为当前多边形颜色；置Z缓冲器的第u单元值为d;/处理下一条扫描线 扫描描线Z-bufferZ-buffer算法算法n n改进之一：将窗口分割成扫描线Z缓冲器的单元数

20、只要等于一条扫描线内像素的个数就可以了。扫描描线Z-bufferZ-buffer算法算法n n改进之二：采用多边形分类表、活化多边形表避免多多边形形与扫描线的盲目求交n n多边形分类表（PT）：对多边形进行分类的一维数组，长度等于绘图窗口内扫描线的数目。若一个多边形在投影平面上的投影的最小v坐标为v，则它属于第v类。扫描描线Z-bufferZ-buffer算法算法扫描描线Z-bufferZ-buffer算法算法n n活化多活化多边边形表（形表（APLAPL）：）：记录记录投影与当前投影与当前扫扫描描线线相交的多相交的多边边形。形。扫描描线Z-bufferZ-buffer算法算法-多多边形形n

21、n其中，多其中，多边边形的数据形的数据结结构如下：构如下：n na,b,c,da,b,c,d：多：多边边形所在平面方程形所在平面方程f(u,v,n)=au+bv+cn+d=0f(u,v,n)=au+bv+cn+d=0的的系数。系数。n ncolor:color:多多边边形的形的颜颜色色n nvmax:vmax:多多边边形在投影平面上的投影的最大形在投影平面上的投影的最大v v坐坐标值标值。n nPIPI：多：多边边形的序号形的序号n nnextPnextP：指向下一个多：指向下一个多边边形形结结构的指构的指针针扫描描线Z-bufferZ-buffer算法算法n n改改进进之三：利用之三：利用边

22、边、边边的分的分类类表、表、边对边对、活化、活化边边对对表避免表避免边边与与扫扫描描线线的盲目求交的盲目求交n n扫描线Z-buffer算法-边边数据数据结结构构n n边边：用来：用来记录记录多多边边形的一条形的一条边边，其中，其中vmaxvmax：边边的投影的投影的上端点的的上端点的v v坐坐标标。n nu u：边边的下端点的的下端点的u u坐坐标标n nn n：边边的下端点的的下端点的n n坐坐标标 D Du u：在：在该边该边上上v v值值增加一个增加一个单单位位时时，u u坐坐标标的的变变化量化量D Dn nnextEnextE：指向下一条：指向下一条边结边结构的指构的指针针。扫描描线

23、Z-bufferZ-buffer算法算法n n边边的分的分类类表（表（ETET）：当一个多）：当一个多边边形形进进入活化多入活化多边边形表形表时时，需需为为其建立一个其建立一个边边分分类类表（表（ETET）。）。这这里，里，ETET与其在与其在扫扫描描转换转换多多边边形的形的扫扫描描线线算法中的含算法中的含义义相同，是相同，是对对多多边边形的非形的非水平水平边进边进行分行分类类的一的一维维数数组组，长长度等于度等于绘图绘图窗口内窗口内扫扫描描线线的数目。若一条的数目。若一条边边在投影平面上的投影的下端点的在投影平面上的投影的下端点的v v坐坐标标为为v v，则则将将该边归为该边归为第第v v类

24、类。区域子分算法（区域子分算法（Warnock Warnock 算法算法)n n由来：由来：Z Z缓缓冲器算法与冲器算法与扫扫描描线线Z Z缓缓冲器算法中都是冲器算法中都是将像素孤立来考将像素孤立来考虑虑，未利用相，未利用相邻邻像素之像素之间间存在的存在的属性的属性的连贯连贯性，即区域的性，即区域的连贯连贯性，所以算法效率性，所以算法效率不高。不高。实际实际上，可上，可见见多多边边形至少覆盖了形至少覆盖了绘图绘图窗内窗内的一的一块块区域，区域，这块这块区域由多区域由多边边形在投影平面上的形在投影平面上的投影的投影的边边界界围围成。如果能将成。如果能将这类这类区域找出来，再区域找出来，再用相用相

25、应应的多的多边边形形颜颜色加以填充色加以填充则则避免了在每个像避免了在每个像素素处计处计算深度算深度值值，消，消隐问题隐问题也就解决了。也就解决了。区域子分算法（区域子分算法（Warnock Warnock 算法）算法）n n算法基本思路：首先将场景中的多边形投影到绘图窗口内（假假设设它它为边长为为边长为k k的正方形的正方形），判断窗口是否足够简单，若是则算法结束；否则将窗口进一步分为四块。对此四个小窗口重复上述过程，直到窗口仅为一个像素大小。此时可能有多个多边形覆盖了该像素，计算它们的深度值，以最近的颜色显示该像素即可。区域子分算法（区域子分算法（Warnock Warnock 算法）算法

26、）n n何谓窗口足够简单？存在下列情况之一即可称存在下列情况之一即可称为为窗口足窗口足够简单够简单：1 1）窗口）窗口为为空，即多空，即多边边形与窗口的关系是形与窗口的关系是分离分离的；的；2 2）窗口内）窗口内仅仅含一个多含一个多边边形，即有一个多形，即有一个多边边形与窗形与窗口的关系是口的关系是包含或相交包含或相交。此。此时时先先对对多多边边形投影形投影进进行裁剪，再行裁剪，再对对裁剪裁剪结结果果进进行填充；行填充；3 3）有一个多）有一个多边边形的投影形的投影包包围围了窗口，并且它是最了窗口，并且它是最靠近靠近观观察点的，以察点的，以该该多多边边形形颜颜色填充窗口。色填充窗口。区域子分算

27、法（区域子分算法（Warnock Warnock 算法）算法）区域子分算法（区域子分算法（Warnock Warnock 算法）算法）n n分离和包分离和包围围多多边边形的判形的判别别：通常有：通常有3 3种判种判别别方法：射方法：射线检查线检查法，法，转转角累角累计检查计检查法和区法和区域域检查检查法。法。这这三种三种检查检查都假定相交的和内都假定相交的和内含的多含的多边边形已形已经经事先判定了。事先判定了。n n射射线检查线检查法：从窗口内的任意点，画一法：从窗口内的任意点，画一条射条射线线至无至无穷远处穷远处，累，累计计射射线线与多与多边边形形交点的个数。如果交点的个数。如果为为偶数偶数

28、(或或为为零零)，则则此多此多边边形与窗口分离；否形与窗口分离；否则则，此多，此多边边形形包包围围窗口。但当射窗口。但当射线线通通过过多多边边形的形的顶顶点点时时，会得出，会得出错误结论错误结论。(如左如左图图)解决方解决方法有：当射法有：当射线线通通过过多多边边形的局部极形的局部极值顶值顶点点时时，记记入两个交点；当射入两个交点；当射线线通通过过多多边边形的非局部极形的非局部极值顶值顶点点时时，记记入一交点。入一交点。yxp6p7p8p4p10p9p3p1p2p5yxp6p4p3p1p2p5p6区域子分算法（区域子分算法（Warnock Warnock 算法）算法）n n转转角累角累计检查计

29、检查法法:按按顺时针顺时针方向或逆方向或逆时针时针方向方向绕绕多多边边形依次累加多形依次累加多边边形各形各边边起点与起点与终终点点对对窗口内任意一点所窗口内任意一点所张张的的夹夹角。按累角。按累计计角度之和可角度之和可以判定：以判定：n n若角度之和等于若角度之和等于0 0，则则表示多表示多边边形与窗口分离；形与窗口分离；n n若角度之和等于若角度之和等于360360 *n*n，则则表示多表示多边边形包形包围围窗口窗口(n(n次次)。多边形多边形窗口窗口窗口窗口多边形多边形区域子分算法（区域子分算法（Warnock Warnock 算法算法n n区域检查法:1）区域编码 2）多边形顶点编码 3

30、）多边形边的编码 4）多边形的编码区域子分算法（区域子分算法（Warnock Warnock 算法算法)n n1 1、区域、区域编码编码。窗口四条。窗口四条边边所在直所在直线线将屏幕划分成将屏幕划分成9 9个区域，个区域，对对窗口以外的窗口以外的8 8个区域按逆个区域按逆时针时针（或（或顺顺时针时针）进进行行编码编码，编码为编码为0707。n n2 2、多、多边边形形顶顶点点编码编码。多。多边边形形v v0 0v v1 1v vn n的的顶顶点点v vi i的的投影落在哪个区域，那个投影落在哪个区域，那个区域的区域的编码编码便作便作为该顶为该顶点点的的编码编码，记为记为I Ii i。区域子分算

31、法（区域子分算法（Warnock Warnock 算法算法)n n3、多边形的编码。多边形的边vi ivi+1i+1的编码定义为Di i=Ii+1i+1-Ii i，i=0,1n；其中，令In+1n+1=I0 0，并且，当Di i 4时，取Di i=Di i-8；当Di i 4时，取Di i=Di i+8；n n当Di i=+/-4时，取该边与窗口边的延长线的交点将该边分为两段，对两段分别按上面的规则编码，再令Di i等于两者之和。n n4、多边形的编码。定义多边形的编码为其边的编码之和，则区域子分算法（区域子分算法（Warnock Warnock 算法算法)区域子分算法（区域子分算法（Warn

32、ock Warnock 算法算法)n n例如：例如：I I0 0=5,I=5,I1 1=7,I=7,I2 2=3,=3,D D0 0=7-5=2,=7-5=2,D D1 1=3-7=-4,=3-7=-4,D D2 2=5-3=2,=5-3=2,因因为为D D1 1=-4,=-4,按按第三步的第三步的处处理理规则规则，取，取边边v v1 1v v2 2与窗口上与窗口上边边所在直所在直线线的交点将的交点将v v1 1v v2 2分分为为两段，两段，两段的两段的编码编码分分别为别为2 2，2 2，从而，从而D D2 2=4=4。最。最终终求出多求出多边边形的形的编码为编码为 D D0 0+D D1

33、1+D D2 2=2+4+2=8=2+4+2=8，因，因此，此，该该三角形包三角形包围围窗口。窗口。区域子分算法（区域子分算法（Warnock Warnock 算法算法)n n如如图图：I I0 0=1,I=1,I1 1=3,I=3,I2 2=7,=7,D D0 0=3-=3-1=2,1=2,D D1 1=7-3=4,=7-3=4,D D2 2=1-7=-6=1-7=-6。按第按第3 3步步处处理理规则规则，取，取v v1 1v v2 2与窗口上与窗口上边边所在直所在直线线的交的交点点v v 将其分将其分为为两段，两段两段，两段的的编码编码分分别为别为-2-2，-2-2，从，从而而D D1 1

34、=-2+=-2+（-2-2）=-4=-4。而。而D D2 2=-6+8=2=-6+8=2。最。最终终求出多求出多边边形的形的编码为编码为D D0 0+D D1 1+D D2 2=2+=2+（-4-4）+2=0+2=0。n n从而得出从而得出结论结论：多：多边边形与形与窗口分离。窗口分离。光光线投射算法投射算法n n算法思想：将通算法思想：将通过绘图过绘图窗口内每一个像素的投影窗口内每一个像素的投影线线与与场场景景中的所有多中的所有多边边形求交。如果有交点，用深度形求交。如果有交点，用深度值值最大的交点最大的交点（最近的）所属的多（最近的）所属的多边边形的形的颜颜色色显显示相示相应应的像素；如果

35、没的像素；如果没有交点，有交点，说说明没有多明没有多边边形的投影覆盖此像素，用背景色形的投影覆盖此像素，用背景色显显示即可。示即可。光光线投射算法投射算法-算法描述算法描述for(v=0;vvmax;v+)for(u=0;uumax;u+)形成通过像素(u,v)的投影线；for(场景中每一个多边形）将投影线与多边形求交；if (有交点）以最近交点所属多边形的颜色显示像素(u,v)else 以背景色显示像素(u,v)；光光线投射算法投射算法n n基本问题n n光光线线与物体表面的求交与物体表面的求交光光线投射算法投射算法-算法描述算法描述for(v=0;vvmax;v+)for(u=0;uZ Z

36、f f时，取时，取S S0 0=S=Sf fn n当当Z Z0 0 Zf ht t,即qt tqi i。如果入射角不断增大，到一定的程度，折射角qt t=90度，此时透射光线沿着平行于分界面的方向传播，称此时的qi i为临界角度，记为qc c。当qi i qc c时，发生全反射，透射与反射光合二为一。光透射模型的研究光透射模型的研究n n早期简单透射现象的模拟n n1980年，Whitted光透射模型，首次考虑了光线的折射现象n n1983年，在Whitted的基础上，Hall光透射模型，考虑了漫透射和规则透射光整体光照明模型整体光照明模型 简单光照明模型亦称局部光照明模型，其假定物体是不透明

37、的，只考虑光源的直接照射，而忽略了光在环境景物之间的传递。为了增加图形的真实感，必须考虑环境的漫射、镜面反射和规则投射对景物表面产生的整体照明效果。整体光照明模型考虑了物体之间的相互影响以产生整体照明效果整体光照明模型整体光照明模型n n物体表面入射光的构成（1 1）光源直接照射）光源直接照射（2 2）其它物体的反射光）其它物体的反射光（3 3）透射光）透射光n n局部光照明模型仅考虑了（1）整体光照明模型整体光照明模型n n例如：从例如：从视视点点观观察到的物体察到的物体A A表面表面的亮度来源于三方面的的亮度来源于三方面的贡贡献：献：（1 1）光源直接照射到）光源直接照射到A A的表面，然

38、后的表面，然后被反射到人眼中的光被反射到人眼中的光产产生的。生的。（2 2）光源或其它物体的光）光源或其它物体的光经经A A物体折物体折射到人眼中的光射到人眼中的光产产生的。生的。（3 3）物体）物体B B的表面将光反射到物体的表面将光反射到物体A A的表面，再的表面，再经经物体物体A A的表面反射到的表面反射到人眼中人眼中产产生的。生的。n n局部光照明模型局部光照明模型仅仅考考虑虑了（了（1 1）WittedWitted光照模型光照模型n nWhitted光照模型基于如下假设：n n物体表面向视点方向V辐射的光亮度I 由三部分组成：（1）光源直接照射引起的反射光亮度Il l。（2）来自V的

39、镜面反射方向R的其它物体反射或折射来的光的亮度Is s。（3）来自V的透射方向T的其它物体反射或折射来的光的亮度It t WittedWitted光照模型光照模型n nWittedWitted光照模型：光照模型：I I=I Il l +K Ks s I Is s +K Kt tI It t n n或或n nI Is s 为镜面反射方向的入射光强度；为镜面反射方向的入射光强度；K Ks s为镜面反射系数，为镜面反射系数，为为0 01 1之间的一个常数之间的一个常数n nI It t 为折射方向光强，为折射方向光强，K Kt t为透射系数，是为透射系数，是0 0 1 1之间的常之间的常数数n nI

40、 Il l 的计算可采用的计算可采用PhongPhong模型模型因此，关键是因此，关键是I Is s和和I It t的计算。如何计算呢？的计算。如何计算呢？WittedWitted光照模型光照模型-反射、折射方向反射、折射方向计算算n n已知视线方向已知视线方向V V，求其，求其反射方向反射方向R R与折射方向与折射方向T T（N N是表面的法向方向是表面的法向方向）n n视线视线V V的反射方向的反射方向R Rn n折射方向折射方向T TT、R方向确定后，下一步即可计算沿二方向投射景物表面上的光亮度，即Is Is 和和It It。另外另外WhittedWhitted模型为一递归模型，为模型为

41、一递归模型，为计算这一模型，将用到下面的计算这一模型，将用到下面的光线跟踪技术。光线跟踪技术。光光线跟踪（跟踪（Raytracing）该方法由Appel于1968年提出。光线跟踪算法的基本原理n n自然界中光线的传播过程光源物体表面 物体表面人眼人眼n n光线跟踪过程-光线传播的逆过程光光线跟踪跟踪n n从从视视点向每个点向每个象素象素发发出一条光出一条光线线，它与，它与场场景中的一些物体表面相交，最近的景中的一些物体表面相交，最近的交点即交点即为为可可见见点，点，记为记为P P，像素的亮度即由，像素的亮度即由P P点的亮度确定。由点的亮度确定。由WhittedWhitted光照模光照模型可知

42、，型可知，P P点的亮度由三部分点的亮度由三部分组组成：成：I Il l ，I Is s 和和I It t。其中其中I Il l 可以直接由局部光照可以直接由局部光照模型模型计计算得到。算得到。光光线跟踪跟踪n n为为了求了求I Is s 和和I It t，从，从P P点点发发出反射光出反射光线线和透射光和透射光线线，它分，它分别别交交场场景中的物体表景中的物体表面于面于PsPs和和PtPt，PsPs和和PtPt点的亮度即分点的亮度即分别为别为I Is s 和和I It t ，将它，将它们们求出代入求出代入WhittedWhitted模模型即可。但是，型即可。但是，I Is s 和和I It

43、t 同同样样由由WhittedWhitted模型确定，即模型确定，即WhittedWhitted模型是一个模型是一个递递归归式，从而式，从而计计算算I Is s 和和I It t 需要重复以上的需要重复以上的计计算算过过程程:计计算局部光亮度、算局部光亮度、发发出反出反射光射光线线与透射光与透射光线线。可以用一棵光。可以用一棵光线树线树来表示来表示光光线跟踪跟踪n n递归终止条件：1、光线不与场景中的任何物体相交2、被跟踪的光线达到了给定的层次3、由于Ks s和Kt t都小于0，当光线经过反射和折射后，其亮度会衰减。因此可以预先设置一个阈值，在进行光线跟踪时，若被跟踪光线对像素亮度的贡献小于这

44、个阈值，便停止跟踪。光光线跟踪算法跟踪算法-算法描述算法描述设置视点，投影平面以及窗口的参数；For（窗口内的每一条扫描线）for（扫描线上的每一个像素）确定从视点指向像素中心的光线ray；像素的颜色=RayTracing(ray,1)；光光线跟踪算法跟踪算法-算法描述算法描述Color RayTracing(Ray ray,int depth)Color RayTracing(Ray ray,int depth)求求rayray与物体表面最近的交点与物体表面最近的交点P P；if if（有交点）（有交点）用局部光照明模型用局部光照明模型计计算算P P点的点的IcIc；color=Ic;col

45、or=Ic;if if （depthdepth给给定的最大跟踪定的最大跟踪层层次）次）计计算算rayray的反射光的反射光线线；Is=RayTracing(Is=RayTracing(反射光反射光线线，depth+1depth+1）；）；if if （物体是透明的）（物体是透明的）计计算算rayray的透射光的透射光线线；It=RayTracing(It=RayTracing(透射光透射光线线，depth+1);depth+1);color=Ic+Is+It;color=Ic+Is+It;else color=black else color=black；return color;return

46、 color;光光线跟踪算法跟踪算法 根据光根据光线线跟踪基本原理，假跟踪基本原理，假设设在在显显示分辨率示分辨率为为NMNM的屏幕上生成的屏幕上生成图图形，必形，必须须从从视视点出点出发发通通过过屏屏幕向景物幕向景物发发射射NMNM条光条光线线。设设每根光每根光线线在在场场景中景中经过经过反射和折射平均派生出反射和折射平均派生出d d根光根光线线，并，并设设每一景每一景物交点朝光源物交点朝光源发发射射m m 条阴影探条阴影探测测光光线线，则总则总的光的光线线数增加至数增加至(m+1)(m+1)d dN NM M。当。当m m为为2 2，d d为为5 5，N N为为800800，M M为为600600时时，其光，其光线线数目是数目是720720万条。万条。这这意味着需意味着需进进行行720720万次直万次直线线与景物的求交与景物的求交计计算才能完成算才能完成图图形形的的绘绘制。制。庞庞大的求交量使大的求交量使图图形形绘绘制耗制耗费费大大增加。大大增加。生成一幅中等复生成一幅中等复杂杂程度的真程度的真实实感感图图形需要数分形需要数分钟钟至数小至数小时时。光光线跟踪算法跟踪算法 优点：能够方便的产生阴影，模拟镜面反射与折射现象。缺点：计算量大，每一条光线都要与场景中的物体进行求交、计算光照模型等。