计算机图形学 隐面算法课件

1、姓名：XX专业：XXXX导师：XX 教授学号：XXXXXXXXX隐面算法用于消除物体上不可见的表面主要针对表面模型，不仅要求画出物体的各个可见棱边，而且还要求填充各个表面点取样算法点取样算法画家算法Z缓冲区算法扫描线算法区域采样算法在绘制物体真实图形时，总是在投影面取一组离散点，在各离散点解决消隐问题，以确定颜色、亮度，用于显示屏幕上的像素。画家算法画家算法基本思想：基本思想： 画家的作画时，先涂背景色，然后由远及近的将景物画上，顺序暗示出所画物体之间的相互遮挡关系。所以称为画家算法。因此，画家算法又被称为深度排序算法或表优先级算法。基本原理：基本原理：1）先把屏幕置成背景色；2）将场景中的物

2、体的各个面按其距观察点的远近进行排序，结果放在一张线性表中；（线性表构造：距观察点远的优先级低，放在表头；距观察点近的优先级高，放在表尾 ）该表称为深度优先级表。3）然后按照从远到近（从表头到表尾）的顺序逐个绘制物体表面。深度优先级表的建立一、多边形优先级的考虑 首先对一个简单的画面，可以直接建立一个确定的深度优先表如图（a）所示。深度方向上无重叠。 当画面略微复杂一点，无法按简单的Z向排序建立确定的深度优先表，以确定每一个多边形的优先级，如图（b）所示 。深度方向上有重叠Q QX XZ ZP PR RQ QX XZ ZP P（a a）（b b）R R深度优先级表的建立二、投影重叠判断：测试按

3、照难度递增顺序排列：y yy yy y包围盒定义：一个形体的包围盒指的是包围它的简单形体。一个好的包围盒要具有两个条件：包围和充分紧密包围着形体；对其的测试比较简单。 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，不需要重新排序深度优先级表的建立对于某一重叠表面，上述五项测试均不成立，则需在有序表中调换两个面的位置。S

4、, SS, S , S, S S S , S, S , , S S S SS S S S z zS, SS, S S S , S , S 有重叠S S S S调换两个面的位置后，需要对调换过顺序的表面重复上述5项测试深度优先级表的建立解决方法是沿多边形所在平面间的交线循环分割这些多边形。无法直接建立正确的深度优先表 排序计算量大； 多边形相交或循环重叠时，必须分割多边形。画家算法的不足：画家算法的不足：Z Z缓冲区算法缓冲区算法基本思想基本思想： 投影平面每个像素所对应的所有面片（平面或曲面）的深度进行比较，然后取离视线最近面片的属性值作为该像素的属性值。 Z缓冲器算法基本思想实现方法帧缓存区

5、 深度缓存区存放每个像素的深度值。Z缓冲器每个单元存放对应像素当前最近面的深度值存放每个像素的颜色值。帧缓冲器每个单元存放对应像素的颜色值屏幕算法描述：算法描述：for ( v= 0;vvmax;v+) for (u= 0; u Z缓冲器的第(u,v)单元的值) 置帧缓冲器的第(u,v)单元值为当前多边形颜色； 置Z缓冲器的第(u,v)单元值为d; 帧缓冲器各单元均置为背景色，深度缓冲器所有单元均置为最小z值，然后逐个处理多边形表中的各面片。计算各像素点（x，y）所对应的深度值z（x，y），并将结果与深度缓冲器中该像素单元所存储的深度值ZB（x，y）进行比较。若zZB（x，y）,则ZB（x，y

