计算机图形学基础教程第2章-光栅图形学(第二版)(孙家广-胡事民编著)(共25页).doc

《计算机图形学基础教程第2章-光栅图形学(第二版)(孙家广-胡事民编著)(共25页).doc》由会员分享，可在线阅读，更多相关《计算机图形学基础教程第2章-光栅图形学(第二版)(孙家广-胡事民编著)(共25页).doc（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上第二次课第2章 光栅图形学光栅图形显示器相当于一个象素的矩阵。图形的扫描转换（或图形的光栅化）：确定最佳逼近图形的象素集合，并用指定属性写象素的过程。重要概念及算法：区域填充：二维图形的光栅化必须确定区域对应的象素集，并用指定的属性或图案显示之。裁剪：确定一个图形的哪些部分在窗口内，必须显示；那些部分落在窗口之外，不该显示的过程。走样反走样：光栅化时，由于显示器分辨率有限，对于非水平、非垂直的直线，因象素逼近误差，使所画图形产生畸变（台阶、锯齿）的现象称之为走样。用于减少或消除走样的技术称为反走样。隐藏消隐：隐藏部分是不可见的，如果不删除隐藏的线或面，可能对图形错误理

2、解。因此必须把隐藏的部分从图中删除，称为消隐。2.1 直线段的扫描转换算法直线的扫描转换：确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。三个常用算法：l 数值微分法（DDA）l 中点画线法l Bresenham算法2.1.1 数值微分(DDA)法基本思想：已知过端点的直线段L：，直线斜率为 ，从x的左端点x0开始，向x右端点步进，步长=1(个象素)，计算相应的y坐标y=kx+b；取象素点(x, round(y)作为当前点的坐标。l 作为最底层的光栅图形算法，在通常的CAD/图形系统中，会被大量应用，因此，哪怕节约一个加法或减法，也是很了不起的改进。l 由此出发点，导致

3、增量算法的思想。计算当时；即：当x每递增1，y递增k(即直线斜率) 。算法程序2-1 （P18）例：画直线段，DDA算法演示。 2.1.2 中点画线法基本思想：当前象素点为(xp, yp) ，下一个象素点为P1或P2。设M=(xp+1, yp+0.5)，为P1与P2之中点，Q为理想直线与x=xp+1垂线的交点。将Q与M的y坐标进行比较。l 当M在Q的下方，则P2应为下一个象素点；l M在Q的上方，应取P1为下一点。构造判别式：d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c其中a=y0-y1, b=x1-x0, c=x0y1-x1y0n 当d0，M在L(Q点

4、)上方，取右方P1为下一个象素；n 当d=0，选P1或P2均可，约定取P1为下一个象素；可采用增量计算，提高运算效率：l 若d0，则取正右方象素P1 (xp+1, yp)，要判下一个象素位置，应计算d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a；增量为a。l 若d0，则取右上方象素P2 (xp+1, yp+1)。要判断再下一象素，则要计算d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b ；增量为ab。画线从(x0, y0)开始，d的初值：d0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b=a+0.5

5、b。可以用2d代替d来摆脱小数，提高效率。令d0=2a+b，d1=2a，d2=2a+2b。算法程序2-2 （P19）例：用中点画线法中点画线算法演示2.1.3 Bresenham算法基本思想：过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素。设直线方程为：yi+1= yi+k(xi+1-xi)= yi+k，其中k=dy/dx。 因为直线的起始点在象素中心，所以误差项d的初值d0=0。x下标每增加1，d的值相应递增直线的斜率值k，即ddk。一旦d1，就把它减去1，这样保证d在0、1之间。l 当d0.5

6、时，最接近于当前象素的右上方象素(xi+1,yi+1)，y方向加1，d减去1；l 而当d0.5时，更接近于右方象素(xi+1,yi)。为方便计算，令ed-0.5，e的初值为-0.5，增量为k。l 当e0时，取当前象素（xi，yi）的右上方象素(xi+1,yi+1)，e减小1；l 而当e0时，更接近于右方象素(xi+1,yi)。算法程序2-3 （P21）例：Line: P0(0, 0), P1(5,2) k=dy/dx=0.4，图示可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换： 。最终，Bresenham算法也是每个象素，需一个整数算法，其优点是可以用于其他二次曲线。第

7、三次课2.2 圆弧的扫描转换算法圆的特征：八对称性，只要扫描转换八分之一圆弧，就可以求出整个圆弧的象素集。中点画圆法：考虑中心在原点，半径为R的第二个8分圆。构造判别式（圆方程）：l 若 d=0, 则应取P2为下一象素，而且下一象素的判别式第一个象素是（0,R），判别式d的初始值为。算法程序2-5 （P22）为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。使用e=d-0.25代替d，e0=1-R。中点画圆算法演示2.3 多边形的扫描转换与区域填充多边形有两种重要的表示方法：顶点表示和点阵表示。多边形的扫描转换：把多边形的顶点表示

8、转换为点阵表示。区域可采用内点表示和边界表示两种表示形式。区域填充：指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。多边形分为凸多边形、凹多边形、含内环的多边形。2.3.1 多边形的扫描转换2.3.1.1 扫描线算法基本思想：按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。对于一条扫描线填充过程可以分为四个步骤：l 求交 计算扫描线与多边形各边的交点。l 排序 把所有交点按x值的递增顺序排序。l 配对 将第1个与第2个、第3个与第4个交点配对每对交点代表扫描线与多边形的一个相交区间。l 填色 把相交区间内的象素置成多边形的颜色，把

9、相交区间外的象素置成背景色。图2-8扫描线与多边形的顶点或边界相交时，必须正确的交点的取舍。只需检查顶点的两条边的另外两个端点的y值。按这两个y值中大于交点y值的个数是0,1,2来决定。 图2-11数据结构：l 活性边表(AET)：把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中。l 结点内容：x：当前扫描线与边的交点坐标x：从当前扫描线到下一条扫描线间x的增量ymax：该边所交的最高扫描线号ymaxl 新边表（NET）：存放在该扫描线第一次出现的边。若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中。图2-10假定当前扫描线与多边形某一条

10、边的交点的横坐标为x，则下一条扫描线与该边的交点不需要重新计算，只要加一个增量x。设该边的直线方程为：ax+by+c=0。若yyi，x=xi；则当y = yi+1时，其中为常数。算法程序2-6图2-8中多边形的AET和填充过程：5 -3 25 3 3 2 0 78 3 3 填充5,5)填充2,8)扫描线1扫描线22 0 711 0 8 填充2,11)扫描线32 0 711 0 8 填充2,11)扫描线42 0 7扫描线55 2 85 -1.5 7填充2,5) 5,11)11 0 8 2 0 7扫描线67 2 83.5 -1.5 7填充2,3.5) 7,11)11 0 8 扫描线79 2 811

