基本图形的扫描转换

第三章基本图形的扫描转换

强调上课和上机纪律

•迟到三次作为旷课一次进行处理，早退二

次作为旷课一次进行处理

・旷课达三次者，不计平时成绩(20%)

•实验作业两次未交者，不计实验成绩

(30%)

2of126

本章内容

•3.1直线的扫描转换

•3.2圆的扫描转换

•3.3椭圆的扫描转换

•3.4直线的反走样技术

•本章小结

•习题

3of126

、r4、,

刖s

•光栅图形显示器是一个像素矩阵，如分辨

率为640X480,每个像素可以用一种或多种

颜色显示，分别称为单色显示器或彩色显

示器

•在光栅显示器上显示的任何一种图形，实

际上都是具有一种或多种颜色的像素的集

合

4of126

图形的扫描转换

•图形的扫描转换：确定一个像素集合及其

颜色，用于显示一个图形的过程，称为图

形的扫描转换或光栅化，也叫图形的生成

5of126

图形生成

•图形生成是根据图形的几何信息和属性信

息，结合图形生成算法，计算出要显示的

中间像素，而不像图像生成是保存了图像

的每一像素点的信息

■基本图形的生成，首先要根据基本图形的

特征找出它的几何信息，然后根据一定的

生成算法实时地在显示器上显示出完整的

图形

6of126

图形扫描转换步骤

•一般分为两个步骤：先确定有关像素,再

用图形的颜色或其它属性对象素进行某种

写操作。后者通常是通过调用设备驱动程

序来实现的。所以扫描转换的主要任务就

是确定最佳逼近于图形的像素集的生成算

法

7of126

理想直线

用一系列的象素点来逼近直线

8of126

•在一个图形系统中，基本图形（也称为图

元、图素等）的生成技术是最基本的，任

何复杂的图形都是由基本图形组成的，基

本图形生成的质量直接影响该图形系统绘

图的质量。所以，需要设计出精确的基本

图形生成算法，以确保图形系统绘图的精

确性

9of126

3.1直线的扫描转换

•3.1.1概述

•3.1.2数值微分DDA直线生成算法

•3.1.3中点直线生成算法

•3.1.4Bresenham直线生成算法

10of126

3.1.1概述

•直线的扫描转换：确定最佳逼近于该直线的

一组象素，并且按扫描线顺序，对这些象

素进行写操作

11of126

概述

•生成直线一般的准则是:

-(1)线条应该显得笔直

•由连续点组成的直线要显示在离散网格的平面上，

一定会有不经过网格的点，如左下图。在这种情况

下，必须选择靠近直线的网格点来逼近这条直线。

若选择的好，线就显得较直；否则就会较弯曲，如

概述

-(2)直线端点位置应该准确

•画出的线段如果不准确，往往会使两条线之间不能

很好的镶接，如下图。

-(3)直线浓度应该均匀

•线段的浓度与单位线段中所显示的点数成正比。要

保持线段的浓度均匀端点应该等距分布。只有平行

和成45。的线才能做到。,

13of126

概述

-(4)直线浓度应该与线段的长度和斜率无关

•要取得均匀的线段浓度，应该保持每单位长度的点

数是个常数。一般，采用线段的近似长度，以及生

成直线的算法，使在线段近似长度范围内保持线段

浓度均匀。

-(5)显示线段的速度应快

•生成直线可用软件和硬件来实现，一般情况下，硬

件要比软件实现得快。

14of126

3.1.2数值微分DDA直线生成算法

•数值微分法,DDA(DigitalDifferential

Analyzer)是根据数学上直线的微分方程来设计

的

