计算机图形学 - GOOGLE CODE(精品·公开课件).ppt

北大计算机系多媒体与人机交互 第三章 输出图元 图形显示前需要：扫描转换+裁剪 ●裁剪---〉扫描转换：最常用，节约计算时间。 ●扫描转换---〉裁剪：算法简单； ●扫描转换到画布--〉位块拷贝：算法简单，但耗时耗内存。常用于字符显示。 线段的扫描转换算法 圆和椭圆的扫描转换 保持图形对象的数学性质 多边形的扫描转换 区域填充算法 线宽和线型 填充图案 字符技术 图形保真技术 半色调技术 线段的扫描转换算法 圆和椭圆的扫描转换 保持图形对象的数学性质 多边形的扫描转换 区域填充算法 线宽和线型 填充图案 字符技术 图形保真技术 半色调技术 DDA扫描转换直线段 扫描转换直线段 求与直线段充分接近的像素集 假设 直线段的宽度为1 DDA扫描转换直线段 数字微分(DDA)画线算法 （ digital differential analyzer） 条件： 待扫描转换的直线段：P1(x1,y1),P2(x2,y2) ?x=x2-x1, ?y=y2-y1 参数方程：x=x1+ ?x*t y=y1+ ?y*t 0≤ t≤1 直接求交算法： 划分区间[0, 1],dt=1/n 计算坐标. 取整. DDA扫描转换直线段 复杂度：乘法+加法+取整 DDA增量算法 xi+1=x1+?x*ti+1=xi+?x*dt=xi+xinc yi+1=y1+?y*ti+1=yi+?y*dt=yi+yinc 复杂度：加法+取整 DDA扫描转换直线段 算法描述 void DDA_line(int x1, y1, x2, y2) { int deltax, deltay, n, i; float x, y, xinc, yinc; deltax = x2 - x1; deltay = y2 – y1; if ( abs(deltax)abs(deltay) ) n = abs(deltax); else n = abs(deltay); xinc = (float)deltax / n; yinc = (float)deltay / n; x = x1; y = y1; write_pixel(round(x), round(y)); for ( i=0; in; i++ ) { x += xinc; y += yinc; write_pixel(round(x), round(y)); } } DDA扫描转换直线段 DDA算法缺点 需要进行浮点数运算 运行效率低 不便于用硬件实现 Bresenham扫描转换直线段 Bresenham画线算法 目标：消除DDA算法中 的浮点运算 条件： 同DDA算法 斜 率：0≤k≤1 直线段的隐式方程 （(x0,y0)(x1,y1)两端点） F(x,y)=ax+by+c=0 式中 a=y0-y1, b=x1-x0, c=x0y1-x1y0 Bresenham扫描转换直线段 分 析 线段的端点坐标:(x1,y1)和(x2,y2) 线段方程: y=k*x+b， 将平面以(x1,y1)为坐标原点划分为八个卦限， 考虑线段在第一卦限，即 Δx=x2-x10，Δy=y2-y1≥0， 并且Δx≥Δy的情况 此时xinc=1，yinc=k（0≤k≤1） Bresenham扫描转换直线段 Bresenham扫描转换直线段 并行画线算法 有p个处理器。将线段沿着x方向分为p个区段，区段的宽度为 ?xp=ceiling(?x/p)=(?x+p-1) div p 其中?x=xe-xs为线段宽度 ceiling(?x/p)为≥ ?x/p的最小整数 div为整数除法运算 再将这p个区段按照从左向右的次序依次编号为0,1,…,p-1,则编号为i的区段的起点的x坐标 xi=xs+i* ?xp 并行画线算法 计算编号为i的区段的起点的y坐标yi和判别式fi 的初始值。 区段的高度?yp=k*?xp yi=y1+round(i*?yp) ei=di-0.5 =k*i*?xp-round(i*?yp)+k-0.5 fi=2*?x*ei =2*?y*i*?xp-2*?x*round(i*?yp)+2* ?y- ?x