【XJTUSE计算机图形学】第二章 光栅图形学(2)—消隐

【XJTUSE计算机图形学】第二章 光栅图形学(2)—消隐

基本概念

投影变换失去了深度信息,往往导致图形的二义性

消隐为了消除二义性,必须在绘制时消除被遮挡的不可见的线或面,习惯上称作消除隐藏线和隐藏面;

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

image-20220107095649285

消隐的对象是三维物体。三维体的表示主要有边界表示和构造实体几何表示等。

最简单的方法:用表面上的平面多边形表示。

消隐结果与观察物体有关,也与视点有关。

image-20220107095756500

几个假设

1️⃣ 投影平面是oxy平面;

2️⃣ 投影方向为负z轴方向的平行投影;

值越大,离视点越近;

透视变换转化为平行投影。

3️⃣ 不能处理相互贯穿或循环遮挡的物体,此时应做特殊处理。

image-20220107095914682

在实时模拟过程中,要求消隐算法速度快,通常生成的图形质量一般;

在真实感图形生成过程中,要生成高质量的图形,通常消隐算法速度较慢。

消隐算法的权衡:消隐效率图形质量

与消隐与密切相关的因素

物体排序:判断场景中的物体全部或者部分与视点之间的远近;

连贯性:场景中物体或其投影所表现出来的相似程度。

提高消隐算法效率的常见方法

利用连贯性、包围盒技术、背面剔除、空间分割技术、物体分层表示

利用连贯性

利用连贯性:相邻事物的属性之间有一定的连贯性,其属性值通常是平缓过渡的,如颜色值、空间位置关系等

物体连贯性

面的连贯性

区域连贯性

扫描线的连贯性

深度连贯性

包围盒技术

一个形体的包围盒指的是包围它的简单形体

假设包围和充分紧密包围着形体;

对其的测试比较简单。

常用包围盒:长方体圆柱

image-20220107100748712

背面剔除

外法向:规定每个多边形的外法向都是指向物体外部的。

前向面:若多边形的外法向与投影方向(观察方向)的夹角为钝角(V· N<0),称为前向面。

后向面:若多边形的外法向与投影方向(观察方向)的夹角为锐角(V· N>0),称为后向面(背面)。

后向面总是看不见的,不会由于后向面的遮挡,而使别的棱成为不可见的。因此计算时,可以把这些后向面全部去掉,这并不影响消隐结果。

空间分割技术

将投影平面上的窗口分成若干小区域;为每个小区域建立相关物体表,表中物体的投影于该区域有相交部分;则在小区域中判断那个物体可见时,只要对该区域的相关物体表中的物体进行比较即可

物体分层表示

image-20220107101337599

减少场景中物体的个数,降低算法复杂度

消隐的分类

按消隐对象和输出结果分类

线消隐:消除的是物体上不可见的边。

面消隐:消除的是物体上不可见的面。

image-20220107101446906

根据消隐空间分类

1️⃣ 物体空间的消隐算法:以场景中的物体为处理单元;

for (场景中的每一个物体)
{
	将其与场景中的其它物体比较,确定其表面的可见部分;
	显示该物体表面的可见部分;
}

假设场景中有k个物体,平均每个物体表面由h个多边形构成,显示区域中有m*n个像素,则算法的复杂度为:O((kh)*(kh))

image-20220107101755615

2️⃣ 图像空间的消隐算法:以窗口内的每个像素为处理单元;

for(窗口内的每一个像素)
{
 确定距视点最近的物体,以该物体表面的颜色来显示像素
}

假设场景中有k个物体,平均每个物体表面由h个多边形构成,显示区域中有m*n个像素,则算法的复杂度为:O(mnkh)

image-20220107101853016

•实际应用中通常会考虑画面的连贯性,所以图像空间算法的效率有可能更高。

3️⃣ 物体空间和图像空间的消隐算法:在物体空间中预先计算面的可见性优先级,再在图像空间中生成消隐图;

