图形基元输出

图形设计中最基本的图形元素是点、直线、圆、曲线。任何复杂的图形均可看成是点和直线组成。本质上，物体的形状和颜色可用像素矩阵或直线段和多边形填充区域等基本几何结构来描述。通常，图形编程软件包提供使用输出图元的基本几何结构来描述场景和将输出图元组合成更复杂结构的功能。点和直线段是最简单的几何成分 。

点和直线

在CRT上，点的显示是通过开关电子枪，使电子束打击在屏幕上的某一位置发光。 电子束的定位取决于采用的显示技术。

• a.在向量显示系统中，画点命令存放在显示列表中，而坐标位置被转换为偏转线圈上的电压以使电子束定位在指定的屏幕位置上。
• b.在黑白光栅显示系统中，通过设置帧缓冲区中对应屏幕位置的位的值为1来显示点，这样，当电子束扫描过水平扫描线时，如遇到帧缓冲区中值为1时，就发射电子打击屏幕，产生亮点。对于RGB系统，颜色码随帧缓存加载，以便能显示彩色点。

画直线

通过计算两端点间的中间点来画直线。像向量笔、向量显示器这样的模拟输出设备能输出光滑的直线。

数字设备画直线是通过画直线两个端点间的各个离散的点来完成。每个分散的点的位置通过直线方程来计算。对于光栅显示系统，直线颜色装载在相应象素位置的帧缓存中。屏幕坐标只能为整数（整的像素值），因此，画点的位置只能近似实际直线上点的位置。例如计算的点的位置(10.48,20.51)近似为(10,21)。这样画出的直线会出现锯齿样，在低分辨率的显示系统上尤其明显。通过调整显示点的亮度可以减轻锯齿影响，无法消除。

点的坐标

• 点在屏幕上的位置坐标用像素为单位，点的像素坐标只能是整数。
• 而理论上的点的坐标根据直线方程可以为任何实数，而点的像素坐标受设备坐标系的制约，只能为整数。

本章将讨论光栅系统上设备级图元生成算法，物体坐标用整数的设备坐标指定。目前我们假定象素位置根据水平扫描线和垂直扫描线的交叉定义，如图。 装载指定位置象素的颜色到帧缓存用函数：setPixel(x,y)或setPixel(x,y,color) 读取指定位置象素的颜色用函数： getPixel(x,y)

** 光栅扫描转换的定义**

根据图形的几何描述,确定在二维的像素矩阵上那些像素正好在图形上或最靠近图形,这一过程就称为光栅扫描转换。

评价光栅扫描转换算法优劣的标准 a.显示图形的精度。 b.算法的时间复杂性。 c.算法的空间复杂性。

直线生成算法

计算机绘制的直线是由一系列与该直线最近的像素绘制而成,因此,理论直线与计算机绘制的直线之间总有一定的偏差,由绘图的方式决定,只能尽量减少偏差。偏差取决于屏幕光栅(分辨率)和光点的运动方向。 直线的笛卡尔斜率截距方程：

•  	y=mx+b    		    (3-1)
  

给定直线的两个端点(xa,ya)和(xb,yb)，则可计算出：

•   m=( yb- ya)/( xb- xa)        (3-2)
    b=(yaxb-ybxa)/(xb-xa)        (3-3)   
  

给定直线的两个端点(xa,ya)和(xb,yb)，则可计算出：

对于任何沿直线给定的x方向上的增量△x，可从方程(3-2)计算出对应的y方向上的增量△y: △y=m△x (3-4)

同样，可以得出对应于指定y方向上的增量△y, 可从方程(3-2)计算出对应的x向上的增量△x △x=△y/m (3-5)

对于模拟显示设备，方程(3-4)(3-5)使决定偏转电压变化的基础。

• a.当|m|<1， △x 可以设置为正比于一水平偏转电压， △y则可以根据公式计算。
• b.当|m|>1， △y 可以设置为正比于一水平偏转电压， △x则可以根据公式计算。

对于光栅显示器，直线用象素点来画，在水平或垂直上的步长△x / △y受象素间距限制。即需要在直线上不同的位置取样，并在每个样本点上取最接近直线的点。

