计算机图形chapter

1、清华大学清华大学 计算机图形学计算机图形学第二章 光栅图形学2.1直线段的扫描转换算法2.2圆弧的扫描转换算法2.3多边形的扫描转换与区域填充2.4字符2.5裁剪2.6反走样2.7消隐清华大学清华大学 计算机图形学计算机图形学2.7 消隐 消隐的分类 消除隐藏线 消除隐藏面 画家算法 Z缓冲区(Z-Buffer)算法 扫描线Z-buffer算法 区域子分割算法 光线投射算法清华大学清华大学 计算机图形学计算机图形学基本概念 投影变换失去了深度信息，往往导致图形的二义性 要消除二义性，就必须在绘制时消除被遮挡的不可见的线或面，习惯上称作消除隐藏线和隐藏面，简称为消隐消隐。 经过消隐得到的投影图称

2、为物体的真实图形。长方体线框投影图的二义性 清华大学清华大学 计算机图形学计算机图形学 消隐的对象是三维物体。三维体的表示主要有边界表示和CSG表示等。 消隐结果与观察物体有关，也与视点有关。 线框图 消隐图 真实感图形清华大学清华大学 计算机图形学计算机图形学 物体的表示 CSG表示 边界表示(体、面、环、边、点)清华大学清华大学 计算机图形学计算机图形学2.7.1消隐的分类 按消隐对象分类 线消隐 消隐对象是物体上的边，消除的是物体上不可见的边。 面消隐 消隐对象是物体上的面，消除的是物体上不可见的面。 清华大学清华大学 计算机图形学计算机图形学Southerland按消隐空间分类 物体空

3、间的消隐算法 （光线投射、Roberts） 将场景中每一个面与其他每个面比较，求出所有点、边、面遮挡关系。 Roberts的故事：IEEE CS计算机先驱奖清华大学清华大学 计算机图形学计算机图形学 图像空间的消隐算法 (Zbuffer、扫描线、Warnock) 对屏幕上每个象素进行判断，决定哪个多边形在该象素可见。 物体空间和图像空间的消隐算法 (画家算法) 在物体空间中预先计算面的可见性优先级，再在图像空间中生成消隐图。清华大学清华大学 计算机图形学计算机图形学2.7.2消除隐藏线 对造型的要求 在线框显示模型中,要求造型系统中有面的信息，最好有体的信息。 坐标变换 将视点变换到Z轴的正无

4、穷大处，视线方向变为Z轴的负方向。清华大学清华大学 计算机图形学计算机图形学 最基本的运算 判断面对线的遮挡关系.反复地进行线线、线面之间的求交运算清华大学清华大学 计算机图形学计算机图形学平面对直线段的遮挡判断算法 视点与线段同侧 包围盒不交 分段交替取值 线面相交 线面平行，线在面后 线面交与线段外清华大学清华大学 计算机图形学计算机图形学(1) 若线段的两端点及视点在给定平面的同侧，线段不被给定平面遮挡，转7(2) 若线段的投影与平面投影的包围盒无交，线段不被给定平面遮挡，转7(3)求直线与相应无穷平面的交。若无交点，转4。否则，交点在线段内部或外部。若交点在线段内部，交点将线段分成两段

5、，与视点同侧的一段不被遮挡，另一段在视点异侧，转4再判；若交点在线段外部，转4。清华大学清华大学 计算机图形学计算机图形学(4)求所剩线段的投影与平面边界投影的所有交点，并根据交点在原直线参数方程中的参数值求出Z值(即深度)。若无交点，转5。(5) 以上所求得的各交点将线段的投影分成若干段，求出第一段中点。(6) 若第一段中点在平面的投影内，则相应的段被遮挡，否则不被遮挡；其他段的遮挡关系可依次交替取值进行判断。(7) 结束。 清华大学清华大学 计算机图形学计算机图形学前向面、后向面 为了提高算法的效率，需要设法减少求交的工作量。 若V N0，称该多边形为后向面后向面。 若V N0，称该多边形

6、为前向面前向面。 后向面总是看不见的，不会由于后向面的遮挡，而使别的棱成为不可见的。因此计算时，可以把这些后向面全部去掉，这并不影响消隐结果。 示意图 清华大学清华大学 计算机图形学计算机图形学 前向面 后向面 多面体的隐藏线消除图3中的JEAF、HCBG和DEABC所在的面均为后向面。其它为前向面。V VABCDEFGHIJN NVnVn清华大学清华大学 计算机图形学计算机图形学线消隐 基本数据结构 面表(存放参与消隐的面) + 线表(存放待显示的线) 算法 假设E为面F的一条边, 需判别F以外每一个面与E的遮挡关系.清华大学清华大学 计算机图形学计算机图形学2.7.3消除隐藏面 3.3.1