11、 0 8 填充9,11)扫描线8扫描线0初始化2.3.1.2 边界标志算法基本思想：l 帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上标志。l 然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。l 使用一个布尔量inside来指示当前点是否在多边形内的状态。l Inside的初值为假，每当当前访问的象素为被打上边标志的点，就把inside取反。对未打标志的象素，inside不变。 l 若访问当前象素时，inside为真，说明该象素在多边形内，则把该象素置为填充颜色。 用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，但由于边界标志算法不

12、必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。2.3.2 区域填充算法l 区域指已经表示成点阵形式的填充图形，它是象素的集合。l 区域可采用内点表示和边界表示两种表示形式。l 区域可分为4向连通区域和8向连通区域。l 区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的。l 4向连通区域和8向连通区域2.3.2.1 区域填充的递归算法内点表示的4连通区域的递归填充算法，算法程序2-8边界表示的4连通区域的递归填充算法，算法程序2-92.3.2.2 区域填充的扫描线算法算法基本过程

13、：l 首先填充种子点所在扫描线上的位于给定区域的一个区段；l 然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来；l 反复这个过程，直到填充结束。(1) 初始化：堆栈置空。将种子点（x，y）入栈。(2) 出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。(3) 填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。(4) 并确定新的种子点：在区间xl，xr中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压

