计算机图形学论文：计算机图形学中二维裁剪算法的研究

计算机图形学论文：计算机图形学中二维裁剪算法的研究 计算机图形学论文:计算机图形学中二维裁剪算法的研究 摘要:随着计算机技术的发展，计算机图形学也日益成熟。在我们的日常生活中，也成了随处可见的必需部分。在医学、娱乐、图形艺术、商业、教育培训、科学 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 等众多领域，计算机图形学的应用非常普遍。 计算机图形学主要研究的是在计算机中构造图形，将用数学模型描述的图形数据采用合适的算法转换为屏幕上图形的显示。计算机图形学学科研究的对象为二维图形学和三维图形学及其显示和变化情况。点、线、面为二维图形学范畴，几何体和场等数学构造方法则为三维图形学范畴。 现在，计算机图形学的一些基本算法已经形成了固化在硬件中的规范软件包，这个学科也日趋成熟和完善。但是依然有很多算法还需要不断的改进才能应用到实际中，而裁剪算法就是其中之一。本文主要对二维图形裁剪中的椭圆形窗口裁剪算法进行了研究，使其具有较高的效率和稳定性。 关键词:计算机图形学 裁剪算法 椭圆形窗口线裁剪算法 1 裁剪概述 裁剪算法，简称裁剪，是计算机图形学中很多重要问题的基础，它就是从数据集合中识别指定区域内或指定区域外图形部分的过程。裁剪用途很广泛，最典型的就是确定场景中位于指定区域内的景物部分。其中，指定区域成为裁剪窗 口，一般为矩形，由四条边组成，上、下、左、右，即:(xl，yb)，(xr，yt)。实质上来说，裁剪就是确定哪些多边形等几何体位于裁剪窗口内。对于点(x，y)，只要判断两对不等式:xl?x?xr，yb?y?yt即可。 如果四个点坐标的不等式都不成立，则这个点在矩形窗口外，否则，在窗口内。有一种最简单的裁剪方法，就是将所有图形扫描转换成点，然后在进行判断。但是这种方法时间消耗太大，非常不可取。倘若将全部在窗口外的图形完全排除而不进行扫描转换，则时间上面可以高效很多，故一般采用先裁剪再扫描的方法。 按裁减对象来分，裁剪算法大概分为如下几种:点裁剪、直线段裁剪、区域多边形裁剪、曲线裁剪和文字裁剪。 裁剪有多方面应用，主要包括:使用实体造型创建对象、在三维视图中标示出可见面、对图形的一部分进行删除、复制或移动操作、防止图形边界混淆、从特定场景中抽取指定部分等。在不同的应用中，裁剪窗口的形状也不尽相同。然而，裁剪算法是否高效关键在减少求交运算，高效识别裁剪线段是否与裁剪窗口边界相交。 二维裁剪算法分为两种，对二维线段的裁剪以及对二维多边形的裁剪，在这两方面，国内外许多专家学者都进行了深入的研究，出现了很多经典算法。对于前者，比较经典的算法有便于硬件实现的中点分割算法，基于编码技术的 cyrus-berk裁剪算法，nicholl等提出的基于几何变换技术的nln算法，通过法向点积判别的cyrus-ber k裁剪算法，在nln算法基础上发展的elc算法，以及liang-bars ky算法等。另外，还有一种比较高效的只用整数运算来计算整数交点的线裁剪算法，是由m.dorr综合了直线参数表示方法和cohen-suthcrland的编码方法而得到的。 2 椭圆形窗口线裁剪算法描述 椭圆形不仅是计算机图形学中的基本几何元素之一，而且许多实际问题的解决中，椭圆也是作为处理对象进行操作的。对于计算机图形学中的裁剪算法来说，关于椭圆形窗口的裁剪算法是非常重要的。设标准椭圆的方程为: x2/a2+y2/b2=1 其中，标准椭圆的中心点为坐标轴的原点o，假设a(xa，ya)、b(xb，yb)(xa?xb)为被裁剪线段的两个端点，则裁剪可按如下步骤进行: 2.1 特殊情况的处理 当xa=xb时，即坐标轴的纵轴与被裁减的线段平行，这时分为两种情况，线段完全位于椭圆外部，即xa>a;否则，则需求取椭圆和线段的交点，其横坐标设为xa。 当ya=yb时，即坐标轴的横轴与被裁剪线段平行，这时也有两种情况，线段完全位于椭圆外部;即ya>b;否则，求 需要求椭圆与线段的交点，其纵坐标均为ya。 2.2 去除所有位于椭圆外切矩形外的线段。本步采用外切矩形包围盒的方法，外切矩形由四条直线组成，x=-a、x=a、y =-b、y=b。当min(xa，xb)?a或max(xa，xb)?-a或min(ya，yb}?b或max{ya，yb)?-b时，线段ab位于外切矩形的同侧，然后转步骤3。 2.3 线段端点与椭圆窗口的位置关系 椭圆有一条基本性质，即圆周上任意一点到两个定点的距离和等于特定常数。又由椭圆方程可得，a为椭圆的长半轴长度，因此可以根据线段的两端点到椭圆两焦点的距离之和是否小于2a的方法，来确定线段的端点是否位于椭圆内。因为椭圆上任意一点到两焦点的距离之和等于2a，在椭圆外部的点，到两焦点的距离之和大于2a，而在椭圆内部的点，到两焦点的距离之和大于2a。 最简单的直接可以显示的情况就是，线段两端点均位于椭圆内部，进而不需要求交点，因为该线段移动位于椭圆内。另一种情况就是线段与椭圆有一个交点，即线段的一个端点在椭圆内，一个在椭圆外，此时要通过联立线段与椭圆的方程求出交点，进而得到交点和位于椭圆内的端点之间的线段，即为所求。最复杂的情况就是线段的两个端点均位于椭圆外，这个时候，又有两种情况产生: ?线段完全位于椭圆窗口外，二者无交点，则可判定裁 剪结束。 ?当椭圆与线段有两个交点时，要进行如下区分，首先过原点o向线段ab做垂线交线段ab于点p(xp，yp)，设l为椭圆两个焦点与p的距离和。此时点p分为如下情况:当xa2a，b>2a，点p位于椭圆外部，可以根据平行于线段ab且与椭圆相切的线段cd来判断。假设设op与cd的交点为r，上一步切点为q，由于cd平行于ab，因此op垂直于cd，垂足设为r，lr为or的距离。如果lp>lr，则椭圆在线段cd的一侧，线段ab在线段cd的另一侧，这个时候，椭圆与ab无交点，因此不必显示。若lp a) break;//被裁剪线段完全位于椭圆窗口外的情况 else x1=x2=xa; else if(ya == yb) { if(ya > b) break;//被裁剪线段完全位于椭圆窗口外的情况 else y1=y2 =ya; } else if(min{xa，xb}?a或max{xa，xb}?-a 或min(ya，yb)?b或max{ya，yb}?-b) break;//被裁剪线段完全位于椭圆窗口外的情况 else if( da 2a或da>2a&&db lr ) break;//被裁剪线段完全位于椭圆外部的情况 else 求出(x1，y1)、(x2，y2); } } else break;//线段与椭圆无交点，完全位于椭圆外部的情况 } 椭圆是计算机图形学中的基本图形元素之一，近年来，在椭圆的研究上也取得了很大的进步，很多椭圆生成方面的有效算法应运而生。由于椭圆窗口裁剪情况在工程 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 当中应用非常广泛，故上文中的椭圆窗口裁剪算法在实际中是非常有效的。 参考文献: [1]韩明峰，李传林.基于一般多边形窗口的线裁剪算法.计算机工程与科学，1999. [2]吴章文，勾成俊，杨代伦，罗正明.有共线边的多边形窗口的线裁剪算法.计算机辅助设计与图形学报，2004. [3]刘永奎，刘桂芳.一般多边形窗口的线裁剪.计算机 辅助设计与图形学学报，1993. [4]陆国栋，邢世海.基于顶点编码的多边形窗口线裁剪算法.计算机学报，2002 [5]姚涵珍，宋鹏，张国安.圆形窗口线裁剪算法的研究与实践.计算机辅助设计与图形学学报，1992. [6]刘勇奎.圆形及椭圆形裁剪窗口.计算机工程与设计，1994. [7]沈庆云，周来水，周儒荣.一种圆形窗口裁剪的新方法.计算机辅助设计与图形学学报，1997.