第三章(3D图形-变换)

第三章、三维图形3.1坐标系3.2三维变换3.3坐标系变换3.4投影变换3.5视变换3.6三维剪取3.7消隐第三章1第三章2坐标系坐标系现实的物体具有高度、宽度、和深度。它们可以用三维坐标系的x轴、y轴和z轴来表示。三维坐标系是一个直角坐标系；坐标系内任何一点可以由一个有序的三元组(x,y,z)来表示。每个坐标表示该点与坐标原点之间沿相应坐标轴的正向或反向的距离。在现实世界中，人们通常使用右手坐标系表示物体的位置，因此它又经常被称为世界坐标系(WorldCoordinateSystem)。在计算机图形显示时，一般采用另一种三维坐标系：计算机的屏幕是一个平面。指定它的左下角为原点，x轴正向向右延伸，y轴正向向上延伸。另外，定义z轴从原点开始，指向屏幕内部，表示深度。这个坐标系称作左手坐标系。zxyxyz第三章3三维图形3.2

三维变换

一、平移变换二、缩放变换三、旋转变换四、变形变换第三章4平移变换平移变换每个三维点(x,y,z)对应于一个齐次坐标[x,y,z,1]。所有的三维变换都可通过乘以一个4×4的变换矩阵来进行。平移变换

点(x,y,z)沿x轴方向平移Tx距离，沿y轴方向平移Ty距离，沿z轴方向平移Tz距离，变成点(x´,y´,z´)，这一变换过程的变换矩阵为:

T3(Tx,Ty,Tz)=

[x´,y´,z´,1]=[x,y,z,1]×T3[Tx,Ty,Tz]=[x+Tx,y+Ty,z+Tz,1]1

0

0

0

0

1

0

0

0

0

1

0

TxTyTz1TxTzTy第三章5三维图形3.2

三维变换

一、平移变换二、缩放变换三、旋转变换四、变形变换第三章6缩放变换缩放变换几何图形的三维缩放变换是通过对构成图形的各个点同时进行坐标值的缩放来实现的。设一个点沿x,y,z轴缩放的比例分别为Sx,Sy,Sz,则缩放变换矩阵可表示为：

S3(Sx,Sy,Sz)=

[x´,y´,z´,1]=[x,y,z,1]×S3[Sx,Sy,Sz]=[x·Sx,y·Sy,z·Sz,1]当|Sx|,|Sy|,|Sz|分别大于1时，为物体的放大，小于1时，为缩小变换;

当|Sx|,|Sy|,|Sz|皆等于1时，即为恒等变换；

当|Sx|,|Sy|,|Sz|分别小于0时，作相应坐标轴的镜面变换。Sx0

0

0

0

Sx0

0

0

0

Sx0

0

0

0

1第三章3三维图形3.2

三维变换

一、平移变换二、缩放变换三、旋转变换四、变形变换第三章8旋转变换绕坐标轴旋转旋转角度θ为正时，点的旋转方向：在右手坐标系中

旋转轴 相应的旋转方向

x轴 从y轴到z轴

y轴 从z轴到x轴

z轴 从x轴到y轴在左手坐标系中

从旋转轴的正向看去，旋转方向是顺时针方向。

这样定义旋转方向的原因是为了保证无论在在

右手坐标系中还是在左手坐标系中，所用的旋

转矩阵是相同的。yzxzxy第三章9旋转变换绕坐标轴旋转绕z轴旋转的变换矩阵是

Rz(θ)=绕x轴旋转的变换矩阵是

Rx(θ)=

绕y轴旋转的变换矩阵是

Ry(θ)=cosθ

sinθ

00

-sinθ

cosθ

0

0

0

0

1

0

0

0

0

11

0

00

0

cosθ

sinθ

0

0

-sinθ

cosθ

0

0

0

0

1cosθ

0

-sinθ

0

0

1

0

0

sinθ

0

cosθ0

0

0

0

1第三章10旋转变换绕任意轴旋转求绕任意直线旋转矩阵的原则任意变换的问题基本几何变换的问题饶任意直线旋转的问题绕正轴旋转的问题第三章10旋转变换绕任意轴旋转yzxP1P2P´1P´2zyxP´2(a,b,c)P´´2abcyxzP´´2αyxzθ第三章10旋转变换绕任意轴旋转绕直线P1P2旋转θ角的过程可分解为下列步骤：把点P1

(x1,y1,z1)移至原点；绕x轴旋转，使直线与xz平面重合；绕y轴旋转，使直线与z轴重合；绕z轴旋转θ角；执行步骤(3)的逆变换；执行步骤(2)的逆变换；执行步骤(1)的逆变换；第三章11旋转变换绕任意轴旋转步骤(1)把点P1(x1,y1,z1)移至原点:变换矩阵为：

T3(-x1,-y1,-z1)=

步骤(2)绕x轴旋转，使直线与xz平面重合：设此刻P2(x2,y2,z2)的坐标变为P’2(a,b,c)。可知 cosφ=c/(b2+c2)1/2；sinφ=b/(b2+c2)1/2；

设d1=(b2+c2)1/2，则变换矩阵为:

Rx(φ)=1

0

0

0

0

c/d1b/d10

0

-b/d1c/d10

-x1

-y1

-z111

0

0

0

0

1

0

0

0

0

1

0

-x1-y1-z11yzxP1P2P’1P’2zyxP’2(a,b,c)P’’2abc第三章12绕任意轴旋转步骤(3)绕y轴旋转，使直线与z轴重合：

此刻P’2的坐标为P’’2(a,0,d1),可知：

cosα=-d1/(a2+d12)1/2=(b2+c2)1/2/(a2+b2+c2)1/2；

sinα=a/(a2+b2+c2)1/2；

令d2

=(a2+b2+c2)1/2，则变换矩阵为:

Ry(α)=

步骤(4)绕z轴旋转θ角，变换矩阵为:

Rz(θ)=旋转变换d1/d2

0

a/d2

0

0

1

0

0

-a

0

d1/d2

0

0

0

0

1cosθ

0

-sinθ

0

0

1

0

0

sinθ

0

cosθ0

0

0

0

1yxzyxzP’’2(a,0,d1)αθ第三章13绕任意轴旋转步骤(5)执行步骤(3)的逆变换,变换矩阵为Ry(-α)；步骤(6)执行步骤(2)的逆变换,变换矩阵为Rx(-φ)；步骤(7)执行步骤(1)的逆变换,变换矩阵为T3(x1,y1,z1)；

