计算机图形学chp8_SurfaceHidden

1、1计算机图形学计算机图形学吴 伟计算机学院E-mail: wuwei_2第8讲 消隐3 基本概念(1/3)n产生真实感的方法之一产生真实感的方法之一 反映三维场景中的相互遮挡关系反映三维场景中的相互遮挡关系n面消隐与线消隐面消隐与线消隐 表面模型与线框模型表面模型与线框模型 物体表面：平面与曲面物体表面：平面与曲面 面消隐对象：面消隐对象： 由平面多边形构成的多面体由平面多边形构成的多面体4基本概念(2/3)n消隐算法的分类消隐算法的分类1）类：以窗口内的每个像素为处理单元；）类：以窗口内的每个像素为处理单元； for (窗口内的每一个像素窗口内的每一个像素) 确定距视点最近的物体，以该物体表

2、面的颜色来显确定距视点最近的物体，以该物体表面的颜色来显示像素示像素 2）类：以场景中的物体为处理单元；）类：以场景中的物体为处理单元； for (场景中的每一个物体场景中的每一个物体) 将其与场景中的其它物体比较，确定其表面的可见将其与场景中的其它物体比较，确定其表面的可见部分；部分； 显示该物体表面的可见部分；显示该物体表面的可见部分；5基本概念(3/3)n算法复杂度算法复杂度 假设场景中有假设场景中有k个物体，平均每个物体表个物体，平均每个物体表面由面由h个多边形构成，显示区域中有个多边形构成，显示区域中有m x n个像素，则：个像素，则：第一种算法的复杂度为：第一种算法的复杂度为：O(

3、mnkh) 第二种算法的复杂度为：第二种算法的复杂度为：O(kh)*(kh)6提高消隐算法效率的常见方法n利用连贯性利用连贯性n将透视投影转换成平行投影将透视投影转换成平行投影n包围盒技术包围盒技术n背面剔除背面剔除n空间分割技术空间分割技术n物体分层表示物体分层表示7提高消隐算法效率的常见方法1n利用连贯性利用连贯性 物体连贯性物体连贯性 面的连贯性面的连贯性 区域连贯性区域连贯性 扫描线的连贯性扫描线的连贯性 深度连贯性深度连贯性8提高消隐算法效率的常见方法2n将透视投影转换成平行投影将透视投影转换成平行投影 消隐与投影关系密切消隐与投影关系密切,体现在：体现在：1 1）消隐必须在投影之前

4、完成；）消隐必须在投影之前完成；2 2）物体之间的遮挡关系与投影中心（视点）物体之间的遮挡关系与投影中心（视点）的选取有关；的选取有关；3 3）物体之间的遮挡关系与投影方式有关）物体之间的遮挡关系与投影方式有关9提高消隐算法效率的常见方法3n包围盒技术包围盒技术 定义：定义：一个形体的包围盒指的是包围它的简单形体。一个形体的包围盒指的是包围它的简单形体。比如，比如， 该技术常用于：该技术常用于： 避免盲目的求交测试、避免盲目的求交测试、各种物体间的比较等。各种物体间的比较等。 一个好的包围盒要具有两个条件：一个好的包围盒要具有两个条件：包围盒充分紧密包围着形体；包围盒充分紧密包围着形体；对其的

5、测试比较简单。对其的测试比较简单。 例：例：使用矩形包围合及长方体包围合来提高算法效使用矩形包围合及长方体包围合来提高算法效率率10提高消隐算法效率的常见方法4n背面剔除背面剔除 外法向外法向 外法向与投影方向（观察方向）的夹角外法向与投影方向（观察方向）的夹角 前向面与后向面前向面与后向面（背面）（背面） 剔除依据：剔除依据： 物体表面是封闭的，背面总是物体表面是封闭的，背面总是被前向面所遮挡，从而始终是不可见的。被前向面所遮挡，从而始终是不可见的。11提高消隐算法效率的常见方法5n空间分割技术空间分割技术依据：依据：场景中的物体，它们的投影在投影场景中的物体，它们的投影在投影平面上是否有重

