《计算机图形学》课件第七章

第七章真实感图形生成技术基础7.1隐藏线隐藏面消除7.2光源属性和物体表面属性7.3基本光照明模型7.4阴影7.5整体光照明模型7.6明暗处理技术7.7光线跟踪技术7.8物体表面细节模拟

7.1隐藏线隐藏面消除

7.1.1多面体的隐藏线消除

如果能把每条棱边可见和不可见的分界点找到，消隐问题就能迎刃而解。这些分界点都是多面体的各棱边在oxy

平面上投影的交点，如图7.1所示。图7.1棱边间交点情况这样一来，消隐问题便转化为在oxy平面上求许多直线段交点的计算。若构成场景的各多面体共有N条棱边，用两两求所有直线段的交点，其工作量为O(N2)，当N很大时，这个工作量极其大。要提高算法的效率，就要设法减少求交的工作量，这是可以做到的。实际上，交点的数目远少于O(N2)，如图7.1所示的多面体共有15条边，若不记棱边端点处的交点，其在oxy平面上的投影间的交点仅有5个。采用一些处理技术后，可使交点减少到两个。这说明有许多棱边在oxy平面上的投影相互间并不相交，且即使相交，也不一定为有效交点。要解决的问题是如何能预先知道它们是不相交的，从而把它们排除在求交计算之外。

1．后向面判别

我们把内法线方向背向视点的面称为前向面，其余的面称为后向面（图7.2）。后向面是看不见的，仅由后向面的遮挡不会使别的棱边成为不可见。因此，把后向面全部剔除并不影响消隐的结果。那么，如何判别一个面为后向面呢？这可以通过内外测试法来完成。图7.2后向面判别设多边形P的顶点为Vi=(xi，yi，zi)，i=1，2，…，

L，顶点的次序排列要求为：观察者在多面体外沿V1→

V2→…→VL行走时，多边形的内部始终在他的右侧。为了确定多边形的内法线方向，可计算多边形在oxy平面上投影的有向面积：若SP≥0，则多边形P所在平面为后向面。实际计算时，考虑到误差影响，上述条件可放宽为：(7.2)其中，ε为适当小的正数。这样做有可能把某些前向面误判为后向面而舍去。由于被误判为后向面的前向面多边形在oxy平面上的投影面积很小，因此，不会影响其显示结果。对体来说，相应的包围盒用六个参数：xmini，xmaxi，

ymini，ymaxi，zmini，zmaxi来确定。那么，式（7.3）是两

个体在oxy平面上投影不相交的充分条件。若zmin1>zmax2

(zmin2>zmax1)则第一个（第二个）多面体位于第二个（第一

个）多面体之前，因而前者不会被后者遮挡。以上措施可有效地减少直线段求交的次数，实际计算时，要对构成场景的多面体逐个来考虑。如考虑多面体A的显示时，要先确定可能遮挡A的那些多面体(包括A本身)；对多面体A的每一个多边形G，要找出可能遮挡它的所有多边形，这些多边形要从可能遮挡A的所有多面体的表面多边形中找；对于G的每一条边E，找出可能遮挡它的所有多边形，这些多边形要从可能遮挡G的所有多边形中去找。以上各步均采用包围盒法，找到了所有可能遮挡E的多边形后，便可求E和这些多边形的交点，并决定E的可见部分。

3．边的可见性确定

设边E的端点为Vi，Vi+1，对E和每一个可能遮挡它的多边形进行以下计算和判断：

（1）若Vi，Vi+1都在多边形平面靠近观察者一侧，则该多边形不遮挡直线段E。此时，无须考虑E和该多边形的关系。

（2）否则，将边E和多边形的边界投影到oxy平面，求其投影间的交点。（3）对（2）中求出的每一个交点，判断它在E上的对应点和多边形平面的关系。只有在多边形平面的面后时，交点才予以保留，如图7.3所示，边ViVi+1和多边形ABCD在oxy平面上的投影相交于点Q，但Q在ViVi+1上的对应点V在多边形平面的前面，这种交点称为无效交点，不予保留。

（4）若ViVi+1和多边形在oxy平面上的投影不相交，那么要判断Vi或者Vi+1的投影是否在多边形投影的内部。若在内部，则E被整个遮挡了。图7.3多边形不遮挡直线段的情况

4．算法描述

设多边形P的顶点为Vi=(xi，yi，zi)，i=1，2，…，L，边E的端点为Vl，Vl+1，则多边形P所在平面的方程可由任意三个不共线的点求得。比如，顶点Vi，Vj和Vk不共线，那么平面方程为：～～～～～～～（7.4）其显式表示为(7.5)那么，其交点的参数为：当R<0时，QlQl+1由多边形外进入多边形；当R>0时，QlQl+1

由多边形内离开多边形（图7.4）。～～图7.4

QlQl+1进入或离开多边形判断点Ql在多边形内或外的方法是从点Ql出发沿x轴正向做一条射线，若该射线与多边形交点的个数为奇数，则Ql在多边形内；若该射线与多边形交点的个数为偶数，则Ql在多边形外。但要正确地找到交点个数并不容易，如图7.5中的点Q6处，可能由于舍入误差的原因，计算时认为射线QlF和线段Q5Q6，Q6Q7均有交点，也可能算出只有一个交点或无交点。～～～～～图7.5确定Ql在多边形内外的方法不同的交点数目会产生完全不同的结果，因此，为了准确求出交点个数，首先做以下判断：（7.9）若其为真，则表明Qm和Qm+1分属于射线QlF的两侧，然后再求QmQm+1和QlF的交点横坐标：（7.10）一旦求出QlQl+1和所有可能遮挡它的多边形边界的交点后，即可确定其可见部分。首先，把所有交点的参数值t按其大小排序。计算点Ql处的不可见阶ivord，Ql处的ivord初值为零。对每一个和QlQl+1有交点的多边形，找出值t最小的那个交点。若为出点，则ivord加1；若为进点，则ivord不变。这样即可求出点Ql处的不可见阶ivord。设QlQl+1上交点的参数值t排序如下：

t1，t2，t3，…若Ql处的不可见阶为零，则QlQl+1上从参数t=0到t=t1那一段可见，否则不可见。t1处的ivord可根据参数为t1的点是进点还是出点来确定。若为进点，则ivord加1；若为出点，则ivord减1。若t1处的ivord≠0，那么QlQl+1上从参数t=t1到t=t2那一段不可见，否则可见。采用这种方法，从

Ql一步步走到Ql+1便可确定出QlQl+1上的可见部分与不可见部分。在确定不可见阶时，Ql处的工作量大一些，以后每经过一个交点时，只要把上一点的ivord加1或减1就行了。由上述的讨论可见，准确求出QlQl+1和各多边形的交点个数与位置至关重要。比如，Qm+1和QlQl+1很近时，那求交点时算出的参数s将接近于1。此时，需要检查Qm和

Qm+2是位于QlQl+1的同侧还是异侧。若是前者，则认为

