第六章_二维观察.ppt

1、第六章 二维观察,问题：如何方便地实现在显示设备上对二维图形进行观察,主要内容,6.1 观察流程 6.2 世界坐标系到观察坐标系的变换 6.3 裁剪 点的裁剪 线的裁剪 多边形的裁剪 字符串的裁剪,6.1 观察流程,基本概念 在计算机图形学中，将在世界坐标系中需要进行观察和处理的一个坐标区域称为窗口（Window） 将窗口映射到显示设备上的坐标区域称为视区（Viewport）,要将窗口内的图形在视区中显示出来，必须经过将窗口到视区的变换（Window-Viewport Transformation）处理，这种变换就是观察变换（Viewing Transformation）。,(1)、模型坐标系

2、（局部坐标系）：当构造单个对象的数字模型 时，为了方便,可以将其置于一个特定的坐标系下，即模型坐 标系或局部坐标系.,(2)、世界坐标系：为描述图形场景中所有图形之间的空间关系， 将它们置于一个统一的坐标系中，该坐标系被称为世界坐标系。,(3)、设备坐标系：要输出经过处理后的数字化图形，需要在输 出设备上建立一个坐标系，称为设备坐标系。,（4）、标准化（规格化）设备坐标系： 有些图形系统，对设备坐 标系进行了规范化，将坐 标范围限定在区间 x,y,z | 0 x1, 0y1, 0z1 内，称标准化设备坐标系,观察坐标系(View Coordinate)和规格化坐标系(Normalized De

3、vice Coordinate) 观察坐标系是依据窗口的方向和形状在世界坐标平面中定义的直角坐标系。 规格化坐标系也是直角坐标系，它是将二维的坐标系规格化到（0.0，0.0）到（1.0，1.0）的坐标范围内形成的。,引入了观察坐标系和规格化设备坐标系后，观察变换分为如下图所示的几个步骤，通常称为二维观察流程，或者二维观察变换流水线。,二维图形的显示流程图,从应用程序得到图形的用户坐标,对窗口区进行裁剪,窗口区到视图区的规格化变换,视图区从规格化坐标系到设备坐标系的变换,WC,VC,NDC,DC,在图形设备上输出,变焦距效果,整体放缩效果,漫游效果,6.2 世界坐标系到观察坐标系的变换 世界坐标

4、系到观察坐标系的变换分由两个变换步骤合成： 1. 将观察坐标系原点移动到世界坐标系原点,2. 绕原点旋转使两坐标系重合,窗口到视区的变换,要将窗口内的点（xw,yw）映射到相对应的视区内的点（xv,yv）需进行以下步骤： (1) 将窗口左下角点移至世界系统系的坐标原点 (2) 针对原点进行比例变换 (3) 进行反平移,窗口内的点（xw,yw）映射到对应视口的点（xv,yv），为保证视区与窗口中相同对象具有同样的相对位置，需满足：,窗口到视区的变换,窗口到视区的变换,6.3 裁剪,裁剪(定义): 识别指定区域内或区域外的图形部分的过程称为裁剪(clipping), 用来裁剪对象的区域成为裁剪窗口

5、 裁剪的应用: 点的裁剪、直线段的裁剪、多边形的裁剪、曲线边界对象的裁剪、文字的裁剪等,假设窗口是标准矩形，即边与坐标轴平行的矩形，由上（y=ywmax）、下（y=ywmin）、左（x= xwmin）、右（x= xwmax）四条边描述。 一、点的裁剪,二、直线段的裁剪 假定直线段用p1(x1,y1)p2(x2,y2)表示。则直线段和剪裁窗口的可能关系： 完全落在窗口内 完全落在窗口外 与窗口边界相交,实交点是直线段与窗口矩形边界的交点。 虚交点则是直线段与窗口矩形边界延长线或直线段的延长线与窗口矩形边界的交点。,直接求交算法,直线与窗口边都写成参数形式，求参数值。,三种直线裁剪方法： Suth

