计算机图形学隐面算法

计算机图形学隐面算法第一页，共三十一页，编辑于2023年，星期一消除隐藏面隐面算法用于消除物体上不可见的表面主要针对表面模型，不仅要求画出物体的各个可见棱边，而且还要求填充各个表面点取样算法画家算法Z缓冲区算法扫描线算法区域采样算法在绘制物体真实图形时，总是在投影面取一组离散点，在各离散点解决消隐问题，以确定颜色、亮度，用于显示屏幕上的像素。第二页，共三十一页，编辑于2023年，星期一消除隐藏面

画家算法画家算法基本思想：

画家的作画时，先涂背景色，然后由远及近的将景物画上，顺序暗示出所画物体之间的相互遮挡关系。所以称为画家算法。因此，画家算法又被称为深度排序算法或表优先级算法。基本原理：1）先把屏幕置成背景色；2）将场景中的物体的各个面按其距观察点的远近进行排序，结果放在一张线性表中；（线性表构造：距观察点远的优先级低，放在表头；距观察点近的优先级高，放在表尾）该表称为深度优先级表。3）然后按照从远到近（从表头到表尾）的顺序逐个绘制物体表面。第三页，共三十一页，编辑于2023年，星期一消除隐藏面

画家算法深度优先级表的建立一、多边形优先级的考虑首先对一个简单的画面，可以直接建立一个确定的深度优先表如图（a）所示。深度方向上无重叠。当画面略微复杂一点，无法按简单的Z向排序建立确定的深度优先表，以确定每一个多边形的优先级，如图（b）所示。深度方向上有重叠QXZPRQXZP（a）（b）R第四页，共三十一页，编辑于2023年，星期一消除隐藏面

画家算法深度优先级表的建立二、投影重叠判断：测试按照难度递增顺序排列：yyy包围盒定义：一个形体的包围盒指的是包围它的简单形体。一个好的包围盒要具有两个条件：包围和充分紧密包围着形体；对其的测试比较简单。

1.P和Q在oxy平面上投影的包围盒在x方向上不相交，图a；2.P和Q在oxy平面上投影的包围盒在y方向上不相交,图b；3.P在Q之后。P的各顶点均在Q的远离视点的一侧,图d；4.Q在P之前。Q的各顶点均在P的靠近视点的一侧,图e；5.P和Q在观察平面oxy上的投影不相交,图c；上面5项只要有一项成立，P就不遮挡Q，不需要重新排序第五页，共三十一页，编辑于2023年，星期一消除隐藏面

画家算法深度优先级表的建立对于某一重叠表面，上述五项测试均不成立，则需在有序表中调换两个面的位置。S,S,S

S,S,SSSSzS,S

S,S有重叠SS调换两个面的位置后，需要对调换过顺序的表面重复上述5项测试……第六页，共三十一页，编辑于2023年，星期一消除隐藏面

画家算法深度优先级表的建立解决方法是沿多边形所在平面间的交线循环分割这些多边形。无法直接建立正确的深度优先表第七页，共三十一页，编辑于2023年，星期一消除隐藏面

画家算法排序计算量大；多边形相交或循环重叠时，必须分割多边形。画家算法的不足：第八页，共三十一页，编辑于2023年，星期一消除隐藏面

Z缓冲区算法Z缓冲区算法基本思想：

投影平面每个像素所对应的所有面片（平面或曲面）的深度进行比较，然后取离视线最近面片的属性值作为该像素的属性值。

Z缓冲器算法基本思想第九页，共三十一页，编辑于2023年，星期一消除隐藏面

Z缓冲区算法实现方法帧缓存区深度缓存区存放每个像素的深度值。Z缓冲器每个单元存放对应像素当前最近面的深度值存放每个像素的颜色值。帧缓冲器每个单元存放对应像素的颜色值屏幕第十页，共三十一页，编辑于2023年，星期一消除隐藏面

