2024年5月25日发(作者：朱同甫)

第 1 章

基本图形的生成

计算机图形学已成为计算机技术中发展最快的领域，计算机图形软件也相应得到快

速发展。计算机绘图显示有屏幕显示、打印机打印图样和绘图机输出图样等方式，其中

用屏幕显示图样是计算机绘图的重要内容。

计算机上常见的显示器为光栅图形显示器，光栅图形显示器可以看作像素的矩

阵。像素是组成图形的基本元素，一般称为“点”。通过点亮一些像素，灭掉另一些

像素，即在屏幕上产生图形。在光栅显示器上显示任何一种图形必须在显示器的相

应像素点上画上所需颜色，即具有一种或多种颜色的像素集合构成图形。确定最佳

接近图形的像素集合，并用指定属性写像素的过程称为图形的扫描转换或光栅化。

对于一维图形，在不考虑线宽时，用一个像素宽的直、曲线来显示图形。二维图形

的光栅化必须确定区域对应的像素集，并用指定的属性或图案进行显示，即区域

填充。

复杂的图形系统，都是由一些最基本的图形元素组成的。利用计算机编制图形软件

时，编制基本图形元素是相当重要的，也是必需的。点是基本图形，本章主要讲述如何

在指定的输出设备（如光栅图形显示器）上利用点构造其他基本二维几何图形（如点、

直线、圆、椭圆、多边形域及字符串等）的算法与原理，并利用Visual C++编程实现这

些算法。

1.1 直 线

数学上，理想的直线是由无数个点构成的集合，没有宽度。计算机绘制直线是在显

示器所给定的有限个像素组成的矩阵中，确定最佳逼近该直线的一组像素，并且按扫描

线顺序，对这些像素进行写操作，实现显示器绘制直线，即通常所说的直线的扫描转换，

或称直线光栅化。

由于一图形中可能包含成千上万条直线，所以要求绘制直线的算法应尽可能地快。

本节介绍一个像素宽直线的常用算法：数值微分法（DDA）、中点画线法、Bresenham

算法。

计算机图形学原理及算法教程 (Visual C++版)

2

1.1.1 DDA（数值微分）算法

DDA算法原理：如图1-1所示，已知过端点

p

0

(x

0

, y

0

), p

1

(x

1

, y

1

)

的直线段

p

0

p

1

；直

yy

0

线斜率为

k

1

，从

x

的左端点

x

0

开始，向

x

右

Line: P

0

(0，0)…P

1

(5，2)

x

1

x

0

端点步进画线，步长=1（个像素），计算相应的

y

坐标

] 作为当前点的

ykxB

