第五章 虚拟环境的绘制技术 第三节 图形消隐.pptVIP

第五章 虚拟环境的绘制技术 第三节 图形消隐 4.2 画家算法 一、 画家算法的原理： 先把屏幕置成背景色，再把物体的各个面按其离视点的远近进行排序，离视点远者在表头，离视点近者在表尾，排序结果存在一张深度优先级表中。然后按照从表头到表尾的顺序逐个绘制各个面。由于后显示的图形取代先显示的画面，而后显示的图形所代表的面离视点更近，所以由远及近的绘制各面，就相当于消除隐藏面。这与油画作家作画的过程类似，先画远景，再画中景，最后画近景。 由于这个原因，该算法习惯上称为画家算法或列表优先算法。 ??? 二、算法： 下面给出了一种建立深度优先级表方法。先可根据每个多边形顶点z坐标的极小值Zmin的大小把多边形作一初步的排序。设Zmin最小的多边形为P，它暂时成为优先级最低的一个多边形。把多边形序列中其它多边形记为Q。 现在先来确定P和其它多边形Q的关系： Zmin(P)Zmin(Q)若Zmax(P)Zmin(Q)，则P肯定不能遮挡Q。 如果对某一多边形Q有Zmax(P)Zmin(Q)，则必须作进一步的检查。这种检查分以下五项（如图abcde所示）： a、P和Q在oxy平面上投影的包围盒在x方向上不相交 b、P和Q在oxy平面上投影的包围盒在y方向上不相交 c、P和Q在oxy平面上的投影不相交 d、P的各顶点均在Q的远离视点的一侧 e、Q的各顶点均在P的靠近视点的一侧 上面的五项只要有一项成立，P就不遮挡Q。如果所有测试失败，就必须对两个多边形在XY平面上的投影作求交运算。计算时不必具体求出重叠部分，在交点处进行深度比较，只要能判断出前后顺序即可。若遇到多边形相交或循环重叠的情况（如图f），还必须在相交处分割多边形，然后进行判断。 ?? 画家算法原理简单。其关键是如何对场景中的物体按深度排序。它的缺点是只能处理互不相交的面，而且深度优先级表中面的顺序可能出错。在两个面相交，三个以上的面重叠的情形，用任何排序方法都不能排出正确的序。这时只能把有关的面进行分割后再排序。 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)处 } ????? } ?? } } ?? Z-Buffer 的优缺点： Z-Buffer算法在象素级上以近物取代远物。形体在屏幕上的出现顺序是无关紧要的。这种取代方法实现起来远比总体排序灵活简单，有利于硬件实现。然而Z-Buffer算法存在缺点：占用空间大，没有利用图形的相关性与连续性。 Z-Buffer算法以算法简单著称，但也以占空间大而闻名。一般认为，Z-Buffer算法需要开一个与图象大小相等的缓存数组ZB，实际上，可以改进算法，只用一个深度缓存变量zb。 ?? 光线投射算法的思想是：考察由视点出发穿过观察屏幕的一象素而射入场景的一条射线，则可确定出场景中与该射线相交的物体。在计算出光线与物体表面的交点之后，离象素最近的交点的所在面片的颜色为该象素的颜色；如果没有交点，说明没有多边形的投影覆盖此象素，用背景色显示它即可。 将通过屏幕各象素的投影线与场景中的物体表面求交 算法描述： for（屏幕上的每一象素） { 形成通过该屏幕象素(u,v)的射线； ? for（场景中的每个物体） ??? 将射线与该物体求交； ? if （存在交点） ??? 以最近的交点所属的颜色显示象素(u,v) ? else 以背景色显示象素(u,v) } 光线投射算法与Z缓冲器算法相比，它们仅仅是内外循环颠倒了一下顺序，所以它们的算法复杂度类似。区别在于光线投射算法不需要Z缓冲器。为了提高本算法的效率可以使用包围盒技术，空间分割技术以及物体的层次表示方法等来加速。 ???? ????  ??? 区域子分割算法的基本思想是：把物体投影到全屏幕窗口上，然后递归分割窗口，直到窗口内目标足够简单，可以显示为止。首先，该算法把初始窗口取作屏幕坐标系的矩形，将场景中的多边形投影到窗口内。如果窗口内没有物体则按背景色显示；若窗口内只有一个面，则把该面显示出来。否则，窗口内含有两个以上的面，则把窗口等分成四个子窗口。对每个小窗口再做上述同样的处理。这样反复地进行下去。如果到某个时刻，窗口仅有象素那么大，而窗口内仍有两个以上的