第六章 二维变换及二维观察 6.1 基本概念 齐次坐标 齐次坐标表示就是用n+1维向量表示一个n维向量。

Slides:



Advertisements
Similar presentations
2.8 函数的微分 1 微分的定义 2 微分的几何意义 3 微分公式与微分运算法则 4 微分在近似计算中的应用.
Advertisements

2.6 隐函数微分法 第二章 第二章 二、高阶导数 一、隐式定义的函数 三、可微函数的有理幂. 一、隐函数的导数 若由方程 可确定 y 是 x 的函数, 由 表示的函数, 称为显函数. 例如, 可确定显函数 可确定 y 是 x 的函数, 但此隐函数不能显化. 函数为隐函数. 则称此 隐函数求导方法.
练一练: 在数轴上画出表示下列各数的点, 并指出这些点相互间的关系: -6 , 6 , -3 , 3 , -1.5, 1.5.
§3.4 空间直线的方程.
《解析几何》 -Chapter 3 §7 空间两直线的相关位置.
第八章 向量代数 空间解析几何 第五节 空间直线及其方程 一、空间直线的点向式方程 和参数方程 二、空间直线的一般方程 三、空间两直线的夹角.
3.4 空间直线的方程.
第七章 空间解析几何 §5 空间直线及其方程 一、空间直线的一般方程 二、空间直线的对称式方程与参数方程 三、两空间直线的夹角
圆的一般方程 (x-a)2 +(y-b)2=r2 x2+y2+Dx+Ey+F=0 Ax2+Bxy+Cy2+Dx+Ey+ F=0.
《解析几何》 乐山师范学院 0 引言 §1 二次曲线与直线的相关位置.
第五章 二次型. 第五章 二次型 知识点1---二次型及其矩阵表示 二次型的基本概念 1. 线性变换与合同矩阵 2.
云南省丽江市古城区福慧学校 执教者 :和兆星.
第二章 二次函数 第二节 结识抛物线
一次函数的图象复习课 南华实验学校 初二(10)班 教师:朱中萍.
第5章 定积分及其应用 基本要求 5.1 定积分的概念与性质 5.2 微积分基本公式 5.3 定积分的换元积分法与分部积分法
2-7、函数的微分 教学要求 教学要点.
初中数学八年级下册 (苏科版) 10.4 探索三角形 相似的条件(2).
计算机科学与技术专业研究型课程 矩阵和线性变换 宋传鸣 辽宁师范大学计算机与信息技术学院.
强连通分量 无向图 1、任意两顶点连通称该图为连通图 2、否则将其中的极大连通子图称为连通分量 A D C B E 有向图
用函数观点看方程(组)与不等式 14.3 第 1 课时 一次函数与一元一次方程.
工业机器人技术基础及应用 主讲人:顾老师
双曲线的简单几何性质 杏坛中学 高二数学备课组.
§7.2 直线的方程(1) 1、经过两点P1(x1,y1),P2(x2,y2)的斜率公式: 2、什么是直线的方程?什么是方程的直线?
第六章 二维变换及二维观察 如何对二维图形进行方向、尺寸和形状方面的变换。 如何进行二维观察。.
2.1.2 空间中直线与直线 之间的位置关系.
平行四边形的性质 灵寿县第二初级中学 栗 彦.
工业机器人技术基础及应用 主讲人:顾老师
第三章 图形变换.
第四章 基本图形生成算法 (三) 2019/4/6 IBM Confidential.
第六章 图形裁剪 在用户坐标系中定义的图形往往是大而复杂的,而输出设备如显示屏幕的尺寸及其分辨率却是有限的,为了能够清晰地观察某一部分或对其进行某些绘图操作,就需要将所关心的这一局部区域的图形从整个图形中区分出来,这个区分指定区域内和区域外的图形过程称为裁剪,所指定的区域称为裁剪窗口。 裁剪通常是对用户坐标系中窗口边界进行裁剪,然后把窗口内的部分映射到视区中,也可以首先将用户坐标系的图形映射到设备坐标系或规范化设备坐标系中,然后用视区边界裁剪。
变换与裁剪.
第二十二章 曲面积分 §1 第一型曲面积分 §2 第二型曲面积分 §3 高斯公式与斯托克斯公式.
第三章 图形变换.
实数与向量的积.
线段的有关计算.
正方形 ——计成保.
北师大版八年级(上) 第五章 位置的确定 5.2 平面直角坐标系(3).
第四章 一次函数 4. 一次函数的应用(第1课时).
3.3 垂径定理 第2课时 垂径定理的逆定理.
第五节 对坐标的曲面积分 一、 对坐标的曲面积分的概念与性质 二、对坐标的曲面积分的计算法 三、两类曲面积分的联系.
复习: 若A(x1,y1,z1) , B(x2,y2,z2), 则 AB = OB - OA=(x2-x1 , y2-y1 , z2-z1)
正切函数的图象和性质 周期函数定义: 一般地,对于函数 (x),如果存在一个非零常数T,使得当x取定义域内的每一个值时,都有
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
第四章 第四节 函数图形的描绘 一、渐近线 二、图形描绘的步骤 三 、作图举例.
抛物线的几何性质.
1.设A和B是集合,证明:A=B当且仅当A∩B=A∪B
第三章 函数的微分学 第二节 导数的四则运算法则 一、导数的四则运算 二、偏导数的求法.
O x y i j O x y i j a A(x, y) y x 5.4 平面向量的坐标运算 5.4 平面向量的坐标运算 5.4 平面向量的坐标运算 5.4 平面向量的坐标运算 5.4 平面向量的坐标运算 5.4 平面向量的坐标运算 5.4 平面向量的坐标运算.
第七章 图 形 变 换 (一) 2019/5/7 Thank you for your time today.
一元二次不等式解法(1).
轴对称在几何证明及计算中的应用(1) ———角平分线中的轴对称.
二维裁剪 计算机科学与技术系.
第三章 空间向量与立体几何 3.1 空间向量及其运算 3.1.2空间向量的数乘运算.
高中数学必修 平面向量的基本定理.
§2 方阵的特征值与特征向量.
§2-2 点的投影 一、点在一个投影面上的投影 二、点在三投影面体系中的投影 三、空间二点的相对位置 四、重影点 五、例题 例1 例2 例3
在发明中学习 线性代数概念引入 之四: 矩阵运算 李尚志 中国科学技术大学.
4.6 图形的位似     观察思考:这两幅图片有什么特征? 都是有好几张相似图形组成,每个对应顶点都经过一点.
第六章 裁 剪.
23.6 图形与坐标 图形的变换与坐标
第四节 向量的乘积 一、两向量的数量积 二、两向量的向量积.
1.2轴对称的性质 八 年 级 数 学 备 课 组.
反比例函数(复习课) y o x 常州市新北区实验中学 高兴林.
三角 三角 三角 函数 余弦函数的图象和性质.
位似.
复习回顾 条件:不重合、都有斜率 条件:都有斜率 两条直线平行与垂直的判定 平行:对于两条不重合的直线l1、l2,其斜率分别为k1、k2,有
§4.5 最大公因式的矩阵求法( Ⅱ ).
正方形的性质.
第三章 图形的平移与旋转.
3.3.2 两点间的距离 山东省临沂第一中学.
Presentation transcript:

第六章 二维变换及二维观察 6.1 基本概念 6.1.1 齐次坐标 齐次坐标表示就是用n+1维向量表示一个n维向量。 第六章 二维变换及二维观察 6.1 基本概念 6.1.1 齐次坐标 齐次坐标表示就是用n+1维向量表示一个n维向量。 在二维平面中,点p[x,y]的齐次坐标表示为[hx,hy,h],其中h是一个实数。 一个向量的齐次表示是不唯一的 齐次坐标的h取不同的值都表示的是同一个点,比如齐次坐标[8,4,2]、[4,2,1]表示的都是二维点[2,1]。 规范化齐次坐标表示就是h=1的齐次坐标表示。 如何从齐次坐标转换到规范化齐次坐标?

引进齐次坐标的优点 提供了用矩阵运算把二维、三维甚至高维空间中的一个点集从一个坐标系变换到另一个坐标系的有效方法。 可以表示无穷远的点。 n+1维的齐次坐标中如果h=0,实际上就表示了n维空间的一个无穷远点。

6.1.2 几何变换 图形的几何变换是指对图形的几何信息经过平移、比例、旋转等变换后产生新的图形,是图形在方向、尺寸和形状方面的变换。 6.1.3 二维变换矩阵

上面矩阵每一个元素都是有特殊含义的。    可以对图形进行缩放、旋转、对称、错切等变换;    是对图形进行平移变换;    是对图形作投影变换;    则是对图形整体进行缩放变换。