DDA画线

DDA(digital differential analyzer)方法是利用方程(3-4)或(3-5)计算△x或△y的一个线段扫描转换算法。在一个坐标轴上以单位间隔取样，以决定另一个坐标轴上最靠近线段路径的对应整数值。 对于0≤m≤1，则在单位x间隔(△x=1)取样并计算每个顺序的y值：

		yk+1=yk+ m    （3-6）     

下标k取整数，从起点开始递增至末点。由于m可是0到1之间的任意实数，所以计算出的y值必须取整。

对于1≤m的直线段，则将x和y的规则交换，即在单位y间隔(△y=1)取样，并计算每个连续的x值：

		xk+1=xk+ 1/m    （3-7）

方程（3-6）和（3-7）基于线段从左端点到右端点进行处理的假设。假设这个过程相反，即起始点在右侧，那么，△x=-1，并且

		yk+1=yk - m      （3-8）

或△y=-1，且

		xk+1=xk- 1/m    （3-9）

方程（3-6）至（3-9）也可用于计算负斜率的线段的像素位置。

为了让直线的采样尽可能密集，斜率小于1，x更长，能分成更多的1，大于1，y更长，能分成更多的1，y作为Step。

画直线的DDA算法可表示为:

若|m|≤1:

	xk+1=xk+1,yk+1=yk+m       ;xa<xb
    or :  xk+1=xk-1,yk+1=yk-m 	    ;xa>xb

若|m|≥1:

	yk+1=yk+1,xk+1=xk+1/m   ;ya<yb
    or  :yk+1=yk-1,xk+1=xk-1/m     ; ya>yb

DDA算法的C实现

#define Round(a) ((int)(a+0.5))
void lineDDA(int xa,int ya,int xb,int yb)
{
 int dx=xb-xa,dy=yb-ya,steps,k;
 float xIncrement,yIncrement,x=xa,y=ya;
if (abs(dx)>abs(dy)) 
	steps=abs(dx);
else 
	steps=abs(dy);
  
xIncrement=dx/(float)steps;
yIncrement=dy/(float)steps;
setpixel(Round(x),Round(y),RED);
for(k=0;k<steps;k++)
 {
	x+=xIncrement;
	y+=yIncrement;
	setpixel(Round(x),Round(y),RED);
 }
}

DDA算法的缺点:

• a.计算量大(取整操作和浮点运算)
• b.效率低，速度慢
• c.误差累计，造成画长直线时点逐渐偏离理论点

Bresenham直线算法

它是由Bresenham提出的一种精确而有效的光栅线段生成算法,可用于直线、圆(圆弧)和其它曲线的生成。 考虑直线斜率0≤m≤1,且xa<xb,根据DDA算法，则 :

		xk+1=xk+1
		yk+1=yk+m

(xk,yk) 是第k步计算出的点的坐标,它在x=xk处最接近/通过直线。那么下一点需要确定在xk+1处绘制哪个像素，是(xk+1,yk)还是(xk+1,yk+1)?其位置如图：

由DDA算法知道，当xk+1=xk+1时，yk+1=yk+m后取整，有两种情况yk+1=yk和yk+1=yk+1，即B(xk+1, yk)和A(xk+1, yk+1)两个点 . 对于Bresenham算法，根据直线y=mx+b在x= xk+1处的理论坐标点与点A、B间的距离大小关系，选择距离小的点。 设定d1=|BC|，d2=|AC|，由直线方程y=mx+b，在x=xk+1的y坐标。

		y=m(xk+1)+b 

DDA是尽可能分多的Step来画线，而Breseham在每次画点时都比一下理论点和实际点。

则：

d1=y-yk=m(xk+1)+b-yk
d2=yk+1-y=yk+1-m(xk+1)-b
△d=d1-d2=2m(xk+1)-2yk+2b-1 

根据△d的符号可判断在x=xk+1应该取理论坐标的上下中的那一个点，判定方法：

	A. △d>0，  取上面的点A(yk+1=yk+1)
	B. △d≤0，取下面的点B(yk+1=yk)

