第三章 (计算机图形学基本图形算法之一).pptVIP

计算机图形学基础Computer Graphics 赵东保 基本图形元素是指点、直线、圆弧、区域填充和字符等图形元素，这些基本图形元素是生成计算机图形图像的基础。计算机绘图系统就是由这些基本算法命令组合而成的，研究计算机图形学需先从二维图形的生成开始。 直线的扫描转换 确定最佳逼近于该直线的一组象素 按扫描线顺序，对这些象素进行写操作 三个常用算法： 1数值微分法（DDA） 2中点画线法 3Bresenham算法。 直线生成算法的假设前提 像素间均匀网格，整型坐标系，直线段斜率0m1 对m＞1，x、y互换 已知线段端点：P0(x0,y0), P1(x1,y1) 直线方程：y=kx+b {(xi, yi)}, i=0,….n. 浮点数取整 : yi=round(yi)=(int)(yi+0.5) 用到浮点数的乘法、加法和取整运算 思路：选择距离理想直线最近的象素点作为下一个 像素点，已知：线段两端点(x0,y0)，(x1,y1) 直线方程：F(x,y)=ax+by+c=0 a=y0-y1 b=x1-x0 c=x0y1-x1y0 直线上方点： F(x,y)＞0 直线下方点: F(x,y)＜0 构造判别式： d=F(M)=F(Xp+1,Yp+0.5) 由d＞0，d＜0可判定下一个象素 分两种情形考虑再一下个象素的判定： 若d≥0，中点M在直线上方，取正右方象素 P1 (Xp+1,Yp) 再下一个象素的判别式为： d1=F((Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c = d+a d的增量为a 若d＜0，中点M在直线下方，取右上方象素 P2 (Xp+1,Yp+1) 再下一个象素的判别式为： d2=F((Xp+1)+1,(Yp+1)+0.5)= a(Xp+2)+b(Yp+1.5)+c =d+a+b d的增量为a+b d的初始值 d0=F(X0+1,Y0+0.5) =F(X0,Y0)+a+0.5b =a+0.5b 用2d代替d后，d0=2a+b d的增量都是整数 优点： 只有整数运算，不含乘除法 可用硬件实现 void Midpoint Line (int x0,int y0,int x1, int y1,int color) { int a, b, d1, d2, d, x, y； ? a=y0-y1； b=x1-x0；d=2*a+b； ? d1=2*a；d2=2* (a+b)； ? x=x0；y=y0； ? drawpixel(x, y, color); ? while (xx1) ? { if (d0)?? {x++；y++； d+=d2; } ??? else????? {x++； d+=d1;} ??? drawpixel (x, y, color); ? } /* while */ } /* mid PointLine */ F(X,Y)=X2+Y2-R2=0 中点 M=(Xp+1,Yp-0.5) 当F(M)＜0时，M在圆内，P1距离圆弧近，取P1 当F(M)＞0时，M在圆外，P2距离圆弧近，取P2 若 d0, 取P2为下一象素，再下一象素的判别式为 若d=0, 取P1为下一象素，再下一象素的判别式为 初始象素是（0,R），判别式d的初值为 MidPointCircle(int r int color) { int x,y; ? float d; ? x=0; y=r; d=1.25-r; ? circlepoints (x,y,color); ? while(x=y) { if(d0)?? d+=2*x+3; ?? else?? { d+=2*(x-y)+5; y--;} ?? x++; ?? circlepoints (x,y,color); ? } } * * 华北水利水电学院 2011.9 第三章 基本图形算法（一） 1 概述 地址 = (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址 x y xmax xmin ymax ymin 每行像素点数 行数 行中位置 像素由其左下角坐标表示 2 光栅图形中点的表示 Address(x,y) = (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址 = k1 + k2y + x Address(x±1,y) = k1 + k2y + (x±1) = Address(x,y) ± 1 Address(x,y±1) = k1