QmQm+1、Qm+1Qm+2和QlQl+1均无交点；若是后者，则认为只有一个交点（图7.6）。～～～～～～～图7.6确定QlQl+1和多边形的交点个数7.1.2参数曲面的隐藏线消除

由参数方程（7.11）定义的曲面是CAD/CAM中最常用的曲面表示形式。参数曲面的显示通常采用曲线网格形式，因此，参数曲面的隐藏线消除就是去掉被遮挡的曲线网格部分。所以，为了实现消隐，必须进行以下工作：①建立曲面的网格表示；②点的可见性测试；③轮廓处理。下面我们以透视投影为例，介绍一种在物空间实现隐藏线消除的简单算法。

1．建立曲面网格表示

对于给定的参数曲面（7.11），对参数u和v进行等距

分割：计算曲面上的点列：顺次连接点集{Pi，j}所构成的空间矩形拓扑网格便是曲面（7.11）的网格表示。

2．点的可见性测试

设透视投影中心为V，待测试点为P，网格三角

形为ΔPi，jPi+1，

jPi，j+1，如图7.7所示。图7.7网格三角形及点P的可见对点P关于所有的网格三角形进行上述两步测试，并记录点P的可见性标志。点P的可见性测试过程描述如下：

3．轮廓处理

一旦完成了每一条网格曲线的可见性测试之后，那么对每一条网格曲线，根据其上的点的可见性标志，即可绘制图形。若相邻两点可见，则这两点之间的线段可见；若相邻两点均不可见，则这两点间的线段不可见；若一点可见，一点不可见，则需要确定线段可见部分与不可见部分的分界点。这些分界点必然会形成曲面投影之后的外轮廓，因此这一过程称为轮廓处理。如图7.8所示，等参数曲线u=ui上相邻两点A和B，其中A可见，B不可见，则需要确定线段AB的可见部分与不可见部分的分界点。图7.8轮廓处理令vC=(vA+vB)/2，根据参数(ui，vC)求出曲面上的对应点C=(x(ui，vC)，y(ui，vC)，z(ui，vC))，判断点C的可见性。若点C的可见性同点A，则修改点A为点C，反之修改点B

为点C。对修改后的点A、B继续上述操作，直到A与B间

的距离满足精度要求为止，这样即可求得分界点。7.1.3区域子分算法

区域子分算法是在象空间讨论物体表面可见性的一种分而治之的算法。整个屏幕称为窗口，区域子分算法是一个递推的四等分过程，每一次把矩形的窗口等分成四个相等的小矩形，分成的矩形也称为窗口，见图7.9。每一次子分，均要把显示的多边形和窗口的关系作一次判断。图7.9子分的过程这种关系有以下四种：

（1）多边形包围了窗口（图7.10情况1）。

（2）多边形和窗口相交（图7.10中情况2）。

（3）窗口包围了多边形（图7.10中情况3）。

（4）窗口和多边形分离（图7.10中情况4）。图7.10四种多边形和窗口的关系在窗口和每个多边形的关系确定之后，有些窗口内的图形便可以显示了。它们属于下列三种情况之一：

（1）所有多边形都和窗口分离，这时只要把窗口内所有的象素着上背景颜色即可。

（2）只有一个多边形和窗口相交，或这个多边形包含在窗口内，这时需先对窗口内每一个象素着上背景颜色，再对窗口内多边形部分用扫描线算法着色（3）只有一个多边形和窗口相交，这个多边形把窗口整个包围在内，或虽有几个多边形和窗口相交，但离观察者最近的一个多边形包围了整个窗口，这时需把整个窗口着上离观察者最近的那个多边形的颜色。

对上述三种情况的窗口来说，图已经可以画出，因而不必再分细了。对上述三种情况不成立的窗口再一分为四，见图7.9。对分得的窗口重复上述的处理，对不能处理的窗口继续一分为四。如此重复，直到窗口的边长和一个象素的宽度一样。这时，这个窗口对应的象素的颜色可取成最靠近观察者的多边形的颜色或和这个窗口相交的多边形颜色的平均值。

分而治之算法的思想比较简单，具体实现时要处理好细节，才能提高效率，下面介绍一些有效的处理方法。对所有的多边形按其顶点的z坐标最大值（即最靠近观察者的一个顶点的z坐标值）来排序。对一个具体窗口来说，随着窗口不断地被细分，这个多边形序列的元素将越来越少。这是因为窗口分小了，用包围盒的办法就可能判定一些多边形和这个窗口是无交的，这些多边形也不会和这个窗口的子窗口相交，因此对这个窗口来说，这些多边形可从多边形序列中排除。对于不能用包围盒办法判断和窗口不相交的多边形，则要经过计算去确定它们之间的关系。这时可以采用与第四章中多边形裁剪算法类似的方法去确定多边形和窗口的边界是否有交点。有交点时，说明多边形和窗口有交；无交点时，还要去确定它们是分离还是有包含关系。后面一个问题可用本章第一节中说明的判断一个点在多边形内或外

的算法来解决。在找到了一个多边形包围所考虑的窗口后，就要把它和多边形序列中其他多边形离观察者的远近进行比较，把被它遮挡的多边形从序列中去掉。为此，可把窗口四个顶点坐标的x，y值代入那个包围窗口的多边形所在的平面方程，以求出对应四个顶点处该平面的z坐标值。以zmin记这四个z坐标值的最小值。对序列中第i个多边形，把它各顶点z坐标值的最大值记为zmaxi。若zmin≥zmaxi，则序列中第i个多边形便被遮挡了。如图7.11所示，多边形AB包含了窗口，多边形CD便可用此法证实是被遮挡的，但多边形EF则不能用此方法证实被多边形AB所遮挡。遇见这种情况，可在窗口内多边形EF上任找一点G(xG，yG，zG)，把xG，yG代入多边形AB所在的平面方程，求出H点处的坐标z值zH，若zH>zG，则AB在窗口内遮挡多边形EF。图7.11确定被遮挡多边形的方法对于分辨率为2N×2N的光栅显示器，窗口经N次细分便可使子窗口和一个象素的大小一样了。

区域子分方法提出来后，有不少文章提出了一些改进方法。WeilerKJ和AthertonPR提出了用多边形的边界来对窗口作划分的方法。该方法先用某种方法对各多边形在深度方向作初步的排序，例如，可按多边形顶点z坐标值的最大值zmaxi来排序，zmaxi值大的排在前面。现把多边形序列中的第一个多边形(裁剪多边形)取为窗口，多边形序列中的其他的多边形都要被这个窗口裁剪。裁剪的结果要建立两个多边形序列表，一个是窗口内的多边形表，一个是窗口外的多边形表。每一个被裁剪的多边形裁剪后，位于窗口内的部分放入内部表中，位于窗口外的部分放在外部表中。图7.13（a）和图7.13（b）分别为

图7.12中多边形的内部表和外部表，图7.12中多边形1作为窗口。图7.12要消隐的多边形图7.13下面要确定裁剪多边形是否都比内部表中的多边形更靠近观察者，这一工作还是可以用顶点z坐标极大值极小值比较的办法来做，即求出裁剪多边形各顶点坐标z的极小值

