2013-3-1 华中理工大学计算机学院 陆枫
99-7
1
第 6章 二维变换及二维观察
提出问题
? 如何对二维图形进行方向, 尺寸和形状方面的变换
? 如何方便地实现在显示设备上对二维图形进行观察
2013-3-1 华中理工大学计算机学院 陆枫
99-7
2
第 6章 二维变换及两维观察
6.1 基本概念
6.1.1 齐次坐标
? 齐次坐标表示 就是用 n+1维向量表示一个 n维向量 。
? 齐次坐标的不唯一性
? 规范化齐次坐标表示 就是 h=1的齐次坐标表示 。
? 如何从齐次坐标转换到规范化齐次坐标？
2013-3-1 华中理工大学计算机学院 陆枫
99-7
3
6.1.2 几何变换
图形的 几何变换 是指对图形的几何信息经过平移, 比
例, 旋转等变换后产生新的图形, 是图形在方向,
尺寸和形状方面的变换 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
4
6.1.3 二维变换矩阵
? ? ? ? ? ?
?
?
?
?
?
?
?
?
?
?
????
sml
qdc
pba
yxTyxyx D 111'' 2
2013-3-1 华中理工大学计算机学院 陆枫
99-7
5
6.2 基本几何变换
基本几何变换都是 相对于坐标原点和坐标轴进行的
几何变换
6.2.1 平移变换
平移 是指将 p点沿直线路径从一个坐标位置移到另一
个坐标位置的重定位过程 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
6
平移是一种不产生变形而移动物体的刚体变换
（ rigid-body transformation）
Y
X
Tx
Ty
图6 - 1 平移变换
P'
P
T
2013-3-1 华中理工大学计算机学院 陆枫
99-7
7
Tx,Ty称为 平移矢量
?
?
?
?
?
?
?
?
?
?
1
010
001
yx
TT
推导,
矩阵,
2013-3-1 华中理工大学计算机学院 陆枫
99-7
8
6.2.2 比例变换
比例变换 是指对 p点相对于坐标原点沿 x方向放缩 Sx倍,
沿 y方向放缩 Sy倍 。 其中 Sx和 Sy称为 比例系数 。
Y
X
图6- 2 比 例变换(S x =2,S y =3 )
P ' ( 4,3 )
P ( 2,1 )
2013-3-1 华中理工大学计算机学院 陆枫
99-7
9
推导,
矩阵,
?
?
?
?
?
?
?
?
?
?
100
00
00
y
x
S
S
2013-3-1 华中理工大学计算机学院 陆枫
99-7
10
( a ) S x=S y比例
原图
( b ) S x<>Sy比例
原图
图6 - 3 比例变换
S x < S y
S x > S y
S x = S y > 1
S x = S y < 1
2013-3-1 华中理工大学计算机学院 陆枫
99-7
11
整体比例变换,
?
?
?
?
?
?
?
?
?
?
s00
010
001
2013-3-1 华中理工大学计算机学院 陆枫
99-7
12
6.2.3 旋转变换
二维旋转 是指将 p点绕坐标原点转动某个角度 （ 逆时针为
正, 顺时针为负 ） 得到新的点 p’的重定位过程 。
Y
X
图6 - 4 旋转变换
P'
P
r
r
α
θ
2013-3-1 华中理工大学计算机学院 陆枫
99-7
13
推导,
矩阵,逆时针旋转 θ角
?
?
?
?
?
?
?
?
?
?
?
100
0c o ss i n
0s i nc o s
??
??
顺时针旋转 θ角?
2013-3-1 华中理工大学计算机学院 陆枫
99-7
14
简化计算
? ? ? ?
?
?
?
?
?
?
?
?
?
?
???
100
01
01
11'' ?
?
yxyx
2013-3-1 华中理工大学计算机学院 陆枫
99-7
15
6.2.4 对称变换
对称变换 后的图形是原图形关于某一轴线或原点的镜像 。
X
Y
( a ) 关于x 轴对称
X
Y
(b)关 于y轴 对称
X
Y
( c ) 关于原点对称
2013-3-1 华中理工大学计算机学院 陆枫
99-7
16
X
Y
( d ) 关于x = y 对称
X
Y
(e)关 于x=-y 对称
2013-3-1 华中理工大学计算机学院 陆枫
99-7
17
(1)关于 x轴对称
?
?
?
?
?
?
?
?
?
?
?
100
010
001
Y
X
P'(x,-y)
P(x,y)
( a ) 关于x 轴对称
2013-3-1 华中理工大学计算机学院 陆枫
99-7
18
(2)关于 y轴对称
Y
X
P'(-x,y) p(x,y)
( b ) 关于y 轴对称
?
?
?
?
?
?
?
?
?
? ?
100
010
001
2013-3-1 华中理工大学计算机学院 陆枫
99-7
19
(3)关于原点对称
Y
X
P(x,y)
( c ) 关于原点对称
?
?
?
?
?
?
?
?
?
?
?
?
100
010
001
2013-3-1 华中理工大学计算机学院 陆枫
99-7
20
(4)关于 y=x轴对称
Y
X
p(x,y)
p'(y,x)
x=y
( d ) 关于x = y 对称
?
?
?
?
?
?
?
?
?
?
100
001
010
2013-3-1 华中理工大学计算机学院 陆枫
99-7
21
(5)关于 y=-x轴对称
Y
X
P'(-y,-x)
P(x,y)
x=-y
(e )关于 x= -y 对称
?
?
?
?
?
?
?
?
?
?
?
?
100
001
010
2013-3-1 华中理工大学计算机学院 陆枫
99-7
22
6.2.5 错切变换
错切变换, 也称为剪切, 错位变换, 用于产生弹性物
体的变形处理 。
Y
X
Y
X
Y
X
(a) 原 图 (b) 沿 x方 向错切
(c) 沿 y方 向错切
图6-7 错切变换
2013-3-1 华中理工大学计算机学院 陆枫
99-7
23
其变换矩阵为,
?
?
?
?
?
?
?
?
?
?
100
01
01
c
b
(1)沿 x方向错切
(2)沿 y方向错切
(3)两个方向错切
2013-3-1 华中理工大学计算机学院 陆枫
99-7
24
6.2.6 二维图形几何变换的计算
几何变换均可表示成 P’=P*T的形式
1,点的变换
2,直线的变换
3,多边形的变换
4,曲线的变换
2013-3-1 华中理工大学计算机学院 陆枫
99-7
25
6.3 复合变换
复合变换 是指,
? 图形作一次以上的几何变换, 变换结果是每次的变换矩
阵相乘 。
? 任何一复杂的几何变换都可以看作基本几何变换的组合
形式 。
复合变换具有形式,
)1(
)('
321
321
??????
???????
nTTTTP
TTTTPTPP
n
n
?
?
2013-3-1 华中理工大学计算机学院 陆枫
99-7
26
6.3.1 二维复合平移
两个连续平移是加性的 。
6.3.2 二维复合比例
连续比例变换是相乘的 。
6.3.3 二维复合旋转
两个连续旋转是相加的 。 可写为,
)( 21)()( 21 ???? ???? RRRR
2013-3-1 华中理工大学计算机学院 陆枫
99-7
27
6.3.4 其它二维复合变换
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?????
100
0c o s0
00c o s
100
01
01
100
01
01
100
0c o s0
00c o s
100
0 c o s s in
0 s inc o s
?
?
?
?
?
?
?
?
??
??
tg
tg
tg
tg
R
2013-3-1 华中理工大学计算机学院 陆枫
99-7
28
6.3.5 相对任一参考点的二维几何变换
相对某个参考点 (xF,yF)作二维几何变换, 其变换过程为,
(1) 平移
(2) 针对原点进行二维几何变换 。
(3) 反平移
例 1,相对点 (xF,yF)的旋转变换
例 2,相对点 (xF,yF)的比例变换
2013-3-1 华中理工大学计算机学院 陆枫
99-7
29
6.3.6 相对任意方向的二维几何变换
相对任意方向作二维几何变换, 其变换的过程是,
(1) 旋转变换
(2) 针对坐标轴进行二维几何变换；
(3) 反向旋转
例 3,相对直线 y=x的反射变换
2013-3-1 华中理工大学计算机学院 陆枫
99-7
30
例 4,将正方形 ABCO各点沿图 6-8所示的 (0,0)→( 1,1)方
向进行拉伸, 结果为如图所示的, 写出其变换矩阵和
变换过程 。
Y
X1 3/21/2
1/2
3/2
2
2
图6 - 8 针对固定方向的拉伸
O
A B
C
C'
B'
A'
2013-3-1 华中理工大学计算机学院 陆枫
99-7
31
6.3.7 坐标系之间的变换
问题,
图6 - 9 坐标系间的变换
x
y
x'
y'
θ
O
O'
x 0
y0
p(x p,y p )
2013-3-1 华中理工大学计算机学院 陆枫
99-7
32
分析,
x
y
y'
O
O'(x 0,y 0 )
图6 - 1 1 坐标系变换的变换原理
x'
p,也即p '
p* p x
p y
?
*
x
Op
*
y
Op
2013-3-1 华中理工大学计算机学院 陆枫
99-7
33
可以分两步进行,
x
y
y'
θ
O
O'
x 0
y0
x'
( a ) 将x ' y ' 坐标系的原点平移到x y 坐标系的原点
p(x p,y p )
x
y
θ
O
y'
x'
(b)将x'轴 旋转到x轴 上
p(x p,y p )
2013-3-1 华中理工大学计算机学院 陆枫
99-7
34
于是,
R
T
t
TpTp
T
p
y
p
x
p
y'
p
x'p'
?????
?
??
?
??
?
?
??
?
??
?
? 11
2013-3-1 华中理工大学计算机学院 陆枫
99-7
35
6.3.8 光栅变换
直接对帧缓存中象素点进行操作的变换称为 光栅变换 。
? 光栅平移变换,
(a) 读出象素块的内容 (b) 复制象素块的内容 ( c ) 擦除原象素块的内容
2013-3-1 华中理工大学计算机学院 陆枫
99-7
36
? 90°, 180° 和 270° 的光栅旋转变换,
(a )逆 时针旋转90 °
(x,y)
(y,rowlen-x)
rowlen
(x,y)
(rowlen-x,vollen-y)
( b ) 逆时针旋转1 8 0 °
rowlen
vollen
2013-3-1 华中理工大学计算机学院 陆枫
99-7
37
? 任意角度的光栅旋转变换,
旋转的
象素阵列
光栅网格
A A
2
1 3
2013-3-1 华中理工大学计算机学院 陆枫
99-7
38
? 光栅比例变换,
(a)Sx=1/2,Xy=1/2 (b )原 图 (a)Sx=1,Xy=3/2
缩小时原图
中的相应象
素区域
放大时原图
中的相应象
素区域
2013-3-1 华中理工大学计算机学院 陆枫
99-7
39
6.3.9 变换的性质
? 仿射变换具有平行线不变性和有限点数目的不变性
? 平移, 比例, 旋转, 错切和反射等变换均是二维仿射
变换的特例, 反过来, 任何常用的二维仿射变换总可
以表示为这五种变换的复合 。
?
?
?
???
???
ndycxy
mbyaxx
'
'
二维仿射变换 是具有如下形式的二维坐标变换,
2013-3-1 华中理工大学计算机学院 陆枫
99-7
40
二维几何变换具有如下一些性质,? 直线的中点不变性；
? 平行直线不变性；
? 相交不变性；
? 仅包含旋转, 平移和反射的仿射变换维持角度和长
度的不变性；
? 比例变化可改变图形的大小和形状；
? 错切变化引起图形角度关系的改变, 甚至导致图形
发生畸变 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
41
6.4 两维观察
6.4.1 基本概念
? 在计算机图形学中, 将在用户坐标系中需要进行
观察和处理的一个坐标区域称为 窗口 （ Window）
? 将窗口映射到显示设备上的坐标区域称为 视区
（ Viewport）
2013-3-1 华中理工大学计算机学院 陆枫
99-7
42
要将窗口内的图形在视区中显示出来, 必须经过将窗口
到视区的变换 （ Window-Viewport Transformation） 处理,
这种变换就是 观察变换 （ Viewing Transformation） 。
X
Y
wxl X
Y
wyb
wxr
wyt
窗口
vxr
vyb
vyt
视区
( a ) 用户坐标系中的窗口 ( b ) 屏幕坐标系中的视区
vxl
2013-3-1 华中理工大学计算机学院 陆枫
99-7
43
X
Y
窗
口
图6-17 用 户坐标系中旋转的窗口
1x用 户
y
用
户
xNDC
y
N
D
C
窗口
视区
y
观
察
x 观
察
1
(a) 观察坐标系 (b) 规格化设备坐标系
2013-3-1 华中理工大学计算机学院 陆枫
99-7
44
观察坐标系 (View Coordinate)和规格化设备坐标系
(Normalized Device Coordinate)
? 观察坐标系 是依据窗口的方向和形状在用户坐标
平面中定义的直角坐标系 。
? 规格化设备坐标系 也是直角坐标系, 它是将二维
的设备坐标系规格化到 （ 0.0,0.0） 到 （ 1.0,1.0）
的坐标范围内形成的 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
45
引入了观察坐标系和规格化设备坐标系后, 观察变换分
为如下图所示的几个步骤, 通常称为 二维观察流程 。 观察坐
标系下
对窗口
进行裁
剪
窗口到视
区( 规范
化设备坐
标系中定
义) 的变
换
视图区从
规范化坐
标系到设
备坐标系
的变换
在图形
设备上
输出
DC
用户坐
标系到
观察坐
标系间
的变换
应用
程序
到图
形的
用户
坐标
图6 - 1 9 两维观察流程
NDCVCWC VC
2013-3-1 华中理工大学计算机学院 陆枫
99-7
46
? 变焦距效果
图6-20 变 焦距效果（窗口变、视区不变）
( a ) 原图及变化的窗口
( b ) 与窗口对应
的视区1
( c ) 与窗口对应
的视区2
( d ) 与窗口对应
的视区3
1123 2 3
2013-3-1 华中理工大学计算机学院 陆枫
99-7
47
? 整体放缩效果
(a) 原 图及窗口
(b) 视 区1
图6 - 2 1 整体放缩效果（窗口不变、视区变）
(c) 视 区2
(d) 视区3
? 漫游效果
6.4.2 用户坐标系到观察坐标系的变换
用户坐标系到观察坐标系的变换分由两个变换步骤合成：
1,将观察坐标系原点移动到用户坐标系原点
x用户
y
用
户
窗口
y
观
察
x
观
察
(a) 平移 变换
2013-3-1 华中理工大学计算机学院 陆枫
99-7
49
2,绕原点旋转使两坐标系重合
x用 户
y
用
户
窗口
y
观
察
x观 察
(b ) 旋 转变换
2013-3-1 华中理工大学计算机学院 陆枫
99-7
50
6.4.3 窗口到视区的变换
X
Y
wxl X
Y
wyb
wxr
wyt
窗口
vxl
vyb
vyt
视区
图6-23 窗 口到视区的变换
( a ) 窗口中的点 ( b ) 视区中的点
(x w,y w )
(x v,y v )
vxr
2013-3-1 华中理工大学计算机学院 陆枫
99-7
51
要将窗口内的点 （ xw,yw） 映射到相对应的视区内的点
（ xv,yv） 需进行以下步骤,
(1) 将窗口左下角点移至用户系统系的坐标原点
(2) 针对原点进行比例变换
(3) 进行反平移
2013-3-1 华中理工大学计算机学院 陆枫
99-7
52
6.5 裁剪
? 在二维观察中, 需要在观察坐标系下对窗口进行 裁剪,
即只保留窗口内的那部分图形, 去掉窗口外的图形 。
? 假设 窗口是标准矩形, 即边与坐标轴平行的矩形, 由
上 （ y=wyt）, 下 （ y=wyb）, 左 （ x=wxl）, 右
（ x=wxr） 四条边描述 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
53
6.5.1 点的裁剪
w y tyw y b
w x rxw x l
??
??
且
,
2013-3-1 华中理工大学计算机学院 陆枫
99-7
54
6.5.2 直线段的裁剪
假定 直线段用 p1(x1,y1)p2(x2,y2)表示 。
? 直线段和剪裁窗口的可能关系,
? 完全落在窗口内
? 完全落在窗口外
? 与窗口边界相交
窗口
图6 - 2 4 直线段与窗口的关系
A
B
C
D
E
F
H
G
I
J
2013-3-1 华中理工大学计算机学院 陆枫
99-7
55
? 实交点 是直线段与窗口矩形边界的交点 。
? 虚交点 则是直线段与窗口矩形边界延长线或直线
段的延长线与窗口矩形边界的交点 。
窗口
图6- 2 5 实交点与虚交点
A
B
C
D
E
F
H
G
I
J
虚交点
实交点
实交点
实交点
虚交点
虚交点
2013-3-1 华中理工大学计算机学院 陆枫
99-7
56
1,Cohen-Sutherland算法
基本思想,对每条直线段 p1(x1,y1)p2(x2,y2)分三种情况处理：
(1) 直线段完全可见,, 简取, 之 。
(2) 直线段完全不可见,, 简弃, 之 。
(3) 直线段既不满足, 简取, 的条件, 也不满足, 简弃,
的条件, 需要对直线段按交点进行分段, 分段后重复上
述处理 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
57
编码,对于任一端点 (x,y),根据其坐标所在的区域,
赋予一个 4位的二进制码 D3D2D1D0。
编码规则如下,
? 若 x<wxl,则 D0=1,否则 D0=0；
? 若 x>wxr,则 D1=1,否则 D1=0；
? 若 y<wyb,则 D2=1,否则 D2=0；
? 若 y>wyt,则 D3=1,否则 D3=0。
0 0 0 0
窗口
0 1 0 00 1 0 1
1 0 0 1
0 0 0 1
1 0 1 0
0 1 1 0
1 0 0 0
0 0 1 0
图6-26 窗 口及区域编码
D
3
D
2
D
1
D
0
2013-3-1 华中理工大学计算机学院 陆枫
99-7
58
裁剪
裁剪一条线段时, 先求出端点 p1和 p2的编码 code1和
code2,然后,
(1)若 code1|code2=0,对直线段应简取之 。
(2)若 code1&code2≠0,对直线段可简弃之 。
(3)若上述两条件均不成立 。 则需求出直线段与窗口边
界的交点 。 在交点处把线段一分为二, 其中必有一段
完全在窗口外, 可以弃之 。 再对另一段重复进行上述
处理, 直到该线段完全被舍弃或者找到位于窗口内的
一段线段为止 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
59
求交,假定直线的端点坐标为 (x1,y1)和 (x2,y2)
? 左, 右边界交点的计算,
? 上, 下边界交点的计算,
窗口
A
B
C
D
E
F
H
G
I
J
虚交点
实交点
实交点
实交点
虚交点
虚交点
2013-3-1 华中理工大学计算机学院 陆枫
99-7
60
算法的步骤,
(1)输入直线段的两端点坐标,p1(x1,y1),p2(x2,y2),以及窗口的四条
边界坐标,wyt,wyb,wxl和 wxr。
(2)对 p1,p2进行编码：点 p1的编码为 code1,点 p2的编码为 code2。
(3) 若 code1|code2=0,对直线段应简取之, 转 ( 6 ) ；否则, 若
code1&code2≠0,对直线段可简弃之, 转 (7)；当上述两条均不满
足时, 进行步骤 (4)。
(4)确保 p1在窗口外部：若 p1在窗口内, 则交换 p1和 p2的坐标值和编
码 。
(5)按左, 右, 上, 下的顺序求出直线段与窗口边界的交点, 并用该
交点的坐标值替换 p1的坐标值 。 也即在交点 s处把线段一分为二,
并去掉 p1s这一段 。 考虑到 p1是窗口外的一点, 因此可以去掉 p1s。
转 (2)。
(6)用直线扫描转换算法画出当前的直线段 p1p2。
(7)算法结束 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
61
例如,
特点,
P 1
P 2
P 3
P 4
0 0 0 0
0 1 0 00 1 0 1
1 0 0 1
0 0 0 1
1 0 1 0
0 1 1 0
1 0 0 0
0 0 1 0
图6- 27 直线段p 1 p 2 的编码裁剪
2013-3-1 华中理工大学计算机学院 陆枫
99-7
62
2,中点分割算法
基本思想,
当对直线段不能简取也不能简弃时, 简单地把线段等
分为二段, 对两段重复上述测试处理, 直至每条线段
完全在窗口内或完全在窗口外 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
63
算法步骤,
(1)输入直线段的两端点坐标,p1(x1,y1),p2(x2,y2),以及窗口的四条
边界坐标,wyt,wyb,wxl和 wxr。
(2)对 p1,p2进行编码：点 p1的编码为 code1,点 p2的编码为 code2。
(3)若 code1|code2=0,对直线段应简取之, 保留当前直线段的端点坐
标, 转 (5)；否则, 若 code1&code2≠0,对直线段可简弃之, 转 (5)；
当上述两条均不满足时, 进行步骤 (4)。
(4)求出直线段的中点 M,将 p1M,p2M入栈 。
(5)当栈不空时, 从栈中弹出一条直线段, 取为 p1p2,转 (2)进行处理 。
否则, 继续 (6)。
(6)当栈为空时, 合并保留的直线段端点, 得到窗口内的直线段 p1p2。
用直线扫描转换算法画出当前的直线段 p1p2,算法结束 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
64
中点分割算法的 核心思想 是 通过二分逼近来确定直
线段与窗口的交点 。
p
1
p
2
p
3
p
4
p
5
p
6
p
7
2013-3-1 华中理工大学计算机学院 陆枫
99-7
65
重新构造 算法步骤,
( 1 )若 code1|code2=0,对直线段应简取之, 结束；否则, 若
code1&code2≠0,对直线段可简弃之, 结束；当这两条均不满
足时, 进行步骤 (2)。
(2)找出该直线段离窗口边界最远的点和该直线段的中点 。 判中点
是否在窗口内, 若中点不在窗口内, 则把中点和离窗口边界最
远点构成的线段丢掉, 以线段上的另一点和该中点再构成线段
求其中点；如中点在窗口内, 则又以中点和最远点构成线段,
并求其中点, 直到中点与窗口边界的坐标值在规定的误差范围
内相等, 则该中点就是该线段落在窗口内的一个端点坐标 。
(3)如另一点在窗口内, 则经 (2)即确定了该线段在窗口内的部分 。
如另一点不在窗口内, 则该点和所求出的在窗口上的那一点构
成一条线段, 重复步骤 (2),即可求出落在窗口内的另一点 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
66
例如,
特点,
p
1
p
2
p
3
p
4
p
5
p
6
p
7
2013-3-1 华中理工大学计算机学院 陆枫
99-7
67
3,Liang-Barsky算法
分析
推导
2013-3-1 华中理工大学计算机学院 陆枫
99-7
68
特殊处理,
(a )直 线段与窗口边界
wx l和 wx r平 行的情况
(b )直 线段与窗口边界
wy b和 wy t平 行的情况
wyt
wyb
wxl wxr wxrwxl
wyb
wyt
A
B
C
D
E
F
G
H I
J
K
L
2013-3-1 华中理工大学计算机学院 陆枫
99-7
69
算法步骤,
(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)利用直线的扫描转换算法绘制在窗口内的直线段 。 算法结束 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
70
4,其它裁剪算法简介
? Cohen-Sutherland算法, 中点分割算法和 Liang-
Barsky算法
? Cyrus-Beck算法
? Nicholl-Lee-Nicholl算法
2013-3-1 华中理工大学计算机学院 陆枫
99-7
71
6.5.3 多边形的裁剪
问题的提出,
( a ) 裁剪前
( b ) 直接采用直线段
裁剪的结果 ( c ) 正确的裁剪结果
2013-3-1 华中理工大学计算机学院 陆枫
99-7
72
1,Sutherland-Hodgeman多边形裁剪
基本思想
输入：A B C D E F G H
A
B
C
D
E
F
G
H
输出：A 1 2 D E F G H
1
2
( a ) 用左边界裁剪
输出：A 1 3 4 D 5 6 F G H
A
D
E
F
G
H
输入：A 1 2 D E F G H
1
2
( b ) 用下边界裁剪
3 4 5 6
2013-3-1 华中理工大学计算机学院 陆枫
99-7
73
输入：A134D56FGH
A
D F
G
H
1
(c)用右边界裁剪
3 4 5 6
输出：A134D5678GH
7
8
A
D
G
H
1
(d)用上边界裁剪
3 4 5 6
7
8
输入：A134D5678GH
输出：K34D56789IHJ
9IJK
2013-3-1 华中理工大学计算机学院 陆枫
99-7
74
算法实施策略,
? 为窗口各边界裁剪的多边形存储输入与输出顶点表 。
在窗口的一条裁剪边界处理完所有顶点后, 其输出
顶点表将用窗口的下一条边界继续裁剪 。
? 窗口的一条边以及延长线构成的裁剪线把平面分为
两个区域, 包含有窗口区域的一个域称为 可见侧 ；
不包含窗口区域的域为 不可见侧 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
75
沿着多边形依次处理顶点会遇到四种情况,
S
P S
P SP S
P
I
I
( a ) 输出I,P ( b ) 输出P ( c ) 输出I
可见侧
( d ) 不输出
可见侧 可见侧可见侧
2013-3-1 华中理工大学计算机学院 陆枫
99-7
76
特点,
A
( a ) 裁剪前
(b)Sutherland-Hodgeman
算法的裁剪结果
B C
D
E
F
A
B C
D
E
F
V 1 V 2 V 3 V 4
2013-3-1 华中理工大学计算机学院 陆枫
99-7
77
2,Weiler-Atherton多边形裁剪
假定 按顺时针方向处理顶点, 且将用户多边形定义为 Ps,窗
口矩形为 Pw。 算法从 Ps的任一点出发, 跟踪检测 Ps的每一
条边, 当 Ps与 Pw相交时 （ 实交点 ）, 按如下规则处理,
(1)若是由不可见侧进入可见侧, 则输出可见直线段, 转 (3)；
(2)若是由可见侧进入不可见侧, 则从当前交点开始, 沿窗口
边界顺时针检测 Pw的边, 即用窗口的有效边界去裁剪 Ps的
边, 找到 Ps与 Pw最靠近当前交点的另一交点, 输出可见直
线段和由当前交点到另一交点之间窗口边界上的线段, 然
后返回处理的当前交点；
(3)沿着 Ps处理各条边, 直到处理完 Ps的每一条边, 回到起点
为止 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
78
下图示了 Weiler-Atherton算法裁剪凹多边形的过程和结果 。
A
B
C
D
E
C
E
V 1
V 2
V 3V 4
V 1
V 2
V 3V 4
图6 - 3 4 W e i l e r - A t h e r t o n 算法裁剪凹多边形
(a) 裁剪前 (b)Weiler-Atherton算法的 裁剪结果
返回
返回
2013-3-1 华中理工大学计算机学院 陆枫
99-7
79
6.5.4 其它裁剪
1,曲线边界对象的裁剪
? 曲线边界对象与矩形窗口和多边形窗口的裁剪
? 加速方法
2013-3-1 华中理工大学计算机学院 陆枫
99-7
80
2,文字裁剪
文字裁剪的策略包括几种,
? 串精度裁剪
? 字符精度裁剪
? 笔划, 象素精度裁剪
3,外部裁剪
保留落在裁剪区域外的图形部分, 去掉裁剪区域内的
所有图形, 这种裁剪过程称为 外部裁剪, 也称 空白裁
剪 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
81
习题
99-7
1
第 6章 二维变换及二维观察
提出问题
? 如何对二维图形进行方向, 尺寸和形状方面的变换
? 如何方便地实现在显示设备上对二维图形进行观察
2013-3-1 华中理工大学计算机学院 陆枫
99-7
2
第 6章 二维变换及两维观察
6.1 基本概念
6.1.1 齐次坐标
? 齐次坐标表示 就是用 n+1维向量表示一个 n维向量 。
? 齐次坐标的不唯一性
? 规范化齐次坐标表示 就是 h=1的齐次坐标表示 。
? 如何从齐次坐标转换到规范化齐次坐标？
2013-3-1 华中理工大学计算机学院 陆枫
99-7
3
6.1.2 几何变换
图形的 几何变换 是指对图形的几何信息经过平移, 比
例, 旋转等变换后产生新的图形, 是图形在方向,
尺寸和形状方面的变换 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
4
6.1.3 二维变换矩阵
? ? ? ? ? ?
?
?
?
?
?
?
?
?
?
?
????
sml
qdc
pba
yxTyxyx D 111'' 2
2013-3-1 华中理工大学计算机学院 陆枫
99-7
5
6.2 基本几何变换
基本几何变换都是 相对于坐标原点和坐标轴进行的
几何变换
6.2.1 平移变换
平移 是指将 p点沿直线路径从一个坐标位置移到另一
个坐标位置的重定位过程 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
6
平移是一种不产生变形而移动物体的刚体变换
（ rigid-body transformation）
Y
X
Tx
Ty
图6 - 1 平移变换
P'
P
T
2013-3-1 华中理工大学计算机学院 陆枫
99-7
7
Tx,Ty称为 平移矢量
?
?
?
?
?
?
?
?
?
?
1
010
001
yx
TT
推导,
矩阵,
2013-3-1 华中理工大学计算机学院 陆枫
99-7
8
6.2.2 比例变换
比例变换 是指对 p点相对于坐标原点沿 x方向放缩 Sx倍,
沿 y方向放缩 Sy倍 。 其中 Sx和 Sy称为 比例系数 。
Y
X
图6- 2 比 例变换(S x =2,S y =3 )
P ' ( 4,3 )
P ( 2,1 )
2013-3-1 华中理工大学计算机学院 陆枫
99-7
9
推导,
矩阵,
?
?
?
?
?
?
?
?
?
?
100
00
00
y
x
S
S
2013-3-1 华中理工大学计算机学院 陆枫
99-7
10
( a ) S x=S y比例
原图
( b ) S x<>Sy比例
原图
图6 - 3 比例变换
S x < S y
S x > S y
S x = S y > 1
S x = S y < 1
2013-3-1 华中理工大学计算机学院 陆枫
99-7
11
整体比例变换,
?
?
?
?
?
?
?
?
?
?
s00
010
001
2013-3-1 华中理工大学计算机学院 陆枫
99-7
12
6.2.3 旋转变换
二维旋转 是指将 p点绕坐标原点转动某个角度 （ 逆时针为
正, 顺时针为负 ） 得到新的点 p’的重定位过程 。
Y
X
图6 - 4 旋转变换
P'
P
r
r
α
θ
2013-3-1 华中理工大学计算机学院 陆枫
99-7
13
推导,
矩阵,逆时针旋转 θ角
?
?
?
?
?
?
?
?
?
?
?
100
0c o ss i n
0s i nc o s
??
??
顺时针旋转 θ角?
2013-3-1 华中理工大学计算机学院 陆枫
99-7
14
简化计算
? ? ? ?
?
?
?
?
?
?
?
?
?
?
???
100
01
01
11'' ?
?
yxyx
2013-3-1 华中理工大学计算机学院 陆枫
99-7
15
6.2.4 对称变换
对称变换 后的图形是原图形关于某一轴线或原点的镜像 。
X
Y
( a ) 关于x 轴对称
X
Y
(b)关 于y轴 对称
X
Y
( c ) 关于原点对称
2013-3-1 华中理工大学计算机学院 陆枫
99-7
16
X
Y
( d ) 关于x = y 对称
X
Y
(e)关 于x=-y 对称
2013-3-1 华中理工大学计算机学院 陆枫
99-7
17
(1)关于 x轴对称
?
?
?
?
?
?
?
?
?
?
?
100
010
001
Y
X
P'(x,-y)
P(x,y)
( a ) 关于x 轴对称
2013-3-1 华中理工大学计算机学院 陆枫
99-7
18
(2)关于 y轴对称
Y
X
P'(-x,y) p(x,y)
( b ) 关于y 轴对称
?
?
?
?
?
?
?
?
?
? ?
100
010
001
2013-3-1 华中理工大学计算机学院 陆枫
99-7
19
(3)关于原点对称
Y
X
P(x,y)
( c ) 关于原点对称
?
?
?
?
?
?
?
?
?
?
?
?
100
010
001
2013-3-1 华中理工大学计算机学院 陆枫
99-7
20
(4)关于 y=x轴对称
Y
X
p(x,y)
p'(y,x)
x=y
( d ) 关于x = y 对称
?
?
?
?
?
?
?
?
?
?
100
001
010
2013-3-1 华中理工大学计算机学院 陆枫
99-7
21
(5)关于 y=-x轴对称
Y
X
P'(-y,-x)
P(x,y)
x=-y
(e )关于 x= -y 对称
?
?
?
?
?
?
?
?
?
?
?
?
100
001
010
2013-3-1 华中理工大学计算机学院 陆枫
99-7
22
6.2.5 错切变换
错切变换, 也称为剪切, 错位变换, 用于产生弹性物
体的变形处理 。
Y
X
Y
X
Y
X
(a) 原 图 (b) 沿 x方 向错切
(c) 沿 y方 向错切
图6-7 错切变换
2013-3-1 华中理工大学计算机学院 陆枫
99-7
23
其变换矩阵为,
?
?
?
?
?
?
?
?
?
?
100
01
01
c
b
(1)沿 x方向错切
(2)沿 y方向错切
(3)两个方向错切
2013-3-1 华中理工大学计算机学院 陆枫
99-7
24
6.2.6 二维图形几何变换的计算
几何变换均可表示成 P’=P*T的形式
1,点的变换
2,直线的变换
3,多边形的变换
4,曲线的变换
2013-3-1 华中理工大学计算机学院 陆枫
99-7
25
6.3 复合变换
复合变换 是指,
? 图形作一次以上的几何变换, 变换结果是每次的变换矩
阵相乘 。
? 任何一复杂的几何变换都可以看作基本几何变换的组合
形式 。
复合变换具有形式,
)1(
)('
321
321
??????
???????
nTTTTP
TTTTPTPP
n
n
?
?
2013-3-1 华中理工大学计算机学院 陆枫
99-7
26
6.3.1 二维复合平移
两个连续平移是加性的 。
6.3.2 二维复合比例
连续比例变换是相乘的 。
6.3.3 二维复合旋转
两个连续旋转是相加的 。 可写为,
)( 21)()( 21 ???? ???? RRRR
2013-3-1 华中理工大学计算机学院 陆枫
99-7
27
6.3.4 其它二维复合变换
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?????
100
0c o s0
00c o s
100
01
01
100
01
01
100
0c o s0
00c o s
100
0 c o s s in
0 s inc o s
?
?
?
?
?
?
?
?
??
??
tg
tg
tg
tg
R
2013-3-1 华中理工大学计算机学院 陆枫
99-7
28
6.3.5 相对任一参考点的二维几何变换
相对某个参考点 (xF,yF)作二维几何变换, 其变换过程为,
(1) 平移
(2) 针对原点进行二维几何变换 。
(3) 反平移
例 1,相对点 (xF,yF)的旋转变换
例 2,相对点 (xF,yF)的比例变换
2013-3-1 华中理工大学计算机学院 陆枫
99-7
29
6.3.6 相对任意方向的二维几何变换
相对任意方向作二维几何变换, 其变换的过程是,
(1) 旋转变换
(2) 针对坐标轴进行二维几何变换；
(3) 反向旋转
例 3,相对直线 y=x的反射变换
2013-3-1 华中理工大学计算机学院 陆枫
99-7
30
例 4,将正方形 ABCO各点沿图 6-8所示的 (0,0)→( 1,1)方
向进行拉伸, 结果为如图所示的, 写出其变换矩阵和
变换过程 。
Y
X1 3/21/2
1/2
3/2
2
2
图6 - 8 针对固定方向的拉伸
O
A B
C
C'
B'
A'
2013-3-1 华中理工大学计算机学院 陆枫
99-7
31
6.3.7 坐标系之间的变换
问题,
图6 - 9 坐标系间的变换
x
y
x'
y'
θ
O
O'
x 0
y0
p(x p,y p )
2013-3-1 华中理工大学计算机学院 陆枫
99-7
32
分析,
x
y
y'
O
O'(x 0,y 0 )
图6 - 1 1 坐标系变换的变换原理
x'
p,也即p '
p* p x
p y
?
*
x
Op
*
y
Op
2013-3-1 华中理工大学计算机学院 陆枫
99-7
33
可以分两步进行,
x
y
y'
θ
O
O'
x 0
y0
x'
( a ) 将x ' y ' 坐标系的原点平移到x y 坐标系的原点
p(x p,y p )
x
y
θ
O
y'
x'
(b)将x'轴 旋转到x轴 上
p(x p,y p )
2013-3-1 华中理工大学计算机学院 陆枫
99-7
34
于是,
R
T
t
TpTp
T
p
y
p
x
p
y'
p
x'p'
?????
?
??
?
??
?
?
??
?
??
?
? 11
2013-3-1 华中理工大学计算机学院 陆枫
99-7
35
6.3.8 光栅变换
直接对帧缓存中象素点进行操作的变换称为 光栅变换 。
? 光栅平移变换,
(a) 读出象素块的内容 (b) 复制象素块的内容 ( c ) 擦除原象素块的内容
2013-3-1 华中理工大学计算机学院 陆枫
99-7
36
? 90°, 180° 和 270° 的光栅旋转变换,
(a )逆 时针旋转90 °
(x,y)
(y,rowlen-x)
rowlen
(x,y)
(rowlen-x,vollen-y)
( b ) 逆时针旋转1 8 0 °
rowlen
vollen
2013-3-1 华中理工大学计算机学院 陆枫
99-7
37
? 任意角度的光栅旋转变换,
旋转的
象素阵列
光栅网格
A A
2
1 3
2013-3-1 华中理工大学计算机学院 陆枫
99-7
38
? 光栅比例变换,
(a)Sx=1/2,Xy=1/2 (b )原 图 (a)Sx=1,Xy=3/2
缩小时原图
中的相应象
素区域
放大时原图
中的相应象
素区域
2013-3-1 华中理工大学计算机学院 陆枫
99-7
39
6.3.9 变换的性质
? 仿射变换具有平行线不变性和有限点数目的不变性
? 平移, 比例, 旋转, 错切和反射等变换均是二维仿射
变换的特例, 反过来, 任何常用的二维仿射变换总可
以表示为这五种变换的复合 。
?
?
?
???
???
ndycxy
mbyaxx
'
'
二维仿射变换 是具有如下形式的二维坐标变换,
2013-3-1 华中理工大学计算机学院 陆枫
99-7
40
二维几何变换具有如下一些性质,? 直线的中点不变性；
? 平行直线不变性；
? 相交不变性；
? 仅包含旋转, 平移和反射的仿射变换维持角度和长
度的不变性；
? 比例变化可改变图形的大小和形状；
? 错切变化引起图形角度关系的改变, 甚至导致图形
发生畸变 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
41
6.4 两维观察
6.4.1 基本概念
? 在计算机图形学中, 将在用户坐标系中需要进行
观察和处理的一个坐标区域称为 窗口 （ Window）
? 将窗口映射到显示设备上的坐标区域称为 视区
（ Viewport）
2013-3-1 华中理工大学计算机学院 陆枫
99-7
42
要将窗口内的图形在视区中显示出来, 必须经过将窗口
到视区的变换 （ Window-Viewport Transformation） 处理,
这种变换就是 观察变换 （ Viewing Transformation） 。
X
Y
wxl X
Y
wyb
wxr
wyt
窗口
vxr
vyb
vyt
视区
( a ) 用户坐标系中的窗口 ( b ) 屏幕坐标系中的视区
vxl
2013-3-1 华中理工大学计算机学院 陆枫
99-7
43
X
Y
窗
口
图6-17 用 户坐标系中旋转的窗口
1x用 户
y
用
户
xNDC
y
N
D
C
窗口
视区
y
观
察
x 观
察
1
(a) 观察坐标系 (b) 规格化设备坐标系
2013-3-1 华中理工大学计算机学院 陆枫
99-7
44
观察坐标系 (View Coordinate)和规格化设备坐标系
(Normalized Device Coordinate)
? 观察坐标系 是依据窗口的方向和形状在用户坐标
平面中定义的直角坐标系 。
? 规格化设备坐标系 也是直角坐标系, 它是将二维
的设备坐标系规格化到 （ 0.0,0.0） 到 （ 1.0,1.0）
的坐标范围内形成的 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
45
引入了观察坐标系和规格化设备坐标系后, 观察变换分
为如下图所示的几个步骤, 通常称为 二维观察流程 。 观察坐
标系下
对窗口
进行裁
剪
窗口到视
区( 规范
化设备坐
标系中定
义) 的变
换
视图区从
规范化坐
标系到设
备坐标系
的变换
在图形
设备上
输出
DC
用户坐
标系到
观察坐
标系间
的变换
应用
程序
到图
形的
用户
坐标
图6 - 1 9 两维观察流程
NDCVCWC VC
2013-3-1 华中理工大学计算机学院 陆枫
99-7
46
? 变焦距效果
图6-20 变 焦距效果（窗口变、视区不变）
( a ) 原图及变化的窗口
( b ) 与窗口对应
的视区1
( c ) 与窗口对应
的视区2
( d ) 与窗口对应
的视区3
1123 2 3
2013-3-1 华中理工大学计算机学院 陆枫
99-7
47
? 整体放缩效果
(a) 原 图及窗口
(b) 视 区1
图6 - 2 1 整体放缩效果（窗口不变、视区变）
(c) 视 区2
(d) 视区3
? 漫游效果
6.4.2 用户坐标系到观察坐标系的变换
用户坐标系到观察坐标系的变换分由两个变换步骤合成：
1,将观察坐标系原点移动到用户坐标系原点
x用户
y
用
户
窗口
y
观
察
x
观
察
(a) 平移 变换
2013-3-1 华中理工大学计算机学院 陆枫
99-7
49
2,绕原点旋转使两坐标系重合
x用 户
y
用
户
窗口
y
观
察
x观 察
(b ) 旋 转变换
2013-3-1 华中理工大学计算机学院 陆枫
99-7
50
6.4.3 窗口到视区的变换
X
Y
wxl X
Y
wyb
wxr
wyt
窗口
vxl
vyb
vyt
视区
图6-23 窗 口到视区的变换
( a ) 窗口中的点 ( b ) 视区中的点
(x w,y w )
(x v,y v )
vxr
2013-3-1 华中理工大学计算机学院 陆枫
99-7
51
要将窗口内的点 （ xw,yw） 映射到相对应的视区内的点
（ xv,yv） 需进行以下步骤,
(1) 将窗口左下角点移至用户系统系的坐标原点
(2) 针对原点进行比例变换
(3) 进行反平移
2013-3-1 华中理工大学计算机学院 陆枫
99-7
52
6.5 裁剪
? 在二维观察中, 需要在观察坐标系下对窗口进行 裁剪,
即只保留窗口内的那部分图形, 去掉窗口外的图形 。
? 假设 窗口是标准矩形, 即边与坐标轴平行的矩形, 由
上 （ y=wyt）, 下 （ y=wyb）, 左 （ x=wxl）, 右
（ x=wxr） 四条边描述 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
53
6.5.1 点的裁剪
w y tyw y b
w x rxw x l
??
??
且
,
2013-3-1 华中理工大学计算机学院 陆枫
99-7
54
6.5.2 直线段的裁剪
假定 直线段用 p1(x1,y1)p2(x2,y2)表示 。
? 直线段和剪裁窗口的可能关系,
? 完全落在窗口内
? 完全落在窗口外
? 与窗口边界相交
窗口
图6 - 2 4 直线段与窗口的关系
A
B
C
D
E
F
H
G
I
J
2013-3-1 华中理工大学计算机学院 陆枫
99-7
55
? 实交点 是直线段与窗口矩形边界的交点 。
? 虚交点 则是直线段与窗口矩形边界延长线或直线
段的延长线与窗口矩形边界的交点 。
窗口
图6- 2 5 实交点与虚交点
A
B
C
D
E
F
H
G
I
J
虚交点
实交点
实交点
实交点
虚交点
虚交点
2013-3-1 华中理工大学计算机学院 陆枫
99-7
56
1,Cohen-Sutherland算法
基本思想,对每条直线段 p1(x1,y1)p2(x2,y2)分三种情况处理：
(1) 直线段完全可见,, 简取, 之 。
(2) 直线段完全不可见,, 简弃, 之 。
(3) 直线段既不满足, 简取, 的条件, 也不满足, 简弃,
的条件, 需要对直线段按交点进行分段, 分段后重复上
述处理 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
57
编码,对于任一端点 (x,y),根据其坐标所在的区域,
赋予一个 4位的二进制码 D3D2D1D0。
编码规则如下,
? 若 x<wxl,则 D0=1,否则 D0=0；
? 若 x>wxr,则 D1=1,否则 D1=0；
? 若 y<wyb,则 D2=1,否则 D2=0；
? 若 y>wyt,则 D3=1,否则 D3=0。
0 0 0 0
窗口
0 1 0 00 1 0 1
1 0 0 1
0 0 0 1
1 0 1 0
0 1 1 0
1 0 0 0
0 0 1 0
图6-26 窗 口及区域编码
D
3
D
2
D
1
D
0
2013-3-1 华中理工大学计算机学院 陆枫
99-7
58
裁剪
裁剪一条线段时, 先求出端点 p1和 p2的编码 code1和
code2,然后,
(1)若 code1|code2=0,对直线段应简取之 。
(2)若 code1&code2≠0,对直线段可简弃之 。
(3)若上述两条件均不成立 。 则需求出直线段与窗口边
界的交点 。 在交点处把线段一分为二, 其中必有一段
完全在窗口外, 可以弃之 。 再对另一段重复进行上述
处理, 直到该线段完全被舍弃或者找到位于窗口内的
一段线段为止 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
59
求交,假定直线的端点坐标为 (x1,y1)和 (x2,y2)
? 左, 右边界交点的计算,
? 上, 下边界交点的计算,
窗口
A
B
C
D
E
F
H
G
I
J
虚交点
实交点
实交点
实交点
虚交点
虚交点
2013-3-1 华中理工大学计算机学院 陆枫
99-7
60
算法的步骤,
(1)输入直线段的两端点坐标,p1(x1,y1),p2(x2,y2),以及窗口的四条
边界坐标,wyt,wyb,wxl和 wxr。
(2)对 p1,p2进行编码：点 p1的编码为 code1,点 p2的编码为 code2。
(3) 若 code1|code2=0,对直线段应简取之, 转 ( 6 ) ；否则, 若
code1&code2≠0,对直线段可简弃之, 转 (7)；当上述两条均不满
足时, 进行步骤 (4)。
(4)确保 p1在窗口外部：若 p1在窗口内, 则交换 p1和 p2的坐标值和编
码 。
(5)按左, 右, 上, 下的顺序求出直线段与窗口边界的交点, 并用该
交点的坐标值替换 p1的坐标值 。 也即在交点 s处把线段一分为二,
并去掉 p1s这一段 。 考虑到 p1是窗口外的一点, 因此可以去掉 p1s。
转 (2)。
(6)用直线扫描转换算法画出当前的直线段 p1p2。
(7)算法结束 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
61
例如,
特点,
P 1
P 2
P 3
P 4
0 0 0 0
0 1 0 00 1 0 1
1 0 0 1
0 0 0 1
1 0 1 0
0 1 1 0
1 0 0 0
0 0 1 0
图6- 27 直线段p 1 p 2 的编码裁剪
2013-3-1 华中理工大学计算机学院 陆枫
99-7
62
2,中点分割算法
基本思想,
当对直线段不能简取也不能简弃时, 简单地把线段等
分为二段, 对两段重复上述测试处理, 直至每条线段
完全在窗口内或完全在窗口外 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
63
算法步骤,
(1)输入直线段的两端点坐标,p1(x1,y1),p2(x2,y2),以及窗口的四条
边界坐标,wyt,wyb,wxl和 wxr。
(2)对 p1,p2进行编码：点 p1的编码为 code1,点 p2的编码为 code2。
(3)若 code1|code2=0,对直线段应简取之, 保留当前直线段的端点坐
标, 转 (5)；否则, 若 code1&code2≠0,对直线段可简弃之, 转 (5)；
当上述两条均不满足时, 进行步骤 (4)。
(4)求出直线段的中点 M,将 p1M,p2M入栈 。
(5)当栈不空时, 从栈中弹出一条直线段, 取为 p1p2,转 (2)进行处理 。
否则, 继续 (6)。
(6)当栈为空时, 合并保留的直线段端点, 得到窗口内的直线段 p1p2。
用直线扫描转换算法画出当前的直线段 p1p2,算法结束 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
64
中点分割算法的 核心思想 是 通过二分逼近来确定直
线段与窗口的交点 。
p
1
p
2
p
3
p
4
p
5
p
6
p
7
2013-3-1 华中理工大学计算机学院 陆枫
99-7
65
重新构造 算法步骤,
( 1 )若 code1|code2=0,对直线段应简取之, 结束；否则, 若
code1&code2≠0,对直线段可简弃之, 结束；当这两条均不满
足时, 进行步骤 (2)。
(2)找出该直线段离窗口边界最远的点和该直线段的中点 。 判中点
是否在窗口内, 若中点不在窗口内, 则把中点和离窗口边界最
远点构成的线段丢掉, 以线段上的另一点和该中点再构成线段
求其中点；如中点在窗口内, 则又以中点和最远点构成线段,
并求其中点, 直到中点与窗口边界的坐标值在规定的误差范围
内相等, 则该中点就是该线段落在窗口内的一个端点坐标 。
(3)如另一点在窗口内, 则经 (2)即确定了该线段在窗口内的部分 。
如另一点不在窗口内, 则该点和所求出的在窗口上的那一点构
成一条线段, 重复步骤 (2),即可求出落在窗口内的另一点 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
66
例如,
特点,
p
1
p
2
p
3
p
4
p
5
p
6
p
7
2013-3-1 华中理工大学计算机学院 陆枫
99-7
67
3,Liang-Barsky算法
分析
推导
2013-3-1 华中理工大学计算机学院 陆枫
99-7
68
特殊处理,
(a )直 线段与窗口边界
wx l和 wx r平 行的情况
(b )直 线段与窗口边界
wy b和 wy t平 行的情况
wyt
wyb
wxl wxr wxrwxl
wyb
wyt
A
B
C
D
E
F
G
H I
J
K
L
2013-3-1 华中理工大学计算机学院 陆枫
99-7
69
算法步骤,
(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)利用直线的扫描转换算法绘制在窗口内的直线段 。 算法结束 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
70
4,其它裁剪算法简介
? Cohen-Sutherland算法, 中点分割算法和 Liang-
Barsky算法
? Cyrus-Beck算法
? Nicholl-Lee-Nicholl算法
2013-3-1 华中理工大学计算机学院 陆枫
99-7
71
6.5.3 多边形的裁剪
问题的提出,
( a ) 裁剪前
( b ) 直接采用直线段
裁剪的结果 ( c ) 正确的裁剪结果
2013-3-1 华中理工大学计算机学院 陆枫
99-7
72
1,Sutherland-Hodgeman多边形裁剪
基本思想
输入：A B C D E F G H
A
B
C
D
E
F
G
H
输出：A 1 2 D E F G H
1
2
( a ) 用左边界裁剪
输出：A 1 3 4 D 5 6 F G H
A
D
E
F
G
H
输入：A 1 2 D E F G H
1
2
( b ) 用下边界裁剪
3 4 5 6
2013-3-1 华中理工大学计算机学院 陆枫
99-7
73
输入：A134D56FGH
A
D F
G
H
1
(c)用右边界裁剪
3 4 5 6
输出：A134D5678GH
7
8
A
D
G
H
1
(d)用上边界裁剪
3 4 5 6
7
8
输入：A134D5678GH
输出：K34D56789IHJ
9IJK
2013-3-1 华中理工大学计算机学院 陆枫
99-7
74
算法实施策略,
? 为窗口各边界裁剪的多边形存储输入与输出顶点表 。
在窗口的一条裁剪边界处理完所有顶点后, 其输出
顶点表将用窗口的下一条边界继续裁剪 。
? 窗口的一条边以及延长线构成的裁剪线把平面分为
两个区域, 包含有窗口区域的一个域称为 可见侧 ；
不包含窗口区域的域为 不可见侧 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
75
沿着多边形依次处理顶点会遇到四种情况,
S
P S
P SP S
P
I
I
( a ) 输出I,P ( b ) 输出P ( c ) 输出I
可见侧
( d ) 不输出
可见侧 可见侧可见侧
2013-3-1 华中理工大学计算机学院 陆枫
99-7
76
特点,
A
( a ) 裁剪前
(b)Sutherland-Hodgeman
算法的裁剪结果
B C
D
E
F
A
B C
D
E
F
V 1 V 2 V 3 V 4
2013-3-1 华中理工大学计算机学院 陆枫
99-7
77
2,Weiler-Atherton多边形裁剪
假定 按顺时针方向处理顶点, 且将用户多边形定义为 Ps,窗
口矩形为 Pw。 算法从 Ps的任一点出发, 跟踪检测 Ps的每一
条边, 当 Ps与 Pw相交时 （ 实交点 ）, 按如下规则处理,
(1)若是由不可见侧进入可见侧, 则输出可见直线段, 转 (3)；
(2)若是由可见侧进入不可见侧, 则从当前交点开始, 沿窗口
边界顺时针检测 Pw的边, 即用窗口的有效边界去裁剪 Ps的
边, 找到 Ps与 Pw最靠近当前交点的另一交点, 输出可见直
线段和由当前交点到另一交点之间窗口边界上的线段, 然
后返回处理的当前交点；
(3)沿着 Ps处理各条边, 直到处理完 Ps的每一条边, 回到起点
为止 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
78
下图示了 Weiler-Atherton算法裁剪凹多边形的过程和结果 。
A
B
C
D
E
C
E
V 1
V 2
V 3V 4
V 1
V 2
V 3V 4
图6 - 3 4 W e i l e r - A t h e r t o n 算法裁剪凹多边形
(a) 裁剪前 (b)Weiler-Atherton算法的 裁剪结果
返回
返回
2013-3-1 华中理工大学计算机学院 陆枫
99-7
79
6.5.4 其它裁剪
1,曲线边界对象的裁剪
? 曲线边界对象与矩形窗口和多边形窗口的裁剪
? 加速方法
2013-3-1 华中理工大学计算机学院 陆枫
99-7
80
2,文字裁剪
文字裁剪的策略包括几种,
? 串精度裁剪
? 字符精度裁剪
? 笔划, 象素精度裁剪
3,外部裁剪
保留落在裁剪区域外的图形部分, 去掉裁剪区域内的
所有图形, 这种裁剪过程称为 外部裁剪, 也称 空白裁
剪 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
81
习题