综上，绕直线P1P2旋转θ角的变换矩阵为：

R(θ)=T3(-x1,-y1,-z1)Rx(φ)Ry(α)Ry(θ)Ry(-α)Rx(-φ)T3(x1,y1,z1)注意：变换的过程有多种选择，但如果中间的几个旋转次序变了，则各个矩阵参数的对应矩阵参数也会完全不同。旋转变换第三章14三维图形3.2

三维变换

一、平移变换二、缩放变换三、旋转变换四、变形变换第三章15变形变换变形变换对于过原点的一条直线，如果希望把它

变换成另一条不同的过原点的直线，可

以通过变形变换来实现。它可以产生变形

的效果。例如：一个正方体可通过三维变形变换变成一个平行六面体。这里只考虑比较简单的情况。把一条不在x，y平面上的过原点的直线变换成z轴，对应的z轴坐标都保持不变。这样z-变形变换的矩阵可以考虑在yoz平面和xoz平面上的组合变形情况。zxy第三章15变形变换变形变换对于yoz平面上的变形情况，考虑直线y=-bz， 则变形后的直线方程为：

y’=y-(-bz)=y+bz z’=z对于xoz平面上的变形情况，考虑直线x=-az， 则变形后的直线方程为：

x’=x-(-az)=x+az z’=zzyy=-bzzxx=-az第三章15变形变换变形变换则z-变形变换的矩阵表达式如下：

shz=

其中a,b参数由直线方程所决定。设直线上任一点P(x1,y1,z1)≠0经过z变形变换，将变成P(0,0,z1)，即：

[x1,y1,z1,1]×shz=[x1+az1,y1+bz1,z1,1]=[0,0,z1,1]

即 x1+az1=0 则 a=-x1/z1 y1+bz1=0 b=-y1/z1如果该直线位于x，y平面，则z1=0，无法把它变换成z轴。1000

0100

ab10

0001zxy第三章16坐标系变换坐标系变换同一物体在不同的坐标系中描述时，会有不同的坐标值。在甲坐标系中定义一个物体，那么只要把乙坐标系的坐标轴变换成甲坐标系的坐标轴，就可以在乙坐标系中定义物体了。坐标系平移例1：新坐标系x’o’y’的原点o’在坐标系xoy的坐标为(2,4),则从x’o’y’到xoy的变换矩阵为T2(-2,-4),xoy坐标系中一点P(4,5),在x’o’y’坐标系中的坐标矢量为：

[4,5,1]×T2(-2,-4)=[2,1,1]

yy’oo’x’xP(4,5)(2,4)第三章16坐标系变换坐标系变换坐标系旋转例2：x’o’y’坐标系与xoy坐标系原点重合，将x’o’y’坐标系逆时针旋转45°就变成了xoy坐标系，则变换矩阵为：

R(π/4)= =cosπ/4

sinπ/4

0

-sinπ/4

cosπ/4

0

0

0

121/2/2

21/2/2

0

-21/2/2

21/2/2

0

0

0

1y’xx’yo(o’)45。第三章17坐标系变换坐标系复合变换例3：求变换矩阵为平移矩阵和旋转 矩阵的乘积矩阵：

T2(-2,-4)×R2(π/4)分析 根据旋转矩阵， 其中，第一列(cosπ/4,-sinπ/4,0)和第二列(sinπ/4,cosπ/4,0)分别是新坐标x’轴和y’轴在原坐标中方向矢量，且为正交单位矢量。坐标系变换cosπ/4

sinπ/4

0

-sinπ/4

cosπ/4

0

0

0

1yy’oo’x’x第三章17坐标系变换三维坐标的推广比较适合于给出了旋转角度或很容易求出旋转角度的情况在新坐标系的旋转角度没有给出时，且不易计算。这时一般会给出新坐标系的原点坐标和三个坐标的方向矢量。坐标系变换坐标系变换把给出的新坐标的3个方向矢量分别规格化，

得到用原坐标系定义的3个正交单位矢量： u=(ux,uy,uz)

v=(vx,vy,vz)

w=(wx,wy,wz)

新的坐标原点位置是(x,y,z)，则变换矩阵为：

T3×R3=

1

0

0

0

0

1

0

0

0

0

1

0

-x

-y

-z

1ux

vx

wx

0

uy

vy

wy

0

uz

vz

wz

0

0

0

0

1第三章18坐标系变换XYZWZVYUX(X,Y,Z)第三章18三维图形3.4

投影变换

一、概述二、平行投影三、透视投影第三章19概述概述要把现实世界的三维物体在计算机的二维屏幕上显示出来，必须经过投影变化这一步骤，把物体从三维表示形式转化为二维表示形式。投影变换常用平行投影以及透视投影、椎顶投影等多种。投影面投影中心投影线ABA’B’投影面投影中心投影线ABA’B’第三章20三维图形3.4

投影变换

一、概述二、平行投影三、透视投影投影变换根据投影线是否平行，

可分为：正平行投影斜平行投影等距平行投影

正平行投影

投影方向垂直于投影平面时称为正平行投影

三视图（正视图、顶视图、侧视图）均属于正平行投影第三章21平行投影正平行投影顶视图侧视图正视图第三章22平行投影正平行投影三视图的生成就是把x、y、z

坐标系下的形体投影到z=0的平面，变换到u、v、w

坐标系。一般还需将三视图在一个平面上画出。zyxa2c2b2a1b1c1第三章22平行投影正平行投影变换矩阵（其中(a,b)为u、v坐标下的值） 正视图(uvw1)=(xyz1)顶视图(uvw1)=(xyz1)

侧视图(uvw1)=(xyz1)-1

0

0

0

0

-1

0

0

0

0

0

0

a-tx

b-ty

0

10

0

0

0

1

0

0

0

0

1

0

0

a+ty

b+tz

0

1-1

0

0

0

0

0

0

0

0

1

0

0

a-tx

b+tz

0

1uzyyxozyyxoo’vtztztxtxtyty(a,b)第三章23平行投影斜平行投影如果投影方向不垂直于投影平面，则称为斜平行投影。在斜平行投影中，投影平面一般取坐标平面。以下用两种方法推导斜平行投影的公式。设投影方向矢量为(xp,yp,zp),若形体被投影到xoy平面上，形体上的一点为(x,y,z)，要确定其投影(xs,ys)。可知投影线的方程为：

