计算机图形学隐面算法.pptx

《计算机图形学隐面算法.pptx》由会员分享，可在线阅读，更多相关《计算机图形学隐面算法.pptx（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、级算法。基本原理：基本原理：1）先把屏幕置成背景色；2）将场景中的物体的各个面按其距观察点的远近进行排序，结果放在一张线性表中；（线性表构造：距观察点远的优先级低，放在表头；距观察点近的优先级高，放在表尾）该表称为深度优先级表。3）然后按照从远到近（从表头到表尾）的顺序逐个绘制物体表面。现在学习的是第3页，共31页消除隐藏面消除隐藏面 画家算法画家算法深度优先级表的建立一、多边形优先级的考虑首先对一个简单的画面，可以直接建立一个确定的深度优先表如图（a）所示。深度方向上无重叠。当画面略微复杂一点，无法按简单的Z向排序建立确定的深度优先表，以确定每一个多边形的优先级，如图（b）所示。深度方向上有

3、重叠Q QX XZ ZP PR RQ QX XZ ZP P（a a）（b b）R R现在学习的是第4页，共31页消除隐藏面消除隐藏面 画家算法画家算法深度优先级表的建立二、投影重叠判断：测试按照难度递增顺序排列：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

4、在观察平面oxy上的投影不相交,图c；上面5项只要有一项成立，P就不遮挡Q，不需要重新排序现在学习的是第5页，共31页消除隐藏面消除隐藏面 画家算法画家算法 深度优先级表的建立对于某一重叠表面，上述五项测试均不成立，则需在有序表中调换两个面的位置。S,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项测试现在学习的是第6页，共31页消除隐藏面消除隐藏面 画家算法画家算法深度优先级表的建立解决方法是沿多边形所在平面间的交线循环分割这些多边形。无法直接建立正确的深度优先表现在

5、学习的是第7页，共31页消除隐藏面消除隐藏面 画家算法画家算法排序计算量大；多边形相交或循环重叠时，必须分割多边形。画家算法的不足：画家算法的不足：现在学习的是第8页，共31页消除隐藏面消除隐藏面 Z Z缓冲区算法缓冲区算法Z Z缓冲区算法缓冲区算法基本思想基本思想：投影平面每个像素所对应的所有面片（平面或曲面）的深度进行比较，然后取离视线最近面片的属性值作为该像素的属性值。Z缓冲器算法基本思想现在学习的是第9页，共31页消除隐藏面消除隐藏面 Z Z缓冲区算法缓冲区算法实现方法帧缓存区 深度缓存区存放每个像素的深度值。Z缓冲器每个单元存放对应像素当前最近面的深度值存放每个像素的颜色值。帧缓冲器

6、每个单元存放对应像素的颜色值屏幕现在学习的是第10页，共31页消除隐藏面消除隐藏面 Z 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）=z，同时将该像素的颜色值I（x，y）写入帧缓冲器

7、，即IB（x，y）=I（x，y）；否则不变。现在学习的是第11页，共31页消除隐藏面消除隐藏面 Z Z缓冲区算法缓冲区算法深度值的计算若已知多边形的方程，则可用增量法计算扫描线每一个像素的深度。设平面方程为：C0C0 则多边形面上的点（x，y）所对应的深度值为：现在学习的是第12页，共31页消除隐藏面消除隐藏面 Z Z缓冲区算法缓冲区算法深度值的计算 由于所有扫描线上相邻点间的水平间距为1个像素单位，扫描线行与行之间的垂直间距也为1。因此可以利用这种连贯性来简化计算过程，如图所示。若已计算出（x，y）点的深度值为zi，沿x方向相邻连贯点（x+1，y）的深度值zi+1可由下式计算：现在学习的是第

8、13页，共31页消除隐藏面消除隐藏面 Z Z缓冲区算法缓冲区算法深度值的计算沿多边形左边界递归计算边界上各点的坐标：m为该边的斜率，沿该边的深度也可以递归计算出来，即：如果该边是一条垂直边界，则计算公式简化为：现在学习的是第14页，共31页消除隐藏面消除隐藏面 Z Z缓冲区算法缓冲区算法深度值的计算对于每条扫描线，首先根据公式计算出与其相交的多边形最左边的交点所对应的深度值，然后，利用图形连贯性将该扫描线上所有的后续点计算出来。所有的多边形处理完毕，即得消隐后的图形。现在学习的是第15页，共31页消除隐藏面消除隐藏面 Z Z缓冲区算法缓冲区算法Z Z缓冲区算法的优缺点：缓冲区算法的优缺点：优点

9、1.简单稳定，利于硬件实现2.Z缓冲器算法的最大优点：Z缓存器算法在像素级上以近物取代远物。形体在屏幕上的出现顺序是无关紧要的。可以轻而易举地处理隐藏面以及显示复杂曲面之间的交线。缺点1.需要一个额外的Z 缓冲器，需更大的存储空间，例如，当像素数目为500*500时，就需要250K个深度值的存储空间。深度值一般用浮点数表示，每个数占4个字节，故共需要1M字节的额外存储空间。2.在每个多边形占据的每个像素处都要计算深度值，计算量大。现在学习的是第16页，共31页消除隐藏面消除隐藏面 扫描线算法扫描线算法扫描线算法扫描线算法 基本思想基本思想：按扫描行的顺序处理一帧画面，在由视点和扫描线所决定的扫

