二维裁剪算法的研究.doc

二维裁剪算法的研究专业班别：计算机科学与技术08-1班 姓名：陆金泉 学号：20082525摘要：近几十年来,计算机图形学有了引人瞩目的发展,它已广泛应用于计算机辅助设计、电视广告、动画和仿真等许多领域并发挥着重要作用。可以说计算机图形学已经发展成为一门成熟的学科。在各种实践应用中,计算机图形学的许多基础算法发挥着不可替代的重要作用,因此不断提高和完善图形学的基础算法至关重要。 计算机图形学主要研究的是在计算机中构造图形，将用数学模型描述的图形数据采用合适的算法转换为屏幕上图形的显示。计算机图形学学科研究的对象为二维图形学和三维图形学及其显示和变化情况。点、线、面为二维图形学范畴，几何体和场等数学构造方法则为三维图形学范畴。 现在，计算机图形学的一些基本算法已经形成了固化在硬件中的规范软件包，这个学科也日趋成熟和完善。但是依然有很多算法还需要不断的改进才能应用到实际中，而裁剪算法就是其中之一。本文主要对二维图形裁剪中的椭圆形窗口裁剪算法进行了研究，使其具有较高的效率和稳定性。 关键词：计算机图形学 裁剪算法 一 裁剪概述 裁剪算法，简称裁剪，是计算机图形学中很多重要问题的基础，它就是从数据集合中识别指定区域内或指定区域外图形部分的过程。裁剪用途很广泛，最典型的就是确定场景中位于指定区域内的景物部分。其中，指定区域成为裁剪窗口，一般为矩形，由四条边组成，上、下、左、右，即：(Xl，Yb)，(Xr，Yt)。实质上来说，裁剪就是确定哪些多边形等几何体位于裁剪窗口内。对于点(X，Y)，只要判断两对不等式：XlXXr，YbYYt即可。 如果四个点坐标的不等式都不成立，则这个点在矩形窗口外，否则，在窗口内。有一种最简单的裁剪方法，就是将所有图形扫描转换成点，然后在进行判断。但是这种方法时间消耗太大，非常不可取。倘若将全部在窗口外的图形完全排除而不进行扫描转换，则时间上面可以高效很多，故一般采用先裁剪再扫描的方法。 按裁减对象来分，裁剪算法大概分为如下几种：点裁剪、直线段裁剪、区域多边形裁剪、曲线裁剪和文字裁剪。 直线段裁剪又包含有矩形窗口的直线段裁剪、多边形窗口的直线段裁剪、圆形窗口的直线段裁剪。裁剪有多方面应用，主要包括：使用实体造型创建对象、在三维视图中标示出可见面、对图形的一部分进行删除、复制或移动操作、防止图形边界混淆、从特定场景中抽取指定部分等。在不同的应用中，裁剪窗口的形状也不尽相同。然而，裁剪算法是否高效关键在减少求交运算，高效识别裁剪线段是否与裁剪窗口边界相交。 二维裁剪算法分为两种，对二维线段的裁剪以及对二维多边形的裁剪，在这两方面，国内外许多专家学者都进行了深入的研究，出现了很多经典算法。对于前者，比较经典的算法有便于硬件实现的中点分割算法，基于编码技术的Cyrus-Berk裁剪算法，Nicholl等提出的基于几何变换技术的NLN算法，通过法向点积判别的Cyrus-Ber k裁剪算法，在NLN算法基础上发展的ELC算法，以及Liang-Bars ky算法等。另外，还有一种比较高效的只用整数运算来计算整数交点的线裁剪算法，是由M.Dorr综合了直线参数表示方法和Cohen-Suthcrland的编码方法而得到的。二 Cyrus-Berk裁剪算法方法，求出两个端点的t值，通过两个t值的位置关系判断线段与裁剪面的相对位置。2D：1、将线段表示为参数化方程 p = p1 +（p2 - p1）* t，（0 = t = 1）2、令dx = x2 - x1，dy = y2 - y1，以坐标分量表示： x = x1 + dx * t y = y1 + dy * t3、位于裁剪区域内条件： xmin = x1 + dx * t = xmax ymin = y1 + dy * t = ymax 转化并化简： 左边界不等式（n = 0）：-dx * t =（-xmax + x1） 右边界不等式（n = 1）： dx * t =（ xmax - x1） 上边界不等式（n = 2）： dy * t =（ ymax - y1） 下边界不等式（n = 3）：-dy * t = 0，线段位于边界内侧 pn 0，线段位于边界外侧 pn 0，线段穿过边界离开裁剪区6、若为条件1、2、3，则拒绝 若为上述第4、5个条件，将不等式转换为：t = qn / pn，对每个不等式求解t， 结果依次为rn（r0 - r3），根据pn的符号将rn分成两组，根据进入裁剪区的那组计算t1： t1 = max（0，r0，r3） 根据离开裁剪区的那组计算t2： t2 = min（1，r1，r2）7、若t1 t2，表明线段位于裁剪区外，否则将t1和t2分别代入参数方程中，求出 两个点的坐标，它们是裁减后的线段的端点三 ELC算法椭圆形不仅是计算机图形学中的基本几何元素之一，而且许多实际问题的解决中，椭圆也是作为处理对象进行操作的。对于计算机图形学中的裁剪算法来说，关于椭圆形窗口的裁剪算法是非常重要的。设标准椭圆的方程为： x2/a2 y2/b2=1 其中，标准椭圆的中心点为坐标轴的原点O，假设A(Xa，Ya)、B(Xb，Yb)(XaXb)为被裁剪线段的两个端点，则裁剪可按如下步骤进行： 2.1 特殊情况的处理 当Xa=Xb时，即坐标轴的纵轴与被裁减的线段平行，这时分为两种情况，线段完全位于椭圆外部，即Xaa；否则，则需求取椭圆和线段的交点，其横坐标设为Xa。 当Ya=Yb时，即坐标轴的横轴与被裁剪线段平行，这时也有两种情况，线段完全位于椭圆外部；即Yab；否则，求需要求椭圆与线段的交点，其纵坐标均为Ya。 2.2 去除所有位于椭圆外切矩形外的线段。本步采用外切矩形包围盒的方法，外切矩形由四条直线组成，x=-a、x=a、y =-b、y=b。当min(Xa，Xb)a或max(Xa，Xb)-a或min(Ya，Ybb或maxYa，Yb)-b时，线段AB位于外切矩形的同侧，然后转步骤3。 2.3 线段端点与椭圆窗口的位置关系 椭圆有一条基本性质，即圆周上任意一点到两个定点的距离和等于特定常数。又由椭圆方程可得，a为椭圆的长半轴长度，因此可以根据线段的两端点到椭圆两焦点的距离之和是否小于2a的方法，来确定线段的端点是否位于椭圆内。因为椭圆上任意一点到两焦点的距离之和等于2a，在椭圆外部的点，到两焦点的距离之和大于2a，而在椭圆内部的点，到两焦点的距离之和大于2a。 最简单的直接可以显示的情况就是，线段两端点均位于椭圆内部，进而不需要求交点，因为该线段移动位于椭圆内。另一种情况就是线段与椭圆有一个交点，即线段的一个端点在椭圆内，一个在椭圆外，此时要通过联立线段与椭圆的方程求出交点，进而得到交点和位于椭圆内的端点之间的线段，即为所求。最复杂的情况就是线段的两个端点均位于椭圆外，这个时候，又有两种情况产生： 线段完全位于椭圆窗口外，二者无交点，则可判定裁剪结束。 当椭圆与线段有两个交点时，要进行如下区分，首先过原点O向线段AB做垂线交线段AB于点P(Xp，Yp)，设L为椭圆两个焦点与P的距离和。此时点P分为如下情况：当Xa xa2a，b2a，点P位于椭圆外部，可以根据平行于线段AB且与椭圆相切的线段CD来判断。假设设OP与CD的交点为R，上一步切点为Q，由于CD平行于AB，因此OP垂直于CD，垂足设为R，Lr为OR的距离。如果LpLr，则椭圆在线段CD的一侧，线段AB在线段CD的另一侧，这个时候，椭圆与AB无交点，因此不必显示。若Lp三 椭圆形窗口线裁剪算法实现 椭圆形窗口裁剪算法的伪代码如下，其中，裁剪后所得线段的两个端点设为(X1，Y1)、(X2，Y2)，线段两端点到椭圆焦点的距离之和为Da、Db，原点O到AB的垂足为P(Xp，Yp)，平行于线段AB且和椭圆相切的线段CD到中心点的距离为Lt。 if (Xa = Xb) if( Xa a) break；/被裁剪线段完全位于椭圆窗口外的情况 else X1=X2=Xa； else if(Ya = Yb) if(Ya b) break；/被裁剪线段完全位于椭圆窗口外的情况 else Y1=Y2 =Ya； else if(minXa，Xba或maxXa，Xb-a 或min(Ya，Yb)b或maxYa，Yb-b) break；/被裁剪线段完全位于椭圆窗口外的情况 else if( Da 2a 四 Liang-Bars ky算法1. 算法的基本思想 以直线的参数方程为基础，对不同情况下的裁剪求得相应的参数值。2. 算法的推导过程情形一 pk=0（1）p1p20若q10或q2=0且q2=0,则进一步判断 u=qk/pk（k=3,4）令 u1=max(0,u|pk0)若u1u2,则可删除直线段若u1=u2,将u1,u2代入直线方程，得到直线段的两个可见端点。（2）p3p40若q30或q4=0且q4=0,则进一步判断 u=qk/pk（k=1,2）令 u1=max(0,u|pk0)若u1u2,则可删除直线段若u1=u2,将u1,u2代入直线方程，得到直线段的两个可见端点。情形二 pk不为0u=qk/pk（k=1,2,3,4）令 u1=max(0,u|pk0,u|pk0, u|pk0)若u1u2,则可删除直线段若u1=u2,将u1,u2代入直线方程，得到直线段的两个可见端点。3. 算法步骤(1)输入直线段的两端点坐标以及窗口的四条边界坐标。(2)若x=0，则p1=p2=0。进一步判断是否满足q10或q20且q20，则进一步计算u