基本图形反走样绘制算法的改进研究

摘要

直线、圆和椭圆是最基本的光栅图形，其生成算法的速度和质量直接影响到整个图形系统的绘制效率。尽管Windows的 GDI(图形设备接口)已经提供了相关的画图函数，但直接使用这些函数仍然无法满足真实感图形绘制的要求，最典型的例子就是对基本图形进行反走样方面的处理。光栅图形显示器用一系列离散的像素点来表示图形，这将导致所显示的图形出现明显的锯齿状，影响显示效果。这种由离散量表示连续量而引起的失真称为走样。用于减轻走样现象的技术称为反走样。当前，计算机图形学的研究热点是生成具有高度真实感的图形，因此研究图形的反走样算法具有重要意义。 本文主要研究了在实数坐标中，用32位定点小数表示中点初始值和增量来计算画点位置和颜色分配比例，从而实现直线、圆和椭圆的反走样，然后通过矩形裁剪算法来加快基本图形反走样绘制的速度。主要研究工作如下： 1.为了实现简单、快速的直线的反走样绘制，本文提出了一种基于 DDA和Wu 算法的改进算法。该算法首先根据计算机浮点数的内部格式，将中点误差项的初始值和增量表示为32位定点小数，实现增量整数运算；然后提取更新后的中点误差项整数部分用于确定画像素点的坐标位置，小数部分用于确定像素点的颜色混合比例；最后利用整数乘法快速进行像素点颜色与背景色相混合，从而显著地提高了反走样的绘制效率。结果表明，该算法具有很好的执行速度和光滑度。 2.在研究和总结现有的绘制圆与椭圆算法的基础上，设计并实现了一种基于中点算法的改进算法。该算法首先利用泰勒公式展开圆或椭圆的因变量表达式；然后用三级差分的方法实现增量运算，进而转换为只用整数的加减乘和位运算；最后利用改进的直线算法思想确定圆或椭圆的画点位置与颜色混合，从而实现了圆或椭圆的反走样。结果表明，该算法在速度和光滑度方面有了很大改善。 3.在实际绘制基本图形之前，不可避免地要进行窗口裁剪，本文提出了一种矩形裁剪方法。该算法首先通过坐标系变换使一个点坐标变成实数坐标；然后通过矩形裁剪窗口的四条边界线来判断直线段完全在边界线外的情形，在四条边界线不能完全判定时，再用矩形窗口的四个角点进行判断；最后利用中间结果计算裁剪，进一步提高了算法的运行速度。结果表明，该算法减少了图形绘制的重复计算，达到快速画线的目的。

目录

声明

插图索引

附表索引

第1章 绪 论

1.1 研究背景及意义

1.2 国内外研究现状

1.3 存在的问题及分析

1.4 论文的主要研究内容与创新点

1.5 论文的组织结构与安排

第2章 图元反走样绘制与裁剪的相关理论知识

2.1 经典的直线绘制及反走样算法

2.2 经典的圆与椭圆绘制及反走样算法

2.3 经典的二维裁剪算法

2.4 本章小结

第3章 直线反走样绘制算法的改进

3.1 引言

3.2 算法原理

3.3 直线段的中点处理

3.4 直线段的端点处理

3.5 颜色混合进行反走样处理

3.6 算法的具体实现过程

3.7 其他斜率的处理

3.8 运行结果比较与算法复杂度分析

3.9 本章小结

第4章 圆与椭圆反走样绘制算法的改进

4.1 引言

4.2 圆反走样绘制算法的改进

4.3 椭圆反走样绘制算法的改进

4.4 本章总结

第5章 矩形裁剪算法

5.1 引言

5.2 算法二维观察中画布坐标系与世界坐标系间的转换

5.3 矩形裁剪算法

5.4 本章总结

总结与展望

研究工作总结

展望

参考文献

致谢

附录 攻读硕士学位期间所发表的学术论文