印刷图像及图形处理实验参考生成

印刷图像及图形处理PrintingImageandGraphProcessing主讲：钟云飞第三章图形处理的基本理论3.1二维输出图元及其属性3.2多边形的扫描转换及区域填充（X）3.3几何变换3.4曲线曲面造型知识点：熟悉掌握计算机图形学的基本概念，计算机图形算法基础知识，了解图形变换基础类型，了解计算机对曲线与曲面处理的工作原理。重点：计算机图形学的基本概念。难点：计算机图形算法。

3.1二维输出图元及其属性如何在指定的输出设备上根据坐标描述构造基本二维几何图形（点、直线、圆、椭圆、多边形域、像素数组、字符串及其相关属性等）提出问题直线生成算法圆弧生成算法椭圆生成算法其它输出图元的生成输出图元的属性字符的生成本章内容主要内容学习目标深入认识图形函数包功能，了解函数是如何实现的，从而可改进图形函数以适应某些特殊的应用需求。开发和改进图形技术，发展网络图形应用，开发更快的实时性更强的图形显示。掌握直线、圆、椭圆的生成算法熟悉输出图元的属性控制、字符的生成学习目标图形设计中最基本的图形元素是点、直线、圆、曲线。任何复杂的图形均可看成是点和直线组成。本质上，物体的形状和颜色可用像素矩阵或直线段和多边形填充区域等基本几何结构来描述。通常，图形编程软件包提供使用输出图元的基本几何结构来描述场景和将输出图元组合成更复杂结构的功能。点和直线段是最简单的几何成分。一、点和直线在CRT上，点的显示是通过开关电子枪，使电子束打击在屏幕上的某一位置发光。电子束的定位取决于采用的显示技术。

a.在向量显示系统中，画点命令存放在显示列表中，而坐标位置被转换为偏转线圈上的电压以使电子束定位在指定的屏幕位置上。

b.在黑白光栅显示系统中，通过设置帧缓冲区中对应屏幕位置的位的值为1来显示点，这样，当电子束扫描过水平扫描线时，如遇到帧缓冲区中值为1时，就发射电子打击屏幕，产生亮点。对于RGB系统，颜色码随帧缓存加载，以便能显示彩色点。画直线通过计算两端点间的中间点来画直线。像向量笔、向量显示器这样的模拟输出设备能输出光滑的直线。数字设备画直线是通过画直线两个端点间的各个离散的点来完成。每个分散的点的位置通过直线方程来计算。对于光栅显示系统，直线颜色装载在相应象素位置的帧缓存中。屏幕坐标只能为整数，因此，画点的位置只能近似实际直线上点的位置。例如计算的点的位置(10.48,20.51)近似为(10,21)。这样画出的直线会出现锯齿样，在低分辨率的显示系统上尤其明显。通过调整显示点的亮度可以减轻锯齿影响，无法消除。点的坐标 点在屏幕上的位置坐标用像素为单位，点的像素坐标只能是整数。 而理论上的点的坐标根据直线方程可以为任何实数，而点的像素坐标受设备坐标系的制约，只能为整数。本章将讨论光栅系统上设备级图元生成算法，物体坐标用整数的设备坐标指定。目前我们假定象素位置根据水平扫描线和垂直扫描线的交叉定义，如图。装载指定位置象素的颜色到帧缓存用函数：setPixel(x,y)或setPixel(x,y,color)读取指定位置象素的颜色用函数：

getPixel(x,y)0123453210光栅扫描转换的定义 根据图形的几何描述,确定在二维的像素矩阵上那些像素正好在图形上或最靠近图形,这一过程就称为光栅扫描转换。评价光栅扫描转换算法优劣的标准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)

