可能这会是图形学期末复习最后一个整理了, 感觉其实不如直接看PPT。

1、填空20+选择20+判断10+简答20+综合30

2、没有编程题

3、复习PPT上的基本概念和算法

光栅图形中电的表示

像素由其左下角坐标表示

增量法：

图形显示

图元：基本图形元素

图元的生成：完成图元的参数表示形式到点阵表示形式的转换。通常也称扫描转换图元。

直线的扫描转换:

确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。

三个常用算法：

生成目标，求与直线段充分接近的像素集

生成前提条件

基本思想：

已知过端点P0 (x0, y0), P1(x1, y1)的

直线段L ： y = k x + b y = kx + b y=kx+b

直线斜率为 k = y 1 − y 2 x 1 − x 0 k = \frac{y_1-y_2}{x_1-x_0} k=x1​−x0​y1​−y2​​

从x的左端点x0开始，向x右端点步进。

步长=1(个象素)，计算相应的y坐标 y = k x + b y=kx+b y=kx+b；

取象素点 ( x , r o u n d ( y ) ) (x, round(y)) (x,round(y))作为当前点的坐标。

基本思想：

当前象素点为 ( x p , y p ) (x_p, y_p) (xp​,yp​) ，下一个象素点为P1或P2。

设 M = ( x p + 1 , y p + 0.5 ) M=(x_p+1, y_p+0.5) M=(xp​+1,yp​+0.5)，为p1与p2之中点

Q为理想直线与 x = x p + 1 x=x_p+1 x=xp​+1垂线的交点。

将Q与M的y坐标进行比较。

当M在Q的下方，则P2应为下一个象素点；

当M在Q的上方，应取P1为下一点。

构造判别式： d = F ( M ) = F ( x p + 1 , y p + 0.5 ) = a ( x p + 1 ) + b ( y p + 0.5 ) + c d=F(M)=F(x_p+1,y_p+0.5)=a(x_p+1)+b(y_p+0.5)+c d=F(M)=F(xp​+1,yp​+0.5)=a(xp​+1)+b(yp​+0.5)+c

（其中 a = y 0 − y 1 , b = x 1 − x 0 , c = x 0 y 1 − x 1 y 0 a=y_0-y_1, b=x_1-x_0, c=x_0y_1-x_1y_0 a=y0​−y1​,b=x1​−x0​,c=x0​y1​−x1​y0​）

当d0，M在L(Q点)上方，取右方 P D P_D PD​为下一个象素；

当d=0，选P1或P2均可，约定取 P D P_D PD​为下一个象素；

d是 x p x_p xp​， y p y_p yp​的线性函数，因此可采用增量计算，提高运算效率。

初值 d 0 = F ( x 0 + 1 , y 0 + 0.5 ) = a + 0.5 b d_0=F(x_0+1, y_0+0.5)=a+0.5b d0​=F(x0​+1,y0​+0.5)=a+0.5b

若 d ≥ 0 d\ge0 d≥0时，则取正右方象素 P D ( x p + 1 , y p ) P_D(x_p+1, y_p) PD​(xp​+1,yp​),

要判断下一个象素位置，则要计算 d i + 1 = F ( x p + 2 , y p + 0.5 ) = a ( x p + 2 ) + b ( y p + 0.5 ) = d + a d_{i+1}=F(x_p+2, y_p+0.5)=a(x_p+2)+b(y_p+0.5)=d+a di+1​=F(xp​+2,yp​+0.5)=a(xp​+2)+b(yp​+0.5)=d+a

增量为 a

若d=0, 则应取P2为下一象素，而且下一象素的判别式为

d ′ = F ( x p + 2 , y p − 1.5 ) = ( x p + 2 ) 2 + ( y p − 1.5 ) 2 − R 2 = d + 2 ( x p − y p ) + 5 d' = F(x_p+2,y_p-1.5) = (x_p+2)^2+(y_p-1.5)^2-R^2=d+2(x_p-y_p)+5 d′=F(xp​+2,yp​−1.5)=(xp​+2)2+(yp​−1.5)2−R2=d+2(xp​−yp​)+5

第 一个象素是（0, R），判别式d的初始值为

d 0 = F ( 1 , R − 0.5 ) = 1.25 − R d_0 = F(1,R-0.5) =1.25-R d0​=F(1,R−0.5)=1.25−R

为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。

使用e=d-0.25代替d

e0=1-R

