第 4章 基本图形（元）生成技术
提纲：
1,直线生成技术；
2,圆与椭圆生成技术
? 我们知道, 光栅图形显示器是一个像素矩阵, 如
分辨率为 640X480,每个像素可以用一种或多种
颜色显示, 分别称为单色显示器或彩色显示器 。
在光栅显示器上显示的任何一种图形, 实际上都
是具有一种或多种颜色的像素的集合 。 确定一个
像素集合及其颜色, 用于显示一个图形的过程,
称为图形的扫描转换或光栅化, 也叫图形的生成 。
实际上, 图形生成是根据图形的几何信息和属性
信息, 结合图形生成算法, 计算出要显示的中间
像素, 而不像图像生成是保存了图像的每一像素
点的信息 。 所以, 基本图形的生成, 首先要根据
基本图形的特征找出它的几何信息, 然后根据一
定的生成算法实时地在显示器上显示出完整的图
形 。
? 图形扫描转换一般分为两个步骤：先确
定有关像素, 再用图形的颜色或其它属
性对象素进行某种写操作 。 后者通常是
通过调用设备驱动程序来实现的 。 所以
扫描转换的主要任务就是确定最佳逼近
于图形的像素集的生成算法 。
.
? 本章主要讨论基本图形的扫描转换问题,
包括：
? （ 1） 一维直线, 圆, 椭圆的生成；
? （ 2） 二维图形 （ 多边形 ） 的填充；
? （ 3） 字符的表示和输入输出；
? （ 4） 图形的裁剪和反走样技术；
? 在一个图形系统中，基本图形（也称为
图元、图素等）的生成技术是最基本的，
任何复杂的图形都是由基本图形组成的，
基本图形生成的质量直接影响该图形系
统绘图的质量。所以，需要设计出精确
的基本图形生成算法，以确保图形系统
绘图的精确性。
4,1 直线图形的生成技术
? 在数学上，两个坐标点可以确定出一条
直线，理想的直线是没有宽度的，由无
数个点构成的。在光栅图形显示器上显
示一条直线时，只能在显示器给定的有
限像素组成的矩阵中，确定最佳逼近于
该直线的一组像素点来表示，这就是直
线的扫描转换。
? 在绘制斜线时, 有些点不一定正好落在
像素点上, 直线扫描转换算法必须确定
哪一个像素点来显示, 从而形成, 梯形
线, 。 当显示器分辩率很高时, 仍可以
生成高质量的直线 。
? 本节主要介绍三种创用的直线生成算法,
即数值微分法 （ DDA）, 中点画线法和
Bresenham算法 。 这三种算法都是只考虑
一个像素宽的直线, 生成直线算法的函
数形式如下,Line(x0,y0,x1,y1,color);
4,1,1 数值微分法
1,原理
数值微分法 （ DDA,Digital Differential Analysis
） 是根据数学上直线的微分方程来设计的 。 设
A(x0,y0),B(x1,y1)是直线的端点坐标, 首先计算
出直线的斜率
k=dy/dx=△ y/△ x=(y1-y0)/(x1-x0)
直线方程为,y=kx+B 或 x=1/k.y+T
当 |k|≤1时, 让 x每步增加 1,y最多增加 1，
然后用四舍五入的方法来确定直线上的
像素位置为 (x,round(y)) 。 设当前点为
(xi,yi),则下一个像素 xi+1 = xi +1,则
yi+1 =k xi+1 +B
=k(xi+1)+B=(k xi +B)+k
= yi +k
即当 x每递增 1时, y递增斜率 k。
当 |k|>1时, 应当让 y每步递增 1,这时 x最多
增加 1,然后然后用四舍五入的方法来确
定直线上的像素位置为 (round(x),y)。 设
当前点为 (xi,yi),则下一个像素 yi+1 =yi +1
,则
=1/k.(yi+1)+T=(1/k yi +T)+1/k
= xi +1/k
即当 y每递增 1时, x递增斜率 1/k。
DDA示意图
?
(xi,yi)
图 4.1 DDA示意图
(xi+1,yi+1)
实现算法
DDALine(x0,y0,x1,y1,color)
int x0,y0,x1,y1,color;
{
int length,i;
float x,y,dx,dy;
length=abs(x1-x0);
if abs(y1-y0)>length
length=abs(y1-y0);
dx=(x1-x0)/length;
dy=(y1-y0)/length;
x=x0+0.5; y=y0+0.5; //实现四舍五入
for (i=1;i<=length;i++)
{
putpixel(int(x),int(y),color);
x=x+dx;
y=y+dy;
}
}
4,1,2 中点画线法
中点画线算法示意图
1.原理,
? 设点前点为 P(xi,yi),只考虑直线斜率在
? 0,1之间时, 若直线在 x方向上增加一个
? 单位, 则在 y方向上增量只能在 0,1之间 。
? 下 一 个 像 点 只 可 能 是 P1((xi+1,yi) 或
P2((xi+1,yi+1)。
? 在以 M 表示 P1 和 P2 的中点, 即
M((xi+1,yi+0.5)。
? 又设 Q是理想直线与 x= xi+1的交点,
? 当 M在 Q的下方，则取 P2为下一个像素；
否则，取 P1为下一个像素位置。
2．递推公式和算法
? 假设直线的起点和终点分别为 （ x0,y0）
和 （ x1,y1）, 则直线方程为：
? F(x,y)=ax+by+c=0 即 (y-
y0)/(x-x0)=(y1-y0)/(x1-x0)
? 其中, a=y0-y1,b=x1-x0,c=x0y1-x1y0。
? 对于直线中的点, 则有 F(x,y)=0;对于直
线上方的点, 则有 F(x,y)>0;对于直线下
方的点, 则有 F(x,y)<0。
? 判断中点 M在 Q的上方, 还是
在下方, 只 要 将 中 点 坐 标
M(xi+1,yi+0.5)代入 F(x,y)方程
中, 并判断它的符号 。 构造判
别式
? d=F(M)=F(xi+1,yi+0.5)= a((xi+1)+b(yi+0.5)+c
? 当 d<0时，表示 M在直线的下方，则取 P2为下
一点；当 d>0时，表示 M在直线的上方，则取
P1为下一点；当 d=0时，表示 M在直线中，取
P1或 P2均可，我们约定取 P1。
递推式子
? （ 1） 当 d>=0时, 取 P1为下一个像素点,
欲判断再下一个像素, 应计算
? d1=F(M1)=F((xi+2,yi+0.5)=a(xi+2)+b(yi+0.5)+
c=d+a
? 即 d的增量 △ d=a
? （ 2） 当 d<0时, 取 P2为下一个像素点, 欲
判断再下一个像素, 应计算
? d2=F(M2)=F((xi+2,yi+1.5)=a(xi+2)+b(yi+1.5)+
c=d+a+b
? 即 d的增量△ d=a+b
（ (3) 求 d 的 初 始 值 。 第 一 个 像 素 点 为 起 点
（ x0,y0）, 则
d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c
=(ax0+by0+c)+a+0.5b
=F(x0,y0)+a+0.5b
由 由于起点 （ x0,y0） 在直线上, 即 F(x0,y0)=0，
所以 d0=a+0.5b。
中点画线算法：
MidPointLine(x0,y0,x1,y1,color)
int x0,y0,x1,y1,color;
{
int a,b,delta1,delta2,d,x,y;
a=y0-y1; b=x1-x0;
d=a+0.5*b; delta1=a; delta2=a+b;
x=x0; y=y0;
putpixel(x,y,color);
while (x<x1)
{
if (d<0)
{
x++; y++;
d+=delta2; //取 P2,并且计算下一点的 d值
}
else
{
x++;
d+=delta1; //取 P1,并且计算下一点的 d值
}
putpixel(x,y,color);
}
}
? 由于在整个算法中只考虑 d的符号, 而且
d的增量都是整数, 只是起初值包含小数,
因此, 在算法中可以用 2d代替 d,从而去
掉小数 。
? d0’=2d0=2a+b
? d1’=2d1=2(d+a)=2d+2a,即 △ d =2a
? d2’=2d2=2(d+a+b)=2d+2a+2b,
? 即 △ d =2(a+b)
? 因此, 算法中第 3行可以替换为
? d=2*a+b; delta1=2*a; delta2=2*(a+b);
中点画线法示图
4,1,3 Bresenham画线算法
? 1.算法原理
? Bresenham算法是计算机图形学领域中使用
最广泛的直线生成技术 。 该算法适合于光栅图
形显示器, 数字化仪设计等设备, 其原理描述
如下：
? Bresenham也是通过在每列像素中确定与理
想直线最近的像素来进行支线的扫描转换的 。
通过各行, 各列像素中心构造一组虚拟网格线,
按直线从起点到终点的顺序计算直线与各垂直
网格线的交点, 然后确定该列像素中与此交点
最近的像素 。
? Bresenham算法与 DDA算法类似，只是
不再采用四舍五入的办法，而是巧妙地
采用了增量计算，使得对于每一列，只
要检查一个误差项的符号，就可以确定
该列所求的像素。
2．递推公式
? 设 直 线 的 起 始 点 为 （ x0,y0 ）, 终点为
（ x1,y1）, 则直线的斜率
? k=△ y/△ x=(y1-y0)/(x1-x0)
? 考虑 0≤k≤ 1的情况 。
? 在起始点 （ x0,y0）, 误差项初值 d=0;
? 确定下一个像素点时, 当 x递增 1时, 误差项
? d的值增加一个斜率 k的值, 即
? d=d+k
Bresenham算法示图
? (1) 当 d≥0.5时, 取 （ x+1,y+1）, 且 d=d-1；
? (2) 当 d<0.5时, 取 （ x+1,y）,误差 d值不变；
? 令误差 e=d-0.5,则有
? （ 1） e=e+k,并且误差 e的初值, e = -0.5;
? （ 2） 当 e≥0时, 取 （ x+1,y+1）, 且 e=e-1；
? 当 e<0时，取（ x+1,y）,误差 e值不变；
程序描述
? Bresenham_line(x0,y0,x1,y1,color)
? int x0,y0,x1,y1,color;
? {
? int x,y,dx,dy,i;
? float k,e;
? dx=x1-x0;dy=y1-y0;
? k=dy/dx;
? e=-0.5; x=x0; y=y0;
? for (i=0; i<=dx; i++)
? {
? putpixel(x,y,color);
? x=x+1;
? e=e+k;
? if (e>=0)
? {
? y=y+1; e=e-1;
? }
? }
程序改进：
? 在每次计算 e值时得到都是小数, 为了
便于硬件计算, 取掉小数 。 由于算法只
需要用到误差项 e的符号, 所以可以作如
下替换：
? 设 e’=2e=2(d-0.5)=2d-1,即 e= e’/2
? 误差 e’的初值 e’= -1,
? e=e+k 替换为 e’/2=e’/2+k,即 e’=e’+2k
即可 。
算法举例：
? 设直线的起点为 （ 0,0）, 终点为 （ 5，
3）, 按 Bresenham 算法计算并确定个
像素点位置 。
? 计算 dx=5,dy=3,k=3/5=0.6,误差 e=-0.5;
? x=0,y=0
? (1) i=0,输出像素 (0,0)
? x=1,e=e+k=-0.5+0.6=0.1>0,则有
y=y+1=1,e=e-1=0.1-1=-09
? (2)i=1,输出像素 (1,1)
? x=2,e=e+k=-0.9+0.6= -0.3<0,则
有 y和 e不变, 即 y=1,e= -0.3;
? (3)i=2,输出像素 (2,1)
? x=3,e=e+k=-0.3+0.6= 0.3>0,则有
y=y+1=2,e= e-1=0.3-1= -0.7;
? (4)i=3,输出像素 (3,2)
? x=4,e=e+k=-0.7+0.6= -0.1<0,则
有 y和 e不变, 即 y=2,e= -0.1;
? (5)i=4,输出像素 (4,2)
? x=5,e=e+k=-0.1+0.6= 0.5>0,则有
y=y+1=3,e= e-1=0.5-1= -0.5;
? (6)i=5,输出像素 (5,3)
? x=6,e=e+k=-0.5+0.6= 0.1>0,则有
y=y+1=4,e= e-1=0.1-1= -0.9;
? 程序结束 。
4,1,4 程序实现与上机实践 (一 )
? 实验目的：利用 Visual C++实现三种直线生成
算法, 验证算法的正确性；
? 实验任务：
? 1,理解三种直线生成算法思想, 写出实现程
序；
? 2,添加鼠标功能, 实现交互式画直线程序；
? 3, 将 10 个 像 素 作 为 步 距 单 位, 编出
Bresenham算法的示例 。
实验步骤：
? 任务一：实现 DDA画线程序
? 实验步骤：
? 1,建立一个 DDALine的工程文件；
? 2,添加 ddaline()成员函数
? 方法：在工作区中选择 CLASSVIEW类窗
口, 右击 CDDAlineView类, 选择, add
member function…,,定义如下的成员
函数：
? void ddaline(CDC* pDC,int x0,int
y0,int x1,int y1,COLORREF color);
编写自定义的成员函数 ddaline()程序
? void CDDALineView::ddaline(CDC* pDC,int
x0,int y0,int x1,int y1,COLORREF color)
? {
? int length,i;
? float x,y,dx,dy;
? length=abs(x1-x0);
? if (abs(y1-y0)>length)
? length=abs(y1-y0);
? dx=(x1-x0)/length;
? dy=(y1-y0)/length;
? x=x0+0.5;y=y0+0.5;
?
? for (i=1;i<=length;i++)
? {
? pDC->SetPixel((int)x,(int)y,color);
? x=x+dx;y=y+dy;
? }
? }
4．编写 OnDraw()函数
? void CDDALineView::OnDraw(CDC* pDC)
? {
? CDDALineDoc* pDoc = GetDocument();
? ASSERT_VALID(pDoc);
? // TODO,add draw code for native data
here
?
ddaline(pDC,100,100,400,100,RGB(255,0,0)
);
?
ddaline(pDC,400,100,400,400,RGB(0,255,0)
);
?
? ddaline(pDC,100,400,100,100,RGB(255,255
,0));
?
ddaline(pDC,400,400,100,400,RGB(0,0,255)
);
?
ddaline(pDC,100,100,400,400,RGB(255,0,2
55));
?
ddaline(pDC,100,400,400,100,RGB(0,255,2
55));}
? }
? 5．编译、调试和运行程序，查看程序结
果。
任务二、放大 10倍后，算法演示程序
? 先画出 （ 100,100） 到 （ 600,400） 大
小为 10的网格, 然后从 （ 100,100） 以
10为单位, 计算出直线上各个像素位置 。
? 步骤：
? 1,建立 DDA2Line工程；
?2,在 OnDraw()函数中画出网格，并调
用 DDA2Line()函数
? void CDDA2LineView::OnDraw(CDC*
pDC)
? {
? CDDA2LineDoc* pDoc =
GetDocument();
? ASSERT_VALID(pDoc);
? // TODO,add draw code for native
data here
? //画网格
? int gi,gj;
? //画横线
? pDC->TextOut(90,90,"(100,100)");
? pDC->MoveTo(100,100);
? for(gj=100;gj<=400;gj=gj+10)
? {
? pDC->MoveTo(100,gj);
? pDC->LineTo(600,gj);
? }
? //画竖线
? pDC->MoveTo(100,100);
? for (gi=100;gi<=600;gi=gi+10)
? {
? pDC->MoveTo(gi,100);
? pDC->LineTo(gi,400);
? }
? pDC->TextOut(590,410,"(600,400)");
?
? //画出像素点
? DDA2line(pDC,100,100,600,400,RG
B(255,0,0));
? }
3．添加 DDA2Line()成员函数
? 方法：在工作区中选择 CLASSVIEW类
窗口, 右击 CDDAlineView 类, 选择
,add member function…,,定义如下
的成员函数：
? void DDA2Line(CDC* pDC,int x0,int
y0,int x1,int y1,COLORREF color);
4.编写 DDA2Line()函数
? void CDDA2LineView::DDA2line(CDC *pDC,int x0,
int y0,int x1,int y1,COLORREF color)
? {
? int length,i,tx,ty;
? float x,y,dx,dy;
? length=abs(x1-x0);
? if (abs(y1-y0)>length)
? length=abs(y1-y0);
? dx=(float)(x1-x0)/length;
? dy=(float)(y1-y0)/length;
? //char tbuf[20];
? //sprintf(tbuf,"dx,dy=%f,%f",dx,dy);
? //AfxMessageBox(tbuf);
? x=x0;y=y0;
? for (i=0;i<=length;i=i+10)
? {
? tx=(int)((x+5)/10)*10;
? ty=(int)((y+5)/10)*10;
?
? pDC->SetPixel(tx,ty,color);
? pDC->Ellipse(tx-5,ty-5,tx+5,ty+5);
? x=x+dx*10;y=y+dy*10;
? }
? }
? 5.调试、运行程序
任务三、加入鼠标功能，实现
交互式画直线
? 第一步：建立 DDAMouseLine工程文件；
? 第二步：向视图类中添加自定义的成员变量
? 用鼠标右键单击视图类, 选择, Add
Member Variable…,,添加下面三个成员变量 。
? proctected,
? CPoint m_p1; // 起点
? CPoint m_p2; //终点
? int m_ist; //区别, m_ist=0,表示直线
起点,
? //m_ist=1，表示直线终点
? 第三步：向视图类中添加自定义的成员函数原
型：
? public:
? void DDAMouseLine(CDC *pDC,int
x0,int y0,int x1,int y1,COLORREF color);
? 第四步：在视图类 CPP文件的构造函数中初始
化成员变量 。
? 视图类的构造函数名与该视图类的名字相
同 。 在 视 图 类 中 选 择 构 造 函 数, 如：
CDDAMouseLineView(),用鼠标左键双击,
输入下面程序代码：
? CDDAMouseLineView::CDDAMouseLineVi
ew()
? {
? // TODO,add construction code here
? m_p1.x=0; m_p1.y=0; //起点
? m_p2.x=0; m_p2.y=0; //终点
? m_ist=0; //0,第 1点； 1,第 2点；
? }
第五步：在视图类的 OnDraw()
函数中加入下列代码，实现视
图绘图
? void CMouseSpringView::OnDraw(CDC* pDC)
? {
? CMouseSpringDoc* pDoc = GetDocument();
? ASSERT_VALID(pDoc);
? // TODO,add draw code for native data here
? pDC-
>SelectStockObject(NULL_BRUSH);
? DDAMouseLine(pDC,m_p1.x,m_p1.y,m_p2.x,
m_p2.y,RGB(255,0,0));
? // 调用自定义的成员函数,用鼠标画直线
? }
第六步：向视图类中添加鼠标
OnLButtonDown()函数消息响应函数，
并输入鼠标处理程序代码 。
? void CMouseSpringView::OnLButtonDown(UINT nFlags,
CPoint point)
? {
? // TODO,Add your message handler code here and/or
call default
? CDC *pDC=GetDC();
? pDC->SelectStockObject(NULL_BRUSH);
? if (!m_ist) //是起点
? {
? m_p1=m_p2=point; //纪录第一次单击鼠标位置,
定圆心
? m_ist++;
? }
? else
? {
? m_p2=point; //记录第二次单击鼠标的位置, 定终
点的点
? m_ist--; // 为新绘图作准备
?
DDAMouseLine(pDC,m_p1.x,m_p1.y,m_p2.x,m_p2.y,R
GB(255,0,0)); //绘制新直线
? }
? ReleaseDC(pDC); //释放设备环境
? CView::OnLButtonDown(nFlags,point);
? }
第七步：添加成员函数的程序代码
? void CDDAMouseLineView::DDAMouseLine(CDC *pDC,int x0,int
y0,int x1,int y1,COLORREF color)
? {
? int length,i;
? float x,y,dx,dy;
? length=abs(x1-x0);
? if (abs(y1-y0)>length)
? length=abs(y1-y0);
? dx=(float)(x1-x0)/length;
? dy=(float)(y1-y0)/length;
? x=x0+0.5;y=y0+0.5;
? for (i=1;i<=length;i++)
? {
? pDC->SetPixel((int)x,(int)y,color);
? x=x+dx;y=y+dy;
? }
? //pDC->MoveTo(x0,y0);
? //pDC->LineTo(x1,y1);
? }
? 第八步：编译运行程序，验证运行结果。
? 程序改进, 添加橡皮筋绘图技术, 实现交互式
画直线 。
? 向视图类中添加鼠标 OnMouseMove ()函数
消息响应函数, 并输入鼠标处理程序代码 。
? void CDDAMouseLineView::OnMouseMove(UINT
nFlags,CPoint point)
? {
? // TODO,Add your message handler code
here and/or call default
? CDC *pDC=GetDC();
? int nDrawmode=pDC->SetROP2(R2_NOT); //设
置异或绘图模式, 并保存原来绘图模式
? pDC->SelectStockObject(NULL_BRUSH);
? if(m_ist==1)
? {
? CPoint prePnt,curPnt;
? prePnt=m_p2; //获得鼠标所在的前一位置
? curPnt=point;
? //绘制橡皮筋线
?
DDAMouseLine(pDC,m_p1.x,m_p1.y,prePnt.x,prePnt.y,
RGB(255,0,0));
? //DrawCircle(pDC,m_bO,prePnt); //用异或模式重
复画圆, 擦出所画的圆
?
DDAMouseLine(pDC,m_p1.x,m_p1.y,curPnt.x,curPnt.y,
RGB(255,0,0));
?
? //DrawCircle(pDC,m_bO,curPnt); //用当前位置作为圆周上的
点画圆
? m_p2=point;
? }
? pDC->SetROP2(nDrawmode); //恢复原绘图模式
? ReleaseDC(pDC); //释放设备环境
?
? CView::OnMouseMove(nFlags,point);
? }
4,2 圆与椭圆的扫描转换
?4,2,1 圆的扫描转换
? 为了讲述原理方便, 我们只考虑中心在
原点, 半径为 R的圆, 圆的方程为：
X2+Y2=R2。 对于圆心不在原点的圆, 可
以通过平移变换, 化为中心在原点的圆,
再进行扫描转换 。 而对于显示器坐标原
点在左上角的情况, 要根据圆的扫描转
换原理进行适当的修改 。
? 由于圆的对称性，要扫描转换生成
X2+Y2=R2的圆，只要能生成 8分圆，那
么圆的其它部分可以通过对称关系得到。
设圆上一点的坐标为（ x,y），可得到其
它 7个 8分圆上对应的点（ y,x）、（ y,-
x）、（ x,-y）、（ -x,-y）、（ -y,-x）、
（ -y,x）、（ -x,y），如图 4.2.1所示。因
此，只需讨论 8分圆的扫描转换。
一、中点画圆法
? 1,原理：考虑第二个 8分圆, 讨论如何
从 （ 0,R） （ R/sqrt(2),R/sqrt(2)） 顺时
针地确定最佳逼近于该圆弧的像素序列 。
如图 4.2.2所示, 假设 x坐标为 xp的像素已
经确定, 为 P(xp,yp),那么, 下一个像素
只能是正右方的 P1(xp+1,yp)或右下方的
P2(xp+1,yp-1)两者之一 。
? 2,构造函数
? F(x,y)= X2+Y2-R2
? 存在下面关系：对于圆上的点, F(x,y)=0；对
于圆外 的点, F(x,y)>0 ；对 于圆内的点,
F(x,y)<0；
? 假设 M是 P1 和 P2 的中点, 即 M=( xp+1,yp-0.5)。
那么,
? （ 1） 当 F(M)<0时, 表示 M在圆内, 应取
P1作为下一个像素；
? （ 2） 当 F(M)>0时, 表示 M在圆外, 应取
P2作为下一个像素；
? （ 3） 当 F(M)=0时, 表示 M在圆上, 取 P1
和 P2均可, 约定取 P2作为下一像素；
? 构造判别式
? d=F(M)=F(xp+1,yp-0.5)=( xp+1)2+( yp-
0.5)2-R2
? 若 d<0,则应取 P1为下一像素, 而且再下一
个像素的判别式为
? d=F(xp+2,yp-0.5)= ( xp+2)2+( yp-0.5)2-R2
=d+2 xp +3
? 即 △ d=2 xp +3
?
? 若 d≥ 0,则应取 P2为下一像素, 而且再下一个
像素的判别式为
? d=F(xp+2,yp-1.5)= ( xp+2)2+( yp-1.5)2-R2
=d+(2 xp +3)+(-2 yp +2) =d+2(xp- yp )+5
? 即 △ d=2(xp- yp )+5
? 初值：我们只考虑按顺时针方向生成第二个 8
分圆, 因此第一个像素是 （ 0,R）,判别式 d的
初值为：
? d0=F(1,R-0.5)=12+(R-0.5)2-R2=1.25-R
? 3,算法描述
? MidpointCircle(int r,int color)
? {
? int x,y;
? float d;
? x=0;y=r;d=1.25-r;
? setpixel(x,y,color);
? while (x<y)
? {
? if(d<0)
? {
? d+=2*x+3; x++;
? }
?
? else
? {
? d+=2*(x-y)+5;
? x++; y--;
? }
? Setpixel(x,y,color);
? } /* while*/
? } /* MidpointCiecle */
? 在算法描述中, 使用了浮点数来表示判
别式 d。 为了简化算法, 摆脱浮点数, 在
算法中全部使用整数, 我们使用 e=d-
0.25来代替 d。 则有：
? 初值,d=1.25-R 替换为 e=1-R；
? 判别式,d<0 替换为 e<-0.25。 由于
e的处置为整数, 而且在运算过程中的增
量也是整数, 故 e始终为整数, 所以判别
式 e<-0.25等价于 e<0；
? 增量,d=d+2x+3 改为 e=e+2x+3;
? d=d+2(x-y)+5 改为 e=e+2(x-
y)+5
?
在算法中 e仍用 d来表示，算法描述如下,
? MidpointCircle(int r,int color)
? {
? int x,y,d;
? x=0;y=r;d=1-r;
? setpixel(x,y,color);
? while (x<y)
? {
? if(d<0)
? {
? d+=2*x+3; x++;
? }
? else
? {
? d+=2*(x-y)+5;
? x++; y--;
? }
? Setpixel(x,y,color);
? } /* while*/
? } /* MidpointCiecle */
4,2,2 椭圆的扫描转换
? 中点画圆法可以推广到一般的二次曲线
的生成 。 下面介绍用中点生成法来生成
椭圆的算法 。
? 1,原理描述
? 设椭圆的方程为：
? x2/a2+y2/b2=1 或 F(x,y)= b2 x2+
a2 y2- a2,b2=0
? 其中, a为沿 x轴方向的长半轴的长度, b
为沿 y轴方向的长半轴的长度, a,b均为
整数 。 由于椭圆的对称性, 我们只考虑
第一象限椭圆弧的生成 。 在处理这段椭
圆弧时, 我们进一步把它分成两部分,
上部分和下部分, 以弧上斜率为 -1的点
（ 即法向量两个分量相等的点 ） 作为分
界 。 如图 4.2.3所示 。
? 由微积分知识, 该椭圆上一点 （ x,y） 处的法
向量为：
?
? 其中, i和 j分别是沿 x轴和 y轴方向的单位向量 。
从图中可以看出, 上部分法向量的 y分量更大,
而在下部分法向量的 x分量更大 。 因此, 若在
当前中点, 法向量 （ 2b2(xp+1),2a2(yp-0.5） )
的 y分量比 x分量大, 即
? 2b2(xp+1)<2a2(yp-0.5）
? 而在下一个中点，不等号改变方向，则说明椭
圆弧从上部分转入下部分。
? 与中点画圆法类似, 当我们确定一个像素之后,
接着在两个候选像素的中点计算一个判别式的
值, 并根据判别式符号确定两个候选像素哪个
离椭圆更近 。 下面讨论算法的具体步骤 。
? 先看椭圆弧的上部分 。 假设横坐标为 xp的像素
中与椭圆弧最接近者是 （ xp,yp）, 那么下一
对候选像素的中点是 （ xp+1,yp-0.5） 。 因此,
判别式为
?
? d1=F(xp+1,yp-0.5)= b2 (xp+1)2+ a2 (yp-0.5)2-
a2,b2
? 它的符号将决定下一个像素是取正右方的那个，
还是右下方的那个。
? 若 d1<0,中点在椭圆内, 则应取正右方的像素,
而且判别式应更新为
? d1’=F(xp+2,yp-0.5)= b2 (xp+2)2+ a2 (yp-
0.5)2- a2,b2
? = d1+ b2 (2xp+3)
? 因此, 往正右方向, 判别式 d1的增量为 b2
(2xp+3)。
? 而当 d1≥ 0,中点在椭圆之外, 这时应取右下
方的像素, 并且更新判别式为
? d1’=F(xp+2,yp-1.5)= b2 (xp+2)2+ a2 (yp-
1.5)2- a2,b2
? = d1+ b2 (2xp+3)+ a2 (-2yp+2)
? 所以, 沿右下方向, 判别式 d1的增量为,b2
(2xp+3)+ a2 (-2yp+2)。
? 判别式 d1的初始条件, 由于椭圆弧的起点为
（ 0,b）, 因此, 第一个中点是 （ 1,b-0.5）,
对应的判别式是：
? d10=F(1,b-0.5)= b2 + a2 (b-0.5)2- a2,b2
? = b2 + a2 (-b+0.25)
? 在扫描转换椭圆弧的上部分时, 在每步迭代中,
必须通过计算和比较法向量的两个分量来确定
何时从上部分转入下部分 。 这是因为在下部分,
算法有所不同 。
? 在下部分, 应改为从正下方和右下方的两个像
素中选择下一个像素 。 在刚转入下部分之时,
必须对下部分的中点判别式 d2进行初始化 。 具
体地说, 如果再上部分所选择的最后一像素是
（ xp,yp ）, 则下部分的中点判别式 d2 在
（ xp+0.5,yp-1） 处计算 。 d2在正下方向与右
下方向的增量计算与上部分计算类似 。 下部分
弧的终止条件是 y=0。
? 当 d2<0时, △ d2 = b2 (2x+2) + a2 (-2y+3)
? 当 d2≥ 0时, △ d2 = a2 (-2y+3)
2,算法描述
? 第一象限椭圆弧的扫描转换中点算法描述如下：
? MiddlepointEllipse(a,b,color)
? int a,b,color;
? {
? int x,y;
? float d1,d2;
? x=0;y=b;
? d1=b*b+a*a*(-b+0.25);
? Setpixel(x,y,color);
? While (b*b*(x+1)<a*a*(y-0.5))
? {
? if (d1<0)
? {
? d1+=b*b*(2*x+3);
? x++;
? }
? else
? {
? d1+=(b*b*(2*x+3)+a*a*(-2*y+2));
? x++; y--;
? }
? Setpixel(x,y,color);
? } // 上半部分
? d2=sqr(b*(x+0.5))+sqr(a*(y-1))-sqr(a*b);
? while (y>0)
? {
? if (d2<0)
? {
? d2+=b*b*(2*x+2)+a*a*(-2*y+3);
? x++; y--;
? }
? else
? {
? d2+=a*a*(-2*y+3);
? y--;
? }
? Setpixel(x,y,color);
? } //下半部分
? }
4.2.3程序实现与上机实践（二）
? 一, 实验目的
? 编写圆和椭圆的扫描转换算法程序, 验
证算法的正确性 。
? 二, 实验任务
? 1,编写中点画圆法的扫描转换程序,
考虑原点在 （ x0,y0） 处程序的改动；
? 2,添加鼠标程序, 实现交互式画圆；
? 3,编写中点画椭圆法的扫描转换程序；
? 添加鼠标程序，实现交互式画椭圆
? 三, 实验内容
? 1,编写中点画圆法的扫描转换程序, 考虑原
点在 （ x0,y0） 处程序的改动；
?
? 分析：考虑圆心不再原点, 设圆心坐标为
（ x0,y0） 。 通过平移坐标原点到圆心, 则第
二个 8分圆上一点 p(x,y),其原始坐标为
? x’=x+x0
? y’=y+y0
? 即 p’1（ x0 +x,y+y0）
? 即 p’1（ x0 +x,y+y0）
? 其它 7 个对称点分别是,p’2
（ x0+y,y+x0）,p’3 (x0+y,y0-x),p’4
(x0+x,y0-y),p’5 (x0-x,y0-y),p’6 (x0-
y,y0-x), p’7 (x0-y,y0+x), p’8 (x0-
x,y0+y)
算法程序如下：
? MidpointCircle(int x0,int y0,int r,int
color)
? {
? int x,y;
? float d;
? x=0;y=r;d=1.25-r;
? CirPot(x0,y0,x,y,color);
? while (x<=y)
? {
? if(d<0)
? {
? d+=2*x+3; x++;
? }
? else
? {
? d+=2*(x-y)+5;
? x++; y--;
? }
? CirPot(x0,y0,x,y,color);
? } /* while*/
? } /* MidpointCiecle */
?
? int CirPot(int x0,int y0,int x,int y,int color)
? {
? Setpixel((x0+x),(y0+y));
? Setpixel((x0+y),(y0+x));
? Setpixel((x0+y),(y0-x));
? Setpixel((x0+x),(y0-y));
? Setpixel((x0-x),(y0-y));
? Setpixel((x0-y),(y0-x));
? Setpixel((x0-y),(y0+x));
? Setpixel((x0-x),(y0+y));
? }
? 程序实现步骤：
? （ 1） 建立 MidPointCircle工程文件；
? （ 2） 右击 CMidPointCircleView类,
建立成员函数
? void MidpointCircle(CDC *pDC,int
x0,int y0,int r,COLORREF color)
? int CirPot(CDC *pDC,int x0,int y0,
int x,int y,COLORREF color)
? (3) 编写成员函数代码，程序如下：
? void
CMidPointCircleView::MidpointCircle(CDC
*pDC,int x0,int y0,int r,COLORREF color)
? {
? int x,y;
? float d;
? x=0;y=r;d=1.25-r;
? CirPot(pDC,x0,y0,x,y,color);
? while (x<=y)
? {
? if(d<0)
? {
? d+=2*x+3; x++;
? }
? else
? {
? d+=2*(x-y)+5;
? x++; y--;
? }
? CirPot(pDC,x0,y0,x,y,color);
? } /* while*/
? }
? int CMidPointCircleView::CirPot(CDC *pDC,int x0,
int y0,int x,int y,COLORREF color)
? {
? pDC->SetPixel((x0+x),(y0+y),color);
? pDC->SetPixel((x0+y),(y0+x),color);
? pDC->SetPixel((x0+y),(y0-x),color);
? pDC->SetPixel((x0+x),(y0-y),color);
? pDC->SetPixel((x0-x),(y0-y),color);
? pDC->SetPixel((x0-y),(y0-x),color);
? pDC->SetPixel((x0-y),(y0+x),color);
? pDC->SetPixel((x0-x),(y0+y),color);
? return 0;
? }
? （ 4） 编写 OnDraw(CDC* pDC)函数, 程序如下：
? void CMidPointCircleView::OnDraw(CDC* pDC)
? {
? CMidPointCircleDoc* pDoc = GetDocument();
? ASSERT_VALID(pDoc);
? // TODO,add draw code for native data here
? MidpointCircle(pDC,100,100,10,
RGB(255,0,0));
? MidpointCircle(pDC,500,300,60,
RGB(255,255,0));
? }
? （ 6） 编译、运行程序，查看结果。
任务 2：添加鼠标程序，实现交
互式画圆
? 在任务 1的基础上, 完成下列步骤：
? （ 1） 向视图类中添加自定义的成员变量
? 用鼠标右键单击视图类, 选择, Add Member
Variable…,,添加下面三个成员变量 。
? proctected,
? int m_r; // 半径
? CPoint m_bO; // 圆心
? CPoint m_bR; //圆上的点
? int m_ist; //圆心与圆周上点的区别, m_ist=0，
表示鼠标左击点为圆心,
? //m_ist=1,表示鼠标左击点为圆周上的
点
? （ 2） 在视图类 CPP文件的构造函数中初始化
成员变量
? CMidPointCircleMouseView::CMidPointCir
cleMouseView()
? {
? // TODO,add construction code here
? m_bO.x=0; m_bO.y=0; //圆心
? m_bR.x=0; m_bR.y=0; //圆上的点
? m_ist=0; //圆心与圆上的点区别
? m_r=0; //圆的半径
? }
? （ 3） 向视图类中添加自定义的成员函数原型：
? public:
? int ComputeRadius(CPoint cenp,CPoint
ardp);
? 添加成员函数的程序代码：
? int CMouseSpringView::ComputeRadius(CPoint
cenp,CPoint ardp)
? {
? int dx=cenp.x-ardp.x;
? int dy=cenp.y-ardp.y;
? //sqrt() 函数的调用, 在头文件中加入 #include
"math.h"
? return (int)sqrt(dx*dx+dy*dy);
? }
? （ 4） 向视图类中添加两个鼠标消息响应函数,
并输入鼠标处理程序代码 。
? 具体操作方法与鼠标示例 1方法相同 。 一个
是 OnLButtonDown() 函数, 另一个是
OnMouseMove()函数 。 程序如下：
? void
CMidPointCircleMouseView::OnLButtonDown(UI
NT nFlags,CPoint point)
? {
? // TODO,Add your message handler code
here and/or call default
?
? CDC *pDC=GetDC();
? pDC->SelectStockObject(NULL_BRUSH);
? if (!m_ist) //绘制圆
? {
? m_bO=m_bR=point; //纪录第一次单击鼠标位置,
定圆心
? m_ist++;
? }
? else
? {
? m_bR=point; //记录第二次单击鼠标的位置, 定圆
周上的点
? m_ist--; // 为新绘图作准备
? m_r=ComputeRadius(m_bO,m_bR);
?
MidpointCircle(pDC,m_bO.x,m_bO.y,m_r,RGB(255,0,0));
? }
? ReleaseDC(pDC); //释放设备环境
?
? CView::OnLButtonDown(nFlags,point);
? }
? void CMidPointCircleMouseView::OnMouseMove(UINT
nFlags,CPoint point)
? {
? // TODO,Add your message handler code here and/or
call default
? CDC *pDC=GetDC();
? int nDrawmode=pDC->SetROP2(R2_NOT); //设置异或绘
图模式, 并保存原来绘图模式
? pDC->SelectStockObject(NULL_BRUSH);
? if(m_ist==1)
? {
? CPoint prePnt,curPnt;
? prePnt=m_bR; //获得鼠标所在的前一位置
? curPnt=point;
? //绘制橡皮筋线
? m_r=ComputeRadius(m_bO,prePnt);
?
MidpointCircle(pDC,m_bO.x,m_bO.y,m_r,RGB(255,0,0));// 用
异或模式重复画圆, 擦出所画的圆
? // DrawCircle(pDC,m_bO,prePnt);
? m_r=ComputeRadius(m_bO,curPnt);
? MidpointCircle(pDC,m_bO.x,m_bO.y,m_r,RGB(255,0,0));
//用当前位置作为圆周上的点画圆
? m_bR=point;
? }
? pDC->SetROP2(nDrawmode); //恢复原绘图模式
? ReleaseDC(pDC); //释放设备环境
?
? CView::OnMouseMove(nFlags,point);
? }
任务 3：编写中点画椭圆法的扫
描转换程序
? 程序实现步骤：
? (1) 建立 MidPointEllise工程文件；
? (2)右击 CMidPointElliseView类, 建立
成员函数
? void MidpointEllise(CDC *pDC,int
x0,int y0,int a,int b,COLORREF
color)
? (3) 编写成员函数代码，程序如下：
? void
CMidPointEllipseView::MidpointEllise(CD
C *pDC,int x0,int y0,int a,int b,
COLORREF color)
? {
? int x,y;
? float d1,d2;
? x=0;y=b;
? d1=b*b+a*a*(-b+0.25);
? pDC->SetPixel(x+x0,y+y0,color);
? while (b*b*(x+1)<a*a*(y-0.5))
? {
? if (d1<0)
? {
? d1+=b*b*(2*x+3);
? x++;
? }
? else
? {
? d1+=(b*b*(2*x+3)+a*a*(-2*y+2));
? x++; y--;
? }
? pDC->SetPixel(x0+x,y0+y,color);
? pDC->SetPixel(x0+x,y0-y,color);
? pDC->SetPixel(x0-x,y0+y,color);
? pDC->SetPixel(x0-x,y0-y,color);
? } // 上半部分
? d2=(b*(x+0.5))*(b*(x+0.5))+(a*(y-1))*(a*(y-1))-(a*b)*(a*b);
? while (y>0)
? {
? if (d2<0)
? {
? d2+=b*b*(2*x+2)+a*a*(-2*y+3);
? x++; y--;
? }
? else
? {
? d2+=a*a*(-2*y+3);
? y--;
? }
? pDC->SetPixel(x0+x,y0+y,color);
? pDC->SetPixel(x0+x,y0-y,color);
? pDC->SetPixel(x0-x,y0+y,color);
? pDC->SetPixel(x0-x,y0-y,color);
? } //下半部分
? }
? (4) 编写 OnDraw()函数
? void CMidPointEllipseView::OnDraw(CDC* pDC)
? {
? CMidPointEllipseDoc* pDoc = GetDocument();
? ASSERT_VALID(pDoc);
? // TODO,add draw code for native data here
? MidpointEllise(pDC,300,200,50,20,
RGB(255,0,0));
? }
? （ 5）编译、运行程序。
任务 4：添加鼠标程序，实现交
互式画椭圆
? 程序实现步骤：
? （ 1 ） ~ （ 3 ） 同上, 建立
MidPointElliseMouse工程文件 。
? （ 4） 添加成员变量
? protected:
? int b;
? int a;
? int m_ist;
? CPoint CenterPoint;
? CPoint RightBottom;
? CPoint LeftTop;
? （ 5） 在构造函数中赋初值
? CMidPointElliseMouseView::CMidPointElli
seMouseView()
? {
? // TODO,add construction code here
? LeftTop.x=0;LeftTop.y=0; // 左上角坐标
初值
? RightBottom.x=0;RightBottom.y=0; // 右
下角坐标初值
? CenterPoint.x=0;CenterPoint.y=0; // 中
心点坐标初值
? a=0; b=0; //长轴和短轴长度
? m_ist=0; //0:表示第一点, 1:表示第二点
? }
? (6) 添加 OnLButtonDown（ ） 函数
? void
CMidPointElliseMouseView::OnLButtonDown(UIN
T nFlags,CPoint point)
? {
? // TODO,Add your message handler code
here and/or call default
? CDC *pDC=GetDC();
? pDC->SelectStockObject(NULL_BRUSH);
? if (!m_ist) //第一点, 左上角
? {
? LeftTop=RightBottom=point; //纪录第一
次单击鼠标位置
? m_ist++;
? }
? else
? {
? RightBottom=point; //记录第二次单击鼠
标的位置
? m_ist--; // 为新绘图作准备
?
CenterPoint.x=(LeftTop.x+RightBottom.x)/2;
? CenterPoint.y=(LeftTop.y+RightBottom.y)/2;
? a=(int)abs((RightBottom.x-LeftTop.x))/2;
? b=(int)abs((RightBottom.y-LeftTop.y))/2;
?
? MidpointEllise(pDC,CenterPoint.x,Cent
erPoint.y,a,b,RGB(255,0,0));
? }
? ReleaseDC(pDC); //释放设备环境
?
? CView::OnLButtonDown(nFlags,point);
? }
? （ 7） 添加 OnMouseMove（ ） 函数
? void
CMidPointElliseMouseView::OnMouseMove(UINT
nFlags,CPoint point)
? {
? // TODO,Add your message handler code
here and/or call default
? CDC *pDC=GetDC();
? int nDrawmode=pDC->SetROP2(R2_NOT); //设
置异或绘图模式, 并保存原来绘图模式
? pDC->SelectStockObject(NULL_BRUSH);
? if(m_ist==1)
? {
? CPoint prePnt,curPnt;
? prePnt=RightBottom; //获得鼠标所在的前一
位置
? curPnt=point;
? //绘制橡皮筋线
? CenterPoint.x=(LeftTop.x+prePnt.x)/2;
? CenterPoint.y=(LeftTop.y+prePnt.y)/2;
? a=(int)abs((prePnt.x-LeftTop.x))/2;
? b=(int)abs((prePnt.y-LeftTop.y))/2;
?
MidpointEllise(pDC,CenterPoint.x,CenterPoint
.y,a,b,RGB(255,0,0));
?
? //用异或模式重复画圆, 擦出所画的圆
? //用当前点作为右下角点, 画椭圆
? CenterPoint.x=(LeftTop.x+curPnt.x)/2;
? CenterPoint.y=(LeftTop.y+curPnt.y)/2;
? a=(int)abs((curPnt.x-LeftTop.x))/2;
? b=(int)abs((curPnt.y-LeftTop.y))/2;
?
? MidpointEllise(pDC,CenterPoint.x,CenterPoint.y,a
,b,RGB(255,0,0));
? //用当前位置作为圆周上的点画圆
? RightBottom=point;
? }
? pDC->SetROP2(nDrawmode); //恢复原绘图模
式
? ReleaseDC(pDC); //释放设备环境
?
? CView::OnMouseMove(nFlags,point);
? }
? （ 8） 编译, 运行程序
提纲：
1,直线生成技术；
2,圆与椭圆生成技术
? 我们知道, 光栅图形显示器是一个像素矩阵, 如
分辨率为 640X480,每个像素可以用一种或多种
颜色显示, 分别称为单色显示器或彩色显示器 。
在光栅显示器上显示的任何一种图形, 实际上都
是具有一种或多种颜色的像素的集合 。 确定一个
像素集合及其颜色, 用于显示一个图形的过程,
称为图形的扫描转换或光栅化, 也叫图形的生成 。
实际上, 图形生成是根据图形的几何信息和属性
信息, 结合图形生成算法, 计算出要显示的中间
像素, 而不像图像生成是保存了图像的每一像素
点的信息 。 所以, 基本图形的生成, 首先要根据
基本图形的特征找出它的几何信息, 然后根据一
定的生成算法实时地在显示器上显示出完整的图
形 。
? 图形扫描转换一般分为两个步骤：先确
定有关像素, 再用图形的颜色或其它属
性对象素进行某种写操作 。 后者通常是
通过调用设备驱动程序来实现的 。 所以
扫描转换的主要任务就是确定最佳逼近
于图形的像素集的生成算法 。
.
? 本章主要讨论基本图形的扫描转换问题,
包括：
? （ 1） 一维直线, 圆, 椭圆的生成；
? （ 2） 二维图形 （ 多边形 ） 的填充；
? （ 3） 字符的表示和输入输出；
? （ 4） 图形的裁剪和反走样技术；
? 在一个图形系统中，基本图形（也称为
图元、图素等）的生成技术是最基本的，
任何复杂的图形都是由基本图形组成的，
基本图形生成的质量直接影响该图形系
统绘图的质量。所以，需要设计出精确
的基本图形生成算法，以确保图形系统
绘图的精确性。
4,1 直线图形的生成技术
? 在数学上，两个坐标点可以确定出一条
直线，理想的直线是没有宽度的，由无
数个点构成的。在光栅图形显示器上显
示一条直线时，只能在显示器给定的有
限像素组成的矩阵中，确定最佳逼近于
该直线的一组像素点来表示，这就是直
线的扫描转换。
? 在绘制斜线时, 有些点不一定正好落在
像素点上, 直线扫描转换算法必须确定
哪一个像素点来显示, 从而形成, 梯形
线, 。 当显示器分辩率很高时, 仍可以
生成高质量的直线 。
? 本节主要介绍三种创用的直线生成算法,
即数值微分法 （ DDA）, 中点画线法和
Bresenham算法 。 这三种算法都是只考虑
一个像素宽的直线, 生成直线算法的函
数形式如下,Line(x0,y0,x1,y1,color);
4,1,1 数值微分法
1,原理
数值微分法 （ DDA,Digital Differential Analysis
） 是根据数学上直线的微分方程来设计的 。 设
A(x0,y0),B(x1,y1)是直线的端点坐标, 首先计算
出直线的斜率
k=dy/dx=△ y/△ x=(y1-y0)/(x1-x0)
直线方程为,y=kx+B 或 x=1/k.y+T
当 |k|≤1时, 让 x每步增加 1,y最多增加 1，
然后用四舍五入的方法来确定直线上的
像素位置为 (x,round(y)) 。 设当前点为
(xi,yi),则下一个像素 xi+1 = xi +1,则
yi+1 =k xi+1 +B
=k(xi+1)+B=(k xi +B)+k
= yi +k
即当 x每递增 1时, y递增斜率 k。
当 |k|>1时, 应当让 y每步递增 1,这时 x最多
增加 1,然后然后用四舍五入的方法来确
定直线上的像素位置为 (round(x),y)。 设
当前点为 (xi,yi),则下一个像素 yi+1 =yi +1
,则
=1/k.(yi+1)+T=(1/k yi +T)+1/k
= xi +1/k
即当 y每递增 1时, x递增斜率 1/k。
DDA示意图
?
(xi,yi)
图 4.1 DDA示意图
(xi+1,yi+1)
实现算法
DDALine(x0,y0,x1,y1,color)
int x0,y0,x1,y1,color;
{
int length,i;
float x,y,dx,dy;
length=abs(x1-x0);
if abs(y1-y0)>length
length=abs(y1-y0);
dx=(x1-x0)/length;
dy=(y1-y0)/length;
x=x0+0.5; y=y0+0.5; //实现四舍五入
for (i=1;i<=length;i++)
{
putpixel(int(x),int(y),color);
x=x+dx;
y=y+dy;
}
}
4,1,2 中点画线法
中点画线算法示意图
1.原理,
? 设点前点为 P(xi,yi),只考虑直线斜率在
? 0,1之间时, 若直线在 x方向上增加一个
? 单位, 则在 y方向上增量只能在 0,1之间 。
? 下 一 个 像 点 只 可 能 是 P1((xi+1,yi) 或
P2((xi+1,yi+1)。
? 在以 M 表示 P1 和 P2 的中点, 即
M((xi+1,yi+0.5)。
? 又设 Q是理想直线与 x= xi+1的交点,
? 当 M在 Q的下方，则取 P2为下一个像素；
否则，取 P1为下一个像素位置。
2．递推公式和算法
? 假设直线的起点和终点分别为 （ x0,y0）
和 （ x1,y1）, 则直线方程为：
? F(x,y)=ax+by+c=0 即 (y-
y0)/(x-x0)=(y1-y0)/(x1-x0)
? 其中, a=y0-y1,b=x1-x0,c=x0y1-x1y0。
? 对于直线中的点, 则有 F(x,y)=0;对于直
线上方的点, 则有 F(x,y)>0;对于直线下
方的点, 则有 F(x,y)<0。
? 判断中点 M在 Q的上方, 还是
在下方, 只 要 将 中 点 坐 标
M(xi+1,yi+0.5)代入 F(x,y)方程
中, 并判断它的符号 。 构造判
别式
? d=F(M)=F(xi+1,yi+0.5)= a((xi+1)+b(yi+0.5)+c
? 当 d<0时，表示 M在直线的下方，则取 P2为下
一点；当 d>0时，表示 M在直线的上方，则取
P1为下一点；当 d=0时，表示 M在直线中，取
P1或 P2均可，我们约定取 P1。
递推式子
? （ 1） 当 d>=0时, 取 P1为下一个像素点,
欲判断再下一个像素, 应计算
? d1=F(M1)=F((xi+2,yi+0.5)=a(xi+2)+b(yi+0.5)+
c=d+a
? 即 d的增量 △ d=a
? （ 2） 当 d<0时, 取 P2为下一个像素点, 欲
判断再下一个像素, 应计算
? d2=F(M2)=F((xi+2,yi+1.5)=a(xi+2)+b(yi+1.5)+
c=d+a+b
? 即 d的增量△ d=a+b
（ (3) 求 d 的 初 始 值 。 第 一 个 像 素 点 为 起 点
（ x0,y0）, 则
d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c
=(ax0+by0+c)+a+0.5b
=F(x0,y0)+a+0.5b
由 由于起点 （ x0,y0） 在直线上, 即 F(x0,y0)=0，
所以 d0=a+0.5b。
中点画线算法：
MidPointLine(x0,y0,x1,y1,color)
int x0,y0,x1,y1,color;
{
int a,b,delta1,delta2,d,x,y;
a=y0-y1; b=x1-x0;
d=a+0.5*b; delta1=a; delta2=a+b;
x=x0; y=y0;
putpixel(x,y,color);
while (x<x1)
{
if (d<0)
{
x++; y++;
d+=delta2; //取 P2,并且计算下一点的 d值
}
else
{
x++;
d+=delta1; //取 P1,并且计算下一点的 d值
}
putpixel(x,y,color);
}
}
? 由于在整个算法中只考虑 d的符号, 而且
d的增量都是整数, 只是起初值包含小数,
因此, 在算法中可以用 2d代替 d,从而去
掉小数 。
? d0’=2d0=2a+b
? d1’=2d1=2(d+a)=2d+2a,即 △ d =2a
? d2’=2d2=2(d+a+b)=2d+2a+2b,
? 即 △ d =2(a+b)
? 因此, 算法中第 3行可以替换为
? d=2*a+b; delta1=2*a; delta2=2*(a+b);
中点画线法示图
4,1,3 Bresenham画线算法
? 1.算法原理
? Bresenham算法是计算机图形学领域中使用
最广泛的直线生成技术 。 该算法适合于光栅图
形显示器, 数字化仪设计等设备, 其原理描述
如下：
? Bresenham也是通过在每列像素中确定与理
想直线最近的像素来进行支线的扫描转换的 。
通过各行, 各列像素中心构造一组虚拟网格线,
按直线从起点到终点的顺序计算直线与各垂直
网格线的交点, 然后确定该列像素中与此交点
最近的像素 。
? Bresenham算法与 DDA算法类似，只是
不再采用四舍五入的办法，而是巧妙地
采用了增量计算，使得对于每一列，只
要检查一个误差项的符号，就可以确定
该列所求的像素。
2．递推公式
? 设 直 线 的 起 始 点 为 （ x0,y0 ）, 终点为
（ x1,y1）, 则直线的斜率
? k=△ y/△ x=(y1-y0)/(x1-x0)
? 考虑 0≤k≤ 1的情况 。
? 在起始点 （ x0,y0）, 误差项初值 d=0;
? 确定下一个像素点时, 当 x递增 1时, 误差项
? d的值增加一个斜率 k的值, 即
? d=d+k
Bresenham算法示图
? (1) 当 d≥0.5时, 取 （ x+1,y+1）, 且 d=d-1；
? (2) 当 d<0.5时, 取 （ x+1,y）,误差 d值不变；
? 令误差 e=d-0.5,则有
? （ 1） e=e+k,并且误差 e的初值, e = -0.5;
? （ 2） 当 e≥0时, 取 （ x+1,y+1）, 且 e=e-1；
? 当 e<0时，取（ x+1,y）,误差 e值不变；
程序描述
? Bresenham_line(x0,y0,x1,y1,color)
? int x0,y0,x1,y1,color;
? {
? int x,y,dx,dy,i;
? float k,e;
? dx=x1-x0;dy=y1-y0;
? k=dy/dx;
? e=-0.5; x=x0; y=y0;
? for (i=0; i<=dx; i++)
? {
? putpixel(x,y,color);
? x=x+1;
? e=e+k;
? if (e>=0)
? {
? y=y+1; e=e-1;
? }
? }
程序改进：
? 在每次计算 e值时得到都是小数, 为了
便于硬件计算, 取掉小数 。 由于算法只
需要用到误差项 e的符号, 所以可以作如
下替换：
? 设 e’=2e=2(d-0.5)=2d-1,即 e= e’/2
? 误差 e’的初值 e’= -1,
? e=e+k 替换为 e’/2=e’/2+k,即 e’=e’+2k
即可 。
算法举例：
? 设直线的起点为 （ 0,0）, 终点为 （ 5，
3）, 按 Bresenham 算法计算并确定个
像素点位置 。
? 计算 dx=5,dy=3,k=3/5=0.6,误差 e=-0.5;
? x=0,y=0
? (1) i=0,输出像素 (0,0)
? x=1,e=e+k=-0.5+0.6=0.1>0,则有
y=y+1=1,e=e-1=0.1-1=-09
? (2)i=1,输出像素 (1,1)
? x=2,e=e+k=-0.9+0.6= -0.3<0,则
有 y和 e不变, 即 y=1,e= -0.3;
? (3)i=2,输出像素 (2,1)
? x=3,e=e+k=-0.3+0.6= 0.3>0,则有
y=y+1=2,e= e-1=0.3-1= -0.7;
? (4)i=3,输出像素 (3,2)
? x=4,e=e+k=-0.7+0.6= -0.1<0,则
有 y和 e不变, 即 y=2,e= -0.1;
? (5)i=4,输出像素 (4,2)
? x=5,e=e+k=-0.1+0.6= 0.5>0,则有
y=y+1=3,e= e-1=0.5-1= -0.5;
? (6)i=5,输出像素 (5,3)
? x=6,e=e+k=-0.5+0.6= 0.1>0,则有
y=y+1=4,e= e-1=0.1-1= -0.9;
? 程序结束 。
4,1,4 程序实现与上机实践 (一 )
? 实验目的：利用 Visual C++实现三种直线生成
算法, 验证算法的正确性；
? 实验任务：
? 1,理解三种直线生成算法思想, 写出实现程
序；
? 2,添加鼠标功能, 实现交互式画直线程序；
? 3, 将 10 个 像 素 作 为 步 距 单 位, 编出
Bresenham算法的示例 。
实验步骤：
? 任务一：实现 DDA画线程序
? 实验步骤：
? 1,建立一个 DDALine的工程文件；
? 2,添加 ddaline()成员函数
? 方法：在工作区中选择 CLASSVIEW类窗
口, 右击 CDDAlineView类, 选择, add
member function…,,定义如下的成员
函数：
? void ddaline(CDC* pDC,int x0,int
y0,int x1,int y1,COLORREF color);
编写自定义的成员函数 ddaline()程序
? void CDDALineView::ddaline(CDC* pDC,int
x0,int y0,int x1,int y1,COLORREF color)
? {
? int length,i;
? float x,y,dx,dy;
? length=abs(x1-x0);
? if (abs(y1-y0)>length)
? length=abs(y1-y0);
? dx=(x1-x0)/length;
? dy=(y1-y0)/length;
? x=x0+0.5;y=y0+0.5;
?
? for (i=1;i<=length;i++)
? {
? pDC->SetPixel((int)x,(int)y,color);
? x=x+dx;y=y+dy;
? }
? }
4．编写 OnDraw()函数
? void CDDALineView::OnDraw(CDC* pDC)
? {
? CDDALineDoc* pDoc = GetDocument();
? ASSERT_VALID(pDoc);
? // TODO,add draw code for native data
here
?
ddaline(pDC,100,100,400,100,RGB(255,0,0)
);
?
ddaline(pDC,400,100,400,400,RGB(0,255,0)
);
?
? ddaline(pDC,100,400,100,100,RGB(255,255
,0));
?
ddaline(pDC,400,400,100,400,RGB(0,0,255)
);
?
ddaline(pDC,100,100,400,400,RGB(255,0,2
55));
?
ddaline(pDC,100,400,400,100,RGB(0,255,2
55));}
? }
? 5．编译、调试和运行程序，查看程序结
果。
任务二、放大 10倍后，算法演示程序
? 先画出 （ 100,100） 到 （ 600,400） 大
小为 10的网格, 然后从 （ 100,100） 以
10为单位, 计算出直线上各个像素位置 。
? 步骤：
? 1,建立 DDA2Line工程；
?2,在 OnDraw()函数中画出网格，并调
用 DDA2Line()函数
? void CDDA2LineView::OnDraw(CDC*
pDC)
? {
? CDDA2LineDoc* pDoc =
GetDocument();
? ASSERT_VALID(pDoc);
? // TODO,add draw code for native
data here
? //画网格
? int gi,gj;
? //画横线
? pDC->TextOut(90,90,"(100,100)");
? pDC->MoveTo(100,100);
? for(gj=100;gj<=400;gj=gj+10)
? {
? pDC->MoveTo(100,gj);
? pDC->LineTo(600,gj);
? }
? //画竖线
? pDC->MoveTo(100,100);
? for (gi=100;gi<=600;gi=gi+10)
? {
? pDC->MoveTo(gi,100);
? pDC->LineTo(gi,400);
? }
? pDC->TextOut(590,410,"(600,400)");
?
? //画出像素点
? DDA2line(pDC,100,100,600,400,RG
B(255,0,0));
? }
3．添加 DDA2Line()成员函数
? 方法：在工作区中选择 CLASSVIEW类
窗口, 右击 CDDAlineView 类, 选择
,add member function…,,定义如下
的成员函数：
? void DDA2Line(CDC* pDC,int x0,int
y0,int x1,int y1,COLORREF color);
4.编写 DDA2Line()函数
? void CDDA2LineView::DDA2line(CDC *pDC,int x0,
int y0,int x1,int y1,COLORREF color)
? {
? int length,i,tx,ty;
? float x,y,dx,dy;
? length=abs(x1-x0);
? if (abs(y1-y0)>length)
? length=abs(y1-y0);
? dx=(float)(x1-x0)/length;
? dy=(float)(y1-y0)/length;
? //char tbuf[20];
? //sprintf(tbuf,"dx,dy=%f,%f",dx,dy);
? //AfxMessageBox(tbuf);
? x=x0;y=y0;
? for (i=0;i<=length;i=i+10)
? {
? tx=(int)((x+5)/10)*10;
? ty=(int)((y+5)/10)*10;
?
? pDC->SetPixel(tx,ty,color);
? pDC->Ellipse(tx-5,ty-5,tx+5,ty+5);
? x=x+dx*10;y=y+dy*10;
? }
? }
? 5.调试、运行程序
任务三、加入鼠标功能，实现
交互式画直线
? 第一步：建立 DDAMouseLine工程文件；
? 第二步：向视图类中添加自定义的成员变量
? 用鼠标右键单击视图类, 选择, Add
Member Variable…,,添加下面三个成员变量 。
? proctected,
? CPoint m_p1; // 起点
? CPoint m_p2; //终点
? int m_ist; //区别, m_ist=0,表示直线
起点,
? //m_ist=1，表示直线终点
? 第三步：向视图类中添加自定义的成员函数原
型：
? public:
? void DDAMouseLine(CDC *pDC,int
x0,int y0,int x1,int y1,COLORREF color);
? 第四步：在视图类 CPP文件的构造函数中初始
化成员变量 。
? 视图类的构造函数名与该视图类的名字相
同 。 在 视 图 类 中 选 择 构 造 函 数, 如：
CDDAMouseLineView(),用鼠标左键双击,
输入下面程序代码：
? CDDAMouseLineView::CDDAMouseLineVi
ew()
? {
? // TODO,add construction code here
? m_p1.x=0; m_p1.y=0; //起点
? m_p2.x=0; m_p2.y=0; //终点
? m_ist=0; //0,第 1点； 1,第 2点；
? }
第五步：在视图类的 OnDraw()
函数中加入下列代码，实现视
图绘图
? void CMouseSpringView::OnDraw(CDC* pDC)
? {
? CMouseSpringDoc* pDoc = GetDocument();
? ASSERT_VALID(pDoc);
? // TODO,add draw code for native data here
? pDC-
>SelectStockObject(NULL_BRUSH);
? DDAMouseLine(pDC,m_p1.x,m_p1.y,m_p2.x,
m_p2.y,RGB(255,0,0));
? // 调用自定义的成员函数,用鼠标画直线
? }
第六步：向视图类中添加鼠标
OnLButtonDown()函数消息响应函数，
并输入鼠标处理程序代码 。
? void CMouseSpringView::OnLButtonDown(UINT nFlags,
CPoint point)
? {
? // TODO,Add your message handler code here and/or
call default
? CDC *pDC=GetDC();
? pDC->SelectStockObject(NULL_BRUSH);
? if (!m_ist) //是起点
? {
? m_p1=m_p2=point; //纪录第一次单击鼠标位置,
定圆心
? m_ist++;
? }
? else
? {
? m_p2=point; //记录第二次单击鼠标的位置, 定终
点的点
? m_ist--; // 为新绘图作准备
?
DDAMouseLine(pDC,m_p1.x,m_p1.y,m_p2.x,m_p2.y,R
GB(255,0,0)); //绘制新直线
? }
? ReleaseDC(pDC); //释放设备环境
? CView::OnLButtonDown(nFlags,point);
? }
第七步：添加成员函数的程序代码
? void CDDAMouseLineView::DDAMouseLine(CDC *pDC,int x0,int
y0,int x1,int y1,COLORREF color)
? {
? int length,i;
? float x,y,dx,dy;
? length=abs(x1-x0);
? if (abs(y1-y0)>length)
? length=abs(y1-y0);
? dx=(float)(x1-x0)/length;
? dy=(float)(y1-y0)/length;
? x=x0+0.5;y=y0+0.5;
? for (i=1;i<=length;i++)
? {
? pDC->SetPixel((int)x,(int)y,color);
? x=x+dx;y=y+dy;
? }
? //pDC->MoveTo(x0,y0);
? //pDC->LineTo(x1,y1);
? }
? 第八步：编译运行程序，验证运行结果。
? 程序改进, 添加橡皮筋绘图技术, 实现交互式
画直线 。
? 向视图类中添加鼠标 OnMouseMove ()函数
消息响应函数, 并输入鼠标处理程序代码 。
? void CDDAMouseLineView::OnMouseMove(UINT
nFlags,CPoint point)
? {
? // TODO,Add your message handler code
here and/or call default
? CDC *pDC=GetDC();
? int nDrawmode=pDC->SetROP2(R2_NOT); //设
置异或绘图模式, 并保存原来绘图模式
? pDC->SelectStockObject(NULL_BRUSH);
? if(m_ist==1)
? {
? CPoint prePnt,curPnt;
? prePnt=m_p2; //获得鼠标所在的前一位置
? curPnt=point;
? //绘制橡皮筋线
?
DDAMouseLine(pDC,m_p1.x,m_p1.y,prePnt.x,prePnt.y,
RGB(255,0,0));
? //DrawCircle(pDC,m_bO,prePnt); //用异或模式重
复画圆, 擦出所画的圆
?
DDAMouseLine(pDC,m_p1.x,m_p1.y,curPnt.x,curPnt.y,
RGB(255,0,0));
?
? //DrawCircle(pDC,m_bO,curPnt); //用当前位置作为圆周上的
点画圆
? m_p2=point;
? }
? pDC->SetROP2(nDrawmode); //恢复原绘图模式
? ReleaseDC(pDC); //释放设备环境
?
? CView::OnMouseMove(nFlags,point);
? }
4,2 圆与椭圆的扫描转换
?4,2,1 圆的扫描转换
? 为了讲述原理方便, 我们只考虑中心在
原点, 半径为 R的圆, 圆的方程为：
X2+Y2=R2。 对于圆心不在原点的圆, 可
以通过平移变换, 化为中心在原点的圆,
再进行扫描转换 。 而对于显示器坐标原
点在左上角的情况, 要根据圆的扫描转
换原理进行适当的修改 。
? 由于圆的对称性，要扫描转换生成
X2+Y2=R2的圆，只要能生成 8分圆，那
么圆的其它部分可以通过对称关系得到。
设圆上一点的坐标为（ x,y），可得到其
它 7个 8分圆上对应的点（ y,x）、（ y,-
x）、（ x,-y）、（ -x,-y）、（ -y,-x）、
（ -y,x）、（ -x,y），如图 4.2.1所示。因
此，只需讨论 8分圆的扫描转换。
一、中点画圆法
? 1,原理：考虑第二个 8分圆, 讨论如何
从 （ 0,R） （ R/sqrt(2),R/sqrt(2)） 顺时
针地确定最佳逼近于该圆弧的像素序列 。
如图 4.2.2所示, 假设 x坐标为 xp的像素已
经确定, 为 P(xp,yp),那么, 下一个像素
只能是正右方的 P1(xp+1,yp)或右下方的
P2(xp+1,yp-1)两者之一 。
? 2,构造函数
? F(x,y)= X2+Y2-R2
? 存在下面关系：对于圆上的点, F(x,y)=0；对
于圆外 的点, F(x,y)>0 ；对 于圆内的点,
F(x,y)<0；
? 假设 M是 P1 和 P2 的中点, 即 M=( xp+1,yp-0.5)。
那么,
? （ 1） 当 F(M)<0时, 表示 M在圆内, 应取
P1作为下一个像素；
? （ 2） 当 F(M)>0时, 表示 M在圆外, 应取
P2作为下一个像素；
? （ 3） 当 F(M)=0时, 表示 M在圆上, 取 P1
和 P2均可, 约定取 P2作为下一像素；
? 构造判别式
? d=F(M)=F(xp+1,yp-0.5)=( xp+1)2+( yp-
0.5)2-R2
? 若 d<0,则应取 P1为下一像素, 而且再下一
个像素的判别式为
? d=F(xp+2,yp-0.5)= ( xp+2)2+( yp-0.5)2-R2
=d+2 xp +3
? 即 △ d=2 xp +3
?
? 若 d≥ 0,则应取 P2为下一像素, 而且再下一个
像素的判别式为
? d=F(xp+2,yp-1.5)= ( xp+2)2+( yp-1.5)2-R2
=d+(2 xp +3)+(-2 yp +2) =d+2(xp- yp )+5
? 即 △ d=2(xp- yp )+5
? 初值：我们只考虑按顺时针方向生成第二个 8
分圆, 因此第一个像素是 （ 0,R）,判别式 d的
初值为：
? d0=F(1,R-0.5)=12+(R-0.5)2-R2=1.25-R
? 3,算法描述
? MidpointCircle(int r,int color)
? {
? int x,y;
? float d;
? x=0;y=r;d=1.25-r;
? setpixel(x,y,color);
? while (x<y)
? {
? if(d<0)
? {
? d+=2*x+3; x++;
? }
?
? else
? {
? d+=2*(x-y)+5;
? x++; y--;
? }
? Setpixel(x,y,color);
? } /* while*/
? } /* MidpointCiecle */
? 在算法描述中, 使用了浮点数来表示判
别式 d。 为了简化算法, 摆脱浮点数, 在
算法中全部使用整数, 我们使用 e=d-
0.25来代替 d。 则有：
? 初值,d=1.25-R 替换为 e=1-R；
? 判别式,d<0 替换为 e<-0.25。 由于
e的处置为整数, 而且在运算过程中的增
量也是整数, 故 e始终为整数, 所以判别
式 e<-0.25等价于 e<0；
? 增量,d=d+2x+3 改为 e=e+2x+3;
? d=d+2(x-y)+5 改为 e=e+2(x-
y)+5
?
在算法中 e仍用 d来表示，算法描述如下,
? MidpointCircle(int r,int color)
? {
? int x,y,d;
? x=0;y=r;d=1-r;
? setpixel(x,y,color);
? while (x<y)
? {
? if(d<0)
? {
? d+=2*x+3; x++;
? }
? else
? {
? d+=2*(x-y)+5;
? x++; y--;
? }
? Setpixel(x,y,color);
? } /* while*/
? } /* MidpointCiecle */
4,2,2 椭圆的扫描转换
? 中点画圆法可以推广到一般的二次曲线
的生成 。 下面介绍用中点生成法来生成
椭圆的算法 。
? 1,原理描述
? 设椭圆的方程为：
? x2/a2+y2/b2=1 或 F(x,y)= b2 x2+
a2 y2- a2,b2=0
? 其中, a为沿 x轴方向的长半轴的长度, b
为沿 y轴方向的长半轴的长度, a,b均为
整数 。 由于椭圆的对称性, 我们只考虑
第一象限椭圆弧的生成 。 在处理这段椭
圆弧时, 我们进一步把它分成两部分,
上部分和下部分, 以弧上斜率为 -1的点
（ 即法向量两个分量相等的点 ） 作为分
界 。 如图 4.2.3所示 。
? 由微积分知识, 该椭圆上一点 （ x,y） 处的法
向量为：
?
? 其中, i和 j分别是沿 x轴和 y轴方向的单位向量 。
从图中可以看出, 上部分法向量的 y分量更大,
而在下部分法向量的 x分量更大 。 因此, 若在
当前中点, 法向量 （ 2b2(xp+1),2a2(yp-0.5） )
的 y分量比 x分量大, 即
? 2b2(xp+1)<2a2(yp-0.5）
? 而在下一个中点，不等号改变方向，则说明椭
圆弧从上部分转入下部分。
? 与中点画圆法类似, 当我们确定一个像素之后,
接着在两个候选像素的中点计算一个判别式的
值, 并根据判别式符号确定两个候选像素哪个
离椭圆更近 。 下面讨论算法的具体步骤 。
? 先看椭圆弧的上部分 。 假设横坐标为 xp的像素
中与椭圆弧最接近者是 （ xp,yp）, 那么下一
对候选像素的中点是 （ xp+1,yp-0.5） 。 因此,
判别式为
?
? d1=F(xp+1,yp-0.5)= b2 (xp+1)2+ a2 (yp-0.5)2-
a2,b2
? 它的符号将决定下一个像素是取正右方的那个，
还是右下方的那个。
? 若 d1<0,中点在椭圆内, 则应取正右方的像素,
而且判别式应更新为
? d1’=F(xp+2,yp-0.5)= b2 (xp+2)2+ a2 (yp-
0.5)2- a2,b2
? = d1+ b2 (2xp+3)
? 因此, 往正右方向, 判别式 d1的增量为 b2
(2xp+3)。
? 而当 d1≥ 0,中点在椭圆之外, 这时应取右下
方的像素, 并且更新判别式为
? d1’=F(xp+2,yp-1.5)= b2 (xp+2)2+ a2 (yp-
1.5)2- a2,b2
? = d1+ b2 (2xp+3)+ a2 (-2yp+2)
? 所以, 沿右下方向, 判别式 d1的增量为,b2
(2xp+3)+ a2 (-2yp+2)。
? 判别式 d1的初始条件, 由于椭圆弧的起点为
（ 0,b）, 因此, 第一个中点是 （ 1,b-0.5）,
对应的判别式是：
? d10=F(1,b-0.5)= b2 + a2 (b-0.5)2- a2,b2
? = b2 + a2 (-b+0.25)
? 在扫描转换椭圆弧的上部分时, 在每步迭代中,
必须通过计算和比较法向量的两个分量来确定
何时从上部分转入下部分 。 这是因为在下部分,
算法有所不同 。
? 在下部分, 应改为从正下方和右下方的两个像
素中选择下一个像素 。 在刚转入下部分之时,
必须对下部分的中点判别式 d2进行初始化 。 具
体地说, 如果再上部分所选择的最后一像素是
（ xp,yp ）, 则下部分的中点判别式 d2 在
（ xp+0.5,yp-1） 处计算 。 d2在正下方向与右
下方向的增量计算与上部分计算类似 。 下部分
弧的终止条件是 y=0。
? 当 d2<0时, △ d2 = b2 (2x+2) + a2 (-2y+3)
? 当 d2≥ 0时, △ d2 = a2 (-2y+3)
2,算法描述
? 第一象限椭圆弧的扫描转换中点算法描述如下：
? MiddlepointEllipse(a,b,color)
? int a,b,color;
? {
? int x,y;
? float d1,d2;
? x=0;y=b;
? d1=b*b+a*a*(-b+0.25);
? Setpixel(x,y,color);
? While (b*b*(x+1)<a*a*(y-0.5))
? {
? if (d1<0)
? {
? d1+=b*b*(2*x+3);
? x++;
? }
? else
? {
? d1+=(b*b*(2*x+3)+a*a*(-2*y+2));
? x++; y--;
? }
? Setpixel(x,y,color);
? } // 上半部分
? d2=sqr(b*(x+0.5))+sqr(a*(y-1))-sqr(a*b);
? while (y>0)
? {
? if (d2<0)
? {
? d2+=b*b*(2*x+2)+a*a*(-2*y+3);
? x++; y--;
? }
? else
? {
? d2+=a*a*(-2*y+3);
? y--;
? }
? Setpixel(x,y,color);
? } //下半部分
? }
4.2.3程序实现与上机实践（二）
? 一, 实验目的
? 编写圆和椭圆的扫描转换算法程序, 验
证算法的正确性 。
? 二, 实验任务
? 1,编写中点画圆法的扫描转换程序,
考虑原点在 （ x0,y0） 处程序的改动；
? 2,添加鼠标程序, 实现交互式画圆；
? 3,编写中点画椭圆法的扫描转换程序；
? 添加鼠标程序，实现交互式画椭圆
? 三, 实验内容
? 1,编写中点画圆法的扫描转换程序, 考虑原
点在 （ x0,y0） 处程序的改动；
?
? 分析：考虑圆心不再原点, 设圆心坐标为
（ x0,y0） 。 通过平移坐标原点到圆心, 则第
二个 8分圆上一点 p(x,y),其原始坐标为
? x’=x+x0
? y’=y+y0
? 即 p’1（ x0 +x,y+y0）
? 即 p’1（ x0 +x,y+y0）
? 其它 7 个对称点分别是,p’2
（ x0+y,y+x0）,p’3 (x0+y,y0-x),p’4
(x0+x,y0-y),p’5 (x0-x,y0-y),p’6 (x0-
y,y0-x), p’7 (x0-y,y0+x), p’8 (x0-
x,y0+y)
算法程序如下：
? MidpointCircle(int x0,int y0,int r,int
color)
? {
? int x,y;
? float d;
? x=0;y=r;d=1.25-r;
? CirPot(x0,y0,x,y,color);
? while (x<=y)
? {
? if(d<0)
? {
? d+=2*x+3; x++;
? }
? else
? {
? d+=2*(x-y)+5;
? x++; y--;
? }
? CirPot(x0,y0,x,y,color);
? } /* while*/
? } /* MidpointCiecle */
?
? int CirPot(int x0,int y0,int x,int y,int color)
? {
? Setpixel((x0+x),(y0+y));
? Setpixel((x0+y),(y0+x));
? Setpixel((x0+y),(y0-x));
? Setpixel((x0+x),(y0-y));
? Setpixel((x0-x),(y0-y));
? Setpixel((x0-y),(y0-x));
? Setpixel((x0-y),(y0+x));
? Setpixel((x0-x),(y0+y));
? }
? 程序实现步骤：
? （ 1） 建立 MidPointCircle工程文件；
? （ 2） 右击 CMidPointCircleView类,
建立成员函数
? void MidpointCircle(CDC *pDC,int
x0,int y0,int r,COLORREF color)
? int CirPot(CDC *pDC,int x0,int y0,
int x,int y,COLORREF color)
? (3) 编写成员函数代码，程序如下：
? void
CMidPointCircleView::MidpointCircle(CDC
*pDC,int x0,int y0,int r,COLORREF color)
? {
? int x,y;
? float d;
? x=0;y=r;d=1.25-r;
? CirPot(pDC,x0,y0,x,y,color);
? while (x<=y)
? {
? if(d<0)
? {
? d+=2*x+3; x++;
? }
? else
? {
? d+=2*(x-y)+5;
? x++; y--;
? }
? CirPot(pDC,x0,y0,x,y,color);
? } /* while*/
? }
? int CMidPointCircleView::CirPot(CDC *pDC,int x0,
int y0,int x,int y,COLORREF color)
? {
? pDC->SetPixel((x0+x),(y0+y),color);
? pDC->SetPixel((x0+y),(y0+x),color);
? pDC->SetPixel((x0+y),(y0-x),color);
? pDC->SetPixel((x0+x),(y0-y),color);
? pDC->SetPixel((x0-x),(y0-y),color);
? pDC->SetPixel((x0-y),(y0-x),color);
? pDC->SetPixel((x0-y),(y0+x),color);
? pDC->SetPixel((x0-x),(y0+y),color);
? return 0;
? }
? （ 4） 编写 OnDraw(CDC* pDC)函数, 程序如下：
? void CMidPointCircleView::OnDraw(CDC* pDC)
? {
? CMidPointCircleDoc* pDoc = GetDocument();
? ASSERT_VALID(pDoc);
? // TODO,add draw code for native data here
? MidpointCircle(pDC,100,100,10,
RGB(255,0,0));
? MidpointCircle(pDC,500,300,60,
RGB(255,255,0));
? }
? （ 6） 编译、运行程序，查看结果。
任务 2：添加鼠标程序，实现交
互式画圆
? 在任务 1的基础上, 完成下列步骤：
? （ 1） 向视图类中添加自定义的成员变量
? 用鼠标右键单击视图类, 选择, Add Member
Variable…,,添加下面三个成员变量 。
? proctected,
? int m_r; // 半径
? CPoint m_bO; // 圆心
? CPoint m_bR; //圆上的点
? int m_ist; //圆心与圆周上点的区别, m_ist=0，
表示鼠标左击点为圆心,
? //m_ist=1,表示鼠标左击点为圆周上的
点
? （ 2） 在视图类 CPP文件的构造函数中初始化
成员变量
? CMidPointCircleMouseView::CMidPointCir
cleMouseView()
? {
? // TODO,add construction code here
? m_bO.x=0; m_bO.y=0; //圆心
? m_bR.x=0; m_bR.y=0; //圆上的点
? m_ist=0; //圆心与圆上的点区别
? m_r=0; //圆的半径
? }
? （ 3） 向视图类中添加自定义的成员函数原型：
? public:
? int ComputeRadius(CPoint cenp,CPoint
ardp);
? 添加成员函数的程序代码：
? int CMouseSpringView::ComputeRadius(CPoint
cenp,CPoint ardp)
? {
? int dx=cenp.x-ardp.x;
? int dy=cenp.y-ardp.y;
? //sqrt() 函数的调用, 在头文件中加入 #include
"math.h"
? return (int)sqrt(dx*dx+dy*dy);
? }
? （ 4） 向视图类中添加两个鼠标消息响应函数,
并输入鼠标处理程序代码 。
? 具体操作方法与鼠标示例 1方法相同 。 一个
是 OnLButtonDown() 函数, 另一个是
OnMouseMove()函数 。 程序如下：
? void
CMidPointCircleMouseView::OnLButtonDown(UI
NT nFlags,CPoint point)
? {
? // TODO,Add your message handler code
here and/or call default
?
? CDC *pDC=GetDC();
? pDC->SelectStockObject(NULL_BRUSH);
? if (!m_ist) //绘制圆
? {
? m_bO=m_bR=point; //纪录第一次单击鼠标位置,
定圆心
? m_ist++;
? }
? else
? {
? m_bR=point; //记录第二次单击鼠标的位置, 定圆
周上的点
? m_ist--; // 为新绘图作准备
? m_r=ComputeRadius(m_bO,m_bR);
?
MidpointCircle(pDC,m_bO.x,m_bO.y,m_r,RGB(255,0,0));
? }
? ReleaseDC(pDC); //释放设备环境
?
? CView::OnLButtonDown(nFlags,point);
? }
? void CMidPointCircleMouseView::OnMouseMove(UINT
nFlags,CPoint point)
? {
? // TODO,Add your message handler code here and/or
call default
? CDC *pDC=GetDC();
? int nDrawmode=pDC->SetROP2(R2_NOT); //设置异或绘
图模式, 并保存原来绘图模式
? pDC->SelectStockObject(NULL_BRUSH);
? if(m_ist==1)
? {
? CPoint prePnt,curPnt;
? prePnt=m_bR; //获得鼠标所在的前一位置
? curPnt=point;
? //绘制橡皮筋线
? m_r=ComputeRadius(m_bO,prePnt);
?
MidpointCircle(pDC,m_bO.x,m_bO.y,m_r,RGB(255,0,0));// 用
异或模式重复画圆, 擦出所画的圆
? // DrawCircle(pDC,m_bO,prePnt);
? m_r=ComputeRadius(m_bO,curPnt);
? MidpointCircle(pDC,m_bO.x,m_bO.y,m_r,RGB(255,0,0));
//用当前位置作为圆周上的点画圆
? m_bR=point;
? }
? pDC->SetROP2(nDrawmode); //恢复原绘图模式
? ReleaseDC(pDC); //释放设备环境
?
? CView::OnMouseMove(nFlags,point);
? }
任务 3：编写中点画椭圆法的扫
描转换程序
? 程序实现步骤：
? (1) 建立 MidPointEllise工程文件；
? (2)右击 CMidPointElliseView类, 建立
成员函数
? void MidpointEllise(CDC *pDC,int
x0,int y0,int a,int b,COLORREF
color)
? (3) 编写成员函数代码，程序如下：
? void
CMidPointEllipseView::MidpointEllise(CD
C *pDC,int x0,int y0,int a,int b,
COLORREF color)
? {
? int x,y;
? float d1,d2;
? x=0;y=b;
? d1=b*b+a*a*(-b+0.25);
? pDC->SetPixel(x+x0,y+y0,color);
? while (b*b*(x+1)<a*a*(y-0.5))
? {
? if (d1<0)
? {
? d1+=b*b*(2*x+3);
? x++;
? }
? else
? {
? d1+=(b*b*(2*x+3)+a*a*(-2*y+2));
? x++; y--;
? }
? pDC->SetPixel(x0+x,y0+y,color);
? pDC->SetPixel(x0+x,y0-y,color);
? pDC->SetPixel(x0-x,y0+y,color);
? pDC->SetPixel(x0-x,y0-y,color);
? } // 上半部分
? d2=(b*(x+0.5))*(b*(x+0.5))+(a*(y-1))*(a*(y-1))-(a*b)*(a*b);
? while (y>0)
? {
? if (d2<0)
? {
? d2+=b*b*(2*x+2)+a*a*(-2*y+3);
? x++; y--;
? }
? else
? {
? d2+=a*a*(-2*y+3);
? y--;
? }
? pDC->SetPixel(x0+x,y0+y,color);
? pDC->SetPixel(x0+x,y0-y,color);
? pDC->SetPixel(x0-x,y0+y,color);
? pDC->SetPixel(x0-x,y0-y,color);
? } //下半部分
? }
? (4) 编写 OnDraw()函数
? void CMidPointEllipseView::OnDraw(CDC* pDC)
? {
? CMidPointEllipseDoc* pDoc = GetDocument();
? ASSERT_VALID(pDoc);
? // TODO,add draw code for native data here
? MidpointEllise(pDC,300,200,50,20,
RGB(255,0,0));
? }
? （ 5）编译、运行程序。
任务 4：添加鼠标程序，实现交
互式画椭圆
? 程序实现步骤：
? （ 1 ） ~ （ 3 ） 同上, 建立
MidPointElliseMouse工程文件 。
? （ 4） 添加成员变量
? protected:
? int b;
? int a;
? int m_ist;
? CPoint CenterPoint;
? CPoint RightBottom;
? CPoint LeftTop;
? （ 5） 在构造函数中赋初值
? CMidPointElliseMouseView::CMidPointElli
seMouseView()
? {
? // TODO,add construction code here
? LeftTop.x=0;LeftTop.y=0; // 左上角坐标
初值
? RightBottom.x=0;RightBottom.y=0; // 右
下角坐标初值
? CenterPoint.x=0;CenterPoint.y=0; // 中
心点坐标初值
? a=0; b=0; //长轴和短轴长度
? m_ist=0; //0:表示第一点, 1:表示第二点
? }
? (6) 添加 OnLButtonDown（ ） 函数
? void
CMidPointElliseMouseView::OnLButtonDown(UIN
T nFlags,CPoint point)
? {
? // TODO,Add your message handler code
here and/or call default
? CDC *pDC=GetDC();
? pDC->SelectStockObject(NULL_BRUSH);
? if (!m_ist) //第一点, 左上角
? {
? LeftTop=RightBottom=point; //纪录第一
次单击鼠标位置
? m_ist++;
? }
? else
? {
? RightBottom=point; //记录第二次单击鼠
标的位置
? m_ist--; // 为新绘图作准备
?
CenterPoint.x=(LeftTop.x+RightBottom.x)/2;
? CenterPoint.y=(LeftTop.y+RightBottom.y)/2;
? a=(int)abs((RightBottom.x-LeftTop.x))/2;
? b=(int)abs((RightBottom.y-LeftTop.y))/2;
?
? MidpointEllise(pDC,CenterPoint.x,Cent
erPoint.y,a,b,RGB(255,0,0));
? }
? ReleaseDC(pDC); //释放设备环境
?
? CView::OnLButtonDown(nFlags,point);
? }
? （ 7） 添加 OnMouseMove（ ） 函数
? void
CMidPointElliseMouseView::OnMouseMove(UINT
nFlags,CPoint point)
? {
? // TODO,Add your message handler code
here and/or call default
? CDC *pDC=GetDC();
? int nDrawmode=pDC->SetROP2(R2_NOT); //设
置异或绘图模式, 并保存原来绘图模式
? pDC->SelectStockObject(NULL_BRUSH);
? if(m_ist==1)
? {
? CPoint prePnt,curPnt;
? prePnt=RightBottom; //获得鼠标所在的前一
位置
? curPnt=point;
? //绘制橡皮筋线
? CenterPoint.x=(LeftTop.x+prePnt.x)/2;
? CenterPoint.y=(LeftTop.y+prePnt.y)/2;
? a=(int)abs((prePnt.x-LeftTop.x))/2;
? b=(int)abs((prePnt.y-LeftTop.y))/2;
?
MidpointEllise(pDC,CenterPoint.x,CenterPoint
.y,a,b,RGB(255,0,0));
?
? //用异或模式重复画圆, 擦出所画的圆
? //用当前点作为右下角点, 画椭圆
? CenterPoint.x=(LeftTop.x+curPnt.x)/2;
? CenterPoint.y=(LeftTop.y+curPnt.y)/2;
? a=(int)abs((curPnt.x-LeftTop.x))/2;
? b=(int)abs((curPnt.y-LeftTop.y))/2;
?
? MidpointEllise(pDC,CenterPoint.x,CenterPoint.y,a
,b,RGB(255,0,0));
? //用当前位置作为圆周上的点画圆
? RightBottom=point;
? }
? pDC->SetROP2(nDrawmode); //恢复原绘图模
式
? ReleaseDC(pDC); //释放设备环境
?
? CView::OnMouseMove(nFlags,point);
? }
? （ 8） 编译, 运行程序