6、叠部分？（是否存在相互遮挡平面上是否有重叠部分？（是否存在相互遮挡的可能？）对于根本不存在相互遮挡关系的物的可能？）对于根本不存在相互遮挡关系的物体，应避免这种不必要的测试。体，应避免这种不必要的测试。方法：方法：将投影平面上的窗口分成若干小区将投影平面上的窗口分成若干小区域；为每个小区域建立相关物体表，表中物体域；为每个小区域建立相关物体表，表中物体的投影于该区域有相交部分；则在小区域中判的投影于该区域有相交部分；则在小区域中判断那个物体可见时，只要对该区域的相关物体断那个物体可见时，只要对该区域的相关物体表中的物体进行比较即可表中的物体进行比较即可。12提高消隐算法效率的常见方法5复杂度比

7、较：复杂度比较：不妨假定每个小区域的相关物体表中平均不妨假定每个小区域的相关物体表中平均有有h个物体，场景中有个物体，场景中有k个物体，由于物体在场个物体，由于物体在场景中的分布是分散的，显然景中的分布是分散的，显然h远小于远小于k。根据第。根据第二种消隐方法所述，其算法复杂度为二种消隐方法所述，其算法复杂度为O(h*h),远小于远小于O(k*k)。13提高消隐算法效率的常见方法6n物体分层表示物体分层表示l表示形式表示形式：模型变换中的树形表示方式：模型变换中的树形表示方式l原理：原理：减少场景中物体的个数，从而降低算法复杂度。减少场景中物体的个数，从而降低算法复杂度。l方法：方法： 将父节

8、点所代表的物体看成子节点所代表物体的将父节点所代表的物体看成子节点所代表物体的包围盒，当两个父节点之间不存在遮挡关系时，就没有包围盒，当两个父节点之间不存在遮挡关系时，就没有必要对两者的子节点做进一步测试。必要对两者的子节点做进一步测试。父节点之间的遮挡关系可以用它们之间的包围父节点之间的遮挡关系可以用它们之间的包围盒进行预测试。盒进行预测试。14消除隐藏线n对造型的要求对造型的要求n在线框显示模型中在线框显示模型中,要求造型系统中有要求造型系统中有面的信息，最好有体的信息。面的信息，最好有体的信息。n坐标变换坐标变换n将视点变换到将视点变换到Z轴的正无穷大处，视线轴的正无穷大处，视线方向变为

9、方向变为Z轴的负方向。轴的负方向。15消除隐藏线n最基本的运算最基本的运算n判断面对线的遮挡关系判断面对线的遮挡关系.n反复地进行线线、线面之间的求反复地进行线线、线面之间的求交运算交运算16平面对直线段的遮挡判断算法平面对直线段的遮挡判断算法 视点与线段同侧视点与线段同侧 包围盒不交包围盒不交 分段交替取值分段交替取值 线面相交线面相交 线面平行，线在面后线面平行，线在面后 线面交与线段线面交与线段外外17(1) 若线段的两端点及视点在给定平面的若线段的两端点及视点在给定平面的同侧，线段不被给定平面遮挡，转同侧，线段不被给定平面遮挡，转7(2) 若线段的投影与平面投影的包围盒无若线段的投影与

10、平面投影的包围盒无交，线段不被给定平面遮挡，转交，线段不被给定平面遮挡，转7(3)求直线与相应无穷平面的交。若无交点，求直线与相应无穷平面的交。若无交点，转转4。否则，交点在线段内部或外部。若。否则，交点在线段内部或外部。若交点在线段内部，交点将线段分成两段，交点在线段内部，交点将线段分成两段，与视点同侧的一段不被遮挡，另一段在与视点同侧的一段不被遮挡，另一段在视点异侧，转视点异侧，转4再判；若交点在线段外部，再判；若交点在线段外部，转转4。18(4)求所剩线段的投影与平面边界投影的所求所剩线段的投影与平面边界投影的所有交点，并根据交点在原直线参数方程有交点，并根据交点在原直线参数方程中的参数

