《计算机图形学》中直线生成算法的教学心得

季洁

摘要：《计算机图形学》是计算机科学与技术专业一门重要的专业课，其中直线生成算法是教学重点之一。该文通过分析几种直线生成算法的特点，阐述了理论教学和实践教学的重点和难点，总结了教学的体会和心得，对《计算机图形学》直线生成算法的本科教学有一定借鉴作用。

关键词：计算机图形学；直线生成算法；DDA算法；Bresenham算法

中图分类号：G642 文献标识码：A 文章编号：1009-3044（2015）23-0072-02

Teaching Experience of the Straight Line Generation Algorithm in Computer Graphics

JI Jie

（College of Computer and Electronic Engineering， Hunan University of Commerce， Changsha 410205， China）

Abstract："Computer graphics" is an important course in the major of computer science and technology， and the straight line generation algorithm is one of the key points in teaching of this course. In this paper， we analyse the characteristics of several line generating algorithm， describe the key and difficult points of theory teaching and practice teaching，summarize the teaching experience.It has some reference for the teaching of the straight line generating algorithm in computer graphics.

Key words： Computer graphics； straight line generating algorithm；DDAalgorithm； Bresenham algorithm

计算机图形学是计算机科学中一门重要的分支研究方向，主要研究将二维或三维的图形通过数学算法转换为计算机输出设备中的光栅形式。《计算机图形学》这门课程是计算机科学与技术、软件工程等相关专业在本科高年级教学中一门重要的专业课，在教学计划中占有重要地位和作用。学习本课程旨在使学生掌握基本二维、三维图形生成和变换技术算法、真实感图形生成算法、计算机动画技术的基本方法和原理，并通过编写计算机程序加深对图形学基本理论知识的理解，提高理论指导实践的动手能力，为学生今后学习其他相关课程和进行相关方面的研究夯实基础。

1 直线生成算法的教学重要性分析

计算机图形学中的图形可分为二维图形和三维图形，在坐标系中，三维图形可以通过一系列的投影变换得到二维的平面图形，所以说，二维图形的生成是三维图形生成的基础。

各种无论多么复杂的二维图形，实际上都是通过直线段和曲线段组成的。在理论上，绝对光滑的曲线是绘制不出来的，曲线段经过微分之后可以转换成细微的短直线段。例如，一个较复杂的曲面，可能是由成千上万条很短的直线组成的。所以，可以说所有图形都是以直线段的生成为基础的，而直线段生成质量的好坏和速度的快慢也直接决定整个图形生成的质量和速度[1]，所以直线生成算法的学习显得尤为重要。因此，在《计算机图形学》的教学中，直线生成算法是教学重点之一，并且是学生们接触到的第一类图形生成算法。

2 几种经典直线生成算法分析和回顾

由于显示设备的栅格性质，图形显示器是由一个个排列有序的像素点构成的，一条直线就是由一些像素点组成的。无论分辨率的大小，像素点之间还是存在一定距离的，而直线在图形学中是不存在厚度的，所以一条直线不可能刚好经过所有的像素点（平行于x轴、y轴以及斜率为45度的直线除外）。直线生成算法是计算出与该直线靠近的像素点，并绘制出来的过程。在教学中，主要给学生们介绍以下几种直线生成算法：

1）中点生成算法：以第一象限为例，假设当前像素点P已经确定，那么下一个像素点只能是正右方的点P1或者是右上方的点P2，另M为P1和P2的中点，若直线与P1P2所在垂直线的交点在M的上方，则P2离直线比较近，应选为下一个像素点；否则应取P1位下一个像素点[2]。

2）逐点比较算法：逐点比较算法主要运用于绘图仪中，其主要思路为：在绘图的过程中，每绘制一个像素点，就与规定图形进行比较，然后决定下一个像素点的位置。同样以第一象限为例，如画的直线为OA，当前画笔的位置为M，以OM和OA之前的斜率之差来计算偏差δ，若δ<0，则表示笔在直线OA的下方，应该往+y方向走一步；若δ>0，则表示笔在直线OA的上方，应该往+x方向走一步[1]。

3）数值微分（DDA）算法：这是一种基于直线的微分方程来生成直线的方法。设（x1，y1）和（x2，y2）分别为直线的端点坐标，选定x2-x1和y2-y1中较大者作为步进方向，假设x2-x1比较大，则取x方向每次的增量为1个像素点，通过直线的微分方程，求出相应的y值，并四舍五入取整之后作为下一个像素点输出[1]。