•设A(Xo，y()),B(Xi，yJ是直线的端点坐标，首先计

算出直线的斜率

k=dy/dx=Ay/Ax=(y1-y0)/(x1-x0)

宜线方程为：y=kx+B或x=1/k*y+T

15of126

­作为最底层的光栅图形算法，在通常的

CAD图形系统中，会被大量应用，因此，

哪怕节约一个加法或减法，也是很了不起的

改进。

•由此出发点，导致增量算法的思想

根据k值做不同处理

•当|k日时,让x每步增加1,y最多增加1,

然后用舍掉尾数的方法来确定直线上的像

素位置为(x,round(y))

•设当前点为(4yj,则下一个像素Xj+i=%

+1,则

yi+i=kxi+1+B=k(x.+1)+B=(kXj+B)+k=1+k

即当x每递增1时，y递增斜率k

17of126

根据k值做不同处理

•当|k|>l时，应当让y每步递增1,这时x最多

增加1,然后然后用舍掉尾数的方法来确定

直线上的像素位置为(round(xby)

•设当前点为(4yj,则下一个像素yi+i=x+l

,则

Xi+i=l/k*yi+i+T=l/k*(yi+l)+T=(l/k*yj+T)+l/k

=x.+l/k

即当y每递增1时，x递增斜率1/k

18of126

输出坐标求整

•由于屏幕上的坐标为整数坐标，则真正作

为输出显示为：y输出=ROUND(yJ,其中函

数ROUND()是指会尾的整数

•因此y输出和丫门之间的量化误差最大为1。

为了改善这方面的误差，使x和y的值增加

0.5,使量化误差在(・0・5,0,5)范围之间

x=x0+0.5

y=y0+0.5

•ROUND(a)=(int)(a+0.5)

19of126

DDA直线生成举例

•例：画直线段Po(O,O)“Pi(5,2)k=0.4

xint(y+0.5)y+0.5

Line:P(O,0)—(5,2)

000+0.5o

100.4+0.5

210.8+0.5

311.2+0.5

421.6+0.5

522.0+0.5

20of126

DDA直线生成算法描述

1.if|Xi-XoF|y「yo|then

计算直线在y方向上的增量：length=|yi-y0|

2.else计算直线在x方向上的增量：length=M-Xo|

3.计算x方向的单位增量：dx=(x1-x0)/length//即1或1/k

4.计算y方向的单位增量：dy=(y1-y0)/length//BP1°Jck

5.置初值：x=x0,y=y0

6.fori=1tolengthdo

begin

7.输出点(ROUND(x),ROUND(y))

8.计算下一个点坐标x=x+dx,y=y+dy

end

9.endofalgorithm21of126

DDA直线生成算法程序

voidCTestView::OnDdaline()

{

CDC*pDC=GetDC();

COLORREFc=RGB(255,0,0);

intlength,i;

floatx,y,dx,dy;

length=abs(xb-xa);

if(abs(yb-ya)>length)

(

length=abs(yb-ya);

}

dx=(float)(xb-xa)/length;dy=(float)(yb-ya)/length;

x=(float)xa;y=(float)ya;

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

(

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

x=x+dx;y=y+dy;

}

ReleaseDC(pDC);

}22of126

DDA直线生成算法小结

•优点：

一在同一坐标上，不可能连续停留两次。

•缺点：

-开始需要执行一个除法△¥/△*或Ax/^y来确

定增量，用硬件来实现比较复杂和昂贵，用软

件实现相对容易些，但效率较低

-浮点增量的连续迭加中取整误差的积累会使长

线段锁计算的像素位置偏离实际线段

-取整操作和浮点运算十分耗时

3.1.3中点直线生成算法

•采用增量思想的DDA算法，每计算一个象

素，只需计算一个加法，是否最优？

・如非最优，如何改进？

•目标：进一步将一个加法改为一个整数加

法。

•新思路一＞DDA算法采用点斜式，可否采

用其他的直线表示方式？

•隐式表示：F(x,y)=ax+by+c=O

24of126

3.1.3中点直线生成算法

•假定直线斜率0<K<1,且

已确定点亮象素点P（Xi，y）,

则下一个与直线最接近的

像素只能是Pi（x+1,yj点或

「2（%+1»+1）点。设

1\/1（玉+1邛+0.5）为中点，Q

为交点

•问题：如何确定下一个点

亮的象素？

中点画线算法示意图

25of126

1.原理

•M在Q的下方：P2离直

线更近，取P2

•M在Q的上方：离直

线更近，取

•M与Q重合：PvP2任

取一点

•问题：如何判断M与Q

点的关系？

26of126

2.算法

・假设直线的起点和终点分别为(Xo，yo)和(xi，y])，则直

线方程为：F(x,y)=ax+by+c=O,看

•Srjqa=yo.yijb=xrx0,c=xoy1-x1yo

•由常识知：

「尸（x,y）=0点与直线重合

I/、

《尸（］,F）>0点在直线上方

/（x,y）<0点在直线下方

•结论：欲判断中点M点是在Q点上方还是在Q点下方，只

需把M代入F(x,y),并检查它的符号。

27of126

构造判别式

•将中点坐标M(Xj+1,yi+0.5)代

入F(x,y)方程中，并判断它

的符号

­构造判别式

d=F(M)=F(xi+1,yi+0.5)=

a(Xj+1)+b(yj+0.5)+c

-当d〈0时，表示M在直线(Q

点)下方，则取P2为下一点；

-当d>0时，表示M在直线(Q

点)上方，则取〕为下一点；

P问题：能否采用增

-当d=0时，表示M在直线中，

取Pl或P2均可，约定取Py量算法呢？

28of126

增量算法

•d=F(M)=F(Xj+1,yj+0.5)=a(Xj+1)+b(yj+0.5)+c

•这样做，每一个象素的计算量是4个加法,

两个乘法

•“山穷水尽疑无路”

•如果也采用增量算法呢？

•d是与y的线性函数，因此可采用增量计

算，提高运算效率

29of126

递推式子

•(1)当d>=0时，取Pi为下一个像素点，欲判断

再下一个像素，应计算

d1=F(M1)=F(xi+2,yi+0.5)=a(Xj+2)+b(yi+0.5)+c=d+a

注:d=F(M)=F(xi+1,yi+0.5)=a(xi+1)+b(yi+0.5)+c

•即d的增量△d=a

30of126

递推式子(续)

•(2)当d<0时，取P2为下一个像素点，欲判断再

下一个像素，应计算

d2=F(M2)=F(xj+2,yj+1.5)=a(xj+2)+b(yj+1.5)+c=d+a+b

注：d=F(M)=F(xi+1,yi+0.5)=a(Xj+1)+b(yj+0.5)+C

•即d的增量△d=a+b

31of126

递推式子（续）

・(3)求d的初始值

-第一个像素点为起点(x0,y0),则Mo(Xo+1,yo+O.5)

d0=F(x0+1,yo+O.5)=a(xo+1)+b(yo+O.5)+c

=(axo+byo+c)+a+O.5b

=F(xo,yo)+a+O.5b

-由于起点(x0,y0)在直线上，即F(x°,yo)=O,所以

do=a+O.5b

32of126

算法改进

•至此，至少新算法可以和DDA算法一样好

•能否再做改进？

•能否实现整数运算?

33of126

算法改进

•由于在整个算法中只考虑d的符号，而且d

的增量都是整数，只是初始值包含小数，

因此，在算法中可以用2d代替d,从而去掉

小数

d0'=2d0=2a+b

d/=2d1=2(d+a)=2d+2a,即=2a

d2'=2d2=2(d+a+b)=2d+2a+2b,BPAd

=2(a+b)

34of126

中点直线生成算法举例

•用中点画线法Po(O,O)Pi(5,2)k=O.4

•a=y()・y产2b=x1-x0=5

•d0=2a+b=1d1=2a=-4d2=2(a+b)=6

XiYid

1001d>0,取P1,增量为d1

210-3CKO,取P2,增量为d2

3213

431-1

5425

6521

中点直线生成算法程序

voidCTestView::OnMidline()

{

CDC*pDC=GetDC();

COLORREFc=RGB(0,255,0);

〃基于中点算法画斜率在0和1之间的直线，如xa=0,ya=0,xb=500,yb=200

inta,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<=xb)

(

if(d<0)

{y++;d+=d2;〃取P2,并且计算下一点的d值}

else

{d+=d1;〃取P1,并且计算下一点的d值}

x++；

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

)

ReleaseDC(pDC);36of126

}

voidCTestView::OnRandomkmidline()

{

CDC*pDC=GetDC();COLORREFc=RGB(0,0,255);

intx=xa,y=ya;

inta=ya-yb,b=xb-xa;

intex=(b>=0?1:(b=-b,-1));

intcy=(a<=0?1:(a=-a,-1));

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

intd,d1,d2;

if(-a<=b)II斜率绝对值v=1

(

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

while(x!=xb)

{

if(d<0)

y+=cy,d+=d2;

else

d+=d1;

x+=ex;

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

)

}

elseII斜率绝对值>1

(

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

while(y!=yb)

(

if(d<0)

d+=d1;

else

x+=ex,d+=d2;

y+=cy;

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

)

}

ReleaseDC(pDC);

)

3.1.4Bresenham直线生成算法

•问题

-DDA算法采用点斜式，中点法采用隐式表示

-中点法可以有整数算法

-其他表示可以推出整数算法吗？

38of126

3.1.4Bresenham直线生成算法

•Bresenham（布雷森汉姆）算法是计算机图

形学领域中使用最广泛的直线生成技术。

该算法适合于光栅图形显示器、数字化仪

等设备

Bresenham直线算法描绘的直线

39of126

1.算法思想

•Bresenham算法也是通过在每列像素中确定与理

想直线最近的像素来进行直线的扫描转换的。通

过各行、各列像素中心构造一组虚拟网格线，按

直线从起点到终点的顺序计算直线与各垂直网格

线的交点，然后确定该列像素中与此交点最近的

像素

of126

算法思想

•Bresenham算法与DDA算法类似，只是不

再采用舍去尾数的办法，而是巧妙地采用

了增量计算，使得对于每一列，只要检查

一个误差项的符号，就可以确定该列所求

的像素

P二(4o,y°)1

41of126

M

2.递推公式

•设直线的起始点为(Xo，yo),终点为(乂外必)，

则直线的斜率

•k=Ay/Ax=(y1-y0)/(x1.x0)

•由DDA算法可知：产y+k

•判断d=yg-ROUND(yi),可判定下一像素点选取

•考虑OSkR的情况：

一起始点(Xo/y。)在像素中心，所以误差项初值d=0;

-确定下一个像素点时，当x递增定由，误差项d的值增加

一个斜率k的值，即€1=€1+1<1

2.递推公式(续)

•⑴当曲0.5时,取点(x+1,y+1),且d=d・1

(一旦dNl,就把它减去1,这样保证d在0、

1之间)；

・(2)当dv0.5时，取点(x+1,y),误差d值不变；

•为方便计算，令误差e=d-0.5,则有

-(1)e=e+k,并且误差e的初值，e=・0.5;

-(2)当eNO时，取点(x+1,y+1),>e=e-1；

-(3)当evO时,取(x+1,y),误差e值不变；

43of126

算法步骤

•1,输入直线的两端点Po(x0,yo)和PEy)。

•2.计算初始值Ax、Ay>e=-0.5>x=x0>

V=Vo。

•3.绘制点(x,y)。

•4念更新为e+k,判断e的符号。若e>0,贝U

(x,y)更薪为(x+1,y+1),同时将e更新为e-1；

否贝辰y)匣薪为(x+1,y)。

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

结束。

44of126

Bresenham直线生成算法程序W

voidCTestView::OnBresenhamline()

{

CDC*pDC=GetDC();

COLORREFc=RGB(0,255,0);

〃基于Bresenham算法画斜率在0和1之间的直线，如xa=0,ya=0,xb=500,yb=200

intx,y,dx,dy,i;

floatk,e;

dx=xb-xa;dy=yb-ya;

k=(float)dy/dx;e=-0.5;x=xa;y=ya;

for(i=0;i<=dx;i++)

{

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

x=x+1;e=e+k;

if(e>=0)

{y=y+1；e=e-1;}

}

ReleaseDC(pDC);

}

算法举例

•设直线的起点为（0,0）,终点为（5,

3）,按Bresenham算法计算并确定个像

素点位置

•计算dx=5,dy=3,k=3/5=0.6,误差e=・0,5

46of126

算法举例■步骤

•x=0,y=0

•(1)i=0:输出像素(0,0)

-x=1,e=e+k=-0.5+0,6=0.1>0,贝Ll有y=y+1=1,e=e-1=0.1-

1=-0.9

•(2)i=1：输出像素(1,1)

-x=2,e=e+k=-0.9+0.6=-0,3v0,贝Ll有y和e不变,即

y=1,e=-0.3

•(3)i=2:输出像素(2,1)

-x=3,e=e+k=-0.3+0.6=0,3>0,贝Ll有y=y+1=2,e=e-

1=0.3-1=-0.7

47of126

算法举例-步骤

•(4)i=3:输出像素(3,2)

-x=4,e=e+k=-0.7+0.6=-0.1<0,贝ll有y和e不变,

即y=2,e=-0.1;

•(5)i=4:输出像素(4,2)

-x=5,e=e+k=-0,1+0.6=0,5>0,贝ll有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;

•程序结束48of126

算法改进1

•在每次计算e值时得到都是小数，为了便于

硬件计算，去掉小数。由于算法只需要用

到误差项e的符号，所以可以两边乘2作如

下替换：

-误差e'的初值e'=-1

-e=e+k替换为e'=e'+2k

-e=e-1替换为为=e'-2

49of126

算法改进程序1

voidCTestView::OnBresenhamline()

{

CDC*pDC=GetDC();

COLORREFc=RGB(0,255,0);

〃基于Bresenham算法画斜率在0和1之间的直线，如xa=0,ya=0,xb=500,yb=200

intx,y,dx,dy,i;

floatk,e;

dx=xb-xa;dy=yb-ya;

k=(float)dy/dx;e=-1;x=xa;y=ya;

for(i=0;i<=dx;i++)

{

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

x=x+1;e=e+2*k;

if(e>=0)

{y=y+1；e=e-2;}

}

ReleaseDC(pDC);

}

算法改进2

•由于只需判断e的符号，K涉及到除法，所

以式子e=e+k=e+/Xy/4x两边同乘2Zkx,

这样可以不做除法和去掉小数

-误差e'的初值e'=-Ax

-e=e+k替换为e'=e?+2Ay

-e=e-1替换为为=e'-2Ax

51of126

算法改进程序2

voidCTestView::OnBresenhamline()

{

CDC*pDC=GetDC();

COLORREFc=RGB(0,255,0);

〃基于Bresenham算法画斜率在0和1之间的直线，如xa=0,ya=0,xb=500,yb=200

intx,y,dx,dy,i,e;

dx=xb-xa;dy=yb-ya;

e="dx;x=xa;y=ya;

for(i=0;i<=dx;i++)

(

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

x=x+1;e=e+2*dy;

if(e>=0)

{y=y+1;e=e-2dx;}

)

ReleaseDC(pDC);

}

Bresenham直线生成算法程序（任意

斜率K）

•见程序

53of126

上机实践1

•1.将10个像素作为步距单位，编出DDA算

法的演示示例

(100J00]

h

y\9—

>■ck

f-

f

L

■'■)

-(■

UI

，s

yJ

M*

■■r-

■Uk

JLr-

,U|

■Js9-

f

r•V

---L-

♦、r

.--lJ

c--

r八卜

--x

q-1

•MhjJ

、

.•

卜

r*•■h

八L

--

F9k

f

11八ir-

f、/k

r,•Vr-

i

--

■

卜

(■­