CG第3章_图形生成算法.pptVIP

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