6、erlandCohen算法 中点分割算法 梁友栋-Barsky算法（Cyrus-Beck算法和梁友栋Barsky算法）,1、算法的的基本思想：对于每条线段P1P2分为三种情况处理。 （1）若P1P2完全在窗口内，则显示该线段P1P2简称“取”之。 （2）若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。 （3）若线段既不满足“取”的条件，也不满足“弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。,具体如何操作呢？,1 Sutherland-Cohen算法,2、SutherlandCohen算法分成两部分： 第一步是判定： 1) 完全在窗口内的直线

7、段，称为 完全可见的线段； 2) 完全在窗口外的线段，称为 完全不可见线段。 第二步处理不能断定为完全可见或完全不可见的线段。 *这时需要计算出直线段和窗口边界的一个交点，这个交点把直线分成两段，其中一条为完全不可见的线段,被抛弃。 *对余下部分再作第一步的判断，重复上述过程，直到直线段余下的部分可用第一步的判断得出肯定的结论为止。,Sutherland-Cohen算法,a:算法的第一步 判断完全可见/不可见,在x=xL左侧的区域,编码的第四位是1； 在x=xR右侧的区域,编码的第三位是1； 在y=yB下侧的区域,编码的第二位是1； 在y=yT上侧的区域,编码的第一位是1。,为使计算机能够快速

8、判断一条直线段与窗口属何种关系，采用如下编码方法。窗口的四条边把整个平面分成九个区域，每一个区域采用四位编码表示：,对要被裁剪的线段的两个端点，如果其所在的区域的编码均是 0000（逻辑或为0）,则这条线段完全可见； 如果两个编码的逻辑与不为0000，则这条线段完全不可见,如何判断,具体步骤,b:算法的第二步,线段KL为例，从K点(1001)的编码分析出K在x=xL的左侧，KL必和x=xL有交点， 求出其交点M，KM显然是完全不可见的，因而只要对ML从第一步开始重复上述处理步骤。 由于ML还是不能用第一步下结论，又从M的编码发现M在y=yT的上侧，因而要求ML和y=yT的交点N。 丢掉MN，对

9、NL用第一步的方法可断定NL为完全可见，至此裁剪结束。,K,M,N,xL,xR,yT,yB,L,程序代码,float x1, xr, yt, yb; public int code(float x, float y) int c = 0; if (x xr) c = c|2; if (y yt) c = c|8; return c; Sutherland_Cohen(float x0,float y0,float x2,float y2) int c1,c2,c; float x,y,wx,wy; bool accept=false, done=false; c1=code(x0,y0); c

