欢迎来到天天文库
浏览记录
ID:58300874
大小:100.99 KB
页数:1页
时间:2020-05-09
《Computer Graphics的基本算法实现分析-论文.pdf》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、计算机科学ComputerScienceComputerGraphics的基本算法实现分析许敏,邵向阳(漯河医学高等专科学校,河南漯河462000)摘要:ComputerGraphics又称计算机图形学,本文对计算机图形学中多边形剪裁和逐点生成的基础算法进行比较和研究,对于提高计算机图形系统的性能具有很大的帮助,具有很强的理论和现实意义。关键词:计算机图形学;基本算法;分析中图分类号:TP391.41文献标识码:A文章编号:1674—7712(2014)16—0160—01计算机图形学(ComputerGraphics)是伴随着电子计随着
2、广泛使用光栅扫描显示器作为图形显示器,随之出算机及其外围设备而产生和发展起来的。目前几乎所有的计现了一类图形算法,即象素级的图形绘制算法(或称点式生算机的实际应用都不同程度地使用了图形技术。所以计算机成算法)。这类算法生成的曲线是很细致的并且误差小(坐图形技术同计算机网络,人工智能及图像处理等技术一样是标轴方向最大偏差不大于半个象素中一位)。可以说这类算目前计算机领域的研究热点之一。法充分利用了光栅显示器的特点。一、计算机图形学基木算法研究曲线的像素级生成算法大体可以分为两类。一类是根据(一)多边形剪裁算法曲线的隐式方程,通过判断曲线的可
3、能的走向,找出在各个线裁剪是计算机图形学中的一个基本操作。对于凸多走向中的下一个像素中距离曲线最近的像素。由于,曲线的边形窗口的裁剪,经过国内外学者的多年研究己经形成了每一步都是一个像素距离,所以误差在坐标轴方向不会超过许多经典有效的算法。但对于凹多边形窗口的线裁剪,还一个像素。此类算法的优点是每步走一个像素距离,速度快。有待进一步研究。对于凸多边形窗口的线裁剪,国内外提其缺点是适用的范围小,且下一个像素的位置判断比较麻烦。出了多种多样的线裁剪算法,其中五个具代表性意义的另一类方法是根据曲线的平滑度,利用参数方程求导,求出算法为:Cohe
4、n—Sutherland的分区编码算法、基于硬使每一步前进距离都小于等于一个像素的迭代步长。这类算件实现的中点分割算法、通过法向点积进行判别的Cyrus法的优点是适用范围广。缺点是由于步长的选取是针对整个—Beck裁剪算法、梁友栋一Barskv线裁剪算法、以及曲线的,因此在曲线的某此阶段,需要走许多步以后才能到Nieholl—LPe算法、为叙述方便,下面我们分别简称为C、达一个像素,造成许多多余的计算。它们共同的特点是让每中点、CB、梁B,NLN算法。一步的像素选取都和前一个像素的距离小于等于一个像素。算法在计算机图形学上曾经占据重要的地
5、位,它对每条无论那种算法都必须使前后像素的坐标满足一个迭代关系,线段分三中情况处理。(1)窗内;(2)窗外;(3)不满足条尽量减少乘法和除法运算。件(1)(2)的情况。它需要确定线段端点的编码以辨别线段与这类算法在2O世纪6O年代和7O年代出现了著名窗口的位置关系,其判断的运算量明泉多于其它算法。的Bresenham直线算法,Pitteway椭圆和双曲线算法和中点算法把线段与窗口的关系一样分为三种情况。对前Bresenham圆生成算法。其实至此直线和圆的像素级生成算两种情况的处理与CS相同,对第三种情况则简单的把线段法己相当成热,但仍有人
6、在继续从事这方面的研究。其着等分为两段。它适用于对乘、除没有硬件支持的计算机,其眼点主要集中在研制每一步生成多个点的算法上,2O世纪算法便于硬化,用软件实现则效率不高。cB算法适用于对任80年代以后,人们的主要精力集中在其它曲线(高阶或自意凸多边形窗口的裁剪。它通过判断直线段的方向矢量与窗由曲线等)的生成算法的研究上,如国内学者蔡耀志、金口边法矢量的点积是否大于零而将所有交点分为上、下两组。通光等提出的正负法、T—N法等,而在国外则有许多学者在然后,分别取上组中的最小交点和下组中的最大交点,即为进行这方面的研究,目前出现的自由曲线生成算法
7、中大部线段可见部分的端点。由于所采用的方法过于一般化,对一分属于生成或逼近算法,或者有此算法可以说是点式生成根不平行于坐标轴但完全落在窗口内部的线段的裁剪,cB算算法。但其两点的间距较大,并非逐点选择,所以生成的法需做12次加法、16次减法、2O次乘法和除法。曲线不够细致。在象素级算法中主要是关于二次和三次自梁B算法速度最快,但当线段在某窗口边界线的不可见由曲线的生成算法。如Patt提出的二次样条曲线的象素级一侧时,或完全落在窗口内部可见时,梁B算法仍要做算术生成算法能够较精确地选择距离曲线最近的象素点,但该运算。对四种算法比较,CS与中
8、点法在区码测试阶段能以位算法所生成的曲线的走向只能在一个象限内变化(9O度范运算方式高效率地进行,因而当大多数线段需要进行裁剪时,围),不能生成曲率大的曲线。效率较好、,CB算法在多数线段需要
此文档下载收益归作者所有