光栅图形学算法

Posted by Haiden on April 9, 2019

光栅图形学算法

光栅图形算法多数属于计算机图形的底层算法。

光栅图形学算法的研究内容:

1
2
3
4
5
1) 直线段的扫描转换算法
2) 多边形的扫描转换与区域填充算法
3) 裁剪算法
4) 反走样算法
5) 消隐算法

一、直线段的扫描算法

1.1 直线段的扫描转换算法

直线绘制的三个常用算法:

1
2
3
1) 数值微分法(DDA)
2) 中点画线法
3) Bresenham算法
1.1.1 数值微分DDA法

对于$X_{i+1}$,相当于$X_{i}$向x轴加1的处理。

这个式子的含义是:当前步的y值等于前一步的y值加上斜率k,k为增量。

1.1.2 中点画线法

一般的直线把平面分成3部分:

1) 对于直线上的点: F(x,y) = 0

2) 对于直线上方的点: F(x,y) > 0

3) 对于直线下方的点: F(x,y) < 0

每次在最大位移方向上走一步,而另一个方向是走步还是不走步要取决于中点误差项的判断。

假定: $0≤ \mid k \mid ≤1$ 。因此,每次在x方向上加1,y方向上加1或不变需要判断。

1) M在Q的下方,则Pu 离直线近,应为下一个象素点。

2) M在Q的上方,应取Pd 为下一象素点。

判断Q在M的上方还是下方?

把M点代入理想直线方程:

$F(x_{m},y_{m}) = Ax_{m} + By_{m} + C​$

$d_{i} = F(x_{m},y_{m}) = F(x_{i} + 1,y_{i}+ 0.5) = A(x_{i} + 1) + B(y_{i} + 0.5) + C$

最终得出 y的取值

1
2
y = y + 1   (d < 0)
y = y       (d >=0)
1.1.3 Bresenham算法

算法的思想是通过各行、各列像素中心构造一组虚拟网格线,按照直线起点到终点的顺序,计算直线与各垂直网格线的交点,然后根据误差项d的符号确定该列象素中与此交点最近的象素。

误差项d的初值$d_{0}$=0 ; d=d+k ; 当d≥1,就把它减去1,保证d的相对性,且在0、1之间。

1) 最终得到x,y的取值公式:

$x_{i+1}$ = $x_{i}$ + 1

$y_{i+1}$ = $y_{i}$ + 1 (d > 0.5) ;

$y_{i+1}​$ = $y_{i}​$ (d<= 0.5)

2) 改进公式:

令 e = d-0.5,得到:

$x_{i+1}$ = $x_{i}$ + 1

$y_{i+1}$ = $y_{i}$ + 1 (e > 0) ;

$y_{i+1}​$ = $y_{i}​$ (e<= 0)

e > 0,y方向递增1;e<0,y方向不递增 e = 0 时,可任取上、下光栅点显示

1)$e_{初}$ = -0.5

2)每走一步有 e = e+k

3)if (e>0) then e = e-1

​ $e_{初}​$ = -0.5 ; $k = \frac{d_{y}}{d_{x}} ​$

3) 改进公式的表示:

各项乘以 2△x 后得到:

1)$e_{初}$(2△x) = -0.5(2 △x)

2)每走一步有 e(2△x)= e(2△x)+k(2△x)

3)if (e>0) then e(2△x) = e(2△x)-1(2△x)

4 ) 因为 $k = \frac{d_{y}}{d_{x}} $ 进一步化简得到:

1)$e_{初}$(2△x) = -△x

2)每走一步有 e(2△x)= e(2△x)+2△y

3)if (e>0) then e(2△x) = e(2△x)- 2△x

又因为e需要使用浮点数表示,涉及到整型的转换,因此可以进一步优化,由于e的取值大小不影响像素的选择,仅仅e值得符号会影响,可以通过放大e值而不改变其符号,

5) 设e=2eΔx,则:

1)$e_{初}$ = -△x

2)每走一步有 e= e+2△y

3)if (e>0) then e = e - 2△x

算法步骤为:

1) 输入直线的两端点$P0(x_{0},y_{0})​$ 和 $P1(x_{1},y_{1})​$。

2) 计算初始值△x、△y、e=-△x、x= $x_{0}$、y= $y_{0}​$ 。

3) 绘制点(x,y)。

4)e更新为e+2△y,判断e的符号。若e>0,则(x,y)更新为( x+1,y+1),同时将e更新为e-2△x;否则 (x,y)更新为(x+1,y)。

