《计算机图形学》练习题（答案）

《计算机图形学》练习题

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=2?y-?x=1

2?y=8 2?y-2?x=-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边分类表 y 10 9 8 V6 7 6 5 4 3 2 1 V5 E5 E6 E4 V4 E3 V3 E2 V1 E1 V2 1 2 3 4 5 6 7 8 9 10 图1多边形的边和顶点

x 1

1 2 3 4 5 6 7 8 9 10

Y值(Scan Line Number) 1 2 3 4 5 6 7 8 9 10 边(Edge Number) 0 0 0 E1 E6,E2 E6 E3 E5,E3 E4 0 表2 边的初始值

边 4 5 6 7 8 9 x 1 1 9 1 9 1 9 1 1 8 2 7 3 3 6 ymax 7 4 6 7 6 6 6 7 7 9 9 9 9 9 9 1/m 0 0 0 0 0 0 0 1 -1 1 -1 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)

(2)?平移这个对象，使得他的固定点与原点重合

2

?缩放这个在坐标原点的对象

?平移这个对象，使得他的固定点回到原始位置

?x'??sx?y'???0????1??0 ???

所以 A(-5,-2) B(-3,0) C(5,2)

4二维变换

(1) 请用齐次坐标表示写出点Q(x,y)绕定点P(a,b)旋转的旋转变换矩阵。

0

(2) 求出以A(0,0)、B(1,1)和C(5,2)为顶点的三角形绕固定点P(-1,-1)点旋转45后的三角形的顶点坐标。 (1)

0sy0xf(1?sx)??xr??yr?yf(1?sy)??????1???1?? x’=xr+(x- xr)cos θ -(y- yr)sin θ y’=yr+(x- xr)sin θ +(y- yr)cos θ

(2)?平移这个对象，使得他的固定点与原点重合 ?旋转这个在坐标原点的对象

?平移这个对象，使得他的固定点回到原始位置

?x'??cos??y'???sin?????1??0 ????sin?cos?0xr(1?cos?)?yrsin???x??y?yr(1?cos?)?xrsin???????1???1??

A(-1,-1+2) B(-1,-1+22) C(-1+3/2*2,-1+9/2*2)

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) 根据线段端点的编码对图中所有线段分类，指出哪些线段是可见的？哪些是不可见的？哪些是候选的裁剪线段。

3

（1） 1001 J(-2,10) B(-1,7) C(-1,5) R(2,6) D(3,8) I(-4,7) E(-2,3) A(-4,2) F(1,2) 1 H(3,3) L(-3,1) -1 1 -1 G(1,-2) 3 1000 1010 0001 0000 0010 0101 0100 0110

（2） A:0001 B:1000 C:0000 D:1010 E:0000 F:0000 G:0100

4

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)中用实线绘出最后裁剪结果。

P9 P9 P9

P7 P7

P8 P1 P8 P8 P1 P6 P6 P1 P3 P3 P3 P P 55

P4 P4 P4 P2 P2 P2

图1多边形裁剪 图1(b) 图1(a)

P9 P9

P7

P7

P7

P6 P5

P1

P3 P8

P6 P5

P1

P3

P8

P6 P5

P2

P4

P2

图1(c)

P4 图1(d)

5