最新图像空间的消隐算法Zbuffer扫描线warnock课件PPT.ppt 55页

'图像空间的消隐算法Zbuffer扫描线warnock 第九章：真实感图形学图9.1长方体线框投影图的二义性图9.2线框图         图9.3消隐图          图9.4真实感图形2021/8/22 第九章：真实感图形学消隐的分类消隐的对象是三维物体。三维体的表示：边界表示和CSG(结构实体几何学)表示等。最简单的表示方式：用表面上的平面多边形表示。如物体的表面是曲面，则将曲面用多个平面多边形近似。消隐结果与观察物体有关，也与视点有关。按消隐对象分类线消隐消隐对象是物体上的边，消除物体上不可见的边。面消隐消隐对象是物体上的面，消除物体上不可见的面。2021/8/23 第九章：真实感图形学平面对直线段的遮挡判断算法不失一般性，取视点在Z轴正无穷远，视线为Z轴负方向，物体投影到XOY平面上。若线段的两端点及视点在给定多边形的同侧，线段不被其遮挡，转7（结束）。(深度检测，多边形顶点的最大Z坐标小于等于线段端点的最小Z坐标，多边形完全在线段之后，不可能遮挡线段，即线段完全可见)若线段的投影与多边形投影的包围盒(覆盖多边形投影的最小矩形区域)无交，线段不被给定多边形遮挡，转7（结束）。求直线与相应多边形的交。若无交点，转4。否则，交点在线段内部或外部。若交点在线段内部，交点将线段分成两段，与视点同侧的一段不被遮挡，另一段在视点异侧，转4再判；若交点在线段外部，转4。2021/8/27 第九章：真实感图形学求所剩线段(可能被遮挡部分)的投影与多边形边界投影的所有交点，并根据交点在原直线参数方程中的参数值求出Z值(即深度)。若无交点，转5。以上所求得的各交点将线段的投影分成若干段，求出第一段中点。若第一段中点在平面的投影内，则相应的段被遮挡，否则不被遮挡；其他段的遮挡关系可依次交替取值进行判断。结束。2021/8/28 第九章：真实感图形学图9.6视点与线段同侧       图9.7包围盒不交图9.8分段交替取值2021/8/29 第九章：真实感图形学线消隐算法基本数据结构:面表(存放参与消隐的面)＋线表(存放待显示的线)HiddenLineRemove(){坐标变换；for(对每个面Fj)for(Fj的每一条边Ei)将二元组压入堆栈While(栈不空){=栈顶；for(j!=j0的每一个面Fj){if(Ei被Fj全部遮挡){将Ei清空；break;}if(Ei被Fj部分遮挡){从Ei中将被遮挡的部分裁掉；if(Ei被分成若干段){取其中的一段作为当前段；将其它段及相应的j压栈}}}if(Ei段不为空)显示Ei;}}2021/8/210 第九章：真实感图形学如果消隐对象有N条棱，当N很大时，用两两求交的方法工作量很大O(N2)。为提高算法效率，要设法减少求交的工作量。设V为由视点出发的观察向量，N为某多边形面的法向量。若V·N>0，称该多边形为后向面。若V·N<0，称该多边形为前向面。如下图中的JEAF、HCBG和DEABC所在的面均为后向面。后向面总是看不见的，由于后向面的遮挡，别的棱成为不可见－》可以把后向面去掉，并不影响消隐结果。2021/8/211 第九章：真实感图形学图9.9   (a)前向面(b)后向面(c)多面体的隐藏线消除2021/8/212 第九章：真实感图形学消除隐藏面使用光栅图形显示器绘制物体的真实图形时，必须解决消除隐藏面的问题。画家算法(列表优先算法)先把屏幕置成背景色，再把物体的各个面按其离视点的远近进行排序，离视点远者(Z最小)在表头，离视点近者(Z最大)在表尾，排序结果存在一张深度优先级表中。从表头到表尾逐个取出多边形投影到屏幕并显示多边形包含的实心区域。由于后显示的图形取代先显示的画面，而后显示的图形所代表的面离视点更近，所以由远及近的绘制各面，就相当于消除隐藏面。这与油画作家作画的过程类似，先画远景，再画中景，最后画近景。2021/8/213 第九章：真实感图形学检验深度优先级表中相邻面的顺序深度重叠判断若P,Q是深度优先级表中两个相邻的多边形，且Zmax(P)≥Zmin(P)≥Zmax(Q)，则Q不可能遮挡P的任何部分，可以在P之前画出。完成这一测试需使多边形数据结构包括所有顶点的最小和最大Z坐标。投影重叠判断如果P和Q在XY平面上的投影的包围盒不重叠，则P,Q不可能互相遮挡，其顺序无关紧要。完成这一测试需把最大和最小的X,Y坐标存在面的数据表里。2021/8/214 第九章：真实感图形学P在Q之前如果P的所有顶点在Q所在平面的可见一侧，则Q不会遮挡P的任何部分。完成这一测试需把P的各顶点坐标代入Q的平面方程，如果所得式子的符号与视点代入方程的符号相同，则P在Q的可见一侧。面的数据表需包含方程系数。Q在P之前如果“P在Q之前”测试失败，应该进行“Q在P之前”的逆测试，即把所有Q的顶点代入P的方程检验与代入视点得到的符号是否相同，如果测试通过应该把P,Q在深度优先级表中的顺序颠倒过来。2021/8/215 第九章：真实感图形学精确的重叠测试如果所有测试失败，就必须对多边形在XY平面上的投影作求交计算。计算时不必具体求出重叠部分，只要能判断出前后顺序即可。最简单的方法是对每对边(一条P边，一条Q边)作线段求交测试，若没有循环重叠情况，则只要求出第一个交点，在交点处进行深度比较即可确定二者顺序。画家算法原理简单。其关键是如何对场景中的物体按深度排序。它的缺点是只能处理互不相交的面，而且深度优先级表中面的顺序可能出错。在两个面相交，三个以上的面重叠的情形，用任何排序方法都不能排出正确的序。这时只能把有关的面进行分割后再排序。2021/8/216 第九章：真实感图形学2021/8/217 第九章：真实感图形学Z缓冲区(Z-Buffer)算法画家算法中，深度排序计算量大，而且排序后，还需再检查相邻的面，以确保在深度优先级表中前者在前，后者在后。若遇到多边形相交，或多边形循环重叠的情形，还必须分割多边形。为避免这些复杂的运算，发明了Z缓冲区(Z-Buffer)算法。在这个算法里，不仅需要有帧缓存来存放每个象素的颜色值，还需要一个深度缓存来存放每个象素的深度值。2021/8/218 第九章：真实感图形学图9.10Z缓冲区示意图2021/8/219 第九章：真实感图形学Z缓冲器中每个单元的值是对应象素点所反映对象的z坐标值，Z缓冲器中每个单元的初值取成z的极小值。帧缓冲器每个单元的初值可放对应背景颜色的值。图形消隐的过程就是给帧缓冲器和Z缓冲器中相应单元填值的过程。在把显示对象的每个面上每一点的属性(颜色或灰度)值填入帧缓冲器相应单元前，要把这点的z坐标值和z缓冲器中相应单元的值进行比较。只有前者大于后者时才改变帧缓冲器的那一单元的值，同时z缓冲器中相应单元的值也要改成这点的z坐标值。2021/8/220 第九章：真实感图形学如果这点的z坐标值小于z缓冲器中的值，则说明对应象素已经显示了对象上一个点的属性，该点要比考虑的点更接近观察点。对显示对象的每个面上的每个点都做了上述处理后，便可得到消除了隐藏面的图。多边形在各象素深度值的增量求法对于一给定多边形，在某一点(x,y)的深度值可通过平面方程ax+by+cz+d=0表示为z=(-d-ax-by)/c若在(x,y)处求出z值是z1,则在(x+Δx,y)处的z值为z1-a/c(Δx)。a/c是常数，且一般取Δx=1。所以当已知(x,y)处的深度值时，求(x+1,y)处的深度值只要做一次减法。2021/8/221 第九章：真实感图形学Z-Buffer算法(){帧缓存全置为背景色深度缓存全置为最小Z值for(每一个多边形){扫描转换该多边形for(该多边形所覆盖的每个象素(x,y)){计算该多边形在该象素的深度值Z(x,y);if(Z(x,y)大于Z缓存在(x,y)的值){把Z(x,y)存入Z缓存中(x,y)处把多边形在(x,y)处的颜色值存入帧缓存的(x,y)处}}}}2021/8/222 第九章：真实感图形学Z-Buffer算法在象素级上以近物取代远物。形体在屏幕上的出现顺序是无关紧要的。这种取代方法实现起来远比总体排序灵活简单，有利于硬件实现。Z-Buffer算法的缺点：占用空间大，没有利用图形的相关性与连续性。Z-Buffer算法以算法简单著称，但也以占空间大而闻名。一般认为，Z-Buffer算法需要开一个与图象大小相等的缓存数组ZB，实际上，可以改进算法，只用一个深度缓存变量zb。2021/8/223 第九章：真实感图形学区间扫描线算法与Z－buffer算法相比，扫描线Z－buffer算法做两点改进:将整个绘图窗口内的消隐问题分解到一条条扫描线上解决，使所需的Z缓冲器大大减少。计算深度值时，利用了面连贯性，只用了一个加法。但它在每个象素处都计算深度值，进行深度比较。因此，被多个多边形覆盖的象素区处还要进行多次计算，计算量仍然很大。区间扫描线算法克服了这一缺陷，使得在一条扫描线上每个区间只计算一次深度值，并且不需要Z缓冲器。它是把当前扫描线与各多边形在投影平面的投影的交点进行排序后，使扫描线分为若干子区间。因此，只要在区间任一点处找出2021/8/224 第九章：真实感图形学图9.15扫描线与多边形的投影相交得到若干子区间在该处z值最大的一个面，这个区间上的每一个象素就用这个面的颜色来显示。2021/8/225 第九章：真实感图形学确定小区间的颜色小区间上没有任何多边形，如[a4,a5]，这时该小区间用背景色显示。小区间上只有一个多边形，如[a1,a2]，[a3,a4]，[a5,a6]，[a7,a8]，以对应多边形在该处的颜色显示。小区间上存在两个或两个以上的多边形,如[a6,a7]，必须通过深度测试判断哪个多边形可见。若允许物体表面相互贯穿时，还必须求出它们在扫描平面(ZX平面)的交点。用这些交点把该小区间分成更小的子区间(称为间隔)，在这些间隔上决定哪个多边形可见。如将[a2,a3]区间分成[a2,b][b,a3]两个子区间。为了确定某间隔内那一2021/8/226 第九章：真实感图形学多边形可见，可在间隔内任取一采样点(如间隔中点)，分析该点处哪个多边形离视点最近，该多边形即是在该间隔内可见的多边形。在[a2,b]上F2可见，在[b,a3]F1可见。图9.16(a)两个平面在屏幕上的投影(b)无贯穿的情形(c)相互贯穿的情形2021/8/227 第九章：真实感图形学区域子分割算法(Warnack算法，区域采样算法)画家算法、Z缓冲区算法和扫描线算法都是点取样算法，绘制图形时在投影面取一组离散点，在各个离散点解决消隐问题，确定颜色亮度，以显示屏幕上的对应象素。区域采样算法利用区域的连贯性，在连续的区域上确定可见面及其颜色、亮度。区域采样算法基本思想：把物体投影到全屏幕窗口上，然后递归分割窗口，直到窗口内目标足够简单可以显示为止。首先，该算法把初始窗口取作屏幕坐标系的矩形，将场景中的多边形投影到窗口内。如果窗口内没有物体则按背景色显示；若窗口内只有一个面，则把该面显示出来。否则，窗2021/8/228 第九章：真实感图形学口内含有两个以上的面，则把窗口等分成四个子窗口。对每个小窗口再做上述同样的处理。这样反复地进行下去。如果到某个时刻，窗口仅有象素的可见面的颜色或所有可见面的平均颜色作为该象素那么大，而窗口内仍有两个以上的面，这时不必再分割，只要取窗口内最近的值。四叉树算法假设全屏幕窗口分辨率为1024×1024。窗口以左下角点(x，y)和边宽s定义。下图为使用栈结构实现的区域子分割算法流图。由于算法中每次递归的把窗口分割成四个与原窗口相似的小窗口，故这种算法通常称为四叉树算法。2021/8/229 第九章：真实感图形学图9.19区域子分割算法流图2021/8/230 第九章：真实感图形学2021/8/231 第九章：真实感图形学窗口与多边形的覆盖关系：内含、相交、包围和分离。判断内含和相交关系可以借助于裁剪算法来解决。不必具体求出交点和裁剪，只要判断出多边形含于窗口内或多边形某边与窗口某边有交就可以了。图9.18 (a)内含(b)多边形与窗口相交(c)包围(d)窗口和多边形分离2021/8/232 第九章：真实感图形学判断包围和分离的转角检查方法按顺时针或逆时针方向绕多边形边界一周，累计相邻的两个顶点对窗口所张的角之和∑α，若∑α＝360º,则多边形包含窗口。若∑α＝0，则多边形与窗口分离。2021/8/233 第九章：真实感图形学判断包围和分离区域编码法把窗口外的平面区域分为八个区，编号为0-7,多边形的每个顶点一定落在某个区域内，否则为前述的内含或相交关系。顶点所在区的编号就作为顶点的编号。2021/8/234 第九章：真实感图形学对每条边，令α＝(终点编码)－(起点编码)若α>4则α＝α－8;若α<-4则α＝α＋8若α＝±4，将该边在窗口边界分为两段，对每段求α。对每边的α求和得：例1:a12=2-0=2a23=4-2=2a34=6-4=2a45=7-6=1a51=0-7=-7(<-4)=-7+8=1可判断多边形包含窗口例2:a12=7-0=7(>4)=7-8=-1a23=7-7=0a34=0-7=-7(<-4)=-7+8=1a45=1-0=1a51=0-1=-1可判断多边形与窗口分离2021/8/235 第九章：真实感图形学a=±4的特殊情况a12=3-7=-4,a23=2,a31=2,若a＝-4不做特殊处理，则∑a＝0,把多边形包含窗口误判为与窗口分离。若把线段a12分成两段，则a1m=0-7=-7(<-4)=-7+8=1,am2=3-0=3,∑a＝1+3+2+2=8,正确判断多边形包含窗口a12=1-7=-6(<-4)=-6+8=2,a23=3-1=2,a31=7-3=4,若a=4不做特殊处理，则∑a＝2+2+4=8,把多边形与窗口分离误判为包含窗口。若把线段P1P3分成两段，则a3m=0-3=-3,am1=7-0=7(>4)=7-8=-1,∑a＝2+2-3-1=0,正确判断多边形与窗口分离。2021/8/236 第九章：真实感图形学2021/8/237 第九章：真实感图形学下列情况之一发生时，窗口足够简单，可以直接显示：所有多边形均与窗口分离。该窗口置背景色只有一个多边形与窗口相交，或该多边形包含窗口，则先整个窗口置背景色，在对多边形在窗口内部分扫描线算法绘制。有一个多边形包围了窗口，或窗口与多个多边形相交，但有一个多边形包围窗口，而且在最前面最靠近观察点。2021/8/238 第九章：真实感图形学光线投射算法思想：考察由视点出发穿过观察屏幕的一象素而射入场景的一条射线，则可确定出场景中与该射线相交的物体。在计算出光线与物体表面的交点之后，离象素最近的交点的所在面片的颜色为该象素的颜色；如果没有交点，说明没有多边形的投影覆盖此象素，用背景色显示它即可。从光线投射算法与Z缓冲器算法相比，仅仅是内外循环颠倒一下顺序，所以它们的算法复杂度类似。区别在于光线投射算法不需要Z缓冲器。为提高算法效率可以使用包围盒技术，空间分割技术以及物体的层次表示方法等来加速。2021/8/239 第九章：真实感图形学图9.20将通过屏幕各象素的投影线与场景中的物体表面求交2021/8/240 第九章：真实感图形学算法描述：for(屏幕上的每一象素){形成通过该屏幕象素(u,v)的射线；for(场景中的每个物体)将射线与该物体求交；if(存在交点)以最近的交点所属的颜色显示象素(u,v)else以背景色显示象素(u,v)}2021/8/241 小学常见病句类型原则：句子的原意要保留、修改要恰当。修改步骤：1、读懂句子的意思；2、找准病处，对症下药；3、改后读读是否通顺，是否改变原意。 九种类型：一、成份残缺这类病句主要有2种类型。 1、句子缺少了主要成份。例1：正在仔细地批改学生的作业。例2：我们从小讲卫生的好习惯。例3：校园里到处洋溢着欢乐。2、句子中多了一些词语造成成份残缺。例：经过这次活动，使我受到了深刻的教育。 二、用词不当　　这类病句主要有2种类型。1、用错了近义词。例：红军长征时期的生活非常艰巨。2、用错了关联词。例：虽然我们是为人民服务的，但是我们有缺点，就不怕别人批评指出。 三、搭配不当　　这类病句主要有3种类型。1、句中主要成份不搭配。例：他的写作水平明显改进了。2、修饰限制的词语与中心词不搭配。例：农民伯伯在山坡上种了许多欣欣向荣的果树。3、一个词语和两个词语搭配，其中一个搭配，另一个不搭配。例：星期天，我在家里写了一篇文章和一幅图画。 四、词序颠倒　　这类病句主要有3种类型。1、主动者和被动者颠倒。例：集邮对我特别感兴趣。2、先后发生的几件事颠倒。例：气象小组的同学记录并收听了天气预报。3、修饰限制的词语用错了对象。例：在回家的路上，他唱起心情舒畅的歌。 五、重复累赘　　这类病句主要有3种类型。1、句子中用了相同意思的几个词语。例：那个房间非常宽敞得很。2、修饰限制的词语与中心词中的字意思重复。例：松树屹立在陡峭的险峰上。3、句子中用了没有必要用的词语。例：那个三条边的三角形画好了。 六、前后矛盾　　这类病句主要有2种类型。1、句子的主要意思前后矛盾。例：这个养猪场养的猪不少于500头左右。2、修饰限制的词语与中心词相矛盾。例：今年春天的这场秋雨下得真不是时候。 七、指代不明　　代词分为人称代词［我、你、他（她、它）、我们……］，指示代词［这、那、这里、那儿……］和疑问代词［谁、哪里］三种，指代不明的病句指的是代词使用错误。这类病句主要有2种类型。1、一个代词同时代替几个人或物，造成指代混乱。例：刘明和陈庆是好朋友，他经常约他去打球。2、指示代词和疑问代词误用。例：哪里有困难，他就出现在那里。 八、归类不当　　这类病句主要有3种类型。1、不是同一类的词语放在一起当作同一类的；例：《中国少年报》和《科学画报》这两种报纸我都爱看。2、范围大小不同的词放在一起。例：秋天到了，地里的庄稼和稻子成熟了。3、分类标准不一样的词放在一起。例：参加这次劳动的有工人、农民和青年等。 九、不符事理　　这类病句指的是句子的意思不符合生活实际。例1：他异口同声地说：“这里的风景真美。例2：这明月高悬、繁星满天的夜空真美。 想一想下列的病句属于哪一种类型的，然后用正确的修改符号修改，不能改变原来的句子意思。1、妈妈烙的饼和馒头很好吃。2、我遇到困难的时候，同学们总是虚心而热情地帮助我。3、河南省的名胜古迹有开封的相国寺，登封的少林寺，郑州的黄河公路大桥。4、多读好书，可以丰富和提高我们的知识。 5、气象小组的同学，每天早上都记录和收听当天的天气预报。6、妈妈常对我说起那过去的往事，要我们珍惜今天的幸福生活。7、出席今天会议的有工人、学生、机关干部等一百多人参加了晚会。8、我们从小要学会爱劳动的好习惯。9、丁叔叔被评为“优秀党员”的光荣称号。10、每个人都难免没有缺点。 11、两辆新旧车子，骑起来就是不一样啊！12、这本书的内容和插图都很精美。13、指南针、造纸、印刷术、火药是我国的四大发明之一。14、我们家的生活在逐步提高和改善。15、队员们和师生们一起唱着校园歌声。16、全体教师和班主任和我们一起参加升旗仪式。'