4）Bresenham算法：这种方法最初是为数字绘图仪设计的，但同样也适用于光栅图形显示器。其基本思想是：过各行各列的像素中线虚拟的栅格化出一组网格线，直线与网格线的生成一系列交点，通过计算与该列中像素点的偏差距离e，并判断偏差的符号来找到最近的像素点。以通过原点（0，0），且斜率k∈（0，1）的直线为例，则偏差e≥1/2的直线，下一个像素点应该x加1，y+1；偏差e<1/2的直线，下一个像素点应该x加1，y不变[2]。

3 教学的开展和体会

1）教学思路和过程

笔者对于计算机图形学中直线生成算法的教学思路，总体分为四步走：首先，让学生了解直线生成算法的统一特点，即在图形输出设备所给定的有限个像素矩阵中，确定最佳逼近于该直线的一组像素，从直线的起点开始，通过判断寻找下一个最接近直线的像素点，一直到终点；第二步，让学生具体了解算法的基本思路及具体实现的数学推导过程，判别函数、误差项的生成过程；第三步，通过习题的演算和练习加深对算法的理解；最后，理论指导实践的过程，上机操作将算法形成代码，运行后得出结果。

2）教学重点和难点

在以上的教学过程中，第二步是教学的难点。因为这四种直线生成算法涉及大量的数学模型和算法实现，对于计算机专业的学生，数学基础相对薄弱，学生在理解算法的基本思路上掌握得还不错，但对于学习算法具体实现的数学推导过程就只能被动的听课，很难主动地去进行推导，尤其是为了判别函数或者误差项的计算简单，常常需要进行各种推导变换及除法消除等操作。

由于课时有限，以上的四种算法不可能面面俱到，因此在教学安排中，中点生成法和逐点比较法做简单阐述，DDA法和Bresenham法则作为重点讲述。DDA法虽然效率不高，但比较直观，方便通过实例让学生了解每一步分解过程，通过改进之后使得算法中只包含加法和取整，适合硬件实现。Bresenham法是计算机图形学领域使用最广泛的直线生成算法，且算法很简单，速度也相当快。认真掌握这两种算法能帮助学生后续学习圆和曲线生成的算法奠定基础。

3）实验课程的内容安排

计算机图形学中涉及理论知识、数学模型和构造算法，一般比较抽象和难懂。为了加深对书本理论知识的理解，加强本科学生动手能力的培养，从而突出实践性和实用性，计算机图形学重点的算法都安排了上机实验。实验平台环境为Visual C++，因为Visual C++是集编辑、编译、运行、调试于一体功能强大的集成编程环境。且MFC将图形设备接口（GDI）的设备描述表（DC）封装在C++类中，程序员可以通过调用专门的GDI函数来进行图形程序设计。

直线生成算法的实验任务安排了实现DDA画线程序和Bresenham画线程序。DDA算法程序逻辑简单，学生理解较为轻松，原本DDA算法中含有浮点运算和取整运算，不利于硬件实现，但改进后的DDA算法只含有加法运算和取整运算，虽然效率不高，但硬件实现起来变得方便。通过分支语句结构可以实现判断x和y方向增量较大者作为步进方向，通过语句int（x+0.5）或者int（y+0.5）可以实现四舍五入取整的操作，通过循环语句可以实现从起点到终点像素点的绘制。Bresenham算法程序相对复杂，关键点在于区分直线位于不同的象限，判断条件有所不同，具体用程序实现的时候，会需要进行直线区域的变换。大部分的学生能够在课程规定的时间内完成DDA算法和Bresenham算法的程序实现，基础较好的同学还能完成中点生成算法及逐点比较法的程序实现。

之后的教学中圆弧、椭圆、曲线的生成都牵涉到用短的直线段来逼近曲线，实践证明，学生较好掌握了直线生成算法后，对后续的学习奠定了良好的基础。

4 结束语

本文主要总结了在计算机科学与技术、软件工程等相关专业《计算机图形学》课程本科教学中直线生成算法的教学体会。基于直线生成算法在本课程中的重要性，通过阐述和对比四种直线生成算法的异同，设计出了适合计算机科学与技术、软件工程等相关专业《计算机图形学》课程本科生教学的思路，并给出了相关实验课程开展的良好建议。对于《计算机图形学》课程本科教学有一定的借鉴作用。

参考文献：

[1] 王汝传，黄海平，林巧民，等.计算机图形学教程[M]. 3版. 北京：人民邮电出版社，2014.

[2] 银红霞，杜四春，蔡立军.计算机图形学[M].北京：中国水利水电出版社，2013.