代表性算法:画家算法

消除隐藏线

对造型的要求

在线框表示模型中,要求造型系统中有面的信息,最好有体的信息。

坐标变换

通过坐标变换,将视点变换到Z轴的正无穷大处,视线方向变为Z轴的负方向。

最基本的运算

线消隐中,判断面对线的遮挡关系:体分解成面,再判断面与线关系。判断过程中需反复地进行线线、线面之间的求交运算。

算法

1️⃣ 若线段的两端点及视点在给定平面的同侧,线段不被给定平面遮挡,转(7);

2️⃣ 若线段的投影与平面投影的包围盒无交,线段不被给定平面遮挡,转(7);

3️⃣ 求直线与相应无穷平面的交:

•无交点转(4);

•若交点在线段内部,交点将线段分成两段,与视点同侧一段不被遮挡,另一段在视点异侧转(4);

•若交点在线段外部,转(4)。

4️⃣ 求所剩线段的投影与平面边界投影的所有交点。若无交点,转(7)。

5️⃣ 以上所求得的各交点将线段的投影分成若干段,求出第一段中点。

6️⃣ 若第一段中点在平面的投影内,则相应的段被遮挡,否则不被遮挡;其他段的遮挡关系可依次交替取值进行判断。

7️⃣ 结束。

假设E为面F的一条边, 需判别F以外每一个面与E的遮挡关系。

假设消隐对象有n条边和m个面,当n和m很大时,两两求交的消隐方法工作量很大:

解决方法:背面剔除。

消除隐藏面(不太好出考题)

画家算法

列表优先算法:画家的作画顺序暗示出所画物体之间的相互遮挡关系。

基本思想

1️⃣ 先把屏幕置成背景色;

2️⃣ 再把物体的各个面按其离视点的远近进行排序,排序结果存在一张深度优先级表中;

3️⃣ 然后按照从远到近的顺序逐个绘制各个面。

关键是如何对场景中的物体按深度排序。

多边形排序算法

在规范投影坐标系里 XYZ 中,投影方向是 Z轴的负方向,因而 Z坐标大者距观察者更近。Zmin(P)和 Zmax(P) 分别为 P 各顶点 Z坐标的最小和最大值。[投影为正平行投影]

Step 1:将场景中所有多边形存入一个线性表,记为L;

Step 2:如果L中仅有一个多边形,算法结束;否则根据每个多边形的Zmin对它们预排序。不妨假定多边形P落在表首,即Zmin§为最小。再记Q为L–{P}(表中其余多边形)中任意一个;

Step 3:判别P, Q之间的关系,有如下二种:

对所有的Q,有Zmax§< Zmin(Q), 则多边形P的确距观察点最远,它不可能遮挡别的多边形。令L=L–{P}, 返回第二步;

存在某一个多边形Q,使Zmax§>Zmin(Q),需进一步判别:image-20220107103622817

优点:简单(如何对场景中的物体按深度排序)。

缺点:只能处理互不相交的面,且深度优先级表中面的顺序可能出错

Z缓冲区算法

组成

帧缓冲器–保存各像素颜色值;

Z 缓冲器 –保存各像素处物体深度值

image-20220107103923683Z缓冲器中的单元与帧缓冲器中的单元一一对应

算法思想

1️⃣ 将 Z 缓冲器中个单元的初始值置为最小值。

2️⃣ 多边形投影时,当要改变某个像素的颜色值时,首先检查当前多边形的深度值是否大于该像素原来的深度值:

大于,说明当前多边形更靠近观察点,用它的颜色替换像素原来的颜色;同时更新深度值;

否则说明在当前像素处,当前多边形被前面所绘制的多边形遮挡了,是不可见的, 像素的颜色值不改变。