5)当直线没有画完时,重复步骤3和4。否则结束。

二、 多边形的扫描转换及边界填充

多边形有两种重要的表示方法:顶点表示和点阵表示。

顶点表示是用多边形的顶点序列来表示多边形。由于它没有明确指出哪些象素在多边形内,故不能直接用于面着色。

点阵表示是用位于多边形内的象素集合来刻画多边形。这种表示丢失了许多几何信息(如边界、顶点等)但它却是光栅显示系统显示时所需的表示形式。

光栅图形的一个基本问题是把多边形的顶点表示转换为点阵表示。这种转换称为多边形的扫描转换。使用的算法有:

2.1 X-扫描线算法

X-扫描线算法填充多边形的基本思想是按扫描线顺序,计算扫描线与多边形的相交区间,再用要求的颜色显示这些区间的像素,即完成填充工作。

如扫描线y=3与多边形的边界相交于4点: (2,3)、(4,3)、(7,3)、(9,3)。

这四点定义了扫描线从X=2到X=4,从X=7到X=9两个落在多边形内的区间,该区间内的像素应取填充色。

X-扫描线算法步骤如下:

1)确定多边形所占有的最大扫描线数,得到多边形顶点的最小和最大y值($y_{min}​$ 和 $y_{max}​$)

2) 从y = $y_{min}$ 到y = $y_{max}$,每次用一条扫描线进行填充。

3)对一条扫描线填充的过程可分为四个步骤:

1
2
3
4
1.求交:计算扫描线与多边形各边的交点
2.排序:把所有交点按递增顺序进行排序
3.交点配对:第一个与第二个,第三个与第四个
4.区间填色:把这些相交区间内的像素置成不同于背景色的填充色

当扫描线与多边形顶点相交时,交点的取舍问题(交点的个数保证为偶数个)

1))若共享顶点的两条边分别落在扫描线的两边,交点只算一个。

2)若共享顶点的两条边在扫描线的同一边,这时交点作为零个或两个(检查若共享顶点的两条边的另外两个端点的y值,若在共享顶点的下方,则算0,在上方,则算2)。

2.2 改进X-扫描线算法

X-扫描线算法填充多边形的基本思想是按扫描线顺序计算扫描线与多边形的相交区间,求交的计算量是非常大.

避免求交运算,引进一套特殊的数据结构:

1) 活性边表(AET):把与当前扫描线相交的边称为活性边,并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中。

2) 结点内容:一个结点在数据结构里可用结构来表示

x △x y~max~ next
当前扫描线与边的交点坐标 从当前扫描线到下一条扫描线间x的增量 该边所交的最高扫描线的坐标值 指向下一条边的指针

随着扫描线的移动,扫描线与多边形的交点和上一次交点相关:

设边的直线斜率为k 因$y_{i+1} - y_{i} = 1$,所以:

即:△x = 1/k

需构造一个新边表(NET),用来存放多边形的边的信息。

1
2
1)首先构造一个纵向链表,链表的长度为多边形所占有的最大扫描线数
2)NET挂在与该边低端y值相同的扫描线桶中。也就是说,存放在该扫描线第一次出现的边

构造链表节点:

该边的$y_{max}$

该边较低点的x坐标值$x_{min}$

该边的斜率1/k

指向下一条具有相同较低端y坐标的边的指针

扫描完成后在这个表里只有1、3、5、7处有边,

y=1开始做,而在1这条线上有两条边进来了,然后就把这两条边放进活性边表来处理。

每做一次新的扫描线时,要对已有的边进行三个处理:

1
2
3
1) 是否被去除掉;
2) 如果不被去除,第二就要对它的数据进行更新。所谓更新数据就是要更新它的x值,即:x+1/k
3) 看有没有新的边进来,新的边在NET里,可以插入排序插进来。

2.3 边缘填充算法

按任意顺序处理多边形的每条边。在处理每条边时,首先求出该边与扫描线的交点,然后将每一条扫描线上交点右方的所有像素取补。多边形的所有边处理完毕之后,填充即完成。

2.4 栅栏填充算法

栅栏指的是一条过多边形顶点且与扫描线垂直的直线。它把多边形分为两半。在处理每条边与扫描线的交点时,将交点与栅栏之间的像素取补

2.5 边界标志算法

1) 帧缓冲器中对多边形的每条边进行直线扫描转换,亦即对多边形边界所经过的象素打上标志。