由于△d的计算量大，考虑到△x=xb-xa>0, △y=yb-ya因此做如下变化：

 pk=△x△d=2△yxk-2△xyk+c，(c=2△y+△x(2b-1)为常数) 
 
则：pk+1=2△yxk+1-2△xyk+1+c 
    pk+1=pk+2△y-2△x(yk+1-yk) 
	p0=2△y-△x

Bresenham的算法表示(适用于0≤m≤1且xa<xb)：

p0=2△y-△x
xk+1=xk+1
yk+1=yk+1，pk+1=pk+2(△y-△x)    当pk≥0
yk+1=yk，pk+1=pk+2△y          当pk<0

0≤m≤1,且xa<xb的Bresenham画线算法步骤：

1. 输入线的两个端点，左端点存储在(x0,y0)中；
2. 将(x0,y0)装入帧缓冲器，画出第一个点；
3. 计算常量△x，△y，2△y和2△y-2△x，并得到决策参数的第一个值：p0=2△y-△x
4. 从k=0开始，在沿线的每个xk处，进行如下检测： 假如pk<0，下一个待画点是(xk+1,yk)，且 pk+1=pk+2△y 否则，下一个待画点是(xk+1,yk+1)，且pk+1=pk+2(△y-△x)
5. 重复步骤4，共△x次。

Bresenham算法的C实现(0<m<1且x0<x1)

void lineBres(int xa,int ya,int xb,int yb)
{
 int dx=xb-xa,dy=yb-ya;
 int p=2*dy-dx;
 int twoDy=2*dy,twoDyDx=2*(dy-dx);
 int x,y,xEnd;
 x=xa;y=ya;
 xEnd=xa;
 setpixel(x,y,RED); 
 while(x<xEnd){
 	x++;
    if(p<0)
	p+=twoDy;
 	else
    {
 		y++;
 		p+=twoDyDx;
 	}
  setpixel(x,y,RED);
 }
} 

思考：请给出任意m且区分起始点的Bresenham直线算法表示或程序。

• (1) 0<m<1, xa<xb
• (2) 0<m<1, xa>xb
• (3) 1<m，ya<yb
• (4) 1<m，ya>yb
• (5) -1<m<0, xa<xb
• (6) -1<m<0, xa>xb
• (7) m<-1，ya<yb
• (8) m<-1，ya>yb

中点直线算法

一种精确而有效的光栅线段生成算法,可用于直线、圆(圆弧)和其它曲线的生成。 考虑直线斜率0≤m≤1,且xa<xb,根据DDA算法，则 :

		xk+1=xk+1
		yk+1=yk+m

(xk,yk) 是第k步计算出的点的坐标,它在x=xk处最接近/通过直线。那么下一点需要确定在xk+1处绘制哪个像素，是(xk+1,yk)还是(xk+1,yk+1)?其位置如图：

由DDA算法知道，当xk+1=xk+1时，yk+1=yk+m后取整，有两种情况yk+1=yk和yk+1=yk+1，即B(xk+1, yk)和A(xk+1, yk+1)两个点 . A,B的中点M(xk+1,yk+0.5)，直线与x=xk+1的交点C(xk+1,mxk+1+b)，如果YC>YM(C的纵坐标较大)，则C离A近，下一点取A，否则取B. 判别式：点与直线的位置关系

	F(x,y)=y-(mx+b)

则

		<0   (x,y)位于直线下方
F(x,y)  =0   (x,y)位于直线本身上 
     	>0   (x,y)位于直线上方

所以：

△d=-2F(M)
  =-2F(xk+1,yk+0.5)=2m(xk+1) -2yk+2b-1

根据△d的符号可判断在x=xk+1应该取理论坐标的上下中的那一个点，判定方法：

	A. △d>0， 取上面的点A(yk+1=yk+1)
	B. △d≤0，取下面的点B(yk+1=yk)

由于△d的计算量大，考虑到△x=xb-xa>0, △y=yb-ya因此做如下变化：

pk=△x△d=2△yxk-2△xyk+c，(c=2△y+△x(2b-1)为常数)

则：

pk+1=2△yxk+1-2△xyk+1+c 
pk+1=pk+2△y-2△x(yk+1-yk)

