.
精品
《计算机图形学》练习题
1．直线扫描转换的Bresenham算法
(1) 请写出生成其斜率介于0和1之间的直线的Bresenham算法步骤。
(2) 设一直线段的起点和终点坐标分别为(1,1)和(8,5)，请用Bresenham算法生成此直线
段，确定所有要绘制象素坐标。
(1)输入线段的两个端点，并将左端点存储在(x0,y0)中
将(x0,y0)装入帧缓存，画出第一个点
计算常量∆x, ∆y, 2∆y, and 2∆y-2∆x,并得到决策参数的第一个值：
p0 = 2∆y - ∆x
④从k=0开始，在沿线路径的每个xk处，进行下列检测:
如果pk < 0,下一个要绘制的点就是(xk +1,yk) ，并且pk+1 = pk + 2∆y
否则下一个要绘制的点就是(xk +1, yk +1)，并且 pk+1 = pk + 2∆y- 2∆x
⑤重复步骤4，共 ∆x-1次
(2)m=(5-1)/(8-1)=0.57
x=7 y=4
P0=2y-x=1
2y=8 2y-2x=-6
k pk (xk+1,yk+1)
0 1 (2,2)
1 -5 (3,2)
2 3 (4,3)
3 -3 (5,3)
4 5 (6,4)
5 -1 (7,4)
6 7 (8,5)
2．已知一多边形如图1所示，其顶点为V1、V2、V3、V4、V5、V6，边为E1、E2、E3、E4、E5、
E6。用多边形的扫描填充算法对此多边形进行填充时(扫描线从下到上)要建立边分类表
(sorted edge table)并不断更新活化边表(active edge list)。
(1) 在表1中填写边分类表中每条扫描线上包含的边(标明边号即可)；
(2) 在表2中写出边分类表中每条边结构中各成员变量的初始值
(3) 指出位于扫描线y=6,7,8,9和10时活化边表中包含那些边，并写出这些边中的x值、
ymax值、和斜率的倒数值1/m。
表1边分类表
x
4
8
1
图1多边形的边和顶点
y
1 4 8 2 3 5 6 7
9
10
2
3
5
6
7
9
10
V1
V2
V3
V4
V5
V6
E1
E2
E3
E4
E5
E6
.
精品
边 x ymax 1/m
4 1 1 9 7 4 6 0 0
5 1 9 7 6 0 0
6 1 9 6 6 0 0
7 1 1 8 7 7 9 0 1 -1
8 2 7 9 9 1 -1
9 3 3 6 9 9 9 1 -1
3. 二维变换
(1) 记P(xf,yf)为固定点，sx、sy分别为沿x轴和y轴方向的缩放系数，请用齐次坐标
(Homogeneous Coordinate)表示写出二维固定点缩放变换的变换矩阵。
(2) 把以A(0,0)、B(1,1)和C(5,2)为顶点的三角形以顶点C为固定点放大2倍。求出放大
后的三角形的顶点坐标。
(1)
Y值(Scan Line Number) 边(Edge
Number)
1 0
2 0
3 0
4 E1
5 E6,E2
6 E6
7 E3
8 E5,E3
9 E4
10 0
1 2 3 4 5 6 7 8 9 1
0
表2 边的初始值
.
精品
(2)平移这个对象，使得他的固定点与原点重合
缩放这个在坐标原点的对象
平移这个对象，使得他的固定点回到原始位置
1100)1(0)1(01''rryfyxfxyxsyssxsyx
所以 A(-5,-2) B(-3,0) C(5,2)
4二维变换
(1) 请用齐次坐标表示写出点Q(x,y)绕定点P(a,b)旋转的旋转变换矩阵。
(2) 求出以A(0,0)、B(1,1)和C(5,2)为顶点的三角形绕固定点P(-1,-1)点旋转450后的三
角形的顶点坐标。
(1)
(2)平移这个对象，使得他的固定点与原点重合
旋转这个在坐标原点的对象
平移这个对象，使得他的固定点回到原始位置
1100sin)cos1(cossinsin)cos1(sincos1
''yxxyyxy
x
rr
rr
A(-1,-1+2) B(-1,-1+22) C(-1+3/2*2,-1+9/2*2)
x’=xr+(x- xr)cos θ -(y- yr)sin θ
y’=yr+(x- xr)sin θ +(y- yr)cos θ
.
精品
5. 如图所示，L(-3,1)和R(2,6)为正方形裁剪窗口两个对角线角点，线段AB、CD、EF、GH
和IJ为被裁剪线段。用Cohen-Sutherland线裁剪算法进行裁剪时要对线段的端点进行编码。
(1) 请写出编码
规则，并在图中
标出相应区域的
编码
(2) 分别指出于
点A、B、C、D、E、
F、G、H对应的编
码
(3) 根据线段端
点的编码对图中
所有线段分类，
指出哪些线段是
可见的？哪些是
不可见的？哪些
是候选的裁剪线
段。
J(-2,10)
1
1 L(-3,1) 3 -1
-1
R(2,6)
A(-4,2)
B(-1,7)
C(-1,5)
D(3,8)
E(-2,3)
F(1,2)
G(1,-2)
H(3,3)
I(-4,7)
.
精品
（1）
1001 1000 1010
0001 0000 0010
0101 0100 0110
（2）
A:0001
B:1000
C:0000
D:1010
E:0000
F:0000
G:0100
H:0010
I:1000
J:1000
（3）
可见的：EF
不可见的：GH,IJ
候选的：AB,CD
6. 分别用Sutherland-Hodgman算法和Weiler-Atherton算法裁剪图1所示的多边形
p1p2p3p4p5p6p7p8p9p1，裁剪窗口为如图所示的矩形窗口。
要求：
(1) 用实线分别在图1(a)(b)(c)(d)中绘出用Sutherland-Hodgman算法沿裁剪窗口的左、
右、上、下窗口边裁剪后的中间结果
(2) 用Weiler-Atherton算法对图1所示的多边形进行裁剪，以p1为起点，以图1箭头所
示的方向为走向，在图1(e)中用箭头表示画出所有走过的边(包括多边形边和窗口边)
及其走向；并在图1(f)中用实线绘出最后裁剪结果。
P1
P3
P5
P6
P7
P8
P9
P1
P3
P5
P6
P7
P8
P9
P1
P3
P5
P6
P7
P8
P9
.
精品
7．简述多边形扫描填充算法基本原理和大致步骤，并以具体例子说明边分类表内容、扫描
过程中活化边表的信息变化。
(1)原理：
在直角坐标系中，假设有一条从左至右的扫描线穿过多边形，从左至右开始计数，与多边形
交点为奇数时，开始进入多边形，与多边形交点为偶数时，走出多边形。这样在这相邻配对
的奇偶交点间的所有象素都在多边形内。如图，奇数交点a，c，都是入多边形，偶数交点b
，d都是走出多边形，相邻的奇偶交点配对，a，b之间，c，d之间的象素都多边形内，可
见一条扫描线上，与多边形交点个数需要为偶数。依据这样的思路，扫描线从上到下从左到
右依次扫过多边形即可求得多边形所占据的象素。（注意退化情况的处理，也就是扫描线刚
图1(c)
P1
P2
P3
P4
P5
P6
P7
P8
P9
图1(d)
P1
P2
P3
P4
P5
P6
P7
P8
P9
图1(e)
P1
P2
P3
P4
P5
P6
P7
P8
P9
图1(f)
P1
P2
P3
P4
P5
P6
P7
P8
P9