计算机图形学简明教程_第7章

《计算机图形学简明教程_第7章》由会员分享，可在线阅读，更多相关《计算机图形学简明教程_第7章（52页珍藏版）》请在金锄头文库上搜索。

1、 场景可见部分的判断过程称为可见线判定或可见 面判定，也可称为隐藏线消除或隐藏面消除。1以构成图像的每一个像素 为处理单元，确定场景中 的所有在该像素上有投影 的表面，相对于观察点可 见的表面。适于面消隐。2以三维场景中的物体对象 为处理单元，在所有对象 之间进行比较，除去完全 不可见的物体和物体上不 可见的部分。 适于面消隐 也适于线消隐。窗口像素视点图7.1 以像素为对象的消隐算法xz窗口平行投影y图7.2 以物体为对象的消隐算法前提：把物体看成是由一个或多个多边形（或更复杂的面片）组成！假定构成物体 的面不能相互 贯穿，也不能 有循环遮挡的 情况。(a)(b)贯穿和循环遮挡如果构成物体的

2、面不满足该假 定，可以把它们剖分成互不贯 穿和不循环遮挡的情况。 例如，用上图中的虚线便可把原来 循环遮挡的三个平面，分割成不存 在循环遮挡的四个面。 提 醒7.1.1347.1.27.1.3后向面消除边界盒投影规范化物体的边界盒是指能够包含该物体的一个简单的几何形状， 如矩形，圆，长方体等。 边界盒 ：采用边界盒在消隐中的好处：可避免不必要的裁剪运算，避免在物体或它们的投影之间进 行不必要的比较运算。 xyz图7.4 两个物 体投影在xy 平面，包围 投影的边界 盒为矩形注意选取适当的边界盒： 不可太小，也不可太大。 一种简单的求边界盒的方法： 计算多边形顶点坐标的最大值和 最小值得到（即采

3、用矩形边界盒） A边界盒不相交：在Oxy平面投影的边界盒，两个边界盒不相交，所以两个多边形不相交。 B 边界盒相交：相交的情况可分为两种，投影相交或投影 不相交。无论哪种情况都需要做进一步的处理，以判断两物体的投影是否相交。 边界盒应用原则xyzA 不相交(a)边界盒和投影均重 叠(b) 边界盒重叠，投影不重叠 用边界盒技术判断两条直线是否相交。 举例：xminxmaxymaxyminxyQ1Q6Q5Q2Q4Q3记点vi在oxy面上的投影为 。直线段 的边界盒是包含该直线且 边平行于坐标轴的最小矩形，这个矩形由下面四个参数确定 设两个边界盒的参数为: 当它们满足: 或或或表明两个边界盒不相交，

4、则边界盒中的两条直线段也不相交。v 用球代替长方体作为边界盒可以简化判断直线同边界盒是 否相交的计算过程，即若边界球的球心到直线的距离大于 球的半径，那么直线与边界球不相交，也就与球内的物体 不相交。一个有效的确定边界球的方法是取球的中心为：取半径为：其中：进一步简化判断v 1、后向面 v 多面体表面多变形的法向可分为两种，一种是指向多面体 的外部，我们称之为外法向，一种指向多面体的内部，我 们称之为内法向。 v 必然有一些多边形表面的外法向指向与观察者相背离的方 向，这些多边形完全被多面体上其它多边形遮挡。这些被遮挡的多边形称为后向面。 v 首先消除掉这些面，去除后向面的过程称为后向面消除。

5、 思路：把显然不可见的面去掉，减少消隐过程中的 直线求交数目IJFGH，FABG，HCDI，IDEJ 所在的面为前向面 JEAF， DEABC,HGBC所在的面为后向面1）首先对多边形的顶点进行排序：设多边形F的顶点为 v1,v2,vL顶点 的坐标为 。次序如图所示2）判断后向面：如果v1,v2,vL构成凸的多边形，则向量 是F的内法线方向，如果 的z分量说明向量和z轴正方向的夹角大于90度， F的外法线方向和z轴正方向的夹角小于 90度，F为前向面。否则，即a的z分量 大于0 即 ，则F的内法向z轴正方 向的夹角大于90度，外法线方向和z轴正方向 的夹角小于90度，F为前向面。2、判断后向面