Z-Buffer算法()
{ 	
	帧缓存全置为背景色
	深度缓存全置为最小Z值
	for(每一个多边形)
	{   
		扫描转换该多边形
	    for(该多边形所覆盖的每个象素(x,y) )
	   {	
	   		计算该多边形在该象素的深度值Z(x,y);
			if(Z(x,y)大于Z缓存在(x,y)的值)
			{Z(x,y)存入Z缓存中(x,y)处
				把多边形在(x,y)处的颜色值存入帧缓存的(x,y)}	
	  }                       
     }                                                
}

需要计算的像素深度值次数 =多边形个数*多边形平均占据的像素个数

所有图像空间算法中最简单的一种隐藏面消除算法

优点

简单稳定,利于硬件实现;

不需要整个场景的几何数据。

缺点:

空间:需要一个额外的Z缓冲器;

时间:在每个多边形占据的每个像素处都要计算深度值。

只用一个深度缓存变量zb的改进算法:需要开一个与图象大小相等的缓存数组ZB

{
	帧缓存全置为背景色
	for (屏幕上的每个象素(i, j)) {
		深度缓存变量zb置最小值MinValue
		for (多面体上的每个多边形Pk) {
			if (象素点(i, j)在Pk的投影多边形之内) {
				计算Pk在(i, j)处的深度值depth;
				if (depth大于zb) {
					zb = depth;
					indexp = k;
				}
			}
		}
		if (zb != MinValue)
			在交点 (i, j) 处用多边形Pindexp的颜色显示
		}
}

先像素后多边形

关键问题

1️⃣ 计算多边形 在点(i,j)处的深度。设多边形的平面方程为:

image-20220107105550460

2️⃣ 判断象素点(i,j)是否在 的投影多边形之内(点与多边形的包含性检测)

射线法

image-20220107105648534

由被测点P处向 y = – ¥方向作射线

交点个数是奇数,则被测点在多边形内部

否则,偶数,在多边形外部

若射线正好经过多边形的顶点,则采用“左开右闭”的原则来实现。

弧长法(单位圆)

–以被测点为圆心作单位圆,计算其在单位圆上弧长的代数和

代数和为0,点在多边形外部;

代数和为

2

π

2\\pi

2π,点在多边形内部;

代数和为

π

\\pi

π,点在多边形边上。

image-20220107140435401

弧长累加方法:以顶点符号为基础。

将坐标原点移到被测点P。各象限内点的符号对分别为(+,+),(-,+),(-,-),(+,-)。

算法规定:若顶点pi的某个坐标为0,则其符号为+。若顶点pi的x、y坐标都为0,则说明这个顶点为被测点,我们在这之前予以排除。于是弧长变化如下表。

注意:当边的终点Pi+1在起点Pi的相对象限时,弧长变化可能增加或减少p:

扫描线Z-buffer算法[了解就行]

Z 缓冲器算法中所需要的Z 缓冲器容量较大,可以将整个绘图区域分割成若干个小区域,然后一个区域一个区域地显示,以减少Z 缓冲器的单元数;

如果将小区域取成屏幕上的扫描线,就得到扫描线 Z 缓冲器算法。

算法思想

1️⃣ 面Buffer到线Buffer;

2️⃣ 利用图形的连贯性(指深度计算);

3️⃣ 在处理当前扫描线时,开个一维数组作为当前扫描线的Z-buffer。找出与当前扫描线相关的多边形,以及每个多边形中相关的边对;

4️⃣ 对每一个边对之间的小区间上的各象素,计算深度,并与Z-buffer中的值比较,找出各象素处可见平面;

5️⃣ 确定颜色,写帧缓存:采用增量算法计算深度。

改进

1️⃣ 将窗口分割成扫描线:Z缓冲器的单元数只要等于一条扫描线内像素的个数就可以了。

image-20220107141259785

2️⃣ 采用多边形Y(分类)表、活化多边形表避免多边形与扫描线的盲目求交;

