习 题 解 答余敦辉湖北大学 数计学院习题解答窗口
B(-2,-1)
A(3,3)
x
y
1、试用 liang-barsky算法裁剪图中的线段 AB。
3,Liang-Barsky算法分析,P1(x1,y1)和 P2(x2,y2)
将线段看成由方向性：外到内 内到外
p1
p2
p1
p1
左 右下上
3,Liang-Barsky算法
x=x1+u·(x2-x1)
y=y1+u·(y2-y1) 0 ≤ u ≤ 1
任意直线段 I（ X1,Y1） J(X2,Y2)的参数方程：
x
y
o
wyt
wyb
wxl wxr
窗口给定裁剪窗口：
3,Liang-Barsky算法
wxl≤ x1+u·(x2-x1) ≤ wxr
wyb≤ y1+u·(y2-y1) ≤ wyt
u·(x1-x2) ≤ x1 – wxl 左边界
u·(x2-x1) ≤ wxr – x1 右边界
u·(y1-y2) ≤ y1 – wyb 下边界
u·(y2-y1) ≤ wyt – y1 上边界
p1 = x1-x2
p2 = x2-x1
p3 = y1-y2
p4 = y2-y1
令：
q1 = x1 – wxl
q2 = wxr – x1
q3 = y1 – wyb
q4 = wyt – y1
u·pk≤q k k=1,2,3,4
如果任一点（）在窗口内则：
取,=” 时求得的 u对应的是直线与窗口边界的交点
1,2,3,4分别对应左、右、下、上边界
U=0和 1时分别对应直线的起点和中点
x
y
o
wyt
wyb
wxl wxr
窗口裁剪后的两端点是哪些点？
分析：裁剪的本质
Uone=max(0,uk|pk<0,uk|pk<0)
Utwo=min(1,uk|pk>0,uk|pk>0)
I1 J
1
对于 I1J1
P1,P4小于 0 U在 0,U1,U4取大者
P2,P3大于 0 U在 1,U2,U3取小者如果 Uone≤ Utwo取可求得两端点左 p1 = x1-x2
右 p2 = x2-x1
下 p3 = y1-y2
上 p4 = y2-y1
q1 = x1 – wxl
q2 = wxr – x1
q3 = y1 – wyb
q4 = wyt – y1
假定 PK不为 0
左 p1 = x1-x2
右 p2 = x2-x1
下 p3 = y1-y2
上 p4 = y2-y1
q1 = x1 – wxl
q2 = wxr – x1
q3 = y1 – wyb
q4 = wyt – y1如果 U
one>Utwo表明什么？
P1,P3小于 0 U在 0,U1,U3取大者
P2,P4大于 0 U在 1,U2,U4取小者
Uone=max(0,uk|pk<0,uk|pk<0)
Utwo=min(1,uk|pk>0,uk|pk>0)
I1
J1
特殊处理：
(a) 直线段与窗口边界
wxl 和wxr 平行的情况
(b) 直线段与窗口边界
wyb 和wyt 平行的情况
wyt
wyb
wxl wxr wxrwxl
wyb
wyt
A
B
C
D
E
F
G
H I
J
K
L
PK为 0
p1=p2=0 p3=p4=0Uone=max(0,uk|pk<0)U
two=min(1,uk|pk>0)
左 p1 = x1-x2
右 p2 = x2-x1
下 p3 = y1-y2
上 p4 = y2-y1
q1 = x1 – wxl
q2 = wxr – x1
q3 = y1 – wyb
q4 = wyt – y1
算法步骤,
(1)输入直线段的两端点坐标,(x1,y1)和 (x2,y2),以及窗口的四条边界坐标,wyt,wyb,wxl和 wxr。
(2)若 Δx= 0,则 p1=p2=0。 此时进一步判断是否满足 q1<0或
q2<0,若满足,则该直线段不在窗口内,算法转 (7)。
否则,满足 q1>0且 q2>0,则进一步 计算 u1和 u2。 算法转
(5)。
(3)若 Δy= 0,则 p3=p4=0。 此时进一步判断是否满足 q3<0或
q4<0,若满足,则该直线段不在窗口内,算法转 (7)。
否则,满足 q1>0且 q2>0,则进一步 计算 u1和 u2。 算法转
(5)。
(4)若上述两条均不满足,则有 pk≠ 0（ k=1,2,3,4） 。 此时 计算 u1和 u2。
(5)求得 u1和 u2后,进行判断：若 u1>u2,则直线段在窗口外,算法转 (7)。 若 u1<u2,利用直线的参数方程求得直线段在窗口内的两端点坐标 。
(6)利用直线的扫描转换算法绘制在窗口内的直线段 。 算窗口
B(-2,-1)
A(3,3)
x
y
x=3+u·(-2-3)
y=3+u·(-1-3) 0 ≤ u ≤ 1
即：
x=3-5u
y=3-4u
这里：
wxl=0,wxr=2
wyb=0,wyt=2
（ 0 ≤ u ≤ 1 ）
解：
直线段 AB的参数方程为：
p1 = x1-x2=5>0
p2 = x2-x1 =-5<0
p3 = y1-y2 =4>0
p4 = y2-y1 =-4<0 可见 P均不为 0
因此：
q1 = x1 – wxl=3
q2 = wxr – x1=-1
q3 = y1 – wyb=3
q4 = wyt – y1=-1
1、试用 liang-barsky算法裁剪图中的线段 AB。
由于有：
p1,p3大于 0,p2,p4小于 0
Uone=max(0,uk|pk<0,uk|pk<0)
Utwo=min(1,uk|pk>0,uk|pk>0)
因此：
Uone=max(0,u2,u4)=max(0,0.2,0.25)=0.25
Utwo=min(1,u1,u3)=min(1,0.6,0.75)=0.6
可见 Uone<Utwo,它们分别对应输出直线段的起点和终点由于有,x=3-5u
y=3-4u
因此：
Uone对应的交点为（ 1.75,2）,Utwo对应的交点为 (0,0.6)
裁剪后输出线段的端点即为 I（ 1.75,2） 和 J(0,0.6)。
直线段与窗口边界的交点计算如下：
uk·pk=qk k=1,2,3,4
U1=0.6,U2=0.2,U1=0.0.75,U1=0,25 窗口
P2(-2,-1)
P1(3,3)
x
y
p1 = x1-x2=5>0
p2 = x2-x1 =-5<0
p3 = y1-y2 =4>0
p4 = y2-y1 =-4<0
q1 = x1 – wxl=3
q2 = wxr – x1=-1
q3 = y1 – wyb=3
q4 = wyt – y1=-1
I（ 1.75,2）
J(0,0.6)
2、试用中点 Bresenham算法扫描转换一条连接两点（ 0,0）
和（ 8,5）的直线段。
o x
y 解法见书 5.1.2后的例题！
如果两点变为（ 0,0）和（ 5,8）的直线段，可以怎样做？
o x
解,Δ x=x2-x1=8-0=8
Δ y=y2-y1=5-0=5
直线斜率 k= Δ y / Δ yx = 5/8，
满足 0≤ k≤1,
所以每次 x增加 1，求 y的值。
d的初始值为 Δ x-2Δ y=8-2*5=-2
往右上方的增量为 2Δ x-2Δ y=6
往正右方的增量为 -2Δ y=-10
初始点为（ 0,0）
由于 d<0时,y向上走一步；
否则 y不变因此，扫描转换的过程如右表所示：
x y d x y d
0 0 -2 5 3 -4
1 1 4 6 4 2
2 1 -6 7 4 -8
3 2 0 8 5 -2
4 2 -10
y
1 2 3 4 5 6 7 8
5
4
3
2
1
2、试用中点 Bresenham算法扫描转换一条连接两点（ 0,0）和（ 8,5）的直线段。
3、试用改进的 Bresenham算法画直线段的原理推导斜率为大 1
的直线段的扫描转换算法，并对算法进行优化。
d
d
d
d
m
m
m
m yi+1 = yi + 1
xi+1 = xi + 1 d>0.5x
i d≤0.5
证明,k>1,Δ x < Δ y,y方向为最大位移方向因此,y每次向上走一步，求 x的值。
如果判别式为左图中所示的 d,则有：
d的初值为 0；
y每走一步,d增加 m,m=1/k；
一旦 x向前走了一步，将 d减 1。
由此可写出算法的基本步骤,
1.输入直线的两端点 P0(x0,y0)和 P1(x1,y1)。
2.计算初始值 △ x,△ y,d=0,x=x0,y=y0。
3.绘制点 (x,y)。
4.d更 新为 d+m,判断 d 的符 号 。 若 d>0.5,则 (x,y)更新为
(x+1,y+1),同时将 d更新为 d-1； 否则 (x,y)更新为 (x,y+1)。
5.当直线没有画完时,重复步骤 3和 4。 否则结束 。
影响此算法效率的主要原因是存在浮点数及浮点数与 0.5的大小比较，为消除这些不利因素的影响，可进行如下优化：
优化 1：令 e = d - 0.5
yi+1 = yi + 1
xi+1 = xi + 1 e>0x
i e≤0
e初 =-0.5，
每走一步有 e=e+m。
if (e>0) then e=e-1
改进 2：用 2e△ y来替换 e
e初 =-△ y，
每走一步有 e=e+2△ x。
if (e>0) then e=e-2△ y
最终得到了一个整数的算法 。
影响此算法效率的主要原因是存在浮点数及浮点数与 0.5的大小比较，为消除这些不利因素的影响，可进行如下优化：
优化后的算法步骤：
1.输入直线的两端点 P0(x0,y0)和 P1(x1,y1)。
2.计算初始值 △ x,△ y,e=-△ y,x=x0,y=y0。
3.绘制点 (x,y)。
4.e更新为 e+2△ x,判断 e的符号 。 若 e>0,则 (x,y)更新为
(x+1,y+1),同时将 e更新为 e-2△ y； 否则 (x,y)更新为
(x,y+1)。
5.当直线没有画完时,重复步骤 3和 4。 否则结束 。
4、求将图中的空间四面体进行如下变换的变换矩阵，写出复合变换后图形各顶点的规范化齐次坐标，并画出符合变换后的图形。
（ 1）关于点 P整体放大 2倍；
（ 2）关于 y轴进行对称变换。
C(0,2,0)
A(2,0,0)
B(2,2,0)
D(2,2,2)
y
x
z
P(2,-2,2)
解：
（ 1）分为 3次基本变换：平移、整体放大、反向平移
①平移,Tx=-2,Ty=2,Tz=-2
T1=
② 整体放大,S=1/2 ③ 反向平移,Tx=2,Ty=-2,Tz=2
T2= T3=
1 0 0 0
0 1 0 0
0 0 1 0
-2 2 -2 1
C(0,2,0)
A(2,0,0)
B(2,2,0)
D(2,2,2)
y
x
z
P(2,-2,2)
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 0.5
1 0 0 0
0 1 0 0
0 0 1 0
2 -2 2 1
T= T1·T2·T3= · · =
1 0 0 0
0 1 0 0
0 0 1 0
-2 2 -2 1
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 0.5
1 0 0 0
0 1 0 0
0 0 1 0
2 -2 2 1
1 0 0 0
0 1 0 0
0 0 1 0
-1 1 -1 0.5
C(0,2,0)
A(2,0,0)
B(2,2,0)
D(2,2,2)
y
x
z
P(2,-2,2)
四面体 ABCD的齐次坐标表示矩阵为：
2 0 0 1 A
2 2 0 1 B
0 2 0 1 C
2 2 2 1 D
P=
2 0 0 1
2 2 0 1
0 2 0 1
2 2 2 1
P’=P·T= · =
1 0 0 0
0 1 0 0
0 0 1 0
-1 1 -1 0.5
1 1 -1 0.5 A’
1 3 -1 0.5 B’
-1 3 -1 0.5 C’
1 3 1 0.5 D’
四面体 ABCD各顶点变换后的齐次坐标为：
A(1,1,-1,0.5),B(1,3,-1,0.5),C(-1,3,-1,0.5),D(1,3,1,0.5)
规范化的齐次坐标为：
A(2,2,-2,1),B(2,6,-2,1),C(-2,6,-2,1),D(2,6,2,1)
变换后各点的坐标为：
A(2,2,-2),B(2,6,-2),C(-2,6,-2),D(2,6,2)
C(0,2,0)
A(2,0,0)
B(2,2,0)
D(2,2,2)
y
x
z
P(2,-2,2) C(-2,6,-2)
A(2,2,-2)
B(2,6,-2)
D(2,6,2)
y
x
z
变换后各点的坐标为：
A(2,2,-2),B(2,6,-2),C(-2,6,-2),D(2,6,2)
图形如下（ b） 所示：
P(2,-2,2)
（ b）（ a）
5、试证明一个均匀比例（ Sx=Sy） 和一个旋转变换是一个可交换对。
证明：即需要证明这两个变换的变换矩阵的乘积满足交换率。
均匀比例变换的变换矩阵为：
Ts =
旋转变换的变换矩阵为：
Tr =
S 0 0
0 S 0
0 0 1
cosθ sinθ 0
-sinθ cosθ 0
0 0 1
T2=Tr·Ts = · =
S 0 0
0 S 0
0 0 1
cosθ sinθ 0
-sinθ cosθ 0
0 0 1
s·cosθ s·sinθ 0
-s·sinθ s·cosθ 0
0 0 1
T1=Ts·Tr = · =
S 0 0
0 S 0
0 0 1
cosθ sinθ 0
-sinθ cosθ 0
0 0 1
s·cosθ s·sinθ 0
-s·sinθ s·cosθ 0
0 0 1
如果先作比例变换再作旋转变换，复合变换的变换矩阵为 T1,
如果先作旋转变换再作比例变换，复合变换的变换矩阵为 T2,
T1 =T2,因此可 证明一个均匀比例（ Sx=Sy） 和一个旋转变换是一个可交换对。
6、如下图所示多边形，若采用扫描转换算法（ ET边表算法）
进行填充，试写出该多边形的 ET表和当扫描线 Y=2时的有效边表 AET表（活性边表），并说明在该处的填充区间。
x
y
21 3 4 5 6 7 8 9 11
1
2
3
4
5
6
7
8
9
10
11
12
10 12
p 1
p 3
p 4
p 5
( a ) 多边形P 0 P 1 P 2 P 3 P 4 P 5 P 6 P 0
p 2
p 0 p 6
1
2
3
4
5
6
7
8
9
10
11
12
3 -1/3 3 5 3/4 8 5 -1/2 8 9 1/2
1 12 2/5
7 12 -1 7 9 5
桶
p 3 p 2 p 3 p 4 p 5 p 4 p 5 p6
p 2 p 1
p 0 p 1 p 0 p6
x|y min ymax 1/k next
( c ) 边表
6
解：
边表的纵向链表长度为多边形所占有的最大扫描线数 12；
共有 7条边，每条边的数据形成一个结点，链入与该边最小 y坐标相对应的桶处。
由此，可写出该多边形的 ET表，如下图所示：
x
y
21 3 4 5 6 7 8 9 11
1
2
3
4
5
6
7
8
9
10
11
12
10 12
p 1
p 3
p 4
p 5
( a ) 多边形P 0P 1P 2P 3P 4P 5P 6P 0
p 2
p 0 p 6
当扫描线 Y=1时的有效边表 AET表（活性边表）如下：
可见，这 4个节点在扫描线 Y=2时仍为有效边，且在扫描线 Y=2处没有新边出现，
因此，扫描线 Y=2时的有效边表 AET表（活性边表）如下：
x
y
21 3 4 5 6 7 8 9 11
1
2
3
4
5
6
7
8
9
10
11
12
10 12
p 1
p 3
p 4
p 5
( a ) 多边形P 0P 1P 2P 3P 4P 5P 6P 0
p 2
p 0 p 6
在扫描线 Y=2的交点按序为,（ 8/3,2）（ 3.75,2）（ 7.5,2）（ 8.5,2）
真正的交点序列为,（ 3,2）（ 4,2）（ 8,2）（ 9,2）
填色区间为,（ 3,2）和（ 4,2）之间，（ 8,2）和（ 9,2）之间。
补充说明：
（ 1）水平线的处理：
进行说明，表明不用考虑且不会影响结果
（ 2）垂直线的处理：
与一般直线段统一处理，只是 m=1/k=0
7、名词解释：字符精度文字剪裁字符精度字符剪裁是一种舍弃不完全落在窗口内的字符的一种文字裁剪方法，如图所示：
Computer
graph
mpute
graph
（ a） 裁剪前 （ b） 裁剪后
`2
w
级D A C
帧缓冲存储器
C R T 光栅电子抢
n
w 位查找表
2
n
表项
2
w
为总光强等级
2
n
为每次可显示的光强等级图2 - 2 8 具有N 位帧缓存和W 位颜色查找表的光栅显示器
8、填空如果分辨率为 1024*768，能同时显示的颜色数为 256，颜色查找表位数为 10，则颜色位面数为,帧缓存大小为 KB,
总的颜色数为 。
草稿上计算：
（ 1）颜色位面数：
log2n=log2256=8
（ 2）帧缓存：
每位面大小 *位面数
=1024*768*8（ bit）
=1024*768(Byte)=768(KB)
（ 3）总颜色数：
2w= 210 =1024
B(-2,-1)
A(3,3)
x
y
1、试用 liang-barsky算法裁剪图中的线段 AB。
3,Liang-Barsky算法分析,P1(x1,y1)和 P2(x2,y2)
将线段看成由方向性：外到内 内到外
p1
p2
p1
p1
左 右下上
3,Liang-Barsky算法
x=x1+u·(x2-x1)
y=y1+u·(y2-y1) 0 ≤ u ≤ 1
任意直线段 I（ X1,Y1） J(X2,Y2)的参数方程：
x
y
o
wyt
wyb
wxl wxr
窗口给定裁剪窗口：
3,Liang-Barsky算法
wxl≤ x1+u·(x2-x1) ≤ wxr
wyb≤ y1+u·(y2-y1) ≤ wyt
u·(x1-x2) ≤ x1 – wxl 左边界
u·(x2-x1) ≤ wxr – x1 右边界
u·(y1-y2) ≤ y1 – wyb 下边界
u·(y2-y1) ≤ wyt – y1 上边界
p1 = x1-x2
p2 = x2-x1
p3 = y1-y2
p4 = y2-y1
令：
q1 = x1 – wxl
q2 = wxr – x1
q3 = y1 – wyb
q4 = wyt – y1
u·pk≤q k k=1,2,3,4
如果任一点（）在窗口内则：
取,=” 时求得的 u对应的是直线与窗口边界的交点
1,2,3,4分别对应左、右、下、上边界
U=0和 1时分别对应直线的起点和中点
x
y
o
wyt
wyb
wxl wxr
窗口裁剪后的两端点是哪些点？
分析：裁剪的本质
Uone=max(0,uk|pk<0,uk|pk<0)
Utwo=min(1,uk|pk>0,uk|pk>0)
I1 J
1
对于 I1J1
P1,P4小于 0 U在 0,U1,U4取大者
P2,P3大于 0 U在 1,U2,U3取小者如果 Uone≤ Utwo取可求得两端点左 p1 = x1-x2
右 p2 = x2-x1
下 p3 = y1-y2
上 p4 = y2-y1
q1 = x1 – wxl
q2 = wxr – x1
q3 = y1 – wyb
q4 = wyt – y1
假定 PK不为 0
左 p1 = x1-x2
右 p2 = x2-x1
下 p3 = y1-y2
上 p4 = y2-y1
q1 = x1 – wxl
q2 = wxr – x1
q3 = y1 – wyb
q4 = wyt – y1如果 U
one>Utwo表明什么？
P1,P3小于 0 U在 0,U1,U3取大者
P2,P4大于 0 U在 1,U2,U4取小者
Uone=max(0,uk|pk<0,uk|pk<0)
Utwo=min(1,uk|pk>0,uk|pk>0)
I1
J1
特殊处理：
(a) 直线段与窗口边界
wxl 和wxr 平行的情况
(b) 直线段与窗口边界
wyb 和wyt 平行的情况
wyt
wyb
wxl wxr wxrwxl
wyb
wyt
A
B
C
D
E
F
G
H I
J
K
L
PK为 0
p1=p2=0 p3=p4=0Uone=max(0,uk|pk<0)U
two=min(1,uk|pk>0)
左 p1 = x1-x2
右 p2 = x2-x1
下 p3 = y1-y2
上 p4 = y2-y1
q1 = x1 – wxl
q2 = wxr – x1
q3 = y1 – wyb
q4 = wyt – y1
算法步骤,
(1)输入直线段的两端点坐标,(x1,y1)和 (x2,y2),以及窗口的四条边界坐标,wyt,wyb,wxl和 wxr。
(2)若 Δx= 0,则 p1=p2=0。 此时进一步判断是否满足 q1<0或
q2<0,若满足,则该直线段不在窗口内,算法转 (7)。
否则,满足 q1>0且 q2>0,则进一步 计算 u1和 u2。 算法转
(5)。
(3)若 Δy= 0,则 p3=p4=0。 此时进一步判断是否满足 q3<0或
q4<0,若满足,则该直线段不在窗口内,算法转 (7)。
否则,满足 q1>0且 q2>0,则进一步 计算 u1和 u2。 算法转
(5)。
(4)若上述两条均不满足,则有 pk≠ 0（ k=1,2,3,4） 。 此时 计算 u1和 u2。
(5)求得 u1和 u2后,进行判断：若 u1>u2,则直线段在窗口外,算法转 (7)。 若 u1<u2,利用直线的参数方程求得直线段在窗口内的两端点坐标 。
(6)利用直线的扫描转换算法绘制在窗口内的直线段 。 算窗口
B(-2,-1)
A(3,3)
x
y
x=3+u·(-2-3)
y=3+u·(-1-3) 0 ≤ u ≤ 1
即：
x=3-5u
y=3-4u
这里：
wxl=0,wxr=2
wyb=0,wyt=2
（ 0 ≤ u ≤ 1 ）
解：
直线段 AB的参数方程为：
p1 = x1-x2=5>0
p2 = x2-x1 =-5<0
p3 = y1-y2 =4>0
p4 = y2-y1 =-4<0 可见 P均不为 0
因此：
q1 = x1 – wxl=3
q2 = wxr – x1=-1
q3 = y1 – wyb=3
q4 = wyt – y1=-1
1、试用 liang-barsky算法裁剪图中的线段 AB。
由于有：
p1,p3大于 0,p2,p4小于 0
Uone=max(0,uk|pk<0,uk|pk<0)
Utwo=min(1,uk|pk>0,uk|pk>0)
因此：
Uone=max(0,u2,u4)=max(0,0.2,0.25)=0.25
Utwo=min(1,u1,u3)=min(1,0.6,0.75)=0.6
可见 Uone<Utwo,它们分别对应输出直线段的起点和终点由于有,x=3-5u
y=3-4u
因此：
Uone对应的交点为（ 1.75,2）,Utwo对应的交点为 (0,0.6)
裁剪后输出线段的端点即为 I（ 1.75,2） 和 J(0,0.6)。
直线段与窗口边界的交点计算如下：
uk·pk=qk k=1,2,3,4
U1=0.6,U2=0.2,U1=0.0.75,U1=0,25 窗口
P2(-2,-1)
P1(3,3)
x
y
p1 = x1-x2=5>0
p2 = x2-x1 =-5<0
p3 = y1-y2 =4>0
p4 = y2-y1 =-4<0
q1 = x1 – wxl=3
q2 = wxr – x1=-1
q3 = y1 – wyb=3
q4 = wyt – y1=-1
I（ 1.75,2）
J(0,0.6)
2、试用中点 Bresenham算法扫描转换一条连接两点（ 0,0）
和（ 8,5）的直线段。
o x
y 解法见书 5.1.2后的例题！
如果两点变为（ 0,0）和（ 5,8）的直线段，可以怎样做？
o x
解,Δ x=x2-x1=8-0=8
Δ y=y2-y1=5-0=5
直线斜率 k= Δ y / Δ yx = 5/8，
满足 0≤ k≤1,
所以每次 x增加 1，求 y的值。
d的初始值为 Δ x-2Δ y=8-2*5=-2
往右上方的增量为 2Δ x-2Δ y=6
往正右方的增量为 -2Δ y=-10
初始点为（ 0,0）
由于 d<0时,y向上走一步；
否则 y不变因此，扫描转换的过程如右表所示：
x y d x y d
0 0 -2 5 3 -4
1 1 4 6 4 2
2 1 -6 7 4 -8
3 2 0 8 5 -2
4 2 -10
y
1 2 3 4 5 6 7 8
5
4
3
2
1
2、试用中点 Bresenham算法扫描转换一条连接两点（ 0,0）和（ 8,5）的直线段。
3、试用改进的 Bresenham算法画直线段的原理推导斜率为大 1
的直线段的扫描转换算法，并对算法进行优化。
d
d
d
d
m
m
m
m yi+1 = yi + 1
xi+1 = xi + 1 d>0.5x
i d≤0.5
证明,k>1,Δ x < Δ y,y方向为最大位移方向因此,y每次向上走一步，求 x的值。
如果判别式为左图中所示的 d,则有：
d的初值为 0；
y每走一步,d增加 m,m=1/k；
一旦 x向前走了一步，将 d减 1。
由此可写出算法的基本步骤,
1.输入直线的两端点 P0(x0,y0)和 P1(x1,y1)。
2.计算初始值 △ x,△ y,d=0,x=x0,y=y0。
3.绘制点 (x,y)。
4.d更 新为 d+m,判断 d 的符 号 。 若 d>0.5,则 (x,y)更新为
(x+1,y+1),同时将 d更新为 d-1； 否则 (x,y)更新为 (x,y+1)。
5.当直线没有画完时,重复步骤 3和 4。 否则结束 。
影响此算法效率的主要原因是存在浮点数及浮点数与 0.5的大小比较，为消除这些不利因素的影响，可进行如下优化：
优化 1：令 e = d - 0.5
yi+1 = yi + 1
xi+1 = xi + 1 e>0x
i e≤0
e初 =-0.5，
每走一步有 e=e+m。
if (e>0) then e=e-1
改进 2：用 2e△ y来替换 e
e初 =-△ y，
每走一步有 e=e+2△ x。
if (e>0) then e=e-2△ y
最终得到了一个整数的算法 。
影响此算法效率的主要原因是存在浮点数及浮点数与 0.5的大小比较，为消除这些不利因素的影响，可进行如下优化：
优化后的算法步骤：
1.输入直线的两端点 P0(x0,y0)和 P1(x1,y1)。
2.计算初始值 △ x,△ y,e=-△ y,x=x0,y=y0。
3.绘制点 (x,y)。
4.e更新为 e+2△ x,判断 e的符号 。 若 e>0,则 (x,y)更新为
(x+1,y+1),同时将 e更新为 e-2△ y； 否则 (x,y)更新为
(x,y+1)。
5.当直线没有画完时,重复步骤 3和 4。 否则结束 。
4、求将图中的空间四面体进行如下变换的变换矩阵，写出复合变换后图形各顶点的规范化齐次坐标，并画出符合变换后的图形。
（ 1）关于点 P整体放大 2倍；
（ 2）关于 y轴进行对称变换。
C(0,2,0)
A(2,0,0)
B(2,2,0)
D(2,2,2)
y
x
z
P(2,-2,2)
解：
（ 1）分为 3次基本变换：平移、整体放大、反向平移
①平移,Tx=-2,Ty=2,Tz=-2
T1=
② 整体放大,S=1/2 ③ 反向平移,Tx=2,Ty=-2,Tz=2
T2= T3=
1 0 0 0
0 1 0 0
0 0 1 0
-2 2 -2 1
C(0,2,0)
A(2,0,0)
B(2,2,0)
D(2,2,2)
y
x
z
P(2,-2,2)
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 0.5
1 0 0 0
0 1 0 0
0 0 1 0
2 -2 2 1
T= T1·T2·T3= · · =
1 0 0 0
0 1 0 0
0 0 1 0
-2 2 -2 1
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 0.5
1 0 0 0
0 1 0 0
0 0 1 0
2 -2 2 1
1 0 0 0
0 1 0 0
0 0 1 0
-1 1 -1 0.5
C(0,2,0)
A(2,0,0)
B(2,2,0)
D(2,2,2)
y
x
z
P(2,-2,2)
四面体 ABCD的齐次坐标表示矩阵为：
2 0 0 1 A
2 2 0 1 B
0 2 0 1 C
2 2 2 1 D
P=
2 0 0 1
2 2 0 1
0 2 0 1
2 2 2 1
P’=P·T= · =
1 0 0 0
0 1 0 0
0 0 1 0
-1 1 -1 0.5
1 1 -1 0.5 A’
1 3 -1 0.5 B’
-1 3 -1 0.5 C’
1 3 1 0.5 D’
四面体 ABCD各顶点变换后的齐次坐标为：
A(1,1,-1,0.5),B(1,3,-1,0.5),C(-1,3,-1,0.5),D(1,3,1,0.5)
规范化的齐次坐标为：
A(2,2,-2,1),B(2,6,-2,1),C(-2,6,-2,1),D(2,6,2,1)
变换后各点的坐标为：
A(2,2,-2),B(2,6,-2),C(-2,6,-2),D(2,6,2)
C(0,2,0)
A(2,0,0)
B(2,2,0)
D(2,2,2)
y
x
z
P(2,-2,2) C(-2,6,-2)
A(2,2,-2)
B(2,6,-2)
D(2,6,2)
y
x
z
变换后各点的坐标为：
A(2,2,-2),B(2,6,-2),C(-2,6,-2),D(2,6,2)
图形如下（ b） 所示：
P(2,-2,2)
（ b）（ a）
5、试证明一个均匀比例（ Sx=Sy） 和一个旋转变换是一个可交换对。
证明：即需要证明这两个变换的变换矩阵的乘积满足交换率。
均匀比例变换的变换矩阵为：
Ts =
旋转变换的变换矩阵为：
Tr =
S 0 0
0 S 0
0 0 1
cosθ sinθ 0
-sinθ cosθ 0
0 0 1
T2=Tr·Ts = · =
S 0 0
0 S 0
0 0 1
cosθ sinθ 0
-sinθ cosθ 0
0 0 1
s·cosθ s·sinθ 0
-s·sinθ s·cosθ 0
0 0 1
T1=Ts·Tr = · =
S 0 0
0 S 0
0 0 1
cosθ sinθ 0
-sinθ cosθ 0
0 0 1
s·cosθ s·sinθ 0
-s·sinθ s·cosθ 0
0 0 1
如果先作比例变换再作旋转变换，复合变换的变换矩阵为 T1,
如果先作旋转变换再作比例变换，复合变换的变换矩阵为 T2,
T1 =T2,因此可 证明一个均匀比例（ Sx=Sy） 和一个旋转变换是一个可交换对。
6、如下图所示多边形，若采用扫描转换算法（ ET边表算法）
进行填充，试写出该多边形的 ET表和当扫描线 Y=2时的有效边表 AET表（活性边表），并说明在该处的填充区间。
x
y
21 3 4 5 6 7 8 9 11
1
2
3
4
5
6
7
8
9
10
11
12
10 12
p 1
p 3
p 4
p 5
( a ) 多边形P 0 P 1 P 2 P 3 P 4 P 5 P 6 P 0
p 2
p 0 p 6
1
2
3
4
5
6
7
8
9
10
11
12
3 -1/3 3 5 3/4 8 5 -1/2 8 9 1/2
1 12 2/5
7 12 -1 7 9 5
桶
p 3 p 2 p 3 p 4 p 5 p 4 p 5 p6
p 2 p 1
p 0 p 1 p 0 p6
x|y min ymax 1/k next
( c ) 边表
6
解：
边表的纵向链表长度为多边形所占有的最大扫描线数 12；
共有 7条边，每条边的数据形成一个结点，链入与该边最小 y坐标相对应的桶处。
由此，可写出该多边形的 ET表，如下图所示：
x
y
21 3 4 5 6 7 8 9 11
1
2
3
4
5
6
7
8
9
10
11
12
10 12
p 1
p 3
p 4
p 5
( a ) 多边形P 0P 1P 2P 3P 4P 5P 6P 0
p 2
p 0 p 6
当扫描线 Y=1时的有效边表 AET表（活性边表）如下：
可见，这 4个节点在扫描线 Y=2时仍为有效边，且在扫描线 Y=2处没有新边出现，
因此，扫描线 Y=2时的有效边表 AET表（活性边表）如下：
x
y
21 3 4 5 6 7 8 9 11
1
2
3
4
5
6
7
8
9
10
11
12
10 12
p 1
p 3
p 4
p 5
( a ) 多边形P 0P 1P 2P 3P 4P 5P 6P 0
p 2
p 0 p 6
在扫描线 Y=2的交点按序为,（ 8/3,2）（ 3.75,2）（ 7.5,2）（ 8.5,2）
真正的交点序列为,（ 3,2）（ 4,2）（ 8,2）（ 9,2）
填色区间为,（ 3,2）和（ 4,2）之间，（ 8,2）和（ 9,2）之间。
补充说明：
（ 1）水平线的处理：
进行说明，表明不用考虑且不会影响结果
（ 2）垂直线的处理：
与一般直线段统一处理，只是 m=1/k=0
7、名词解释：字符精度文字剪裁字符精度字符剪裁是一种舍弃不完全落在窗口内的字符的一种文字裁剪方法，如图所示：
Computer
graph
mpute
graph
（ a） 裁剪前 （ b） 裁剪后
`2
w
级D A C
帧缓冲存储器
C R T 光栅电子抢
n
w 位查找表
2
n
表项
2
w
为总光强等级
2
n
为每次可显示的光强等级图2 - 2 8 具有N 位帧缓存和W 位颜色查找表的光栅显示器
8、填空如果分辨率为 1024*768，能同时显示的颜色数为 256，颜色查找表位数为 10，则颜色位面数为,帧缓存大小为 KB,
总的颜色数为 。
草稿上计算：
（ 1）颜色位面数：
log2n=log2256=8
（ 2）帧缓存：
每位面大小 *位面数
=1024*768*8（ bit）
=1024*768(Byte)=768(KB)
（ 3）总颜色数：
2w= 210 =1024
