《计算机图形学基础与CAD开发》课件-第3章 二维图形处理技术

第3章二维图形生成与图形处理3.1图形坐标系3.2字符的生成3.3直线的生成3.5

二维图形的几何变换3.6

窗口到视区的变换3.7二维图形的裁剪算法

3.8区域填充算法世界坐标系

初始的笛卡尔坐标系，可以是二维也可以是三维的。取值范围为整个实数域，也可根据需要设定。用户坐标系

用户在世界坐标系下建立的直角坐标系。位置、方向任意。3.1图形坐标系4.规范化设备坐标系

将所有设备坐标系的数据化为统一的数据范围。比如x(0.0,1.0),y(0.0,1.0),z(0.0,1.0)。对于每种设备来说，设备坐标系与规范化坐标系之间的坐标值相差一个比例系数。这种规范化便于设备间的数据通信，要输出到具体设备只要乘上该设备的规范化比例因子即可。

设备坐标系

与图形设备关联的坐标系。通常是二维的，个别有三维的（如三维雕刻机、打印机）。取值范围是某个整数域。如:分辨率是1024×768的显示器，则坐标系x:（0,1023,）y:（0,767），单位是像素；幅面为385×280的绘图机，步距（分辨率）为0.1mm,则设备坐标系为x:(0,3850)y:(0,2800).5.圆柱面坐标系

使用（r，Φ，z).

ρ、φ为空间点在XOY平面上投影的极坐标（r为极径，φ为极角），z为空间点到XOY平面的距离。球面坐标系使用(

r,θ,φ).

r为空间点到原点的距离，φ为以X轴正向起度量的经度角，θ为以Z轴正向起度量的纬度角）。

Back2.2字符的生成

1.字符的分类

生成方式有点阵式和矢量式两种。（1）点阵式是用像素点阵拼成字符。它可以通过硬件和软件来实现，在显示卡内字符发生器里存放256个ASCII字符的位图编码。

2.2字符的生成

1.字符的生成

（2）矢量式字符是根据一定的数学模型，把每个字符的笔画分解成数学模型中定义好的各种直线和曲线，然后记录这些直线和曲线的参数。显示时根据尺寸大小和参数绘制出字符。常见的矢量字库有Type1字库和Truetype字库。

2.2字符的生成2.点阵字符与矢量字符的特点

（1）变换：点阵字符的变换需要对字符位图的每个像素进行变换，而矢量字符的变换只需对其笔画端点进行变换。点阵字库存储量大、变换速度慢；矢量字库存储量小，变换方便快速。

（2）显示速度和效果：显示速度快，但在缩放的情况下容易出现锯齿；矢量字库显示效果平滑，显示效果平滑，但相对而言需要经过一系列的数学运算并光栅化后才能显示，显示速度相对慢。

Back3.3直线的生成算法直线的生成算法,也可解决曲线的绘制（曲线由多段直线逼近）直线的生成算法：

像素化算法：用于点阵显示设备及绘图设备的直线生成，如DDA法、Bresenham法。

矢量化算法：用于笔式绘图机绘制直线，线切割机床、刻字机等设备加工直线，如逐点比较法、正负法等。像素化算法（直线的像素化）：用一系列靠近直线的像素点逼近直线。(1)(2)直线像素化的基本要求：

（1）

直线要直；

（2）

起点、终点位置尽可能准确；

（3）

直线上亮度尽可能均匀；

（4）绘制效率高。像素化算法（直线的像素化）：

1.像素化直线生成算法--DDA(DigitalDifferentialAnalyzer)法，即为数字微分分析法，基本原理如下：直线微分方程像素化得到坐标点的递推公式对称DDA法简单DDA法（1）直线微分方程为:(Δx=xb-xa,Δy=yb-ya)

(xa,ya)、(xb

yb)为直线起点和终点坐标。

（2）将上式数字化（即像素化），得出下面的递推公式:当ε取不同值时，便形成对称DDA法和简单DDA法。

对称DDA法

取ε=2-n,n由下面关系式决定:

2n-1≤Max(|Δx|,|Δy|)≤2n,n为正整数

计算点的公式为

x1=xa+0.5,y1=ya+0.5xi+1=xi+ε·Δx,yi+1=yi+ε·Δyxis=［xi］,yis=［yi］i=1,2,…,2n取整，得到显示坐标，即像素点坐标四舍五入法【例2.1】用对称DDA法在起点A（2，1）和终点B（12，7）之间生成一段直线。解：(1)计算初值Δx、Δy、n。Δx=10,Δy=6,n=4。（2）按递推公式循环计算点的坐标，并取整显示。ε=2-n=1/162n-1≤Max(|Δx|,|Δy|)≤2n对称DDA法计算过程对称DDA法生成的直线简单DDA法

取ε=1/l,l=Max(|Δx|,|Δy|)。