对于任何沿直线给定的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受象素间距限制。即需要在直线上不同的位置取样，并在每个样本点上取最接近直线的点。如图:xaxb二、常用直线生成算法.1.1DDA算法.1.2Bresenham直线算法.1.3中点直线算法.1.4并行直线算法DDA(digitaldifferentialanalyzer)方法是利用方程(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.1DDA算法对于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）也可用于计算负斜率的线段的像素位置。一般地： 画直线的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,yk+1=yk-1/m;ya>ybDDA算法的C实现#defineRound(a)((int)(a+0.5))voidlineDDA(intxa,intya,intxb,intyb){intdx=xb-xa,dy=yb-ya,steps,k;floatxIncrement,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);}}分析从(0,0)到(20,10)的直线段和从(20,10)到(0,0)的直线DDA算法的缺点:a.计算量大(取整操作和浮点运算)b.效率低，速度慢

c.误差累计，造成画长直线时点逐渐偏离理论点.1.2Bresenham直线算法它是由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)?其位置如图：XkYkXk+1Yk+1ABC由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则：

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+cpk+1=pk+2△y-2△x(yk+1-yk)p0=2△y-△xBresenham的算法表示(适用于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<00≤m≤1,且xa<xb的Bresenham画线算法步骤：1.输入线的两个端点，左端点存储在(x0,y0)中；2.将(x0,y0)装入帧缓冲器，画出第一个点；3.计算常量△x，△y，2△y和2△y-2△x，并得到决策参数的第一个值：p0=2△y-△x4.从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)voidlineBres(intxa,intya,intxb,intyb){intdx=xb-xa,dy=yb-ya;intp=2*dy-dx;inttwoDy=2*dy,twoDyDx=2*(dy-dx);intx,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);}}例:分析从(0,0)到(20,10)的直线段051015200510思考：请给出任意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>ybBresenham的算法表示(适用于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.1.3中点直线算法一种精确而有效的光栅线段生成算法,可用于直线、圆(圆弧)和其它曲线的生成。考虑直线斜率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)?其位置如图：XkYkXk+1Yk+1ABC由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+cpk+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-△xxk+1=xk+1yk+1=yk+1，pk+1=pk+2(△y-△x)当pk≥0yk+1=yk，pk+1=pk+2△y当pk<0.1.4并行直线算法前面讨论的直线生成算法顺序地生成象素点。对于并行计算机，可以将这样的顺序执行任务在多个处理器间分配来实现直线的并行生成。假设有np个处理器，对于Bresenham直线算法，我们可将直线分成np段，然后在每个处理器上分别计算这些直线段。设直线斜率0<m<1，且左端点坐标(xa,ya)。则两个相邻直线段的开始x坐标的距离：

xp=

(x+np-1)/np整数除法

(3-15)直线段从0,1,2,…,np-1编号，第k段的起始x坐标：

xk=xa+kxp(3-16)例：设x=15，4个处理器，则每段直线段长度4，每直线段的起始x坐标xa，xa+4，xa+8，xa+12。要应用Bresenham直线算法，还必须知道每段直线段的起始y坐标和决策参数的初始值。知道xp，则yp=mxp(3-17)第k段直线段的起始y坐标:yk=ya+round(kyp)(3-18)第k段直线段的初始决策参数:pk=(kxp)(2y)-round(kyp)(2x)+2y-x三、帧缓冲器装载用光栅显示系统进行直线段和其它物体扫描转换显示时，必须计算帧缓冲器的位置前面，我们已经假设由setpixel程序来完成，它将像素的亮度存储到帧缓冲器矩阵中对应位置，而扫描转换算法以连续的单位间隔生成像素位置.因而，就可以用增量方法来计算帧缓冲器地址假设帧缓冲器地址是以行序为主序来编址，且像素位置以屏幕左下方为(0,0)变化到屏幕右上方(xmax,ymax)。对于像素位置(x,y)的帧缓冲器位地址可计算为：

addr(x,y)=addr(0,0)+y(xmax+1)+x沿扫描线移动，像素(x+1,y)处的帧缓冲器地址可从位置(x,y)的地址做偏移来计算：

addr(x+1,y)=addr(x,y)+1从(x,y)对角地跳到下一条扫描线，(x+1,y+1)的帧缓冲器地址的计算公式为：

addr(x+1,y+1)=addr(x,y)+xmax+2上述的计算公式只针对黑白系统而言，对于能显示彩色的显示系统，因为屏幕上每个像素在存储器中占用多个bit，因此，在用上述的计算公式计算特定点在帧缓冲器中的地址时还必须考虑像素宽度。例如8/16/24/32bit。四、圆弧生成算法由于圆是图形和图像中常使用的元素，因此在大多数图形软件中都包含了生成圆和圆弧的过程。也会提供一个既能显示圆曲线，又能显示椭圆曲线的过程。.4.1直角坐标法.4.2极坐标法.4.3折线逼近法.4.4中点圆算法.4.5Bresenham圆算法.4.1直角坐标法圆被定义为所有离一中心位置(xc,yc)距离为给定值r的点集。可用方程表示如下：