当d为整数时（d if(d d += 2*(x-y) + 5; x++; y--; } } } /* 注意到d的增量是x,y的线性函数， 每当x递增1，则d的增量递增Δx=2 每当y递减1，则d的增量递增Δy=2 Δx初始值=3 Δy初始值=-2r+2 */ //中点画圆-改进版 MidpointCircle(int r, int color) { int x,y; int d,d1,d2; x=0; y=r; d=1-r; d1=3; d2=-2*r+2; drawpixel(x,y,color); while(x d += d1; x++; d1+=2; } else{ d += d1+d2; x++; y--; d1+=2; d2+=2; } } } 4.3 多边形填充算法

多边形表示方法：顶点表示和点阵表示

多边形的扫描转换：把多边形的顶点表示转化为点阵表示

逐个判断绘图窗口内的像素是否在多边形内

判断点是否在多边形内部的方法

步骤：

从待判别点v发出射线

求交点个数k

K的奇偶性决定了点与多边形的内外关系

特殊情况处理

步骤

从v点向多边形P顶点发出射线，形成有向角 θ i \theta_i θi​

计算有向角的和，得出结论

基本思想

处理对象

步骤

扫描线（YX）算法中扫描线要和所有的边求交，效率较低。因为一条扫描线往往只和少数几条边相交。

利用两个性质

边的连贯性：当某条边与当前扫描线相交时，它很可能也与下一条扫描线相交。

当前扫描线与多边形某一条边的交点的x坐标为x，则下一扫描线与该边的交点不要重计算，只要加一个增量△x。

扫描线的连贯性：当前扫描线与各边的交点顺序，与下一条扫描线与各边的交点顺序很可能相同或类似。

主要思想

与当前扫描线相交的边称为活动边（active edge)，把它们按与扫描线交点x坐标递增的顺序存入一个链表中，称为活动边表（AET, Active edge table)

只需对当前扫描线的活动边表作更新，即可得到下一条扫描线的活动边表。

数据结构

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

边桶表(NET)

特殊情况

水平边扔掉

交点的取整规则

要求：使生成的像素全部位于多边形之内

假定非水平边与扫描线y=e相交，交点的横坐标为x,规则如下

X为小数

(x,e)落在像素上

交点位多边形的顶点（下闭上开）

应该是指经过P1的点

取余: M ˉ = A − M , A = 0 x F F F F F F F F \bar{M} = A - M, A = 0xFFFFFFFF Mˉ=A−M,A=0xFFFFFFFF

原理

算法基本思想

步骤

将绘图窗口的背景色置为 M ˉ \bar{M} Mˉ；

对多边形的每一条非水平边，从该边上的每个象素开始向右求余；

适合用于具有帧缓存的图形系统。处理后，按扫描线顺序读出帧缓存的内容，送入显示设备。

优点：算法简单

缺点：对于复杂图形，每一象素可能被访问多次，输入/输出的量比有序边表算法大得多。

引入栅栏，以减少填充算法访问象素的次数

栅栏：与扫描线垂直的直线，通常过一顶点，且把多边形分为左右二半。

基本思想：扫描线与多边形的边求交，将交点与栅栏之间的象素取补。

减少了象素重复访问数目，但不彻底。

基本思想：

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

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

使用一个布尔量inside来指示当前点是否在多边形内的状态。

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

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

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

区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的