zmin，求出内部多边形各顶点坐标z的极大值zmaxi。对那些满足zmin>zmaxi的内部表中的多边形，便可确认它被裁剪多边形所遮挡。若某一内部多边形不满足上式，则要从该多边形上取一点，作一条和z轴平行的线，求出该线和两个多边形所在平面的交点，根据交点的位置便可准确地确定哪一个多边形更靠近观察者。7.1.4深度缓冲器(Z-buffer)算法

设屏幕的分辨率为m×n，算法需要两个数组：一个是深度缓冲器数组ZB［m］［n］，也就是所谓的Z-buffer，用于存储每一象素上离观察者最近的面片的z坐标值；另一个是颜色属性数组CB［m］［n］(Color-buffer)，用于存

储每一象素上离观察者最近的面片的颜色属性。消除隐藏面可通过不断刷新数组ZB［m］［n］和CB［m］［n］来完成。

Z-buffer算法的步骤如下：

(1)初始化数组ZB［m］［n］和CB［m］［n］：

ZB［i］［j］=zmin，i=0，1，…，m－1，j=0，1，…，n－1；

CB［i］［j］=Background_Color，i=0，1，…，

m－1，j=0，1，…，n－1。(3)输出CB［m］［n］。算法的关键是第(2)步，要尽快判断出哪些点落在一个多边形内，并尽快求出一个点的深度值，这需要应用扫描线的连贯性和多边形边的连贯性。设多边形P所在平面方程为：

Ax+By+Cz+D=0

若C≠0，则多边形P

内点（xi，yj）对应的深度值为(7.12)由于扫描线上相邻点间的水平位移为1，相邻扫描线间的垂直位移也为1，所以，若已知象素点（xi，yj）对应的深度值，则其相邻点（xi+1=xi+1，yj）的深度值zi+1,j为(7.13)对于多边形P，－A／C为常数，故沿扫描线的后继点深度值可由前面点的深度值仅执行一次加法而获得。类似地，可建立多边形内的点在垂直方向上的递推关系。设多边形一条边的方程为ax+by+c=0，将多边形投影到xoy平面上。在y=yj处，xj=－(byj+c)/a；在y=yi+1处，因为yj+1=yj+1，所以xj+1=xj－b/a。若已知象素点(xi，

yj)的对应深度值zij，则沿该边相邻扫描线上点(xi+1，yj+1)的深度值

zi+1,j+1为(7.14)利用扫描线的连贯性和多边形边的连贯性，可得到多边形的点及其深度值的算法。

（1）将多边形的边按其y方向的最小值排序，搜索多边形中各顶点的y值，求其最小值zmin和最大值zmax。

（2）令扫描线y=ymin到y=ymax以增量1变化。

①找出与当前扫描线相交的所有边，利用多边形边的连贯性，求出这些边与扫描线的交点，并将这些交点按x坐标值从小到大排序。②在相邻两交点中选一点，判断其是否被多边形包含。如果被多边形包含，则利用扫描线的连贯性，求出两交点之间各点的深度值。

③重复①、②，直到当前扫描线上所有在多边形内的点的深度值都被求出为止。

深度缓冲器算法原理简单、易于实现，且无须对场景中的面片进行排序。其最大的缺点是两个缓冲器占用的存储空间太大。对于一个1024×1024分辨率的系统来说，则需要容量超过100万个单元的颜色属性缓冲器和深度缓冲器，且深度缓冲器中每个单元还需包含表示深度值所足够的位数。一个减少存储量需求的方案是：将屏幕划分为若干个小区域，逐个区域地处理。特别地是，若将两个缓冲器ZB和CB改为行缓冲器，每计算出一条扫描线上的象素值就输出，然后刷新行缓冲器，再计算下一条扫描线上的象素值，这就得到了扫描线算法。7.1.5扫描线算法

在多边形填充算法中，活化边表的使用取得了节省运行空间的效果。用同样的思想改造Z-buffer算法，就产生了扫描线算法。

扫描线算法的原理是从屏幕最上面的扫描线开始逐行处理的，对每一条扫描线来说，它把相应的颜色属性缓冲器CB置成背景色，用深度缓冲器ZB存放z的极小值。对每一个多边形，检查它在xoy平面上的投影和当前扫描线是否相交。若不相交，则不考虑该多边形；如果相交，则扫描线和多边形边界的交点必定成对出现。对每对交点中间的像素点计算多边形所在平面对应点的深度，并和Z缓冲器ZB中相应单元存放的深度值进行比较，若前者大于后者，则Z缓冲器ZB中相应内容被求得的平面深度值代替，颜色属性缓冲器CB中相应内容也要修改成该平面的属性。对所有的多边形都做上述处理之后，颜色属性缓冲器CB中便存放了当前扫描线上的消隐图形。

1.建立多边形Y桶PT和边Y桶ET

每个筒的深度和显示器上扫描线的行数相同。对于多边形，根据其顶点y坐标的最大值决定放入多边形Y桶的相应行数；对于边，根据两端点最大y坐标决定放入边Y桶的相应行数。多边形Y桶中的多边形结点记录的信息有：多边形平面方程Ax+By+Cz+D=0的系数A、B、

C和D，该多边形在xoy平面上之投影跨过的扫描线数Δy，多边形的颜色属性，多

边形的编号以及下一多边形结点的指针，其结点结构如下：边Y桶中的边结点记录的信息有：边在xoy平面上之

投影跨过的扫描线数Δy，投影和相邻两扫描线交点x坐标的增量Δx，边所属多边形的编号，边的投影之上端点的

x坐标以及指向下一条边结点的指针，相应的结点结构为例如，对于图7.14所示的多边形场景，其相应的多边形Y桶和边Y桶如图7.15和图7.16所示。图7.14要消隐的对象图7.15多边形Y桶图7.16边Y桶

2.建立多边形活化表APL和边活化表AEL

多边形活化表中记录的是在xoy平面上和当前扫描线相交的多边形，边活化表中记录的是多边形边界和扫描线相交的边对。

边对结点的结构如下：

Δzx：沿扫描线方向右移一个象素时，多边形所在

平面深度值之增量。对平面方程Ax+By+Cz+D=0而言，Δzx=－A/C(C≠0)；

Δzy：沿y方向下移一条扫描线时，多边形所在平面

深度值之增量。对平面方程Ax+By+Cz+D=0而言，Δzy=B/C(C≠0)；

IP：边所在多边形的编号。

3.算法步骤

Step1

(初始化)置颜色属性缓冲器每个单元为背景色；

Step2

(y初始化)取扫描线纵坐标y的初始值为PT中非空元素的最大序号；

Step3(APL、AEL初始化)将多边形活化表APL和边活化表AEL置为空表；

Step4按照从上到下的顺序对纵坐标值为y的扫描线，执行以下操作：

(1)将Z-buffer各单元初始化为z的极小值；