7、画家算法（列表优先算法）列表优先算法） 先把屏幕置成背景色， 再把物体的各个面按其离视点的远近进行排序，排序结果存在一张深度优先级表中。 然后按照从远到近的顺序逐个绘制各个面。 关键是如何对场景中的物体按深度排序清华大学清华大学 计算机图形学计算机图形学对场景中的物体按深度排序 深度重叠测试. Zmin(P)Zmin(Q),若Zmax(P)0，则弧长代数和增加，若f0，则弧长代数和减少iiiiyxxyf11清华大学清华大学 计算机图形学计算机图形学2.7.3.32.7.3.3扫描线扫描线Z-bufferZ-buffer算法算法 算法思想: 点Buffer, 面Buffer 到线Buffer 利

8、用图形的连贯性 （指深度计算）清华大学清华大学 计算机图形学计算机图形学 在处理当前扫描线时，开一个一维数组作为当前扫描线的Z-buffer。首先找出与当前扫描线相关的多边形，以及每个多边形中相关的边对。 对每一个边对之间的小区间上的各象素，计算深度，并与Z-buffer中的值比较，找出各象素处可见平面。 计算颜色，写帧缓存。采用增量算法计算深度。清华大学清华大学 计算机图形学计算机图形学 数据结构 多边形Y表：将所有多边形存在多边形Y表中。 根据多边形顶点中最小的y坐标，插入多边形Y表中的相应位置。多边形Y表中只保存多边形的序号和其顶点的最大y坐标。根据序号可以从定义多边形的数据结构中取多边

9、形信息 待消隐对象 多边形y表0 1 2 3 4 5 6 71234567xy1234560IP2 Ymax2IP1 Ymax1P1P2e0e1e2e3e4e5清华大学清华大学 计算机图形学计算机图形学活化多边形表APT:与当前扫描线相交的多边形。APT是一个动态的链表边Y表ET:活化多边形表中的每一个多边形都有一个边表ET 多边形P1的边表ETIP2 Ymax2IP1 Ymax1IP2 Ymax2APTAPTy=2y=41234560Ymax, x,x,zYmax, x,x,zYmax, x,x,ze0e1e2清华大学清华大学 计算机图形学计算机图形学活化边对表AET 在一条扫描线上，同一多

10、边形的相邻两条边构成一个边对边对。活化边表AET中存放当前多边形中与当前扫描线相交的各边对的信息。 xl xl ylmax xr xr yr max zl IP za zb (示意图见下页)清华大学清华大学 计算机图形学计算机图形学AET(y=6)0 1 2 3 45 6 71234567xye0e1e2e3e4AET(y=2)e0e4e3e2e0e1清华大学清华大学 计算机图形学计算机图形学扫描线Z-buffer算法()建多边形y表；对每一个多边形根据顶点最小的y值，将多边形置入多边形y表。活化多边形表APT，活化边表AET初始化为空。For(每条扫描线i，i从小到大)1. 帧缓存CB置为背

11、景色。2. 深度缓存ZB (一维数组) 置为无穷大。3. 将对应扫描线i的，多边形y表中的多边形加入到活化多边形表APT中。4. 对新加入的多边形，生成其相应的边Y表。5. 对APT中每一个多边形，若其边Y表中对应扫描线I增加了新的边， 清华大学清华大学 计算机图形学计算机图形学将新的边配对，加到活化边对表AET中。6. 对AET中的每一对边：6.1 对xl x xr 的每一个象素，按增量公式z = z - za计算各点深度depth。6.2 与ZB中的量比较，depth ZB(I), 则令ZB(I) =depth，并计算颜色值， 写帧缓存。 7. 删除APT中，多边形顶点最大y坐标为I的多边