14、入堆栈，返回第（2）步。上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充算法提高了区域填充的效率。例题图示，共6幅图，未完成部分由学生思考完成2.4 字符字符指数字、字母、汉字等符号。计算机中字符由一个数字编码唯一标识。国际上最流行的字符集：“美国信息交换用标准代码集” （American Standard Code for Information Interchange），简称ASCII码。它是用7位二进制数进行编码表示128个字符；包括字母、标点、运算符以及一些特殊符号。汉字编码的国家标准字符集GB2312-80，94个区，94个位，符号 = 1个区码 + 1个位码用字节的最高

15、位标识，最高位为0表示ASCII码；最高位为1表示汉字编码。字库：存储每个字符的形状信息，分为点阵型和矢量型。2.4.1 点阵字符点阵字符：每个字符由一个位图表示，该位为1表示字符的笔画经过此位，对应于此位的象素应置为字符颜色。该位为0表示字符的笔画不经过此位，对应于此位的象素应置为背景颜色。图2-15在实际应用中，有多种字体（如宋体、楷体等），每种字体又有多种大小型号，因此字库的存储空间是很庞大的。解决这个问题一般采用压缩技术。点阵字符的显示分为两步。首先从字库中将它的位图检索出来。然后将检索到的位图写到帧缓冲器中。2.4.2 矢量字符2.4.2.1 相关概念在一个使用X-Y坐标系的平面中，

16、对于一个有确定方向的线段，若已知：l 一个端点（如起点）坐标l 线段长度l 线段与X座标轴正方向的夹角角度值就可以画出平面内的一个有向线段矢量，那么：(1) 矢量的方向是线段起点指向线段的终点，(2) 矢量X坐标轴正方向的夹角是指，以矢量起点为旋转中心，该矢量从与X轴正向平行、且方向相同的位置逆时针旋转至当前位置所经过的旋转角度，记作LDA。在一个使用X-Y坐标系的平面中，一个有确定方向的线段（即矢量），有以下特征：l 起点的坐标l 线段的长度l LDA值YOA(x0,y0)LDAB(x1,y1)X2.4.2.2 矢量字符构建定义：(1) 字符由线段构成；(2) 每条线段有方向；(3) 构成字

17、符的所有线段是连续的，即首尾相连；(4) 每条线段有三个属性：a.长度；b.LDA值；c.可见性；(5) 整个字符图形只有一个起点和一个终点；(6) 起点位于右下角。矢量字符构造步骤：(1) 使用起点作为第一个矢量线段的端点；(2) 将矢量线段置于水平位置，线段方向与X轴正向相同，以起点为中心，旋转角度为LDA；(3) 以矢量线段的终点作为下一个线段的起点，重复(1)(2)，直到所有的矢量线段被放在正确的位置上。2.4.2.3 矢量字符举例特点：l 点阵字符：存储量大，易于显示l 矢量字符：存储量小，美观，变换方便；但需要光栅化后才能显示。2.4.3 字符属性l 字体： l 字高：l 字宽因子

18、：l 字倾斜角：l 对齐：l 字色：l 写方式：“替换”方式，字符掩膜中空白区置成背景色；“与”方式，空白区颜色不受影响。字符掩膜：包含表示该字符的象素图案的一小块光栅。2.5 裁剪裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外，以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。图2-16最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗内。但那样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法。2.5.1 直线段裁剪直线段裁剪算法是复杂图元裁剪的基础。复杂的曲线可以通过折线段来近似，