10、描平面上解决消隐问题。基本步骤：基本步骤：把物体各面投影到屏幕上计算扫描线与物体各投影面的相交区间。当两个区间在深度方向上重叠时，采用深度测试确定可见部分。典型实现：典型实现：扫描线Z缓冲区算法扫描线间隔连贯性算法现在学习的是第17页，共31页消除隐藏面消除隐藏面 扫描线算法扫描线算法扫描线扫描线Z Z缓冲缓冲器器每个单元存放对应像素每个单元存放对应像素当前最近面的深度值当前最近面的深度值（每一个扫描线用一个缓冲器）（每一个扫描线用一个缓冲器）扫描线Z缓冲区算法现在学习的是第18页，共31页消除隐藏面消除隐藏面 扫描线算法扫描线算法3,2,103,2,107,2,107,2,107,4,107

11、,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 41010101010101010 101012121616101010101010101010101212 1616 20201616202020202020现在学习的是第19页，共31页消除隐藏面消除隐藏面 区域采样算法区域采样算法区域采样算法区域采样算法 区域采样算法区域采样算法是利用图形的区域连贯性，在连续的区域上确定可见面及其颜色、亮度。基本思想基本思想：把物体投影到全屏幕窗口上，然后递归地分割窗口

12、，直到窗口内目标足够简单，可以直接显示为止。基本步骤：基本步骤：首先将场景中的多边形投影到绘图窗口内，判断窗口是否足够简单，若是，则算法结束；否则将窗口进一步分为四块。对此四个小窗口重复上述过程，直到窗口仅为一个像素大小。此时可能有多个多边形覆盖了该像素，计算它们的深度值，以最近的颜色显示该像素即可。现在学习的是第20页，共31页消除隐藏面消除隐藏面 区域采样算法区域采样算法如何判断窗口是否足够简单如何判断窗口是否足够简单 存在下列情况之一即可称为窗口足够简单：1）窗口为空，即多边形与窗口的关系是分离的，图a；2）窗口内仅含一个多边形，即有一个多边形与窗口的关系是包含或相交。此时先对多边形投影

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

14、多边形包围窗口(n次)。多边形多边形窗口窗口窗口窗口多边形多边形现在学习的是第22页，共31页消除隐藏面消除隐藏面 区域采样算法区域采样算法 如何判断包围和分离的关系？如何判断包围和分离的关系？区域检查法区域检查法:区域编码多边形顶点编码多边形边的编码多边形的编码区域编码窗口四条边所在直线将屏幕划分成9个区域，对窗口以外的8个区域按逆时针（或顺时针）进行编码，编码为07。多边形顶点编码多边形v0v1vn的顶点vi的投影落在哪个区域，那个区域的编码便作为该顶点的编码，记为Vi。现在学习的是第23页，共31页消除隐藏面消除隐藏面 区域采样算法区域采样算法 如何判断包围和分离的关系？如何判断包围和分

15、离的关系？区域检查法区域检查法:区域编码多边形顶点编码多边形边的编码多边形的编码多边形边的编码多边形的边vivi+1的编码定义为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)等于两者之和。多边形的编码定义多边形的编码为其边的编码之和，则现在学习的是第24页，共31页消除隐藏面 区域采样算法 例：例：STEP1STEP1：区域编码STEP2STEP

16、2：多边形顶点编码 v0=1,v1=3,v2=7,STEP3STEP3：多边形边的编码 V01=3-1=2,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。因此，多边形与窗口分离。现在学习的是第25页，共31页消除隐藏面 区域采样算法 STEP2STEP2：多边形顶点编码 V0=5,V1=7,V2=3,STEP3STEP3：多边形边的编码 V01=7-5=

17、2,V12=3-7=-4,V20=5-3=2.STEP4STEP4：多边形的编码 V01+V12+V20=2+4+2=8。取v1v2与窗口上边所在直线的交点v将其分为两段，两段的编码分别为-6(-4，故为-6+8=2)，2 从而V12=2+2=4。因此，多边形与窗口关系是包围。例：例：STEP1STEP1：区域编码现在学习的是第26页，共31页消除隐藏面消除隐藏面 区域采样算法区域采样算法 颜色显示颜色显示在判断结束，确保“窗口中目标简单”以后，应判断出以下三种情况：窗口为空，不含任何物体，这是显示为背景色；窗口内含有一个多边形（内含或相交），这时用窗口对多边形剪裁，显示多边形在窗口中的部分；

18、有一个多边形包围窗口，并且比其他多边形离视点近，这时，用该多边形的颜色显示窗口。现在学习的是第27页，共31页纹理纹理现在学习的是第28页，共31页纹理纹理 物体表面的细节分为两类一类是由物体表面颜色色彩、明暗变化体现出来的细节(取决于物体表面的材质属性材质属性)；一类是由物体表面不规则的细小凹凸造成的细节(取决于物体本身的几何形状几何形状)。纹理映射分类颜色纹理映射，颜色纹理映射，用来在光滑表面上产生花纹图案的效果几何纹理映射几何纹理映射，用来使物体表面产生凹凸不平的效果现在学习的是第29页，共31页纹理纹理 纹理映射技术纹理映射技术 纹理映射纹理映射进行纹理映射的过程主要是建立几何和纹理图片之间的几何对应关系，这种几何对应关系确立以后，纹理的某一块对应着场景中某个多边形的某个位置，如果处理不好这种关系，那么纹理可能会出现在我们与预料之外的地方，甚至颠倒扭曲，或者纹理映射失败。纹理映射的三个主要步骤：（1）定义纹理坐标；纹理坐标是纹理本身的像素位置，有了纹理坐标就等于用坐标系对纹理的每一个像素点进行了编号。（2）映射函数定义；通过纹理坐标将纹理图片和需要映射纹理的几何多边形进行对应。（3）纹理映射的实施；(a)纹理坐标 (b)物体表面 图二 映射函数的建立图一 纹理坐标 现在学习的是第30页，共31页光线跟踪光线跟踪现在学习的是第31页，共31页