6、的方法v1v2v3 v4v5 v6v73） 可以看作是三角形v1vk vk+1在平面oxy上投影的 有向面积的二倍。 2、判断后向面的方法顶点为A，B，C的三角形面积：3）可以通过计算多边形在平面上投影的有向面积判断F 是否为后向面。有向面积sp可如下计算如果 ，则F所在的面为后向面。 如果 ，则F所在的面为前向面。注意：如果多边形是凸的，则可只取一个三角形计算有向面积sp。如 果多边形不是凸的，只取一个三角形计算有向面积sp可能会出现错误 ，即F所在的面为前向面也可能出现sp0的情况,因此，需按上式计算 多边形F的有向面积。 物体之间的遮挡关系与投影中心和投影方向 有着密切的关系，对物体的可

7、见性判定也和 投影方式有密切的关系。如果投影为垂直投影，则多边形在oxy平面 上的投影可由忽略了z坐标的顶点得到，从 而可大大减少计算量。具体如下： 如何把透视投影变为垂直投影，其本质是把棱台变成长方体 。 AB投影平面由棱台到长方体的变换把左边的棱台A变换成右边长方体B。设 (x,yz )是棱台A中任意一点，它 在投影平面的投影为 (x,y,0) ，事实上透视投影是把线段 (x,yz )和(x,y,0) 之间的点都变换成 (x,y,0)，如果能把 (x,yz )和(x,y,0)之间的点指定一个 相应的Z值，且该值不改变原线段上点之间的前后关系，就可把棱台A变 为长方体B。AB如何求解？此射影

8、变换可由下式定义 如果对的射影变换是线 性的，则不改变视见体 内各表面的前后位置关 系可以通过不改变视见 体的前后平面 z=zf和z zb，的前后位置关系实现 ，把这两个条件代入左 式，得： 7.2.17.2.2基于多边形的细分算法基于窗口的细分算法概述区域细分算法是一种分而治之(Divide-Conquer) 的算法，它把投影区域作为考察对象，如果很 容易确定投影区域内的多边形是否可见，便显 示这些多边形，否则将这些区域进一步细分， 随着不断细分，判断多边形的可见性将越来越 简单。本节介绍基于窗口的细分算法和基于多 边形的细分算法。基本思想 把物体投影到全屏幕窗口上，然后递归的将窗口一分为

9、四，如果可以确定小窗口内的多边形是否可见，则显示 这些多边形，否则，将小窗口细分为更小的窗口，递归 地执行上述过程。 子分的过程具体分析关系判断 细分后都要对多边形和窗口就下面四种关系作判断：窗口和多边形分离(图中情况1)1多边形和窗口相交(图中情况2)2窗口包围了多边形(图中情况3)3多边形包围了窗口(图中情况4)41234多边形和窗口的关系具体分析可见性判断 对以下的三种情况，窗口中多边形的可见性容易判定，不需要再对 窗口进行分割： 所有多边形均和窗口分离，则窗口内只需 显示背景色； 1只有一个多边形和窗口相交，或这个多边 形包含在窗口内。这时，先对窗口内每一 像素填上背景颜色，再对窗口内

10、多边形部 分用扫描线算法填色。 2一个多边形包围窗口，其他多边形和窗口 分离，或有多个多边形和窗口的关系分别 是相交、内含或包围，但是有一个多边形 包围窗口并且在其他多边形前面，则窗口 用包围多边形的颜色填充。 3橙色紫色具体分析分割结束条件 对不满足上述三种情况的窗口，重复细分过程，并对细 分后的各子窗口重复做同样的处理。细分若干次后，窗 口的面积就小于或等于一个像素的面积了，此时细分结 束，该窗口对应的像素的颜色可取成最靠近观察者的多 边形的颜色。 橙色紫色基本思想 用多边形的边界对区域作划分，其目的是尽量减少对区域划分的次数。该算法是对上节基于窗口细分算法的改进。由于算法在景物空间中以任

11、意指定的精度进行运算，其输出结果仍为多边形，所以算法不仅可用来处理隐藏面消除，也可用来处理多面体隐藏线消除问题。 算法描述Step1：对各多边形在深度方向作初步的排序对各多边形在深度方向作初步的排序Step2：把多边形序列中的第一个多边形（裁剪多边形）取为窗把多边形序列中的第一个多边形（裁剪多边形）取为窗口。口。 多边形序列中的其它的多边形都要被此窗口裁剪。多边形序列中的其它的多边形都要被此窗口裁剪。 Step3：裁剪结果要建立两个多边形序列表裁剪结果要建立两个多边形序列表内部表:放入位于窗口内的部分外部表:放入位于窗口外的部分yx4 321要消隐的多边形xyz43212i3i4i4oni为窗