19、从而裁剪问题也可以化为直线段的裁剪问题。l Cohen-Sutherlandl 中点分割算法l 梁友栋barskey算法2.5.1.1 Cohen-Sutherland裁剪算法算法：对于每条线段P1P2分为三种情况处理：(1) 若P1P2完全在窗口内，则显示该线段P1P2简称“取”之。(2) 若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。(3) 若线段不满足“取”或“弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。编码：为快速判断，采用如下编码方法：每个区域赋予4位编码CtCbCrCl。定义：图2-17，18先求出P1P2所在的区号code1

20、，code2。若code1=0且code2=0，则P1P2完全在窗口内，“取”之；若按位与运算code1&code20，则P1P2明显在窗口外，“弃”之；否则求出线段与窗口某边的交点，在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。算法程序2-11 #define LEFT 1 /0001#define RIGHT 2 /0010#define BOTTOM 4 /0100#define TOP 8 /1000“|”按位或，如c|=LEFT即c=c|LEFT=0000|0001=0001“&”按位与XLXRYBYTP1code1=0000P2code2=0000

21、“|”或“&”与更正：if(yYT)c|=TOP;求交部分算法示例1：code1=0000；XLXRYBYTP1code1=1001P2code2=0001code2=0000；不进入while循环；displaylineP1P2。示例2：code1=1001；code2=0001；进入while循环；code1&code2=00010；return，即不绘制线段。XLXRYBYTP1code1=1001P2code2=0110示例3：code1=1001；code2=0110；进入while循环； code10 code=code1=1001即从P1点开始求交；LEFT & code=000

22、1&1001=00010即端点P1在左；XLXRYBYTP1code1=0000P2code2=0110求左交点(XL,y)；code=code1=1001 左交点为新的P1点，且code1=0000；进入第二次循环；code1=0 code=code2=0110即从P2点开始求交；BOTTOM & code=0100&0110=01000XLXRYBYTP1code1=0000P2code2=0000即端点P2在下；求下交点(x,YB)；code=code2=0110下交点为新的P2点，且code2=0000；此时，code1=code2=0000； 跳出循环；displaylineP1P2

23、。2.5.1.2 中点分割裁剪算法基本思想：与前一种Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况：全在、完全不在和线段和窗口有交。对前两种情况，进行一样的处理。对于第三种情况，用中点分割的方法求出线段与窗口的交点。图2-19描述算法：求线段与窗口的交点，A、B分别为距P0、P1最近的可见点，Pm为P0P1中点。AB之间的连线即为线段P0P1的可见部分。l 从P0出发找最近可见点A的方法先求出P0 P1 的中点Pm若P0Pm不是显然不可见的，并且P0 P1在窗口中有可见部分，则距P0最近的可见点一定落在 P0 Pm上，所以用P0 Pm代替P0

24、P1 ；否则取 PmP1代替P0 P1 再对新的P0 P1求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常数为止，此时Pm收敛于交点。l 从P1出发找最近可见点B采用上面类似方法。作业：按中点分割裁剪算法，求出点A、B的坐标，控制常数为1。P0(-2,3)P1(3,-1)PmABXL=0XR=4YB=0YT=42.5.1.3 梁友栋-Barskey裁剪算法描述算法：梁-Barsky算法的几何含义：入边、出边与端点。入边出边端点参数化形式写出裁剪条件：可以统一表示为形式：更正：q3=y1-YB当pk=0，即直线平行于裁剪边界（其中k=1，2，3，4对应左、右、下、上边界）若qk0，则线

25、段完全在边界外；若qk0，则该线段平行于裁剪边界并且在窗口内；当pk0，若pk0，线段从裁剪边界延长线的内部延伸到外部。可计算出线段与边界k的延长线的交点的u值：u= qk/pk。对于每条直线，可以计算出参数u1和u2，它们定义了在裁剪矩形内的线段部分。l u1的值由线段从外到内遇到的矩形边界所决定（p0）。对这些边界计算rk=qk/pk 。u2取1和各个rk值之中的最小值。l 如果u1u2，则线段完全落在裁剪窗口之外，被舍弃。l 否则裁剪线段由参数u的两个值u1，u2计算出来。对三种算法比较：l Cohen-Sutherland与中点法在区域码测试阶段能以位运算方式高效率地进行，因而当大多数

