计算机图形学课件

安徽工业大学机械工程学院童宝宏

直线的扫描转换

第

H圆的扫描转换

3

章

H椭圆的扫描转换

基

本H多边形的扫描转换与区域填充

图

形y字符处理

生

成B属性处理

算

法H反走样

■•提出问题

第

3

章如何在指定的输出设备上根据坐标描

基述构造基本二维几何图形？

本

图（点、直线、圆、椭圆、多边形域、字

形

符串及其相关属性等）

生

成

算

法

:在指定的输出设备上，根据坐标

描述构造二维几何图形。

3图形的扫描转n：在光栅显示器等数字设备上

早确定一个最佳逼近于图形的象素集的过程。

基

本

图

形

生

成

算

法

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

点的生成

▼

点是图形中最基本的图素，直线、曲线以及其

第它的图元都是点的集合。

3在，何二中，一个点既没有大小，也没有维数,

点只是表示坐标系统中一个位置。

章

在中，点是用数值坐标来表示的。

基在直角坐标系中点由（X,y）两个数值组成的坐标

本表示，在三维坐标系中点是由（x,y,z）三个数值组

图成的坐标表示。

在输出设备上输出一个点，就要把应用程序中

形

的坐标信息转换成所用输出设备的相应位置。对于

生一个CRT监视器来说，输出一个点就是要在指定的

成屏幕位置上打开电子束，使该位置上的荧光点亮。

算在PC机中，点亮屏幕上一个点是由BIOS控制完

成的，各种程序语言中都有描点语句。例如C语言

法

为putpixel（x,y,color）o

光栅图形中点的表示

第

3

章

（XJ）坐标

基

本

图

形地址线性表显示屏幕

生1D表示2D表示

成

算

法像素由其左下角坐标表示

■光栅图形中点的表示

第

3

章

基

本

图

Xmin^max

形

生

成

算

法

直线是点的集合，在几何学中直线被定义为

T

两个点之间的最短距离。

第

也就是说一条直线是指所有在它上面的点的

3.1

节集合。

直

直线是一维的，即它们具有长度但没有面积。

线

的直线可以向一个方向及其相反的方向无限伸

扫长，这不是计算机图形学中所需要的，在图

描形学中研究的对象是直线段。已知线段的起

转点坐标（Xi，yi）,终点坐标（乂2，丫2）,这两

换点就确定了一条线段。

▼

一般来讲，任何图形输出设备都能准确地画出

第水平线X和垂直线Y,或对角线，但要画出一条准确

斜线不是件容易的事。

3.1

节

在光栅系统中，线段通过象素绘制，水平和垂直方

直

向的台阶大小受象素的间隔限制。

线

的这就是说，必须在离散位置上对线段取样，并且在

扫每个取样位置上决定距线段最近的象素，画一条直

线实际上就计算出来一系列与该线靠近的象素。

描

转

换

对直线进行光栅化时，需要在显示器有限个象

,干

素中，确定最佳逼近该直线的一组象素，并且按扫

第描线顺序，对这些象素进行写操作，这个过程称为

3.1用显示器绘制或1的扫描转换。

节

直线绘制的质量要求：

直

直线要直：尽量接近理想直线

线V1.

的▼2.直线的端点要准确：即无定向性和断裂情况

扫v3.直线的亮度、色泽要均匀

描V4.画线的速度要快

转

V5.要求直线具有不同的色泽、亮度、线型等

换

解决的问题：

给定直线L的两端点Po（Xo，yo）和P］（x「yi）,画出该直线

第

方法：逐点比较法，正负法，数值微分算法，

Bresenham算法等

3.节1

直

线3.1.1数值微分法(DigitalDifferential

的Analyzer,DDA法)

扫直线的微分方程:

描

转_也=乃一％

(3-1)

换,_Ax_%1-XQ

DDA算法原理:

第

阴

节

直

线

的

扫DDA算法原理

描

转

换

e=l/max（|Ax，Ayl）》单位步长