6、）= z，同时将该像素的颜色值I（x，y）写入帧缓冲器，即IB（x，y）= I（x，y）；否则不变。深度值的计算若已知多边形的方程，则可用增量法计算扫描线每一个像素的深度。设平面方程为： 0DCzByAxCDByAxz)(C0C0 则多边形面上的点（x，y）所对应的深度值为：深度值的计算 CAzCDByxAziii)1(1由于所有扫描线上相邻点间的水平间距为1个像素单位，扫描线行与行之间的垂直间距也为1。因此可以利用这种连贯性来简化计算过程，如图所示。 若已计算出（x，y）点的深度值为zi，沿x方向相邻连贯点（x+1，y）的深度值zi+1可由下式计算：深度值的计算沿多边形左边界递归计算边界上各

7、点的坐标： mxxii11CBmAzCDyBmxAziiii)1()1(1CBzzii 1m为该边的斜率，沿该边的深度也可以递归计算出来，即：如果该边是一条垂直边界，则计算公式简化为：深度值的计算对于每条扫描线，首先根据公式计算出与其相交的多边形最左边的交点所对应的深度值，然后，利用图形连贯性将该扫描线上所有的后续点计算出来。所有的多边形处理完毕，即得消隐后的图形。 Z Z缓冲区算法的优缺点：缓冲区算法的优缺点：优点1. 简单稳定，利于硬件实现2.Z缓冲器算法的最大优点 ：Z缓存器算法在像素级上以近物取代远物。形体在屏幕上的出现顺序是无关紧要的。可以轻而易举地处理隐藏面以及显示复杂曲面之间的交

8、线。缺点1.需要一个额外的Z 缓冲器，需更大的存储空间，例如，当像素数目为500*500时，就需要250K个深度值的存储空间。深度值一般用浮点数表示，每个数占4个字节，故共需要1M字节的额外存储空间。2.在每个多边形占据的每个像素处都要计算深度值，计算量大。扫描线算法扫描线算法 基本基本思想思想： 按扫描行的顺序处理一帧画面，在由视点和扫描线所决定的扫描平面上解决消隐问题。 基本步骤：基本步骤：把物体各面投影到屏幕上计算扫描线与物体各投影面的相交区间。当两个区间在深度方向上重叠时，采用深度测试确定可见部分。典型实现：典型实现：扫描线Z缓冲区算法扫描线间隔连贯性算法扫描线扫描线Z Z缓冲缓冲器器

9、每个单元存放每个单元存放对应像素对应像素当前最近面的深度值当前最近面的深度值（每一个扫描线用一个缓冲器）（每一个扫描线用一个缓冲器）扫描线Z缓冲区算法3,2,103,2,107,2,107,2,107,4,107,4,103,4,103,4,101 12 23 34 4z=10z=103,5,03,5,08,4,208,4,208,0,208,0,201 12 23 3Z=(4x-12)0 04 41010 1010 1010 1010 10101212 16161010 1010 1010 1010 10101212 1616 20201616 202020202020区域采样算法区域采样算

10、法 区域采样算法区域采样算法是利用图形的区域连贯性，在连续的区域上确定可见面及其颜色、亮度。基本基本思想思想： 把物体投影到全屏幕窗口上，然后递归地分割窗口，直到窗口内目标足够简单，可以直接显示为止。基本步骤：基本步骤：首先将场景中的多边形投影到绘图窗口内，判断窗口是否足够简单，若是，则算法结束；否则将窗口进一步分为四块。对此四个小窗口重复上述过程，直到窗口仅为一个像素大小。此时可能有多个多边形覆盖了该像素，计算它们的深度值，以最近的颜色显示该像素即可。如何判断窗口是否足够简单如何判断窗口是否足够简单 存在下列情况之一即可称为窗口足够简单：1）窗口为空，即多边形与窗口的关系是分离的，图a；2）

11、窗口内仅含一个多边形，即有一个多边形与窗口的关系是包含或相交。此时先对多边形投影进行裁剪，再对裁剪结果进行填充，图b、c。【判别方法： 借助剪裁算法来解决，这里不必求出交点和进行裁剪，只要判断出多边形含于窗口内，或多边形某边与窗口某边有相交即可。】3）有一个多边形的投影包围了窗口，并且它是最靠近观察点的，以该多边形颜色填充窗口，图d。 如何判断包围和分离的关系？如何判断包围和分离的关系？转角累计检查法转角累计检查法:按顺时针方向或逆时针方向绕多边形依次累加多边形各边起点与终点对窗口内任意一点所张的夹角。按累计角度之和可以判定： 若角度之和等于0，则表示多边形与窗口分离； 若角度之和等于360

12、*n，则表示多边形包围窗口(n次)。多边形多边形窗口窗口窗口窗口多边形多边形 如何判断包围和分离的关系？如何判断包围和分离的关系？区域检查法区域检查法: : 区域编码多边形顶点编码多边形边的编码多边形的编码区域编码窗口四条边所在直线将屏幕划分成9个区域，对窗口以外的8个区域按逆时针（或顺时针）进行编码，编码为07。 多边形顶点编码多边形v0v1vn的顶点vi的投影落在哪个区域，那个区域的编码便作为该顶点的编码，记为Vi。 如何判断包围和分离的关系？如何判断包围和分离的关系？区域检查法区域检查法: : 区域编码多边形顶点编码多边形边的编码多边形的编码多边形边的编码多边形的边vivi+1的编码定义

13、为Vi(i+1)=vi+1-vi，令Vn(n+1)=Vn0 i=0,1n；当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)等于两者之和。多边形的编码定义多边形的编码为其边的编码之和 ，则8000niinii当多边形包围窗口当窗口与多边形分离 例：例：STEP1STEP1：区域编码STEP2STEP2：多边形顶点编码 v0=1,v1=3,v2=7,STEP3STEP3：多边形边的编码 V01=3-1=2

14、, V12=7-3=4, V20=1-7=-6(-4),故V20=-6+8=2。STEP4STEP4：多边形的编码 V01+V12+V20=2+（-4）+2=0。 取v1v2与窗口上边所在直线的交点v将其分为两段，两段的编码分别为-2，6（4，故为6-8=-2）， 从而V12=-2+（-2）=-4。因此，多边形与窗口分离。 STEP2STEP2：多边形顶点编码 V0=5,V1=7,V2=3,STEP3STEP3：多边形边的编码 V01=7-5=2, V12=3-7=-4, V20=5-3=2.STEP4STEP4：多边形的编码 V01+V12+V20=2+4+2=8。 取v1v2与窗口上边所在

15、直线的交点v将其分为两段，两段的编码分别为-6(-4，故为-6+8=2)，2 从而V12=2+2=4。因此，多边形与窗口关系是包围。例：例：STEP1STEP1：区域编码 颜色显示颜色显示在判断结束，确保“窗口中目标简单”以后，应判断出以下三种情况：窗口为空，不含任何物体，这是显示为背景色；窗口内含有一个多边形（内含或相交），这时用窗口对多边形剪裁，显示多边形在窗口中的部分；有一个多边形包围窗口，并且比其他多边形离视点近，这时，用该多边形的颜色显示窗口。 物体表面的细节分为两类一类是由物体表面颜色色彩、明暗变化体现出来的细节(取决于物体表面的)；一类是由物体表面不规则的细小凹凸造成的细节(取决于物体本身的)。纹理映射分类用来在光滑表面上产生花纹图案的效果，用来使物体表面产生凹凸不平的效果进行纹理映射的过程主要是建立几何和纹理图片之间的几何对应关系，这种几何对应关系确立以后，纹理的某一块对应着场景中某个多边形的某个位置，如果处理不好这种关系，那么纹理可能会出现在我们与预料之外的地方，甚至颠倒扭曲，或者纹理映射失败。纹理映射的三个主要步骤：（1）定义纹理坐标；纹理坐标是纹理本身的像素位置，有了纹理坐标