26、线段能够简单的取舍时，效率较好。l 梁友栋Barskey算法只能应用于矩形窗口的情形，但其效率比前两者要高，这是因为运算只涉及到参数，仅到必要时才进行坐标计算。2.5.2 多边形裁剪Sutherland-Hodgeman算法：l 基本思想是一次用窗口的一条边裁剪多边形。l 考虑窗口的一条边以及延长线构成的裁剪线，该线把平面分成两个部分：可见一侧；不可见一侧。l 多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种，图2-20，S、P与裁剪线的位置关系对于l 情况（1）仅输出顶点P；l 情况（2）输出0个顶点；l 情况（3）输出线段SP与裁剪线的交点I；l 情况（4）输出线段SP与裁剪线

27、的交点I和终点P上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。对于每一条裁剪边，只是判断点在窗口哪一侧改变求线段SP与裁剪边的交点的算法。图2-21；裁剪例题示意图2.5.3 字符裁剪按三个精度裁剪：l 串精度：将包围字串的外接矩形对窗口作裁剪l 字符精度：将包围字的外接矩形对窗口作裁剪l 画笔或象素精度：将笔划分解成直线段对窗口作裁剪2.6 反走样走样：用离散量表示连续量引起的失真现象称之为走样(aliasing)。反走样：用于减少或消除这种效果的技术称为反走样(antialiasing)。光栅图形的走样现象： (1) 锯齿现象（图示）(2) 图形

28、细节失真（图示）(3) 微小对象遗失与动态图形闪烁（图示）常用的反走样方法：(1) 提高分辨率(2) 区域采样 非加权区域采样（盒式滤波器） 加权区域采样（圆锥形滤波器、半球形滤波器等）2.6.1提高分辨率把显示器分辨率提高一倍，直线经过两倍的象素，锯齿也增加一倍，但同时每个阶梯的宽度也减小了一倍，所以显示出的直线段看起来就平直光滑了一些。增加分辨率虽然简单，但是不经济的方法，有物理上的困难；而且它也只能减轻而不能消除锯齿问题。2.6.2 非加权区域采样基本思想：每个象素是一个具有一定面积的小区域，将直线段看作具有一定宽度的狭长矩形。当直线段与象素有交时，求出两者相交区域的面积，然后根据相交区

29、域面积的大小确定该象素的亮度值。面积计算：l 情况(1)(5)阴影面积为：D2/2m；l 情况(2)(4)阴影面积为：D-m/2；l 情况(3)阴影面积为：1-D2/m为了简化计算可以采用离散的方法：l 首先将屏幕象素均分成n个子象素；l 然后计算中心点落在直线段内的子象素的个数k；l 将屏幕该象素的亮度置为相交区域面积的近似值可k/n。非加权区域采样方法有两个缺点：l 象素的亮度与相交区域的面积成正比，而与相交区域落在象素内的位置无关，这仍然会导致锯齿效应。l 直线条上沿理想直线方向的相邻两个象素有时会有较大的灰度差。2.6.3 加权区域采样(1) 圆锥形滤波器为了克服非加权区域采样的两个缺

30、点，可采用更接近优化的圆锥形滤波器。该滤波器（加权函数）是一个圆锥。圆锥的底圆中心在当前象素中心，底圆半径为一个象素单位，锥高为1。当直线条经过该象素时，该象素的灰度值是在直线与圆锥相交区域上对滤波器进行积分的积分值。相当于使用过直线条两边缘，且垂直于象素区域的一对平面，切割圆锥所得到的厚度等于直线条宽度的三维物体的体积。圆锥形滤波器特点：l 接近理想直线的象素将被分配更多的灰度值。l 相邻两个象素的滤波器相交，所以直线条经过该相交区域时，将对这两个象素都分配给适当的灰度值，有利于缩小直线条上相邻象素的灰度差。(2) 离散计算方法：n 将屏幕划分为n=33个子象素，加权表可以取作：；n 计算每