10、2=code(x2,y2); do if (c1|c2)=0) accept=true; done=true; ,else if(c1 ,为端点按编码原则进行编码,两个都为0则必在内部,即c1!=0 y0 = y; c1 = code(x0, y0); else /终点不在窗口内，交点作为新的终点 x2 = x; y2 = y; c2 = code(x2, y2); While(donefalse) if (accept) drawLine(int(x0), int(y0), int(x2), int(y2); ,算法的步骤： (1) 输入直线段的两端点坐标：p1(x1,y1)、p2(x2,y

11、2)，以及窗口的四条边界坐标：xwmin、xwmax、ywmin、ywmax。 (2) 对p1、p2进行编码：点p1的编码为code1，点p2的编码为code2。 (3) 若code1|code2=0，对直线段应简取之，转(6)；否则，若code1 判断特殊情况即： Ni(p2-p1)0 如果Ni(p1-Ai)0则表明整条直线在 外侧，退出循环，结束。 否则， 即Ni(p2-p1)！0 按公式求解t 如果Ni(p2-p1)0 t与前一个出点比较，取小值为 新的出点参数值为te 否则t t与前一个出点比较，取大值为 新的出点参数值为ts ,1、基本思想：当凸多边形是矩形窗口，且矩形的边平行于坐标

12、轴时，前述算法即Cyrus-Beck算法可简化为梁友栋-Barsky算法。 2、分析：对于窗口的每条边，表6.1列出了其内法向量 ，该边上一点 ,从 指向线段起点P1 的向量 ，以及线段与该边(或延长线)的交点参数。由于每条边上法向量只有一个非零分量,所以任意一个向量与法向量求内积的运算很简单.,梁友栋-Barsky算法,表6.1 梁友栋-Barsky算法所用的量,设x=x2x1，y=y2y1，令,上述终点组和起点组的特征分别表现为rk0和rk0时，将进入k边界的外侧；rk0时，将进入k边界的内侧。若rk=0时sk0,线段完全不可见.,实际就是判断Ni(p2-p1)0还是0,实际上就是判断Ni

13、(p1-Ai)0则表明整条直线在外侧。,初始化线段在边界内的端点参数为ts=0、te=1。 计算出各个裁剪边界的r、s值。 当r=0且s0时，参数t用于更新te。 如果更新了ts或te后，若tste，则舍弃该线段。,3、梁友栋-Barsky算法的基本步骤,具体梁友栋-Barsky算法过程,设要裁剪的线段是P0P1。 P0P1和窗口边界交于A,B,C,D四点，见图。算法的基本思想是从A,B和P0三点中找出最靠近P1的点，图中要找的点是P0。从C,D和P1中找出最靠近P0的点。图中要找的点是C点。那么P0C就是P0P1线段上的可见部分。,梁友栋-Barsky算法,梁友栋-Barsky算法,线段的参

14、数表示 x=x0+tx y=y0+ty 0=t=1 x=x1-x0 y=y1-y0 窗口边界的四条边分为两类：始边和终边。,求出P0P1与两条始边的交点参数t0, t1 , 令tl=max(t0 ,t1,0)，则tL即为三者中离p1最近的点的参数 求出p0p1与两条终边的交点参数t2, t3, 令tu=min(t2,t3,1) ，则tU即为三者中离p0最近的点的参数 若tu tl,则可见线段区间tl , tu,0,梁友栋-Barsky算法：交点计算,梁友栋-Barsky算法,始边和终边的确定及交点计算： 令 QL= - x DL= x0-xL QR= x DR= xR-x0 QB= - y D

15、B= y0-yB QT= y DT= yT-y0 交点为 ti= Di / Qi i=L,R,B,T Qi 0 ti为与终边交点参数 Qi =0 Di 0 时, 分析另一D,E,F,A,B,梁友栋-Barsky算法,当Qi =0时 若Di 0 时, 分析另一D, （如图中的EF就是这种情况，它使QL=0，DL0和QR=0，DR0。这时由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交点，而让EF和y=yT及y=yB的交点决定直线段上的可见部分。）,算法步骤： (1) 输入直线段的两端点坐标：(x1,y1)和(x2,y2)，以及窗口的四条边界坐标：xwmin、xwmax、

16、ywmin、ywmax。 (2) 若x=0，则p1=p2=0。此时进一步判断是否满足q10且q20，则进一步计算uu和ul。算法转(5)。 (3) 若y=0，则p3=p4=0。此时进一步判断是否满足q30且q20，则进一步计算uu和ul。算法转(5)。 (4) 若上述两条均不满足，则有pk0（k=1,2,3,4）。此时计算uu和ul。 (5) 求得uu和ul后，进行判断：若ul uu，则直线段在窗口外，算法转(7)。若 ul uu，利用直线的参数方程求得直线段在窗口内的两端点坐标。 (6) 利用直线的扫描转换算法绘制在窗口内的直线段。 (7) 算法结束。,梁友栋-Barsky算法与Cohen-

17、Sutherland算法比较 梁友栋-Barsky算法更具效率 梁友栋-Barsky算法与Cohen-Sutherland算法都可以扩展为三维剪裁算法,三、多边形的裁剪,问题的提出： 对于多边形，线段裁剪进行处理后的多边形边界显示为不连接的线段,三、多边形裁剪,错觉：直线段裁剪的组合？ 新的问题：1）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？,三、多边形裁剪,2）一个凹多边形可能被裁剪成几个小的多边形，如何 确定这些小多边形的边界？,分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。 流水线过程(左上右下)：前边的结果是后边的输入。,亦称逐边

18、裁剪算法,Sutherland-Hodgman算法,1、基本原理：只要对多边形用窗口的四条边依次裁剪四次便可得到裁剪后的多边形。 每次用窗口的一条边界(包括延长线)对要裁剪的多边形进行裁剪，裁剪时，顺序地测试多边形各顶点，保留边界内侧的顶点，删除外侧的顶点，同时，适时地插入新的顶点：即交点和窗口顶点，从而得到一个新的多边形顶点序列。 然后以此新的顶点序列作为输入，相对第二条窗边界线进行裁剪，又得到一个更新的多边形顶点序列。 依次下去，相对于第三条、第四条边界线进行裁剪，最后输出的多边形顶点序列即为所求的裁剪好了的多边形。如下图所示。,Sutherland-Hodgman算法,a: 算法的输入是

19、以顶点序列表示的多边形，输出也是一个顶点序列，构成一个或多个多边形。 b: 考虑以窗口的一条边及其延长线构成的裁剪线，该线把平面分成两部分：一部分包含窗口，称为可见侧；另一部分称为不可见侧。,裁剪线AR,可见侧,不可见侧,Sutherland-Hodgman算法新的多边形的顶点序列的产生,c:线段端点S、P与裁剪线的位置关系,每条线段端点S、P与裁剪线比较后可输出0至2个顶点。 情况1： S、P都在可见一侧，则输出P。 情况2： S、P都在不可见一侧，则不输出顶点。 情况3： S在可见一侧，P在不可见一侧，则输出SP与 裁剪线的交点点I。 情况4： S在不可见一侧，P在可见一侧，则输出SP与

20、裁剪线的交点点I和P 。,输出I1和P2,输出P3,输出I2,无输出,处理线段SP子过程,主框图,算法框图,Sutherland-Hodgman算法,上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。 对于每一条裁剪边，算法框图同上，只是判断点在窗口哪一侧以及求线段SP与裁剪边的交点算法应随之改变。,Sutherland-Hodgeman算法,对凸多边形应用本算法可以得到正确的结果，但是对凹多边形的裁剪将如图所示显示出一条多余的直线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。

21、,Sutherland-Hodgeman算法,解决这个问题有多种方法: 一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。 二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。 再有就是Weiler-Atherton算法。,Sutherland-Hodgman算法,思考： 如何推广到任意凸多边形 裁剪窗口？,Weiler-Atherton多边形裁剪 基本思想：有时沿多边形某一条边的方向来处理顶点，有时沿窗口的边界方向处理。一般按逆时针（顺时针）以及当前处理多边形顶点对是由外到内还是由内到外。,下图示了Weiler-Atherton算法裁剪凹多边形的过程和结果,Wei

22、ler-Athenton算法,裁剪窗口为任意多边形（凸、凹、带内环）的情况： 主多边形：被裁剪多边形，记为A 裁剪多边形：裁剪窗口，记为B,Weiler-Athenton算法,多边形顶点的排列顺序（使多边形区域位于有向边的左侧 ）外环：逆时针 ；内环：顺时针 主多边形和裁剪多边形把二维平面分成两部分。 内裁剪：AB 外裁剪：A-B,裁剪结果区域的边界由A的部分边界和B的部分边界两部分构成，并且在交点处边界发生交替，即由A的边界转至B的边界，或由B的边界转至A的边界,Weiler-Athenton算法,如果主多边形与裁剪多边形有交点，则交点成对出现，它们被分为如下两类：,进点：主多边形边界由此进

23、入裁剪多边形内 如，I1,I3, I5, I7, I9, I11 出点：主多边形边界由此离开裁剪多边形区域. 如， I0,I2, I4, I6, I8, I10,Weiler-Athenton算法,1）建顶点表； 2）求交点； 3）裁剪 ,1、建立主多边形和裁剪多边的顶点表 2、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立双向指针 。 3、裁剪: 如果存在没有被跟踪过的交点，执行以下步骤：,Weiler-Athenton算法,(1)建立空的裁剪结果多边形的顶点表 (2)选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中 (3)如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪多边形边界 (4