(2)检查多边形Y桶PT。如果有新的多边形和该扫描线相交，则将其插入到多边形活化表APL之中；

(3)如果有新的多边形插入到APL中，则把该多边形

在xoy平面上的投影和扫描线相交的边对插入到边活化表AEL中；

(4)如果有些边在该扫描线处结束了，而所在多边形仍在APL中，则从边Y桶ET中找出该多边形在xoy平面上的投影和扫描线相交的新的边或边对，修改AEL或插入到AEL中；

(5)从AEL中取出一个边对，令zx=zl，对每一个满足

条件xl≤x≤xr的坐标为（x，

y）的象素，从左到右做以下处理：

Step5重复Step4，直到多边形活化表APL和边活化表AEL都变空为止。

当处理完一条扫描线后，对于下一条扫描线而言，需要更新多边形活化表APL和边活化表AEL，以求得下一条扫描线的多边形活化表和边活化表。下面说明对多边形活化表APL和边活化表AEL的修改方法。对每一边对先计算:

Δyl=Δyl－1，Δyr=Δyr－1若Δyl<0或Δyr<0，则从一个边对中删去相应的边，并从该边对所属多边形中找出合适的边来代替；若Δyl<0且Δyr<0，则从边活化表中删除该边对。边和下一条扫描线交点的x坐标值由下式求得:

xl=xl+Δxl，xr=xr+Δxr

多边形所在平面对应下一条扫描线在xl

处的深度值为

zl=zl+ΔzxΔxl+Δzy

对多边形活化表APL中的每一个多边形，令Δy=Δy－1，并从其中删除满足条件Δy<0的多边形。7.1.6曲面的扫描线消隐算法

现实场景中的绝大多数景物是曲面物体，如飞机、船舶、汽车和陶瓷器皿等，曲面物体的计算机表示和绘制是计算机图形学研究的重要内容。参数曲面由于其具有外形光滑、形状不依赖于坐标系的选取、容易离散、易于拼接的优点，已成为计算机图形学中曲面造型的主要手段，接下来要解决的问题是怎样绘制参数曲面。在7.1.2节中，我们采用曲线网格形式显示参数曲面，并讨论了隐藏线的消除问题。当然，我们也可在参数曲面上选取一系列采样点，连接这些采样点构成一个多面体逼近参数曲面，并采用多面体绘制算法来显示曲面。但这样的绘制效果总不能令人很满意，例如会出现绘制的曲面不够光滑，轮廓线呈现折线型而非连续光滑的曲线等。

鉴于此，Catmull首先提出了基于曲面精确数学表达式的直接绘制算法。尽管Catmull算法是针对双三次参数曲面片，但其基本原理适用于任何曲面的显示。Catmull算法通过对曲面做递归剖分来显示曲面，其步骤如下：

Step1递归地将曲面分割为子曲面片，直到每一子曲面片在图像空间至多覆盖一个像素为止；

Step2计算在此像素上曲面的属性并显示该像素。只要曲面不是过分弯曲，均可取子曲面片的逼近多边形来检查它是否仅覆盖一个像素。上述分割过程中可能会产生不覆盖任何像素的子曲面片，这些子曲面片的属性赋予离它们最近的像素进行计算。位于显示窗口之外的子曲面片可以略去，与显示窗口相交的子曲面片则需进一步剖分，直至可明确地判定它位于边界内或边界外。

Catmull算法的效率取决于曲面分割的效率，有关曲面分割的具体方法可参阅计算几何中的相关内容。Catmull算法虽然简单巧妙，但它并不按扫描线次序输出结果，因而需占用较大的存储空间来进行消隐处理。因此，Blinn、Whitted、Lane和Carpenter以及Clark等人相继提出了基于扫描线的双参数多项式曲面绘制算法。对多面体而言，由于：①各顶点的最大最小y值容易求得；②扫描线与多边形的交点可用增量法计算；③沿扫描线在交点区间内的像素点处z值亦可用增量法计算。这使得多面体的消隐容易处理，但是参数曲面不具有上述几何性质，因此其消隐要比多面体困难得多。本节我们重点介绍曲面扫描线的两个典型算法：Blinn算法和LaneCarpenter算法。曲面消隐算法的关键在于求解扫描平面和场景中景物表面的交线，设参数曲面为：(7.15)那么，扫描平面y=yscan与参数曲面的交线是：

y(u，v)=yscan=const(7.16)其中u，v为曲面参数，交线称为层面线或等高线。上述交线不一定是单值的，在同一层面上可能并存几支交线。因此，求出交线后，还需沿扫描线相邻像素对交线进行采样，确定采样点的位置，计算出在采样点处曲面的深度值并确定其可见性。

上述问题在数学上可表示为对给定扫描线上的像素，求其投影于该像素的曲面采样点(u，v)，即求解方程：

x(u，v)=xs，y(u，v)=yscan

(7.17)根据求出的u，v参数值即可计算采样点处曲面深度值z(u，v)，以决定扫描线上该像素的可见性。方程（7.17）一般用Newton

Raphson迭代方法求解，采用Newton

Raphson方法需要为待求的采样点选取一个初值。

1.Blinn算法

利用投影于扫描线上的曲面交线的连贯性，采用左边相邻像素处已求得的采样点作为迭代初值，以减少每个像素上的迭代次数。该算法的内层循环可描述如下：

与多边形不同的是，曲面的最高点和最低点不一定出现在曲面边界顶点处，它们通常出现在曲面的边界线内或曲面内部的侧影轮廓线上。曲面的y极大值和极小值满足

条件：

yu(u，v)=0，yv(u，v)=0（7.18）求解上述方程并剔除鞍点后，将所得到y的极大值和

极小值与曲面角点的y值y(0，0)，y(0，1)，y(1，0)，y(1，1)相比较，便可得到曲面y的最大值和最小值。曲面内的侧影轮廓线可基于曲面法向量中的z分量为零这一条件来决定。图7.17显示了一些例子。显然，并非在扫描线上的每一像素处均可求得曲面上的采样点。扫描平面与曲面的交线在屏幕上的投影可位于曲面两条边界线、一条边界线和一条侧影轮廓线或者两条侧影轮廓线之间。图7.17侧影轮廓线扫描平面与曲面边界线的交点由下式确定：扫描平面与侧影轮廓线的交点由下式确定：其中Nz表示曲面法向量的z分量。

2.LaneCarpenter算法

该算法是一种基于曲面分割的消隐算法，与Catmull算法按任意次序剖分、显示曲面不同，LaneCarpenter算法按扫描线顺序处理分割生成的各曲面片。该算法先根据每一曲面片最大的y值，对所有曲面片作y桶分类。在每一扫描线上，活化曲面片表中同当前扫描线相交的曲面片被分割，直到分割生成的每一子曲面片满足一定的“平坦性”准则，或者不与当前扫描线相交为止。不与扫描线相交的子曲面片置入非活化曲面片表中等

待处理，把满足一定平坦性准则的子曲面片看作平面多

