计算机图形学第八章精选文档.ppt

《计算机图形学第八章精选文档.ppt》由会员分享，可在线阅读，更多相关《计算机图形学第八章精选文档.ppt（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机图形学第八章本讲稿第一页，共八十三页问题的提出本讲稿第二页，共八十三页消隐算法的两点假设假定投影平面是OXY平面，投影方向是Z轴方向。讨论的景物是不能互相贯穿，不能有循环遮挡的情况。如果不满足第一个条件可以通过各种变换方法把投影平面转换成OXY平面或把投影方向转换成Z轴方向。本讲稿第三页，共八十三页多面体的隐藏线的消除本讲稿第四页，共八十三页预测多面体哪些棱肯定不相交的方法1）区分前向面和后向面的方法2）投影的边界盒法本讲稿第五页，共八十三页预测多面体哪些棱肯定不相交的方法1）区分前向面和后向面的方法2）边界盒法本讲稿第六页，共八十三页前向面与后向面前向面是指内法线方向背向视点的面。AB

2、CD，ADHE，DCGH都是前向面。其余的面都是后向面。本讲稿第七页，共八十三页前向面后向面判断法的算法思想多面体中的面可以分为前向面和后向面，后向面总是看不见的，不会仅由于后向面的遮挡，而使别的棱成为不可见。所以可以去除所有的后向面，然后对剩下的面中的线段求交点。本讲稿第八页，共八十三页前向面后向面判断法的算法假设假设多边形F的顶点为V1,V2 VL。顶点Vi的坐标为(xi,yi,zi),顶点次序要求是使观察者沿着V1-V2-VL走时，多面体的内部始终在其右侧。本讲稿第九页，共八十三页此方法的关键是如何判断出前向面或后向面判断后向面的方法：计算多边形在OXY平面上投影的有向面积。有向面积sp

3、的计算表达式为：如果计算出sp 0，那该面就是后向面。本讲稿第十页，共八十三页实际计算中的sp表达式这么做的目的是为了消除舍入误差的影响。本讲稿第十一页，共八十三页预测多面体哪些棱肯定不相交的方法1）区分前向面和后向面的方法2）投影的边界盒法本讲稿第十二页，共八十三页边界盒的定义假设Vi在oxy平面上的投影为Qi，它的坐标记作(xi,yi)。线段Q1Q2的边界盒是以下面四点形成的矩形。本讲稿第十三页，共八十三页边界盒不相交的定义如果有两个边界盒：若满足：就称这两个边界盒不相交。本讲稿第十四页，共八十三页投影的边界盒法的算法思想算法思想：考察包含两条棱投影的边界盒，如果这两个边界盒不相交，那么这

4、两条线段的投影就肯定不会相交；从而这两条棱不相交。本讲稿第十五页，共八十三页投影的边界盒法的注意点边界盒不相交只是两条线段不相交的充分条件。不相交的两条线段的边界盒也有可能重合。本讲稿第十六页，共八十三页边界盒法的推广若不对三维线段投影后采用二维的边界盒法，可以对三维线段直接应用三维的边界盒法。本讲稿第十七页，共八十三页三维的边界盒算法要用六个参数：来确定一个三维的边界盒，如果满足则可知道这两个体在oxy平面上的投影肯定不相交（从z正向来看），所以i=1的物体不会被i=2的物体所遮挡。本讲稿第十八页，共八十三页如何实际应用三维边界盒算法用边界盒来排除相交情况时要按体、面、线的次序来进行。如果两

5、个多面体不相交，则不同多面体上的两个多边形也不会相交。如果两个多边形不相交，则在这两个多边形上的两条边也不相交。本讲稿第十九页，共八十三页三维的边界盒算法的具体实施本讲稿第二十页，共八十三页三维的边界盒算法的具体实施本讲稿第二十一页，共八十三页确定线段Vi Vj上的可见部分时会出现的几种情况若Vi 和Vj都在多边形靠观察者的一侧，则Vi Vj完全可见。不然，就把Vi Vj和多边形的边界投影到oxy平面，求出投影之间的交点。对于交点对应点在多边形前面的才要保留。本讲稿第二十二页，共八十三页确定线段Vi Vj上的可见部分时会出现的几种情况如果投影间没有交点，则要判断Vi Vj是否全在多边形内部，若

6、在，则可能Vi Vj完全不可见。本讲稿第二十三页，共八十三页在上述过程中需要解决的几个问题如何判断一个点是在多边形的前还是后如何求oxy平面上投影的交点如何判断投影点在多边形投影的外还是内本讲稿第二十四页，共八十三页需要解决的几个问题如何判断一个点是在多边形的前还是后如何求oxy平面上投影的交点如何判断投影点在多边形投影的外还是内本讲稿第二十五页，共八十三页如何判断点在多边形前还是后假设多边形的顶点为 ，其坐标为 ，i=1,2,L。任取三个不在一直线上的顶点。设为 ，则这多边形所在平面方程为：本讲稿第二十六页，共八十三页如何判断点在多边形前还是后即：其中：设点Vj的坐标为(xj,yj,zj)，

