2024/9/11 / 41第九章：真实感图形学第九章：真实感图形学 9.1 消隐消隐真实图形在仿真模拟、几何造型、广告影视、指挥控制和科学计算的可视化等许多领域有广泛应用。用计算机生成三维物体的真实图形，是计算机图形学研究的重要内容。显示设备描述物体的图形时，必须把三维信息经过某种投影变换，在二维的显示表面上绘制出来。由于投影变换失失去去了了深深度度信信息息，往往导致图形的二义性(如图9.1所示)。要消除二义性，就必须在绘制时消除被遮挡的不可见的线或面，称作消除隐藏线和隐藏面，或简称为消隐。经过消隐得到的投影图称为物体的真实图形。2024/9/12 / 41第九章：真实感图形学第九章：真实感图形学图9.1长方体线框投影图的二义性图9.2线框图图9.3消隐图图9.4真实感图形2024/9/13 / 41第九章：真实感图形学第九章：真实感图形学l 消隐的分类消隐的分类消隐的对象是三维物体。三维体的表示：边界表示和CSG(结构实体几何学)表示等。最简单的表示方式：用表面上的平面多边形表示。如物体的表面是曲面，则将曲面用多个平面多边形近似。消隐结果与观察物体有关，也与视点有关。按消隐对象分类按消隐对象分类1. 线消隐线消隐消隐对象是物体上的边，消除物体上不可见的边。2. 面消隐面消隐消隐对象是物体上的面，消除物体上不可见的面。2024/9/14 / 41第九章：真实感图形学第九章：真实感图形学Southerland根据消隐空间消隐空间的不同，将消隐算法分为三类：1.物体空间的消隐算法物体空间的消隐算法 (光线投射、光线投射、Roberts) 将场景中每一个面与其他每个面比较，求出所有点、边、面遮挡关系。2.图像空间的消隐算法图像空间的消隐算法 (Zbuffer、扫描线、扫描线、warnock)对屏幕上每个象素进行判断，决定哪个多边形在该象素可见。3.物体空间和图像空间的消隐算法物体空间和图像空间的消隐算法 (画家算法画家算法)在物体空间中预先计算面的可见性优先级，再在图像空间中生成消隐图。2024/9/15 / 41第九章：真实感图形学第九章：真实感图形学l 消除隐藏线消除隐藏线 对造型的要求对造型的要求在线框显示模型中，用边界线表示有界平面，用边界线及若干参数曲线表示参数曲面，所以待显示的所有实体均为线。但线不可能对线有遮挡关系，只有面或体才有可能对线形成遮挡。故消隐算法要求造型系统中有面的信息，最好有体的信息。正则形体的消隐可利用其面的法向量，比一般情况快的多。 坐标变换坐标变换为运算方便，一般通过平移、旋转、透视等各种坐标变换，将视点变换到Z轴的正无穷大处，视线方向变为Z轴的负方向。变换后，坐标Z值反映了相应点到视点的距离，作为判断遮挡的依据。对视角以外的物体应先行虑掉，减少不必要的运算。 2024/9/16 / 41第九章：真实感图形学第九章：真实感图形学 线消隐中最基本的运算线消隐中最基本的运算判断面对线的遮挡关系。体也要分解为面，再判断面与线的遮挡关系。在遮挡判断中，要反复地进行线线、线面之间的求交运算。图9.5遮挡关系2024/9/17 / 41第九章：真实感图形学第九章：真实感图形学平面对直线段的遮挡判断算法平面对直线段的遮挡判断算法不失一般性，取视点在Z轴正无穷远，视线为Z轴负方向，物体投影到XOY平面上。1.若线段的两端点及视点在给定多边形的同侧，线段不被其遮挡，转7（结束）。(深深度度检检测测，多边形顶点的最大Z坐标小于等于线段端点的最小Z坐标，多边形完全在线段之后，不可能遮挡线段，即线段完全可见)2.若线段的投影与多边形投影的包包围围盒盒(覆覆盖盖多多边边形形投投影影的的最最小小矩矩形形区区域域)无交，线段不被给定多边形遮挡，转7（结束）。3.求直线与相应多边形的交。若无交点，转4。否则，交点在线段内部或外部。若交点在线段内部，交点将线段分成两段，与视点同侧的一段不被遮挡，另一段在视点异侧，转4再判；若交点在线段外部，转4。2024/9/18 / 41第九章：真实感图形学第九章：真实感图形学4.求所剩线段(可能被遮挡部分)的投影与多边形边界投影的所有交点，并根据交点在原直线参数方程中的参数值求出Z值(即深度)。若无交点，转5。5.以上所求得的各交点将线段的投影分成若干段，求出第一段中点。6.若第一段中点在平面的投影内，则相应的段被遮挡，否则不被遮挡；其他段的遮挡关系可依次交替取值进行判断。7.结束。2024/9/19 / 41第九章：真实感图形学第九章：真实感图形学图9.6视点与线段同侧图9.7包围盒不交图9.8分段交替取值2024/9/110 / 41第九章：真实感图形学第九章：真实感图形学线消隐算法线消隐算法基本数据结构:面表面表(存放参与消隐的面)线表线表(存放待显示的线)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;2024/9/111 / 41第九章：真实感图形学第九章：真实感图形学如果消隐对象有N条棱，当N很大时，用两两求交的方法工作量很大O(N2)。为提高算法效率，要设法减少求交的工作量。设V为由视点出发的观察向量，N为某多边形面的法向量。若VN0，称该多边形为后后向向面面。若VN4则8;若-4则8若4，将该边在窗口边界分为两段，对每段求。对每边的求和得：例1:a12=2-0=2a23=4-2=2a34=6-4=2a45=7-6=1a51=0-7=-7(4)=7-8=-1a23=7-7=0a34=0-7=-7(-4)=-7+8=1a45=1-0=1a51=0-1=-1可判断多边形与窗口分离2024/9/136 / 41第九章：真实感图形学第九章：真实感图形学a=4的特殊情况的特殊情况1. a12=3-7=-4, a23=2, a31=2,若a-4不做特殊处理，则a0,把多边形包含窗口误判为与窗口分离。若 把 线 段 a12分 成 两 段 ， 则 a1m=0-7=-7(-4)=-7+8=1, am2=3-0=3,a1+3+2+2=8,正确判断多边形包含窗口2. a12=1-7=-6(4)=7-8=-1,a2+2-3-1=0,正确判断多边形与窗口分离。2024/9/137 / 41第九章：真实感图形学第九章：真实感图形学2024/9/138 / 41第九章：真实感图形学第九章：真实感图形学 下列情况之一发生时，窗口足够简单，可以直接显示：下列情况之一发生时，窗口足够简单，可以直接显示：1.所有多边形均与窗口分离。该窗口置背景色2.只有一个多边形与窗口相交，或该多边形包含窗口，则先整个窗口置背景色，在对多边形在窗口内部分扫描线算法绘制。3.有一个多边形包围了窗口，或窗口与多个多边形相交，但有一个多边形包围窗口，而且在最前面最靠近观察点。2024/9/139 / 41第九章：真实感图形学第九章：真实感图形学5. 光线投射算法光线投射算法思思想想：考察由视点出发穿过观察屏幕的一象素而射入场景的一条射线，则可确定出场景中与该射线相交的物体。在计算出光线与物体表面的交点之后，离象素最近的交点的所在面片的颜色为该象素的颜色；如果没有交点，说明没有多边形的投影覆盖此象素，用背景色显示它即可。从光线投射算法与Z缓冲器算法相比，仅仅是内外循环颠倒一下顺序，所以它们的算法复杂度类似。区别在于光线投射算法不需要Z缓冲器。为提高算法效率可以使用包围盒技术，空间分割技术以及物体的层次表示方法等来加速。2024/9/140 / 41第九章：真实感图形学第九章：真实感图形学图9.20将通过屏幕各象素的投影线与场景中的物体表面求交2024/9/141 / 41第九章：真实感图形学第九章：真实感图形学算法描述算法描述：for(屏幕上的每一象素)形成通过该屏幕象素(u,v)的射线；for(场景中的每个物体)将射线与该物体求交；if(存在交点)以最近的交点所属的颜色显示象素(u,v)else以背景色显示象素(u,v)