边形并采用多边形扫描转换算法处理。值得注意的是，这样的平面多边形实际上是参数曲面的近似表示。LaneCarpenter算法的内层循环可描述如下下面讨论曲面片平坦性的判定方法。设参数曲面为

S(u，v)=(x(u，v)，y(u，v)，

z(u，v))，

a≤u≤b，c≤v≤d

T是四边形(S(a，c)，

S(a，d)，S(b，d)，S(b，c))三角化中的一种(图7.18)。不失一般性，设T=(T1，T2)，其中：T1=(S(a，c)，

S(a，d)，S(b，d))

T2=(S(a，c)，S(b，d)，S(b，c))则曲面片的平坦标准由以下不等式来表示：

d(S(u，v)，T(u，v))≤ε(7.21)其中d(A，B)表示在A和B之间的距离，

T(u，v)表示四边形(S(a，c)，S(a，d)，S(b，

d)，S(b，c))三角化后所形成的两个三角形，ε为控制平坦程度的参数。图7.18四边形（S(a，c)，S(a，

d)，S(b，d)，S(b，

c)）的两种三角化方法具体实现LaneCarpenter算法时，可利用参数曲面的特殊性质高效地对曲面片进行分割。但由于曲面各处的曲率变化不同，依据统一的平坦度标准，常会导致对曲面的非均匀分割。当相邻的曲面片取不同层次的剖分时，其近似多边形表示之间可能存在裂缝或小洞，如图7.19所示。因此必须进行裂缝处理，以便得到光滑的曲面表示。图7.19曲面的非均匀分割导致各子曲面片的近似多边形表示之间存在裂缝

3.裂缝问题处理

不管采用何种自适应剖分方法，由近似多边形表示的曲面上都可能出现裂缝。裂缝问题通常因相邻子曲面片的分割层数不一致所引起，解决裂缝问题的主要方法是Clark方法［afastscanlinealgorithmforrenderingparametricsurfaces，Proc.ofthe6thAnnualConf.onCom.GraphicsandInteractiveTechniques,Aug.1979,

Vol.13，No.2，ACMNewYork,NY,USA］，下面我们详细介绍这一方法。设fn(u)表示函数f(u)关于u的n阶导数，则f(u)在u点的

Taylor展开为：对于三次多项式函数，有：由此可得因此，f(u)可表示成中心差分形式(7.23)对上式关于u求二阶导数，得

Clark采用中心差分公式递归细分曲线。设在递归的第k层，曲线由一系列等距的点ui，k，i=0，1，…，2k来表示(图7.20)，则图7.20参数空间［0，1］的第k层递归细分由上述两式可得这表明在递归的下一层，编号为偶数的点已经算出，即剩下的编号为奇数的点可通过相邻偶数点的中心差分来求得。从式（7.25）可得函数g(u)=1/2(du)2f″(u)具有下述的递归关系：其初始条件为将采用中心差分细分参数曲线的思想推广到双三次曲面稍微复杂一些。双变量双三次曲面f(u，v)的Taylor展开为注意到曲面剖分过程实质上是计算和确定曲面剖分所

生成的各子曲面片的角点，并在曲面片满足一定平坦性准则的条件下，用其角点组成的多边形近似表示该子曲面片。因此，对双三次曲面，可沿其边界曲线进行剖分，并采用中心差分技术求取曲线上的分割点。一片双三次曲面沿u

向或v向的递归细分公式与分割一条三次曲线相同。现在我们考虑在参数曲线v=v0上沿u向分割双三次曲面(图7.21)。由于f(u，v0)为三次多项式，故f(u1/2，v0)可通过

f(u，v0)和fuu(u，v0)表示成中心差分的形式图7.21曲面分割设u0，0=u0，u1，0=u1，分割f(u，v0)的初值为：这与在等参数线u=u0上求f(u0，v1/2)的方法类似。实际应用中，为了沿所有方向分割，每个曲面片的角点需存储以下三个值：沿某一方向分割只需把这些值组成适当的f()和g()对。

Clark分割方法的优点在于式（7.25），它把曲面片在某条边界曲线的中点表示成了该曲线端点的平均值，加上一非线性项。若该非线性项为零，则三点共线，所在的边为直线。因而该非线性项提供了衡量曲面片边界曲线直线度的直观的表示形式。一旦非线性项小于给定的阈值，就在分割过程中把它从式（7.25）中去掉，即把该边用直线来代替。在后续的剖分中，相邻的面片都将该公共边界曲线视为直线，从而避免了裂缝问题。Clark方法的几何原理如图7.22所示。图7.22

Clark方法的几何解释中心差分的一个副产品是曲面片各边界曲线的非线性项可作为估计该曲面片的平坦性判据，这将避免总采用别的平坦性测试准则所带来的额外开销。

采用中心差分对曲面进行剖分的严重缺陷是没有利用

Bézier曲面的凸包性，面片四个角点处所存储的信息中没有提供对曲面片y向的最大最小估计，因而不能单独用于曲面扫描算法中。7.1.7优先级表算法

上面讨论的各种算法都是基于构成场景的各多边形离视点的远近来决定它们的隐藏关系。优先级表算法就是试图按多边形离观察者的远近来建立一张表，距观察者远的优先级低，近的优先级高。如果把这张表正确地建立起来，那么只要从优先级低的多边形开始，依次把多边形的颜色填入帧缓冲器以形成该多边形的图，直到优先级最高的多边形画入帧缓冲器后，整幅图就可以显示好了。这种算法的过程与画家创作油画的过程类似，所以也称作画家算法。优先级表算法同时运用物空间和象空间操作，以实现以下基本功能：

（1）将面片按深度递减方向排序。

（2）由深度最大的面片开始，逐个对面片进行扫描

转换。

这里，排序操作同时在象空间和物空间完成，而多边形面的扫描转换仅在象空间完成。该算法的难点在于怎样对多边形面片做一个正确地排序，下面给出一个动态方法。

Step1初始排序：根据多边形面片顶点z坐标的最小值zmin，对多边形做初始排序；

Step2设深度最小的多边形面片为P，确定P和序列中其他多边形Q的关系：

ifPzmax<QzminthenP

和Q的关系确定；

ifPzmax>Qzminthen进行以下五种测试：①P

和Q在xoy平面上的投影的边界包围盒在x方向不相交（图7.23（a））；

②P

和Q在xoy平面上的投影的边界包围盒在y方向不相交（图7.23（b））；

③P的各顶点均在Q的远离视点的一侧(图7.23（c）)；④Q的各顶点均在P的靠近视点的一侧(图7.23（d）)；⑤P

和Q在xoy平面上的投影不相交(图7.23（e)）。图7.23

P不遮挡Q的各种情况上述五项中只要有一项成立，P

和Q的关系就能确定，无需重新排序。由于从第一项开始至第五项结束，测试所需工作量是递增的，因此测试时应按这一顺序进行。如果上述五项测试均不成立，则应在多边形序列中交换P

和Q的位置(次序)，重新排序。