7、代入上式z(x,y)。若z(xj,yj)=xi,说明考察的多边形边和射线有一个交点。本讲稿第三十六页，共八十三页计算中产生的舍入误差的处理在计算x的算式还是会产生舍入误差，可能把x=xi算成xxi，这种情况发生在Qi和边 很接近时，但用了只要Qi和边 比较接近，则认为QiQi+1与 有交点，因此不存在判断Qi在多边形内或外的问题。本讲稿第三十七页，共八十三页区域子分算法算法思想：本讲稿第三十八页，共八十三页要显示的多边形和窗口的关系多边形包围了窗口多边形和窗口相交窗口包围了多边形窗口和多边形分离本讲稿第三十九页，共八十三页窗口内的图形可以显示的情况以及所采取的相应的措施(1)所有多边形都和窗口

8、分离。此时只要把窗口内所有的像素都填上背景颜色。本讲稿第四十页，共八十三页窗口内的图形可以显示的情况以及所采取的相应的措施(2)只有一个多边形和窗口相交，或这个多边形包含在窗口内。这时先对窗口内每一个像素填上背景颜色，再对窗口内多边形部分用扫描线算法填色。本讲稿第四十一页，共八十三页窗口内的图形可以显示的情况以及所采取的相应的措施(3)只有一个多边形和窗口相交，这个多边形把窗口整个包围在内，或虽有几个多边形和窗口相交，但离观察者最近的一个多边形包围了整个窗口。这时把整个窗口填上离观察者最近的那个多边形的颜色。本讲稿第四十二页，共八十三页为了提高效率，对区域子分算法的若干细节进行处理（1）本讲稿

9、第四十三页，共八十三页对区域子分算法的若干细节进行处理（2）在找到一个多边形包围所考察的窗口时，就要把它和多边形序列中其他多边形离观察者远近进行比较，把被它遮挡的多边形从序列中去掉。本讲稿第四十四页，共八十三页对区域子分算法的若干细节进行处理（3）对于算法的数据结构的设计，可采用用一个四叉树，根结点是整个窗口，每一个结点下有四个子结点对应分成的四个子窗口，所以在编程序时可用递归方法或用堆栈的方法。本讲稿第四十五页，共八十三页区域子分算法的效率讨论对于分辨率为2NX2N光栅显示器，窗口经N次细分可使子窗口和一个像素大小一致。本讲稿第四十六页，共八十三页Z缓冲器算法帧缓冲器：其存储的每一个单元就是

10、屏幕上的每一个像素的颜色值。z缓冲器：其存储单元的个数和屏幕上的像素个数相同。它的每一个单元的值一一对应于帧缓冲器中的单元的z坐标值（深度值）。每一个存储单元的大小一般取20bit。本讲稿第四十七页，共八十三页Z缓冲器算法的算法思想本讲稿第四十八页，共八十三页Z缓冲器算法的优缺点优点：简单，可靠缺点：需要很大的z缓冲器；每一个点都必须计算其z值，计算量大。本讲稿第四十九页，共八十三页z缓冲器算法的改进扫描线z缓冲器算法本讲稿第五十页，共八十三页扫描线z缓冲器算法的数据结构本讲稿第五十一页，共八十三页扫描线z缓冲器算法的数据结构多边形Y筒本讲稿第五十二页，共八十三页扫描线z缓冲器算法的数据结构边

11、Y筒本讲稿第五十三页，共八十三页多边形Y筒中存储的内容a,b,c,d:多边形所在平面ax+by+cz+d=0的系数IP：多边形的编号color：多边形的颜色属性y：该多边形在oxy平面上的投影与扫描线相交的条数。本讲稿第五十四页，共八十三页边Y筒中存储的内容x：边的上端点的x坐标值x：该边在oxy平面上的投影在相邻两条扫描线交点的x坐标值之差。y：该边在oxy平面上的投影与扫描线相交的条数。IP：该边所在多边形的编号。本讲稿第五十五页，共八十三页扫描线z缓冲器算法的数据结构多边形活化表多边形活化表中记录了在oxy平面上的投影和当前扫描线相交的多边形。多边形活化表中存储的信息类型与多边形Y筒保存

12、的信息类型相同。本讲稿第五十六页，共八十三页扫描线z缓冲器算法的数据结构边活化表边活化表存放多边形在oxy平面上的投影和扫描线相交的边对。本讲稿第五十七页，共八十三页边活化表中存储的内容xl：左交点的x坐标值。xl：左交点所在边和两相邻扫描线的x坐标之差。为了下移一条扫描线后，左交点x坐标的增量。yl：以和左交点所在边相交的扫描线条数为初值，以后每下移一条扫描线就减1。同理，对应右交点也要存储xr，xr，yr，其意义和左交点各值相似。本讲稿第五十八页，共八十三页边活化表中存储的内容zl：左交点处多边形所在平面的深度值。zx：沿扫描线向右走过一个像素时，多边形所在平面深度的增量。对于方程ax+b