xs=x+xp·t 因为(xs,ys,zs)在z=0平面上，故t=-z/zp,

ys=y+yp·t 由此 xs=x-xp/zp·z

zs=z+zp·t ys=y-yp/zp·z若令Sxp=xp/zp,Syp=yp/zp,则有：

[xs,ys,zs,1]=[x,y,z,1]

1

0

0

0

0

1

0

0

-Sxp-Syp1

0

0

0

0

1yzx(xs,ys)(x,y,z)(xp,yp,zp)第三章24平行投影斜平行投影在左手坐标系中求斜平行投影的坐标变换

设其投影平面为xcocyyc，立方体上的一点P(0,0,1)在平面xcocyycxcocyyc上的坐标为P’(lcosα,lsinα,0)，投影方向为PP’，与投影平面的夹角为β，其方向余弦为(lcosα,lsinα,-1)。现考虑任意一点(xc,yc,zc)在平面xcocyyc上的投影(xs,ys)，因为投影方向与投影线平行，且投影线的方程为：

zc-zs

yc-ys

xc-xs

───=───=───

-1 lsinαlcosα

且zs=0，所以xs=xc+zc(lcosα)，ys=yc+zc(lsinα)矩阵形式为：

[xsyszs1]=[xcyczc1]1

0

0

0

0

1

0

0

lcosαlsinα0

0

0

0

0

1xcyczcocαlzcαycxcP’P(0,0,1)βl第三章25三维图形3.4

投影变换

一、概述二、平行投影三、透视投影一点透视两点透视第三章26透视投影透视投影单位立方体透视投影的视线是从视点(观察点)出发，视线是不平行的，透视投影按照灭点的个数分为一点透视，两点透视和三点透视。任何一束不平行于投影平面的平行线的投影将汇聚在一点称之为灭点，在坐标系上的灭点称为主灭点。第三章27透视投影透视投影主灭点数是和投影平面切割坐标轴的数量相对应的。如投影平面仅切割z轴，则z轴是投影平面的法线，因而只在z轴上有一个灭点，平行于x轴或y轴的直线也平行于投影平面，因而没有灭点。yxzo第三章28透视投影一点透视假设投影中心为原点，投影面平行于xy平面，方程为z=D。设物体上一点P(x1,y1,z1),它的投影点为P´(x´,y´,z´)，则z´=D。投影线的方程为:

x=x1t

y=y1t

z=z1t： 把z=D代入的，得t=D/z1,则:

x1

y1

x=─×D；y=D×─

z1

z1xyDzP´(x´,y´,z´)P(x1,y1,z1)第三章29透视投影一点透视得到投影点的坐标为：((x1/z1)D,(y1/z1)D,D),由相似三角形原理，得：x´/x1=y´/y1=D/z1即：

x1

y1

x´=─×D；y´=─×D

z1

z1

若D固定，z1↑，则x´↓，y´↓即对象越远，成像越小。若视点取无穷远(z≈D)时，则：x´=x，y´=y

此时，透视投影变为正交平行投影Doxzz1P´(x´,y´,z´)P(x1,y1,z1)投影面Doyzz1P´(x´,y´,z´)P(x1,y1,z1)投影面第三章26透视投影一点投影Per(D)=

由上面分析，设透视投影的变换矩阵为：齐次点P[x,y,z,1]乘以矩阵Per(D)，得到：

x´=x/z·D

y´=y/z·D

z´=D

与前面的结果相吻合。1

0

0

0

0

1

0

0

0

0

1

1/D

0

0

0

0xyDzP´(x´,y´,z´)P(x1,y1,z1)第三章31三维图形3.5

视变换

一、数学预备知识二、视变换参数三、视变换矩阵四、剪取五、透视投影第三章32数学预备知识矢量点积设v1(x1,y1,z1)和v2(x2,y2,z2)是两个三维矢量，则其点积定义为： v1·v2=x1x2+y1y2+z1z2 （标量）矢量v(x,y,z)的长度定义为：

|v|=(v·v)1/2=(x2+y2+z2)1/2两个矢量间所成的角θ的余弦值可通过矢量长度和点积来表示 v1-v2

cosθ=

────或v1·v2=|v1|·|v2|·cosθ

|v1|·|v2|

当v1与v2相互垂直时，点积为0。θv1v2第三章33数学预备知识矢量点积点积具有分配律： 设u,v,w为3个矢量，r为实数。有： u·(v+rw)=u·v+r(u·w)构造一个新矢量： 给定长度为1的单位矢量n和一个不平行于n的矢量w，则w在垂直于n的平面上的投影v表示为:

v=w-(n·w)·n

证明：n·v=n·(w-(n·w)·n) =n·w-(n·w)(n·n) =n·w-(n·w)·l2=0 所以v垂直于n。wnv(n·

w)n第三章34数学预备知识矢量叉积矢量叉积定义如下：

v1×v2=(y1z2-z1y2,z1x2-x1z2,x1y2-y1x2)（矢量）2个互不平行的矢量，其叉积形成一个与2个矢量都垂直的新的矢量，它的方向符合右手判别法如果v1平行于v2，则

v1×v2=(0,0,0)v1xv2v1v2第三章35三维图形3.5

视变换

一、数学预备知识二、视变换参数三、视变换矩阵四、剪取五、透视投影第三章36视变换参数视变换参数右手世界坐标系：在进行视变换时，需要一系列的参数来确定投影面的位置、方向和投影中心的位置。这些参数用来定义右手世界坐标系定义视平面（也称投影面）：由平面上的一点和平面的法线来定义。视平面上的点为视图参考点(VRP)，视平面法线为平面方向(VPN)定义左手眼睛坐标系：（用于投影变换）轴VPN：一根坐标轴方向就是视平面的法线方向轴v：用一条不平行于的VPN视图上方矢量(VUP)在视平面上 的投影来构造，即：v=VUP-(VPN·VUP)VPN轴u：使得u,v,VPN形成一个左手坐标系，即VPN,v,u形成一 个右手坐标系，则：u=VPN×vVPNVUPVRPuvCOP视平面视平面窗口第三章37视变换参数窗口和投影中心定义了一个无限四棱锥体，称为视体积只有在视体积内的物体才会被投影到视平面窗口内显示出来通过制定平行于视平面的前后剪取平面来截取视体积，以删除离视平面过近和过远的物体这样视平面体积是有限的视变换参数后剪取窗口视平面窗口前剪取窗口BFCOP第三章38三维图形3.5