Step3重复Step2，直至得到一个正确排序的多边形序列。对于有循环遮挡或有多边形面片相互贯穿的场景，上述排序方法将导致死循环，此时算法反复将面片的位置进行组合。为了避免死循环，在优先级最低的多边形和其他多边形进行交换时，对原来优先级最低的多边形作一标志，当有标志的多边形再换成优先级最低的多边形时，则说明出现了相互遮挡或相互贯穿的现象。此时，把P

沿Q平面一分为二，把多边形序列中原多边形P删掉，将P

分成的两个多边形加入到多边形序列中。7.1.8

BSP算法

BSP(BinarySpacePartitioning)算法是决定场景可见性的一种有效算法。类似于画家算法，BSP算法也是从远到近向屏幕覆盖画面。该算法特别适合于场景不变，仅视点变化的情况。

BSP算法的主要工作是建立BSP树，建立BSP树的过程实质上是对场景所含的景物表面递归地进行二叉分类的过程。（1）在场景中选取一平面P1，将场景空间分为两个半空间，相应地把场景分为两组。相对于视点位置，一组景物位于P1的前面，另一组景物位于P1的后面。若有某一景物与P1相交，则把该景物分割为两个景物。

（2）选取另一平面P2对所生成的两个子空间继续分割，并对每一子空间所含景物进行分类。

（3）递归地进行空间分割和景物分类的过程，直到每一子空间中所含景物少于给定的阈值为止。上述分割过程可表示为一个BSP树，在该树中，景物位于叶结点，左子树为场景中位于分割平面前面的景物，右子树为场景中位于分割平面后面的景物(图7.24)。图7.24

BSP算法的空间分割和BSP树对于由多边形面片组成的场景，分割平面常常选为与多边形面片重合的平面。一旦BSP树构造完成，依据当前视点所在位置，对场景中每一个分割平面所生成的两个子空间进行分类，其中包含视点的子空间标识为“front”，另一子空间标识为“back”。然后递归地搜索场景BSP树，先绘制标识为“back”的子空间中所含景物，再绘制标识为“front”的子空间所含景物。目前已有许多系统借助硬件来完成BSP树的构造和处理的快速实现。7.1.9光线投射算法

光线投射算法(raycastingalgorithm)建立于几何光学基础之上，它沿光线的路径追踪可见面，是一种有效的消隐算法。由于场景中有无数条光线，而我们仅对穿过像素点的光线感兴趣，因此可考虑从像素点出发，逆向跟踪射入场景的光线路径。光线投射算法对包含曲面，特别是球面的场景有很高的效率。光线投射算法可看作是z-buffer算法的一种变形。在

z-buffer算法中，我们每次处理一个面片，并对面片上的每个投影点计算深度值，计算的深度值与z-buffer中相应单元的保存值进行比较，以确定每一个像素点所对应的可见面片。在光线投射算法中，每次处理一个像素，并沿光线的投射路径计算出该像素所对应的所有面片的深度值。光线投射算法只是光线跟踪算法的特例，有关光线跟踪算法，我们将在7.7节详细讨论。

7.2光源属性和物体表面属性

景物表面的反射光或透射光不仅决定于景物表面的材料、景物表面的朝向以及它与光源之间的相对位置，而且还决定于向表面入射光能的光源性质。

光源的属性包括它向四周所辐射光的光谱分布、空间光亮度分布以及光源的几何形状。例如，日光灯与白炽灯所发出的光具有不同的光谱分布，前者偏青色，后者偏

黄色。不同结构和形状的光源向外辐射的光能具有不同的空间分布，探照灯发出定向的平行光，磨沙灯泡向四周均匀发射柔和的光。从几何形状看，光源有四类：点光源、线光源、面光源和体光源，其中以点光源最为简单。计算机图形学中，常假定点光源照明，这是由于采用点光源容易确定到达被照射点的光能大小，阴影计算也较为简单。但将场景中的所有光源均处理成点光源往往会影响所生成图形的真实性，如画面中的阴影区域都具有非常尖锐的边界等。实际上，自然界中的大多数光源并不是理想的点光源，而是具有一定尺寸大小的光源。对于线光源、面光源和体光源等，则不适合用点光源来近似模拟，因为光源的大小与场景中面片相比不足够小。此时，用分布式光源模拟其光照效果更为精确，其做法是计算光源外表面各点所共同产生的光照。物体表面属性包括表面的材质和形状。物体表面的材质类型决定了反射光线的强弱。表面光滑的材质将反射较多的入射光，而较暗的表面则能吸收较多的入射光。同样对一个透明的表面，部分入射光会被反射，而另一部分光会被折射。粗糙的物体表面往往将反射光向各个方向散射，这种光线的散射现象称为漫反射。非常粗糙的材质表面主要产生漫反射，因而从各个视角观察到的光亮度几乎是相同的。我们通常所说的物体颜色实际上就是入射光线被漫反射后所表现出来的颜色。

7.3基本光照明模型

我们知道，从光源发出的光照射到景物表面时，会出现以下三种情况：

（1）经景物表面向外反射形成反射光。

（2）若景物透明，则入射光会穿透该景物，从而产生透射光。

（3）部分入射光将被景物表面吸收而转换为热能。显然，只有反射光和透射光能够刺激人眼产生视觉效果。物体表面的反射光和透射光的光谱分布决定了物体呈现的颜色，反射光和透射光的强弱则决定了景物表面的明暗程度。显然，反射光和透射光决定于入射光的强弱、光谱组成以及景物表面对入射光中不同波长光的吸收程度。例如，当一束白光照射在一个吸收除红光之外所有

不同波长光的不透明景物表面上时，景物呈红色。但若用一束绿光或蓝光照射该景物时，则它

将呈黑色。因而，脱离来自光源的入射光来讨论一个景物的颜色是没有意义的。通常我们所

说的物体颜色都是假定入射光为白光。由以上讨论可知，若已知入射光在每一波长上的强弱和物体表面在各波长上对光的吸收率，即给出入射光的光谱分布以及物体表面的反射率和透射率的光谱分布，我们就能根据环境的光源布置和景物表面的材料属性正确计算出景物表面反射光和透射光的光强和颜色。但由于光谱采样和光谱至颜色的转换的计算量相当大，而在许多应用场合，并不要求如此精确的模拟，因而有必要给出一些简单的光亮度计算方法。从视觉效果来看，通常我们可假定入射光仅由红、绿、蓝三种不同波长的光组成，这样，在光照模型中，我们仅需考虑景物表面对这三种不同波长光的反射和透射，从而大大简化了光亮度的计算。更进一步，若假定光源发出的光为白光，景物为不透明体，则景物表面呈现的颜色仅由其反射光决定。物体表面的反射光分为漫反射光和镜面反射光。漫反射光可以认为是光穿过物体表面层被部分吸收后重新发射出来的光。因此，漫反射均匀地散布在各个方向，观察者不论站在哪一方位，他所观察到的漫反射光的强度均相等。镜面反射光则是物体的外表面对入射光的直接反射。镜面反射