Z缓冲区算法算法描述：for(v=0;v<vmax;v++)for(u=0;u<umax;u++){将帧缓冲器的第(u,v)单元置为背景色；将Z缓冲器的第(u,v)单元置为最小深度值；}for(每个多边形）for(多边形在投影平面上的投影区域内的每个像素(u,v)){计算多边形在当前像素(u,v)处的深度值d； if(d>Z缓冲器的第(u,v)单元的值) {置帧缓冲器的第(u,v)单元值为当前多边形颜色； 置Z缓冲器的第(u,v)单元值为d;}}帧缓冲器各单元均置为背景色，深度缓冲器所有单元均置为最小z值，然后逐个处理多边形表中的各面片。计算各像素点（x，y）所对应的深度值z（x，y），并将结果与深度缓冲器中该像素单元所存储的深度值ZB（x，y）进行比较。若z＞ZB（x，y）,则ZB（x，y）=z，同时将该像素的颜色值I（x，y）写入帧缓冲器，即IB（x，y）=I（x，y）；否则不变。第十一页，共三十一页，编辑于2023年，星期一消除隐藏面

Z缓冲区算法深度值的计算若已知多边形的方程，则可用增量法计算扫描线每一个像素的深度。设平面方程为：

C≠0

则多边形面上的点（x，y）所对应的深度值为：第十二页，共三十一页，编辑于2023年，星期一消除隐藏面

Z缓冲区算法深度值的计算

由于所有扫描线上相邻点间的水平间距为1个像素单位，扫描线行与行之间的垂直间距也为1。因此可以利用这种连贯性来简化计算过程，如图所示。

若已计算出（x，y）点的深度值为zi，沿x方向相邻连贯点（x+1，y）的深度值zi+1可由下式计算：第十三页，共三十一页，编辑于2023年，星期一消除隐藏面

Z缓冲区算法深度值的计算沿多边形左边界递归计算边界上各点的坐标：

m为该边的斜率，沿该边的深度也可以递归计算出来，即：如果该边是一条垂直边界，则计算公式简化为：第十四页，共三十一页，编辑于2023年，星期一消除隐藏面

Z缓冲区算法深度值的计算对于每条扫描线，首先根据公式计算出与其相交的多边形最左边的交点所对应的深度值，然后，利用图形连贯性将该扫描线上所有的后续点计算出来。所有的多边形处理完毕，即得消隐后的图形。

第十五页，共三十一页，编辑于2023年，星期一消除隐藏面

Z缓冲区算法Z缓冲区算法的优缺点：优点1.简单稳定，利于硬件实现2.Z缓冲器算法的最大优点：Z缓存器算法在像素级上以近物取代远物。形体在屏幕上的出现顺序是无关紧要的。可以轻而易举地处理隐藏面以及显示复杂曲面之间的交线。缺点1.需要一个额外的Z缓冲器，需更大的存储空间，例如，当像素数目为500*500时，就需要250K个深度值的存储空间。深度值一般用浮点数表示，每个数占4个字节，故共需要1M字节的额外存储空间。2.在每个多边形占据的每个像素处都要计算深度值，计算量大。第十六页，共三十一页，编辑于2023年，星期一消除隐藏面

扫描线算法扫描线算法

基本思想：按扫描行的顺序处理一帧画面，在由视点和扫描线所决定的扫描平面上解决消隐问题。

基本步骤：把物体各面投影到屏幕上计算扫描线与物体各投影面的相交区间。当两个区间在深度方向上重叠时，采用深度测试确定可见部分。典型实现：扫描线Z缓冲区算法扫描线间隔连贯性算法第十七页，共三十一页，编辑于2023年，星期一消除隐藏面

扫描线算法扫描线Z缓冲器每个单元存放对应像素当前最近面的深度值（每一个扫描线用一个缓冲器）扫描线Z缓冲区算法第十八页，共三十一页，编辑于2023年，星期一消除隐藏面

扫描线算法3,2,107,2,107,4,103,4,101234z=103,5,08,4,208,0,20123Z=(4x-12)0410101010101216101010101012162016202020……第十九页，共三十一页，编辑于2023年，星期一消除隐藏面

区域采样算法区域采样算法

区域采样算法是利用图形的区域连贯性，在连续的区域上确定可见面及其颜色、亮度。基本思想：

把物体投影到全屏幕窗口上，然后递归地分割窗口，直到窗口内目标足够简单，可以直接显示为止。基本步骤：首先将场景中的多边形投影到绘图窗口内，判断窗口是否足够简单，若是，则算法结束；否则将窗口进一步分为四块。对此四个小窗口重复上述过程，直到窗口仅为一个像素大小。此时可能有多个多边形覆盖了该像素，计算它们的深度值，以最近的颜色显示该像素即可。第二十页，共三十一页，编辑于2023年，星期一消除隐藏面

区域采样算法如何判断窗口是否足够简单

存在下列情况之一即可称为窗口足够简单：

1）窗口为空，即多边形与窗口的关系是分离的，图a；

2）窗口内仅含一个多边形，即有一个多边形与窗口的关系是包含或相交。此时先对多边形投影进行裁剪，再对裁剪结果进行填充，图b、c。【判别方法：借助剪裁算法来解决，这里不必求出交点和进行裁剪，只要判断出多边形含于窗口内，或多边形某边与窗口某边有相交即可。】

3）有一个多边形的投影包围了窗口，并且它是最靠近观察点的，以该多边形颜色填充窗口，图d。第二十一页，共三十一页，编辑于2023年，星期一消除隐藏面

区域采样算法

如何判断包围和分离的关系？转角累计检查法:按顺时针方向或逆时针方向绕多边形依次累加多边形各边起点与终点对窗口内任意一点所张的夹角。按累计角度之和可以判定：若角度之和等于0，则表示多边形与窗口分离；若角度之和等于±360º*n，则表示多边形包围窗口(n次)。多边形窗口窗口多边形α第二十二页，共三十一页，编辑于2023年，星期一消除隐藏面

区域采样算法

如何判断包围和分离的关系？区域检查法:区域编码多边形顶点编码多边形边的编码多边形的编码区域编码窗口四条边所在直线将屏幕划分成9个区域，对窗口以外的8个区域按逆时针（或顺时针）进行编码，编码为0~7。

多边形顶点编码多边形v0v1…vn的顶点vi的投影落在哪个区域，那个区域的编码便作为该顶点的编码，记为Vi。第二十三页，共三十一页，编辑于2023年，星期一消除隐藏面

区域采样算法

如何判断包围和分离的关系？区域检查法:区域编码多边形顶点编码多边形边的编码多边形的编码多边形边的编码多边形的边vivi+1的编码定义为Vi(i+1)=vi+1-vi，令Vn(n+1)=Vn0i=0,1…n；当Vi(i+1)>4时，取Vi(i+1)=Vi(i+1)-8；当Vi(i+1)<-4时，取Vi(i+1)=Vi(i+1)+8；当Vi=±4时，取该边与窗口边的延长线的交点将该边分为两段，对两段分别按上面的规则编码，再令Vi(i+1)等于两者之和。多边形的编码定义多边形的编码为其边的编码之和，则第二十四页，共三十一页，编辑于2023年，星期一消除隐藏面

区域采样算法

例：STEP1：区域编码STEP2：多边形顶点编码v0=1,v1=3,v2=7,STEP3：多边形边的编码V01=3-1=2,V12=7-3=4,V20=1-7=-6(＜-4),故V20=-6+8=2。STEP4：多边形的编码V01+V12+V20=2+（-4）+2=0。取v1v2与窗口上边所在直线的交点v’将其分为两段，两段的编码分别为-2，6（＞4，故为6-8=-2），

从而V12=-2+（-2）=-4。因此，多边形与窗口分离。第二十五页，共三十一页，编辑于2023年，星期一消除隐藏面

区域采样算法

STEP2：多边形顶点编码V0=5,V1=7,V2=3,STEP3：多边形边的编码V01=7-5=2,V12=3-7=-4,V20=5-3=2.STEP4：多边形的编码V01+V12+V20=2+4+2=8。取v1v2与窗口上边所在直线的交点v’将其分为两段，两段的编码分别为-6(＜-4，故为-6+8=2)，2从而V12=2+2=4。因此，多边形与窗口关系是包围。例：STEP1：区域编码第二十六页，共三十一页，编辑于2023年，星期一消除隐藏面

区域采样算法

颜色显示在判断结束，确保“窗口中目标简单”以后，应判断出以下三种情况：①窗口为空，不含任何物体，这是显示为背景色；②窗口内含有一个多边形（内含或相交），这时用窗口对多边形剪裁，显示多边