6.2 基本几何变换 6.2.1 平移变换 基本几何变换都是相对于坐标原点和坐标轴进行的几何变换 6.2 基本几何变换 基本几何变换都是相对于坐标原点和坐标轴进行的几何变换 6.2.1 平移变换 平移是指将p点沿直线路径从一个坐标位置移到另一个坐标位置的重定位过程。

6.2.2 比例变换 比例变换是指对p点相对于坐标原点沿x方向放缩Sx倍,沿y方向放缩Sy倍。其中Sx和Sy称为比例系数。 变换后有: 6.2.2 比例变换 比例变换是指对p点相对于坐标原点沿x方向放缩Sx倍,沿y方向放缩Sy倍。其中Sx和Sy称为比例系数。 变换后有: x’=x.sx y’=y.sy 比例变换的坐标计算如下:

6.2.3 旋转变换 二维旋转是指将p点绕坐标原点转动某个角度(逆时针为正,顺时针为负)得到新的点p’的重定位过程。 6.2.3 旋转变换 二维旋转是指将p点绕坐标原点转动某个角度(逆时针为正,顺时针为负)得到新的点p’的重定位过程。 对于给定的点p(x,y),其极坐标形式为 x = rcosα y = r sinα 于是p’(x’,y’)为 x’ = rcos(α+θ)=rcosαcosθ-rsinαsinθ=xcosθ-ysinθ y’= rsin(α+θ) =rcosαsinθ + rsinαcosθ=xsinθ+ ycosθ

简化计算 

6.2.4 对称变换 对称变换后的图形是原图形关于某一轴线或原点的镜像,也称为反向变换或镜像变换。

(1)关于x轴对称

(2)关于y轴对称

(3)关于原点对称

(4)关于y=x轴对称

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

6.2.5 错切变换 错切变换,也称为剪切、错位变换,用于产生弹性物体的变形处理。

其变换矩阵为: (1)沿x方向错切 x’=x+cy y’=y (2)沿y方向错切 x’=x y’=bx+y  (3)两个方向错切 x’=x+cy y’=bx+y

6.2.6 二维图形几何变换的计算 几何变换均可表示成P’=P*T的形式 1. 点的变换 2. 直线的变换 3. 多边形的变换 6.2.6 二维图形几何变换的计算 几何变换均可表示成P’=P*T的形式   1. 点的变换 2. 直线的变换 3. 多边形的变换 4. 曲线的变换

6.3 复合变换 图形作一次以上的几何变换,变换结果是每次的变换矩阵相乘。 任何一复杂的几何变换都可以看作基本几何变换的组合形式。 6.3 复合变换 图形作一次以上的几何变换,变换结果是每次的变换矩阵相乘。 任何一复杂的几何变换都可以看作基本几何变换的组合形式。 复合变换具有形式:

6.3.1 二维复合平移 6.3.2 二维复合比例 6.3.3 二维复合旋转 两个连续平移是加性的。 连续比例变换是相乘的。 6.3.1 二维复合平移 两个连续平移是加性的。 6.3.2 二维复合比例 连续比例变换是相乘的。 6.3.3 二维复合旋转 两个连续旋转是相加的。可写为:

6.3.4 其它二维复合变换 旋转变化可看作先进行比例变换,再进行一次错切变化;或顺序相反。

注意: 矩阵相乘的顺序。通常M1.M2≠M2.M1 在下列特殊情况下,M1.M2中的M1和M2顺序才是可变换的。 M1 M2   平移变换  平移变换   放缩变换    放缩变换   旋转变换    旋转变换    放缩(sx=sy)变换  旋转变换