2)再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。

由于边界标志算法不必建立维护边表以及对它进行排序,所以边界标志算法更适合硬件实现,这时它的执行速度比有序边表算法快一至两个数量级。

三、区域填充算法

区域指已经表示成点阵形式的填充图形,是象素的集合。

区域填充是指将区域内的一点(常称种子点)赋予给定颜色,然后将这种颜色扩展到整个区域内的过程。

区域可采用内点表示和边界表示两种表示形式。

内点表示:枚举出区域内部的所有像素,内部的所有像素着同一个颜色,边界像素着与内部像素不同的颜色 边界表示:枚举出边界上的所有像素,边界上的所有像素着同一个颜色,内部像素着与边界像素不同的颜色

区域填充算法要求区域是连通的,因为只有在连通区域中,才可能将种子点的颜色扩展到区域内的其它点。

区域可分为4向连通区域和8向连通区域。

使用栈结构来实现简单的种子填充算法

种子像素入栈,当栈非空时重复执行如下三步操作:

1
2
3
1)栈顶像素出栈
2)将出栈像素置成要填充色
3)按左、上、右、下顺序检查与栈像素相邻的四个像素,若其中某个像素不在边界且未置成填充色,则把该像素入栈

四、 反走样

走样:对于像素生成的线条具有明显的“锯齿形”即会发生走样(Liasing)现象。

走样是光栅显示的一种固有性质。产生走样现象的原因是像素本质上的离散性。

反走样技术涉及到某种形式的“模糊”来产生更平滑的图像对于在白色背景中的黑色矩形,通过在矩形的边界附近掺入一些灰色像素,可以柔化从黑到白的尖锐变化。

反走样方法:1、非加权区域采样方法 2、加权区域采样方法

1.4.1 非加权区域采样方法

根据物体的覆盖率(coverage)计算像素的颜色。覆盖率是指某个像素区域被物体覆盖的比例。

把这个多边形放在方格线中,其中每个正方形的中心对应显示器上一个像素中心。被多边形覆盖了一半的像素的亮度值赋为1/2,覆盖三分之一的像素赋值为1/3;以此类推。

如果帧缓冲区的每个像素有 4个比特位,那么0表示黑色,15表示白色。

1.4.2 加权区域采样方法

将直线段看作是具有一定宽度的狭长矩形;当直线段与像素有交时,根据相交区域与像素中心的距离来决定其对象素亮度的贡献。直线段对一个像素亮度的贡献正比于相交区域与像素中心的距离。

采用离散计算方法

加权方案:中心子像素的加权是角子像素的4倍,是其它像素的2倍,对九个子像素的每个网格所计算出的亮度进行平均。

1) 然后求出所有中心落于直线段内的子象素。

2) 最后计算所有这些子象素对原象素亮度贡献之和。

五、裁剪算法

使用计算机处理图形信息时,计算机内部存储的图形往往比较大,而屏幕显示的只是图形的一部分。

5.1 点的裁剪

对于任意一点P(x,y),若满足下列两对不等式:

$x_{left}$ <= x <= $x_{right}$

$y_{bottom}$ <= y <= $y_{top}​$

则点P在矩形窗口内;否则,点P在矩形窗口之外。

5.2 直线段的裁剪

5.2.1 Cohen-Sutherland算法

这算法又称为编码裁剪算法,算法的基本思想是对每条直线段分三种情况处理

1)若点p1和p2完全在裁剪窗口内,全取。

2)若点p1(x1,y1)和p2(x2,y2)均在窗口外,且满足下列四个条件之一:,全弃。

3) 直线段既不满足“全取”的条件,也不满足“全弃”的条件,需要对直线段按交点进 行分段,分段后判断直线是“全取”还是“全弃”

每条线段的端点都赋以四 位二进制码$D_{3}D_{2}D_{1}D_{0}​$,编码规则如下:

若x< $X_{left}​$ ,则$D_{0}​$ = 1,

若x> $X_{right}​$ ,则$D_{1}​$ = 1,

若y< $Y_{bottom}​$,则$D_{2}​$ =1,

若y> $Y_{top}​$,则$D_{3}​$ = 1,

$D_{0}$对应窗口左边界 $D_{1}$对应窗口右边界 $D_{2}$对应窗口下边界 $D_{3}​$对应窗口上边界

裁剪一条线段时,先求出端点p1和p2的编码code1和code2然后进行二进制“或”运算和“与”运算

