电脑基础知识计算机图形学chap6 二维变换及二维观察

ECUST

计算机■移孽基磁

华东理工人学必算机祭•谢屹玲

第力*二箱暧换及二瓶机塞

□如何对二维图形进行方向、尺寸和形状方面的

变换。

□如何进行二维观察。

2

二瓶变换及二横机察

□基本几何变换与基本概念

口二维图形几何变换的计算

口复合变换

口变换的性质

3

6.2基4几何麦换

□图形的几何变换

■平移、旋转、缩放、反射和错切

■变换的组合

□图形几何变换的目的

改变图形的位置、方向、大小

□基本几何变换

都是相对于坐标原点和坐标轴进行的几何变换。

4

6-2齐次全标

口齐次坐标

将一个原本是〃维的向量用一个〃+i维向量来表示。

■例如：向量（再，巧，…，司）的齐次坐标表示为（〃片,

例，…，Hxn,由，其中跟一个不为。的实数。

■省1的齐次坐标称为规范化齐次坐标；

■反之：由点或向量的齐次坐标（〃入1，〃巧，…，Hxn,

⑼，求它的规范化齐次坐标，可根据如下公式求得

〔=例Hx[H

x/H,•••xn=

□齐次坐标表示法的优点

■修平移、旋转、缩放等变换同统一的方式表示

基洋几何暧族----规范化齐次坐标

口齐次坐标表示就是用n+1维向量表示一个n维向量。

口规范化齐次坐标表示就是h=l的齐次坐标表示。

（X,V）U（X,V,1）

6

7.2二瓶几何变换的齐决坐标表东

口恒等变换

平面图形的恒等变换保持原图形的大小、形状

、位置不变，其变换矩阵为：

1oo

心。=|010

001

基洋几何变换——平移变换

□平移是指将P点沿直线路径从一个坐标位置移

到另一个坐标位置的重定位过程。

x'=x+7

x

图6-1平移变换

8

基洋几何变换——平移变换

-100

设：P'=[/y，l]=[xy1]010

TxTy1

令：T(&7p=[1001

010

工Ty1

记：P'=P*T(&Q

&4称为平移矢量。

基洋几何变换----比例变换

□比例变换是指对p点相对于坐标原点沿X方向放

缩5x倍，沿y方向放缩5y倍o其中5乂和Sy称为

比例系数。%'=S,-X

V=s-

图6-2比例变换(Sx=2,Sy=3)

10

基洋几何变换----比例变换

矩阵形式：「S.00

设：P'=[/y，1]=[xy1]0Sy0

_001.

令：s（鼠与）=]&oo-

0多0

-001-

记：P，=P*S（%5P

S『，历称为比例系数。

11

基洋几何变换----比例变换

(a)Sx=Sy比例(b)Sx<>Sy比例

图6-3比例变换

基洋几何变换一叱例变换

整体比例变换：

100

x!y!1]=[xy1]・010

005

当S>1,图形整体缩小;当S<1,图形整体放大。

基洋几何变换——族籍变换

□二维旋转是指圈P点绕坐标原点转动某个角度（逆时

针为正，顺时针为负)得到新的点p'的重定位过程。

x'=r*cos(a+0)

=r,cose,cosa-r,sin&sina

=x*cos0-y*sin0

y'=resin(a+0)

=r・cos®・sina+r・sine・cosoc

=x*sin6+yecos6

图6-4旋转变换

基洋几何变换——族籍变换

口矩阵形式：逆时针旋转e角

cosOsinO1

设：P、=[x'y'l]=[xy1]-sinOcosO0

[001

令：R(。)=cosOsinG1

-sinOcosO0

001

记：P'=P*R(8)

15

基井几何暧换----二推变换择阵OF

X

T1=Fab］比例、旋转、对称、错切等;

cd；_ax+cy+1

T2=［jm］平移X

T3=p］投影px+qy+s

q_bx+dy+m

T4=\S］整体匕匕伤］

基井几何暧换----对称变换

□对称变换后的图形是原图形关于某一轴线或

原点的镜像。•

A

(a)关于x轴对称(c)关于原点对称

17

基洋几何暧族----对称变换

(d)关于x=y对称

18

基4几何变换—对繇变换

(1)关于X轴对称▲

•P(x,y)

「％Q?9飞-----------►

X

||0)/

