计算机图形学若干基本算法的拓展与改进分析

《计算机图形学若干基本算法的拓展与改进分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浙江大学硕士学位论文第一章绪论计算机美术的发展已经进入了应用和普及阶段。以微机和工作站为平台的个人计算机图形系统逐渐走向成熟，大批商业性美术(设计)软件面市：以苹果公司的MAC机和图形化系统软件为代表的桌面创意系统披广泛接受，CAD成为美术设计领域的重要组成部分。计算机图形学对计算机动画技术的研究和发展起着十分重要的推动作用。计算机动画的一个重要应用就是制作电影特技。可以说电影特技的发展和计算机动画的发展是相互促进的。除了用来制作影视作品外，在科学研究、视觉模拟、电子游戏、工业设计、教学训练、写真仿真、过程控制、平面绘画、建筑设计等许多方面都有重要应用，如军事战术

2、模拟。’1．1．2计算机图形学算法的发展随着计算机系统、图形输入、图形输出设备的发展，计算机图形软件有了很大的发展。在这基础上，计算机图形学所涉及的算法通过了几十年热烈的讨论和探索，也越来越丰富和完善。计算机图形学涉及的算法非常丰富，大致可分为以下几类：(1)基本图形元素的生成算法，如生成直线、圆弧、二次曲线、区域填色、反走样等。(2)基本图形元素的几何变换、投影变换、裁剪等。(3)图形元素(点、线、环、面、体)的求交与分类以及集合运算。(4)自由曲线和曲面的生成、插值、拼接、分解等。(5)隐藏面和隐藏线的消除以及具有光照颜色效果的真实图形显示。(6)不同字体的点

3、阵表示，矢量中、西文字符的生成及变换。(7)模糊景物的生成。(8)三维或高维数据场的可视化。(9)三维形体的实时显示和图形的并行处理。(10)虚拟现实环境的生成及其控制算法等。围绕这些算法，多年来发表了很多论文，有些算法越来越完善，甚至实现了固化。然而有些算法还不是十分理想，可以进行适当的改进来进一步提高其效率。1．2国内外研究情况综述本文所研究的计算机图形学若干基本算法包括裁剪算法和直线生成算法，关于这些算法的国内外现有的研究情况如下所述。塑坚盔堂堕主兰垒堕苎一———笙二!!童垒1．2．1裁剪算法本课题中所研究的裁剪算法包括矩形窗口线裁剪算法、一般多边形窗口线裁

4、剪算法、矩形窗口多边形裁剪算法以及球形窗口线裁剪算法。前三种是二维空间的裁剪，后者是三维空间的裁剪。1。矩形窗口线裁剪算法SproulRF和SutherlandIE口1在1968年第～次提出了基于编码技术的裁剪算法，即Cohen-Suthedand裁剪算法。此算法的大意是：延长矩形窗口的边，把未裁剪的图形区域分为九个区，然后进行编码，每个区具有一个四位代码，据此可以得到被裁剪线段两端点的编码。然后根据端点编码判断线段是否可见或不可见。如果线段完全可见，直接取之；如果线段完全不可见，直接弃之；如果上述两种情况均不成立，则按第三种情况处理。求出线段与窗口某边的交点，在

5、交点处把线段一分为二，其中必有一段完全在窗口外，可以弃之。再对另一段重复进行上述处理。NewmanWM和SprouURF[31在1979年提出了无需乘除，易于硬件实现的中点分割算法，被广泛应用于几何裁剪器。此算法经过对线段端点的预编码可简单取舍所有的窗内线段和一部分的窗外线段；对于剩下的窗外线段和所有与窗口相交的线段。则需要通过中点分割来判断该线段是否与窗口相交，并求出交点。Cyrus和Beck[41于1978年提出了参数化线裁剪算法，后来在这基础上，梁友栋和Barsky[习于1984年提出了更快的参数化线段裁剪算法。此算法在求交之前进行测试。只有在霰要时才计算交

6、点，减少了计算蠡．提高了算法的速度，此算法在现有的算法中速度最快。2．一般多边形窗口线裁剪算法Cyrus和Beckt4J在1978年提出了一种凸多边形窗口的线裁剪算法。它先判断直线段的方向矢量与窗口边法失量的点积，若大于零，交点分在上组：若小于零。交点分在下组。然质，分鄹取上组中的最小交点和下组中的最大交点，即为线段可见部分的端点。但对于凹多边形窗口，这样的分组是没有意义的，所以Cyrus--Beck算法只适用于凸多边形窗口的线裁剪，丽不是一般意义上的多边形窗口线裁剪算法。沈阳工业大学刘勇奎等ⅢJp5j击是出了一个基于一般多边形窗口的线裁剪算法。该算法在被裁剪直线

7、的延长线上取一固定点，然后求多边形密门妁每一项点到该固定点引线的斜率。这样对于每个窗口边只需判断被裁剪直线的斜率是否在该边两顶点到固定点引线斜率之间，就可判定直线与边是否相交。复旦大学蔡志杰8‘11998年也提出一般多边形的裁剪算法，用参数求交法求出浙江大学硕士学位论文第一章绪论线段及其延长线与多边形各边的交点，然后判断交点是否是真实交点，并根据参数值排序，去掉重复的交点，最后判断以相邻交点为端点的线段的中点是否可见，若是，则此线段可见，若不是，则不可见。3。矩形窗口多边形裁剪算法Sutherland和Hodgman[91于1974年提出了逐次多边形裁剪算法，此算

8、法仅适合凸