1) 若$code1 \mid code2=0​$,对直线段应简取之

2) 若$code1 \& code2≠0​$,对直线段可简弃之

3) 若上述两条件均不成立,则需求出直线段与窗口边界的交点在交点处把线段一分为二

5.2.2 中点分割算法

首先对直线段的端点进行编码。把线段和窗口的关系分成三种情况:

1
2
3
1、完全在窗口内
2、完全在窗口外
3、和窗口有交点

中点分割算法的核心思想是通过二分逼近来确定直线段与窗口的交点。

5.2.3 Liang-Barsky算法

算法主要处理

1) 用参数方程表示一条直线

x = $x_{1}$ + △x * u (0<= u <= 1)

y = $y_{1}$ + △y * u (0<= u <= 1)

2) 把被裁剪的红色直线段看成是一条有方向的线段,把窗口的四条边分成两类:入边和出边

裁剪线段的起点是直线和两条入边的交点以及始端点三个点里最前面的一个点,即参数u最大的那个点; 裁剪线段的终点是和两条出边的交点以及端点最后面的一个点,取参数u最小的那个点。

u1,u2分别表示线段(u1≤u2)可见部分的开始和结束.

$u_{1}$ = max(0,$U_{l}$, $U_{b}$)

$u_{2}$ = min(1,$U_{t}$, $U_{r}​$)

直线的参数方程

x = $x_{1}​$ + △x * u (0<= u <= 1)

y = $y_{1}​$ + △y * u (0<= u <= 1)

得到:

$x_{left}​$ <= $x_{1}​$ + △x * u <= $x_{right}$

$y_{bottom}​$ <= $y_{1}​$ + △y * u <= $y_{top}$

令:

$p_{1}$ = -△x ; $q_{1}$ = $x_{1}$ - $x_{left}$

$p_{2}$ = △x ; $q_{2}$ = $x_{right}$ - $x_{1}$

$p_{3}$ = -△y ; $q_{3}$ = $y_{1}$ - $y_{bottom}$

$p_{4}$ = △y ; $q_{4}$ = $y_{top}$ - $y_{1}$

于是有: u* $p_{k}​$ <= $q_{k}​$ 其中,k = 1,2,3,4

入边:左边和下边 出边:右边和上边
$p_{1}$ = -△x ; $q_{1}$ = $x_{1}$ - $x_{left}$ $p_{2}$ = △x ; $q_{2}$ = $x_{right}$ - $x_{1}$
$p_{3}$ = -△y ; $q_{3}$ = $y_{1}$ - $y_{bottom}$ $p_{4}$ = △y ; $q_{4}$ = $y_{top}$ - $y_{1}$

1) 分析 $P_{k}​$ =0的情况

任何平行于窗口某边界的直线

满足 $ q_{k}​$ < 0 ,则线段完全在边界外,应舍弃该线段

满足 $ q_{k}$ >= 0,则进一步判断

2) 分析 $P_{k}$ ≠0的情况

当 $P_{k}$ <0时: 线段从裁剪边界延长线的外部延伸到内部,是入边交点

当 $P_{k}$ >0时:线段从裁剪边界延长线的内部延伸到外部,是出边交点

一共四个u值,再加上u=0、u=1两个端点值,总共六个值

把 $P_{k}$ <0的两个u值和0比较去找最大的,

把 $P_{k}$ >0的两个u值和1比较去找最小的,这样就得到两个端点的参数值

$u_{max}​$ = max ( 0, $u_{k}​$ , $u_{k}​$ )

$u_{min}​$ = min ( $u_{k}​$ , $u_{k}​$ , 1)

若 $u_{max}> u_{min}​$,则直线段在窗口外,删除该直线

若 $u_{max} ≤ u_{min}$ ,将 $u_{max}$ 和 $u_{min}$ 代回直线参数方程,即求出直线与窗口的两实交点坐标。

$ x = x_{1} +(x_{2} -x_{1}) * u$

$y= y_{1} + (y_{2} - y_{1}) * u$

因为对于实交点0 ≤u ≤1,因此 $u_{max}​$ 不能小于0,$u_{min}​$ 不能大于1。

5.3 多边形剪裁

多边形裁剪算法的输出应该是裁剪后的多边形边界的顶点序列

5.3.1 Sutherland-Hodgeman多边形裁剪

算法的基本思想是将多边形边界作为一个整体,每次用窗口的一条边对要裁剪的多边形和 中间结果多边形进行裁剪。