1）深度递归的种子填充算法(漫水法）

从已知种子点出发，每填充一点，在其周围寻找新种子点，重复进行，直到再无未填充的点为止。

针对内点表示的4连通区域的递归填充具体步骤:

1.种子入栈.

2.当栈非空时,进行下面的操作,否则结束.

3.栈顶元素出栈,如果是未填充的内部点,则将其填充. 继续考察与其连通的点,若是未填充的内部点,则该点入栈.返回2.

2）扫描线种子填充算法

种子填充的递归算法原理和程序都很简单，但由于多次递归，费时、费内存，效率不高。为了减少递归次数，提高效率可以采用采用扫描线算法。

算法的基本过程如下：

当给定种子点(x,y)时，首先填充种子点所在扫描线上的位于给定区域的一个区段，

然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，确定新种子点，并依次保存下来。

反复这个过程，直到填充结束。

上述算法对于每一个待填充区段，只需压栈一次；而在递归算法中，每个象素都需要压栈。因此，扫描线填充算法提高了区域填充的效率。

扫描线种子填充算法

(1)初始化：堆栈置空。将种子点（x，y）入栈。

(2)出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。

(3)填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到非内部。分别标记区段的左、右端点坐标为xl和xr。

(4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。

用离散量表示连续量引起的失真现象称之为走样(aliasing)

光栅图形的走样现象有：

阶梯状边界

图形细节失真（图形中的那些比象素窄的细节变宽）

狭小图形遗失和动态图形的闪烁

用于减少或消除这种效果的技术称为反走样(antialiasing)

把显示器分辨率提高一倍

直线经过两倍的象素，锯齿也增加一倍

但同时每个阶梯的宽度也减小了一倍

所以显示出的直线段看起来就平直光滑了一些

→

优缺点

增加分辨率虽然简单，却是一种不经济的方法

显示器的水平、竖直分辩率各提高一倍，则显示器的点距减少一倍，帧缓存容量则增加到原来的4倍，而扫描转换同样大小的图元却要花4倍时间

而且它也只能减轻而不能消除锯齿问题

基本原理

假设与现实的矛盾是导致走样现象出现的原因之一

基本思想：

有宽度的线条轮廓

象素相交的五种情况及用于计算面积的量，其中m是直线的斜率。一个像素宽为1。

面积计算

情况(1)(5)阴影面积为： D 2 2 m \frac{D^2}{2m} 2mD2​

情况(2)(4)阴影面积为： D − m 2 D - \frac{m}{2} D−2m​

情况(3)阴影面积为： 1 − D 2 m 1-\frac{D^2}{m} 1−mD2​

上述阴影面积是介于0-1之间的正数，用它乘以象素的最大灰度值，再取整，即可得到象素的显示灰度值。这种区域取样法的反走样效果较好。

为了简化计算可以采用离散的方法

步骤

首先将屏幕象素均分成n个子象素

然后计算中心点落在直线段内的子象素的个数k

将屏幕该象素的亮度置为相交区域面积的近似值可k/n

非加权区域采样方法有两个缺点

象素的亮度与相交区域的面积成正比，而与相交区域落在象素内的位置无关，这仍然会导致锯齿效应

直线条上沿理想直线方向的相邻两个象素有时会有较大的灰度差

裁剪：

确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。

基本思想：

对于每条线段 P 1 P 2 P_1P_2 P1​P2​分为三种情况处理:

（1）若 P 1 P 2 P_1P_2 P1​P2​完全在窗口内，则显示该线段

（2）若 P 1 P 2 P_1P_2 P1​P2​明显在窗口外，则丢弃该线段

（3）若线段不满足“取”或 “弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理

为快速判断，采用编码方法：每个区域赋予4位编码

本算法的优点在于简单，易于实现。

他可以简单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。

在这个算法中求交点是很重要的，他决定了算法的速度。

另外，本算法对于其他形状的窗口未必同样有效。

特点：用编码方法可快速判断线段的完全可见和显然不可见。

(A、B分别为距 P 0 、 P 1 P_0、P_1 P0​、P1​最近的可见点， P m P_m Pm​为 P 0 P 1 P_0P_1 P0​P1​中点)

与编码裁剪算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况:

全在、完全不在和线段和窗口有交。对前两种情况，进行一样的处理

对于第三种情况，用中点分割的方法求出线段与窗口的交点

从 P 0 P_0 P0​出发找最近可见点采用中点分割方法

先求出 P 0 P 1 P_0P_1 P0​P1​的中点Pm

若 P 0 P m P_0P_m P0​Pm​不是显然不可见的，并且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在 P 0 P m P_0P_m P0​Pm​上，所以用 P 0 P m P_0P_m P0​Pm​代替 P 0 P 1 P_0P_1 P0​P1​

否则取 P m P 1 P_mP_1 Pm​P1​代替 P 0 P 1 P_0P_1 P0​P1​

再对新的 P 0 P 1 P_0P_1 P0​P1​求中点 P m P_m Pm​。重复上述过程，直到 P m P 1 P_mP_1 Pm​P1​长度小于给定的控制常数为止，此时 P m P_m Pm​收敛于交点

从 P 1 P_1 P1​出发找最近可见点采用上面类似方法

这个看PPT确实是不好理解, 可以看看这里计算机图形学——梁友栋-Barsky算法

主要思想：

将线段 P 1 P 2 P_1P_2 P1​P2​表示为参数形式：

确定始边和终边 左→右，右→左 下→上，上→下

对于每条直线，裁剪矩形内的线段部分由参数u1和u2定义

u1的值由线段的始边边界（即：从外到内遇到的矩形边界）(p0)所决定。对这些边界计算rk。u2取1和各个rk值之中的最小值

如果u1>u2，则线段完全落在裁剪窗口之外，被舍弃

否则裁剪线段由参数u的两个值u1,u2计算出来

基本思想是一次用窗口的一条边裁剪多边形

考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分:可见一侧；不可见一侧

多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种:

情况（1）仅输出顶点P；

情况（2）输出0个顶点

情况（3）输出线段SP与裁剪线的交点 I

情况（4）输出线段SP与裁剪线的交点 I 和终点 P

上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入 对于每一条裁剪边，算法框图同上，只是判断点在窗口哪一侧以及求线段SP与裁剪边的交点算法应随之改变

裁剪过程

裁剪窗口为任意多边形（凸、凹、带内环）的情况