max(|Ax|JAy|)=|Ax|,即|k[l的情况:

▼

X

第+£-A=X,+

Ax|

(3-3)

3.1

节j+£.Ay=y+।—7•A-

IM

直

线max(|Ax|JAy|)=|Ay|,止匕时|k|Nl：

的

・

扫+£Ax=天

描(3-4)

转D+£,AV=N■+仄

换

■

第

直

线

的

以上的起点Po的横坐标勺向上的终点Pl的横坐标七步进，取步

扫

长=1（个象素），用2的直线方程y=Ax+A计算相应的y坐标，并

描

取象素点（x,rounds））作为当前点的坐标。因为：

转

=々匕+

换yj+i=kxj+i+bXj+A+ZrDx=ZrDx

所以，当Dx=1;M+[=%+限也就是说，当x每递增Ly递增

〃（即斜率）。

DDA算法程序:

▼

voiddda(intxl,intyl,intx2,inty2)//直线DDA

第{intk,i;floatx,y,dx,dy;

k=abs(x2-xl);

3.1

节if(abs(y2-yl)>k)k=abs(y2-yl);

dx=float(x2-xl)/k;

直

dy=float(y2-yl)/k;

线x=float(xl+0.5);

的y=float(yl+0.5);

扫for(i=0;i<k;i++){

描gl_Point(int(x),int(y));

转x=x+dx;

y=y+dy；

换图中圆黑点表示用

DDA法生成的直线

}//endDDA

▼

注意：上述分析的算法仅适用于|k|31的情形。在这

种情况下，x每增加1,y最多增加L当|k|>l时，

第

必须把x,y地位互换，y每增加1,x相应增加1/k。

3.1

节DDA算法的特点：

直

Y增量算法

线

的V直观、易实现

扫

▼需对浮点表示的变量进行四舍五入，不利于用硬

描

转件实现

换

3.1.2中点Bresenham算法(正负法)

第直线的方程

3.

节与/一%

(X/)

直尸=y-kx=。，其中左=(3-5)

ArxY一％)

线

的该直线方程号平面分为三个区域:

扫

•对于直线上的点，F(x,y)=O;

描

转•对于直线上方的点,F(x,y)>0;

换

•对于直线下方的点，F(x,y)<0o

直线将平面分为三个区域

中点画线法的基本原理：假定Owkwi,x是最大位移方向

____券渤嚓素点为（£.汉.）,则下一

------------------------------------------------------------11----------------------•

象素点有两种可盅择点：

Pd（X.+1J7.）或Pu（Xj+ljj+l）

_________Pu(xi：l,yi+

若Pu与Pd的中点（七+1叫・+0.5）

称为M,。为理想直线与*=七+1

啜(Xi+1,yi+1/2)垂线的交点。

”^i,yi)Pd(xi+1,yi)当〃在。的下方时，则取应/为

下一个象素点；当M在2的上方

时，则取Pd为下一个象素点。

Brensemham算法生成直线的原理

中点画线法的实现：

直线段£的方程式为F(x,y)=y-kx-b=O,欲判断中点AT在Q点的上方

还是下方，只要把"代入厂(x,y),并判断它的符号即可。

判别式：

di=F(XM」M)=F(%+14+0.5)=y+0.5-k^+1)-b

则有:

歹+1

>=0

J

Brensemham算法生成直线的原理

dt=F(xM.yM)=F(xz-+1/.+0.5)=y+0.5-k{xt+1)-b

误差项的递推

d<0:取右上方象素

(xi+hyi+o.fl)

4+i=厂区+2,乂+1.5)

=y+1.5—k(Xj+2)—b

=yt+1.5—4(玉+l)-b-kd<0

=%+1—k

dt=F(xM.yM)=F(xz-+1/.+0.5)=y+0.5-k{xt+1)-b

误差项的递推

d>0：取正右方象素

^Xi+2^yi+0.5)

