cg第3章电子教案

《cg第3章电子教案》由会员分享，可在线阅读，更多相关《cg第3章电子教案（123页珍藏版）》请在金锄头文库上搜索。

1、第3章 基本图形生成算法,提出问题,如何在指定的输出设备上根据坐标描述构造基本二维几何图形（点、直线、圆、椭圆、多边形域、字符串及其相关属性等）。,图形的生成：是在指定的输出设备上，根据坐标描述构造二维几何图形。 图形的扫描转换：在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。,3.1 直线的扫描转换,直线的绘制要求： 1.直线要直 2.直线的端点要准确，即无定向性和断裂情况 3.直线的亮度、色泽要均匀 4.画线的速度要快 5.要求直线具有不同的色泽、亮度、线型等,3.1.1 数值微分法(DDA法),解决的问题： 给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。

2、,直线的微分方程：,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。,基本原理： 假定0k1，x是最大位移方向,判别式：,则有：,误差项的递推 d0：,误差项的递推 d0：,初始值d的计算,0k1

3、时Bresenham算法的算法步骤为： 1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。 2.计算初始值x、y、d=0.5-k、x=x0、y=y0； 3.绘制点(x,y)。判断d的符号； 若d0，则(x,y)更新为(x+1,y+1)，d更新为d+1-k； 否则(x,y)更新为(x+1,y)，d更新为d-k。 4.当直线没有画完时，重复步骤3。否则结束。,改进：用2dx代替d 1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。 2.计算初始值x、y、d=x-2y、x=x0、y=y0。 3.绘制点(x,y)。判断d的符号。 若d0.5，则(x,y)更新为(x+1,y+1)，同

4、时将d更新为d-1；否则(x,y)更新为(x+1,y)。 5.当直线没有画完时，重复步骤3和4。否则结束。,改进1：令e=d-0.5,e初=-0.5， 每走一步有e=e+k。 if (e0) 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的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。 5.当直线没有画完时，重复步骤3和4。否则结束。,改进2：用2ex来替换e e初=-x，

5、 每走一步有e=e+2y。 if (e0) then e=e-2x,算法步骤： 1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。 2.计算初始值x、y、e=-x、x=x0、y=y0。 3.绘制点(x,y)。 4.e更新为e+2y，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2x；否则(x,y)更新为(x+1,y)。 5.当直线没有画完时，重复步骤3和4。否则结束。,作业：利用中点Bresenham画线算法的原理推导如图所示的直线段的扫描转换算法（从A到B，要求写清原理、误差函数、递推公式）。,3.2 圆的扫描转换,解决的问题： 绘出圆心在原点，半径

6、为整数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时，下一点取Pd(xi +1,yi-1)。,M的坐标为：M(xi +1,yi-0.5) 当F(xM,yM)0时，取Pd(xi +1,y

7、i-1) 当F(xM,yM)=0时，约定取Pu。 构造判别式：,误差项的递推 d0：,d0：,判别式的初始值,算法步骤： 1.输入圆的半径R。 2.计算初始值d=1.25-R、x=0、y=R。 3.绘制点(x,y)及其在八分圆中的另外七个对称点。 4.判断d的符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。 5.当xy时，重复步骤3和4。否则结束。,改进：用d-0.25代替d 算法步骤： 1.输入圆的半径R。 2.计算初始值d=1-R、x=0、y=R。 3.绘制点(x,y)及其在八分圆中

8、的另外七个对称点。 4.判断d的符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。 5.当x0； 对于椭圆内的点，F(x,y)0，取Pd(xi+1,yi-1),误差项的递推 d10：,d10：,判别式的初始值,再来推导椭圆弧下半部分的绘制公式 原理,判别式,若d20，取Pl(xi,yi-1) 若d20，取Pr(xi+1,yi-1),误差项的递推 d20：,d20：,注意： 上半部分的终止判别 下半部分误差项的初值算法步骤： 1.输入椭圆的长半轴a和短半轴b。 2.计算初始值d=b2+a2(

9、-b+0.25)、x=0、y=b。 3.绘制点(x,y)及其在四分象限上的另外三个对称点。,4.判断d的符号。若d0，则先将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)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 离直线近，

10、应取为下一个像素；否则应取PB 。,正负法的具体实现,设直线的起点和终点分别为(x0,y0)和(x1,y1),直线方程为:其中 分别对应于点 在直线上、上方和下方,要判断点M在直线上，上方还是下方可将M代入下面的判别式判断符号即可,正负法算法的具体实现,d0，取P1为下一像素,d=0,可在两个点中任取一个，约定取右下方的点,在d0，取右下方像素P1 ，下一个像素应取哪个，应计算,若d0时，,当d0时，,当d0时，,正负法程序,void MidpointLine(int x0,int y0,int x1,int y1) int a, b, delta1, delta2, d,x, y;a=y0-

11、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(xx1)if(d0)x+; y+; d += delta2;elsex+; d += delta1;glBegin(GL_POINTS);glVertex2s(x,y); glEnd(); /End While /End MidpointLine,3.4 多边形的扫描转换与区域填充,多边形的扫描转换主要是通过确定穿越区域的扫描线的覆盖区间来填充，区域填充是从给定的位置开始涂描

12、直到指定的边界条件为止。,3.4.1 多边形的扫描转换,顶点表示用多边形的顶点序列来刻划多边形 点阵表示是用位于多边形内的象素的集合来刻划多边形 扫描转换多边形或多边形的填充：从多边形顶点表示到点阵表示的转换。,1. 什么是多边形的扫描转换,2. x-扫描线算法 基本思想,算法步骤： (1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。 (2)从y=ymin到y=ymax，每次用一条扫描线进行填充。 (3)对一条扫描线填充的过程可分为四个步骤：a.求交b.排序c.交点配对d.区间填色,存在问题：当扫描线与多边形顶点相交时，交点的取舍问题。,解决：当扫描线

13、与多边形的顶点相交时， 若共享顶点的两条边分别落在扫描线的两边，交点只算一个； 若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。,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，则该边就放在相应的扫描线桶中。,