(x-xc)2+(y-yc)2=r2为简便起见，我们讨论圆心在原点，半径为r的圆：

x2+y2=r2可以沿x轴从-r到r，以单位步长计算对应的y值来得到圆周上每点的位置：

y=±(r2-x2)1/2缺点：计算量大，且画出的像素位置的距离是不一致的。考虑到圆的对称性，可先计算1/8圆，再计算其余的7/8圆。在计算1/8圆时，根据DDA算法的讨论，当|m|<1时，取x方向步长1，计算y后取整；当|m|>1时，取y方向步长1，计算x后取整。.4.2极坐标法使用极坐标法表示圆：

x=rcosθ y=rsinθ 0≤θ≤360但是，算法的计算量仍然很大。更有效的圆算法是如Bresenham画线算法一样以决策参数的增量计算为基础，仅包括简单的整数操作。.4.3折线逼近法圆可以用内接正多边形来逼近。同样，对于曲线也可以用折线段来逼近，当然，折线段的数量越多则越逼近曲线本身，但复杂性就越大。下面我们讨论用折线逼近圆。假设用n段等长折线段来逼近一段半径R，弧角θ的圆弧，则每段圆弧对应的弧角为δ=θ/n.误差计算a.弧长-弦长=Rδ-Rcos(δ/n)不容易计算。b.e=半径-|OA|=R[1-cos(δ/2)]≈2Rsin2(δ/4)≈Rδ2/8.

即:e=Rδ2/8

为了使误差e≤ε,则：

n≥θ*[R/(8ε)]1/2

表明，对于R越大，要求的误差越小，则所需要的折线段就越多例如：假设圆弧的半径R=256个像素，圆弧的角度θ=π,若要求误差不超过两个像素，则最少需要多少段折线段来逼近该圆弧？.4.4中点圆算法像在光栅画线算法中一样，以单位间隔取样并在每个步长中确定离指定圆最近的像素位置。对于给定半径r和圆心(xc,yc)，可先给出计算中心在原点(0,0)圆的像素位置的算法，然后通过平移使每个计算出的(x,y)移动到其适当的屏幕位置。同样，只考虑1/8圆，x从０到R/21/2结束.为了应用中点圆算法，定义一个圆函数：

fcircle(x,y)=x2+y2-r2

则任何点(x,y)的相对位置可由对圆函数符合的检测来决定: <0(x,y)位于圆边界内fcircle(x,y)=0(x,y)位于圆边界上

>0(x,y)位于圆边界外假设用该算法计算出第k个点(xk,yk),下一步需要决定像素位置是A(xk+1,yk),B(xk+1,yk-1)，其中xk+1=xk+1 A,B的中点M(xk+1,yk-0.5)在M处决策参数：

pk=fcircle(xk+1,yk-0.5)=xk+12+(yk-0.5)2-r2

当pk<0，这个中点M在圆内，扫描线yk上的像素(xk+1,yk)更接近于圆边界，则下一点应取右边的点A(xk+1,yk)。否则，中点M位于圆外或在边界上，我们选择扫描线yk-1上的像素B(xk+1,yk-1)pk+1=(xk+1+1)2+(yk+1-0.5)2-r2递归表达式：

pk+1=pk+2xk+1+(y2k+1-y2k)-(yk+1-yk)+1

其中:yk+1是yk(pk<0)或是yk-1(pk≥0)，这取决于pk的符号。圆在起始位置(x0,y0)=(0,r)处求值就可得到初始决策参数：

p0=fcircle(1,r-0.5)=5/4–r中点圆算法的算法表示：

p0=5/4–r xk+1=xk+1 yk+1=yk，pk+1=pk+2xk+1+1，当pk<0yk+1=yk-1，pk+1=pk+2xk+1+1-2yk+1，当pk≥0对于2xk+1和2yk+1本身又是一个增量表达式，2xk+1增量始终为2，而2yk+1增量为0(当pk<0)或-2(当pk≥0)，在起始位置(x0,y0)=(0,r)，2xk+1和2yk+1的初始值分别为0和2r。中点画圆算法的步骤：

1.输入圆半径r和圆心(xc,yc),并得到圆心在原点的圆周上的第一点为:(x0,y0)=(0,r)2.计算决策参数的初始值：

