当前位置：文档之家 › 计算机图形学 隐面算法

计算机图形学 隐面算法

  • 格式：pptx
  • 大小：676.15 KB
  • 文档页数：33

下载文档原格式

  / 33

合集下载

计算机图形学 机械工业出版社第七章 消隐

计算机图形学 机械工业出版社第七章 消隐
第七章 消除隐藏线和隐藏面的算法
人不能一眼看到一个三维物体的全部表面。从 一个视点去观察一个三维物体，必然只能看到 该物体表面上的部分点、线、面，而其余部分 则被 这些可见部分遮挡住。如果观察的是若干 个三维物体，则物体之间还可能彼此遮挡而部 分不可见。因此，如果想有真实感地显示三维 物体，必须在视点确定之后，将对象表面上不 可见的点、线、面消去。执行这一功能的算法， 称为消隐算法 消隐算法。 消隐算法
y ji = f ( x j , zi ), i = n, n − 1, L ,1, j = 1,2, L y ji = yu ( j )或y ji < yl ( j ) 若
则(xi,yji,zi)为可见，并按如下原则修改yu(j)或yl(j) 的值： 若y > y ( j )，则y ( j ) = y
–1、线消隐 采用线框模型表示物体时，消隐对象是物体上的 边，消除的是物体上不可见的边。 –2、面消隐 采用表面模型表示物体时，消隐对象是物体上的 面，消除的是物体上不可见的面。
1、消除隐藏线
对造型的要求
– 在线框显示模型中,要求造型系统中有面的信息，
最好有体的信息，否则可能产生二义性。
最基本的运算
C k
1、凸多面体的面可见性
具体计算时，n和k记作n(nx,ny,nz),k(kx,ky,kz) 则有： n k +n k +n k nk
cos α = | n || k | =
x x y y z z 2 2 2 nx + n y + nz2 ⋅ k x2 + k y + k z2
分母为正，若分子为正，则 0 ≤ α < π / 2 ，面 可见；若为负，则 π / 2 < α ≤ π ，面不可见； 若为0，则 α = π / 2 ，此面退化为线。

计算机图形学——隐藏线和隐藏面的消除（消隐算法）

计算机图形学——隐藏线和隐藏面的消除（消隐算法）

计算机图形学——隐藏线和隐藏⾯的消除（消隐算法）⼀、概述由于投影变换失去了深度信息，往往导致图形的⼆义性。

要消除⼆义性，就必须在绘制时消除被遮挡的不可见的线或⾯，习惯上称作消除隐藏线和隐藏⾯（或可见线判定、可见⾯判定），或简称为消隐。

经过消隐得到的投影图称为物体的真实感图形。

下⾯这个图就很好体现了这种⼆义性。

消隐后的效果图：消隐算法的分类所有隐藏⾯消隐算法必须确定:在沿透视投影的投影中⼼或沿平⾏投影的投影⽅向看过去哪些边或⾯是可见的两种基本算法1、以构成图像的每⼀个像素为处理单元，对场景中的所有表⾯，确定相对于观察点是可见的表⾯，⽤该表⾯的颜⾊填充该像素.适于⾯消隐。

算法步骤：a.在和投影点到像素连线相交的表⾯中，找到离观察点最近的表⾯；b.⽤该表⾯上交点处的颜⾊填充该像素；2、以三维场景中的物体对象为处理单元，在所有对象之间进⾏⽐较，除去完全不可见的物体和物体上不可见的部分.适于⾯消隐也适于线消隐。

算法步骤：a.判定场景中的所有可见表⾯；b.⽤可见表⾯的颜⾊填充相应的像素以构成图形；提醒注意1.假定构成物体的⾯不能相互贯穿，也不能有循环遮挡的情况。

2.假定投影平⾯是oxy平⾯，投影⽅向为z轴的负⽅向。

如果构成物体的⾯不满⾜该假定，可以把它们剖分成互不贯穿和不循环遮挡的情况。