视变换

一、数学预备知识二、视变换参数三、视变换矩阵四、剪取五、透视投影第三章39视变换矩阵视变换矩阵把右手世界坐标系里的图像变换为左手眼睛坐标系里的图像的全过程如下：

用三维世界坐标系定义图像模式变换把图像变成三维眼睛

坐标系，原点为观察

者，观察方向为Z轴视变换

截取视体积，执行三维剪取剪取

执行透视投影，

把三维物体投

影到视平面上投影变换视窗口内图像变

换到屏幕坐标系

加以显示显示第三章40视变换矩阵模式变换在变换开始时，输入视变换参数：视图参考点(VRP)，视图上方矢量(VUP)和投影中心(cop)，然后输入视窗口在u,VPN,v坐标系中的位置：输入窗口坐下角的位置(umin,vmin)和右上角的位置(umax,vmax)；

以及输入前后剪取平面与视平面的距离F和B：

计算矢量u,v。v为VUP

在视平面上的投影。先

把视平面方向矢量进行

规格化，再计算v,u：

v=VUP-(VPN·VUP)VPN

u=VPN×vVPNVUPVRPuvcop视平面视平面窗口当F<0时 当F>0时

前剪取平面

前剪取平面

视平面

视平面

后剪取平面

后剪取平面FFBB第三章41视变换矩阵视变换视变换的目的是：把以cop为原点，

为坐标轴方向的左手系变换成右

手世界坐标系。变换矩阵是一个平

移矩阵和一个旋转矩阵的乘积。设

左手坐标系原点cop在世界坐标系中的坐标为：(VRP[x]+cop[x],VRP[y]+cop[y],VRP[z]+cop[z])则此平移矩阵为：

T=1

0

0

0

0

1

0

0

0

0

1

0

-(VRP[x]

-(VRP[y]

-(VRP[z]

1

+cop[x])

+cop[y])

+cop[z])

uVPNvcopuVPNvVRPzxoyzxoyuVPNvcopuVPNvVRP第三章42视变换矩阵视变换设u,v,VPN为规格化后的3个

正交单位矢量,则旋转矩阵为：

R=

改变z轴符号的矩阵为：

ch=

R与ch相乘得到的矩阵：

Rot=

经过以上三步，视图参考点VRP变换为视平面上的点VRP´:VRP´=VRP×T×R×ch=VRP×T×Rotu(x)

v(x)

-VPN(x)

0

u(y)

v(y)

-VPN(y)

0

u(z)

v(z)

-VPN(z)

0

0

0

0

11

0

0

0

0

1

0

0

0

0

-1

0

0

0

0

1u(x)

v(x)

VPN(x)

0

u(y)

v(y)

VPN(y)

0

u(z)

v(z)

VPN(z)

0

0

0

0

1xzoyuVPNvcopuVPNvVRPzxoyuvcop

视方向中心还要进行z-变形变换，使视方向与z轴平行。首先，计算出视平面窗口相对于的位置VRP´的中心：

Ucenter=(umin+umax)/2

Vcenter=(vmin+vmax)/2

它在左手眼睛坐标系中的x,y坐标为： Center[x]=VRP´[x]+(umin+umax)/2

Center[y]=VRP´[y]+(vmin+vmax)/2

所以得到变换的变换矩阵：

sh=

窗口右上角xy坐标为：

x=(Umax-Umin)/2

y=(Vmax-Vmin)/21

0

0

0

0

1 0

0

-Center[x]/VRP´[z]

-Center[y]/VRP´[z]

1

0

0

0

0

1zxoyuvcop

视方向中心视线方向中心zxy第三章43视变换矩阵视变换第三章44三维图形3.5

视变换

一、数学预备知识二、视变换参数三、视变换矩阵四、剪取五、透视投影第三章45剪取剪取先对图像在视体积内的部分进行三维剪取。第一步是要求出现视体积的6个平面方程，然后求交剪取方法将在以后介绍。为了使求交过程相对方便一些，可对视体积进行缩放变换，把视体积变成有以下6个平面构成：前平面：z=a；后平面：z=1；顶平面：y=z；底平面：y=-z；左平面：x=-z；右平面：x=z；zyxFB前

视窗口后xyzy=zz=az=1y=-z第三章46剪取剪取z的缩放因子Sz把平面z=VRP´[z]变换成，

1

Sz=────

VRP´[z]+B所以：由此可得：

VRP´[z]+F

a=────

VRP´[z]+B

后剪裁平面的右上角的y坐标,将从原来((VRP´[z]+B)/VRP´[z],(Vmax-Vmin)/2)的变为1，

所以得到y的缩放因子：

2VRP´[z]

Sy=

───────────

(VRP´[z]+B)(Vmax-Vmin)

同理：

2VRP´[z]

Sx=───────────

(VRP´[z]+B)(Umax-Umin)yxFB前

视窗口后xyzy=zz=az=1y=-z第三章47剪取剪取缩放矩阵为

Sc=

然后进行三维图像的裁剪(方法见后一节)最后进行缩放变换的逆变换，把图像恢复原状。逆变换的矩阵为:

Sc=Sx

0

0

0

0

Sy

0

0

0

0

Sz

0

0

0

0

11/Sx

0

0

0

0

1/Sy

0

0

0

0

1/Sz

0

0

0

0

1yxFB前

视窗口后xyzy=zz=az=1y=-z第三章48三维图形3.5

视变换

一、数学预备知识二、视变换参数三、视变换矩阵四、剪取五、透视投影第三章49透视投影透视投影裁剪后的图像还需经过投影变换。

采用透视投影，需要决定的视变换矩阵中的D值。投影面(即视平面)到投影中心的距离为VRP´[z]，所以D=VRP´[z]。

投影矩阵为：

Per=1

0

0

0

0

1

0

0

0

0

1

1/VRP´[z]

0

0

0

1第三章50三维图形3.6

三维剪取

一、三维剪取体的形状二、三维Cohen-Sutherland

直线剪取算法三、三维Cyrus-Beck算法第三章51三维剪取体的形状三维剪取体的形状通常的三维剪取体有长方体和棱锥台体。其中长方体适用于平行投影，棱锥台体适用于透视投影，这两种剪取体均为六面体，包括左侧面、右侧面、顶面、底面、前面和后面。其他形状的剪取体并不常见。顶面左面后面右面前面底面顶面左面后面右面前面底面yyxxzz第三章52三维图形3.6