p0=5/4–r3.在每个xk位置处，从k=0开始，完成下列检测：假如pk<0，中心在(0,0)的圆的下一个点为(xk+1,yk)，且

pk+1=pk+2xk+1+1

否则，圆的下一个点为(xk+1,yk-1)，且

pk+1=pk+2xk+1+1-2yk+1

其中：2xk+1=2xk+1，2yk+1=2yk-24.确定在其它7个8分圆中的对称点

5.将每个计算出的像素位置(x,y)移动到中心在(xc,yc)的圆路径上，并画坐标值：

x=xc+xy=yc+y6.重复步骤3到5，直至x≥y.中点圆算法的C实现：voidcircleMidpoint(intxCenter,intyCenter,intradius){intx=0;inty=radius;intp=1-radius;voidcirclePlotPoints(int,int,int,int);circlePlotPoints(xCenter,yCenter,x,y);while(x<y){x++if(p<0)p+=2*x+1;else{y--;p+=2*(x-y)+1;}circlePlotPoints(xCenter,yCenter,x,y);}}voidcirclePlotPoints(intxCenter,intyCenter,intx,inty){setpixel(xCenter+x,yCenter+y);setpixel(xCenter-x,yCenter+y);setpixel(xCenter+x,yCenter-y);setpixel(xCenter-x,yCenter-y);setpixel(xCenter+y,yCenter+x);setpixel(xCenter-y,yCenter+x);setpixel(xCenter+y,yCenter-x);setpixel(xCenter-y,yCenter-x);}Ex.半径为20个像素的1/8圆.4.5Bresenham圆算法与Bresenham直线生成算法一样，其基本思想：利用判别变量来判断选择最近的像素，判别变量仅用加减和移位就可计算出来同样，只考虑1/8圆，x从０到R/21/2结束假设用该算法计算出第k个点(xk,yk),下一步需要决定像素位置是A(xk+1,yk), B(xk+1,yk-1)，其中xk+1=xk+1根据理论坐标点与A,B的距离大小选择A或B. da=yk2-y2=yk2-r2+xk+12

db=y2-(yk-1)2=r2-xk+12-(yk-1)2

∆d=da-db≥0，则下一像素取B(xk+1,yk)∆d<0，则下一像素取A(xk+1,yk-1)决策参数：

pk=∆d=2xk+12+(yk-1)2+yk2-2r2

pk+1=2(xk+1+1)2+(yk+1-1)2+yk+12-2r2

所以：

pk+1=pk+4xk+6+2(yk+12-yk2)-2(yk+1-yk)初始条件 起始点(x0,y0)＝(0,r)带入上式：

p0=3-2rBresenham圆弧算法可表示为：

p0=3-2r xk+1=xk+1 yk+1=yk-1，pk+1=pk+4(xk-yk)+10当pk≥０

yk+1=yk，pk+1=pk+4xk+6，当pk<０Bresenham圆弧算法的C实现voidcircleBres(intxCenter,intyCenter,intradius){intx=0,y=radius,p=3-2*radius;voidcirclePlotPoints(int,int,int,int);circlePlotPoints(xCenter,yCenter,x,y);while(x<y){if(p<0)p+=(4*x+6);else{p+=(4*(x-y)+10);y--;}x++;circlePlotPoints(xCenter,yCenter,x,y);}}半径为20个像素的1/8圆五、椭圆生成算法椭圆曲线的生成考虑长轴和短轴尺寸不同，可通过修改画圆程序来实现.5.1椭圆的特征.5.2中点椭圆算法.5.1椭圆的特征椭圆被定义为到两个定点(焦点)的距离之和等于常数的点的集合。椭圆上任意点p(x,y)到两个焦点的距离记为d1和d2，那么，椭圆方程可表示为：d1+d2=常数设两个焦点坐标F1=(x1,y1)和F2=(x2,y2)来表示的椭圆方程：

[(x-x1)2+(y-y1)2]1/2+[(x-x2)2+(y-y2)2]1/2=常数改写椭圆方程，则通用椭圆方程：

Ax2+By2+Cxy+Dx+Ey+F=0标准位置的椭圆：长轴和短轴与X和Y轴平行，椭圆中心可在(xc,yc)。标准位置椭圆方程：

[(x-xc)/rx]2+[(y-yc)/ry]2=1

其中：rx

和ry分别为长半轴和短半轴。极坐标表示：