12、形，并删除相应的边。8. 对AET中的每一个边对，作如下处理：8.1 删除ylmax或yrmax 已等于i的边。若一边对中只删除了其中一边， 需对该多边形的边重新配对。 8.2 用增量公式计算新的xl 、 xr 和zl - END清华大学清华大学 计算机图形学计算机图形学2.7.3.4区间扫描线算法a1a2a3a4a6a5a7a8F1F2清华大学清华大学 计算机图形学计算机图形学 基本思想： 它是把当前扫描线与各多边形在投影平面的投影的交点进行排序后，使扫描线分为若干子区间。只要在区间任一点处找出在该处z值最大的一个面，这个区间上的每一个象素就用这个面的颜色来显示。清华大学清华大学 计算机图形

13、学计算机图形学 算法的优点：将逐点(象素、Pixel)计算 改为逐段计算 效率大大提高！清华大学清华大学 计算机图形学计算机图形学 如何确定小区间的颜色可分为三种情况：(1)小区间上没有任何多边形，如a4,a5，这时该小区 间用背景色显示。(2)小区间上只有一个多边形，如a1,a2a5,a6这时可 以对应多边形在该处的颜色显示。(3)小区间上存在两个或两个以上的多边,形如a6,a7， 必须通过深度测试判断哪个多边形可见。清华大学清华大学 计算机图形学计算机图形学 两个平面在屏幕上的投影 无贯穿的情形 相互贯穿的情形 若允许物体表面相互贯穿时，还必须求出它们在扫描平面（ZX平面）的交点。用这些交

14、点把该小区间分成更小的子区间（称为间隔），在这些间隔上决定哪个多边形可见。如将a2,a3区间分成a2,bb,a3两个子区间。a1a2a3a4a1a2a3a4a1a2xa4byxxzz清华大学清华大学 计算机图形学计算机图形学 确定某间隔内哪一多边形可见: 可在间隔内任取一采样点（如间隔中点），分析该点处哪个多边形离视点最近，该多边形即是在该间隔内可见的多边形。清华大学清华大学 计算机图形学计算机图形学 具体实现： 采用类似的数据结构 多边形Y表：将所有多边形存在多边形Y表中。 根据多边形顶点中最小的y 坐标，插入多边形Y表中的相应位置。多边形Y表中只保存多边形的序号和其顶点的最大y坐标。根据序

15、号可以从定义多边形的数据结构中取多边形信息。0 1 2 3 45 6 71234567xy1234560IP2 Ymax2IP1 Ymax1P1P2e0e1e2e3e4e5清华大学清华大学 计算机图形学计算机图形学 活化多边形表APT:与当前扫描线相交的多边形。APT是一个动态的链表。 边Y表ET:活化多边形表中的每一个多边形都有一个边表ET。 活化边对表AET1234560Ymax, x,x,zYmax, x,x,zYmax, x,x,ze0e1e2清华大学清华大学 计算机图形学计算机图形学 区别：活化边表中的结点是边，而非边对。a1a2a3a4a6a5a7a8F1F2清华大学清华大学 计算

16、机图形学计算机图形学 关键：如何知道每一个区间中，有几个相关的多边形？是哪几个？清华大学清华大学 计算机图形学计算机图形学 解决方案：活化多边形表中增加一个标志，flag=0, 每遇到它的边，flag取反。a1a2a3a4a6a5a7a8F1F2清华大学清华大学 计算机图形学计算机图形学2.7.3.5区域子分割算法 (Warnack算法) 基本思想: 把物体投影到全屏幕窗口上，然后递归分割窗口，直到窗口内目标足够简单，可以显示为止。区域子分的过程清华大学清华大学 计算机图形学计算机图形学 算法步骤该算法把初始窗口取作屏幕坐标系的矩形，将场景中的多边形投影到窗口内。 如果窗口内没有物体则按背景色

17、显示； 若窗口内只有一个面，则把该面显示出来。 否则，窗口内含有两个以上的面，则把窗口等分成四个子窗口。对每个小窗口再做上述同样的处理。这样反复地进行下去。清华大学清华大学 计算机图形学计算机图形学如果到某个时刻，窗口仅有象素那么大，而窗口内仍有两个以上的面，这时不必再分割，只要取窗口内最近的可见面的颜色或所有可见面的平均颜色作为该象素的值。清华大学清华大学 计算机图形学计算机图形学 窗口与多边形的覆盖关系有四种：内含、相交包围和分离。如图所示。内含 多边形与窗口相交 包围 窗口和多边形分离清华大学清华大学 计算机图形学计算机图形学 下列情况之一发生时，窗口足够简单，可以直接显示： 所有多边形均与窗口分离。该窗口置背景色清华大学清华大学 计算机图形学计