cg第3章电子教案.ppt
123页
第3章 基本图形生成算法,提出问题,如何在指定的输出设备上根据坐标描述构造基本二维几何图形（点、直线、圆、椭圆、多边形域、字符串及其相关属性等）图形的生成：是在指定的输出设备上，根据坐标描述构造二维几何图形 图形的扫描转换：在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程3.1 直线的扫描转换,直线的绘制要求： 1.直线要直 2.直线的端点要准确，即无定向性和断裂情况 3.直线的亮度、色泽要均匀 4.画线的速度要快 5.要求直线具有不同的色泽、亮度、线型等,3.1.1 数值微分法(DDA法),解决的问题： 给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线直线的微分方程：,DDA算法原理：,ε=1/max(|△x|,|△y|),max(|△x|,|△y|)=|△x|，即|k|≤1的情况：,max(|△x|,|△y|)=|△y|，此时|k|≥1：,程序 注意： round(x)=(int)(x+0.5),特点： 增量算法 直观、易实现 不利于用硬件实现,3.1.2 中点Bresenham算法,直线的方程,该直线方程将平面分为三个区域： 对于直线上的点，F(x,y)=0； 对于直线上方的点，F(x,y)>0； 对于直线下方的点，F(x,y)<0。
基本原理： 假定0≤k≤1，x是最大位移方向,判别式：,则有：,误差项的递推 d<0：,误差项的递推 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的符号； 若d<0，则(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的符号 若d<0，则(x,y)更新为(x+1,y+1)，d更新为d+2△x-2△y； 否则(x,y)更新为(x+1,y), d更新为d-2△y 4.当直线没有画完时，重复步骤3否则结束 程序,,,,3.1.3 改进的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的符号若d>0.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,y)更新为(x+1,y) 5.当直线没有画完时，重复步骤3和4否则结束改进1：令e=d-0.5,e初=-0.5， 每走一步有e=e+k if (e>0) then e=e-1,算法步骤为： 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的符号若e>0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y) 5.当直线没有画完时，重复步骤3和4否则结束改进2：用2e△x来替换e e初=-△x， 每走一步有e=e+2△y if (e>0) then e=e-2△x,算法步骤： 1.输入直线的两端点P0(x0,y0)和P1(x1,y1) 2.计算初始值△x、△y、e=-△x、x=x0、y=y0 3.绘制点(x,y) 4.e更新为e+2△y，判断e的符号。
若e>0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2△x；否则(x,y)更新为(x+1,y) 5.当直线没有画完时，重复步骤3和4否则结束作业：利用中点Bresenham画线算法的原理推导如图所示的直线段的扫描转换算法（从A到B，要求写清原理、误差函数、递推公式）3.2 圆的扫描转换,解决的问题： 绘出圆心在原点，半径为整数R的圆x2+y2==R2,3.2.1 八分法画圆,八分法画圆,(y,x),(-y,x),(-x,y),(-x,-y),(-y,-x),(y,-x),(x,-y),解决问题：,3.2.2 简单方程产生圆弧,算法原理：利用其函数方程，直接离散计算,圆的函数方程为：,圆的极坐标方程为：,3.2.3 中点Bresenham画圆,构造函数F(x,y)=x2+y2-R2 对于圆上的点，有F(x,y)=0； 对于圆外的点，F(x,y)>0； 而对于圆内的点，F(x,y)<0算法原理,当d≤0时，下一点取Pu(xi +1,yi)； 当d>0时，下一点取Pd(xi +1,yi-1)M的坐标为：M(xi +1,yi-0.5) 当F(xM,yM)0时，取Pd(xi +1,yi-1) 当F(xM,yM)=0时，约定取Pu。
构造判别式：,误差项的递推 d≤0：,d>0：,判别式的初始值,算法步骤： 1.输入圆的半径R 2.计算初始值d=1.25-R、x=0、y=R 3.绘制点(x,y)及其在八分圆中的另外七个对称点 4.判断d的符号若d≤0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1) 5.当x
引理5-1：若在当前中点，法向量的y分量比x分量大，即,而在下一个中点，不等号改变方向，则说明椭圆弧从上部分转入下部分法向量,5.3.2 椭圆的中点Bresenham算法,算法原理,先推导上半部分的椭圆绘制公式,判别式,若d1≤0，取Pu(xi+1,yi) 若d1>0，取Pd(xi+1,yi-1),误差项的递推 d1≤0：,d1>0：,判别式的初始值,再来推导椭圆弧下半部分的绘制公式 原理,判别式,若d2>0，取Pl(xi,yi-1) 若d2≤0，取Pr(xi+1,yi-1),误差项的递推 d2>0：,d2≤0：,注意： 上半部分的终止判别 下半部分误差项的初值算法步骤： 1.输入椭圆的长半轴a和短半轴b 2.计算初始值d=b2+a2(-b+0.25)、x=0、y=b 3.绘制点(x,y)及其在四分象限上的另外三个对称点4.判断d的符号若d≤0，则先将d更新为d+b2(2x+3)，再将(x,y)更新为(x+1,y)；否则先将d更新为d+b2(2x+3)+a2(-2y+2)，再将(x,y)更新为(x+1,y-1) 5.当b2(x+1) 6.用上半部分计算的最后点(x,y)来计算下半部分中d的初值：,7.绘制点(x,y)及其在四分象限上的另外三个对称点 8.判断d的符号若d≤0，则先将d更新为b2(2xi+2)+a2(-2yi+3)，再将(x,y)更新为(x+1,y-1)；否则先将d更新为d+a2(-2yi+3)，再将(x,y)更新为(x,y-1) 9.当y>0时，重复步骤7和8否则结束 程序,正负法,基本原理：假设直线斜小于1设P=(x,y)是直线上的一点(用Δ表示)，点P正右方或右上方的点分别为(xi+1,yi)和(xi+1,yi+1),设M表示PB和PT的中点，设Q是直线与垂直线x=xi+1的交点，若M在Q的下方，则 PT 离直线近，应取为下一个像素；否则应取PB 正负法的具体实现,设直线的起点和终点分别为(x0,y0)和(x1,y1),直线方程为:其中 分别对应于点 在直线上、上方和下方,要判断点M在直线上，上方还是下方可将M代入下面的判别式判断符号即可,正负法算法的具体实现,d<0，Q在M上方，取P2为下一像素,d>0，取P1为下一像素,d=0,可在两个点中任取一个，约定取右下方的点,在d>0，取右下方像素P1 ，下一个像素应取哪个，应计算,若d<0，则取右上方像素 P2，并计算,最后讨论d的初始值，第一个像素应取 (x0,y0),P1,P2,正负法算法,由于(x0,y0)在直线上，故F(x0,y0)=0。 因此，设第一个像素取(x0,y0),则,当d>0时，,当d<0时，,当d<0时，,正负法程序,void MidpointLine(int x0,int y0,int x1,int y1) {int a, b, delta1, delta2, d,x, y;a=y0-y1; b=x1-x0;d=2*a+b; delta1=2*a; delta2=2*(a+b); x=x0; y=y0;glBegin(GL_POINTS);glVertex2s(x,y); glEnd();,while(x 1. 什么是多边形的扫描转换,2. x-扫描线算法 基本思想,算法步骤： (1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax） (2)从y=ymin到y=ymax，每次用一条扫描线进行填充 (3)对一条扫描线填充的过程可分为四个步骤：a.求交b.排序c.交点配对d.区间填色,存在问题：当扫描线与多边形顶点相交时，交点的取舍问题解决：当扫描线与多边形的顶点相交时， 若共享顶点的两条边分别落在扫描线的两边，交点只算一个； 若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个0,1,1,1,1,0,2,2,2,填充过程实例,3. 改进的有效边表算法（Y连贯性算法）,改进原理： 处理一条扫描线时，仅对有效边求交 利用扫描线的连贯性 利用多边形边的连贯性,有效边（Active Edge）：指与当前扫描线相交的多边形的边，也称为活性边 有效边表（Active Edge Table, AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表 有效边表的每个结点：x ymax 1/k next,边表（Edge Table） 边表的构造： (1)首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，则对应多边形覆盖的每一条扫描线。 (2)将每条边的信息链入与该边最小y坐标（ymin ）相对应的桶处也就是说，若某边的较低端点为ymin，则该边就放在相应的扫描线桶中。