6.3.5 相对任一参考点的二维几何变换 例1. 相对点Pr(xr,yr)旋转某个角度的变换

例2.关于Pr(xr,yr)点的缩放变换

例. 将正方形ABCO各点沿图6-8所示的(0,0)→(1,1)方向进行拉伸,结果为如图所示的,写出其变换矩阵和变换过程。

例:关于任意方向的对称

6.3.7 坐标系之间的变换 问题:将 空间上某点p (xp , yp)点从XOY坐标系变换到x’o’y’坐标系。 怎样用新坐标系x’o’y’表示空间上的点?

分析:

可以分两步进行:

于是: 

6.3.8 光栅变换 直接对帧缓存中象素点进行操作的变换称为光栅变换。  光栅平移变换: 

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

任意角度的光栅旋转变换:  

光栅比例变换:  

6.3.9 常见的几何变换 刚体变换(rigid body transformation) :图形中任意两点间的距离变换到另一幅图象中后仍然保持不变,它可分解为旋转和平移 仿射变换(affine transformation) :图形中的直线经过变换后仍保持为直线,并且平行线仍保持平行,但它在各个方向上尺度有变换。 投影变换(projective transformation) :与仿射变换相似,投影将直线映射为直线,但不再保持平行性质。 非线性变换(Nonlinear transformation) :它把直线变为曲线,使用较多的是多项式函数,如二次,三次函数及薄板样条函数。

二维仿射变换是具有如下形式的二维坐标变换: 二维仿射变换是具有如下形式的二维坐标变换:  仿射变换具有平行线不变性和有限点数目的不变性 平移、比例、旋转、错切和反射等变换均是二维仿射变换的特例,反过来,任何常用的二维仿射变换总可以表示为这五种变换的复合。 

二维几何变换具有如下一些性质: 直线的中点不变性; 平行直线不变性; 相交不变性; 仅包含旋转、平移和反射的仿射变换维持角度和长度的不变性; 比例变化可改变图形的大小和形状; 错切变化引起图形角度关系的改变,甚至导致图形发生畸变。

6.4二维观察 6.4.1基本概念 世界坐标系(world coordinate):用户在图形对象所在的空间定义的坐标系。 用户坐标系(user coordinate):用户按照自己熟悉的方式建立的世界坐标系。 局部坐标系(local coordinate):简化图形对象的描述,采用相对于物体的坐标系。 屏幕坐标系(screen coordinate)设备坐标系(device coordinate)    图形输出设备上定义的直角坐标系。

窗口:图形很大,屏幕有限,在世界坐标系中指定一个矩形区域,用来指定要显示的图形。 视区:在设备坐标系(屏幕或绘图纸)上指定的矩形区域,用来指定窗口内的图形在屏幕上显示的大小及位置 窗口到视区的变换:窗口与视区在不同坐标系,必须进行变换

要将窗口内的图形在视区中显示出来,必须经过将窗口到视区的变换(Window-Viewport Transformation)处理,这种变换就是观察变换(Viewing Transformation)。

观察坐标系是依据窗口的方向和形状在用户坐标平面中定义的直角坐标系。 观察坐标系(View Coordinate)和规格化设备坐标系(Normalized Device Coordinate)   观察坐标系是依据窗口的方向和形状在用户坐标平面中定义的直角坐标系。 规格化设备坐标系也是直角坐标系,它是将二维的设备坐标系规格化到(0.0,0.0)到(1.0,1.0)的坐标范围内形成的。

引入了观察坐标系和规格化设备坐标系后,观察变换分为如下图所示的几个步骤,通常称为二维观察流程。  

变焦距效果 漫游效果 

整体放缩效果

6.4.2 用户坐标系到观察坐标系的变换 用户坐标系到观察坐标系的变换分别由两个变换步骤合成: 1. 将观察坐标系原点移动到用户坐标系原点

2. 绕原点旋转使两坐标系重合 

6.4.3 窗口到视区的变换 1.窗口区的边与坐标轴平行

2.窗口区的边与坐标轴不平行

