基本图形的生成与计算

第5章 基本图形的生成技术

本章主要讨论一些基本图形的扫描转换问题，如一维线性框图形直线、圆、椭圆的扫描转换问题，二维图形（多边形）的填充问题，字符的表示及输入、输出问题，以及图形的裁剪和反走样问题。

对图形的扫描转换一般分为两个步骤：先确定有关象素，再用图形的颜色或其它属性，对象素进行某种写操作。所以扫描转换的主要工作，是确定最佳逼近于图形的象素集。

5.1 直线的生成算法

在数学上，理想的直线是没有宽度的，由无数个点构成的集合。我们只能在显示器所给定的有限个象素组成的矩阵中，确定最佳逼近于该直线的一组象素，并且按扫描顺序，用当前的写方式，对这些象素进行写操作。在本节，我们先介绍画一个象素宽的直线的两个算法:

5.1.1 直线的DDA 算法

一、DDA 法一

DDA 是数字微分分析式（Digital Differential Analyzer ）的缩写。设直线之起点为（x1，y1），终点为（x2，y2），则斜率k 为：

dx

dy

x x y y k =--=

1212

假设直线在第一象限，并且直线斜率小于1，则y=kx+b 计算yi+1= kxi+1+b

= kxi+b+k D x

= yi+k D x

当D x =1; yi+1 = yi+k

