1 直线生成算法(DDA、BRES) 2 圆生成算法（Mid） 3 多边形填充算法（扫描线、区域）

Presentation on theme: "1 直线生成算法(DDA、BRES) 2 圆生成算法（Mid） 3 多边形填充算法（扫描线、区域）"— Presentation transcript:

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

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

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

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

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

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

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

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

9 可否优化？ 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= 四舍五入 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

10 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= 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算法

11 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(); }

12 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所处的坐标象限有关？

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

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

15 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研究所

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

17 建议优化地方？ #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)); } 建议优化地方？

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

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

20 ? 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

21 改进的直线 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

22 改进的直线 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 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研究所

23 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

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

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

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

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

28 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研究所

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

30 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) 在圆外部

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

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

33 如果r整数，P0=1-r

34 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研究所

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

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

37 原点（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

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

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

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

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

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

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

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

45 问题二：当扫描线与多边形顶点相交时，交点算几个？
╳ 假定：当扫描线与多边形的顶点相交时，交点只算一个？？ 解决方法：　 　共享顶点的两条边分别落在扫描线的两侧，扫描线与顶点的交点只算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

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

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

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

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

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

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

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

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

54 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研究所

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

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

57 程序实现 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研究所

58 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研究所

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

60 程序实现 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研究所

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

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

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

64 直线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)