x=xc+rxcosθ,y=yc+rysinθ标准位置的椭圆其在四分象限是对称的，因此我们只需要计算一个四分象限的椭圆曲线位置，然后根据对称性得到其余的部分。.5.2中点椭圆算法基本思想：计算椭圆中心在(0,0)的标准位置椭圆曲线的第一分象限的曲线部分的位置像素(x,y)，然后将点变换到椭圆中心在(xc,yc)。.5.2中点椭圆算法基本思想：计算椭圆中心在(0,0)的标准位置椭圆曲线的第一分象限的曲线部分的位置像素(x,y)，然后将点变换到椭圆中心在(xc,yc)。.5.2中点椭圆算法基本思想：计算椭圆中心在(0,0)的标准位置椭圆曲线的第一分象限的曲线部分的位置像素(x,y)，然后将点变换到椭圆中心在(xc,yc)。.5.2中点椭圆算法根据前面DDA算法的讨论，当|m|≤1时，取x方向单位步长(1或-1)，相反，取y方向单位步长(1或-1)。因此，对于第一分象限的椭圆曲线分成两部分：一部分曲线的斜率绝对值小于1和斜率绝对值大于1。并分别对两段曲线分别取x方向步长和y方向取步长.这里可选择(0,ry)或(rx,0)作为起点开始算法。以从(0,ry)开始从左到右进行。椭圆函数作为决策参数：

fellipse(x,y)=ry2x2+rx2y2-rx2ry2

该函数具有如下特性：

<0(x,y)位于椭圆边界内fellipse(x,y)=0(x,y)位于椭圆边界上

>0(x,y)位于椭圆边界外椭圆函数fellipse(x,y)作为中点椭圆算法的决策参数。在每个取样位置，按照椭圆函数在沿椭圆轨迹两个候选像素点的中点求值的符号选择下一个像素从(0,ry)开始，在x方向取单位步长1直到斜率变为≥-1。椭圆的斜率：

dy/dx=-ry2x/rx2y两段曲线采用不同的算法的分界点：

2ry2x=2rx2y对于第1段曲线设用该算法计算出点(xk,yk)，下一个点(xk+1,yk+1)为A(xk+1,yk)或B(xk+1,yk-1)，即右边点或右下点。根据如下决策参数符号判断： p1k=fellipse(xk+1,yk-0.5)=ry2(xk+1)2+rx2(yk-0.5)2-rx2ry2

下一点的判断：当p1k<0，取A(xk+1,yk)，

yk+1=yk

当p1k≥0，取B(xk+1,yk-1)，

yk+1=yk-1其中xk+1=xk+1递归表达式：

p1k+1=p1k+2ry2(xk+1)+ry2+rx2[(yk+1-0.5)2-(yk-0.5)2]初始决策参数：将(x0,y0)=(0,ry)带入:p10=fellipse(1,ry-0.5)=ry2-rx2ry+rx2/4该椭圆第一分象限的第一部分椭圆曲线的中点算法表示：

p10=ry2-rx2ry+rx2/4xk+1=xk+1yk+1=yk

，p1k+1=p1k+2ry2xk+1+ry2

当p1k<0yk+1=yk-1，p1k+1=p1k+2ry2xk+1+ry2-2rx2yk+1

当p1k≥0决策参数增量=2ry2xk+1+ry2当p1k<02ry2xk+1+ry2-2rx2yk+1当p1k≥0对于2ry2xk+1和2rx2yk+1本身又是一个增量表达式，2ry2xk+1增量始终为2ry2，而2rx2yk+1增量为0(当p1k<0)或-2rx2(当p1k≥0)，在起始位置(x0,y0)=(0,ry)，2ry2xk+1和2rx2yk+1的初始值分别为0和2rx2ry。然而对于第一分象限的第2段曲线，取y方向单位步长。在每一步，计算决策参数时取两个候选水平像素的中点。设前一步取(xk,yk)，下一个点(xk+1,yk+1)的选择：B(xk,yk-1)或A(xk+1,yk-1)，即下边点或右下点。M(xk+0/5,yk-1)为AB的中点。根据如下决策参数符号判断：

p2k=fellipse(xk+0.5,yk-1)=ry2(xk+0.5)2+rx2(yk-1)2-rx2ry2

取点的判断：

p2k≤0，取(xk+1,yk-1),(xk+1,yk+1)=(xk+1,yk-1),

