计算机图形学教材第二章光栅图形学(希赛教育基础学院).docx

★ 第二章 光栅图形学 【课前思考】 计算机是如何在屏幕上画一条直线或一个圆的？ 在计算机屏幕上画直线时，经常出现锯齿，这是为什么？如何解决？ 【学习目标】 了解光栅图形学的特点； 掌握直线、圆弧和椭圆的光栅显示方法； 学习反走样的几种算法，并能够编程实现。 【学习指南】 在数控插补技术中也有关于直线、圆弧和椭圆的NC 插补的更多算法，可以参考有关的数控编程的书或资料； 某些图象处理方法对学习和掌握反走样技术会有帮助。 【难重点】 Bresenham 画直线和画圆算法； 直线的反走样。 【知识点】 Bresenham 画直线算法； Bresenham 画圆算法； 多边形区域填充； 直线反走样； 离散区域反走样算法。 ◇第一节 画线算法 光栅图形显示器可以看成是由许多可发光的离散点（即像素）组成的矩阵，它需要专门的算法来生成直线、圆弧和曲线等等图形。本章将介绍生成光栅图形的相关算法。这些算法对于开发图形设备驱动程 序是必需的。不过，在 Windows、Unix 或 Linux 操作系统上开发计算机图形时，现在都有支持 OpenGL 的图形硬件和软件开发工具可供使用，而 OpenGL 程序库本身都提供了光栅图形显示的驱动程序，这为图形软件开发人员提供了便利。 画线算法 在数学上，理想的点和直线都是没有宽度的。但是，由于每个像素对应于图形设备上的一个矩形区域， 当我们在光栅图形设备上显示一个点时，实际上它是有用一个发光的矩形区域来表示的；当在光栅图形设备上显示一条直线时，我们只能在显示器所给定的有限个像素组成的矩阵中，按扫描线顺序，依次确定最佳逼近于该直线的一组像素，并且对这些像素进行写操作。这个过程称为直线的扫描转换。 对于水平线、垂直线和 45o斜线，选择哪些像素是显而易见的，但是对于其它的直线，确定用哪些像素来表示它就不那麽简单了。本节我们介绍用于直线扫描转换的常用算法：Bresenham 画线算法。 在介绍画线算法之前，我们先讨论画直线的基本要求：直线必须有精确的起点和终点，外观要直，线宽应当均匀一致、且与直线的长度和方向无关，最后，算法速度要快。 Bresenham 算法是计算机图形学领域使用最广泛的直线扫描转换算法。该方法最初是为数字绘图仪设计的，后来被广泛地应用于光栅图形显示和数控（NC）加工。该算法构思巧妙，使得每次只需检测误差项 的符号就能决定直线上的下一个像素的位置。算法原理如下：过各个像素的中心构造一组虚拟网格线，首先按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后，采用增量计算，使得对于每一列， 只要检查一个误差项的符号，就可以确定该列像素中与此交点最近的像素。 先考虑斜率 k=dy/dx≤1 的直线。如图 2.1 所示，设直线 方程为 ，其中， k = dy/dx。 假设当前像素的 x 坐标已经确定为 x ，其 y 坐标为 y ，由于坐标（x ，y ）（i=0,1,…）只能取 i i i i 整数，那么下一个像素的 x 坐标 保持不变，即 y ＝y ；或者 i＋1 i ，而 y 的坐标有两种可能： i＋1 y 坐标递增 1，即 y 令  i＋1 ＝y ＋1。 i ，y 坐标是否增加 1 取决于如图所示误差项 d 的值。因为直线的起始点 i 在像素中心，所以初始误差 d ＝0。x 每增加 1，y 的值相应递增直线的斜率值 k，即 。一 0 旦 d ≥1，就把它减去 1，这样保证 d 在 0～1 之间。当 d ≥0.5 时，直线 与 x＝x ＋1 的垂线的交点 i+1 i+1 i+1 i 最接近于当前像素（x ，y ）的右上方像素（x ＋1，y ＋1）；而当 d 0.5 时，其交点更接近于（x ，y ） i i i i i+1 i i 右边的像素（x ＋1，y ）。为方便计算，令 e =－0.5，e ＝d －0.5，增量为 k。当 e ≥0 时，取当前像 i i 0 i+1 i+1 i+1 素（x ，y ）的右上方像素（x ＋1， y ＋1）；而当 e 0 时，更接近于右方像素（x ＋1，y ）。 i i i i i+1 i i 直线的基本要求 因此，算法 2.1 可以改进如下： 图 2.1 Bresenham 画线算法 上述算法在计算直线斜率和误差时要用到浮点运算和除法，可以改用整数运算并避免使用除法，以便提高运算速度。由于上述算法中只用到误差项的符号，因此可作一个简单变换： 。 考虑到 xy 平面上各种八分和四分区域的对称性，Bresenham 画线算法的原理对任意斜率的直线都有其通用性。例如，对于斜率 k1 的直线，只要在上述算法中交换 x 和 y 之间的规则即可。 算法 2.1 画斜率 0≤k≤1 的直线的改进的Bresenham 画线算法： void B