计算点的公式为i=1,2,…,l简单DDA法生成的直线对称DDA法简单DDA法3.5二维图形几何变换

2.4.1基本变换

1.比例变换

比例变换就是将图形放大或缩小若干倍。

通过对平面上任意一点的x坐标及y坐标分别乘以比例因子a和d来实现，即用矩阵运算表示为：其中

T=称为比例变换矩阵。

变换后的新坐标变换前的坐标

平面图形的比例变换

等比变化(a=d)不等比变化(a=1d=3)2.旋转变换平面上一点P(x,y)绕原点逆时针旋转θ角后变为P*（x*,

y*），由几何关系推出:x*=xcosθ-ysinθy*=xsinθ+ycosθ

用矩阵运算表示为

平面图形的旋转变换

旋转变换矩阵：T=

3.对称（反射）变换使变换前后的图形相对于某一条线或原点对称的变换叫对称变换。关于一条线的对称变换也称镜像变换。(a)Y轴对称变换；(b)X轴对称变换；(c)原点对称变换x*=-xy*=y

（1）对称于Y轴的变换用矩阵运算表示为:对称于Y轴的变换矩阵为：T=（2）对称于X轴的变换x*=xy*=-y

用矩阵运算表示为对称于X轴的变换矩阵为：T=

（3）对称于原点的变换

点对称于原点变换后仅改变x、y坐标值的符号，即x*=-xy*=-y

用矩阵运算表示为对称于X轴的变换矩阵为：T=4.错切变换错切变换就是图形沿某一坐标方向产生不等量的移动，使图形变形。

(1）沿X方向错切变换:

正方形ABCD沿X方向错切成平行四边形A*B*C*D*

。错切后图形与Y轴间有一错切角θ。

(2）沿Y方向错切变换:

正方形ABCD图形沿Y方向错切后与X轴之间形成错切角θ，错切成平行四边形A*1B*1C*1D*1。

平面图形的错切变换x*=x+ytanθ=x+cy

y*=y

??水平错切竖直错切x*=xy*=y+xtanθ=y+bxX向错切用矩阵运算表示为

Y向错切用矩阵运算表示为

C

5.平移变换

平移变换就是图形沿X方向移动l，沿Y方向移动m，其形状不变，各点的坐标分别增加了平移量l和m，即x*=x+ly*=y+m

平移变换用矩阵运算表示为:

x*=x+ly*=y+m

为了方便，把前面所述的变换矩阵统一用T3×3矩阵表示:

因此，可得到二维图形变换矩阵的一般式:比例、对称、错切、旋转平移

齐次坐标

用［xy1］表示平面上的一点，解决了平移变换的矩阵表示，使各种变换矩阵形式统一为T3×3的方阵。［xy1］称为二维点的齐次坐标形式。齐次坐标表示法：用n+1维向量表示n维向量的方法

二维点用齐次坐标表示的一般形式：

[HXHYH]（H/＝0)

如：[1284][642][321]均表示同一个二维点。

[HXHYH]（H/＝0)[XY1]齐次坐标正常化

H＝1的齐次坐标点

在

T3×3方阵中，第三列元素p、q在变换中的作用:

使方阵中的a=d=1，其余元素为0，即设对某点进行变换，其矩阵运算为:

qq

变换后各点的x、y坐标不变，第三列元素H=px+qx+s。

这相当于把H=1平面上的点变到了H=px+qy+s的空间一般位置平面上。AA1A’q

空间一般位置平面在X、Y、H轴上的截距可以求出:

x=y=0时，H=sy=H=0时，

x=H=0时，H=px+qy+s将位于一般位置平面的点正常化（H=1)：齐次化后的点在哪里？

齐次坐标正常化

齐次坐标正常化几何意义:将位于一般位置的点A’再次变换到H＝1的平面上。

可以证明，齐次化后的A*点是A’与原点O的连线与H＝1平面的交点。齐次化后的点由图得出，△AA′O∽△A2A*O，则因为A2A*=1AA′=px+qy+s所以同理可证

p、q两元素的作用:

在H=1的平面上产生一个以O为中心的中心投影变换—透视投影变换。qabcdlm比例、对称、错切、旋转平移透视变换整体缩放二维图形基本变换矩阵的一般式：

3.5.2组合变换组合变换：通过一系列的基本变换的组合而成。解决这一类问题的关键是：

（1）确定图形变换是由哪些基本变换？组合变换是按照什么样的变换顺序形成？（2）按变换顺序求出基本变换矩阵的乘积得到组合变换矩阵。

【例3.1】如图所示，△ABC绕原点之外的任意点P(m,n)逆时针旋转θ角到△A*B*C*，求其变换矩阵。

解：

（1）把旋转中心P平移到坐标原点，其变换矩阵为（2）使平移后的图形绕原点逆时针旋转θ角