6.5 裁剪 直线段裁剪算法比较简单,但非常重要,是复杂图元裁剪的基础。因为复杂的曲线可以通过折线段来近似,从而裁剪问题也可以化为直线段的裁剪问题。常用的线段裁剪方法有:Cohen-Sutherland、中点分割算法和梁友栋-barskey算法(交点计算方法不同)。 假设窗口是标准矩形,即边与坐标轴平行的矩形,由上(y=wyt)、下(y=wyb)、左(x=wxl)、右(x=wxr)四条边或由上(y=ymax)、下(y=ymin)、左(x=xmin)、右(x=xmax)描述。

判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分 裁剪处理的基础: 1)图元关于窗口内外关系的判别; 裁剪的目的: 判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分 裁剪处理的基础: 1)图元关于窗口内外关系的判别; 2)图元与窗口的求交  假定条件: 矩形裁剪窗口----[xmin,xmax]X[ymin,ymax]            待裁剪线段---- p0(x0,y0),p1(x1,y1)

3)线段至少有一端点在窗口之外,但非显然不可见. 待裁剪线段和窗口的关系: 1)线段完全可见;  2)显然不可见; 3)线段至少有一端点在窗口之外,但非显然不可见. 实交点是直线段与窗口矩形边界的交点。 虚交点则是直线段与窗口矩形边界延长线或直线段的延长线与窗口矩形边界的交点。

6.5.1点的裁剪 对于任意一点p (x , y) ,若满足下列两对不等式 且 则点 P 在矩形窗口内,否则,P 在矩形窗口外。

6.5.2直线段的裁剪 1.直线段的直接求交算法

2.Cohen-Sutherland算法 算法的思想:对于每条线段P0P1分为三种情况处理。 若两端点P0P1完全在窗口内,则完全可见该线段P0P1 。否则进入下一步; 若线段P0P1明显在窗口外,即显然不可见,则丢弃该线段,否则进入下一步; 若线段既不满足(1)的条件,也不满足(2)的条件,则在交点处把线段分为两段。其中一段完全在窗口外,可弃之。然后对另一段重复上述处理。

窗口及区域编码 延长窗口的边,将二维平面分成九个区域。每个区域赋予4位编码Ct Cb Cr Cl.其中各位编码的定义如下:

裁剪一条线段时,先求出端点 P0 和 P1的编码code0 和code1,然后进行处理。 (3)若上述两条件均不成立。则需求出直线段与窗口边界的交点。在交点处把线段一分为二,其中必有一段完全在窗口外,可以弃之。再对另一段重复进行上述处理,直到该线段完全被舍弃或者找到位于窗口内的一段线段为止。 特点:对显然不可见线段的快速判别

求窗口边界与线段 p0p1 的交点: 1)左右边界交点的 y 坐标 y = y0 + k ( x - x0 ) 其中 x =xmin(左边界交点) 或 x = xmax为(右边界交点) 斜率 k =(y1-y0)/(x1-x0) 2)上、下边界交点的 x 坐标 x = x0 + ( y - y0 ) / k 其中y =ymin(下边界交点) 或 y = ymax为(上边界交点)

Cohen-Sutherland算法的步骤: (1)输入直线段的两端点坐标:p0(x0,y0)、 p1(x1,y1),以及窗口的四条边界坐标:xmin、ymin、xmax和ymax。 (2)对p0、p1进行编码:点p0的编码为code0点,p1的编码为code1。 (3)若code0|code1=0,对直线段应简取之,转(6);否则,若code0&code1≠0,对直线段可简弃之,转(7);当上述两条均不满足时,进行步骤(4)。 (4)确保p在窗口外部:若p0在窗口内,则p0坐标值和编码赋给p;否则将p1 的坐标值和编码赋给p。 (5)按左、右、上、下的顺序求出直线段与窗口边界的交点,并用该交点的坐标值替换p的坐标值。也即在交点s处把线段一分为二,并去掉ps这一段。考虑到p是窗口外的一点,因此可以去掉p s。转(2)。 (6)用直线扫描转换算法画出当前的直线段p0 p1。 (7)算法结束。 