।|VC~dxg।•P'(x,-y)

[p/曲1j

图6-6关于x轴对称

19

基洋几何暧族----对称变换

(2)关于y轴对称f

--1oo]P'(-^y)p(*y)

010-----------------------

001

图6-6关于y轴对称

基井几何暧换----对称变换OF

(3)关于原点对称A

A•P(x,y)

--10ol-----------------x

0-10

001

图6-6关于原点对称

21

基井几何暧换----对称变换

(4)关于y=x轴对称

「。10]

100

001

图6-6关于x=y对称

基井几何暧换----对称变换

(5)关于丫=-x轴对称

A

-0-10P(x,y)

-100

P'(%x)\X

001

图6-6关于x=-y对称

23

基井几何暧换----耐切变换

口错切变换,也称为剪切、错位变换，用于产

生弹性物体的变形处理。

图6-7错切变换

24

基井几何暧换----耐切变换

①沿X方向关于Y轴的错切

矩形P1P2P3P4沿X方向错切变换,得到矩形P1P2P3‘pJ错

切角e,点ix,y)变换为：

x'=x+y*tan(0),y'=y

令：shA.=tan(0)■y*tan(0)；

记：_x'y'1_=_xy。100y一1「3的「巴

shY10

-001-

✓

✓

/

✓

----1-z-----------►

Plp2

图6.7沿X方向错切

基井几何暧换----耐切变换

②沿Y方向关于X轴的错切

矩形P1P2P3P4沿丫方向错切变换,得到矩形「逮2,394,错切

角0,点(x,y)变换为：

x'=x,y'=y+x*tan(0)

P\

令：shy=tan(0)

x*tan(O)

记：x，y，L=_xy。1shy0■

77"

010P\

001,4

------V—

,dp2

图6.7沿Y方向错切

基井几何暧换----耐切变换

③沿两个方向的错切

x'=x+y*tan(a)

y'=y+x*tan(0)

令：shY=taxn(a)、ysh=tan(0)

记：x'y'1=xy11sh0y*tan(a)

_i\—_iyv

----p-

shY10

，p4:巧

-001-a/lP\

图6.7沿X、Y方向错切

基井几何暧换----耐切变换

其变换矩阵为：「1b0-

c10

001

(1)沿X方向错切：b=0

(2)沿y方向错切：c=0

(3)两个方向错切：bwO,cwO

28

二箍图形几何变换的计算

几何变换均可表示成P'=P*T的形式。

1.点的变换

abp

x!y!1J=[xy1]•cdq

Imr

29

二箍图形几何变换"算

2.直线的变换

abp

/A11「/Pl11|7

=­caq

xiy2L_x2y2L

Imr

30

二箍图形几何变换"算

3.多边形的变换

X11X11

X2%1X2%1abP

X31X3兀1dq

mr

3几131

31

复合麦换

□图形作一次以上的几何变换，变换结果是每

次变换矩阵的乘积。

□任何一复杂的几何变换都可以看作基本几何

变换的组合形式。

□复合变换具有形式：

P，=p.T=P(T/2T3•…T)

=PTfT2T3...Tn(n>l)

32

复合暧换----二推复合不移

100100

010010

，工2

Ty2

TX1,1Tx2,1

100

010

T,十+T1

X1x2V2

33

复合暧换----二推复合比例

1

Sx1I0o]「Sx200

、・、=*、

Ts=Ts1Ts20s,00sy20

001001

I

sx1•sx2,00

0S-S.0

y1y2

001

34

复合暧换----二推复合族挎

Icose[sin910]「cos3?sin320~|

0!•!-sin9cos90!

—sin/cose[

II

001001

rCOS（0x+。2）sin（圻+2）0]

।-sin（2+%）cos（2+2）0।

001

R=R（a）•R®）=R0十%)

35

复合变换

cos0sin00-)「cos0oonritgeon

R=-sincos00=0cos00--tg010

001J|_001J|_001

itgeoqrcoso0o-

-tg3100cos00

001001

旋转变换等价于先比例后错切，或者先错切后比例。

36

复合变换

□矩阵相乘是符合结合律，但不符合交换律。