13、y+cz+d=0，来说zx=-a/c。zy：沿y方向向下移动一条扫描线时，多边形所在平面的深度增量。对于方程ax+by+cz+d=0，来说zy=b/c。IP：所在多边形的编号。本讲稿第五十九页，共八十三页扫描线z缓冲器算法的步骤从最上面的一条扫描线开始处理，开始之前多边形活化表和边活化表要清空。1）把帧缓冲器的本扫描线置为背景色。2）z缓冲器的各单元放置z的最小值。3）检查多边形的Y筒，如果有新的多边形涉及该扫描线，则把它放入多边形活化表中。本讲稿第六十页，共八十三页扫描线z缓冲器算法的步骤4）如果有新的多边形加入多边形活化表，则要把该多边形在oxy平面上的投影和扫描线相交的边都加入到边的活化

14、表中。本讲稿第六十一页，共八十三页扫描线z缓冲器算法的步骤5）如果有些边在本扫描线结束了，但该边所在的多边形仍在多边形活化表中，则必有新的边代替要结束的边，从边Y筒中找到作为代替的新的这样的边，修改或加到边的活化表中。本讲稿第六十二页，共八十三页扫描线z缓冲器算法的步骤6）从边的活化表中取出一个边对，令zx=zl，对于每一个满足 的坐标为(x,y)的像素。从左到右，计算zx=zx+zx，算出的zx就是(x,y)像素点的深度值，如果此值比z缓冲器单元中存放的值大，就把此值代替z缓冲器中的值，并把帧缓冲器中相应单元改成这个多边形的颜色值。本讲稿第六十三页，共八十三页如何修改边的活化表修改只在本条扫

15、描线已完成，要采用下一条扫描线时才进行。对每一个边对：yl=yl-1，yr=yr 1。若yl=0，则发生算法中新边替换旧边的情况，但也有可能两条边同时结束于一点，说明这一边对可以同时消去。本讲稿第六十四页，共八十三页如何修改边的活化表边和下一条扫描线交点的x值可这样求出：xr=xr+xr，xl=xl+xl，多边形所在平面对应下一条扫描线在x=xl处的深度为：zl=zl+zxxl+zy，对多边形活化表中每一个多边形的y都要做y y-1，当y=0时，该多边形从多边形活化表中删除。本讲稿第六十五页，共八十三页区间扫描线算法算法思想：本讲稿第六十六页，共八十三页算法思想的具体实现本讲稿第六十七页，共八

16、十三页区间扫描线算法的数据结构建立与扫描线算法相同的多边形Y筒、边Y筒、多边形活化表和边活化表不同的是：1）在多边形活化表中要多设立一个活化标志位flag；设立一个初值为0的计数器J。本讲稿第六十八页，共八十三页区间扫描线算法的数据结构2）边活化表所存储的属性：边和扫描线交点x坐标；该边和相邻两扫描线交点x坐标差值x；该边相交的总的扫描线数y，该边所在多边形编号；边表还要按x值大小次序排序，x值小的排在左面。本讲稿第六十九页，共八十三页区间扫描线算法中的具体变量本讲稿第七十页，共八十三页区间扫描线算法中的具体变量所代表的含义如果一多边形在oxy平面上的投影覆盖了区间xi,xi+1，则称该多边形

17、是活化的。若多边形在xi,xi+1上是活化的，那么在这个区间上的flagi为1，在此区间上活化多边形的个数与J值相同。本讲稿第七十一页，共八十三页区间扫描线算法的实质采用区间扫描线算法进行消隐工作的实质就是在多个多边形上选离观察者最近的那个多边形的颜色来填充。本讲稿第七十二页，共八十三页进一步提高该算法效率的细节设置本讲稿第七十三页，共八十三页进一步提高该算法效率的细节设置本讲稿第七十四页，共八十三页出现的新问题本讲稿第七十五页，共八十三页几种算法效率的比较10025006000Z缓冲器算法545454区间扫描线算法521100区域子分算法1164307本讲稿第七十六页，共八十三页优先级表算法

18、算法思想：本讲稿第七十七页，共八十三页算法的难点算法的难点在于怎样对多边形做一个正确的排序。本讲稿第七十八页，共八十三页解决方法本讲稿第七十九页，共八十三页Qzmin Pzmax的解决方法若对某一多边形Q有Qzmin Pzmax，则需进一步的检查，这样的检查分为五项：本讲稿第八十页，共八十三页如何彻底解决谁遮挡谁的问题前面提到的五项只要有一项成立，P就不遮挡Q，但是由于从第一项到第五项的工作是递增的，所以一般检查时按照从第一项到第五项这样的次序。本讲稿第八十一页，共八十三页如何彻底解决谁遮挡谁的问题若以上五项均不成立，就不能判断P不遮挡Q，这时要在多边形序列中把P和Q交换一下次序，对交换后的P继续上述步骤，看P是否遮挡别的多边形。本讲稿第八十二页，共八十三页优先级表算法的应用本讲稿第八十三页，共八十三页