例如，⽤图b中的虚线便可把原来循环遮挡的三个平⾯，分割成不存在循环遮挡的四个⾯。

⼆、可见⾯判断的有效技术1、边界盒指能够包含该物体的⼀个⼏何形状(如矩形/圆/长⽅体等)，该形状有较简单的边界。

边界盒技术⽤于判断两条直线是否相交。

进⼀步简化判断2、后向⾯消除(Back-face Removal)思路：把显然不可见的⾯去掉，减少消隐过程中的直线求交数⽬如何判断：根据定义寻找外（或内）法向，若外法向背离观察者，或内法向指向观察者，则该⾯为后向⾯。

注意：如果多边形是凸的，则可只取⼀个三⾓形计算有向⾯积sp。

如果多边形不是凸的，只取⼀个三⾓形计算有向⾯积sp可能会出现错误，即F所在的⾯为前向⾯也可能出现sp≥0的情况,因此，需按上式计算多边形F的有向⾯积。

计算机图形学 隐面算法

计算机图形学 隐面算法

计算各像素点（x，y）所对应 的深度值z（x，y），并将结 果与深度缓冲器中该像素单元 所存储的深度值ZB（x，y）进 行比较。
消除隐藏面
Z缓冲区算法
（x，y）写入帧缓冲器，即IB （x，y）= I（x，y）；否则不 变。
深度值的计算 若已知多边形的方程，则可用增量法计算扫描线每一个 像素的深度。设平面方程为：
R
R Z （a ） Z （b ）
消除隐藏面
画家算法
深度优先级表的建立
二、投影重叠判断： 测试按照难度递增顺序排列：
包围盒定义：一个形体的包围盒指的是包围它的简单形体。
一个好的包围盒要具有两个条件： 包围和充分紧密包围着形体； 对其的测试比较简单。
1. P和Q在oxy平面上投影的包围盒在x方向上不相交，图a； 2. P和Q在oxy平面上投影的包围盒在y方向上不相交,图b； 3. P在Q之后。P的各顶点均在Q的远离视点的一侧,图d； 4.Q在P之前。Q的各顶点均在P的靠近视点的一侧,图e； 5. P和Q在观察平面oxy上的投影不相交,图c； 上面5项只要有一项成立，P就不遮挡Q，不需要重新排序
深度优先级表的建立
无 法 直 接 建 立 正 确 的 深 度 优 先 表
解决方法是沿多边形所在平面间的交线循环分割这些多边形。
消除隐藏面
画家算法
画家算法的不足：
• 排序计算量大； • 多边形相交或循环重叠时，必须分割多边形。
消除隐藏面
画家算法
Z缓冲区算法
基本思想： 投影平面每个像素所对应的所有面片（平面或曲面）的深度 进行比较，然后取离视线最近面片的属性值作为该像素的属 性值。
STEP4：多边形的编码 V01+V12+V20=2+（-4）+2=0。

计算机图形学 消隐

