二维裁剪算法的研究费下载

《二维裁剪算法的研究费下载》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、二维裁剪算法的研究专业班别：计算机科学与技术08・1班姓名：陆金泉学号：20082525摘要：近儿十年来，计算机图形学有了引人瞩目的发展,它已广泛应用于计算机辅助设计、电视广告、动画和仿真等许多领域并发挥着重要作用。可以说计算机图形学已经发展成为一门成熟的学科。在各种实践应用屮，计算机图形学的许多基础算法发挥着不可替代的重要作用，因此不断提高和完善图形学的基础算法至关重要。计算机图形学主耍研究的是在计算机屮构造图形，将用数学模型描述的图形数据采用合适的算法转换为屏幕上图形的显示。计算机图形学学科研究的对象为二维图形学和三维图形学及其显示和变

2、化情况。点、线、而为二维图形学范畴，几何体和场等数学构造方法则为三维图形学范畴。现在，计算机图形学的一些基本算法己经形成了同化在硬件屮的规范软件包，这个学科也H趋成熟和完善。但是依然冇很多算法还需要不断的改进才能应用到实际屮，而裁剪算法就是其屮之一。本文主要对二维图形裁剪屮的椭圆形窗口裁剪算法进行了研究，使其具冇较高的效率和稳定性。关键词：计算机图形学裁剪算法一裁剪概述裁剪算法，简称裁剪，是计算机图形学屮很多重要问题的基础，它就是从数据集合屮识别指定区域内或指定区域外图形部分的过程。裁剪用途很广泛，最典型的就是确定场景屮位于指定区域内的景物

3、部分。其屮，指定区域成为裁剪窗口，一般为矩形，由四条边组成，上、下、左、右，即：(XI,Yb),(Xr,Yt)o实质上来说，裁剪就是确定哪些多边形等几何体位于裁剪窗口内。对于点(X,Y),只要判断两对不等式：Xl

4、法大概分为如下儿种：点裁剪、直线段裁剪、区域多边形裁剪、曲线裁剪和文字裁剪。直线段裁剪乂包含有矩形窗口的直线段裁剪、多边形窗口的直线段裁剪、圆形窗口的直线段裁剪。裁剪有多方面应用，主要包拈：使用实体造型创建对象、在三维视图中标示出可见面、对图形的一部分进行删除、复制或移动操作、防止图形边界混淆、从特定场景中抽取指定部分等。在不同的应用中，裁剪窗口的形状也不尽相同。然而，裁剪算法是否高效关键在减少求交运算，高效识别裁剪线段是否与裁剪窗口边界相交。二维裁剪算法分为两种，对二维线段的裁剪以及对二维多边形的裁剪，在这两方面，国内外许多专家学者都进行

5、了深入的研究，出现了很多经典算法。对于前者，比较经典的算法有便于硕件实现的中点分割算法，基于编码技术的Cyrus-Berk裁剪算法，Nicholl等提出的基于儿何变换技术的NLN算法，通过法向点积判别的Cyrus-Berk裁剪算法，在NLN算法基础上发展的ELC算法，以及Liang-Barsky算法等。另外，还有一种比较高效的只用整数运算来计算整数交点的线裁剪算法，是由M.Dorr综合了直线参数表示方法和Cohen-Sutherland的编码方法而得到的。二Cyrus-Berk裁剪算法方法，求出两个端点的t值，通过两个t值的位置关系判断线段

6、与裁剪面的相对位置。2D：1、将线段表示为参数化方程p=pl+(p2-pl)*t,(0<=t<=1)2、令dx=x2-xl,dy=y2-yl,以坐标分量表示：x=xl+dx*ty=yl+dy*t3、位于裁剪区域内条件：xmin<=xl+dx*t<=xmaxymin<=yl+dy*t<=ymax转化并化简：左边界不等式(n=0)：・dx*t<=(・xmax+xl)右边界不等式(n=1)：dx*t<=(xmax-xl)上边界不等式(n=2)：dy*t<=(ymax-yl)下边界不等式(n=3)：・dy*t<=(ymax+yl)5、将不等式统一看

7、成pn*t=qn的形式：pn=O,线段与边界平行，不可能相交pn>=0,线段位于边界内侧pn<0,线段位于边界外侧pn<0,线段穿过边界进入裁剪区pn>0,线段穿过边界离开裁剪区6、若为条件1、2、3,则拒绝若为上述第4、5个条件，将不等式转换为:t=qn/pn,对每个不等式求解t,结果依次为rn(rO-r3),根据pn的符号将rn分成两组，根据进入裁剪区的那组计算tl：tl=max(0,r0,r3)根据离开裁剪区的那组计算t2：t2=min(1,rl,r2)7、若tl>t2,表明线段位于裁剪区外，否则将tl和t2分别代入参数方程屮，求出两

8、个点的坐标，它们是裁减后的线段的端点三ELC算法椭鬪形不仅是计算机图形学中的基木儿何元素么一，而且许多实际问题的解决中，椭圆也是作为处理对象进行操作的。对于计算机图形学中的裁剪算