（3）再把旋转中心平移回原来位置P(m,n)处，变换矩阵：

以上三种变换的组合变换矩阵：

注意：变换顺序不同，组合变换结果不同。因为矩阵相乘不符合交换律。【例3.2】推导图形关于镜像线ax+by+c=0镜像变换前后坐标之间的关系式。

五个变换的变换矩阵依次为

T1、T2、T3、T4、T5：组合变换矩阵为：结果为x*y*[1]=[x

y1]X镜像后的坐标x*和y*用[x

y1]·T求出：1.简述计算机图形学中采用的坐标系。2.分别用简单DDA和对称DDA法在起点（1,1），终点（17,14）之间生成直线，并比较两种直线生成算法的优劣。4.什么是图形变换？图形变换的实质是什么？5.什么是齐次坐标？为什么引入齐次坐标？6.二维图形基本变换的一般形式是什么？各元素的作用是什么？7.二维图形的基本变换都有哪些？写出它们的变换矩阵。8.什么是组合变换矩阵？若一个二维图形绕平面上一个点A（x，y)顺时针旋转ɑ角度，其经历了什么样的变换过程？写出其变换矩阵。作业3.6窗口到视区的变换

通常是在世界坐标系中描述图形。为了把所描述的图形全部或部分地显示在屏幕上，必须将世界坐标转换为显示设备的屏幕坐标。

转换时需要在世界坐标系中定义一个平行于坐标轴的矩形窗口，框住自己感兴趣的图形区域，然后映射到屏幕视区中显示。

屏幕视区也是一个矩形区域，用屏幕坐标给出。

窗口到视区的变换

(a)世界坐标系；(b)屏幕坐标系

把窗口内的图形映射到视区中显示，实质上也是一种图形变换。

设世界坐标系下的点为(xw,yw)，映射到屏幕视区中为(xs,ys)，其变换关系式:设则(xs,ys)与(xw,yw)间的变换关系为xs=a·xw+mys=d·yw+n

a001d0mn1T=3.7二维图形的裁剪算法

裁减处理的原理就是对点在窗口内外的判断以及交点的计算。但因涉及的图形元素较多，裁减算法的速度（效率）是需考虑的重要问题。本节主要学习：

直线段裁减算法（编码裁减法、中点裁减法等）多边形裁减算法3.7.1直线段的裁剪

点在窗口内的条件：

xL<=x<=xRyB<=y<=yT

线段相对于窗口的位置有下面三种情况:(1)线段在窗外同侧，如线段a，应舍去。

(2)线段在窗内，如线段b，应保留。

(3)线段与窗口边界相交，或线段在窗外两侧，如线段c、d和e，它们可能有一部分在窗内，也可能全部在窗外。

1.编码裁剪法（由Cohen和Sutherland两人提出的）

（1）矩形窗口的四条边界xL=xmin，xR=xmax,yT=ymax,yB=ymin，延长后，将图形所在的平面分成九个区域，每个区域内的点都有一个四位二进制编码对应。即C4C3C2C1，其含义为：

x<xmin,C1=1；否则C1=0

x>xmax,C2=1；否则C2=0

y<ymin,C3=1；否则C3=0

y>ymax,C4=1；否则C4=0

xmin

xmaxymaxymin九个区域四位二进制编码

（2）编码裁剪算法流程P1=p2=0000P1^p2/=0000取窗外一点P1,根据编码确定在那条边界线外，求出与其边界交点p,舍去P1P,令P1=P;保留P1P2舍去P1P2YYNN结束

2.中点再分裁剪法中点再分裁剪法是用不断对分线段的方法排斥线段在窗口外的部分，最后求出离线段的一个端点最远的在窗内的点（可见点）。

中点再分裁剪法

P1最远点

P2最远点离线段的一个端点最远的在窗内的点（可见点）。

2.中点再分裁剪法中点再分裁剪法是用不断对分线段的方法排斥线段在窗口外的部分，最后求出离线段的一个端点最远的在窗内的点（可见点）。算法分别从线段的两个端点出发作相同的处理。得到的两个最远可见点之间的线段在窗内，应保留。

例如，要裁剪的线段是P1P2，求离点P1最远的可见点的算法步骤为:(1)测试P2是否在窗口内，若是，则P2就是离P1最远的可见点，结束。否则，进行下一步。

最远可见点p1p2p1p2

例如，要裁剪的线段是P1P2，求离点P1最远的可见点的算法步骤为:(1)测试P2是否在窗口内，若是，则P2就是离P1最远的可见点，结束。否则，进行下一步。

(2)测试P1P2是否在窗外同侧，若是，P1P2全部不可见，结束。否则，进行下一步。

窗外同侧p1p2p1p2