同样：

	A. pk >0， 取上面的点A(yk+1=yk+1)
	B. pk ≤0，取下面的点B(yk+1=yk)

形式化公式: 初始条件

p0 =2△yxa-2△xya+2△y+△x(2b-1)
   = 2△y-△x

中点直线的算法表示(适用于0≤m≤1且xa<xb)：

 p0=2△y-△x
xk+1=xk+1
yk+1=yk+1，pk+1=pk+2(△y-△x)     当pk≥0
yk+1=yk，    pk+1=pk+2△y               当pk<0

中点直线的公式和Bresham一样。

并行直线算法

前面讨论的直线生成算法顺序地生成象素点。对于并行计算机，可以将这样的顺序执行任务在多个处理器间分配来实现直线的并行生成。 假设有np个处理器，对于Bresenham直线算法，我们可将直线分成np段，然后在每个处理器上分别计算这些直线段。设直线斜率0<m<1，且左端点坐标(xa,ya)。则两个相邻直线段的开始x坐标的距离：

例：设△x=15，4个处理器，则每段直线段长度4，每直线段的起始x坐标xa，xa+4，xa+8，xa+12。

要应用Bresenham直线算法，还必须知道每段直线段的起始y坐标和决策参数的初始值。

知道△xp，则△yp =m△xp (3-17)

第k段直线段的起始y坐标:

     yk=ya+round(k△yp)               (3-18)

第k段直线段的初始决策参数:

pk=(k△xp)(2 △y)-round(k△yp) (2 △x)+2 △y- △x (3-19)

帧缓冲器装载

用光栅显示系统进行直线段和其它物体扫描转换显示时，必须计算帧缓冲器的位置前面，我们已经假设由setpixel程序来完成，它将像素的亮度存储到帧缓冲器矩阵中对应位置，而扫描转换算法以连续的单位间隔生成像素位置.因而，就可以用增量方法来计算帧缓冲器地址 。

圆弧生成算法

由于圆是图形和图像中常使用的元素，因此在大多数图形软件中都包含了生成圆和圆弧的过程。也会提供一个既能显示圆曲线，又能显示椭圆曲线的过程。

• 直角坐标法
• 极坐标法
• 折线逼近法
• Bresenham算法
• 中点圆算法

直角坐标法

缺点：计算量大，且画出的像素位置的距离是不一致的。

考虑到圆的对称性，可先计算1/8圆，再计算其余的7/8圆。

在计算1/8圆时，根据DDA算法的讨论，当|m|<1时（切线斜率），取x方向步长1，计算y后取整；当|m|>1时，取y方向步长1，计算x后取整。

极坐标法

折线逼近法

圆可以用内接正多边形来逼近。同样，对于曲线也可以用折线段来逼近，当然，折线段的数量越多则越逼近曲线本身，但复杂性就越大。下面我们讨论用折线逼近圆。 假设用n段等长折线段来逼近一段半径R，弧角θ的圆弧，则每段圆弧对应的弧角为δ=θ/n.

误差计算（弧高）

半径越大，弧高的误差得越小，要更多的线段。

代入至少13段。

3.4.4 中点圆算法

像在光栅画线算法中一样，以单位间隔取样并在每个步长中确定离指定圆最近的像素位置。

对于给定半径r和圆心(xc,yc)，可先给出计算中心在原点(0,0)圆的像素位置的算法，然后通过平移使每个计算出的(x,y)移动到其适当的屏幕位置。

看中点的f（圆内圆外判断函数）， <0在园内则上面的点离边界近一点，选上面的，>0选下面的，

递归表达式

中点圆算法汇总

求解步骤

中点画圆算法代码实现

3.4.5 Bresenham圆算法

精华

3.5.1 椭圆

精华

3.6区域填充

3.6.1扫描线多边形填充

如何确定边界点呢，只要这个点两边的线在同一侧，就共享，否则不共享，画的时候之画奇偶之间的线。

3.6.2 内外测试

奇偶规则，奇数为内部

非零环绕数

3.6.3 边界填充

四连通递归填充

递归出问题

3.6.4 种子填充