三维剪取

一、三维剪取体的形状二、三维Cohen-Sutherland

直线剪取算法三、三维Cyrus-Beck算法第三章53三维Cohen-Sutherland直线剪取算法Cohen-Sutherland算法原理与二维直线剪取算法一样，三维Cohen-Sutherland直线剪取算法也采用断点编码方法来判断线段的可见性。三维剪取中，按剪取体的每一面把整个空间划分成27个子空间，每个子空间都用唯一编码来标识，采用六位编码，具体编码规则为：第1位为“1”表示端点位于剪取体的左边；第2位为“1”表示端点位于剪取体的右边；第3位为“1”表示端点位于剪取体的下边；第4位为“1”表示端点位于剪取体的上边；第5位为“1”表示端点位于剪取体的前边；第6位为“1”表示端点位于剪取体的后边；否则相应位为零。若一线段的两端点编码均为零，则此线段的两端点可见，此线段也可见。若线段两端点编码相与(AND)不为零，则该线段为完全不可见线段；否则该线段可能部分可见或完全不可见,此时需要计算剪取体与线段交点，方可最后决定。第三章54三维Cohen-Sutherland直线剪取算法Cohen-Sutherland算法原理对于长方体剪取体，三维剪取算法决定线段端点编码只是二维剪取算法的直接推广。但是对棱锥台体剪取体，情况会复杂一些。一个有效的处理方法是作一个规范变换，使6个面的方程为：

y顶=z；y底=-z；

x右=z；x左=-z；

z后=1，z前=a(0＜a≤1)；

且投影中心为坐标系原点。这样情况变得简单多了。第三章55三维Cohen-Sutherland直线剪取算法Cohen-Sutherland算法原理假设未经变换前6个面的方程分别为：

右侧面：x=α1z+α2；左侧面：x=β1z+β2；

顶面：y=γ1z+γ2；底面：y=δ1z+δ2；

前面：z=zH；后

面：z=zY；

判断点P(x,y,z)位于平面的那一侧可以用下列函数测试: P位于平面 P位于平面 ＞0，右方； ＞0，右方；fR=x-α1z-α2

＝0，上方； fL=x-β1z-β2

＝0，上方； ＜0，左方； ＜0，左方；第三章56三维Cohen-Sutherland直线剪取算法Cohen-Sutherland算法原理 P位于平面 P位于平面 ＞0，上方； ＞0，前方；fT=y-γ1z-γ2

＝0，上方；fB=y-δ1z-δ2

＝0，上方； ＜0，下方； ＜0，下方；

P位于平面 P位于平面 ＞0，前方； ＞0，前方；

fH=z-zH

＝0，上方； fγ=z-zγ

＝0，上方； ＜0，后方； ＜0，面后方；

可以看出，本算法与二维算法是一样的，只是空间区域被标识为六部分。所以在算法实现过程中多了两个面的判断，其它部分也只有求交点时多求一个z分量。第三章57Cohen-Sutherland算法描述三维Cohen-Sutherland直线剪取算法 booldone，draw；done表示是否完成，draw表示是否可见,unsignedcharcode1，code2；分别为端点1，端点2的编码

while(!done)begin

if(判断code1，code2，若为第一种情况)begin

done=TRUE；

draw=TRUE；

end

elseif(为第二种情况)begin

done=TRUE；

draw=FALSE；

end

elsebegin

if(检查code1，若在窗口内)begin

交换端点及端点的编码；

end

以左右下上前后的次序对端点1进行判断及交；

将交点的值赋给端点1；

end

end第三章58三维Cohen-Sutherland直线剪取算法Cohen-Sutherland算法分析可以看出，本算法与二维算法是一样的，只是空间区域被标识为六部分。所以在算法实现过程中多了两个面的判断，其它部分也只有求交点时多求一个z分量。由于与二维时算法是一致的，所以它的优缺点也是一样的。Cohen-Sutherland算法的优点在于简单，易于实现。第三章59三维图形3.6

三维剪取

一、三维剪取体的形状二、三维Cohen-Sutherland

直线剪取算法三、三维Cyrus-Beck算法第三章60三维Cyrus-Beck直线剪取算法Cyrus-Beck算法原理在上一章介绍了Cyrus-Beck二维剪取算法，他除了要求剪取区域为凸区域外，对剪取区域的形状没有其他任何限制。所以，剪取区域可以是三维凸体(包括长方体，棱锥台体)，上一章的算法可以直接用于三维情形。不过原来的窗口边，现在为剪取体的面，原来矢量只有x,y两个分量，现在矢量均具有x,y,z三个分量。如上一章所述，在二维情形下，可以采用旋转和平移方法决定多边形的凹凸性以及内法矢量。这种方法同样也可以推广到三维情形。Cyrus-Beck算法描述第三章61三维Cyrus-Beck直线剪取算法while对于剪取体的每一个多边形表面do

begin

平移剪取体，使多边形表面的一个顶点重合于坐标系原点绕原点旋转多边形，使该顶点相邻的两边中，有一边重合于某坐 标轴(如x轴或y轴)

绕此坐标轴旋转，使多边形表面与一坐标平面(如z=0)重合

if

所有顶点的相应坐标分量同号或为零

then对于此多边形平面，剪取体为凸体

else对于此多边形平面，标志剪取体为凹体goto9

end标志剪取体为凸体计算剪取体各多边形表面的内法向量endofalgorithm

第三章62三维Cyrus-Beck直线剪取算法Cyrus-Beck算法分析本算法的实现是简单的，只要将二维算法扩充一下即可。然而，当涉及到图形输出时就碰到了很大的障碍，即如何将对每个凸体实施算法后合成并显示。这里碰到的问题是消隐，包括物体间消隐和自消隐。这个问题将在后面的章节中涉及到，这里不再说明。第三章63三维图形3.7

消隐

一、消隐的考虑二、Roberts算法三、Warnock算法四、表优先级算法五、Z缓冲区算法六、光线跟踪算法七、扫描线算法用计算机生成三维形体的真实图形，是计算机图形学研究的重要内容之一。在使用显示设备描绘三维图形时，必须把三维信息作某种投影变换，在二显示表面上绘制出来。由于投影变换失去了深度信息，往往导致图形的二义性：

要消除二义性，必须在绘制时消隐实际不可见得线和面，即消隐。经过消隐的投影图称为物体的真实图形。投影变换的二义性消隐的考虑第三章65第三章66消隐的考虑消隐的考虑选择不同的消隐算法