光亮度沿镜面反射主方向最强，在该方向四周则逐渐衰减，形成一定的空间分布，因而，观察者只有位于一定方向上才能看到明亮的反射光。7.3.1

Lambert漫反射模型

自然界中的绝大多数景物为理想漫反射体，Lambert余弦定律总结了一个理想漫反射物体在点光源照射下的光的反射规律。根据Lambert定律，一个理想漫反射物体表面上反射出来的漫反射光的强度同入射光与物体表面法向之间夹角的余弦成正比，即

I=kdIlcosθ

(7.24)其中，I为景物表面在被照射点P处的漫反射光的光亮度，

Il为点光源所发出的入射光亮度，kd(0≤kd≤1)为景物表面的漫反射率（diffusereflectivity），θ为入射光与表面法向之间的夹角（图7.25）。

若记景物表面在被照射点P处的单位法向量为N，P到

点光源的单位向量为L，则式（7.24）可表达为如下的向量形式：

I=kdIl(N·L)(7.25)图7.25Lambert漫反射几何说明显然，当点光源离被照射表面很远时，式（7.25）中的向量L变化很小，因而可将L看作为一个常向量。我们称此时的点光源为方向光，它可由一向量完全确定。由式（7.24）可知，当入射角θ不小于π/2时，光源位于物体背面，因而该光源对被照射点的光亮度贡献为零；当入射角θ为0时，光源垂直照射在景物表面上，此时反射光的强度最大；当入射光线以相同入射角照射在不同材质的景物表面时，这些表面会呈现不同的颜色，这是由于不同材质的表面具有不同的漫反射率。在实际场景中，一个物体表面即使不直接暴露于光源之下，只要其周围的物体被照明，它也可能看得见，这是由于物体还会接收到从周围环境投射来的光。在图形学中，称这部分光为环境光（ambientlight）或泛光。环境光是一种分布式光源，精确模拟它非常耗时。在局部光照明模型中，我们常假定环境反射光是均匀入射的漫反射光，并用一个常数来表示其强度。这样Lambert漫反射光照

明模型可写成：

I=kaIa+kdIl(N·L)(7.26)其中，Ia为入射的泛光光强，ka（0≤ka≤1）为景物表

面对泛光的漫反射率。

值得指出的是，式（7.26）没有反映出光的距离衰减效应。若两个相同材质的物体对光源有相同的朝向，但与光源的距离差距较大，那么采用式（7.26）计算得到的两个物体表面的光亮度是相同的。显然，这与实际情况不符。众所周知，光的传播以

距离平方衰减，即某处入射光的强度与该点和光源之间的距离平方成反比。此时，Lambert漫反射模型应修正为(7.27)其中，d为被照射点与光源之间的距离。在实际应用中，对入射光强按距离平方衰减往往不能很好地区分点光源在相距较近的景物表面上所产生的光照效果。假如点光源离被照射表面较远，因为1/d2变化不大，计算得到的表面光亮度难以表现光的距离衰减效果。若距离非常近，则该项变化非常大，会导致不真实的光照效果。为此，图形学中常采用经验模型来模拟点光源的距离衰减效果。常用的模型有线性衰减模型，这时，Lambert漫反射模型可改写为(7.28)其中，k为一任意常数。更一般地，我们可采用以下的Lambert漫反射模型来模拟光的各种距离衰减效果：（7.29）其中，f为光源强度衰减因子，c1，c2和c3为用户确定的常数。上述模型可方便地推广到多光源情形。当景物表面受到M个点光源照射时，这些点光源对景物表面的光亮度贡献应逐个累加起来。此时，Lambert漫反射模型为：(7.30)其中，fi，Ili，Li分别为第i个光源强度衰减因子、光强和单位入射方向的向量。迄今为止，我们还没有涉及到光源入射光和景物表面反射光的光谱组成。在简单光照明模型中，我们只需对红、绿、蓝三分量分别计算即可，即假定光源入射光由红、绿、蓝三种不同波长的光组成，分别确定景物表面材质对红、绿、蓝三色光的漫反射率，然后按红、绿、蓝三分量分别代入式（7.30），求解出景物表面的漫反射光亮度。显然，kdIl表示表面在光强为Il的入射光的垂直照射下所呈现的颜色。注意式（7.30）中ka，kd，I，Ia，Ili均为包含红、绿、蓝三分量的向量。7.3.2

Phong光照明模型

镜面反射在日常生活中随处可见，当一个点光源照射在一个金属球面时，会在球面上形成一块特别亮的“高光”（highlight）区域，它是光源在金属球面上产生的镜面反射光投射到观察者眼中的结果。与漫反射不同的是，镜面反射光在空间的分布具有一定的方向性，它们朝空间一定方向会聚，因此表面上高光区域的位置随观察者的方位不同而变化。根据光的反射定律，反射光和入射光对称地分布在表面法线的两侧。对于纯镜面，入射光线严格遵循光的反射定律单向地反射出去（图7.26(a)）。对于一般景物表面，由于表面实际上是由许多朝向不同的微小平面组成的，其镜面反射光分布于镜面反射方向R的周围（图7.26(b)）。由于一般镜面反射光的计算较为复杂，在实际应用中，常作适当的简化处理。图7.26镜面反射的几何关系

1973年，Phong提出了计算表面镜面反射光亮度的经验模型，即

Ispec=IlW(θ)cosnα

（7.31）其中，W(θ)为景物表面的镜面反射率，它是入射角θ和入射光波长的函数。在实际使用时，往往将W(θ)取为常数

ks，通常0≤ks≤1。n称为镜面高光指数，它被用来模拟镜面反射光在空间的会聚程度。α为视线与镜面反射光线之间的夹角。Ispec即为表面投向视线方向的镜面反射光亮度。式（7.33）表明投向观察者的镜面反射光不仅决定于入射光的强度，而且和观察者的观察方向有关。当观察者位于镜面反射方向附近时，观察者接受到的镜面反射光较强，当偏离这一方向时，镜面反射光就会迅速减弱甚至消失。光的会聚程度愈高，在表面上形成的高光愈集中；相反，物体表面较粗糙时，

n取值较小，其镜面反射光呈发散状态。将Phong关于镜面反射光的经验模型与Lambert漫反射模型相结合，便可得到在单一光源照射下的Phong光照明模型：

I=kaIa+kdIlcosθ+ksIlcosnα（7.32）考虑到入射光的距离衰减效应，可得到在多个点光源照射下的表面光亮度计算的Phong模型：（7.33）其中，

M表示对场景有贡献的点光源的总个数，以i为下标的各参数项的含义同前面所述。

Phong模型实际上是一个纯几何模型，一旦光源颜色及景物表面反射率得到确定，则从景物表面上可见点P处到达观察者的反射光亮度I仅与光源入射角θ和视线与镜面反射方向的夹角α有关。因此，在实际计算时，我们仅需求出景物表面各可见点处的单位法向量N、单位入射光线向量Li、单位视线向量V和Li的单位镜面反射向量Ri（图7.27），则由cosθi=(Li·N)，cosαi=(V·Ri)和式（7.34）就可计算每一可见点处的光亮度。图7.27Phong模型中涉及的各个方向

