第 1 章 基本图形的生成 计算机图形学已成为计算机技术中发展最快的领域，计算机图形软件也相应得到快速发展。计算机绘图显示有屏幕显示、打印机打印图样和绘图机输出图样等方式，其中用屏幕显示图样是计算机绘图的重要内容。
计算机上常见的显示器为光栅图形显示器，光栅图形显示器可以看作像素的矩阵。像素是组成图形的基本元素，一般称为“点”。通过点亮一些像素，灭掉另一些像素，即在屏幕上产生图形。在光栅显示器上显示任何一种图形必须在显示器的相 应像素点上画上所需颜色，即具有一种或多种颜色的像素集合构成图形。确定最佳 接近图形的像素集合，并用指定属性写像素的过程称为图形的扫描转换或光栅化。 对于一维图形，在不考虑线宽时，用一个像素宽的直、曲线来显示图形。二维图形 的光栅化必须确定区域对应的像素集，并用指定的属性或图案进行显示，即区域 填充。
复杂的图形系统，都是由一些最基本的图形元素组成的。利用计算机编制图形软件时，编制基本图形元素是相当重要的，也是必需的。点是基本图形，本章主要讲述如何在指定的输出设备（如光栅图形显示器）上利用点构造其他基本二维几何图形（如点、直线、圆、椭圆、多边形域及字符串等）的算法与原理，并利用Visual C++编程实现这些算法。
1.1 直 线
数学上，理想的直线是由无数个点构成的集合，没有宽度。计算机绘制直线是在显示器所给定的有限个像素组成的矩阵中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，实现显示器绘制直线，即通常所说的直线的扫描转换，或称直线光栅化。
由于一图形中可能包含成千上万条直线，所以要求绘制直线的算法应尽可能地快。本节介绍一个像素宽直线的常用算法：数值微分法（DDA）、中点画线法、Bresenham 算法。
计算机图形学原理及算法教程 (Visual C++版) 2
1.1.1 DDA（数值微分）算法
DDA算法原理：如图1-1所示，已知过端点p0(x0, y0), p1(x1, y1)的直线段p0p1；直
y?y0线斜率为k?1，从x的左端点x0开始，向x右Line: P0(0，0)?P1(5，2) x1?x0端点步进画线，步长=1（个像素），计算相应的y坐标y?kx?B；取像素点 [x, round（y）] 作为当前点的
坐标。计算yi?1?kxi?1?B?kx1?B?k?x?y1?k?x，
当x?1,yi?1?yi?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，下一个像素点有两种选择，点P1或P2。M为P1与P2中点，Q为理想直线与X=Xp+1垂线的交点。当M在Q的下方时，则P2应为下一个像素点；当M在Q的上方时，应取P1为下一点。
中点画线法的实现：令直线段为L[ p0(x0,y0), p1(x1, y1)]，其方程式F(x, y)=ax+by+c=0。 其中，a=y0–y1, b=x1–x0, c=x0y1–x1y0；点与L的关系如下。 在直线上，F(x, y)=0；
P2 在直线上方，F(x, y)>0；
在直线下方，F(x, y)<0。 Q M 把M代入F（x, y），判断F的符号，可知Q点在中
点M的上方还是下方。为此构造判别式d=F(M)=F(xp+1, P=(x, y) P1 pp
yp+0.5)=a(xp+1)+b(yp+0.5)+c。
图1-2 中点画线法每步迭代涉
当d < 0，L(Q点)在M上方，取P2为下一个像素。
及的像素和中点示意图
当d > 0，L(Q点)在M下方，取P1为下一个像素。 当d=0，选P1或P2均可，取P1为下一个像素。
其中d是xp, yp的线性函数。
1.1.3 Bresenham算法
Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。由误差项符号决定下一个像素取右边点还是右上方点。
第1章 基本图形的生成
3
设直线从起点(x1, y1)到终点(x2, y2)。直线可表示为方程y = mx+b，其中b=y1–mx1， m = (y2–y1)/(x2–x1)=dy/dx；此处的讨论直线方向限于第一象限，如图1-3所示，当直线光栅化时，x每次都增加1个单元，设x像素为(xi，yi)。下 一个像素的列坐标为xi+1，行坐标为yi或者递增1为yi+1，由y与yi及yi+1的距离d1及d2的大小而定。计算公式为 y = m(xi + 1) + b （1.1） d1 = y – yi （1.2） d2=yi+1–y （1.3） 如果d1–d2>0，则yi+1=yi+1，否则yi+1=yi。
式（1.1）、（1.2）、（1.3）代入d1–d2，再用dx乘等式两边，并以Pi=(d1–d2)，dx代入上述等式，得
Pi = 2xidy–2yidx+2dy+(2b–1)dx
x1 yi+1 d2 y d1 y1 xi+1
图1-3 第一象限直线光栅化
Bresenham算法
（1.4）
d1–d2是用以判断符号的误差。由于在第一象限，dx总大于0，所以Pi仍旧可以用
做判断符号的误差。Pi+1为
Pi+1 = Pi+2dy–2(yi+1–yi)dx
求误差的初值P1，可将x1、y1和b代入式（1.4）中的xi、yi，而得到
P1 = 2dy–dx
综述上面的推导，第一象限内的直线Bresenham算法思想如下： （1）画点（x1, y1），dx=x2–x1，dy=y2–y1，计算误差初值P1=2dy–dx，i=1。 （2）求直线的下一点位置xi+1 = xi + 1，如果Pi>0，则yi+1=yi+1，否则yi+1=yi。 （3）画点(xi+1, yi+1)。
（4）求下一个误差Pi+1，如果Pi>0，则Pi+1=Pi+2dy–2dx，否则Pi+1=Pi+2dy。 （5）i=i+1；如果i （1.5） 1.1.4 程序设计 1．程序设计功能说明 为编程实现上述算法，本程序利用最基本的绘制元素（如点、直线等），绘制图形。如图1-4所示，为程序运行主界面，通过选择菜单及下拉菜单的各功能项分别完成各种对应算法的图形绘制。 图1-4 基本图形生成的程序运行界面 计算机图形学原理及算法教程 (Visual C++版) 4 2．创建工程名称为“基本图形的生成”单文档应用程序框架 （1）启动VC，选择“文件”|“新建”菜单命令，并在弹出的新建对话框中单击“工程”标签。 （2）选择MFC AppWizard(exe)，在“工程名称”编辑框中输入 “基本图形的生成”作为工程名称，单击“确定”按钮，出现Step 1对话框。 （3）选择“单个文档”选项，单击“下一个”按钮，出现Step 2对话框。 （4）接受默认选项，单击“下一个”按钮，在出现的Step 3～Step 5对话框中，接受默认选项，单击“下一个”按钮。 （5）在Step 6对话框中单击“完成”按钮，即完成“基本图形的生成”应用程序的所有选项，随后出现工程信息对话框（记录以上步骤各选项选择情况），如图1-5所示，单击“确定”按钮，完成应用程序框架的创建。 图1-5 信息程序基本 3．编辑菜单资源 设计如图1-4所示的菜单项。在工作区的ResourceView标签中，单击Menu项左边“+”，然后双击其子项IDR_MAINFRAME，并根据表1-1中的定义编辑菜单资源。此时VC已自动建好程序框架，如图1-5所示。 表1-1 菜单资源表 菜单标题 直线 菜单项标题 DDA算法生成直线 Bresenham算法生成直线 中点算法生成直线 标示符ID ID_DDALINE ID_BRESENHAMLINE ID_MIDPOINTLINE 第1章 基本图形的生成 5 4．添加消息处理函数 利用ClassWizard（建立类向导）为应用程序添加与菜单项相关的消息处理函数，ClassName栏中选择CMyView，根据表1-2建立如下的消息映射函数，ClassWizard会自动完成有关的函数声明。 表1-2 菜单项的消息处理函数 菜单项ID ID_DDALINE ID_MIDPOINTLINE ID_BRESENHAMLINE 消 息 CONMMAN CONMMAN CONMMAN 消息处理函数 OnDdaline OnMidpointline OnBresenhamline 5．程序结构代码，在CMyView.cpp文件中相应位置添加如下代码： // DDA算法生成直线 void CMyView:: OnDdaline() { CDC* pDC=GetDC();//获得设备指针 int xa=100,ya=300,xb=300,yb=200,c=RGB(255,0,0);//定义直线的两端点，直线颜色 int x,y; float dx, dy, k; dx=(float)(xb-xa), dy=(float)(yb-ya); k=dy/dx, y=ya; if(abs(k)<1) { for (x=xa;x<=xb;x++) {pDC->SetPixel (x,int(y+0.5),c); y=y+k;} } if(abs(k)>=1) { for (y=ya;y<=yb;y++) {pDC->SetPixel (int(x+0.5),y,c); x=x+1/k;} } ReleaseDC(pDC); } 说明： （1）以上代码理论上通过定义直线的两端点，可得到任意端点之间的一直线，但由于一般屏幕坐标采用右手系坐标，屏幕上只有正的x, y值，屏幕坐标与窗口坐标之间转换知识请参考第3章。 （2）注意上述程序考虑到当k?1的情形x每增加1，y最多增加1；当k>1时，y每