问题的提出在图形系统部分内容中，我们已经介绍了图形输出设备的工作原理。即无论是画点设备或画线设备，其输出的图线都不是连续的，而是由离散的点或是折线近似地组成。笔式输出设备：图形生成算法就是如何用插补算法生成诸如直线、圆弧和文字等基本图形的方法。点阵输出设备：图形生成算法就是在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。笔式输出设备直线的走步组合圆弧的走步组合点阵输出设备用一系列象素点逼近直线本章主要讨论基本图形的扫描转换问题，包括：（1）直线的生成算法；（2）圆弧的生成算法；（3）规则曲线的生成算法（4）自由曲线的生成算法3.1直线的生成算法3.1.1DDA画线算法直线的微分方程：通常选ε=1/max(|△x|,|△y|),这时ε△x或ε△y将变成单位步长。即在最大位移方向上，每次总是走一步。分两种情况：max(|△x|,|△y|)=|△y|，此时|k|≥1：程序,注意：round(x)=(int)(x+0.5)voidDDAline(intx1,inty1,intx2,inty2){floatdx,dy,k,x,y;dx=x2-x1;dy=y2-y1;k=dy/dx;x=x1;y=y1;for(inti=0;i<=dx;i++){SetPoint(x,int(y+0.5);x+=1;y+=k;}}DDA算法的优.缺点3.1.2Bresenham画线算法2024/10/42024/10/4递推公式：当di≥0时，选Ti，当di<0时，选Si，由于只包含加、减法和左移（乘2）的运算，而且下一个像素点的选择只需检查di的符号，因此Bresenham画线算法很简单，速度也相当快。程序见书P44~45（新版书p68）3.1.3中点Bresenham算法直线上方的点：F(x,y)＞0直线下方的点：F(x,y)＜0基本原理：假定0≤k≤1，x是最大位移方向判别式：误差项的递推d<0：误差项的递推d≥0：初始值d的计算0≤k≤1时中点Bresenham算法的算法步骤为：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、d=0.5-k、x=x0、y=y0；3.绘制点(x,y)。判断d的符号；若d<0，则(x,y)更新为(x+1,y+1)，d更新为d+1-k；否则(x,y)更新为(x+1,y)，d更新为d-k。4.当直线没有画完时，重复步骤3。否则结束。改进：用2d△x代替d1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、d=△x-2△y、x=x0、y=y0。3.绘制点(x,y)。判断d的符号。若d<0，则(x,y)更新为(x+1,y+1)，d更新为d+2△x-2△y；否则(x,y)更新为(x+1,y),d更新为d-2△y。4.当直线没有画完时，重复步骤3。否则结束。3.2生成圆弧的常用算法(y,x)解决问题：343.2.3中点Bresenham画圆2024/10/4当d≤0时，下一点取Pu(xi+1,yi)；当d>0时，下一点取Pd(xi+1,yi-1)。误差项的递推d≤0：d>0：判别式的初始值算法步骤：1.输入圆的半径R。2.计算初始值d=1.25-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d≤0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当x<y时，重复步骤3和4。否则结束。改进：用d-0.25代替d算法步骤：1.输入圆的半径R。2.计算初始值d=1-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d≤0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当x<y时，重复步骤3和4。否则结束。程序voidMidpointCircle(intr,intcolor){intx,y,d;x=0;y=r;d=1-r;while(x<y){SetPixel(x,y,color);if(d<0)d+=2*x+3;else{d+=2*(x-y)+5;y--;}x++;}}3.3规则曲线的生成算法3.3.2椭圆的显示算法对于椭圆上的点，有F(x,y)=0；对于椭圆外的点，F(x,y)>0；对于椭圆内的点，F(x,y)<0。解决问题：以弧上斜率为－1的点作为分界,将第一象限椭圆弧分