图形学 chap5
第五章 基本图形生成算法
*
*
如何在指定的输出设备上根据坐标描述构造基本二维几何图形（点、直线、圆、椭圆、多边形域、字符串及其相关属性等）。
第五章 习题讲解与部分知识点复习
*
P149 5.2 p1(0,0); p2(8,6)
1. 数值微分法(DDA法)
直线的微分方程：
ε=1/max(|△x|,|△y|)
图5.2 DDA算法原理
*
1999年7月07/16/96
*
*##
max(|△x|,|△y|)=|△x|，即|k|≤1的情况：
max(|△x|,|△y|)=|△y|，此时|k|≥1：
k=(6-0)/(8-0)=6/8, 此时|k|<1
x 0 1 2 3 4 5 6 7 8
y 0 1 2 2 3 4 5 5 6
*
2.中点Bresenham算法
输入直线的两端点P0(x0,y0)和P1(x1,y1)。
计算初始值△x、△y、D=△x-2△y、x=x0、y=y0。
绘制点(x,y)。判断D的符号。若D<0，则(x,y)更新为(x+1,y+1)，D更新为D+2△x-2△y；否则(x,y)更新为(x+1,y), D更新为D-2△y。
当直线没有画完时，重复上一步骤，否则结束。
P149 5.2 p1(0,0); p2(8,6)
x 0 1 2 3 4 5 6 7 8
y 0 1 1 2 3 4 4 5 6
d -4 0 -12 -8 -4 0 -12 -8 -4
*
3.改进的Bresenham算法
1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。
2.计算初始值△x、△y、e=-△x、x=x0、y=y0。
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。否则结束。
P149 5.2 p1(0,0); p2(8,6)
x 0 1 2 3 4 5 6 7 8
y 0 1 1 2 3 4 4 5 6
e -8 -12 0 -4 -8 -12 0 -4 -8
e+2△y 4 0 12 8 4 0 12 8 —–
复习：中点Bresenham画圆——算法步骤
1.输入圆的半径R。
2.计算初始值d=1-R、x=0、y=R。
3.绘制点(x,y)及其在八分圆中的另外七个对称点。
4.判断d的符号。若d<0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。
5.当x
PR
2
3
1
A(3,3)
B(-1,-2)
图6-40
④交换，使得A’ -> B’(2,7/4)、0000；
B->A’’(-1,-2)、0101
⑤根据codeA’’的从低到高寻找编码位为1所对应的窗口边界为左边界，求A’’B’与左边界的交点PL(0,-3/4)。
令PL->A’’’(0,-3/4)，codeA’’’=0100，并用A’’’代替A’’
⑥根据codeA’’’的从低到高寻找编码位为1所对应的窗口边界为底边界，求A’’’B’与底边界的交点PB(3/5,0)。
令PB->A’’’’(3/5,0)，codeA’’’’=0000，并用A’’’’代替A’’’
⑦至此，裁剪结束，求得裁剪线段为：(2,7/4),(3/5,0)
⑧四舍五入后，裁剪线段为：(2,2),(1,0)
2
3
1
A’’(-1,-2)
B’(2,7/4)
PL
2
3
1
A’’’’(3/5,0)
B’(2,7/4)
2
3
1
A’’’(0,-3/4)
B’(2,7/4)
PB
习题6.13/P183
6.13 试用中点分隔算法裁剪如图6-40的线段，分隔一直到误差小于0.5为止。
codeA=1010，codeB=0101
中点Pm( (x1+x2)/2,(y1+y2)/2)
求A的最远可见点
①∵codeB0 ∴B不在窗口内
②∵codeA&codeB=0 ∴AB不在窗口同一外侧
③用二分法求AB中点Pm( 1,1/2)、0000。
④∵Pm在窗口内，令Pm->A’(1,1/2)、0000，并用A’代替A
2
3
1
A(3,3)
B(-1,-2)
图6-40
Pm
⑤用二分法求A’B中点Pm( 0,-3/4)、0100。
⑥∵Pm在窗口外，codePm&codeB0 ∴PmB在窗口同一外侧，∴令Pm->B’(0,-3/4)、0100，并用B’代替B
⑦用二分法求A’B’中点Pm( 1/2,-1/8)、0100。
⑧同理，令Pm->B’’(1/2,-1/8)、0100，并用B’’代替B
⑨用二分法求A’B’’中点Pm( 3/4,3/16)、0100。
⑩分析Pm和B’’的误差小于0.5，则不再分隔。四舍五入得B’’’(1,0)、0000，为A的最远可见点。
Pm
2
3
1
A’(1,1/2)
B(-1,-2)
A
Pm
2
3
1
A’(1,1/2)
B
A
B’(0,-3/4)
Pm
A’(1,1/2)
B
A
B’’(1/2,-1/8)
B
A
B’’’(1,0)
codeA=1010，codeB=0101
中点Pm( (x1+x2)/2,(y1+y2)/2)
求B的最远可见点
①∵codeA0 ∴A不在窗口内
②∵codeA&codeB=0 ∴AB不在窗口同一外侧
③用二分法求AB中点Pm( 1,1/2)、0000。
④∵Pm在窗口内，令Pm->B’(1,1/2)、0000，并用B’代替B
⑤用二分法求AB’中点Pm( 2,7/4)、0000。
⑥∵Pm在窗口内，∴令Pm->B’’(2,7/4)、0000，并用B’’代替B
2
3
1
A(3,3)
B(-1,-2)
图6-40
Pm
2
3
1
A(3,3)
B’(1,1/2)
Pm
⑥用二分法求AB’’中点Pm( 5/2,19/8)、1010。
⑦∵Pm在窗口外，codePm&codeA0 ∴PmA在窗口同一外侧，∴令Pm->A’(5/2,19/8)、1010，并用A’代替A
⑧用二分法求A’B’’中点Pm( 9/4,33/16)、1010。
⑨分析Pm和A’的误差小于0.5，则不再分隔。四舍五入得A’’(2,2)、0000，为B的最远可见点。
⑩至此，裁剪结束，求得裁剪线段为：(2,2),(1,0)
2
3
1
A(3,3)
B’’(2,7/4)
Pm
2
3
1
A’(5/2,19/8)
B’’(2,7/4)
Pm
习题6.14/P183
6.14 试用Liang-Barsky算法裁剪如图6-40的线段。
P1=-(-x2-x1)=-(-1-3)=4；q1=x1-xWL=3-0=3；
P2=x2-x1=-1-3=-4； q2=xWR-x1=2-3=-1；
P3=-(-y2-y1)=-(-2-3)=5；q3=y1-yWB=3-0=3；
P4=y2-y1=-2-3=-5； q4=yWT-y1=2-3=-1；
①∵Pi0 ∴不存在直线与窗口边界的平行
Umax
Umin
2
3
1
A(3,3)
B(-1,-2)
图6-40
Pm
1
2
3
4
1/5
P4<0,进入
4:上
3/5
P3>0,出去
3:下
1/4
P2<0,进入
2:右
3/4
p1>0,出去
1:左
U(=qi/pi)
AB
边界
Umax
3:下
1/4
P2<0,进入
2:右
3/4
p1>0,出去
1:左
U(=qi/pi)
AB
边界
Umax