12、口内的多边形表；no为窗口外的多边形表3o算法描述Step4：将内部表中每一个其它多边形的深度值与裁剪多边将内部表中每一个其它多边形的深度值与裁剪多边形的深度值进行比较，如果内部表中每一个其它多边形形的深度值进行比较，如果内部表中每一个其它多边形均被裁剪多边形遮挡，则裁剪多边形是完全可见的，可均被裁剪多边形遮挡，则裁剪多边形是完全可见的，可 把该多边形区域填上裁剪多边形的颜色。把该多边形区域填上裁剪多边形的颜色。 yx4 321要消隐的多边形xyz4321算法描述Step5：如果内部表中有某多边形H比裁剪区域（多边形）更靠近观察者，说明原来的预排序不对，此时要用多边 形H的原始多边形(即未被裁

13、剪时的多边形)代替原来的裁剪多边形重复上述工作。 yx4 321要消隐的多边形xyz4321！如左图如果对顶点排序 的话，则1自然要排最 前面，首先会用1做裁 剪多边形，但实际情况 是2在1的前面，所以应 该以2做新的裁剪多边 形，重复上述工作算法描述Step6：内部表中多边形的按前后顺序排好序后，接下来是对外部表中的各多边形进行排序。对外部表中各多边形的排序和对内部表中各多边形的处理方法相同，即把外部表中第一个多边形作为裁剪多边 形(假定外部表中的多边形也是按原来的多边形次序排序)，对外部表中的其它多边形作裁剪并确定遮挡关系，这一过程又形成新的外部表。裁剪过程要重复到外部表中不再有多边形为止

14、。 yx4 321要消隐的多边形xyz43214o3o基本思想将能够包含整个场景的立方体，即八叉树的根结点，按照 x，y，z三个方向中的剖面分割成八个子立方体，称为根结点的八个子结点。对每一个子立方体，如果它包含的表面 片少于一个给定的值（例如3），则该子立方体为八叉树的终端结点，否则为非终端结点并将其进一步分割成八个子立方体；重复上述过程，直到每个小立方体所包含的表 面片少于一个给定的值，分割即告终止。 具体分析1）每一终端结点对应一个求交面片表，该表中包含的是与终端结点对应的立方体中所包含的景物表面片。 2）八叉树由于其不相交立方体之间的规则结构，可以很方便的进行空间预排序，然后再根据列表

15、优先级算法便可以很容易对平行投影给 出正确的显示顺序。1223333144555566 66 777xyzv从后向前显示的八叉树排列对从后向前排 列算法，先显示最 远的八分体，然后 是与最 远的八分 体 共享一个面的三个 相邻八分体顺序任 意），然后显示最 近八分体的三个相 邻八分体（顺序任意 ），最后显示 最近的八分体 基本思想对屏幕上每一个像素点，过像素中心做一条投影线，找到此投影线与所有多边形交点中离观察者最近的点，此点的属性（颜色或灰度）值即为这一屏幕像素点的属性值。 具体实现需要两个缓冲器数组，z缓冲器数组用于存储投影线与所有多边形交点的值，帧缓冲器数组用来存储像素的颜色值。 分别设

16、为Zdepth 与Frame 对屏幕上每个点（x,y），令Zdepth xy为z的极小值，Frame xy为背景颜色。 对所有多边形做如下工作：对多边形上在像素中心有投 影的每一点（x,y）,计算其z值。若zZdepth xy，则Zdepth xyz，并将此点属性值赋给Framexy，否则说明此点离观察者较远，两个数组的值都不用改变。 12扫描线z缓冲器算法 将z缓冲器的单元数置为和一条扫描线上的像素数目相同。从最上面的一条扫描线开始工作，向下对每一条扫描线作如下处理： 把相应的帧缓冲器单元置成底色，在z缓冲器中存放z的极小值。 对每个多边形检查它在平面上的投影和当前的扫描 线是否相交。 step1step2step2相交的判断 36 7 81110118 713要消隐的物体xyo12投影和当前的扫描线若不相交，则 不考虑该多