(xi+1?yi+OjJ

4+i=尸(七+2,凹.+0.5)-i----n-----A-----

—y-+0.5—k(Xj+2)—b

=y+0.5—a(玉+1)—6—ad〉=0

—di—k

初始值d的计算:

第

3.1

节

=F(xo+l,yo+O.5)

直

线=Po+0.5-左(%+1)-

的—J^Q—kx。—b—k+。.5

扫=05—k

描

转

换

▼OgkWl时Bresenham算法的算法步骤为:

1.输入直线的两端点Po(Xo，yo)和Pi(x「yi)。

第

2.计算初始值△*、匕、、d=0.5-k、x=x。、y=y;

3.10

节

3.绘制点(x,y)。判断d的符号;

直

若d<0,则(x,y)更新为(x+l,y+l),d更新为d+l・k;

线

的否则(x,y)更新为(x+1,y),d更新为d・k。

扫

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

描

转

换

■

第

解决的问题:

3.2

节

绘出圆心在原点，

圆

的半径为整数R的圆x2+y2=R2

扫

描

转

换

3.2.1八分法画圆

第

3.2

节

圆

的

扫

描

转

换

要解决的问题：绘制八分之一圆弧

第

3.2

节

圆

的

扫

描

转

换

3.2.2简单方程产生圆弧

第算法原理：利用其函数方程，直接离散计算

3.2

节圆的函数方程为：

圆

的

扫

描

转

换

圆的极坐标方程为:

■

第

3.

节

圆9为-固定角度步长）

的

round

扫

描round

转

利用方程产生圆弧的：简单直观

换

缺点：计算量大，效率低

3.2.3中点Bresenham画圆(正负法)

第

222

构造函数F(x,y)=x-y-R

3.节2

圆

的▼对于圆上的点，有F(x,y)=O;

扫▼对于圆外的点，F(x,y)>0;

描

▼而对于圆内的点，F(x^y)<0

转o

换

中点Bresenham算法原理:

中点BresenhamiEl圆的原理

M的坐标为：M（Xi+l,y「0.5）

•当F（XM，yM）＜。时，取Pe+Ly）

•当F（XM，yM）＞0时，取Pd（Xi+i,yrD

•当F（XM，YM尸o时，约定取Pu。

构造判别式：

2

d=F（XM，加）=F（x,.+l,y（.-0.5）+（j,-0.5）

当心0时，下一点取Pu（Xj+1,y）；

当d＞0时，下一点取Pd（Xj+1,y11）。

取Pu(xi+l,yi)——巧-------o----

yi

以后误差项的递推一T

第yi-1---------o------<-------

d<0：

yi-2---------------------

3.节2

圆

的xixi+1xi+2

扫

描d=/(玉+2,%—0.5)(a)d〈=o的情况

2

2

转=(七+2)2+(K-0.5)-R

换

=a+1)2+(%—0.5)2—炉+2a+3

—dH^2X.

量

增

的

d

'

'

p

yio--------o

d>0：

yi-iQ-----e

第

3.2yi-2

节

圆

xixi+1xi+2

的

扫(b)d〉0的情况

d-F(xi+2,y.-1.5)

描

=5+2)2+。—1.5)2—灭2

转

换=(x,+1)2+(乂—0.5)2—R2+(2x.+3)+(-2J.+2)

=d

J-------1d的增量

中点Bresenham算法误差项的递月隹

第

判别式的初始值

23.

节

二尸(1,火一0.5)

圆

的=1+(&-0.5)2_

扫

描=1.25-7?

转

换

■算法步骤：

1.输入圆的半径R。

第

2•计算初/台值d=l.25-R、x=0、y=Ro

3.2

节3.绘制点(x,y)及其在八分圆中的另外七个对称点。

圆4.判断d的符号。若dSO,则先羽1d更新为d+2x+3,

的再将(x,y)更新为(x+l,y);否则先将d更新为

扫

d+2(x-y)+5,再将(x,y)更新为(x+l,y-l)o

描

5.当xvy时，重复步骤3和4。否则结束。

转

换

改进：用d-0.25代替d(避免计算小数)

算法步骤：

第

L输入圆的半径R。

2.计算初始便乏、y=R

o

3.节2

圆3.绘制点(x,y)及其在八分圆中的另外七个对称点。

的4.判断d的符号。电江列先将d更新为d+