Phong模型成为：（7.34）如前所述，对于一个给定的景物表面，当用上述光照明模型计算景物上一可见点处的光亮度时，需分别对红、绿、蓝三色分别使用式（7.34）来计算。此时，我们采用下面的三个方程来进行三个分量的计算：其中，t=r，g，b分别表示光源入射光强和景物表面漫反射率的三基色分量。这样，用户就可方便地控制物体表面的环境反射、漫反射光的颜色。下面给出用Phong光照明模型计算光亮度的示意性扫描线算法。通过以上讨论可知，Phong模型具有以下明显的特点：（1）光源被假定为理想点光源，且不考虑其辐射光强的空间分布。

（2）除了曲面的法向量外，均不考虑曲面的所有几何信息。这相当于将光源和视点均置于无穷远处。

（3）表面漫反射光亮度和镜面反射光亮度均被认为是对光源入射光的直接反射，且相互独立。（4）表面镜面反射光亮度由一经验模型来模拟。但当该光亮度达到显示器所能显示的最高色度时，其变化将被裁剪掉。

（5）用镜面高光指数n来模拟景物表面的光滑程度。镜面高光指数n的变化可使光源看上去变大或变小。

（6）镜面反射光的颜色被假定为光源的颜色，而与表面材料属性无关。

（7）周围环境对景物表面的影响，即环境光，被假定为常量。

7.4阴影

7.4.1阴影细节多边形算法

由于阴影是景物空间中光源不能直接照射到的区域，位于某一光源阴影区域中的景物表面被它与该光源之间的其他不透明表面所遮挡，因此，它是这一特定光源的隐藏面，画面上的阴影即为从视点可见，但从光源“不可见”的景物表面区域。显然，阴影生成的过程实际上是以光源为视点对场景中的景物进行消隐的过程。由于景物表面上的阴影区域仅跟光源与景物的相对位置有关而与视点的位置无关，当取不同视点观察同一场景时，场景中的阴影区域将保持不变。因此，若以光源为视点，按景物空间消隐算法求取景物表面上的阴影区域，并将它们作为阴影细节附着在表面多边形上，则在取不同视点绘制画面时，所生成的阴影细节多边形可反复使用，从而大大提高了阴影生成的效率。阴影细节多边形算法由Atherton、Weiler和Greenberg于1978年提出。该算法基于在景物空间中实现的WeilerAtherton消隐算法。算法可分为两步实现，首先取光源方向为视线方向进行消隐，确定对光源不可见的表面阴影细节多边形，并通过赋予相同的标识数将它们与所覆盖的原始景物多边形联系在一起。算法的第二步是取视线方向对景物进行第二次消隐。注意阴影细节多边形只是一种表面细节，它们并不作为独立的景物多边形加入第二次消隐。在绘制时，如果多边形上某一部分相对视点可见，但被阴影细节多边形所覆盖，那么该区域的光亮度可按阴影处理。在采用WeilerAtherton消隐算法求取表面的阴影细节多边形时，首先要将场景中所有景物多边形按它们离光源的远近进行排序，然后取距光源最近的景物多边形作为窗口对位于其后的景物多边形进行裁剪。显然，后面多边形中位于窗口之内的部分将被距光源最近的景物多边形所遮挡，成为该光源的阴影细节多边形。对于位于窗口之外的景物多边形，依序取其中离光源最近的多边形作为裁剪窗口，对位于其后的多边形进行裁剪。以上步骤可递归进行，直至在最后一个裁剪窗口之外再不存在任何场景多边形或其中一部分为止。不难发现，在上述递归过程中，作为裁剪窗口的所有场景多边形区域均受到光源的直接照射，场景多边形中的其余部分则构成了该光源的阴影多边形。

Atherton等采取了下述策略来简化数据结构。

第一，保存景物表面受到光源直接照射的部分，即光照多边形，而不是阴影多边形。这不仅是由于在消隐过程中，保存光源可见面即裁剪窗口多边形容易实现，而且是由于就单一光源而言，其光照多边形的数量一般少于阴影多边形的数量。注意，背向光源的自身阴影表面已在背面剔除预处理中消去。第二，对光照多边形注以标记并变换回到景物坐标系，然后作为表面细节附着在原多边形表面上。具体实现时，可将场景中每一表面多边形赋予一标识数。场景中所有表面变换到光源坐标系并以光源为视点进行消隐后，保存下来的光照多边形仍持有原所在多边形的标识数。当这些光照细节多边形变换回到景物坐标系中后，很容易根据其标识数将它们与原所在表面联系起来，在绘制时，仅对这部分表面计入光源的直接光照效果。7.4.2影域多面体算法

在景物空间中，若光源直接照射的表面为不透明面，则在该表面后将形成一个三维的阴影区域，我们将其简称为影域（ShadowVolume）。显然，影域是一个以光源直接照射面为顶面，其轮廓边与光源所张平面为侧面而形成的一个半开放区域，任何包含于影域之内的景物表面必处于该光源的阴影之中。由于屏幕上仅显示位于视域四棱锥之内的场景，因此，可用视域四棱锥对三维影域进行裁剪。由影域多面体的定义确定场景中任一景物表面上的阴

影区域时，只需求取该表面与影域多面体的布尔交。显然，这将涉及复杂的三维布尔运算。由于在景物空间中存在大量的光源直接照射面，每一个直照面对于给定的光源都将形成一个独立的影域多面体，从而使在景物空间中基于影域多面体直接求解景物表面上的区域的计算复杂度大大增加。

1977年，Crow提出了在图像空间中判定景物表面或景物表面的一部分是否内含于影域多面体之内的解法。该阴影生成算法基于扫描线消隐算法，在绘制时，将所有的阴影边界多边形如同普通景物多边形一样参加扫描和排序。每一条扫描线在图像空间中定义了一个垂直于成像平面的水平面，称为扫描平面，该扫描平面与场景中景物多边形相交，形成了一系列截交线段。图7.28所示为一可见景物表面与一影域多面体在当前扫描平面上的截交线，其中P是扫描平面与可见景物表面的交线，S1、S2、S3和S4分别为影域多面体上的阴影边界多边形与当前扫描平面的交线。根据P与S1、

S2、S3和S4相交的情况，可将P在扫描线上的投影划分为三个区间。在区间Ⅰ和区间Ⅲ，穿过每一像素中心的视线在到达可见景物P之前或穿过偶数个影域边界多边形，或不穿过任何阴影边界多边形。显然，P在区间Ⅰ，Ⅲ之内的区段位于影域多面体之外，它们受到了光源的直接照射。而穿过区间Ⅱ内每一像素中心的视线在到达可见景物表面P之前，只穿过一个阴影边界多边形，故P位于区间Ⅱ之内的区段包含于影域多面体之内而为阴影所覆盖。注意