A-B-C=(A-B)-C=A"(B-C)

□在连续的同种变换的特殊情况下，矩阵相乘可以符合

交换律。

1.二次连续旋转，可以用任意顺序进行；

2.连续的平移或连续的比例变换可以交换；

3.两向相同(Sx=Sy)的比例变换与旋转变换

Ay

可以交换。

相对低一参考点的二推几何变换OF

□相对某个参考点(XF，F)作二维几何变换，其变

换过程为：

(1)平移；

(2)针对原点进行二维几何变换；

(3)反平移。

38

相对低一参考点的二推几何变换

则:P'=P•(T(-xA,-yA)•S(sx,sy)*T(xA,yA)}

记:

010000

y0010Sy0

)1-XAVA1-yA(『Sy)1_

2.围绕任一基准点的旋转变换

,(11b

A限、R(。)।\I(XA，yQ

A(XA，?)O'\►A—A”

0

AA

则：P'=P-{T(-x,-y)•R(6)-T(X

AAA，yA))

记：R(0)=T(-X,-y)•R(6)•T(x

AAAA，yA)

「・=100cos6sin001oo-

010-singcos00C10

-%YA1

-xAyA1」L001-1L；」

=cos0sin30

-sin3cos00

.JX(1-COS0)+ysin0y(l-cosQ)-xsin0I.

AAAA

相对值一参考点的二箍率

例工错切变换

矩形片44〃沿X轴、Y轴双向错切仪

*

设:tan（0）=2,tan（（I））二l

100110100111010

010210010二21Q

Q鸟x

111001-1-11211①

--

则P'=-1-1r110一-1-1r

3-11210331

-141211941

34113Y1

相对低一参考点的二推几何变换

例2组合变换平面图形变换举例

设△尸3的三个顶点分别为:

尸1(10,20),

鸟(20,20),

乙(15,30),

它绕点0(5,25)逆时针方向旋转30。。它的复合变换

由如下三种变换组成：

(1)平移，使Q移到簿点。，平移常量/=-5,片一

25,平移变换矩阵为：100

4=010

-5-251

相对低一参考点的二推几何变换

(1)平移，使Q移到原点。，平移常量/=-5,片-25,平

移变换矩阵为。，平移变换后的2〃3。

100

4=01o

-5-251

相对低一参考点的二推几何变换

(2)绕原点逆时针旋转30

变换后的1/2产3。

cos30°sin3O°

4=-sin3O°cos30°

00

相对低一参考点的二推几何变换

(3)最后修。点移回原来位置。(5,25),平移变换矩阵为

T3,旋转变换后的△尸*1卜2#*3。

100

010

5251

相对值意方向的二罐几何要换

□相对任意方向作二维几何变换，其变换的过

程是：

(1)旋转变换，使任意方向与某个轴重合；

(2)针对坐标轴进行二维几何变换；

(3)反向旋转，回到原来的方向。

46

①I：平移（0,-Ty）,使L过坐标原点，图形A变换为A1

②Ri：旋转-6,使L与X轴重合，图形A1变换为A?

③RFx：图形A2关于X轴的对称图形A3

@R2：旋转e,图形A3变换为A4

⑤丁2：平移（O,Ty）,使L回到原来的位置，图形A4变换为A5,

此时，是A关于L的对称图形。

总的变换：L•RFX•R2•T2(7.37)

对任意直线的对称变换

设：直线的方程为：ax+by+c=0

则：在X、Y两轴上的截距分别为-c/a和-c/b;

直线的斜率为tga=-a/b。

⑴让直线沿X轴方向平移c/a,使其通过坐标系原点。

变换矩阵为：

100

Tl=010

c/a01

⑵让直线绕坐标系原点旋转-a角,

使与X轴重合。变换矩阵为：

cosa-since0

T2=sinacosa0

001

(3)由于原直线已与X轴重合，于是对于直线的对称

变换即为对于X轴的对称变换。变换矩阵为：

100

T3=0-10

001

(4)绕原点旋转a角，使直线恢复到原倾斜位置。

变换矩阵为：八

cosasma。

T4=-sinacosa°

001

⑸让直线沿X轴方向平移/a,使其回到原来位置。

变换矩阵为：

100

T5=010

