计算机图形学课件：第五章基本图形生成算法课件.ppt

第5章 基本图形生成算法 本章要解决的问题 ■如何在指定的输出设备上根据坐标描述构造基本二维几何图形。 图形的生成：在指定的输出设备上，根据坐标描述构造二维几何图形。 图形的扫描转换：在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。 5.1 直线的扫描转换 给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。 ? 要求： 直、端点准确、色泽均匀、速度快等。 ■数值微分法(DDA法) 直线的微分方程： DDA算法原理： ε=1/max(|△x|,|△y|) void DDAline(int x0, int y0, int x1, int y1) { int dx,dy,epsl,k; float x,y,xIncre,yIncre; dx=x1-x0; dy=y1-y0; x=x0; y=y0; if(abs(dx)abs(dy)) epsl=abs(dx); else epsl=abs(dy); xIncre=(float)(dx)/epsl; yIncre=(float)(dy)/epsl; for(k=0;k=epsl;k++) { putpixel((int)(x+0.5),(int)(y+0.5)); x+= xIncre; y+= yIncre; } } ■中点Bresenham算法 该直线方程将平面分为三个区域： 对于直线上的点，F(x,y)=0； 对于直线上方的点，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。否则结束。 void MidBhline(int x0, int y0, int x1, int y1) { int dx,dy,d,UpIncre,DownIncre,x,y,xend; if(x0x1){x=x1;x1=x0;x0=x; y=y1;y1=y0;y0=y;} x=x0; y=y0; dx=x1-x0; dy=y1-y0; d=dx-2*dy; UpIncre=2*dx-2*dy; DownIncre=-2*dy; while(x=x1) { putpixel(x,y); x++; if(d0) { y++; d+= UpIncre; } else d+= DownIncre; } } ■改进的Bresenham算法 假定直线段的0≤k≤1 基本原理： 误差项的计算 d初=0， 每走一步：d=d+k 一旦y方向上走了一步，d=d-1 算法步骤： 1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。 2.计算初始值△x、△y、d=0、x=x0、y=y0。 3.绘制点(x,y)。 4.d更新为d+k，判断d的符号。若d0.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,y)更新为(x+1,y)。 5.当直线没有画完时，重复步骤3和4。否则结束。 改进1：令e=d-0.5 算法步骤为： 1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。 2.计算初始值△x、△y、e=-0.5、x=x0、y=y0。 3.绘制点(x,y)。 4.e更新为e+k，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。 5.当直线没有画完时，重复步骤3和4。否则结束。 改进2：用2e△x来替换e e初=-△x， 每