根据多边形每一边与窗口边所形成的位置关系,沿着多边形依次处理顶点会遇到四种情况:

1) 第一点S在不可见 可见侧侧面,而第二点P在可见侧,交点I与点P均被加入到输出顶点表中。

2) 是S和P都在可见侧,则P被加入到输出顶点表中

3) S在可见侧,而P在不可见侧,则交点I被加入到输出顶点表中

4) 如果S和P都在不可见侧,输出顶点表中不增加任何顶点

在窗口的一条裁剪边界处理完所有顶点后,其输出顶点表将用窗口的下一条边界继续裁剪,例:

5.4 文字裁剪

5.4.1 串精度裁剪

当字符串中的所有字符都在裁剪窗口内时,就全部保留它,否则舍弃整个字符串

5.4.2 字符精度裁剪

在进行裁剪时,任何与窗口有重叠或落在窗口边界以外的字符都被裁剪掉

5.4.3 笔画/象素精度裁剪

将笔划分解成直线段对窗口作裁剪。需判断字符串中各字符的哪些像素、笔划的哪一部分在窗口内,保留 窗口内部分,裁剪掉窗口外的部分。

六、消隐算法

消除隐藏线和隐藏面,简称为消隐。消除隐藏线、隐藏面,主要介绍以下几个算法:

1
2
3
Z缓冲区(Z-Buffer)算法
扫描线Z-buffer算法
区域子分割算法

消隐的分类

1、按消隐对象分类

1
2
1)线消隐:消隐对象是物体上的边,消除的是物体上不可见的边
2)面消隐:消隐对象是物体上的面,消除的是物体上不可见的面,通常做真实感图形消隐时用面消隐

2、按消隐空间分类

1
2
3
1)物体空间的消隐算法:场景中有k个物体,将其中一个物体与其余k-1个物体逐一比较,显示它可见表面以达到消隐的
目的(Roberts算法和光线投射法)
2)图像空间的消隐算法:以屏幕窗口内的每个像素为处理单元。确定在每一个像素处,场景中的k个物体哪一个距离观察点最近,从而用它的颜色来显示该像素。(主流消隐算法)

6.1 Z-buffer算法

Z缓冲器算法也叫深度缓冲器算法,属于图像空间消隐算法

该算法有帧缓冲器和深度缓冲器。对应两个数组:

intensity(x,y)——属性数组(帧缓冲器):存储图像空间每个可见像素的光强或颜色

depth(x,y)——深度数组(z-buffer):存放图像空间每个可见像素的z坐标

z-buffer算法比较p1和p2的z值,将最大的z值存入z缓冲器中

算法思想:先将Z缓冲器中各单元的初始值置为最小值。当要改变某个像素的颜色值时,首先检查当前多边形的深度值是否大于该像素原来的深度值(保存在该像素所对应的Z缓冲器的单元中)如果大于原来的z值,说明当前多边形更靠近观察点,用它的颜色替换像素原来的颜色。

6.2 区间扫描线算法

区间扫描线算法。该算法放弃了z-buffer的思想,是一个新的算法,这个算法被认为是消隐算法中最快的

扫描线的交点把这条扫描线分成了若干个区间,每个区间上必然是同样一种颜色 对于有重合的区间,如a6a7这个区间,要么显示F2的颜色,要么显示F3的颜色,不会出现颜色的跳跃

算法的优点:将象素计算改为逐段计算,效率大大提高。

实现算法步骤:

要有投影多边形,然后求交点,然后交点进行排序排序。

排序的结果就分成了一个个区间,然后在每个区间找当中的一个像素(i,j),在(i,j)处计算每个相关面的z值,对相关深度值z进行比较,其中最大的一个就表示是可见的。整个这段区间就画这个z值最大面的颜色

1)小区间上没有任何多边形,如[a4,a5],用背景色显示。

2)小区间只有一个多边形,如[a1,a2],显示该多边形的颜色。

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

6.3 区域子分割算法(Warnock算法)

采用了分治的思想,利用了堆栈的数据结构把物体投影到全屏幕窗口上,然后递归分割窗口,直到窗口内目标足够简单,可以显示为止。

算法步骤:

1)如果窗口内没有物体则按背景色显示。

2)若窗口内只有一个面,则把该面显示出来。

3)否则,窗口内含有两个以上的面,则把窗口等分成四个子窗口。对每个小窗口再做上述同样的处理。这样反复地进行下去。