消隐问题有不同的算法，有些算法要求速度快，有些要求图形的真实度高。例如，快速消隐算法可用于实时模拟如飞行模拟等；具有高度真实感图形的消隐算法可用于计算机动画等领域，所生成的图形一般具有连续色调，并能产生阴影、透明、表面纹理及反射、折射等视觉效果。不过这类算法比较慢。产生一幅图可能需要几分钟甚至几小时。所以，在进行消隐算法的设计时，应在计算速度和图形细节之间进行权衡，任何一种算法都不能兼顾两者。第三章66消隐的考虑消隐的考虑消隐算法的实现空间

消隐算法可以在对象空间或图像空间中实现。对象空间算法是在定义对象的坐标系中实现的，而图像空间算法是在对象显示的屏幕坐标系中实现的。对象空间算法以尽可能高的精度完成几何计算，所以可以把图像放大许多倍而不致损害其准确性，但是图像空间算法只能以与显示屏的分辨率相适应的精度来完成计算，所以其图像的放大效果较差。另外，这两类算法的性能特性也是不同的。对象空间算法所需的计算时间随场量中物体的个数而增加，而图像空间的计算时间则随图像中可见部分的复杂程度而增加。第三章67三维图形3.7

消隐

一、消隐的考虑二、Roberts算法三、Warnock算法四、表优先级算法五、Z缓冲区算法六、光线跟踪算法七、扫描线算法第三章68Roberts算法原理Roberts算法Roberts消隐算法是在图像空间实现的消隐算法，数学处理严谨，计算量甚大。Roberts算法要求所有被显示的物体都是凸的，因此对凹体要先分割成许多个凸体的组合。此算法的基本步骤是：逐个的独立的考虑每个物体自身，找出为其自身所遮挡的边和面；将每一物体上留下的边再与其它物体逐个的进行比较，以确定其是完全可见还是部分或全部被遮挡；确定由于物体之间的相互贯穿等原因，是否要形成新的显示边等。从而使被显示各物体更接近现实。下面先介绍一些用到的一些基本概念以及有关的数学方法。第三章69Roberts算法原理Roberts算法体矩阵

假设在三维空间中，一平面的方程表示为：ax+by+cz+d=0,令P=[a,b,c,d]，表示平面的系数向量；又令S=[x,y,z,1]，表示三维空间重点的其次坐标。上式改写为：S·PT=0。所以凸体可由平面方程系数组成的体矩阵表示：

矩阵的每一列表示物体的对

[V]= 应平面方程的系数，其列数 与物体的面数一致。

由于当PT是一平面系数时，-PT也是该平面的系数，因此为了计算的需要，Roberts算法规定：对平面多面体内部的任一点S0，要使得[S0]·[V]=[Q]=[q1,q2,q3,…,qn]式中的每一个分量qi都不小于零(i=1,2,…,n)。

适当选取物体内部一点S0，用以测试单调态平面系数的符号，使其满足Roberts算法的规定，这是本算法最基本的一步。a1

a2

a3

…

an

b1

b2

b3

…

bn

c1

c2

c3

…

cn

d1

d2

d3

…

dn第三章70Roberts算法原理Roberts算法

平面系数的计算方法方法一：根据平面上的已知点，求解线性方程组。已知平面上不共线三点(x1,y1,z1)，(x2,y2,z2)，(x3,y3,z3)，得到规范方程组:

ax1+by1+cz1=-1 写成矩阵形式为：

ax2+by2+cz2=-1 =

ax3+by3+cz3=-1[X][C]=[D]

解得平面方程系数为：

[C]=[X]-1[D]方法二：根据平面的法矢量和平面上一已知点，求得平面系数。已知平面的法矢量为：n=ai+bj+ck，其中i，j，k分别为x，y，z方向的单位矢量，且又已知平面上一点(x1,y1,z1)。则平面方程是：

ax+by+cz+d=0，其中

d=-(ax1+by1+cz1)x1y1z1

x2y2z2

x3y3z3a

b

c-1

-1

-1第三章71Roberts算法原理Roberts算法方法三：采用MartinNewell方法，即最佳逼近法，计算任何平面多边形所在平面的精确方程或接近于平面的多边形的最佳逼近平面方程。

假设给定n个点(xi,yi,zi)(i=1,2,…,n)，则平面系数可用于下式计算：

n

a=∑(yi-yj)(zi+zj)

i=1n

b=∑(zi-xj)(xi+xj)

i=n

c=∑(xi-xj)(yi+yj)

i=1

其中：若i≠n，则j=i+1，否则j=1。d可由下式求得：

d=-(ax1+by1+cz1)第三章72Roberts算法原理Roberts算法体矩阵的变换

在消隐算法执行之前，为了得到从一指定的试点以给定的观察方向来看所需要显示的物体，常常先要对物体进行三维坐标变换。因此，在变换确定之后，或给定了变换矩阵[T]以后，需要对每一个物体的体矩阵[V]作一个相应的变换，得到变换后的体矩阵[VT]。

同时，还要对物体的顶点齐次坐标矩阵[B]作一个相应的变换，得到变换后的顶点齐次坐标矩阵[BT]。

有两种常用的计算[VT]的方法。第三章73Roberts算法原理Roberts算法方法一：假设[B]与[BT]分别为在体矩阵变换前后的物体顶点齐次坐标构成的矩阵，则[BT]=[B][T]

因为有[X][C]=[D]，所以可得到该物体原各平面的方程为：[B][V]=[D]其中：[D]为零矩阵。

同样，变换后的平面方程也可表示为：[BT][VT]=[D]

并且：[BT][VT]=[B][V]代入到[BT]=[B][T]，方程两边消去[B]并左乘[T]-1，得到：[VT]=[T]-1[V];所以，变换后的体矩阵是由原来的体矩阵左乘变换矩阵的逆矩阵而得到的。方法二：假设原先并未计算形体矩阵[V]，也不希望计算[T]的逆矩阵，则可光计算：[BT]=[B][T],然后用变换后的物体顶点坐标[BT]，按照前面介绍的MartinNewell方法，直接计算变换后的体矩阵[VT]，两种方法所得结果完全一致。Roberts算法原理第三章74自消隐方法:自消隐是对物体自身所遮挡的面(自隐面)和边(自隐边)的消除。对于不同的视点及视方向，既是对同一个物体来说，也会产生不同的自隐面和自隐边。因此自隐面和自隐边不仅取决于物体的形状，而且与视点方向相关。