即右下点Ap2k>0，取(xk,yk-1),(xk+1,yk+1)=(xk,yk-1),

即下边点B递归表达式：

p2k+1=p2k-2rx2(yk-1)+rx2+ry2[(xk+1+0.5)2-(xk+0.5)2]当从第一分象限椭圆的第1段曲线进入第2段曲线时，采用p2k作为决策参数，此时，p2k的初始点为第段曲线的最后计算点，设为(x0,y0)。则第二部分曲线的初始决策参数:p20=fellipse(x0+0.5,y0-1)=ry2(x0+0.5)2+rx2(y0-1)2-rx2ry2

该椭圆第一分象限的第2段椭圆曲线的中点算法表示：

p20=ry2(x0+0.5)2+rx2(y0-1)2-rx2ry2yk+1=yk-1xk+1=xk，p2k+1=p2k-2rx2yk+1+rx2,当p2k>0xk+1=xk+1，p2k+1=p2k-rx2yk+1+rx2+2ry2xk+1

当p2k≤0决策参数增量=-2rx2yk+1+rx2当p2k>0-2rx2yk+1+rx2+2ry2xk+1当p2k≤0对于2rx2yk+1和2ry2xk+1本身又是一个增量表达式，2rx2yk+1增量始终为-2rx2，而2ry2xk+1增量为0(当p2k>0)或2ry2(当p2k≤0)，在起始位置(x0,y0)，2rx2yk+1和2ry2xk+1的初始值分别为2rx2y0和2ry2x0。中点椭圆算法步骤：1.输入rx,ry和椭圆中心(xc,yc)，并得到中心在原点的椭圆上的第一个点。2.计算第一分象限的第1段椭圆曲线的决策参数的初值：

p10=ry2-rx2ry+rx2/43.在第1段曲线的每个xk处，从k=0开始，完成下列测试：假如当p1k<0，则下一个点为(xk+1,yk+1)=(xk+1,yk)，且：p1k+1=p1k+2ry2(xk+1)+ry2，否则，下一个点为(xk+1,yk+1)=(xk+1,yk-1)，且：p1k+1=p1k+2ry2(xk+1)+ry2-2rx2(yk-1)。且循环至2ry2x≥2rx2y，循环结束得到最后点(x0,y0)。4.使用第1段曲线计算最后得到的点(x0,y0)，来计算第2段曲线的初始决策参数：

p20=ry2(x0+0.5)2+rx2(y0-1)2-rx2ry25.在第2段曲线的每个yk处，从k=0开始，完成下列检测：假如p2k>0，则下一个点为(xk+1,yk+1)=(xk,yk-1)，且p2k+1=p2k-2rx2(yk-1)+rx2，否则下一个点为(xk+1,yk+1)=(xk+1,yk-1)，且p2k+1=p2k-2rx2(yk-1)+rx2+2ry2(xk+1)，且循环至2rx2y=0即y=0。6.确定其它三个分象限中对称的点。7.将每个计算出像素位置(x,y)移到中心在(xc,yc)的椭圆轨迹上，并按坐标画点：x=x+xc，y=y+yc。中点椭圆算法的C实现#defineROUND(a)((int)(a+0.5))voidellipseMidpoint(intxCenter,intyCenter,intRx,intRy){intRx2=Rx*Rx,Ry2=Ry*Ry;inttwoRx2=2*Rx2,twoRy2=2*Ry2;intp,x=0,y=Ry,px=0,py=twoRx2*y；

voidellipsePlotPoints(int,int,int,int);ellipsePlotPoints(xCenter,yCenter,x,y)；

p=ROUND(Ry2-(Rx2*Ry)+(0.25*Rx2));