3️⃣ 利用边、边的分类表、边对、活化边对表避免与扫描线的盲目求交。

4️⃣ 利用连贯性计算深度

水平方向:当沿扫描线x递增一个像素时,多边形所在平面在z坐标的增量,对方程ax+by+cz+d=0来说,

Δ

z

a

=

a

/

c

\\Delta z_a=-a/c

Δza=a/c

竖直方向

Δ

z

b

\\Delta z_b

Δzb :当沿扫描线y递增一个像素时,多边形所在平面 z坐标的增量,

Δ

z

b

=

b

/

c

\\Delta z_b=-b/c

Δzb=b/c

下一条扫描线与边对左侧边交点处的深度值:

z

1

=

z

1

+

Δ

x

1

Δ

z

a

+

Δ

z

b

z_1=z_1+\\Delta x_1 \\Delta z_a+\\Delta z_b

z1=z1+Δx1Δza+Δzb

image-20220107142216586

数据结构

多边形Y表; 活化多边形表(APT);边表(ET);活化边对表(AET)。

多边形Y表

存放所有多边形信息。

根据多边形顶点中最小的y坐标,插入多边形Y表中的相应位置;

根据序号可从定义多边形的数据结构中取多边形信息。(ax+by+cz+d=0的系数,多边形的边,顶点坐标和颜色

image-20220107142623370

活化多边形表APT:与当前扫描线相交的多边形。

APT是一个动态的链表。

image-20220107142747773

边表ET:活化多边形表中的每一个多边形都有一个边表ET(每条边端点中较大者,增量 Dx,y值较小一端的x坐标和z坐标)

image-20220107142944395

活化边对表AET

在一条扫描线上,同一多边形的相邻两条边构成一个边对。活化边表AET中存放当前多边形中与当前扫描线相交的各边对的信息。

image-20220107143020380

image-20220107143115098

扫描线Z - buffer算法() {
	建多边形y表;根据多边形顶点最小y值,将多边形置入多边形y表。
	活化多边形表APT,活化边对表AET初始化为空。
	For(每条扫描线i,i从小到大) {
		1. 帧缓存CB置为背景色。
		2. 深度缓存ZB (一维数组) 置为负无穷大。
		3. 将对应扫描线i的,多边形Y表中的多边形加入到活化多边形表APT中。
		4. 对新加入的多边形,生成其相应的边表。
		5. 对APT中每一个多边形,若其边表中对应扫描线i增加了新的边,将新的边配对,加到活化边对表AET中。
		6. 对AET中的每一对边:
			6.1 对xl < j < xr 的每一个象素,按增量公式z = z + ? za计算各点depth 。
		    6.2 与ZB中的量比较,depth > ZB(j), 则令ZB(j) = depth,并确定颜色
		                值,写帧缓存。
		7. 删除APT中多边形顶点最大y坐标为i的多边形,并删除相应的边。
		8. 对AET中的每一个边对,作如下处理:
		    8.1 删除ylmax或yrmax 已等于i的边。若一边对中只删除了其中一边,
		        对该多边形的边重新配对。
		    8.2 用增量公式计算新的xl 、 xr 和zl
	}
}

缺点

在每一个被多边形覆盖像素处需要计算深度值;

被多个多边形覆盖的像素需要多次计算深度值。

对比

与Z-Buffer算法相比,扫描线算法有了很大改进

优点:

将整个绘图窗口内的消隐问题分解到一条条扫描线上解决,使所需的Z-Buffer大大减少 ;

计算深度值时,利用了面连贯性,只用了一个加法 。

缺点

每个像素处都计算深度值,甚至不止一次的计算(多边形重叠区域),运算量仍然很大。

改进

在一条扫描线上,每个区间只计算一次深度,即区间扫描线算法,又称扫描线算法

区间扫描线算法

基本思想

把当前扫描线与各多边形在投影平面的投影的交点进行排序后,使扫描线分为若干子区间。只要在区间任一点处找出在该处z值最大的一个面,这个区间上的每一个象素就用这个面的颜色来显示。

注意:该算法要求多边形不能相互贯穿,否则在同一区间上,多边形深度值的次序会发生变化。

如何确定小区间的颜色可分为三种情况

小区间上没有任何多边形,如[a4,a5],这时该小区间用背景色显示;

小区间上只有一个多边形,如[a1,a2][a5,a6]这时可以对应多边形在该处的颜色显示;

小区间上存在两个或两个以上的多边,形如[a6,a7],必须通过深度测试判断哪个多边形可见。

image-20220107144037607

若允许物体表面相互贯穿时,还必须求出它们在扫描平面的交点。用这些交点把该小区间分成更小的子区间,在这些间隔上决定哪个多边形可见。如将[a2,a3]区间分成[a2,b][b,a3]两个子区间

类似于扫描线Z-Buffer算法中的数据结构

多边形分类表、活化多边形表、边表、活化边表

活化边表中的结点是边,而非边对

❓ 如何知道每一个区间中,有几个相关的多边形?是哪几个?

🏷 解决方案:活化多边形表中增加一个标志,flag=0, 每遇到它的边,flag取反。

for (绘图窗口内的每一条扫描线)
{   求投影与当前扫描线相交的所有多边形
     求上述多边形中投影与当前扫描线相交的所有边,将它们记录在活化边表AEL中
     求AEL中每条边的投影与扫描线的交点;
     按交点的u坐标将AEL中各边从左到右排序,  两两配对组成一个区间;
      for (AEL中每个区间)
       {
          求覆盖该区间的所有多边形,将它们记入活化多边形表APL中;
          在区间上任取一点,计算APL中各多边形在该点的深度值,记深度最大者为P;
           用多边形P的颜色填充该区间
        }
}

算法的优点:将逐点(象素、Pixel)计算改为逐段计算,效率大大提高!

区域子分割算法

基本思想

首先将场景中的多边形投影到绘图窗口内,判断窗口是否足够简单,若是则算法结束;否则将窗口进一步分为四块。对此四个小窗口重复上述过程,直到窗口仅为一个像素大小。此时可能有多个多边形覆盖了该像素,计算它们的深度值,以最近的颜色显示该像素即可。

何谓窗口足够简单

窗口为空,即多边形与窗口的关系是分离的;

窗口内仅含一个多边形,即有一个多边形与窗口的关系是包含或相交。此时先对多边形投影进行裁剪,再对裁剪结果进行填充;

有一个多边形的投影包围了窗口,并且它是最靠近观察点的,以该多边形颜色填充窗口。

image-20220107144633771

•分离和包围多边形的判别方法:射线检查法;转角累计检查法;区域检查法(考试不考)

光线投射算法

基本思想

1️⃣ 考察由视点出发穿过观察屏幕一象素而射入场景的一条射线,则可确定出场景中与该射线相交的物体;

2️⃣ 在计算出光线与物体表面的交点之后,离象素最近的交点的所在面片的颜色为该象素的颜色;

3️⃣ 如果没有交点,说明没有多边形的投影覆盖此象素,用背景色显示它即可。

for屏幕上的每一象素
  {形成通过该屏幕象素(u,v)的射线;
	 for 场景中的每个物体
         {将射线与该物体求交;
		if 存在交点
		     以最近的交点所属的颜色显示象素(u,v)
		 else
		      以背景色显示象素(u,v)
	    }
    }

光线投射算法与Z缓冲器算法相比,它们仅仅是内外循环颠倒了一下顺序,算法复杂度类似

区别在于光线投射算法不需要Z缓冲器;

为了提高本算法的效率可以使用包围盒技术,空间分割技术以及物体的层次表示方法等来加速。

© 版权声明
THE END
喜欢就支持一下吧
点赞0 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片