typedef struct { unsigned all; Unsigned left, right, top, bottom }OutCode; void CohenSutherlandLineClip (float x0, float y, float x1, float y1, Rectangle *rect ) / * p0(x0,y0)p1(x1,y1)为待裁剪线段, * rect为裁剪窗口* / { void CompOutCode (float , float , Rectangle *, OutCode *); boolean accept,done; OutCode outCode0, outCode1; OutCode * outCodeOut; float x,y; accept=FALSE; done=FALSE; CompOutCode(x0, y0, rect, &outCode0); CompOutCode(x1, y1, rect, &outCode1); do{ if (outCode0.all = = 0 &Code1.all = = 0) /*完全可见*/ {accept = TRUE; done = TRUE;} }

else if ( (outCode0.all&outCode1.all) != 0) done =TRUE; /*显然不可见*/ else /*求交测试*/ { if ( outCode0.all != 0) /*判断哪点位于窗口外,并赋给outCodeOut*/ outCodeOut = &outCode0; else outCodeOut = &outCode1; if (OutCodeOut -> left ) /*线段与窗口的左边求交*/ {y = y0 + (y1 – y0) * (rect -> xmin - x0)/(x1-x0); x=(float)rect -> xmin;} else if (OutCodeOut -> top) /*线段与窗口的上边求交*/ {x= x0 + (x1 – x0) * (rect -> ymax - y0)/(y1-y0); y=(float)rect -> ymax;} else if (OutCodeOut -> right) /*线段与窗口的右边求交*/ {y = y0 + (y1 – y0) * (rect -> xmax - x0)/(x1-x0); x=(float)rect -> xmax;} else if (OutCodeOut -> bottom)/*线段与窗口的下边求交*/ {x= x0 + (x1 – x0) * (rect -> ymin - y0)/(y1-y0); y=(float)rect -> ymin;}

if (outCodeOut -> all = = outCode0.all)/*将线段位于窗口边所在的直线外侧丢弃*/ { x0 = x ; /*对剩余部分继续裁剪*/ y0 = y ; CompOutCode( x0, y0, rect , &outCode0); } else { x1 =x ; y1=y ; CompOutCode(x1 , y1 , rect , & outCode1) ;} } } while (!done) If (accept) /*显示线段的部分*/ line (( int) x0 , ( int )y0, ( int) x1, ( int) y1 ); }/*end of CohenSutherlanLineClip()*/ void CompOutCode (float x , float y, Rectangle *rect, OutCode *outCode) { outCode -> all=0; /*计算点(x,y)的编码*/ outCode -> top =outCode -> bottom = 0; outCode -> left = outCode ->right = 0; if (y > (float) rect -> ymax) { outCode -> top = 1; outCode ->all + =1;}

if (y< (float) rect -< ymin) { outCode ->bottom = 1; outCode ->all + =1;} if (x > (float) rect -> xmax) { outCode -> right = 1; if (x< (float) rect -< xmin) { outCode ->left = 1; } } /*end of CompOutCode()*/

3.中点分割算法 方法:分别从P0、P1出发寻找距P0、P1最近的可见点。 从p0出发寻找距离p0最近的可见点A. 与Cohen-Sutherland算法一样首先对线段端点进行编码,并把线段与窗口的关系分为三种情况: 全在、完全不在和线段和窗口有交。对前两种情况,进行一样的处理。对于第三种情况,用中点分割的方法求出线段与窗口的交点。 方法:分别从P0、P1出发寻找距P0、P1最近的可见点。 从p0出发寻找距离p0最近的可见点A. 1)先求出p0p1中点pm; 2)若p0pm不是显然不可见,则用p0pm代替p0p1,否则pmp1 代替p0p1。 3)对新的p0p1求中点pm,重复2),直到p0p1长度小于控制常数ε(通常取1个像素)。 从p1出发寻找距离p1最近的可见点B方法类似。 特点:该算法只用到加法和除2运算,易于硬件实现。

中点算法框图(从p0出发,寻找距p0最近的可见点)