while(px<py){x++;px+=twoRy2;if(p<0)p+=Ry2+px;else{y--,py-=twoRx2;p+=Ry2+px-py;}ellipsePlotPoints(xCenter,yCenter,x,y);}/*section2*/p=ROUND(Ry2*(x+0.5)*(x+0.5)+Rx2*(y-1)*(y-1)-Rx2*Ry2);while(y>0){y--;py-=twoRx2;if(p>0)p+=Rx2-py;else{x++;px+=twoRy2;p+=Rx2-py+px;}ellipsePlotPoints(xCenter,yCenter,x,y);}}voidellipseMidPoints(intxCenter,intyCenter,intx,inty){setpixel(xCenter+x,yCenter+y);setpixel(xCenter-x,yCenter+y);setpixel(xCenter+x,yCenter-y);setpixel(xCenter-x,yCenter-y);}思考：1.由于第2段曲线的初始决策参数依赖于第1段曲线最后计算的点，因此两个部分不能同时进行，如何修改一下算法，使两部分曲线的计算可同时进行。2.对于非标准位置(长/短半轴不与坐标轴重合)的椭圆，如何实现？六、其它输出图元的生成点、线、圆是图形设计中最基本的元素，此外，设计中还需要其它图元，如曲线、文字和符号常用曲线：正弦函数曲线、指数函数曲线、多项式函数曲线、概率分布函数曲线及样条函数曲线等。曲线生成与圆和椭圆相似。思考：如何绘制曲线，如正弦函数曲线。七、输出图元的属性.7.1直线属性.7.2曲线属性.7.3颜色和灰度等级.7.4填充区域的属性通常，任何影响图元显示方法的参数被称为属性参数。如颜色、大小等属性是确定图元的基本特性；其它则指出在特定条件下怎样显示图元。如三维视图的深度信息以及交互式对象选择程序所需的可见性或可检测性。这里我们仅考虑哪些控制图元基本显示特性的属性，而不考虑特定条件。如线段可以是点线或虚线、粗线或细线以及蓝色或其它颜色等。区域可用一种颜色或多色图案填充。文本可从左到右阅读方式显示，沿屏幕对角线倾斜或按垂直列向显示.7.1直线属性直线段的基本属性线型宽度颜色在一些软件包中，线用可选择的笔或刷来显示。下面，考虑怎样修改画线程序来实现各种指定属性。线型线型属性可能包括实线、虚线和点线等。我们通过设置沿线路径显示的实线段的长度和间距来修改画线算法，以生成各种类型的线。虚线可通过在实线段间插入与实线段等长的空白段来显示；画线的长度和空白段长度常作为用户的选项来指定。点线，可通过生成很短的画线和等于或大于画线大小的空白段来显示对于各种画线、点线和点画线，用像素掩模来指定实线段和空白段的长度。例如，掩模1111000可表示画线长度为四个像素和中间空白段为3个像素的虚线。用固定数目的像素画线会产生如图所示的在不同方向不同长度的线段。为此，可按线的斜率来调整实心段和空白段的像素数目。另一个保持画线等长的方法是将画线看作为单独的线段，将每条画线的端点坐标定位后，调用沿画线路径计算像素位置的画线程序。线宽线宽选择的实现取决于输出设备的能力。在视频显示器上的粗线可以用相邻的平行线来显示。在光栅实现中，标准线宽是用像Bresenham算法那样在每个取样位置处用一个像素来生成。其它宽度是作为标准线的正整数倍通过沿相邻平行线路径画额外的像素而显示的。对于斜率绝对值小于1的线，可修改画线程序，通过在沿线的每个x位置画像素的垂直段来显示粗线。每段的像素数目等于线宽的整数值。在图中，我们通过在原线段路径之上生成一条平行线而画出了双倍线宽的线段。在每个位置x处，计算对应的y坐标，并使用屏幕坐标(x,y)和(x,y+1)画像素。通过交替地在单线宽度的上下画像素就可以显示线宽≥3的粗线对于斜率绝对值大于1的粗线，可以在水平段交替地画线段路径左边和右边像素形成粗线，如图，其线宽为4，用水平段绘制。尽管通过绘制水平段或垂直段能快速地生成粗线，但线的显示宽度(垂直于线段路径测量)仍取决于线的斜率，45o线的显示线宽只有垂直线或水平线的用水平段或垂直段实现宽度选择的另一个问题是：不管斜率多少，所生成线段的端点是水平或垂直的。这对于较粗的线的影响更突出。我们可以通过添加“线帽”来调整线端的形状以给出较好的外观，如图。线帽有方帽、圆帽和突方帽。方帽通过调整所构成平行线的端点位置，使粗线的显示具有垂直于线段路径的正方形端点。假如指定线的斜率m，则粗线的方端的斜率-1/m。生成粗线的其它方法包括将显示线段看作填充长方形，或用选定的笔或刷样式来生成线段。生成粗折线需要一些额外的处理。通常，显示单根折线段所用的方法不能生成光滑连接的折线段。我们可通过在线段端点进行额外处理来生成光滑连接的粗折线。图显示出了两线段光滑连接的三种可能方法：斜角连接、圆连接和斜切连接。斜角连接通过延伸两条线的外边界直到它们相交来完成。圆连接通过用直径等于线宽的圆弧边界将两线段间连接而成。斜切连接则是通过用方帽和在两线段相交处的三角形间歇中填充来生成颜色当系统提供颜色(或亮度)选择时，给出当前颜色索引的参数被包括在系统属性表中。折线程序以当前颜色显示折线，是通过用setPixel程序将这种颜色设置在帧缓冲器中沿线段路径像素位置处得以实现。颜色选择的数目取决于帧缓冲器中每个像素有效值的数目笔和画刷有些图形软件包中，线可选择笔或刷的方式来显示。选项包括形状、尺寸和式样。如图显示的可能的笔和刷形状。这些形状可以以像素位置数值形式存储在一个像素模板中，在必要时设置到线段路径上。例如图显示的是一个长方形笔的像素模板，用这个模板的中心沿线段路径运动可画出相应宽度的线段通过改变笔或刷的像素模板的尺寸，则使用该模板的笔或刷来生成的线段就可以有不同的宽度.7.2曲线属性曲线属性的参数与直线段相同，我们可用各种颜色、宽度、点划模式和有效的笔或刷选择来显示曲线。采用画线算法来适应属性选择的方法也类似于画直线。如图,显示的一个用模板11100来生成虚线圆弧。可用圆的对称性生成圆的其它部分。如前面讨论的一样，各种宽度的光栅曲线可用水平或垂直像素段来显示，曲线斜率的绝对值小于1，用垂直段；斜率绝对值大于1，用水平段。如图示另一种显示粗曲线的方法是填充两条距离等于预定宽度的平行曲线路径间的区域。可以用指定的曲线路径作为一条边界，并在其内侧或外侧建立第二条边界来实现，然而，这样的粗曲线会发生偏移，因此，通常在曲线路径两侧以预定宽度的一半距离，设置两条边界曲线来保持曲线位置，如图。曲线的笔或刷显示可使用前面直线段中讨论的相同方法来实现。当曲线斜率为1时，用这种长方形笔显示的曲线会比较粗。因此，要显示一致的曲线宽度可通过旋转长方形笔以使其在沿曲线移动时与曲线斜率方向一致，或用圆弧笔来实现.7.3颜色和灰度等级通用光栅扫描系统通常提供较多的颜色，而随机扫描系统最多只能提供几种颜色供选择。颜色选项用0到某一正整数值编码。对于CRT显示器，这些颜色码被转换成电子束的强度等级。对于彩色绘图仪，这些编码将控制喷墨或选笔.颜色信息可以用两种方法存储在帧缓冲器中：1.将颜色码直接存储在帧缓冲器中.2.把颜色码放在一个独立的表(调色板)中并用像素值作为这个表的索引.利用直接存储策略，一旦在应用程序中指定某种颜色编码，就在帧缓冲器中为要以那种颜色显示的输出图元的每个组成像素设置为对应的二进制值.例如，每个像素占3位存储器时，它提供了最小数目的彩色颜色数，三位位置的每一位用来控制RGB显示器中对应电子枪的亮度等级(开或关)，给缓冲器中每个像素增加位数将使可选择的颜色数量增加，假如每个像素6位，则每支电子枪用2位，这允许三支电子枪的每一支具有四种不同的亮度，对每个屏幕像素共有64个有效颜色。对于1024×1024的分辨率，真彩色/全色(每个像素占24位)RGB系统需要帧缓冲器的存储量：1024×1024×24bit=3Mbyte。彩色表是不需要增大帧缓冲器而又扩充颜色能力的一种变换方法颜色表图显示了在彩色查找表中存储颜色值的一种方案。在该表中，帧缓冲器值用作彩色表的索引。在这个例子中，每个像素在帧缓冲器中占用8位，可引用表中256个表位置的任何一个，表中的每个表项可用24位来指定RGB颜色。拥有这种特殊查找表的系统，将允许用户从将近1亿7千万种颜色的调色表中选择任意256种颜色同时显示。与真彩色系统相比，这种方案减少了可以同时显示的颜色数目，但它也将缓冲器的容量需要减少到1M。有些图形系统在帧缓冲器中为每个像素提供9位，允许用户在每次显示中能