计算机图形学 消隐
第十一讲 面消隐
？基本概念 ？提高消隐算法效率的常见方法 ？画家算法 ？Z缓冲器算法 ？扫描线Z缓冲器算法 ？区域子分算法 ？光线投射算法
-
基本概念
产生真实感的方法之一： 反映三维场景中的相互遮挡关系
面消隐与线消隐
表面模型与线框模型 物体表面：平面与曲面 面消隐对象： 由平面多边形构成的多面体
-
基本概念
2）然后按照从表头到表尾的顺序逐个绘制物 体。
-
画家算法
关键：如何对场景中的物体按深度（远 近）排序，建立深度优先级表？ 一种针对多边形的排序算法如下：
假定在规范化投影坐标系uvn中,投影方向是n 轴的负向，因而n坐标大距观察者近。记nmin(P) nmax(P)分别为多边形P的各个顶点n坐标的最小 值和最大值，算法步骤如下：
-
提高消隐算法效率的常见方法 1
利用连贯性
物体连贯性 面的连贯性 区域连贯性 扫描线的连贯性 深度连贯性
-
提高消隐算法效率的常见方法 2
将透视投影转换成平行投影 消隐与透视关系密切,体现有：
1）消隐必须在投影之前完成； 2）物体之间的遮挡关系与投影中心（视点）的选 取有关； 3）物体之间的遮挡关系与投影方式有关
-
提高消隐算法效率的常见方法 3
图12.3 加入面消隐步骤的三维图形显示 流程图 p285 (参见图8.30 p162）
图12.4 先将透视投影转换成平行投影，南 后再消隐 p285 (参见图8.33 p167）。 （避免除法，提高了效率）
-
提高消隐算法效率的常见方法 4
包围盒技术
定义：一个形体的包围盒指的是包围它的简单形体。
-
提高消隐算法效率的常见方法 6
复杂度比较：

计算机图形学-第7章-消除隐藏线和隐藏面

计算机图形学-第7章-消除隐藏线和隐藏面
第七章 隐藏面的消除
这一章我们将介绍消除隐藏面的方 法。
7.1 概述
第一章我们曾将输出的图形分为线条图和具 有明暗效果的真实感图形（面图），在绘制 或显示三维图形时，无论采用那种图形表示 三维形体，都要消除不可见的线或面，即消 除隐藏线或隐藏面（简称消隐），它是计算 机图形学的重要内容，其算法有很多种，本 章只介绍隐藏面的消除。
对于某一个面片，a/c是常数，故沿扫描线 的后续点的深度值，可由上式仅执行一次 加法计算即可求出。
对于每条扫描线，首先计算出与其相交的多 边形最左边的交点所对应的深度值，然后， 该线上所有后续点由式（7.14）计算。
计算每个面片左边界的深度值
如图所示，由最上方顶点出发，沿多边形 的左边递推地计算各点的z坐标
7.2.1 平面多边形的外法矢量
为了判别物体上各表面是朝前面还是朝后
面，需求出各表面(平面多边形)指向体外
的法矢量。设物体在右手坐标系中，多边
形顶点按逆时针排列。当多边形为凸多边
形时，则其法矢可取成多边形相邻两边矢
量的叉积。
P3
n
n p1 p2 p2 p3 P1
P2
这种算法虽然简单，但当多边形为凹多边形 时，则可能出现错误，即所求的多边形法矢 量指向体内。这时可采用如下的计算方法。
设n={A,B,C}，而
n
A ( yi y j )(zi z j ) i 1 n
B (zi z j )(xi x j ) i 1 n
C (xi x j )( yi y j ) i 1
式中若 i n，则j=i+1；否则i=n，j=1。 以上算法适合任何平面多边形。
非平面但接近平面的多边形的最佳逼近平面 的法矢量也可用此算法求出。为避免在程序 中出现两种计算平面外矢量的方法，建议凸 多边形也采用该算法计算外法矢量。多边形 所在平面的方程可写成

06-消隐

06-消隐

点与多边形的包含性检测： （1）射线法
P P1 P2 P3 P P1 P2
由被测点P处向 y = - 方向作射线 交点个数是奇数，则被测点在多边形内部。否则，偶数 表示在多边形外部。
若射线正好经过多边形的顶点 ，则采用“左开右闭”的原则来 实现。即：当射线与某条边的顶 点相交时，若边在射线的左侧， 交点有效，计数；若边在射线的 右侧，交点无效，不计数。 用射线法来判断一个点是否 在多边形内一是计算量大，二 是不稳定。原因是射线在经过 多边形顶点时，由于计算机本 身的误差（也许多了0.00001）， 把本该无效的交点变成有效的 交点了。所以这种算法是不稳 定的。
上图所画的仅仅是一个简单的立方体，如果一个物体是由多 个形体所组成的，或者整个三维场景是由多个物体构成的，情 况就更为复杂了。 因此，要绘制出意义明确的、富有真实感的立体图形，首 先必须消去形体中的不可见部分，而只在图形中表现可见部 分。这就要去寻求解决显示三维物体的图形中消去不可见部 分的方法，也就是所谓的“消隐”问题。消隐包括消除“隐 藏线”和“隐藏面”两个问题。
消 隐
三维物体的显示和真实感图形是当今计算机图形学研究的 一个焦点。在二维显示设备上显示三维图像, 必须对三维图像 进行消隐处理, 通过消隐处理的物体才能很好的表现三维立体 效果, 但是这种物体明显缺乏真实感, 还需要对物体进行真实 感的处理, 这样才能逼真的显示物体。
主要讲述的内容：
消隐的分类，如何消除隐藏线、隐藏面，主要介绍以 下几个算法：
Z-Buffer算法（） { 帧缓存全臵为背景色
深度缓存全臵为最小Z值（比如赋一个10-8次方）
for(每一个多边形)
{扫描转换该多边形
for(该多边形所覆盖的每个象素(x,y) )

计算机图形学课件：第9章消隐

2.由优先级低的多边形开始逐个对多边形进 行扫描转换。
其中的关键是将多边形按深度进行排序。
排序步骤： 1.将所有多边形按Zmin由小到大的顺序存入队列M中， 并初始化一空队列N。 2.取M中第一个多边形(A)与其他多边形进行深度重叠 比较，若无重叠关系，A入N；否则作重叠处理。 3.将已处理的多边形从M中删除，转2.，直到M为空。
图象空间消隐算法：有深度缓冲器算法、A缓冲 器算法、区间扫描线算法等。 景物空间消隐算法：BSP算法、多边形区域排序 算法。 介于二者之间：深度排序算法、区域细分算法、 光线投射算法等。
9.1 深度缓存器算法
算法的原理：
使用两块缓冲区： Z缓存：存深度 帧缓存：存颜色。
y
(x,y) 0
R P2 P1
算法特点： ①算法简单。 ②需较大的存储空间。 ③处理反走样、透明和半透明效果困难。
对于③ ，可以使用A缓冲器算法克服。
9.2 区间扫描线算法
算法原理：
避免对被遮挡 区域的采样是 进一步提高扫 描线算法计算 效率的关键。
y B2 A2
0
A1 B1
AB
A3
B3
C2
扫描线1 C1
扫描线2 扫描线3
B4 C C4 C3 x
图9-3 区间扫描线算法原理
算法： 三张表：边表、多边形表、有效边表。 算法关键：分割子区间，确定子区间上的唯一可见面。 特殊情形：贯穿情形、循环遮挡情形。
12 3
45
12 3 4 5
z
xz
x
(a)
(b)
1
2
3 45
z
x
(c)
图9-4 扫描线子区间
贯穿情形：
为了使算法能处理互相贯穿的多边形，扫描线上 的分割点不仅应包含各多边形的边与扫描线的交点， 而且应包含这些贯穿边界与扫描线的交点。

计算机图形学课程设计-Z-Buffer隐面算法的实现

枣庄学院信息科学与工程学院课程设计任务书题目：Z-Buffer隐面算法的实现姓名：秦云学号：201012110128专业班级：计算机科学与技术、2010级本1班课程：计算机图形学指导教师：燕孝飞职称：讲师完成时间：2012年12 月----2013年1 月枣庄学院信息科学与工程学院制2012年12 月30日课程设计任务书及成绩评定目录第1章引言 (1)第2章计算机图形学的发展历史 (2)2.1 智能CAD (2)2.2计算机美术与设计 (2)2.2.1 计算机美术的发展 (2)2.3计算机动画艺术 (3)2.3.1历史的回顾 (3)2.4科学计算可视化 (4)2.5虚拟现实 (4)第3章计算机图形学的研究方向 (6)第4章 Z-Buffer隐面算法的相关原理 (7)4.1 Z-Buffer隐面算法简介 (7)4.2 Z-Buffer隐面算法程序 (7)第5章系统设计的相关代码 (8)5.1坐标设置函数的相应代码 (8)5.2旋转角度函数相应代码 (8)5.3多边形填充 (9)第6章系统的运行效果 (12)6.1运行主界面 (12)6.2不同方向键的运行效果 (13)第7章总结 (16)第1章引言计算机图形学一个主要的目的就是要利用计算机产生令人赏心悦目的真实感图形。

为此，必须建立图形所描述的场景的几何表示，再用某种光照模型，计算在假想的光源、纹理、材质属性下的光照明效果。

所以计算机图形学与另一门学科计算机辅助设计有着密切的关系。

事实上，图形学也把可以表示几何场景的曲线曲面造型技术和实体造型技术作为其主要的研究内容。

同时，真实感图形计算的结果是以数字图像的方式提供的，计算机图形学也就和图像处理有着密切的关系。

真实感图形绘制过程中，由于投影变换失去了深度信息，往往导致图形的二义性。

要消除这类二义性，就必须在绘制时消除被遮挡的不可见的线或面，习惯上称之为消除隐藏线和隐藏面，或简称为消隐，经过消隐得到的投影图称为物体的真实图形。

隐藏面消隐


9.2 消隐算法分类
无论多么复杂的空间物体，沿 视线方向上都只能看到一部分表 面，其余的表面背向观察者不可 见。计算机图形学的一个重要任 务就是对空间物体的表面进行可 见性检测，绘制出可见边线和表 面。经过消隐后得到的图形称为 消隐图。
根据消隐方法的不同，消隐算法可分为两类： 1.隐线算法。用于消除物体上不可见的边界线。隐 线算法主要是针对线框模型提出的，它只要求画出 物体的各可见棱边。
9.1.1 图形的几何信息和拓扑信息 9.1.2 基本图形的数据结构 9.1.3 立体表示模型
9.1.1 图形的几何信息和拓扑信息
几何信息：描述几何元素空间位置的信息。
拓扑信息：描述几何元素之间相互连接关系的信息。
描述一个物体不仅要有几何信息的描述而且还要有 拓扑信息的描述。因为只有几何信息的描述，在表示 上存在不惟一性。如图9-1所示的五个顶点，其几何 信息已经确定，如果拓扑信息不同，则可产生图9-2 和9-3所示的两种不同图形。
表9-1 立方体顶点表
z坐标
z1＝0 z2＝0 z3＝a z4＝a z5＝0 z6＝0 z7＝a z8＝a
边
起点
终点
E1
P1
P2
E2
P2
P3
E3
P3
P4
E4
P4
P1
E5
P5
P6
E6
P6
P7
E7
P7
P8
E8
P8
P5
E9
P1
P5
E10
P2
P6
E11
P3
P7
E12
P4
P8
表9-2 立方体边表
面 边1 边2 边3 边4 F1 E1 E4 E3 E2 F2 E5 E6 E7 E8 F3 E9 E8 E12 E4 F4 E10 E2 E11 E6 F5 E1 E10 E5 E9 F6 E3 E12 E7 E11

计算机图形学-第7章-消除隐藏线和隐藏面


可能的四种形体
隐藏线和隐藏面
不可见的线和面分别称为隐藏线和隐藏面。 隐藏线和面不仅仅有形体自身的，而且还 有形体之间互相遮挡的。消除它们即称为 消除隐藏线和消除隐藏面。
形体之间互相遮挡的隐藏线
当我们显示线条图或用笔式绘图仪或其 它线画设备绘制线条图形时，要解决的 主要是消除隐藏线的问题。而当用光栅 扫描显示器显示物体的明暗图形时，就 必须要解决消除隐藏面的问题。
设n={A,B,C}，而
n
A ( y j )(zi z j ) i 1 n
B (zi z j )(xi x j ) i 1 n
C (xi x j )( yi y j ) i 1
式中若 i n，则j=i+1；否则i=n，j=1。 以上算法适合任何平面多边形。
非平面但接近平面的多边形的最佳逼近平面 的法矢量也可用此算法求出。为避免在程序 中出现两种计算平面外矢量的方法，建议凸 多边形也采用该算法计算外法矢量。多边形 所在平面的方程可写成
Ax By Cz D 0
其中 D ( Ax0 By0 Cz0 ，)
(x0 , y0 , z0 ) 为平面上任意一点。
7.2.2 深度检验
深度检验是比较位于同一条投射线的若干 个点的深度坐标（一般为z坐标），以确定 哪个点是可见的，将可见点表示出来。消 隐时必须进行深度检验。一般将需要比较 的各点的z坐标按递增或递减排序，也可从 中选出最大或最小的z坐标。至于选最大或 最小与所选的坐标系有关。
7.2.1 平面多边形的外法矢量
为了判别物体上各表面是朝前面还是朝后
面，需求出各表面(平面多边形)指向体外
的法矢量。设物体在右手坐标系中，多边
形顶点按逆时针排列。当多边形为凸多边
形时，则其法矢可取成多边形相邻两边矢
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

消除隐藏面
画家算法
深度优先级表的建立 一、多边形优先级的考虑 • 首先对一个简单的画面，可以直接建立一个确定的深度优 先表如图（a）所示。深度方向上无重叠。 • 当画面略微复杂一点，无法按简单的Z向排序建立确定的深 度优先表，以确定每一个多边形的优先级，如图（b）所 示 。深度方向上有重叠
X P Q P Q X
Z缓冲器算法基本思想
消除隐藏面
Z缓冲区算法
实现方法
帧缓存区 存放每个像素的颜色值。
深度缓ቤተ መጻሕፍቲ ባይዱ区
屏幕
存放每个像素的深度值。
帧缓冲器
Z缓冲器
每个单元存放对应像素 的颜色值
每个单元存放对应像素 当前最近面的深度值
消除隐藏面
Z缓冲区算法
算法描述：
for ( v= 0;v<vmax;v++) for (u= 0; u<umax; u++) { 将帧缓冲器的第(u,v)单元置为背景色； 将Z缓冲器的第(u,v)单元置为最小深度值； }
基本步骤： 首先将场景中的多边形投影到绘图窗口 内，判断窗口是否足够简单，若是，则 算法结束；否则将窗口进一步分为四块。 对此四个小窗口重复上述过程，直到窗 口仅为一个像素大小。此时可能有多个 多边形覆盖了该像素，计算它们的深度 值，以最近的颜色显示该像素即可。
消除隐藏面
区域采样算法
如何判断窗口是否足够简单
n 窗口与多边形分离 当 i 0 i 0 n 多边形包围窗口 当 i 8 i 0
消除隐藏面
区域采样算法
例：
STEP1：区域编码 STEP2：多边形顶点编码 v0=1,v1=3,v2=7, STEP3：多边形边的编码 V01=3-1=2, V12=7-3=4, V20=1-7=-6(＜-4),故V20=-6+8=2。 取v1v2与窗口上边所在直线的交点v’将其分 为两段，两段的编码分别为-2，6（＞4，故 为6-8=-2）， 从而V12=-2+（-2）=-4。
最左边的交点所对应的深度值，然后，利用图形连贯性将 该扫描线上所有的后续点计算出来。
所有的多边形处理完毕，即得消隐后的图形。
消除隐藏面
Z缓冲区算法
Z缓冲区算法的优缺点：
优点
1. 简单稳定，利于硬件实现 2.Z缓冲器算法的最大优点 ：Z缓存器算法在像素级上以近物取代远物。 形体在屏幕上的出现顺序是无关紧要的。可以轻而易举地处理隐藏面以 及显示复杂曲面之间的交线。
m为该边的斜率，沿该边的深度也可以递归计算出来，即：
z i 1 [ A( xi 1 A ) B( yi 1) D] B m zi m C C
如果该边是一条垂直边界，则计算公式简化为：
zi 1 zi
B C
消除隐藏面
Z缓冲区算法
深度值的计算
对于每条扫描线，首先根据公式计算出与其相交的多边形
纹理
纹理映射
进行纹理映射的过程主要是建立几何和纹理图片之间的几何对应关系，这种几何对应关系确 立以后，纹理的某一块对应着场景中某个多边形的某个位置，如果处理不好这种关系，那么 纹理可能会出现在我们与预料之外的地方，甚至颠倒扭曲，或者纹理映射失败。
帧缓冲器各单元均置为背景 色，深度缓冲器所有单元均 置为最小z值，然后逐个处理 多边形表中的各面片。
for (每个多边形） for (多边形在投影平面上的投影区域内的每个像素(u,v) ) { 计算多边形在当前像素(u,v)处的深度值d； if (d > Z缓冲器的第(u,v)单元的值) { 置帧缓冲器的第(u,v)单元值为当前多边形颜色； 置Z缓冲器的第(u,v)单元值为d; } 若z＞ZB（x，y）,则ZB（x，y） } = z，同时将该像素的颜色值I
Ax By Cz D 0
则多边形面上的点（x，y）所对应的深度值为：
( Ax By D) z C≠0 C
消除隐藏面
Z缓冲区算法
深度值的计算
由于所有扫描线上相邻点间的水平间距为1个像素单位，扫描线行 与行之间的垂直间距也为1。因此可以利用这种连贯性来简化计算 过程，如图所示。
画家算法 Z缓冲区算法 扫描线算法 区域采样算法
点取样算法
消除隐藏面
画家算法
基本思想： 画家的作画时，先涂背景色，然后由远及近的将景物画上，顺序 暗示出所画物体之间的相互遮挡关系。所以称为画家算法。 基本原理： 1）先把屏幕置成背景色； 2）将场景中的物体的各个面按其距观察点的远近进行排序，结果放 在一张线性表中；（线性表构造：距观察点远的优先级低，放在表 头；距观察点近的优先级高，放在表尾 ）该表称为深度优先级表。 3）然后按照从远到近（从表头到表尾）的顺序逐个绘制物体表面。 因此，画家算法又被称为深度排序算法或表优先级算法。
消除隐藏面
区域采样算法
如何判断包围和分离的关系？
区域检查法:
区域编码 多边形顶点编码 多边形边的编码 多边形的编码
多边形边的编码 多边形的边vivi+1的编码定义为Vi(i+1)=vi+1-vi，令Vn(n+1)=Vn0 i=0,1„n； 当Vi(i+1) >4时，取Vi(i+1) = Vi(i+1) -8； 当Vi(i+1) <-4时，取Vi(i+1) = Vi(i+1) +8； 当Vi =±4时，取该边与窗口边的延长线的交点将该边分为两段，对 两段分别按上面的规则编码，再令Vi(i+1)等于两者之和。 多边形的编码 定义多边形的编码为其边的编码之和 ，则
若已计算出（x，y）点的深度值为zi，沿x方向相邻连贯点（x+1，y） 的深度值zi+1可由下式计算：
zi 1
[A(x i 1) By D ] A zi C C
Z缓冲区算法
消除隐藏面
深度值的计算
沿多边形左边界递归计算边界上各点的坐标：
x i 1 x i
1
m
消除隐藏面
区域采样算法
如何判断包围和分离的关系？
转角累计检查法:按顺时针方向或逆时针方向绕多边形依次 累加多边形各边起点与终点对窗口内任意一点所张的夹角。 按累计角度之和可以判定： ◦ 若角度之和等于0，则表示多边形与窗口分离；
◦ 若角度之和等于±360º *n，则表示多边形包围窗口(n 次)。
多边形 窗口
缺点
1.需要一个额外的Z 缓冲器，需更大的存储空间，例如，当像素数目为 500*500时，就需要250K个深度值的存储空间。深度值一般用浮点数表示， 每个数占4个字节，故共需要1M字节的额外存储空间。 2.在每个多边形占据的每个像素处都要计算深度值，计算量大。
消除隐藏面
Z缓冲区算法
扫描线算法
基本思想： 按扫描行的顺序处理一帧画面，在由视点和扫描线所决定 的扫描平面上解决消隐问题。 基本步骤： 把物体各面投影到屏幕上 计算扫描线与物体各投影面的相交区间。当两个区间在 深度方向上重叠时，采用深度测试确定可见部分。 典型实现： 扫描线Z缓冲区算法 扫描线间隔连贯性算法
STEP4：多边形的编码 V01+V12+V20=2+（-4）+2=0。
因此，多边形与窗口分离。
消除隐藏面
区域采样算法
例：
STEP1：区域编码 STEP2：多边形顶点编码 V0=5,V1=7,V2=3, STEP3：多边形边的编码 V01=7-5=2, V12=3-7=-4, V20=5-3=2. 取v1v2与窗口上边所在直线的交点v’将其分为两段， 两段的编码分别为-6(＜-4，故为-6+8=2)，2 从而V12=2+2=4。
计算各像素点（x，y）所对应 的深度值z（x，y），并将结 果与深度缓冲器中该像素单元 所存储的深度值ZB（x，y）进 行比较。
消除隐藏面
Z缓冲区算法
（x，y）写入帧缓冲器，即IB （x，y）= I（x，y）；否则不 变。
深度值的计算 若已知多边形的方程，则可用增量法计算扫描线每一个 像素的深度。设平面方程为：
消除隐藏面
姓名：XX 专业：XXXX 导师：XX 教授 学号：XXXXXXXXX
隐面算法 用于消除物体上不可见的表面 主要针对表面模型，不仅要求画出物体的各个可 见棱边，而且还要求填充各个表面
在绘制物体真实图形时， 总是在投影面取一组离 散点，在各离散点解决 消隐问题，以确定颜色、 亮度，用于显示屏幕上 的像素。
7,4,10 3 z=10 4 7,2,10
扫描线算法
3,5,0 1
8,4,20 2
Z=(4x-12)
消除隐藏面
3 8,0,20
区域采样算法
区域采样算法是利用图形的区域连贯性，在连续的区域上确定可见面
及其颜色、亮度。
基本思想：
把物体投影到全屏幕窗口上，然后递归地分割窗口，直到窗口内目标 足够简单，可以直接显示为止。
消除隐藏面
区域采样算法
纹理
物体表面的细节分为两类
一类是由物体表面颜色色彩、明暗变化体现出来的细节(取决于物 体表面的材质属性)； 一类是由物体表面不规则的细小凹凸造成的细节(取决于物体本身 的几何形状)。
纹理映射分类
颜色纹理映射，用来在光滑表面上产生花纹图案的效果 几何纹理映射，用来使物体表面产生凹凸不平的效果
R
R Z （a ） Z （b ）
消除隐藏面
画家算法
深度优先级表的建立
二、投影重叠判断： 测试按照难度递增顺序排列：
包围盒定义：一个形体的包围盒指的是包围它的简单形体。
一个好的包围盒要具有两个条件： 包围和充分紧密包围着形体； 对其的测试比较简单。
1. P和Q在oxy平面上投影的包围盒在x方向上不相交，图a； 2. P和Q在oxy平面上投影的包围盒在y方向上不相交,图b； 3. P在Q之后。P的各顶点均在Q的远离视点的一侧,图d； 4.Q在P之前。Q的各顶点均在P的靠近视点的一侧,图e； 5. P和Q在观察平面oxy上的投影不相交,图c； 上面5项只要有一项成立，P就不遮挡Q，不需要重新排序