[工学]第4章1 基本光栅图形生成算法.ppt

第4章 基本光栅图形生成算法 4.1 直线生成算法 图形的扫描转换或光栅化 生成直线（段）的方法 4.1.1 生成直线的DDA算法 一、算法思想 数字微分法(DDA)的本质用数值方法解微分方程,通过同时对 和 各增加一个小增量,计算下一步的 , 值 当ΔX ΔY0,即直线斜率小于1，应使x方向每次 增加1，y方向最多增加1，此时取Δt=1/ΔX; 当ΔYΔX0,即直线斜率大于1，应使y方向每次增加1,x方向每次最多增加1,此时应取Δt=1/ΔY; 二、DDA算法程序 void dda(int x1,int y1,int x2,int y2) //直线DDA { int k,i; float x, y, dx, dy; k = abs(x2-x1); if (abs(y2-y1)k) k = abs(y2-y1); dx = float(x2-x1)/k; dy = float(y2-y1)/k; x=float(x1); y=float(y1); for (i=0;ik;i++){ gl_Point(int(x+0.5), int(y+0.5)); x = x+dx; y = y+dy; } }// end DDA 利用数值微分法判断逼近点的位置 为快速很好地求出表示直线的像素,采用参数方程的表达形式 为了提高速度,用等步长来计算直线上的点 DDA算法是一个增量算法 在第一象限内用简单的DDA算法 考虑从(0,0)到(5,5)的直线段的生成 再从(0,0)到(5,2)生成一直线段 4.1.2 正负法 这里只考虑直线斜率小于1的情况 d0，Q在M上方，取PT为下一像素点 由于 在直线上，故 。因此，设第一个像 素取 ,则由 4.1.3 Bresnham算法 令m=△Y/△X, 考虑0≤m≤1 的情况。 第i+1个点只能在C和D中选 ε(xi+2)= yi+2–yi+1, r–0.5 = yi+1+m–yi+1, r–0.5 m=(double)dy/(double)dx； e = m–0.5； for(i=0;idx;i++) { gl_Point(x,y); if(e=0){ y=y+1； e=e–1; } x=x+1；e=e+m; } 其中dy=ye–ys，dx=xe–xs。 4.1.4 改进后的Bresenham 算法 基本原理：每次循环绘制两个象素，也称为二步法。 设0≤m≤1,在x方向每增加两个单元，共有四种绘制模式 由ε(xi+2)=yi+2–yi,r –0.5,可得下面的递推公式 一般情况的讨论 当直线斜率m的 绝对值很小时，同一像素行上可以连续出现很多个表示直线的像素点，每循环一次有可能同时填充多个像素 4.2 圆弧生成算法 4.2.1 正负法 设圆的圆心在(0,0),半径为R,则圆的方程为 x0=0，y0=R，设已求得 二、计算 现由 4.2.3 Bresenham 生成圆弧的算法 假设圆心(0,0)为原点 选点的判别式d 令D(P)=(x2+y2)-R2 选点的判别式d 令D(P)=(x2+y2)-R2 di递推公式 4.2.4 圆弧的离散生成 前面的算法对于生成完整的或者四分之一或者八分之一的圆弧都是很方便和快速的，但是对于生成任意的圆弧，前面的算法就不是很方便。 设圆的圆心为c(0,0),半径为R 内接正多边形的递推公式 椭圆生成的中点算法 基本思想:将圆的中点法推广 上半部分绘制: 算法具体实现: 初始条件： (x,y)=(0，b),顺时针 椭圆弧的离散生成 该椭圆的参数方程为 当di0时,Hi被选中,这时 当di≥0时,Li被选中,这时 二、算法程序 x0=0, y0=R d1 =3–2*R 当di0时 di+1=di+ 4xi-1+6 xi= xi-1+1 当di≥0时 di+1=di+4(xi-1-yi-1)+10 xi= xi-1+1，yi= yi-1-1 void bresenham_arc(int R){ int x,y,d; x=0; y=R; d=3-2*R; while(xy){ gl_Point(x,y); if (d0) d=d+4*x+6; else{ d=d+4*(x-y)+10; y=y-1; } x=x+1; } if(x==y) gl_Point(x,y); } 基本思想：就是将整个圆弧等分成一段段的短直线，用这些短直线形成的折线来逼近圆弧，允许的误差范围内，可以用显示折线代替显