31、个子象素对原象素的贡献，并保存在一张二维加权表中；n 然后求出所有中心落于直线段内的子象素集；n 最后计算所有这些子象素对原象素亮度贡献之和，该值乘以象素的最大灰度值作为该象素的显示灰度值。2.7 消隐消隐：为消除图形的二义性，绘制时消除被遮挡的不可见的线或面，称之为消除隐藏线或隐藏面。2.7.1 消隐的分类消除对象为三维物体，三维物体的表示有B-rep（Boundary representation，边界表示）和CSG（Constructive Solid Geometry，构造实体几何）表示。消隐分类：l 按对象：u 线消隐：消隐物体上不可见的边u 面消隐：消隐物体上不可见的面l 按空间：

32、u 物体空间的消隐算法：光线投射算法，Roberts算法（将场景中每一个面与其它各个面比较，求所有点、边、面的遮挡关系）u 图象空间的消隐算法：Z-Buffer算法，扫描线算法，Warnock算法 （对屏幕上每个象素进行判断，决定哪个多边形在该象素可见）u 物体空间和图象空间的消隐算法：画家算法 （在物体空间中预先计算面的可见性优先级，再在图象空间中生成消隐图）2.7.2 消除隐藏线(1) 对造型的要求 造型系统中要有面的信息，最好有体的信息。(2) 坐标变换视点是Z轴正无穷大处，视线方向变为Z轴的负方向。对视椎体以外的物体先作裁剪。(3) 最基本的运算判断面对线的遮挡关系，反复地进行线线、线

33、面之间的求交运算。 判断面对线的遮挡关系； 把体分解为面，再判断面与线的遮挡关系。算法：(1) 若线段的两端点及视点在给定平面的同侧，线段不被给定平面遮挡，转7(2) 若线段的投影与平面投影的包围盒无交，线段不被给定平面遮挡，转7(3) 求直线与相应无穷平面的交。若无交点，转4。否则，交点在线段内部或外部。若交点在线段内部，交点将线段分成两段，与视点同侧的一段不被遮挡，另一段在视点异侧，转4再判；若交点在线段外部，转4。(4) 求所剩线段的投影与平面边界投影的所有交点，并根据交点在原直线参数方程中的参数值求出Z值(即深度)。若无交点，转5。(5) 以上所求得的各交点将线段的投影分成若干段，求出

34、第一段中点。(6) 若第一段中点在平面的投影内，则相应的段被遮挡，否则不被遮挡；其他段的遮挡关系可依次交替取值进行判断。(7) 结束。 (4) 线消隐算法 基本数据结构：面表（存放参与消隐的面）+ 线表（存放待显示的线）画出数据结构 算法：为了提高算法的效率，需要设法减少求交的工作量。若V N0，称该多边形为后向面。若V N0，称该多边形为前向面。后向面总是看不见的，不会由于后向面的遮挡，而使别的棱成为不可见的。因此计算时，可以把这些后向面全部去掉，这并不影响消隐结果。 2.7.3 消除隐藏面(1) 画家算法算法描述：先把屏幕置成背景色，再把物体的各个面按其离视点的远近进行排序，排序结果存在一张深度优先级表中。然后按照从远到近的顺序逐个绘制各个面。关键是如何对场景中的物体按深度排序。对场景中的物体按深度排序：(1) 深度重叠测试设Zmin最小的多边形为P，多边形序列中其他多边形记为Q；因Zmin(P)Zmin(Q)，若Zmax(P) 0，则弧长代数和增加p；n 若f 0，则弧长代数和减少p。专心-专注-专业