假设视点位于z的负无穷远处，视方向为z轴的正向，即视方向朝z轴正向无穷远处，在齐次坐标系中，该方向矢量为：[E]=[0,0,1,0]显然，若视方向[E]和体矩阵[VT]的乘积中有负的元素，则[E]在这此元素对应的面与形体相对的另一侧，而这正说明这些面被物体自身所遮挡。所以利用[E]·[VT]=[w1,w2,…,wn](表示视线与表面内法线矢量夹角关系)寻找所有wi＜0的i值，其对应面即为自隐面，可被消除。Roberts算法

视方向朝向z轴负向无穷远处

视方向朝向z轴正向无穷远处

结果图第三章75Roberts算法原理Roberts算法当找到了所有的自隐面之后，就可以确定自隐线，自隐线的确定方法是：若相交的两各平面都是自隐面的话，它们的相交边线就是自隐线，可以消除，否则为物体的可见边线。

在确定了自隐面和自隐线之后，该物体余下的边线应当与其它物体一一比较，以确定他们是否为其他物体所遮挡。为了提高算法的执行效率，应先将一些很明显由很容易确定的不必要的比较排除在外，常用的一些方法是最大最小测试法和边框测试法等。

最大最小测试法是对要被显示的每一个物体，以其最小Z值(即最靠近视点的点)进行排序，由大到小组成一个Z值的表，比较某一边线，若它的最大Z值小于表中某一元素，则从该元素起及其以后的元素所对应的物体均不可能遮挡该边线，所以不用进一步的比较。

边框测试法是为较复杂物体加上如球或长方体之类的边框，这样只要能确定某些边线完全处于这些框的上面、下面、左面、右面后前面时，边框内的物体就不会遮挡该边线。Roberts算法原理第三章76最大最小测试法如下：

若物体1的最大Z值≤物体2的最小Z值,则物体1的优先级为1,物体2的优先级为2优先级小的物体离视点距离较近优先级小的物体可能遮挡优先极大的物体优先级小的物体先投影Roberts算法优先级1优先级2分割平面yzRoberts算法原理Roberts算法第三章77边框测试法如下：

判断下式：x_minp＞x_maxe

OR

x_mine＞x_maxpOR

y_minp＞y_maxeORy_mine＞y_maxp

若上式为真，边与多边形不相交；若上式为假，二边框相交，但边与多边形可能相交，可能不相交，需进行第二次边框测试。

框第二次边测试：把边的边框和多边形的每条边的边框进行比较，进行交点测试。

交点测试：对求出的交点，判别其是否同时在边或多边形边上(交点的x,y值是否在边的范围内)若是，边与多边形的边相交若不是，边与多边形的边不相(x_maxp,

y_maxp)(x_maxe,

y_maxe)(x_mine,

y_mine)(x_minp,

y_minp)Roberts算法原理Roberts算法第三章78

边线与物体的比较方法:完成上述工作

后，还有一定数量的边要通过与其它

物体的比较后方能确定其可见性。假设

考虑边线P1P2的可见性，被比较的物体

体矩阵为[VT]。采用直线的参数表示形式：

P(t)=P1+(P2-P1)t0≤t≤1或v=s+dt

0≤t≤1

其中：v是边线上点的位置矢量，s是起始点，d为直线的方向。再构造由P1P2上一点至视点的直线，其参数表示形式为：Q(α,t)=u=v+gα=s+dt+gα(0≤t≤1,α＞0)

其中：g=[0,0,-1,0],与视线方向[E]=[0,0,1,0]相反，且α与t的意义相同。给定一个t值，对应边线P1P2上的一点P(t)，同样对于给定一个α值，则决定了从该点至视点线段上的一点。所以Q(α,t)可以看作是定义了这平面π上的一点集,给定α和t，就确定了这个平面上的一点。α总是取正值，这是因为只有平面的这一区域才能包含遮挡上述边线的物体。如果物体于平面π的交集不定，且落在点集Q(α,t)中，则这个物体部分或全部地遮挡边线P1P2。否则，P1P2就不会被这个物体所遮挡。p1p2πgERoberts算法原理第三章79现在把边线的对于给定物体的可见性问题，转为物体与整个点集之交是否为空集的问题。因为前面已经规定：物体中的点与体矩阵的乘积所产生的向量中所有元素均为非负数。所以，只H=u·[VT]=s·[VT]+t·d[VT]+α·g[VT]≥0

(0≤t≤1，α≥0)

对于物体中的每个面j=1,2,…n，使得hj=pj+tqj+αwj≥0

(0≤t≤1，α≥0)

其中pj，qj，wj，hj分别为向量P，Q，W，H的分量：P=(p1,p2,…,pn)=s·[VT]

Q=(q1,q2,…,qn)=d·[VT]

W=(w1,w2,…,wn)=g·[VT]

H=(h1,h2,…,hn)=Q(α,t)·[VT]Roberts算法第三章79Roberts算法原理Roberts算法第三章80于是，可见与不可见的临界条件是hj=0。

当hj=0时，该点恰好位于对应的平面上。若对物体的每一平面取hj=0，可得有关α和t的联立方程组。

为了求解这个方程组，可将其中的方程两两联立，得到所有可能的α和t值。可能的解的总数为n(n-1)/2。然后在(0≤t≤1,α≥0)范围内求出t的最小值tmin和最大值tmax和相应的α值。

对于tmin≤t≤tmax,必须α≥0，使得Q(α,t)落在物体中，所有这样的t值是边线上被遮挡的点，对于那些α=0的解，说明边线真正贯穿了物体。要保存这些贯穿点，然后连接这些贯穿点，得到的贯穿线再与其它物体相比较，其中可见部分就是可见贯穿线。

可见贯穿线若下图所示:

红色处为贯穿点的位置紫色为可见贯穿线，黄色为不可见贯穿线(不可见贯穿线仅列出几条)第三章84Roberts算法Roberts算法原理

上述方法的计算量很大，下面介绍一种判别完全可见线段的方法，可节省计算量。该方法的基本思想是判断一线段的两端点是否位于视点和一可见面之间，若是，则完全可见。

根据u=s+dt+gα(0≤t≤1,α＞0)当α=0时，u表示该边线本身，

此时当t=0和t=1是，分别表示该边线的两个端点，则：hj=u·[VT]=pj+qj·t+w·α

