1 直线生成算法(DDA、BRES) 2 圆生成算法（Mid） 3 多边形填充算法（扫描线、区域） 第6章 实现图元及属性的算法 1 直线生成算法(DDA、BRES) 2 圆生成算法（Mid） 3 多边形填充算法（扫描线、区域） 2019/1/10 交通运输学院CAD/CAM研究所

图元 图元：图形软件包中用了描述各种几何图形元素的函数称为图形输出原语，简称图元。 描述对象几何要素的输出图元一般称为几何图元。点的定位和直线段是最简单的几何图元。 在选定坐标系中指定一个图形的几何要素后，输出图元投影到该输出设备显示区域对于的二维平面上，并扫描转换到帧缓存的整数像素位置。 2019/1/10 交通运输学院CAD/CAM研究所

输出图元？ 屏幕坐标是像素扫描的行号和列号的位置，其坐标用整数表示． 表示范围是： 0 ~ xmax, 0 ~ ymax … 扫描行号 y 1) 屏幕坐标系 屏幕坐标是像素扫描的行号和列号的位置，其坐标用整数表示． 表示范围是： 0 ~ xmax, 0 ~ ymax x 扫描列号 0 1 2 3 4 5 … x 1 2 1 3 4 1 DAC 5 … 扫描行号 y y 屏幕 帧缓存(颜色缓存)

8.4 帧缓存(颜色缓存) 从几何 2) 光栅坐标系 x y 光栅坐标系 素坐标 观察函数将几 何描述转换成 帧缓存中的整 数像素位置 2) 光栅坐标系 8.4 0 1 2 3 4 5 … x 1 观察函数将几 何描述转换成 帧缓存中的整 2 3 4 5 2 数像素位置 … 2 9.6 世界坐标系下图 y 形的几何描述 帧缓存(颜色缓存) 从几何 描述到 扫描转 换的像 6 5 4 3 2 1 光栅坐标系 素坐标 01 2 3 4 56 7 8 9

A Scan Converted Line (离散、逼近) 2019/1/10 交通运输学院CAD/CAM研究所

1 直线的DDA算法 1 直线生成算法(DDA、BRES) 2 圆生成算法（Mid） 3 多边形填充算法（扫描线、区域） 4 字符图元算法 2019/1/10 交通运输学院CAD/CAM研究所

DDA Example 直线从点 (1,1)到 (8,5) 1 2 3 4 5 6 7 8 5 4 3 2 1 2019/1/10 交通运输学院CAD/CAM研究所

直接计算y坐标后，按四舍五入计算整数像素点 (1) 直线的DDA算法--- Digital Differential Analyzer 设直线的两端点为 (x0, y0)和(xend, yend) ,且坐标为整数值, y = kx + b 其斜截式方程为: 帧缓存 1 8 5 计算转换 1 直接计算y坐标后，按四舍五入计算整数像素点

可否优化？ y= k·x+b 5 k=0.571429 1 8 b=0.428571 X[0]=1 Y[0]=1 X[1]=2 Y[1]= X[0] x[1] x[2] x[3] x[4] x[5] x[6] x[7] b=0.428571 四舍五入 X[0]=1 Y[0]=1 X[1]=2 Y[1]= X[2]=3 Y[2]= X[3]=4 Y[3]= X[4]=5 Y[4]= X[5]=6 Y[5]= X[6]=7 Y[6]= X[7]=8 Y[7]=5 Y[1]=kx[1]+b=1.57 2 Y[2]=kx[2]+b=2.14 2 可否优化？ Y[3]=kx[3]+b=2.71 3 Y[4]=kx[4]+b=3.28 3 Y[5]=kx[5]+b=3.85 4 Y[6]=kx[6]+b=4.4 4