4.Liang-Barsky算法 x = x1 + u . (x2 - x1) 算法的出发点是直线的参数方程。任一直线的参数方程为: x = x1 + u . (x2 - x1) y = y1 + u . ( y2 - y1) 0 < u < 1 如果直线上一点(x ,y )位于由坐标(wxl ,wyb ) 和 (wxr, wyt) 所确定的窗口内,则有下式成立: wxl ≤x1 + u . (x2-x1) ≤wxr wxb ≤y1 + u .(y2-y1) ≤wyt 即 u . (x1 – x2) ≤x1- wxl u . (x2 - x1) ≤wxr – x1 u . (y1 – y2) ≤y1- wyb u . (y2 - y1) ≤wyt – y1 令 △x = x2 – x1,  △y = y2 – y1 代入上式可得

根据窗口四条边与有向线段p1p2相交的顺序将这们分成两类,一类称为始边,一类称为终边。 始边 终边 令 p1 = -△x q1 = x1 – wxl ( 窗口左边的交点 L) p2 = △x q2= wxr – x1 (窗口右边的交点 R) p3 = -△y q3 = y1 – wyb (窗口下边的交点 B) p2 = △y q2= wyt – y1 (窗口上边的交点 T) 于是有 u . PK ≤ qk 根据窗口四条边与有向线段p1p2相交的顺序将这们分成两类,一类称为始边,一类称为终边。 始边 终边 △x≥0 时 x = wxl x = wxr △x<0 时 x = wxr x = wxl △y≥0 时 y = wyb y = wyt △y<0 时 y = wyt y = wyb

情况一:任何平行于裁剪边界之一的直线pk=0,其中k对应于裁剪边界(k=1,2,3,4对应于左、右、下、上边界)如果还满足qk<0,则线段完全在边界外,舍弃该线段。如果qk≥0,则该线段平行于裁剪边界并且在窗口内。

情况二:当pk<0,线段从裁剪边界延长线的外部延伸到内部。当pk>0,线段从裁剪边界延长线的内部延伸到外部。当pk≠0,可以计算出线段与边界k的延长线的交点的u值:u=qk/pk

对于每条直线,可以计算出参数umax和umin,它们定义了在裁剪矩形内的线段部分。 umax的值由线段从外到内遇到的矩形边界所决定(pk<0)。对这些边界计算uk=qk/pk 。 umax取0和各个uk值之中的最大值。 Umax=max(0, uk|pk<0 ,uk|pk<0) 始边交点 umin的值由线段从内到外遇到的矩形边界所决定(pk>0)。对这些边界计算uk=qk/pk 。 umin取1和各个uk值之中的最小值。 Umin=min(uk|pk>0, uk|pk>0, 1)  终边交点 如果umax > umin ,则线段完全落在裁剪窗口之外,被舍弃。否则裁剪线段由参数u的两个值u1,u2计算出来。

#define TRUE 1 #define FALSE 0 #define round(a) (int) (a+0.5) Bool LBLineClipTest(float p, float q, float *umax, float *umin ) {float r; int Returnvalue = TRUE; if (p<0.0){ r=q/p; if ( r> *umin) Returnvalue = FALSE; else if ( r > *umax) *umax = r; } else if (p>0.0) { r = q / p ; if ( r< *umax) Returnvalue = FALSE; else if ( r < *umin) *umin = r; } else if ( q < 0.0) Returvalue = FALSE; return ( Returnvalue); } Void LBLineClip( float wxl, float wxr, float wyb, float wyt, float x1,float y1, float x2,float y2)

{float umax, umin ,deltax, delty; Deltax = x2 - x1; Umax=0.0; umin=1.0; If ( LBLineClipTest (-deltax, x1-wxl, &umax, &umin) ) /*L*/ if ( LBLineClipTest (deltax, wxr-x1, &umax, &umin) ) { /*R*/ deltay=y2-y1; if ( LBLineClipTest (-deltay, y1-wyb, &umax, &umin) ) /*B*/ if ( LBLineClipTest (deltay, wyt – y1 , &umax, &umin) ) { /*L*/ if ( umin < 1.0){ x2= x1 + umin *deltax; y2= y1+ umin * deltay; } if (umax >0.0) { x1 = x1+ umax * deltax; y1= y1 + umax * deltay; } Bresenhamline(round (x1), round (y1),round(x2),round(y2) ); }

6.5.3 多边形的裁剪 新的问题: 1)可能使原来封闭的多边形变成不封闭的或者一些离散的线段。 2)有可能把一个多边形分成几个隔离的部分