当α=0和t=1时，pj+qj表示该边线另一端点和物体上j个平面的点积。

因为wj≤0表示物体的第j个平面可见，所以，

如果wj≤0和pj+qj≤0，则表示该端点位于可见面上或位于视点与可见面之间。

综上，在物体中只要存在一个j，使得wj≤0&pj≤0&pj+qj≤0成立，则该边线完全可见。Roberts算法第三章84Roberts算法原理

边与多边体相交情况有以下几种：边在多边体的内部边的一个端点边完全在多变边贯穿多变体 在多边体的内部体的外部 第三章84Roberts算法Roberts算法描述完整的Roberts算法分为三个部分：对每一个物体进行分析，消去自隐面和自隐线；对余留下的边与其它所有物体一一比较以确定被其他物体所遮挡的部分；确定物体见可能由于相互穿透而增加的贯穿线是否可见。假定物体是由面构成的，而面是由边构成，边则由顶点构成。所有顶点、棱边、面都是已知的。

Roberts算法第三章82Roberts算法描述（续）/*消除自隐线和自隐面*/while对于要被显示的每一个物体do

begin

物体的顶点表构造各表面多边形及棱边

计算物体上每一多边形表面的平面方程

/*检查平面方程的符号*/

取物体各顶点的平均值，作为一个物体内部点

计算该物体内部点与平面方程的点积

if点积＜0then改变平面方程系数的符号

建立物体的体矩阵体矩阵左乘包括透视变换在内的视变换的逆矩阵计算并保存变换后物体包围盒值xmin,xmax,ymin,ymax,zmin,zmaxRoberts算法第三章83Roberts算法描述（续）/*判断自消隐面和线*/

取位于负无穷处的试验点和变换后体矩阵的点积

if点积＜0then标志相应平面为隐藏面

消除相应与该平面的多边形(也消除两隐藏面相交形成的隐藏线)end

/*消除每一物体被其他物体遮挡面产生的隐藏线*/if要显示的物体只有一个thengoto结束

/*建立物体的优先级*/while对于优先表上的每一个物体do

begin

/*检查每一非自隐线的棱边是否被其他物体遮挡。含被检查棱边的物体称试验体，所有用来判断遮挡关系的其他物体称检查体。试验体通常只需对比它优先级低的检查体进行遮挡检查*/Roberts算法第三章84/*对试验体和检查体进行包围盒试验*/

ifxmin(检查体)＞xmax(试验体)或xmax(检查体)＜xmin(试验体)或 ymin(检查体)＞ymax

(试验体) 或ymax

(检查体)＜ymin(试验体) then检查体不可能遮挡试验体任何棱边goto14

/*进行初步的贯穿检查判断试验体是否贯穿检查体而部分的被遮挡*/

/*比较试验体上的最小z值和检查体的最大z值*/

ifzmin

(试验体)＞zmax

(检查体)then试验体和检查体不可能形成 贯穿goto14

/*检查是否存在可见性贯穿*/

ifzmin

(试验体)＜zmax

(检查体)then检查体可能贯穿试验体的前 面，建立可见性贯穿标志goto20

ifxmax

(试验体)＞xmin

(检查体)或xmin

(试验体)＜xmax

(检查体) then检查体可能贯穿试验体的侧面，建立可见性贯穿标志 goto20Roberts算法描述（续）Roberts算法第三章85Roberts算法描述（续）

ifymax

(试验体)＞ymin

(检查体)或ymin

(试验体)＜ymax

(检查体) then检查体可能贯穿试验体的底面或顶面，建立可见性贯穿 标志goto20

if可见性贯穿标志非空，then检查体记入贯穿表

/*进行试验体棱边检查*/

while对于试验体中每一条棱边do

begin

计算试验体棱边的s和d

计算检查体的每一表面的p,q,w

/*检查试验体棱边是否完全可见*/

if完全可见thengoto21

计算联立的方程组hj=0的解

while对于每一组(α,t)解doRoberts算法第三章86Roberts算法描述（续） begin

if0≤t≤1&α≥0&hj＞0(j=1,2,…,n)then计算tmin和tmax

if(α=0)

then计算和保存贯穿点

end

计算和保存棱边上的可见段

end

/*决定贯穿体之间的可见相贯线*/

if可见性贯穿标志为空thengoto32

if无贯穿点存在thengoto32

else将两贯穿提上的全部贯穿注意连接，构成可能的相贯边； 对两个贯穿体逐一检查每一相贯边的可见性；对其它物体，检 查余留下的相贯边的可见性并保存其可见段

显示剩下棱边上的可见段

endendofalgorithm第三章87Roberts算法分析Roberts算法Roberts消隐算法是在图像空间实现的消隐算法，数学处理严谨，计算量甚大。

Roberts算法要求所有被显示的物体都是凸的，因此对凹体要先分割成许多个凸体的组合。

由于Roberts算法的计算量随着被显示物体数的平方递增以及人们对光栅扫描显示的兴趣与日俱增，使得Roberts算法大为逊色。

但Roberts算法数学处理简单、精确、适用性强，在结合一些使用的技巧，使该算法的计算量几乎只与显示物体个数呈线性增长关系。第三章63三维图形3.7

消隐

一、消隐的考虑二、Roberts算法三、Warnock算法四、表优先级算法五、Z缓冲区算法六、光线跟踪算法七、扫描线算法Warnock算法原理Warnock算法第三章89考虑图象空间中的一个窗口，判定窗口是否为空,或者该窗口所包含的画面足够简单可以立即显示；否则，分割该窗口，直到子窗口内所包含的画面相当简单以致可以立即显

示或者其尺寸已达到给定的分辨率为止。

这里称画面足够简单的条件：窗口中仅包含一个多边形；窗口与一个多边形相交，且窗口内无其他多边形；窗口为一个多边形所包围且窗口内无其他多边形；窗口至少为一个多边形所包围且此多边形离视点最近。多边形与窗口之间的关系:zminzmax第三章90Warnock算法原理Warnock算法分为5部分：控制程序：控制检测窗口，当检测失败时，继续分割窗口，保证整个屏幕都被检测到。检查程序：检查全部对象的所有多边形，将它们分成分离、包围、内含和相交多边形，并建立3个表：包围多边形表，分离多边形表，相交及内含多边形表，供分析程序进一步处理。分析程序：分析检查程序提供的信息，分析结果：画面足够简单，调用计