例如，要裁剪的线段是P1P2，求离点P1最远的可见点的算法步骤为:(1)测试P2是否在窗口内，若是，则P2就是离P1最远的可见点，结束。否则，进行下一步。

(2)测试P1P2是否在窗外同侧，若是，P1P2全部不可见，结束。否则，进行下一步。

(3)取P1P2的中点Pm，若PmP2在窗外同侧，舍去，剩余段以P2代替Pm,

重复步骤(2)。否则，以P1代替Pm重复步骤(2)。直到线段不能再分为止。

中点再分裁剪法

p1p2若PmP2在窗外同侧，舍去，剩余段以P2代替Pmpm若PmP2在异侧，以P1代替Pmp2中点再分裁剪法

p1p2pm若PmP2在异侧，以P1代替Pm最远可见点

例如要裁剪的线段是P1P2，求离点P1最远的可见点的算法步骤为:(1)测试P2是否在窗口内，若是，则P2就是离P1最远的可见点，结束。否则，进行下一步。

(2)测试P1P2是否在窗外同侧，若是，P1P2全部不可见，结束。否则，进行下一步。

(3)取P1P2的中点Pm，若PmP2在窗外同侧，舍去，剩余段以P2代替Pm,

重复步骤(2)。否则，以P1代替Pm重复步骤(2)。直到线段不能再分为止。取中点的目的是用中点逼近线段与边界的交点。3.7二维图形的裁剪算法

裁减处理的原理就是对点在窗口内外的判断以及交点的计算。但因涉及的图形元素较多，裁减算法的速度（效率）是需考虑的重要问题。本节主要学习：

直线段裁减算法（编码裁减法、中点裁减法等）多边形裁减算法

3.7.2多边形的裁剪直线段裁剪法可以解决折线以及封闭折线（多边形）的裁剪问题。对多边形区域（如区域填充的多边形）的裁剪则不适用。多边形区域裁剪后应该仍然是多边形区域,裁剪后的多边形区域的边界由原来多边形经裁剪的线段及窗口区域的若干段边界组成。

多边形裁剪SutherlandHodgman算法是适合凸多边形的一种逐边裁剪算法凸多边形

多边形边界线段的连接正确不正确

用计算机处理时，选择窗口边界线段去形成封闭的多边形区域是关键问题，选得不当会产生错误。逐边裁剪法算法思想：

假定裁剪区域是矩形窗口区域，被裁剪的多边形顶点序列为A1A2…An。算法的思想是用窗口的四条边界直线Lj(j=1,2,3,4)依次裁剪四次。

裁剪时，对多边形的各个顶点Ai(i=1,2,…,n)测试各边Ai-1Ai（令Ao=An）与窗口边界Lj是否相交，若相交求出交点Bi-1作为输出顶点。再判断Ai本身是否在窗口边界的可见侧（窗口左边界之右为可见侧，右边界之左为可见侧，……），若在，也作为输出顶点，否则舍去。裁剪时，对多边形的各个顶点Ai(i=1,2,…,n)测试各边Ai-1Ai（令Ao=An）与窗口边界Lj是否相交，若相交求出交点Bi-1作为输出顶点。再判断Ai本身是否在窗口边界的可见侧（窗口左边界之右为可见侧，右边界之左为可见侧，……），若在，也作为输出顶点，否则舍去。

对窗口边界Lj裁剪的输出又作为对下一条窗口边界Lj+1裁剪的输入。经过四次，就得到所要的结果。SutherlandHodgman算法(a)A1A2A3A4A5

输出B1A2A3A4B4(b)A1A2A3A4A5

输出B2A3A4A5B5(c)A1A2A3A4A5

输出A1B1B2A3A4A5(d)A1A2A3A4A5A6

输出A1A2A3B3B5A6作业直线段裁剪算法和多边形裁剪算法的本质区别是什么？总结编码裁剪算法和中点裁剪算法的特点。3.查阅资料，了解总结其他相关的直线段裁剪算法和多边形裁剪算法的思想及应用。3.8区域填充算法

区域填充是指在给出的封闭区域内填充某种颜色或者图案。

区域填充算法分为基于像素的填充算法和基于矢量的填充算法两类。其中：

基于像素的填充算法包括扫描线填充算法、种子填充算法以及由这两种算法派生的一些算法，这类算法可实现图案和颜色的填充；

基于矢量的填充算法是指如剖面线填充算法以及由此派生的一些算法，这类算法适用于图案填充。

本节介绍以基于矢量填充算法为基础的剖面线填充算法，它也是复杂图案填充的基础。1.绘制剖面线需解决的问题

剖面线是一簇同方向、间隔相等的细实线。用计算机模拟人工绘制，每画一条剖面线必须具备以下条件:

（1）剖面线的端点坐标。

（2）剖面线的连线顺序及抬、落笔状态。

2.剖面线