第八章 真实图性感显示技术(精品)

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,第,8,章,真实感图形显示技术,颜色模型、光照模型和透明性,1,阴影生成、纹理映射,2,隐藏线和隐藏面的消除,3,基本检测,4,画家算法、深度缓冲算法,5,扫描线算法、区域细分算法,5,本章知识结构图,8.1,颜 色 模 型,研究内容,RGB,颜色模型,CMY,颜色模型,HSV,颜色模型,颜色模型就是指某个三维颜色空间中的一个可见光子集，它包含某个颜色域的所有颜色。例如，,RGB,颜色模型就是三维直角坐标颜色系统的一个单位正方体。颜色模型的用途是在某个颜色域内方便的指定颜色，由于每一个颜色域都是可见光的子集，所以任何一个颜色模型都无法包含所有的可见光。大多数的彩色图形显示设备一般都是使用红、绿、蓝三原色，我们的真实感图形学中的主要的颜色模型也是,RGB,模型，但是红、绿、蓝颜色模型用起来不太方便，它与直观的颜色概念如色调、饱和度和亮度等没有直接的联系。在本节中，除了讨论,RGB,颜色模型外，还要介绍常见的,CMY,、,HSV,等颜色模型。,8.1.1 RGB,颜色模型,RGB,颜色模型通常使用于彩色阴极射线等彩色光栅图形显示设备中，它是我们使用最多最熟悉的颜色模型。它采用三维直角坐标系。红、绿、蓝原色是加性原色，各个原色混合在一起可以产生复合色，如下图所示。,8.1.2 CMY,颜色模型,以红、绿、蓝的补色青,(Cyan),、品红,(Magenta),、黄,(Yellow),为原色构成的是,CMY,颜色模型，常用于从白光中滤去某种颜色，又被称为减性原色系统。,CMY,颜色模型对应的直角坐标系的子空间与,RGB,颜色模型所对应的子空间几乎完全相同，差别仅仅在于前者的原点为白，而后者的原点为黑。前者是定义在白色中减去某种颜色来定义一种颜色，而后者是通过从黑色中加入颜色来定义一种颜色。,了解,CMY,颜色模型对于我们认识某些印刷硬拷贝设备的颜色处理很有帮助，因为在印刷行业中，基本上都是使用这种颜色模型。我们简单地介绍一下颜色是如何画到纸张上的。当我们在纸面上涂青色颜料时，该纸面就不反射红光，青色颜料从白光中滤去红光。也就是说，青色使白色减去红色。品红颜色吸收绿色，黄色颜色吸收蓝色。现在假如我们在纸面上涂了黄色和品红色，那么纸面上将呈现红色，因为白光被吸收了蓝光和绿光，只能反射红光了。如果在纸面上涂了黄色，品红和青色，那么所有的红、绿、蓝光都被吸收，表面将呈黑色。有关的结果如图,8.3,所示。,8.1.3 HSV,颜色模型,RGB,和,CMY,颜色模型都是面向硬件的，相比较而言，,HSV(Hue,，,Saturation,，,Value),颜色模型是面向用户的。该模型对应于圆柱坐标系的一个圆锥形子集,(,如图,8.4,所示,),。圆锥的顶面对应于,V=1,，它包含,RGB,模型中的,R=1,、,G=1,、,B=1,三个面，因而代表的颜色较亮。色彩,H,由绕,V,轴的旋转角给定，红色对应于角度,0,，绿色对应于角度,120,，蓝色对应于角度,240,。在,HSV,颜色模型中，每一种颜色和它的补色相差,180,。饱和度,S,取值从,0,到,1,，由圆心向圆周过渡。由于,HSV,颜色模型所代表的颜色域是,CIE,色度图的一个子集，它的最大饱和度的颜色的纯度值并不是,100%,。在圆锥的顶点处，,V=0,，,H,和,S,无定义，代表黑色，圆锥顶面中心处,S=0,，,V=1,，,H,无定义，代表白色，从该点到原点代表亮度渐暗的白色，即不同灰度的白色。任何,V=1,、,S=1,的颜色都是纯色。,HSV,颜色模型对应于画家配色的方法。画家用改变色浓和色深的方法来从某种纯色获得不同色调的颜色。其做法是：在一种纯色中加入白色以改变色浓，加入黑色以改变色深，同时加入不同比例的白色，黑色即可得到不同色调的颜色。如图,8.5,所示为具有某个固定色彩的颜色三角形表示。,8.2,光照模型,当光照射到一个物体表面上时，会出现三种情形：首先，光可以通过物体表面向空间反射，产生反射光；其次，对于透明体，光可以穿透该物体并从另一端射出，产生透射光；最后，部分光将被物体表面吸收而转换成热。在上述三部分光中，仅仅是透射光和反射光能够进入人眼产生视觉效果。为模拟这一现象，我们建立一些数学模型来替代复杂的物理模型。这些模型就称为明暗效应模型或者光照模型。,物体所表现的颜色与光源有密切的关系。光照模型的作用就是计算物体可见表面上每个点的颜色与光源的关系，因此它是决定图形真实感的一项重要内容。物体表面发出的光是极其复杂的，它既与环境中光源的数目、形状、位置、光谱组成和光强分布有关，也与物体本身的反射特性和物体表面的朝向有关，甚至还与人眼对光线的生理和心理视觉因素有关。把这一切都通过计算机精确地计算出来是不现实的，我们只能用尽可能精确的数学模型,光照模型来模拟光和物体的相互作用，从而近似地计算物体可见表面每一点的亮度和颜色。,8.2.1,环境光,环境光是这样一种光线，它不来自任何特殊方向；它有光源，但是被周围的房间或场景多次反射，最终达到平衡，以致于变得没有方向，又称为背景光。被环境光照射的物体表面的各个方向都均等受光，如图,8.7,所示。,三维空间中任意一点对环境光的反射光强度可以用公式定量地表示为,Ie=KaIa,其中，,Ka,是物体对环境光的反射系数，与物体表面性质有关；,Ia,是入射的环境光的光强，与环境的明暗度有关。,8.2.2,漫反射,漫反射光是由物体表面的粗糙不平引起的，它均匀地向各个方向传播，与视点无关，如图,8.8,所示。漫反射光在空间均匀分布，反射光强,I,与入射光的入射角,的余弦成正比，即,I,d,=,K,d,I,p,cos,，,其中，,K,d,是漫反射系数,(0,1,的常数,),，与物体表面性质有关；,I,p,是入射光,(,光源,),的光强；,是入射光的入射角，即入射光与物体表面,设物体表面在照射点,P,处的单位法向量为,N,，,P,到点光源的单位向量为,L,，则上式可表达为如下的向量形式：,I,d,=,K,d,I,p,(,N,L,),如果有多个光源，则可以把各个光源的漫反射光照效果进行叠加，即,它跟散射光一样有方向性，但被强制地反射到另一个特定的方向。高亮度的镜面光往往能在被照射的物体表面上产生称之为亮斑的亮点。图,8.9,显示了物体被纯镜面光源照射的情景。,8.2.3,镜面反射,点光源是发光体的最简单的模型，光线从一点出发，均匀地向四周发散。它是对场景中比物体小得多的光源的合理的近似。离场景足够远的光源，如太阳，也可以用点光源来较好地模拟。,柱光源或锥光源是发出的光线有一定方向的发光体，像手电筒、探照灯等。,8.2.4,点光源与柱光源,(,锥光源,),8.3,阴影的生成,阴影体,扫描线阴影生成算法,阴影生成算法,阴影是现实生活中一个很常见的光照现象，它是由于光源被物体遮挡而在该物体后面产生的较暗的区域。在真实感图形学中，通过阴影可以反映出物体之间的相互关系，增加图形的立体效果和真实感，,8.3.1,扫描线阴影生成算法,本算法的简单描述如下：,for(,绘图窗口内的每一条扫描线,),求投影与当前扫描线相交的所有多边形,;,求上述多边形中投影与当前扫描线相交的所有边，将其记录在活化边表,AEL,中；,求,AEL,中每条边的投影与扫描线的交点按交点的,u,坐标将,AEL,中各边从左到右排序，两两配对组成一个区间；,for(AEL,中每个区间,),求覆盖该区间的所有多边形，将它们记入活化多边形表,APL,中；,在区间上任取一点，计算,APL,中各多边形在该点的深度值，记深度值最大者为,P,；用多边形,P,的颜色填充该区间；,现在，我们根据自身阴影的产生原理，归纳出它在图形处理中生成的过程如下：,(1),首先将视点置于光源的位置，以光线照射的方向为观察方向，对在光照模型下的物体实施扫描线消隐算法，判别出在光照模型下的物体的“隐藏面”，并在数据文件中加以标识。,(2),然后按实际的视点位置和观察方向，对物体进行消隐，生成消隐后的立体图形。,(3),检索数据文件，核查消隐后的图形中是否包含有光照模型下的“隐藏面”。若有，则加以阴影符号标识这些面。,扫描线阴影生成算法的图示如下：,8.3.2,阴影体,在物体空间中，按照阴影的定义，若光源照射到的物体表面是不透明的，那么在该表面后面就会形成一个三维的多面体阴影区域，该区域被称为阴影体,(Shadow Volume),。,该算法中涉及大量的复杂三维布尔运算，对于场景中的每一个光源可见面的阴影域多面体都要进行求交运算，算法的计算复杂度是相当可观的。因而这个算法关键是如何有效地判定一个物体表面是否包含在阴影域多面体之内。,Crow,于,1977,年提出了这样的一个算法来生成阴影。他的算法是基于扫描线隐藏面消除算法的。显示的时候，阴影域多面体和普通的物体多边形一起参加扫描和排序，对于每一条扫描线，可以计算出扫描水平面和阴影域多面体及普通的物体多边形的交线，其中阴影域多面体的交线是封闭多边形，而普通物体多边形是一条直线，利用该直线和封闭多边形在光源视线下的相互遮挡关系，可以很方便地确定在该扫描线上物体表面是否是阴影区域。,8.4,纹理映射,几何纹理,颜色纹理,三维裁剪,纹理映射,(Texture Mapping),的方法运用得很广，尤其描述具有真实感的物体。比如绘制一面砖墙，就可以用一幅真实的砖墙图像或照片作为纹理贴到一个矩形上，这样，一面逼真的砖墙就画好了。如果不用纹理映射的方法，则墙上的每一块砖都必须作为一个独立的多边形来画。另外，纹理映射能够保证在变换多边形时，多边形上的纹理图案也随之变化。,纹理映射有许多种情况。例如，任意一块纹理可以映射到平面或曲面上，且对光亮的物体进行纹理映射，其表面可以映射出周围环境的景象；纹理还可按不同的方式映射到曲面上，一是可以直接画上去,(,或称移画印花法,),，二是可以调整曲面颜色或把纹理颜色与曲面颜色混合；纹理不仅可以是二维的，也可以是一维或其他维的。,8.4.1,颜色纹理,采用纹理映射技术可模拟物体表面精致的不规则的颜色纹理。这种技术是将任意的平面图形或图像覆盖到物体的表面，在物体的表面上形成真实的彩色纹理。计算机图形学中的颜色纹理，可定义为一光亮度函数。最常用的纹理函数是二维光亮度函数。纹理函数可由一数学模型定义，也可用一幅平面图像表示。,1,长峰波纹理函数,常用的纹理模型是长峰波,(Long Create Wave),纹理模型。设纹理函数为,F(u,v),背景光亮度为,IG,，则长峰波模型定义为一系列正弦或余弦函数的和，即,两个正交余弦波产生的正四边形纹理，如下图所示：,在纹理映射技术中，最常见的纹理是二维纹理。映射将这种纹理变换到三维物体的表面，形成最终的图像。我们给出一个二维纹理的函数表示：,它的纹理图像模拟国际象棋上黑白相间的方格，如下图所示。,二维纹理还可以用图像来表示，用一个,M,N,的二维数组存放一幅数字化的图像，用插值法构造纹理函数，然后把该二维图像映射到三维的物体表面上。为了实现这个映射，就要建立物体空间坐标,(x,，,y,，,z),和纹理空间坐标,(u,，,v),之间的对应关系，这相当于对物体表面进行参数化，反求出物体表面的参数后，就可以根据,(u,，,v),得到该处的纹理值，并用此值取代光照明模型中的相应项。,两个经常使用的映射方法是圆柱面映射和球面映射。对于圆柱面纹理映射，由圆柱面的参数方程定义，可以得到纹理映射函数。如果参数方程如下式所示：,对给定圆柱面上一点,(x,，,y,，,z),，可以用下式反求参数：,对于球面纹理映射，由球面参数方程：,对给定球面上一点,(x,，,y,，,z),，可以用下式反求参数：,8.4.2,几何纹理,为了给物体表面图像加上一个粗糙的外观，可以对物体的表面几何性质做微小的扰动，来产生凹凸不平的细节效果，就是几何纹理的方法。定义一个纹理函数,F(u,v),，对理想光滑表面,P(u,v),作不规则的位移，具体是在物体表面上的每一个点,P(u,v),，都沿该点处的法向量方向位移,F(u,v),个单位长度，这样新的表面位置变为,新表面的法向量可通过对两个偏导数求叉积得到。,由于,F,的值相对于上式中其他的量很小，可以忽略不计，有,扰动后的向量单位化用于计算曲面的明暗度，可以产生貌似凹凸不平的几何纹理。,8.5,透明性,折射透明性,无折射的透明,透明性,对于透明或半透明的物体，在光线与物体表面相交时，一般会产生反射与折射，经折射后的光线将穿过物体而在物体的另一个面射出，形成透射光。如果视点在折射光线的方向上，就可以看到透射光。,1980,年,Whitted,提出了一个光透射模型：,Whitted,模型，并第一次给出,光线跟踪算法,的范例，实现了,Whitted,模型。,1983,年，,Hall,在此进一步给出,Hall,光透射模型，考虑了漫透射和规则透射光。,8.5.1,无折射的透明,由于透明物体可以透射光，因而可以透过这种材料看到后面的物体，由于光的折射通常会改变光的方向，要在真实感图形学中模拟折射，需要较大的计算量，在,Whitted,和,Hall,提出光透射模型之前，为了能够看到一个透明物体后面的东西，就有一些透明效果模拟的简单方法。,在这类方法中主要的是颜色调和法，该方法不考虑透明体对光的折射以及透明物体本身的厚度，光通过物体表面是不会改变方向的，故可以模拟平面玻璃，隐藏面消除算法可以用于实现模拟这种情况。,设,t,是物体的透明度，,t,=0,表示物体是不透明体；,t,=1,表示物体是完全透体。我们可以看到物体后面的背景和其他物体，这些物体的前后位置可以通过隐藏面消除算法计算出来。如下图所示，设过像素点,(,x,y,),的视线与物体相交处的颜色,(,或光强,),为,I,a,，视线穿过物体与另一物体相交处的颜色,(,或光强,),为,I,b,，则像素点,(,x,y,),的颜色,(,或光强,),可由以下颜色调和公式计算：,8.5.2,折射透明性,1,. Whitted,光透射模型,在简单光照明模型的基础上，加上透射光一项，就得到,Whitted,光透射模型：,其中，,I,t,为折射方向的和射光强度；,Kt,为透射系数，为,0,1,之间的一个常数，其大小取决于物体的材料。如果该透明体又是一个镜面反射体，应再加上反射光一项，以模拟镜面反射效果。于是得到,Whitted,整体光照模型：,这里,，,Is,为镜面反射方向的入射光强度；,Ks,为镜面反射系数，为,0,1,之间的一个常数；其大小同样取决于物体的材料。,需要说明的是，所谓的折射方向和镜面反射方向都是相对于视线而言的，它们实际上是使视线在折射方向和反射方向的入射光的方向，但方向与光传播的方向相反。如下图所示，,S,是视线,V,的镜面反射方向，,T,是,V,的折射方向。在简单光照明模型的情况下，折射光强和镜面反射光强可以认为是折射方向上和反射方向上的环境光的光强。,用,Whitted,模型计算光照效果，剩下的关键问题就是计算反射与折射方向。即已知视线方向,V,，求其反射方向,S,与折射方向,T,。然后可求出反射与折射方向上与另一物体的交点。关于上面的问题可以用几何光学的原理来解决。给定视线方向,V,与法向方向,N,，视线方向,V,的反射方向,S,可以由下式计算,:,S=2N (N,V)-V,那么在给定视线方向,V,与法向方向,N,以后，如何,求,V,的折射方向,T,呢？首先我们令,V,N,T,均为单位向量，,1,是视点所在的介质折射率，,2,为物体的折射率。根据折射定律，入射角,1,和折射角,2,有如下关系：,Whitted,的折射方向计算公式为：,T,=,K,f,(,N,-,V,)-,N,是计算所得的,T,为非单位向量。,Heckbert,给出了一个更为简单的计算公式：,2,Hall,光透射模型,Hall,光透射模型是在,Whitted,光透射模型的基础上推广而来的，它能够模拟透射高光的效果。实际上，就是在,Whitted,模型的光强计算中加入光源引起的规则透射分量，同时还可以处理理想的漫透射。,用,Lambert,余弦定律描述点,P,处的漫透射光的光强为,Idt=Ip,Kdt,(-N,L) Ip,为入射光的强度，即点光源的强度；,Kdt,为物体的漫透射系数，在,0,与,1,之间；,L,为光源方向；,N,为面法向。,对于理想的透明介质，只有在光线的折射方向才能见到透射光，其他方向均见不到。对半透明的物体，视点在透射方向附近也能见到部分透射光，但强度随视线,V,与光线的折射方向,T,的夹角的增大而急剧减小,(,如图,8.17,所示,),。这种规则透射光的光强比漫透射光强高出好多倍，在折射方向周围形成高光域，这个高光域的光强要比其周围区域大得多。,Hall,用下面的公式模拟透射高光现象：,I,t,=,I,p,K,t,(,T,V,),n,其中，,I,t,规则透射光在视线方向的强度；,I,p,为点光源的强度；,K,t,为物体的透明系数；,n,为反映物体表面光泽的常数。简单光照明模型作如下假设：,（,1,） 假定光源在无穷远处，光线方向,L,为常量；,（,2,） 视点在无穷远处，视线方向,V,为常量；,（,3,）用,(,),代替,(,),，这里,H,t,可以视为一个虚拟的理想透射面的法向，使视线恰好为光线的折射方向,(,如下图所示,),。,在使用,Hall,光透射模型的时候，还需要注意如下几点。,（,1,）只有视点与光源在透明物体的两侧时，才能透过透明体看到透射高光。,（,2,）光线射入和射出透明体时均会产生折射，我们通常不考虑第一次折射。,（,3,） 折射的临界角现象，当光线从高密度介质射向低密度介质，而且入射角大于临界角时，不再发生折射，而产生内部反射，这时的临界角为,8.6,隐藏线的消除,。,在计算机屏幕上显示或绘制三维物体时，不能将其所组成的面和线都画出来，否则难于确定物体的形状和位置，同时也给看图带来许多困难，只能画出其中可见的部分，消去隐藏线和隐藏面，或者用虚线画出。,为了消去隐藏线，只要把表示三维物体的每一条线,(,如边界线、轮廓线、交线,),与每一个组成物体的不透明面进行遮蔽判断，即是否全部、部分或没有被遮蔽。把不可见线段或部分不可见线段与可见线段或部分可见线段区分开来。最后画出可见线段和线段的可见部分，不画或用虚线画不可见线段和线段的不可见部分，就得到经过消隐处理的线条图。,为了消去隐藏面，则要把每一个组成物体的面,(,平面或曲面,),与每一个不透明面进行遮蔽判断，把可见的或部分可见的与不可见的或部分不可见的区别开来。最后绘出那些可见面或面的可见部分，就得到经过消隐处理的立体图。,消隐处理是计算机绘图中重要的问题，目前已提出的算法基本上可以分为两大类：一类是隐藏线消除算法，称为隐线算法；另一类是隐藏面消除算法，称为隐面算法。不管是隐线算法还是隐面算法，它们执行的空间分为如下情况：一是算法在描述物体的坐标系空间中进行，这样的算法又叫做物体空间算法或用户空间算法；二是算法在图像空间中进行，这样的算法就叫做图像空间算法或屏幕空间算法；三是算法同时在物体空间和图像空间中实现，如下面的画家算法。,未作消隐处理的输出图形和做消隐处理的输出图形如下图所示。,凹多面体的消隐比凸多面体的消隐复杂，因为凹多面体的朝前面并不都是完全可见的，存在着相互遮挡问题。如果一个朝前面被另一个朝前面完全遮挡，则这个朝面显然不可见，如果被遮挡住一部分，则遮挡处不可见，未遮住的另一部分还要继续与其他朝前面比较，以确定其最终可见的部分。因此，凹多面体表面的可见性分为如下三种,：,完全可见；完全不可见；,部分可见部分不可见。其消隐过程一般分为如下三步：,（,1,）,首先求出平面体各表面的外法线方向，即,值，将其所有的构成表面分为潜在可见面即朝前面,( 0),和不可见面,( 0),两类。,（,2,）,对潜在的可见面进行深度测试和遮挡关系的判定计算，其过程可简述为：依次提取当前潜在可见面的每一条边框线段，检查其是否被其他的潜在可见面挡住了或挡住了线段上的哪些部位,子段。,（,3,）,绘制可见线段及潜在可见线段的最终可见子段，输出图形。经过包含性检验和深度测试后，潜在可见面的每一条边框线段的可见性情况分为三种情形：,(a),完全可见，没有被潜在可见面遮挡；,(b),部分可见，即具有可见子段，经过与其他潜在可见面逐一检查后，当前线段上只有所有表面都未挡住的部位才是最终的可见子段，最终输出的是最终被确定为可见的子段；,(c),完全不可见，即线段被可见表面完全遮挡住了。,消隐面算法,图形,用户界面,8.7,隐藏面的消除,画家算法,深度缓冲器算法,(Z,缓冲区算法,),扫描线算法,区域细分算法,基本检测,8.7.1,基本检测,1,深度检测,在物体的元素到视点的距离深度上，如果平面多边形元素,P,的最近顶点离视点的距离,Z,min,(P),比平面多边形元素,Q,的最远顶点离视点的距离,Z,max,(Q),还远，即,Z,max,(Q) ,且,，那么,P,和,Q,的包围盒在,x,方向分离；或者若,且,q,1,，则,P,和,Q,的包围盒在,y,方向分离，否则相互重叠。同样，只要将,x,改成,y,，就可得到,P,和,Q,的包围盒在,y,方向分离的判断条件。,3,平面多边形位置检测,8.7.2,画家算法,本算法过程与画家创作一幅油画的过程类似，因此而得名。画家画油画时，先画背景，然后画中间景物，最后才画近景。画家通过这种顺序构造画面，从而解决隐藏面或可见性问题。,用计算机绘制图形，也可以建立类似的深度顺序,按照图形中各元素,(,如平面多边形,),到视点的距离确定一个深度优先级表，从而使图形中任意两个元素在深度上均不重叠。算法执行时，先从表中离视点最远的图形元素开始，依次将每个元素写入帧缓冲器。表中离视点较近的元素覆盖帧缓冲器中原有的内容，于是隐藏面自然消除，最后得到物体的图形，实际上是物体可见部分的图形。,1,画家算法,画家算法也可称为表优先级算法。开始，观察方向经变换后与,z,轴负向重合,(,即视点位于,z,轴负向的无穷远处,),，以变换后平面多边形顶点的最大,Z,值,Z,max,.,作为排序关键码，建立初步的深度优先级表。算法处理每一平面多边形时，动态地计算和产生一个新的深度优先级表。表中第一个平面多边形是具有最大,Z,值的多边形，即到位于,Z,轴负向无穷远处视点的距离最远的平面多边形，记为,P,0,，表中第二个平面多边形记为,Q,0,，检查表上每个平面多边形与,P,的关系。,2,要注意几点,深度优先级矛盾,2),新增棱边后平面多边形顶点顺序,8.7.3,深度缓冲器算法,(Z,缓冲区算法,),这种隐面算法是比较简单的一种。它的基本思路是：对于显示屏上的每一个像素，记录下位于该像素内最靠近观察者的那个景物面的深度坐标，同时相应记录下用来显示该景物面的颜色,(,或灰度,),，那么所有记录下的这些像素所对应的颜色就可以形成最后要输出的图形。,深度缓冲器算法的基本步骤如下：,(1),为深度数组和颜色数组赋初值。即对于显示屏上的全部像素，置,depthij = max,；置,colorij = bkcolor(,背景色,),。,(2),对于景物中的每个多边形平面，计算出该多边形平面的投影所包含的全部像素的位置，然后对所包含的全部像素逐一做如下两步工作。,(a),计算出该多边形在对应于像素,(i, j),处的深度坐标值,z,。,(b),比较此,z,值和原先深度数组所记录的值,depthij,的大小。,采用分区的方法来实施深度缓冲器算法，可以大大减少所需的存储量，并且对最终生成图形的质量没有丝毫影响。如果可以适当考虑降低一些图形的质量，例如降低图形的分辨率，那么就可以采用另外一种简化方法：扩大“像素点”的面积。,8.7.4,扫描线算法,扫描线算法实质上可以说是深度缓冲器算法的一种延伸。假如我们在屏幕的分区中采用仅在,y,方向,(,高的方向,),细分，而在,x,方向不分，那么整个显示屏幕将分成许多狭长的子区。如果在,y,方向是以像素为单位细分，那么这样得到的每个子区就是一条线，我们称之为“扫描线”。,扫描线算法的基本思路是：当包含一条扫描线的水平平面,(,称为扫描线平面,),与景物中的立体相交时，组成立体的诸表面就会与该扫描线平面相交而形成若干条截交线段，如下图,(a),所示，这些截交线段把整条扫描线分割成一些间隔，如图,(b),所示。,实施扫描线算法的基本步骤如下：,(1),定义两个数组,：深度数组,depthm,和颜色数组,colorm,，用以保存单条扫描线上的数据值。,(2),算法开始执行时，先对深度数组和颜色数组赋初值。,即置,depthi,max; colori =bkcolor,。,(3),在,y,方向上排序。在逐条处理扫描线的过程中，扫描线平面的位置是不断变化的。,在这个变化的过程中，有些立体表面要开始进入扫描线平面，有些则要退出扫描线平面，还有一些则仍然留在扫描线平面中，这是一个动态的过程。所以要判别出哪些表面与当前的扫描线平面相交，从而可以求出当前扫描线平面与表面的截交线段。,(4),在,x,方向上排序。,按照落在当前扫描线平面内各线段两端,x,坐标值的大小，顺序将扫描线划分为若干个间隔。,(5),按照上面介绍的对不同间隔的处理办法，确定不同类别的间隔所在区域的颜色值，并置入颜色数组。,(6),当一条扫描线处理完毕后，就,把颜色数组中的内容复制到帧缓冲器中,(,或直接输出到屏幕上,),。然后从步骤开始继续处理下一条扫描线。,8.7.5,区域细分算法,区域细分算法的基本思路是：对图形显示屏幕采取递归细分的办法，以产生大小不等的窗口，使得落在该窗口内的图形变得相当简单，以至于能够容易地决定其显示情况。,如果在某个区域内图形的情况很复杂，那么这个窗口再分的过程会一直进行下去，窗口将越分越小。但整个过程总能圆满结束，因为不断再分的结果总会使得落在窗口内的图形变成是简单的情况。极限情况是分到最后把窗口分成只有一个像素点那么大，此时只需要显示该像素点所包含的图形的颜色，如图,(a),所示。,在算法的执行过程中，窗口和图形中多边形之间的关系可以归纳为以下三种情况：,(1),窗口和多边形分离，如图,(b),中的,a,和,b,。,(2),窗口和多边形相交，指多边形部分地或全部地落入到窗口内的一个区域，如图,8(b),中的,c,和,d,。,(3),窗口被多边形所包含，如图,(b),中的,e,。,对这三种情况的处理方法如下：,(1),因为多边形不会影响窗口内的图形输出情况，所以可以把这种无关的多边形舍去。,(2),如果仅有一个多边形和窗口相交，或者虽有几个多边形和窗口相交，但这几个多边形落入窗口内的部分并不相互重叠；那么输出情况是容易决定的，只需要在多边形占据的窗口内部分显示该多边形表面的颜色。如果不是属于这种情况，则是在窗口内同时存在几个相互交叉重叠的多边形，那么就要进一步细分窗口。,(3),如果窗口被一个多边形或者是被几个多边形所包含，那么就要找出距离视点最近的那个多边形，并且要判断其他凡是与该窗口有关,(,不管是相交还是包含,),的多边形是否全部位于该包含着窗口的多边形之后。如果是，则该窗口内全部显示该多边形表面的颜色；如果不是，则要再进一步细分窗口。,