基本图形生成算法.ppt

第5章基本图形生成算法?提出问题如何在指定的输出设备上根据坐标描述构造基本二维几何图形(点、直线、圆、椭圆、多边形域、字符串及其相关属性等)。?图形生成的概念?直线段的扫描转换?圆的扫描转换?多边形的扫描转换与区域填充?属性处理?反走样技术?在OpenGL 中绘制图形本章主要内容: 图形的生成: 是在指定的输出设备上,根据坐标描述构造二维几何图形。图形的扫描转换: 在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。图5-1 用一系列的象素点来逼近直线 直线的扫描转换对直线进行光栅化时,需要在显示器有限个象素中,确定最佳逼近该直线的一组象素,并且按扫描线顺序,对这些象素进行写操作,这个过程称为用显示器绘制直线或直线的扫描转换。直线绘制的质量要求: ? :尽量接近理想直线? :即无定向性和断裂情况? 、色泽要均匀? ? 、亮度、线型等 数值微分法 ( Digital Differential Analyzer, DDA 法) 解决的问题: 给定直线 L的两端点 P 0(x 0,y 0)和P 1(x 1,y 1),画出该直线。方法:数值微分算法,中点 Bresenham 算法(正负法),改进的 Bresenham 算法等直线的微分方程: k xx yyx ydx dy??????? 01 01 (5-1) DDA 算法原理: 2)- (5 1 1yyy xxx ii ii????????????ε△x x i y x y i x i +1 y i +1ε△y 图5-2 DDA算法原理ε=1/max(| △x|,| △ y|) ?单位步长 max(| △ x|,| △ y|)=| △x|,即|k|≤1的情况: max(| △x|,| △ y|)=| △y|,此时|k|≥1: (5-3) 1 1 1???????????? i iiixxx xxxx?(5-4) k xxy xxxx i iii11 1????????????? kyyx yyyy i iii????????????1 1?1 1 1???????????? i iiiyyy yyyy?程序 2 图5-3 DDA算法生成直线段(x i,y i)(x i +1,round(y i +k)) (round(x i +1/k ),y i +1)K≥1K≤1 从L的起点 P 0的横坐标 x 0向L的终点 P 1的横坐标 x 1步进,取步长=1( 个象素),用 L的直线方程 y=kx+b 计算相应的 y坐标,并取象素点(x,round( y))作为当前点的坐标。因为: y i+1= kx i+1 +b = k 1x i+b+k?x = y i+k?x 所以,当? x = 1; y i+1= y i+k。也就是说,当 x每递增 1,y递增 k(即斜率)。 DDA 算法程序例 1 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;i<k;i++){ gl_Point(int(x), int(y)); x = x+dx; y = y+dy; } }// end DDA 图中圆黑点表示用 DDA 法生成的直线注意:上述分析的算法仅适用于| k| ≤1 的情形。在这种情况下, x 每增加 1, y 最多增加 1 。当 | k| > 1 时,必须把 x, y地位互换, y每增加 1,x相应增加 1/k。 DDA 算法的特点: ?增量算法?直观、易实现?需对浮点表示的变量进行四舍五入,不利于用硬件实现