1.Sutherland-Hodgman算法 基本思想:逐边裁剪、两次分解、流水线业 先将多边形对于矩形窗口的裁剪分解为对窗口四边所在直线的裁剪 其次,将多边形对一条直线的裁剪分解为各边对直线的裁剪。 流水线过程:左下右上

沿着多边形依次处理顶点会遇到四种情况: 设当前预处理的顶点是P,先前已处理的顶点是S,多边形各顶点的处理规则如下: P在可见侧,保存P;否则不保存P P和S在边的非同侧,则求交点I,并将点I保存,将它插入P之前或S之后。

Sutherland-Hodgeman算法在处理凹多边形时,只能对裁剪之后仍为一个连通图的凹多边形产生正确的结果。 改进方法:分割成两个或更多的凸多边形或采用Weiler-Atherton算法。 优点:可推广到任意凸多边形裁剪窗口

2.Weiler-Atherton多边形裁剪 如果主多边形与裁剪多边形有交点,则交点成对出现,它们被分为如下两类: 进点:主多边形边界由此进入裁剪多边形 如,I1,I3, I5, I7, I9, I11 出点:主多边形边界由此离开裁剪多边形区域. 如, I0,I2, I4, I6, I8, I10

Weiler_Athenton裁剪算法(内裁剪)步骤: 1、建立主多边形和裁剪多边的顶点表. 2、求主多边形和裁剪多边形的交点,并将这些交点按顺序插入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立双向指针 。 3、裁剪 如果存在没有被跟踪过的交点,执行以下步骤: (1)建立裁剪结果多边形的顶点表. (2)选取任一没有被跟踪过的交点为始点,将其输出到结果多边形顶点表中. (3)如果该交点为进点,跟踪主多边形边边界;否则跟踪裁剪多边形边界. (4) 跟踪多边形边界,每遇到多边形顶点,将其输出到结果多边形顶点表中,直至遇到新的交点. (5)将该交点输出到结果多边形顶点表中,并通过连接该交点的双向指针改变跟踪方向(如果上一步跟踪的是主多边形边界,现在改为跟踪裁剪多边形边界;如果上一步跟踪裁剪多边形边界,现在改为跟踪主多边形边界). (6)重复(4)、(5)直至回到起点

主多边形顶点表 裁剪多边形顶点表

交点的奇异情况处理 1、与裁剪多边形边重合的主多边形的边不参与求交点; 2、对于顶点落在裁剪多边形的边上的主多边的边,如果落在该裁剪边的内侧,将该顶点算作交点;而如果这条边落在该裁剪边的外侧,将该顶点不看作交点

6.5.4 其它裁剪 1. 曲线边界对象的裁剪 2. 文字裁剪 串精度裁剪 字符精度裁剪 笔划、象素精度裁剪 6.5.4 其它裁剪 1. 曲线边界对象的裁剪 曲线边界对象与矩形窗口和多边形窗口的裁剪 加速方法 2. 文字裁剪 串精度裁剪 字符精度裁剪 笔划、象素精度裁剪 

保留落在裁剪区域外的图形部分、去掉裁剪区域内的所有图形,这种裁剪过程称为外部裁剪,也称空白裁剪。 3. 外部裁剪 保留落在裁剪区域外的图形部分、去掉裁剪区域内的所有图形,这种裁剪过程称为外部裁剪,也称空白裁剪。 作 业 在三维坐标系Oxyz中,坐标系O’uvn的原点O’(0,1,0),u,v,n轴的方向矢量分别为(1,0,1),(-1,0,1),(0,-1,0),P点在Oxyz中的坐标为(-1,2, ), 1)求坐标系Oxyz到O’uvn的变换矩阵Mxyz-uvn. 2)求P点在坐标系O’uvn中的坐标。

1)u,v,n轴的方向矢量分别为(1,0,1),(-1,0,1),(0,-1,0),所以其单位矢量为( ,0, ),(- , 0, ),(0,-1,0 )。 2)