-c/a01

综合以上的五步，对任意直线的对称

变换过程为：

[x*y*1]=[xy1]・T1・T2・T3・T4・T5

=[xy1]*T

组合变换矩阵T为：

'cos2asin2a0

T=sin2a-cos2a0

(c/a)(cos2a-1)(c/a)sin2a1

y

相对值意方向的二罐几何要换

□例相对直线y=x的反射变换

T=cos(-45)sin(-45)0100cos(45)sin(45)0

-sin(-45)cos(-45)00-10-sin(45)c0s(45)0

-00iJLo01

-001

55

复合变换

例将正方形ABCO各点沿下图所示的

（0,0）-（1,1）方向进行拉伸（比例变换），结

果为如图所示的，写出其变换矩阵和变换过程。

56

可能发生的变换：沿（0,0）

到（L1）的比例变换

图6Tl沿固定方向拉伸

oO

rcos(-45)sin(-45)0〕「s00"|rcos45°sin45°ol

IooII-S0!-I-sin45°cos45°0!

T=।-sin(-45)cos(-45)0

°r|y|II

001001001

P'=P・T

坐标系之间的变换

问题：已知XOY坐标系上的P(Xp,yp),求P转换到

坐标系上的P，(x1,y')。

图6-9坐标系间的变换

58

坐标系之间的变换

分析:

在xoy坐标系中有点p*,其y▲

坐标与p点在x，o，y，坐标系下P.也即p'

y

的坐标相等：X

5

op/=opx;*

Opg*Px

OPy*=O'Py；y□e

则P*点的坐标是P点变换到P9O'(xo,yo)

点的坐标。

o*X

叽

图6To坐标系间的变换的原理

59

图6T4坐标系间的变换的步骤

于是:

p'-xfyf1-xy1-T

LppPP

-p-T-p-T-T

tR

-100cos0-sin0

T=Tt-Tr=010•sin3cos00

1001

光栅变换

□直接对帧缓存中象素点进行操作的变换称为光

栅变换。

□光栅平移变换：

tsi

，★

（a）读出象素块的内容（b）复制象素块的内容（c）擦除原象素块的内容

图6-12光栅平移变换62

光栅变换

□90°、180°和270。的光栅旋转变换:

(vollen-y,x)

yvo

(r(wlen-x,vollen-y)

^vollen

row1en

(a)逆时针旋转90°(b)逆时针旋转180°

①每行像素值颠倒——擦掉;①每行像素次序颠倒;

②交换其行列。②行的次序颠倒。

图6-13光栅旋转变换63

64

光栅变换

图6-15光栅比例变换

根据Sx和Sy的大小,取出对应于变换后图像中的一个像素点的原图

中的相应像素区域，对其区域的像素点的亮度加权平均，得变换后

像素的亮度。

变换的辘质

二维仿射变换是具有如下形式的二维坐标变换:

x'=ax+by+m

<

y'-ex+dy+n

□平移、比例、旋转、错切和反射等变换均是二

维仿射变换的特例，反过来，任何常用的二维

仿射变换总可以表示为这五种变换的复合。

66

变换的辘质

口仅包含旋转、平移和反射的仿射变换维持角度

和长度的不变性；

□比例变换可改变图形的大小和形状；

口错切变换引起图形角度关系的改变，甚至导致

图形发生畸变。

67

二箍理察

□基本概念

□二维观察变换

□二维裁剪

□OpenGL中的二维观察

68

二箍理察

□坐标系

鼻模坐标系(MC,ModelingCoordinateSystem)

用户坐标系(WC,WorldCoordinateSystem)

I直角坐标系(又称笛卡尔坐标系)

坐标系［"极坐标系

观察坐标系(VC,ViewingCoordinateSystem)

规范化坐标系(NDC,NormalizedCoordinate

System)

设备坐标系(DC,DeviceCoordinateSystem)

二箍理察

□坐标系

1.建模坐标系(MC,ModelingCoordinates)

依据物体而建的局部坐标系，是直角右手坐

标系，长度单位用户自定，取值范围整个实数

域。

2.世界坐标系(WC,WorldCoordinates)

又称用户坐标系，场景采用的坐标系，是直

角右手坐标系，长度单位用户自定，取值范围

整个实数域。

二箍理察

□坐标系

3.设备坐标系(DC,DeviceCoordinates)

依设备而定的坐标系，是二维直角坐标系，原点和轴

的定义依设备不同而不同，长度单位是设备的步距，取

值范围有限的整数。

4.规格化设备坐标系(NDC,NormalizedDeviceCoordinates)

_一种虚拟的坐标系，与具体设备无关，其取值范围在

0一1之间，起到嚼WC与DC联系起来的作用。

用户的绘图数据经过转换成NDC中的值，使得图形有

了统一的设备空间。这对图形的统一处理，带来很大的

方便，从而提高图形程序的可移植性。

二箍理察

□坐标系gDC

MC、WC、NDC、DC之间的转换

X

MC

图二维场景从模型坐标系到设备坐标系的变换序列

(Xmc.Ymc)->(Xwc.Ywc)->(Xndc，丫ndc)->(Xdc.Ydc)

二箱理察----基存概念

口窗口

在世界坐标系(WC)中，指定或选取一个矩形区域(Window)

□视区

在规格化设备坐标系(NDC)或设备坐标系(DC)上，指定一

个矩形区域(ViewPort),用于显示窗口内的图形。

口开窗口

先将图形关于窗口进行裁剪，然后将裁剪后的保留在窗口

内的图形，变换成显示器屏幕上指定视区内的图形。

开窗变换也叫取景变换，它包括裁剪运算和窗口到视区的

变换。

二箱理察----基存概念

(b)屏幕坐标系中的视区

□要将窗口内的图形在视区中显示出来，必须经过将窗口到

视区的变换(Window-ViewportTransformation)处

理，这种变换就是观察变换(Viewing

Transformation)。

74

图6-17用户坐标系中旋转的窗口

八

3

Q

N

1

视区

1xNDC

(a)观察坐标系(b)规格化设备坐标系

二箱理察----基存概念

□观察坐标系(ViewCoordinate)是依据窗口的方

向和形状在用户坐标平面中定义的直角坐标系O

□规格化设备坐标系(NormalizedDevice

Coordinate)也是直角坐标系，它是将二维的设

备坐标系规格化到(0.0,0.0)到(1.0,

1.0)的坐标范围内形成的。

76

二箍机察----基存概念

□引入了观察坐标系和规格化设备坐标系后，观

察变换分为如下图所示的几个步骤，通常称为

二维观察流程。

应

用

察

坐

观窗口到视

程

序用户坐视图区从

系

下

标区（规范

到

图标系到规范化坐在图形

窗

口

VC对VC化设备坐NDC

形

的观察坐标系到设斗设备上

行

裁

进标系中定

用

户标系间备坐标系输出

剪义）的变

坐

标的变换的变换

图6-19二维观察流程

77

二旗机察----基4就念

□变焦距效果

(b)与窗口对应

的视区1

(a)原图及变化的窗口

图6-20变焦距效果(窗口变、视区不变)

视区大小不变，当窗口变小，放大显示；当窗口变大,

缩小显示，则产生焦距(又称变焦)缩放的效果；

78

二旗机察----基4就念

□整体放缩效果

(b)视区1

(a)原图及窗口图6-21整体放缩效果(窗口不变、视区变)

口漫游效果

视区大小不变，窗口大小不变，只改变窗口位置，则产

生摇镜头(又称漫游)的效果。

79

用户生标东♦!也零坐标东的变换

□用户坐标系到观察坐标系的变换分由两个变

换步骤合成：

♦平移：将观察坐标系原点移动到用户坐标

80

用户生标东♦!也零坐标东的变换

♦旋转：绕原点旋转使两坐标系重合

/k

旺

Xk

(b)旋转变换

81

用户生标系割视察坐标东的麦族

假设观察坐标系的原点在用户坐标系中的坐

标为（Xo，yo）,观察坐标系与用户坐标系之间的

夹角为6,则变换矩阵为：

100］「cos0一sin。0

T=T""01o|.|sinQcos60

——歹01001

82

CS

窗口利视成的变换

X

DCS

图6.23窗口-视区变换示意图

观察窗口左下角（xW[,yWb）,右上角（xw〃ywt）。

视区左下角（Xv[,yvb），右上角（Xvr'vt）。

窗口制祝成的变换

要求画面相对比例保持不变。

窗口内点&亚,yw)映射到视区(xv,yv),应满足:

('川一'wmi，/('wmax~^wmin^——XymiP/(Xymax~^vmin^

(YJ~/(ywmax一ywfl4n)-(Vy—yvmiP

窗口割视成的变换

[('vmax—Xymin)^wmax一'wmiP1*-^wmin^X-

Xvvmin

yv—I-vmaxvmin^^wmax一丫亚暄11)】*ywmiPDvinin

简化：Xv=A-xw+B

Yv=C-yw+D

其中.卜一('vmax—Xynii，^wmax~^wmin^

B-Xvmin一xwnun"A

ywiniJ

C=(Yvmax-yvmin)/^wmax

DorninYwmin式

窗口割视成的变换

□将窗口内的点(Xw，。)映射到相对应的视区内的点

(xv/yv)需进行以下步骤：

(1)4号窗口左下角点移至用户系统系的坐标原点，平移矢量

为(-Xwl，-Ywb),

(2)针对原点进行比例变换，使窗口大小与视区相等，比例

因子为：Sx二(又丫L乂丫“色加-乂喇)

s

y=(yvt-yvb)/(ywt-ywb)

(3)进行反平移，使窗口与视区重合，平移矢量为(-Xvi.-

Yvb)0

86

窗口割视成的变换

窗口到视区的变换:

N=T

wc->DCi(-xwh-ywb)•S(Sx.Sy)•T2(-xvh-yvb)

=A0O-

0C0

/这里：A、C称为比例因子，

_BD1.B、D称为平移因子

其中:A二(x-x|)/(x-x|)

vrvwrw/当A=C,窗口到视区的映射,

可以保持在X、Y两方向有相

c=(yvt-yvb)/(ywt-Ywb)同的比例；

/当则保持图形变换

D二yvb-ywbcA=C=1,

前后大小保持不变。

口在二维观察中，需要在观察坐标系下对窗口进行

裁剪，即只保留窗口内的那部分图形，去掉窗口

外的图形。

口假设窗口是标准矩形，即边与坐标轴平行的矩形,

由上（yMWyt）、下（y=Wyb）、左（x=Wxi）、

右（X=Wxr）四条边描述。

□点（X,y）在窗口内，则满足：Wx）<X<Wxr、

wyb<y<wyto

88

二旗直核段的栽噌

已知条件:

(1)窗口边界wxl,wxr,wyb,wyt的坐标值;

(2)直线段端点pip2的坐标值、1,1，々，丫2。

图6.24直线段与窗口的3种关系89

Pz

X

图6.25直线段与窗口边界的2种交点

□实交点：直线段与窗口矩形边界的交点；

口虚交点：处于直线段延长线或窗口边界延长线上

的交点。

□直线裁剪的基本原理

1.首先确定哪些直线全部保留或全部裁剪；

2.对于部分裁剪的直线，应求出直线与窗口边界的

交占-

八、、）

3.把从交点开始到边界外的部分裁剪掉。

□常用裁剪算法

1.Cohen-Sutherland裁剪算法（又称编码裁剪算法）

2.中点分割算法

3匚参数化算法（Liang-Barsky算法）

91

Cohen-Sutherland算收

□基本思想

对于每条线段P1P2分为三种情况处理分为三种情况

处理：

1.若PR2完全在窗口内，则显示该线段P』2简称“取

”之。

2.若PR2明显在窗口外，则丢弃该线段，简称“弃

力之。

3,若线段不满足“取”或“弃”的条件，则在交点

处把线段分为两段。其中一段完全在窗口外，可弃

之。然后对另一段重复上述处理。

Cohen-Sutherland算收

□编码

对于任一端点(x,y),根据其坐标所在的区域,

赋予一个4位的二进制码D3D2DQ0。

3210

编码规则如下:

(1)D0=l,否则Do=O;

(2)若x>wxr,D]=l,否则D]=0;

若y〈wyb,D2=l,否则口2=0；

(4)若y>wyt,D3=l,否则口3=0。

wxlwxr

320

1010

0010

0110

Cohen-Sutherland算收

（1）判断

裁剪一条线段时，先求出直线段端点火和Pz的编

码codel和code2，然后：

①若codel|code2=0,表明pi和p2区域码都为0000,

Pi和P2完全在窗口内，则对直线段简取之；

②若codel&code2wO,表明p1和p2区域码至少在某

一位上同为1,Pi和P2完全在窗口外，则对直线段简

弃之；

95

Cohen-Sutherland算收

(2)求交

若上述判断条件不成立，则需求出直线段与窗口

边界的交点。

通常检测PL如果P1在窗口外，则从低到高的顺

序检测P1的编码CODEL根据值为1的编码位确定

与P1P2求交的窗口边界，按左右上下边界情况求出

交点代替pL用新的P1P2重新计算；如果P1在窗口

内(即编码为全0),贝I将P1和P2交换，继续求交。

96

Cohen-Sutherland算收

(2)求交

设：已知一条端点为(xl,yl)和(x2,y2)的直线：

①左边界(X=XW|)＞右边界(x=xwr)交点的计算:

y=yl+k(x-xl);

②上边界(y=ywb)＞下边界(丫=丫比)交点的计算:

x=xl+(y-yl)/k;

其中，k=(y2-yl)/(x2-xl)o

97

Cohen-Sutherland算收

□计算线段Pl(xl,yl)P2(x2,口)与窗口边界的交点,其区域

码分别为codel和code2。

if(codel!=0)code=codel;elsecode=code2;

if(LEFT&code!=0)

{x=XL;y=yl+(y2-yl)*(XL-xl)/(x2-xl);}

elseif(RIGHT&code!=0)

{x=XR;y=yl+(y2-yl)*(XR-xl)/(x2-xl);}

elseif(BOTTOM&code!=0)

{y=YB;x=xl+(x2-xl)*(YB-yl)/(y2-yl);}

elseif(TOP&code!=0)

{y=YT;x=xl+(x2-xl)*(YT-yl)/(y2-yl);)

这里：LEFT=000KRIGHT=0010.BOTTOM=0100.TOP=1000

Cohen-Sutherland算收

Cohen-Sutherland算收

□用编码方法实现了对完全可见和不可见直线

段的快速接受和拒绝；

□求交过程复杂，有冗余计算，并且包含浮点

运算，不利于硬件实现。

100

中点台制算位

□中点分割算法的

核心思想是通过

二分逼近来确定

直线段与窗口的

交占八、、。

101

中豆今制算该

口基本思想

是Cohen-Sutherland算法的改进，为了避免使用乘除法求

直线段与窗口边界的交点，用不断对分线段的方法排斥线段

在窗口外的部分，最后求出离线段端点最远的可见点（所谓可

见点就是线段落在窗口内的点），若这两点存在，则这两点就

是线段PiP2的可见线段端点。出口图：A、B分另U为笈巨pi、p2最

近的可见点,Pg为P〃2中点。

中点台制算位

首先对线段端点进行编码，并把线

段与窗口的关系分为三种情况：

①线段PR2全在窗口内，保留；

②线段PR2完全在窗口外，不保留；

③线段和窗口有交，用中点分割的

方法求出线段与窗口的交点。

■用中点分割的方法

将线段等分为二段，作①、②、

③处理。直至每条线段要么完全在

窗口内，要么完全在窗口外为止。

求从々出发寻找最远的可见点的步骤：

设：线段的端点在窗口内称为可见点，其区域码为

0000。

(1)测试2是否在窗口内。若是，则22就是离々最远的

可见点，结束；否则，进行下一步。

(2)对夕1、片的区域码作逻辑与，若结果不为0,表明

P、、片是在窗外同侧，线段乙4全部不可见，弃之，结

束；否则，进行下一步。

（3）取尸14的中点4（（XI+X2）/2,（yi+yP/2）,若《可见，

则以代替尸1，重复步骤（3）;若乙不可见，则需要判断乙和

尸2的关系：

•如果乙和鸟在窗口的同侧外面（即月〃、尸2的区域码逻

辑与不为0）,则4代替尸2，重复步骤（3）;

•如果乙和鸟不在窗口的同侧外面（即以、鸟的区域码

逻辑与为0）,则4代替尸］,重复步骤（3）;

（4）一直