11、值求出中的参数值求出Z值值(即深度即深度)。若无交点，。若无交点，转转5。(5) 以上所求得的各交点将线段的投影分以上所求得的各交点将线段的投影分成若干段，求出第一段中点。成若干段，求出第一段中点。(6) 若第一段中点在平面的投影内，则相若第一段中点在平面的投影内，则相应的段被遮挡，否则不被遮挡；其他段应的段被遮挡，否则不被遮挡；其他段的遮挡关系可依次交替取值进行判断。的遮挡关系可依次交替取值进行判断。(7) 结束。结束。 19前向面、后向面n为了提高算法的效率，需要设法减少求为了提高算法的效率，需要设法减少求交的工作量。交的工作量。n若若V N0，称该多边形为后向面。，称该多边形为后向面。n

12、若若V N0，称该多边形为前向面。，称该多边形为前向面。后向面总是看不见的，不会由于后向面后向面总是看不见的，不会由于后向面的遮挡，而使别的棱成为不可见的。因的遮挡，而使别的棱成为不可见的。因此计算时，可以把这些后向面全部去掉，此计算时，可以把这些后向面全部去掉，这并不影响消隐结果。这并不影响消隐结果。20 前向面前向面 后向面后向面 多面体的隐藏多面体的隐藏 图图3中的中的JEAF、HCBG和和DEABC所在的面均为后所在的面均为后向面。其它为前向面。向面。其它为前向面。V VABCDEFGHIJN NVnVn21线消隐n基本数据结构基本数据结构 面表面表(存放参与消隐的面存放参与消隐的面)

13、 + 线表线表(存放待显示的线存放待显示的线) n算法算法 假设假设E为面为面F的一条边的一条边, 需判别需判别F以外每一以外每一个面与个面与E的遮挡关系的遮挡关系.22画家算法n由来由来：画家的作画顺序暗示出所画物体之画家的作画顺序暗示出所画物体之间的相互遮挡关系间的相互遮挡关系n算法基本思路：算法基本思路： 1）先将场景中的物体按其距观察点的远近）先将场景中的物体按其距观察点的远近进行排序，结果放在一张线性表中；进行排序，结果放在一张线性表中；（线性表构造线性表构造：距观察点远的称优先级低，放在表头；距：距观察点远的称优先级低，放在表头；距观察点观察点 近的称优先级高，放在表尾。该表称为近

14、的称优先级高，放在表尾。该表称为深度优先深度优先级表级表） 2）然后按照从表头到表尾的顺序逐个绘制）然后按照从表头到表尾的顺序逐个绘制物体。物体。23画家算法n关键：关键：如何对场景中的物体按深度如何对场景中的物体按深度（远近）排序，建立深度优先级表？（远近）排序，建立深度优先级表？n一种针对多边形的排序算法如下：一种针对多边形的排序算法如下： 假定在规范化投影坐标系假定在规范化投影坐标系uvn中中,投影方向是投影方向是n轴的负向，轴的负向，因而因而n坐标大距观察者近。坐标大距观察者近。u记记nmin(P) nmax(P)分别为多边形分别为多边形P的各个顶点的各个顶点n坐标的最小值和最大值，算

15、法步骤如下：坐标的最小值和最大值，算法步骤如下：24P不遮挡Q的各种情况(ab,c,d,e) 及互相遮挡f25画家算法Step 1:将场景中所有多边形存入一个线性表（链表或数组），记为将场景中所有多边形存入一个线性表（链表或数组），记为L;Step 2: 如果如果L中仅有一个多边形，算法结束；否则根据每个多边形的中仅有一个多边形，算法结束；否则根据每个多边形的nmin对它对它们预排序。不妨假定多边形们预排序。不妨假定多边形P落在表首，即落在表首，即nmin(P)为最小。再记为最小。再记Q为为L P(表中其余多边形）中任意一个；表中其余多边形）中任意一个；Step 3: 判别判别P, Q之间的关

16、系，有如下二种：之间的关系，有如下二种：step 3.1: 对对)所有的所有的Q，有，有nmax(P) nmin (Q),需进一步判别：需进一步判别： step 3.2.1 若若P,Q投影投影P,Q的包围盒不相交，则的包围盒不相交，则P,Q在表中的次序不在表中的次序不重要，令重要，令L = L P, 返回返回step 2;否则进行下一步。否则进行下一步。 step 3.2.2 若若P的所有顶点位于的所有顶点位于Q所在平面的不可见的一侧，则所在平面的不可见的一侧，则P,Q关关系正确，令系正确，令L = L P, 返回返回step 2;否则进行下一步。否则进行下一步。 step 3.2.3 若若Q