(X i ,

即：当x每递增1，y递增k(即直线斜率)；

于是可得到第一象限斜率小于1时的画直线程序：

void DDALine(int x0,int y0,int x1,int y1,int color)

{ int x；

float dx, dy, y, k;

dx = x1-x0; dy=y1-y0;

k=dy/dx ; y=y0;

for (x=x0; x≤x1; x++)

{ drawpixel (x, int(y+0.5), color);

y=y+k;

}

举例：

画直线p1p2(0,0)—(4,6)

如图

注意上述分析的算法仅适用于|k|≤1的情形。在这种情况下，x每增加1,y 最多增加1。

当|k|>1时，必须把x，y地位互换，考虑所有象限，

直线中的每一点坐标都可以由前一点坐标变化一个增量（dx, dy）而得到，即表示为递归式：

xi+1=xi+dx

yi+1=yi+dy

并有关系：dy =k·dx

递归式的初值为直线的起点（x1, y1），这样，就可以用加法来生成一条直线。具体方法是：

图3.2 直线方向的8个象限

图5.2

表5.1

按照直线从（x1，y1）到（x2，y2）的方向不同，分为8个象限（图5.2）。对于方向在第1a象限内的直线而言：

dx=1

dy=k

对于方向在第1b象限内的直线而言：

取值dy=1

dx=1/k。各象限中直线生成时dx, dy的取值列在表3.1之中。

研究表中的数据，可以发现两个规律：

1、当|dx|>|dy|时

|dx|=1, |dy|=k；

2、当|dx|<|dy|时

|dx|=1/k，|dy|=1

这两条规律可以导致程序的简化。由上述方法写成的程序如程序5.2所示。其中steps变量的设置，以及delta x=dx/steps; delta y=dy/steps等语句，正是利用了上述两条规律，使得程序变得简练。

使用DDA算法，每生成一条直线做两次除法，每画线中一点做两次加法。因此，用DDA法生成直线的速度是相当快的。

dda_line (xa, ya, xb, yb, c)

int xa, ya, xb, yb, c;

{

float delta_x, delta_y, x, y;

int dx, dy, steps, k;

dx=xb-xa;

dy=yb-ya;

if (abs(dx)>abs(dy)) steps=abs(dx);

else steps=abs (dy);

delta_x=(float)dx / (float)steps;

delta_y=(float)dy / (float)steps;

x=xa;

y=ya;

set_pixel(x, y, c);

for (k=1; k<=steps; k++)

{

x+=delta_x;

y+=delta_y;

set_pixel(x, y, c);

}

}

程序5.2 DDA直线生成程序

VC++环境下的程序：

// 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值，屏幕坐标与窗口坐标之间转换知识请参考图形转换章节。

（2）注意上述程序考虑到当k 1的情形x每增加1，y最多增加1；当k>1时，y每增加1，x相应增加1/k。在这个算法中，y与k用浮点数表示，而且每一步都要对y进行四舍五入后取整。

二、DDA法二

5.1.2中点画线法

图5.3

原理：

假定直线斜率0

现需确定下一个点的象素。

当M在Q的下方P2时，离直线更近更近，取P2 。

M在Q的上方时，P1离直线更近，取P1

若M与Q重合， P1、P2任取一点。

假设直线方程为：ax+by+c=0

其中a=y0-y1, b=x1-x0, c=x0y1-x1y0

由常识知：

∴欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。

构造判别式：d=F(M)=F(xp+1,yp+0.5)

=a(xp+1)+b(yp+0.5)+c

当d<0，M在直线(Q点)下方，取右上方P2；

当d>0，M在直线(Q点)上方，取右方P1；

当d=0，选P1或P2均可，约定取P1；

在此基础上再判断下一点：

当d>=0时，因为取p1，故此时：

d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)+c

= a(xp +1)+b(yp +0.5)+c +a =d+a；

所以△d1 = a

当d<0时，因为取p2,故

d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c

= a(xp +1)+b(yp +0.5)+c +a +b =d+a+b ；

增量为a＋b，△d2 = a+b

总上，每一次计算下一点坐标时有：

d>=0时△d1 = a

d<0时，△d2 = a+b

对于同一直线，a,b固定

而初始值d0为：

d0=F(x0+1, y0+0.5)= a(x0 +1)+b(y0 +0.5)+c

= F(x0, y0)+a+0.5b = a+0.5b

由于只用d 的符号作判断，为了只包含整数运算, 可以用2d代替d来摆脱小数，提高效率。

这样，2d>=0时，D的初值为：2（a+0.5b）变为2a+b，△d1 =2a

2d<0时△d2 = 2（a+b），程序如下：

void Midpoint Line (int x0,int y0,int x1, int y1,int color)

{ int a, b, d1, d2, d, x, y;

a=y0-y1; b=x1-x0; d0=2*a+b;

d1=2*a ; d2=2*(a+b);

x=x0; y=y0;

drawpixel(x, y, color);

while (x

{

if (d<0)

{

x++;

y++;

d+=d2;

}

else

{

x++;

d+=d1;

}

drawpixel (x, y, color);

} /* while */

} /* mid PointLine */

VC++环境下的程序：

//中点算法生成直线

void CMyView::OnMidpointline()

{

CDC* pDC=GetDC();

int xa=300, ya=200, xb=450, yb=300,c=RGB(0,255,0);

float a, b, d1, d2, d, x, y;

a=ya-yb, b=xb-xa, d=2*a+b;

d1=2*a, d2=2* (a+b);

x=xa, y=ya;

pDC->SetPixel(x, y, c);

while (x

{ if (d<0) {x++, y++, d+=d2; }

else {x++, d+=d1;}

pDC->SetPixel(x, y, c);

}

ReleaseDC(pDC);

}

说明：

（1）其中d是xp, yp的线性函数。为了提高运算效率，程序中采用增量计算。具体算法如下：

若当前像素处于d>0情况，则取正右方像素P1(xp+1, yp)，判断下一个像素点的位置，应计d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)=d+a；，其中增量为a。若d<0时，则取右上方像素P2（xp+1, yp+1）。再判断下一像素，则要计算d2 = F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5) + c=d+a+b，增量为a+b。

（2）画线从(x0, y0)开始，d的初值d0=F(x0+1, y0+0.5)=F(x0,

y0)+a+0.5b，因F(x0, y0)=0，则d0=a+0.5b。

（3）程序中只利用d的符号，d的增量都是整数，只是初始值包含小数，用

2d代替d，使程序中仅包含整数的运算。

例：用中点画线法P0(0,0) P1(5,2)，(x0,y0) = (0,0)

图5.4

(x1,y1)= (5,2) k=2/5 ,0<=k<=1

同时： a=y0-y1=-2

b=x1-x0=5

d>=0 时,取正右方点，△d1 = 2a=-4

d<=0时，取正有上方点，△d2 = 2（a+b）=6

i xi yi d

1 0 0 1

2 1 0 -3

3 2 1 3

4 3 1 -1

5 4 2 5

图5.5

/////////////////////////////////////////////////////////////

5.1.3 直线的Bresenham算法

一、Bresenham算法（一）

本算法由Bresenham在1965年提出。设直线从起点（x1, y1）到终点（x2, y2）。直线可表示为方程y=mx+b。其中

b = y1 - m * x1,

m =

我们的讨论先将直线方向限于1a象限（图5.6）在这种情况下，当直线光栅化时，x每次都增加1个单元，即

x i+1=x i+1

而y的相应增加应当小于1。为了光栅化，y

i+1

只可能选择如下两种位置之一（图5.6）。

图5.6

yi+1的位置选择y

i+1=yi 或者 y

i+1

=y

i

+1

选择的原则是看精确值y与y

i 及y

i+1

的距离d1及d2的大小而定。计算式为：

y=m(xi+1)+b (1)

d1=y-y

i

(2)

d2=y

i+1

-y (3)

如果d1-d2>0，则yi+1=yi+1，否则yi+1=yi。因此算法的关键在于简便地求出d1-d2的符号。将式（1）、（2）、（3）代入d1-d2，得

d1-d2=2y-2yi-1=2(xi+1)-2yi+2b-1

用dx乘等式两边，并以Pi=dx(d1-d2)代入上述等式，得

Pi=2xidy-2yidx+2dy+dx(2b-1) (4)

d1-d2是我们用以判断符号的误差。由于在1a象限，dx总大于0，所以Pi仍旧可以用作判断符号的误差。Pi-1为：

Pi+1=Pi+2dy-2dx(yi+1-yi) (5)

误差的初值P1，可将x1, y1，和b代入式（2.1.4）中的xi, yi而得到：

P1=2dy-dx

综述上面的推导，第1a象限内的直线Bresenham算法思想如下：

1、画点(x1, y2); dx=x2-x1; dy=y2-y1；

计算误差初值P1=2dy-dx; i=1；

2、求直线的下一点位置：

xi+1=xi+1；

if Pi>0 则yi+1=yi+1；

否则yi+1=yi；

3、画点（xi+1, yi-1）；

4、求下一个误差Pi+1；

if Pi>0 则Pi+1=Pi+2dy-2dx;

否则Pi+1=Pi+2dy；

5、i=i+1; if i

Bresenham算法的优点是：

1、不必计算直线之斜率，因此不做除法；

2、不用浮点数，只用整数；

3、只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。Bresenham算法速度很快，并适于用硬件实现。

由上述算法思想编制的程序如下所示。这个程序适用于所有8个方向的直线（图5.2）的生成。程序用色彩C画出一条端点为（x1, y1）和（x2, y2）的直线。其中变量的含义是：P是误差；const1和const2，是误差的逐点变化量；inc是y的单位递变量，值为1或-1；tmp是用作象限变换时的临时变量。程序

以判断|dx|>|dy|为分支，并分别将2a, 3a象限的直线和3b, 4b象限的直线变换到1a, 4a和2b, 1b方向去，以求得程序处理的简洁。

void line (x1, y1, x2, y2, c)

int x1, y1, x2, y2, c;

{

int dx;

int dy;

int x;

int y;

int p;

int const1;

int const2;

int inc;

int tmp;

dx=x2-x1;

dy=y2-y1;

if (dx*dy>=0) /*准备x或y的单位递变值。*/

inc=1;

else

inc=-1;

if (abs(dx)>abs(dy))

{

if(dx<0)

{

tmp=x1; /*将2a, 3a象限方向*/

x1=x2; /*的直线变换到1a, 4a*/

x2=tmp;

tmp=y1; /*象限方向去*/

y1=y2;

dx=-dy;

dy=-dy;

}

p=2*dy-dx;

const1=2*dy; /*注意此时误差的*/

const2=2*(dy-dy); /*变化参数取值. */

x=x1;

y=y1;

set_pixel(x, y, c);

while (x

{

x++;

if (p<0)

p+=const1;

else

{

y+=inc;

p+=const2;

}

set_piexl(x, y, c);

}

}

Else

{

if (dy<0)

{

tmp=x1; /* 将3b, 4b象限方向的*/

x1=x2; /*直线变换到2b, 1b */

x2=tmp; /*象限方向去. */

tmp=y1;

y1=y2;

dx=-dy;

dy=-dy;

}

p=2*dx-dy; /*注意此时误差的*/

const1=2*dx; /*变化参数取值. */

const2=2*(dx-dy);

x=x1;

y=y1;

set_pixel (x, y, c);

while (y

{

y++;

if(p<0)

p+=const1;

else

{

x+=inc;

p+=const2;

set_pixel (x, y, c);

}

}

}

程序3.适用于直线所有八个方向的

Bresenham直线生成算法

VC++环境下的程序：

//Bresenham算法生成直线

void CMyView::OnBresenhamline()

{

CDC* pDC=GetDC();

int x1=100, y1=200, x2=350,

y2=100,c=RGB(0,0,255);

int i,s1,s2,interchange;

float x,y,deltax,deltay,f,temp;

x=x1;

y=y1;

deltax=abs(x2-x1);

deltay=abs(y2-y1);

if(x2-x1>=0) s1=1; else s1=-1;

if(y2-y1>=0) s2=1; else s2=-1;

if(deltay>deltax){

temp=deltax;

deltax=deltay;

deltay=temp;

interchange=1;

}

else interchange=0;

f=2*deltay-deltax;

pDC->SetPixel(x,y,c);

for(i=1;i<=deltax;i++)

{

if(f>=0)

{

if(interchange==1) x+=s1;

else y+=s2;

pDC->SetPixel(x,y,c);

f=f-2*deltax;

}

Else

{

if(interchange==1) y+=s2;

else x+=s1;

f=f+2*deltay;

}

}

}

说明：

（1）以上程序已经考虑到所有象限直线的生成。（2）Bresenham算法的优点如下：

① 不必计算直线的斜率，因此不做除法。 ② 不用浮点数，只用整数。

③ 只做整数加减运算和乘2运算，而乘2运算可以用移位操作实现。

④ Bresenham 算法的运算速度很快。

二 Bresenham 算法（二）（改进的

Brensemham 算法）

过各行各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。由图5-7不难看出：

若s

设起点、终点为：（x0,y0.）,(x1,y1),设其中任意点为（xi ，yi ）,则下一点为： （xi+1,yi+1）,且有：

yi+1=yi+k(xi+1-xi)=yi+k 则x 每增加一步有：

误差项的计算 d 初=0，

每走一步：d=d+k

一旦y 方向上走了一步，d=d-1 算法步骤：

??

?

??

???≤>+=+=++0.5)(d 0.5)(d 1111i i i i i y y y x x

1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。

2.计算初始值△x 、△y 、d=0、x=x0、y=y0。

3.绘制点(x,y)。

4.d 更新为d+k ，判断d 的符号。若d>0.5，则(x,y)更新为(x+1,y+1)，同时将d 更新为d-1；否则(x,y)更新为(x+1,y)。

5.当直线没有画完时，重复步骤3和4。否则结束。 改进1：令e=d-0.5

e 初=-0.5，

每走一步有e=e+k 。 if (e>0) then e=e-1 算法步骤：

1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。

2.计算初始值△x 、△y 、e=-0.5、x=x0、y=y0。

3.绘制点(x,y)。

4.e 更新为e+k ，判断e 的符号。若e>0，则(x,y)更新为(x+1,y+1)，同时将e 更新为e-1；否则(x,y)更新为(x+1,y)。

5.当直线没有画完时，重复步骤3和4。否则结束 改进2：用2edx 来替换e e 初=-dx ，

每走一步有e=e+2dy 。 if (e>0) then e=e-2dx 步骤：

1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。

2.计算初始值dx 、dy 、e=-dx 、x=x0、y=y0。

??

?

?????≤>+=+=++0)(e 0)(e 1111i i i i i y y y x x

3.绘制点(x,y)。

4.e更新为e+2dy，判断e的符号。若e>0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2dx；否则(x,y)更新为(x+1,y)。

5.当直线没有画完时，重复步骤3和4。否则结束。

举例：画直线p0(0,0),p1(5,2),则，x,y,d变化如下（k=0.4）：

实型量计算：

替换（整型量）后

{ int x,y,dx,dy,e;

Dx=x1-x0;

Dy=y1-y0;

e=-dx;x=x0;y=y0;

While (x<=x1)

{ putpixel(x,y);

x++;

e=e+2*dy;

If (e>0)

{y++;

e=e-2*dx;

}

}

}