；取像素点 [

x

, round（y）

坐标。计算

y

i1

kx

i1

Bkx

1

Bkxy

1

kx

，

当

x1,y

i1

y

i

k

，即当x每递增1，y递增k（即

直线斜率）。

注意：上述分析的算法仅适用于k1的情形。在

这种情况下，x每增加1, y最多增加1。当

k1

时，

图1-1 DDA方法扫描转换连接两点

必须把x，y地位互换，y每增加1，x相应增加1/k（请参阅后面的Visual C++程序）。

1.1.2 生成直线的中点画线法

中点画线法的基本原理如图1-2所示。在画直线段的过程中，当前像素点为P，下

一个像素点有两种选择，点P

1

或P

2

。M为P

1

与P

2

中点，Q为理想直线与X=X

p

+1垂线

的交点。当M在Q的下方时，则P

2

应为下一个像素点；当M在Q的上方时，应取P

1

为下一点。

中点画线法的实现：令直线段为L[ p

0

(x

0

,y

0

), p

1

(x

1,

y

1

)]，其方程式F(x, y)=ax+by+c=0。

其中，a=y

0

–y

1

, b=x

1

–x

0

, c=x

0

y

1

–x

1

y

0

；点与L的关系如下。

在直线上，F(x, y)=0；

在直线上方，F(x, y)>0；

在直线下方，F(x, y)<0。

P

2

M

P=(x

p

, y

p

)

Q

P

1

把M代入F（x, y），判断F的符号，可知Q点在中

点M的上方还是下方。为此构造判别式d=F(M)=F(x

p

+1,

图1-2 中点画线法每步迭代涉

及的像素和中点示意图

y

p

+0.5)=a(x

p

+1)+b(y

p

+0.5)+c。

当d < 0，L(Q点)在M上方，取P

2

为下一个像素。

当d > 0，L(Q点)在M下方，取P

1

为下一个像素。

当d=0，选P

1

或P

2

均可，取P

1

为下一个像素。

其中d是x

p

, y

p

的线性函数。

1.1.3 Bresenham算法

2024年5月25日发(作者：朱同甫)

第 1 章

基本图形的生成

计算机图形学已成为计算机技术中发展最快的领域，计算机图形软件也相应得到快

速发展。计算机绘图显示有屏幕显示、打印机打印图样和绘图机输出图样等方式，其中

用屏幕显示图样是计算机绘图的重要内容。

计算机上常见的显示器为光栅图形显示器，光栅图形显示器可以看作像素的矩

阵。像素是组成图形的基本元素，一般称为“点”。通过点亮一些像素，灭掉另一些

像素，即在屏幕上产生图形。在光栅显示器上显示任何一种图形必须在显示器的相

应像素点上画上所需颜色，即具有一种或多种颜色的像素集合构成图形。确定最佳

接近图形的像素集合，并用指定属性写像素的过程称为图形的扫描转换或光栅化。

对于一维图形，在不考虑线宽时，用一个像素宽的直、曲线来显示图形。二维图形

的光栅化必须确定区域对应的像素集，并用指定的属性或图案进行显示，即区域

填充。

复杂的图形系统，都是由一些最基本的图形元素组成的。利用计算机编制图形软件

时，编制基本图形元素是相当重要的，也是必需的。点是基本图形，本章主要讲述如何

在指定的输出设备（如光栅图形显示器）上利用点构造其他基本二维几何图形（如点、

直线、圆、椭圆、多边形域及字符串等）的算法与原理，并利用Visual C++编程实现这

些算法。

1.1 直 线

数学上，理想的直线是由无数个点构成的集合，没有宽度。计算机绘制直线是在显

示器所给定的有限个像素组成的矩阵中，确定最佳逼近该直线的一组像素，并且按扫描

线顺序，对这些像素进行写操作，实现显示器绘制直线，即通常所说的直线的扫描转换，

或称直线光栅化。

由于一图形中可能包含成千上万条直线，所以要求绘制直线的算法应尽可能地快。

本节介绍一个像素宽直线的常用算法：数值微分法（DDA）、中点画线法、Bresenham

算法。

计算机图形学原理及算法教程 (Visual C++版)

2

1.1.1 DDA（数值微分）算法

DDA算法原理：如图1-1所示，已知过端点

p

0

(x

0

, y

0

), p

1

(x

1

, y

1

)

的直线段

p

0

p

1

；直

yy

0

线斜率为

k

1

，从

x

的左端点

x

0

开始，向

x

右

Line: P

0

(0，0)…P

1

(5，2)

x

1

x

0

端点步进画线，步长=1（个像素），计算相应的

y

坐标

] 作为当前点的

ykxB

；取像素点 [

x

, round（y）

坐标。计算

y

i1

kx

i1

Bkx

1

Bkxy

1

kx

，

当

x1,y

i1

y

i

k

，即当x每递增1，y递增k（即

直线斜率）。

注意：上述分析的算法仅适用于k1的情形。在

这种情况下，x每增加1, y最多增加1。当

k1

时，

图1-1 DDA方法扫描转换连接两点

必须把x，y地位互换，y每增加1，x相应增加1/k（请参阅后面的Visual C++程序）。

1.1.2 生成直线的中点画线法

中点画线法的基本原理如图1-2所示。在画直线段的过程中，当前像素点为P，下

一个像素点有两种选择，点P

1

或P

2

。M为P

1

与P

2

中点，Q为理想直线与X=X

p

+1垂线

的交点。当M在Q的下方时，则P

2

应为下一个像素点；当M在Q的上方时，应取P

1

为下一点。

中点画线法的实现：令直线段为L[ p

0

(x

0

,y

0

), p

1

(x

1,

y

1

)]，其方程式F(x, y)=ax+by+c=0。

其中，a=y

0

–y

1

, b=x

1

–x

0

, c=x

0

y

1

–x

1

y

0

；点与L的关系如下。

在直线上，F(x, y)=0；

在直线上方，F(x, y)>0；

在直线下方，F(x, y)<0。

P

2

M

P=(x

p

, y

p

)

Q

P

1

把M代入F（x, y），判断F的符号，可知Q点在中

点M的上方还是下方。为此构造判别式d=F(M)=F(x

p

+1,

图1-2 中点画线法每步迭代涉

及的像素和中点示意图

y

p

+0.5)=a(x

p

+1)+b(y

p

+0.5)+c。

当d < 0，L(Q点)在M上方，取P

2

为下一个像素。

当d > 0，L(Q点)在M下方，取P

1

为下一个像素。

当d=0，选P

1

或P

2

均可，取P

1

为下一个像素。

其中d是x

p

, y

p

的线性函数。

1.1.3 Bresenham算法