17、 的所有顶点位于的所有顶点位于P所在平面的可见的一侧，则所在平面的可见的一侧，则P,Q关系关系正确，令正确，令L = L P, 返回返回step 2;否则进行下一步。否则进行下一步。 step 3.2.4 对对P,Q投影投影P,Q求交，若求交，若P,Q不相交，则不相交，则P,Q在表中的次在表中的次序不重要，令序不重要，令L = L P, 返回返回step 2;否则在它们所相交的区域中任取一点，否则在它们所相交的区域中任取一点，计算计算P,Q在该点的深度值，如果在该点的深度值，如果P的深度小，则的深度小，则P,Q关系正确，令关系正确，令L = L P, 返回返回step 2;否则交换否则交换P,

18、Q,返回返回step 3.26画家算法n本算法不能处理的情况：本算法不能处理的情况：多边形循环遮挡多边形循环遮挡多边形相互穿透多边形相互穿透 解决办法：解决办法：分割成两个分割成两个27Z缓冲器算法先将先将z z缓冲器中各个单元的初始值置为缓冲器中各个单元的初始值置为-1(-1(规范视见体的规范视见体的最小最小n n值）。当要改变某个像素的颜色值时，首先检查当前多边值）。当要改变某个像素的颜色值时，首先检查当前多边形的深度值是否大于该像素原来的深度值（保存在该像素所对应形的深度值是否大于该像素原来的深度值（保存在该像素所对应的的Z Z缓冲器的单元中），如果大于，说明当前多边形更靠近观察缓冲器的

19、单元中），如果大于，说明当前多边形更靠近观察点，用它的颜色替换像素原来的颜色；否则说明在当前像素处，点，用它的颜色替换像素原来的颜色；否则说明在当前像素处，当前多边形被前面所绘制的多边形遮挡了，是不可见的，像素的当前多边形被前面所绘制的多边形遮挡了，是不可见的，像素的颜色值不改变。颜色值不改变。28Z缓冲区算法n帧缓存存放每个象素的颜色值n初值可放对应背景颜色的值初值可放对应背景颜色的值n深度缓存存放每个象素的深度值。n初值取初值取z的极小值的极小值屏幕帧缓冲器Z缓冲器每个单元存放对应象素的颜色值每个单元存放对应象素的深度值29算法过程算法过程n在把显示对象的每个面上每一点的在把显示对象的每个

20、面上每一点的属性（颜色或灰度）值填入帧缓冲属性（颜色或灰度）值填入帧缓冲器相应单元前，要把这点的器相应单元前，要把这点的z坐标坐标值和值和z缓冲器中相应单元的值进行缓冲器中相应单元的值进行比较。只有前者大于后者时才改变比较。只有前者大于后者时才改变帧缓冲器的那一单元的值，同时帧缓冲器的那一单元的值，同时z缓冲器中相应单元的值也要改成这缓冲器中相应单元的值也要改成这点的点的z坐标值。坐标值。30n如果这点的如果这点的z坐标值小于坐标值小于z缓冲器缓冲器中的值，则说明对应象素已经显中的值，则说明对应象素已经显示了对象上一个点的属性，该点示了对象上一个点的属性，该点要比考虑的点更接近观察点。要比考虑

21、的点更接近观察点。n对显示对象的每个面上的每个点对显示对象的每个面上的每个点都做了上述处理后，便可得到消都做了上述处理后，便可得到消除了隐藏面的图。除了隐藏面的图。31Z缓冲器算法： for ( v= 0;vvmax;v+)for (u= 0; u Z缓冲器的第缓冲器的第(u,v)单元的值）单元的值） 置帧缓冲器的第置帧缓冲器的第(u,v)单元值为当前多边形颜色；单元值为当前多边形颜色； 置置Z缓冲器的第缓冲器的第(u,v)单元值为单元值为d; 32Z-BuffernZ-Buffer算法在象素级上以近物取算法在象素级上以近物取代远物。代远物。形体在屏幕上的出现顺序形体在屏幕上的出现顺序是无关紧

22、要的。是无关紧要的。n这种取代方法实现起来远比总体排序这种取代方法实现起来远比总体排序灵活简单，有利于硬件实现。灵活简单，有利于硬件实现。n缺点：占用空间大，没有利用图形的缺点：占用空间大，没有利用图形的相关性与连续性。相关性与连续性。33改进算法改进算法n一般认为，一般认为，Z-Buffer算法需要开算法需要开一个与图象大小相等的缓存数组一个与图象大小相等的缓存数组ZB，实际上，可以改进算法，只实际上，可以改进算法，只用一个深度缓存变量用一个深度缓存变量zb。34算法过程算法过程z-Buffer() 帧缓存全置为背景色帧缓存全置为背景色for(屏幕上的每个象素屏幕上的每个象素(i,j) 深度

23、缓存变量深度缓存变量zb置最小值置最小值MinValue for(多面体上的每个多边形多面体上的每个多边形Pk) if(象素点象素点(i,j)在在pk的投影多边的投影多边形之内形之内) 计算计算Pk在在(i,j)处的深度值处的深度值depth;35 if(depth大于大于zb)zb = depth;indexp = k; If(zb != MinValue) 计算多边形计算多边形Pindexp在交点在交点 (I,j) 处的光照颜色并显示处的光照颜色并显示36n关键问题关键问题：判断象素点：判断象素点(i,j)是否在是否在pk的投影多边形之内的投影多边形之内n计算多边形计算多边形 在点（在点（

24、i，j）处的）处的深度。设多边形深度。设多边形Pk的平面方程为：的平面方程为：0dczbyaxcdbjaidepthkP37扫描线Z缓冲器算法n由来：由来：Z缓冲器算法中所需要的缓冲器算法中所需要的Z缓冲缓冲器容量较大，为克服这个缺点可以将器容量较大，为克服这个缺点可以将整个绘图区域分割成若干个小区域，整个绘图区域分割成若干个小区域，然后一个区域一个区域地显示，这样然后一个区域一个区域地显示，这样Z缓冲器的单元数只要等于一个区域缓冲器的单元数只要等于一个区域内像素的个数就可以了。内像素的个数就可以了。n如果将小区域取成屏幕上的扫描线如果将小区域取成屏幕上的扫描线，就得到就得到扫描线扫描线Z缓冲

25、器算法。缓冲器算法。3839数据结构 多边形多边形Y表表：将所有多边形存在多边形：将所有多边形存在多边形Y表中。表中。 根据多边形顶点中最小的根据多边形顶点中最小的y坐标，插入多边形坐标，插入多边形Y表中表中的相应位置。的相应位置。多边形多边形Y表中只保存多边形的序号和其顶点的最大表中只保存多边形的序号和其顶点的最大y坐坐标。根据序号可以从定义多边形的数据结构中取多边标。根据序号可以从定义多边形的数据结构中取多边形信息形信息 待消隐对象 多边形y表0 1 2 3 45 6 71234567xy1234560IP2 Ymax2IP1 Ymax1P1P2e0e1e2e3e4e540n活化多边形表活

26、化多边形表APT:与当前扫描线相交的多边与当前扫描线相交的多边形。形。APT是一个动态的链表是一个动态的链表n边边Y表表ET:活化多边形表中的每一个多边形都有活化多边形表中的每一个多边形都有一个边表一个边表ETn 多边形多边形P1的边表的边表ETIP2 Ymax2IP1 Ymax1IP2 Ymax2APTAPTy=2y=41234560Ymax, x,x,zYmax, x,x,zYmax, x,x,ze0e1e241n活化边对表活化边对表AETn在一条扫描线上，同一多边形的相邻在一条扫描线上，同一多边形的相邻两条边构成一个边对。活化边表两条边构成一个边对。活化边表AET中存放当前多边形中与当前

27、扫描线相中存放当前多边形中与当前扫描线相交的各边对的信息。交的各边对的信息。nxl xl ylmax xr xr yr max zl IP za zb (示意图见下页示意图见下页)42AET(y=6)0 1 2 3 4 5 6 71234567xye0e1e2e3e4AET(y=2)e0e4e3e2e0e143扫描线Z-buffer算法() 建多边形建多边形y表；对每一个多边形根据顶点最小的表；对每一个多边形根据顶点最小的y值，值，将多边形置入多边形将多边形置入多边形y表。表。活化多边形表活化多边形表APT，活化边表，活化边表AET初始化为空。初始化为空。For(每条扫描线每条扫描线i，i从小

28、到大从小到大)1. 帧缓存帧缓存CB置为背景色。置为背景色。2. 深度缓存深度缓存ZB (一维数组一维数组) 置为无穷大。置为无穷大。3. 将对应扫描线将对应扫描线i的，多边形的，多边形y表中的多边形加入表中的多边形加入到活化多边形表到活化多边形表APT中。中。4. 对新加入的多边形，生成其相应的边对新加入的多边形，生成其相应的边Y表。表。5. 对对APT中每一个多边形，若其边中每一个多边形，若其边Y表中对应扫表中对应扫描线描线I增加了新的边，增加了新的边，44将新的边配对，加到活化边对表将新的边配对，加到活化边对表AET中。中。6. 对对AET中的每一对边：中的每一对边：6.1 对对xl x

29、 xr 的每一个象素，按增量公式的每一个象素，按增量公式z = z - za计计算各点深度算各点深度depth。6.2 与与ZB中的量比较，中的量比较，depth ZB(I), 则令则令ZB(I) =depth，并计算颜色值，写帧缓存。，并计算颜色值，写帧缓存。 7. 删除删除APT中，多边形顶点最大中，多边形顶点最大y坐标为坐标为I的多边形，并删除相的多边形，并删除相应的边。应的边。8. 对对AET中的每一个边对，作如下处理：中的每一个边对，作如下处理：8.1 删除删除ylmax或或ylmax 已等于已等于i的边。若一边对中只删除了其的边。若一边对中只删除了其中一边，中一边， 需对该多边形的

30、边重新配对。需对该多边形的边重新配对。 8.2 用增量公式计算新的用增量公式计算新的xl 、 xr 和和zl - END45区域子分算法n由来：由来： Z缓冲器算法与扫描线缓冲器算法与扫描线Z缓冲器缓冲器算法中都是将像素孤立来考虑，未利用算法中都是将像素孤立来考虑，未利用相邻像素之间存在的属性的连贯性，即相邻像素之间存在的属性的连贯性，即区域的连贯性，所以算法效率不高。区域的连贯性，所以算法效率不高。n实际上，可见多边形至少覆盖了绘图窗实际上，可见多边形至少覆盖了绘图窗内的一块区域。如果能将这类区域找出内的一块区域。如果能将这类区域找出来，则避免了在每个像素处计算深度值，来，则避免了在每个像素处计算深度值，消隐问题也就解决了。消隐问题也就解决了。46区域子分割算法 (Warnack算法)n基本思想基本思想:n把物体投影到全屏幕窗口上，然后递归分割把物体投影到全屏幕窗口上，然后递归分割窗口，直到窗口内目标足够简单，可以显示窗口，直到窗口内目标足够简单，可以显示为止。为止。 区域子分的过程区域子分的过程47区域子分算法区域子分算法48区域子分算法n 窗口与多边形的覆盖关系有四种：窗口