y= k·x+b Y0=kx0+b Y1=kx1+b Y1-Y0=k(X1-X0) Y1=Y0+k=Y0+&y/&x X[0] x[1] x[2] x[3] x[4] x[5] x[6] x[7] b=0.428571 X[0]=1 Y[0]=1 X[1]=2 Y[1]=kx[1]+b=1.57 Y[1]=2 X[2]=3 Y[2]=kx[2]+b=2.14 Y[2]=2 X[3]=4 Y[3]=kx[3]+b=2.71 Y[3]=3 X[4]=5 Y[4]=kx[4]+b=3.28 Y[4]=3 X[5]=6 Y[5]=kx[5]+b=3.85 Y[5]=4 X[6]=7 Y[6]=kx[6]+b=4.4 Y[6]=4 X[7]=8 Y[7]=5 Y0=kx0+b Y1=kx1+b Y[0]=1 Y[1]=y0+k=1.57 Y[2]=y1+k=2.14 Y[3]=y2+k=2.71 Y[4]=y3+k=3.28 Y[5]=y4+k=3.85 Y[6]=y5+k=4.4 Y[7]=5 Y1-Y0=k(X1-X0) Y1=Y0+k=Y0+&y/&x Yi+1=Yi+&y/&x 直线DDA算法

Line_dda(int xa,int ya,int xb,int yb ) { 程序？ Line_dda(int xa,int ya,int xb,int yb ) { } Void setPixel(GLint x, GLint y) { glBegin(GL_POINTS) glVertex2i(x, y); glEnd(); }

Y0=kx0+b Y1=kx1+b Y1-Y0=k(X1-X0) Yi+1=Yi+&y/|&x| Xi+1=Xi+&x/|&x| (1) 直线的DDA算法可能出现问题？ Y0=kx0+b Y1=kx1+b Y1-Y0=k(X1-X0) 如果X1-X0=1 Y1=Y0+k =Y0+&y/&x 如果X1-X0=-1 Y1=Y0-k =Y0-&y/&x Yi+1=Yi+&y/|&x| Xi+1=Xi+&x/|&x| 成立的条件： X1-X0=1或X1-X0=-1 |k|>1不成立 Y0 Y1 Y2 即：|k|<1 即：以X方向为步长方向 X0 X1 X2 【思考】 是否与X0，Y0 ；Xend、Yend所处的坐标象限有关？

显然 |Xi-Xi-1| ≠ 1 即Yi+1≠Yi+&y/|&x| 解决办法？ L L2 8 7 6 5 4 3 2 1 |K|=1 L1 1 2 3 4 5 6 7 8 9 对L1：最逼近的离散点如图L1， 成立的条件： X1-X0=1或X1-X0=-1 即：|k|<1 即： 以X方向为步长方向 对L2：最逼近的离散点如图L2 显然 |Xi-Xi-1| ≠ 1 即Yi+1≠Yi+&y/|&x| 解决办法？

当|k|<1时，即|&x|>|&y| 当|k|>=1时，即|&x|<=|&y|

DDA Example 直线从点 (20,10) and (30,18). dx = 10; dy = 8; steps = 10; 步长 x_in= 1; y_in = 0.8. Step i (x,y) (x i ,y ) 20,10 1 21,10.8 21,11 2 22,11.6 22,12 3 23,12.4 23,12 4 24,13.2 24,13 5 25,14 6 26,14.8 26,15 7 27,15.6 27,16 8 28,16.4 28,16 9 29,17.2 29,17 10 30,18 2019/1/10 交通运输学院CAD/CAM研究所

当|k|<1时，即|&x|>|&y| 当|k|>=1时，即|&x|<=|&y| 程序

建议优化地方？ #define ROUND (a) (int)(a+0.5) void line_DDA(int xa, int ya, int xb, int yb) { int dx = xb - xa, dy = yb - ya, steps, k; float xIncrement, yIncrement, x = xa, y = ya; if (abs (dx) > abs (dy)) steps = abs (dx); else steps = abs (dy); //两个绝对值大者决定step的值 xIncrement = dx / (float) steps; yIncrement = dy / (float) steps; SetPixel (ROUND(x), ROUND(y)) for (k=0; k<steps; k++) { x += xIncrement; y += yIncrement; SetPixel (ROUND (x) , ROUND(y)); } 建议优化地方？

DDA Algorithm Evaluation(评价) |k|<1 建议 优化地方 y1=round(y0+k) y2=round(y1+k) y3=round(y2+k) 优化方法？ 时间：浮点》加法》关系/逻辑 y3 y2 y1 y0

1 直线Bresenham算法 1 直线生成算法(DDA、Bres) 2 圆生成算法（Mid） 3 多边形填充算法（扫描线、区域） 4 字符图元算法 1 直线Bresenham算法 2019/1/10 交通运输学院CAD/CAM研究所

? Pi 直线Bresenham算法 替代Round（）函数方法？ p3 y0=k*x0+b y1=k*x1+b p1=k*(x1-x0) p1=k=&y/&x if p1>=0.5 y1=y0+1 else p1<0.5 y1 = y0 p2 p1 y0 y1 y2

改进的直线 Bresenham 算法 d2 d1 d2 d1 p1=d1-d2； if p1>=0 y1++; //上跳 进一步改进算法，消除K计算 p1=d1-d2； if p1>=0 y1++; //上跳 else y1不变 // 平移 y0 y1 y2

改进的直线 Bresenham 算法 pi=d1-d2 （Xi+1，Yi+1） （Xi，Yi） d1 = y - yi = k•x + b - yi = k • (xi+1) + b - yi d2 = yi+1 - y = yi + 1 - k • (xi+1) - b d1 - d2 = 2k • (xi+1) - 2yi + 2b - 1 斜率 k = △y / △x （△x 、 △y为端点坐标差） 定义Pi为决策参数 △x(d1 - d2 ) ： pi = △x(d1 - d2 ) = 2△y(xi+1) - 2yi • △x - △x(2b -1) = 2△y • xi - 2△x • yi + c c=2△y +△x(2b -1) pi+1 = 2△y • xi+1 - 2△x • yi+1 + c (c 常数.) pi+1 -pi = 2△y(xi+1 - xi)- 2△x(yi+1 - yi) pi=d1-d2 2019/1/10 交通运输学院CAD/CAM研究所

pi+1 -pi = 2△y(xi+1 - xi)- 2△x(yi+1 - yi) ∵ (xi+1 - xi) = 1, (yi+1 - yi)=1 or 0 ∴ pi+1 = pi + 2△y - 2△x(yi+1 - yi) ∵ pi = △x(d1 - d2 ), 即pi 与 d1- d2符号同号 ∴ 如果 pi < 0,选择(xi+1,yi), pi+1 = pi + 2△y 如果pi ≥ 0,选择 (xi+1,yi +1), pi+1= pi +2△y-2△x 初值： （通过pi = 2△y • xi - 2△x • yi + c 计算） y0 = k x0 + b p0 = 2△y - △x

0<k<1， 以xi+1方向为步长 直线Bresenham算法 LineBres.exe

-1<k<0 0<k<1 0<k<1 作业：如果起点在右边，终点在左边； Bresenham画线算法及程序？

是否还有新的直线算法？ 2019/1/10 交通运输学院CAD/CAM研究所

2 圆生成算法 1 直线生成算法(DDA、BRES) 2 圆生成算法（Mid） 3 多边形填充算法（扫描线、区域） 4 字符图元算法 2019/1/10 交通运输学院CAD/CAM研究所

Circle-Generating Algorithms (圆生成算法) Properties of circle Formula (x-xc)2+(y-yc)2=r2 Or x= xc +rcos y= yc +rsin Symmetry(对称性) 8 symmetry (x,y) (x,-y) (y,x) (y,-x) (-y,-x) (-x,-y) (-x,y) (-y,x) Y X y x 2019/1/10 交通运输学院CAD/CAM研究所

(x,y) (x,-y) (y,x) (y,-x) (-y,-x) (-x,-y) (-x,y) (-y,x) Y X 2019/1/10 交通运输学院CAD/CAM研究所

Midpoint Circle Algorithm (中点画圆算法) (-y , x) (-x,y) (-x,-y) (- y, -x) (y ,- x) (x,-y) (x,y) (y, x) 1、圆的八对称性 2、圆函数的内外检测 fcircle(x, y) = x2 + y2 - r2 fcircle(x, y) = 0. <0, 如果 (x, y) 在圆内部 fcircle(x, y) =0, 如果 (x, y) 在圆上 >0, 如果 (x, y) 在圆外部

求决策函数Pk，Pk+1? fcircle(x, y) = x2 + y2 - r2

X方向递增 (0,r) r (0,0)

如果r整数，P0=1-r

Example Centered the circle on the coordinate origin (0,0); radius ：r = 10; P0=1- r =1-10=-9; (x0,y0)=(0,10); 2x0=0, 2y0=20; 2019/1/10 交通运输学院CAD/CAM研究所

Example y y=x k pk (xk+1,yk+1) 2xk+1 2yk+1 0 -9 (1,10) 2 20 0 1 2 3 4 5 6 7 8 9 10 y y=x 10 9 8 7 6 5 4 3 2 1 k pk (xk+1,yk+1) 2xk+1 2yk+1 0 -9 (1,10) 2 20 1 -6 (2,10) 4 20 2 -1 (3,10) 6 20 3 6 (4,9) 8 18 4 -3 (5,9) 10 18 5 8 (6,8) 12 16 6 5 (7,7) 14 14 x

中点画圆算法： 1．输入圆的半径r和圆心 ，得到圆心在原点的圆周上的第一点为： ＝（0,r）； 2．计算决策参数的初始值： ； 3．从k=0开始，进行下列检测： 　　　　假如 ，下一个待画点是 ，　 ； 　　　　否则下一个待画点是　　　　　　，且　　　　　　　　　　　　； 4．确定在其它七个八分圆的对称点； 5．将每个计算出的象素位置（x,y）移动到中心在　　　　的圆路径上， 并画坐标值。 6．重复步骤3－5，直至 。

原点（0，0） 整圆程序？ 任意圆心程序？ CircleMidpoint.txt CircleMidpoint.exe 中点画圆程序实现 void circleMidpoint (GLint radius) { int x0=0, y0=10 ; int xk1=x0 , yk1=y0; GLint p = 5/4 - radius; for(int k=0;k<=radius;k++) xk1++; if (p < 0) p += 2 * xk + 1; else { yk1--; p += 2 * (xk1 – yk1) + 1; } setpixel(xk1,yk1); 语句 语句 语句 原点（0，0） 整圆程序？ 任意圆心程序？ CircleMidpoint.txt CircleMidpoint.exe

作业： 椭圆算法？ 二次曲线算法？ 参数化曲线算法？ 2019/1/10 38 交通运输学院CAD/CAM研究所

3 多边形填充算法 1 直线生成算法(DDA、BRES) 2 圆生成算法（Mid） 3 多边形填充算法（扫描线） 3 区域填充算法（区域） 2019/1/10 交通运输学院CAD/CAM研究所

Filled-Area Primitives (填充区域图元) 掌握 图案填充 实心填充 填充方法 扫描线多边形填充算法 区域填充算法

扫描线多边形填充算法 扫描线算法 目标：利用边、扫描线连贯性，提高算法效率。 处理对象：非自交的 （边与边之间除了顶点外无其它交点）凸、凹多边形。 2019/1/10 交通运输学院CAD/CAM研究所

多边形的填充－－扫描线填充算法 扫描线填充算法的基本思想：按扫描线顺序，计算扫描线与区域的相交区间，再用要求的颜色显示这些区间的象素。 　　扫描线填充算法的基本思想：按扫描线顺序，计算扫描线与区域的相交区间，再用要求的颜色显示这些区间的象素。 图3-16 一个多边形和若干水平扫描线

　　多边形扫描线填充算法，对于每一条扫描线，填充可分为四个步骤： 　　1. 求交：计算扫描线与多边形各边的交点； 　　2. 排序：把所有交点按递增顺序进行排序； 3. 交点配对：对排序交点从头到尾两两配对， 每对交点就代表扫描线与多边形的一个相交区间； 　　4. 区间填色：把这些相交区间内的象素置成填充色。 求交 排序 交点配对 扫描线y=6: 11，7，3.5 ，2 －＞2，3.5，7 ，11 －＞[2，3.5］，[7 ，11] 　　两个问题： 　　　　一 填充时，多边形边界上的象素是否填充？ 二 当扫描线与多边形顶点相交时，交点算几个？ 　　

问题一：填充时，多边形边界上的象素是否填充？ 问题一：填充时，多边形边界上的象素是否填充？　 图3-17 多边形边界上象素的填充 规定： 　　 只填充左、下边界的象素，右、上边界的象素不予填充。　 　　左闭右开：对扫描线与多边形的相交区间取左闭右开 　 下闭上开：

问题二：当扫描线与多边形顶点相交时，交点算几个？ ╳ 假定：当扫描线与多边形的顶点相交时，交点只算一个？？ 解决方法：　 　共享顶点的两条边分别落在扫描线的两侧，扫描线与顶点的交点只算1个； 　共享顶点的两条边在扫描线的同侧，扫描线与顶点的交点算为0个或2个： 　　　　顶点是多边形的局部最高点，交点数算0个 　 顶点是多边形的局部最低点，交点数算2个 求交 排序 交点配对 扫描线y=2: 2，8，2 －＞ 2，2，8 －＞ [2，2)，8 2，8 －＞ 2，8 －＞ [2，8) 扫描线y=7: 11，9，2 －＞ 2，9 ，11 －＞ [2，9)，11

怎样对图形中的所有直线进行求交运算？ 扫描线填充算法的四个步骤： 1. 求交： 2. 排序： 3. 交点配对： 4. 区间填色： 已知xk 待求xk+1 　　扫描线填充算法的四个步骤： 　　1. 求交： 　　2. 排序： 　　3. 交点配对： 　　4. 区间填色： 图3-18 与多边形相交的两条相邻扫描线 扫描线 与AB的交点： 扫描线 与AB的交点： 怎样对图形中的所有直线进行求交运算？

图形中的直线存储方式----链表 活性边表：把与扫描线　相交的边信息按交点x坐标递增的顺序保存在一个链表中，此链表称为扫描线　的活性边表(活化边表)。 　　 每个结点包含相交边的如下信息：　 　　　：边的最大y值 　　　：扫描线　与边的交点x坐标 　　　：边斜率的倒数 箭头　：指向下一个结点的指针　 扫描线y=4的活性边表： 　　1. 求交： 　　扫描线填充算法的四个步骤： 　　3. 交点配对： 　　2. 排序： 　　4. 区间填色：

活性边表的构建原则： 1.修改原则：相邻扫描线 　、　 和多边形的相交边很可能相同。当扫描线 处理完后，不必为扫描线 从新构建活性边表，只需在扫描线 活性边表的基础上进行修改即可。 扫描线 的活性边表： 扫描线 的活性边表： 扫描线y=5的活性边表： 扫描线y=6的活性边表：

2.删除原则:与扫描线 相交的边，若其　　　 　，则该边与下一条扫描线　 不再相交，要从扫描线 的活性边表中删除。 扫描线y=6的活性边表： 扫描线y=7的活性边表： 3. 新增原则:如果扫描线 有新交上的边，则在构建扫描线 的活性边表时，需将新交上的边插入到 活性边表的适当位置，保持有序性。 新边表

新边表：把与扫描线　交的新边信息按交点x坐标递增的顺序保存在一个链表中，此链表称为扫描线　的新边表。若某边的最低位置为　，则该边就放在扫描线　的新边表中。 　　　：边的最大y值 　　　：该扫描线与边的初始交点x坐标 　　　：边斜率的倒数 图3-20 各扫描线新边表

小结 新边表 活性边表的三个构造原则 修改原则 删除原则 新增原则 　扫描线新边表 扫描线活性边表 图3-21 新边表到活性边表

扫描线填充算法实现？ PlineFill.cpp PlineFill.exe

3 区域填充算法 种子（边界）填充算法 泛滥（注入）填充算法 见书 4.13不规则边界区域的填充方法 3 多边形填充算法（扫描线） 3 区域填充算法（区域) 3 区域填充算法 种子（边界）填充算法 泛滥（注入）填充算法 见书 4.13不规则边界区域的填充方法 2019/1/10 交通运输学院CAD/CAM研究所

Boundary-fill Algorithm IDEA -- start at a point known to be inside a figure and starts filling in the figure outward from the point. For single-color boundary 2019/1/10 交通运输学院CAD/CAM研究所

种子填充算法 种子填充算法的基本思想:如在区域内部有一象素已知，由此出发找到区域内的所有象素。 　　种子填充算法的基本思想:如在区域内部有一象素已知，由此出发找到区域内的所有象素。 　 种子填充算法适用于用边界定义的区域，该算法也可称为边界填充算法。 图3-22 四向算法 种子填充算法 八向算法

种子象素入栈，当栈非空时重复执行如下三步操作： 1. 栈顶象素出栈； 2. 将出栈象素置成填充色； 　　可以使用栈结构实现四向算法，步骤如下： 　　种子象素入栈，当栈非空时重复执行如下三步操作： 　　1. 栈顶象素出栈； 　　2. 将出栈象素置成填充色； 　　3. 按右、上、左、下逆时针顺序检查与出栈象素相邻的四个象素，若　　　 其中某个象素不在边界且未置成填充色，则把该象素入栈。 椎栈动态示意图 图3－23

程序实现 public void boundaryFill(int x, int y, int fill, int boundary) { if ((x < 0) || (x >= raster.width)) return; if ((y < 0) || (y >= raster.height)) return; int current = raster.getPixel(x, y); if ( ) { raster.setPixel(fill, x, y); boundaryFill(x+1, y, fill, boundary); boundaryFill(x-1, y, fill, boundary); boundaryFill(x, y+1, fill, boundary); boundaryFill(x, y-1, fill, boundary); } } (current != boundary) && (current != fill) 2019/1/10 交通运输学院CAD/CAM研究所

Flood-Fill Algorithm(泛滥填充算法) IDEA -- replaces all connected pixels of a selected color with a fill color. For multiple-color boundary 2019/1/10 交通运输学院CAD/CAM研究所

Flood-Fill Algorithm(泛滥填充算法) 　步骤如下： 　　种子象素入栈，当栈非空时重复执行如下三步操作： 　　1. 栈顶象素出栈； 2. 将出栈象素所在水平扫描线的连续象素段置成填充色，直至遇到边　　　 界象素为止； 　 3. 按下、上顺序检查当前扫描线相邻两条扫描线的有关象素是否为边　　　 界象素或已填充象素，若存在非边界、未填充的象素，则把每一区间的最左象素入栈。　　 图3－24　填充象素区间及椎栈示意图

程序实现 public void floodFill(int x, int y, int fill, int old) { if ((x < 0) || (x >= raster.width)) return; if ((y < 0) || (y >= raster.height)) return; int current = raster.getPixel(x, y); if ( ) { raster.setPixel(fill, x, y); floodFill(x+1, y, fill, old); floodFill(x-1, y, fill, old); floodFill(x, y+1, fill, old); floodFill(x, y-1, fill, old); } current == old 2019/1/10 交通运输学院CAD/CAM研究所

可选作业 编译运行OpenGL Exam程序 编写调试 直线DDA程序 编译调试 直线Bres程序 编译调试 中点画圆程序 编译调试扫描线填充程序（可选） 编译调试区域填充程序 编写姓名、学号、照片的OpenGL程序

2019/1/10 交通运输学院CAD/CAM研究所

2019/1/10 交通运输学院CAD/CAM研究所

直线Bresenham算法 p2 p3 1 d2 0.5 p1 p1=k p2=d2-(1-p1)=k+(p1-1) 平移 算法精简 p1=k p2=d2-(1-p1)=k+(p1-1) 平移 P3=k+p2 上跳 y0 y1 y2 (p1>0.5) (p2<0.5)