当前位置:首页 >> IT/计算机 >>

2.1 直线段的扫描转换算法


2.1 直线段的扫描转换算法
数值微分(DDA)法 设过端点 P0(x0 ,y0)、P1(x1 ,y1)的直线段为 L(P0 ,P1),则直线段 L 的斜率

L 的起点 P0 的横坐标 x0 向 L 的终点 P1 的横坐标 x1 步进,取步长=1(个象素), 用 L 的直线方程 y=kx+b 计算相应的 y 坐标,并取象素点(x,round(y))作为当前 点的坐标。因为:

yi+1 = kxi+1+b

= k1xi+b+k?x

= yi+k?x

所以,当?x =1; yi+1 = yi+k。也就是说,当 x 每递增 1,y 递增 k(即直线斜率)。 根据这个原理,我们可以写出 DDA 画线算法程序。

DDA 画线算法程序
void DDALine(int x0,int y0,int x1,int y1,int color) { int x; float dx, dy, y, k; dx = x1-x0; dy=y1-y0; k=dy/dx,;y=y0; for (x=x0;x< x1;x++) { drawpixel (x, int(y+0.5), color);

y=y+k; } }

注意:我们这里用整型变量 color 表示象素的颜色和灰度。 举例:用 DDA 方法扫描转换连接两点 P0 (0,0)和 P1(5,2)的直线段。 x int(y+0.5) y+0.5
0 1 2 3 4 0 0 1 1 2 0 0.4+0.5 0.8+0.5 1.2+0.5 1.6+0.5

图 2.1.1 直线段的扫描转换

注意: 上述分析的算法仅适用于|k| ≤1 的情形。 在这种情况下, 每增加 1,y x 最多增加 1。当 |k| > 1 时,必须把 x,y 地位互换,y 每增加 1,x 相应增加 1/k。 在这个算法中,y 与 k 必须用浮点数表示,而且每一步都要对 y 进行四舍五入后 取整,这使得它不利于硬件实现。

中点画线法 假定直线斜率 k 在 0~1 之间,当前象素点为(xp,yp),则下一个象素点有两 种可选择点 P1(xp+1,yp)或 P2(xp+1,yp+1)。若 P1 与 P2 的中点(xp+1,yp+0.5) 称为 M,Q 为理想直线与 x=xp+1 垂线的交点。当 M 在 Q 的下方时,则取 P2 应 为下一个象素点;当 M 在 Q 的上方时,则取 P1 为下一个象素点。这就是中点画 线法的基本原理。

图 2.1.2 中点画线法每步迭代涉及的象素和中点示意图 下面讨论中点画线法的实现。过点(x0,y0)、(x1, y1)的直线段 L 的方程式为 F(x, y)=ax+by+c=0,其中,a=y0-y1, b=x1-x0, c=x0y1-x1y0,欲判断中点 M 在 Q 点的上方还是下方,只要把 M 代入 F(x,y),并判断它的符号即可。为此,我 们构造判别式:

d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c

当 d<0 时,M 在 L(Q 点)下方,取 P2 为下一个象素;

当 d>0 时,M 在 L(Q 点)上方,取 P1 为下一个象素;

当 d=0 时,选 P1 或 P2 均可,约定取 P1 为下一个象素;

注意到 d 是 xp, yp 的线性函数,可采用增量计算,提高运算效率。

若当前象素处于 d≥0 情况,则取正右方象素 P1(xp+1, yp),要判下一个象素 位置,应计算 d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a,增量为 a。

若 d<0 时,则取右上方象素 P2(xp+1, yp+1)。要判断再下一象素,则要计算 d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b , 增量为 a+b。 画线从(x0, y0)

开始,d 的初值 d0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b,因 F(x0, y0)=0,所以 d0=a+0.5b。

由于我们使用的只是 d 的符号,而且 d 的增量都是整数,只是初始值包含小 数。因此,我们可以用 2d 代替 d 来摆脱小数,写出仅包含整数运算的算法程序。

中点画线算法程序:

void Midpoint Line (int x0,int y0,int x1, int y1,int color) { int a, b, d1, d2, d, x, y; a=y0-y1; b=x1-x0;d=2*a+b; d1=2*a;d2=2* (a+b); x=x0;y=y0; drawpixel(x, y, color); while (x<x1) { if (d<0) else {x++;y++; d+=d2; } {x++; d+=d1;}

drawpixel (x, y, color); } /* while */ } /* mid PointLine */

举例:用中点画线方法扫描转换连接两点 P0(0,0)和 P1(5,2)的直线段。
a=y0-y1=-2; b=x1-x0=5; d0=2*a+b=1;d1=2*a=-4;d2=2*(a+b)=6 , x y 0 0 1 0 2 1 3 1 4 2 d 1 -3 3 -1 5

图 2.1.3 中点画线法

5 2

15

问题 1: 若上述算法往下取二步(?i=2), 则算法和象素的取法将变成怎样?

问题 2:与 DDA 法相比,中点法的优点是什么?

2.1 直线段的扫描转换算法
Bresenham 算法 Bresenham 算法是计算机图形学领域使用最广泛的直线扫描转换算法。仍然 假定直线斜率在 0~1 之间, 该方法类似于中点法, 由一个误差项符号决定下一个 象素点。

算法原理如下:过各行各列象素中心构造一组虚拟网格线。按直线从起点到 终点的顺序计算直线与各垂直网格线的交点, 然后确定该列象素中与此交点最近 的象素。该算法的巧妙之处在于采用增量计算,使得对于每一列,只要检查一个 误差项的符号,就可以确定该列的所求象素。

如图 2.1.4 所示,设直线方程为 yi+1=yi+k(xi+1-xi)+k。假设列坐标象素已经 确定为 xi,其行坐标为 yi。那么下一个象素的列坐标为 xi+1,而行坐标要么为 yi,要么递增 1 为 yi+1。是否增 1 取决于误差项 d 的值。误差项 d 的初值 d0=0, x 坐标每增加 1,d 的值相应递增直线的斜率值 k,即 d=d+k。一旦 d≥1,就

把它减去 1,这样保证 d 在 0、1 之间。当 d≥0.5 时,直线与垂线 x=xi+1 交点 最接近于当前象素(xi,yi)的右上方象素(xi+1,yi+1);而当 d<0.5 时,更接近

于右方象素(xi+1,yi)。为方便计算,令 e=d-0.5,e 的初值为-0.5,增量为 k。当 e≥0 时,取当前象素(xi,yi)的右上方象素(xi+1,yi+1);而当 e<0 时, 取(xi,yi)右方象素(xi+1,yi)。

图 2.1.4 Bresenham 算法所用误差项的几何含义

Bresenham 画线算法程序:
void Bresenhamline (int x0,int y0,int x1, int y1,int color) { int x, y, dx, dy; float k, e; dx = x1-x0;dy = y1- y0;k=dy/dx; e=-0.5; x=x0,;y=y0; for (i=0;i<dx;i++) { drawpixel (x, y, color); x=x+1;e=e+k; if (e≥0) { y++; e=e-1;} } } 举例:用 Bresenham 方法扫描转换连接两点 P0(0,0)和 P1(5,2)的直线段。 x y e 0 0 -0.5

1 0 -0.1 2 1 -0.7 3 1 -0.3 4 2 -0.9 5 2 -0.5

图 2.1.5 Bresenham 算法

上述 Bresenham 算法在计算直线斜率与误差项时用到小数与除法。可以改用 整数以避免除法。由于算法中只用到误差项的符号,因此可作如下替换: 2*e*dx。

改进的 Bresenham 画线算法程序:
void InterBresenhamline (int x0,int y0,int x1, int y1,int color) { dx = x1-x0,;dy = y1- y0,;e=-dx; x=x0; y=y0; for (i=0; i<dx; i++) {drawpixel (x, y, color); x++; e=e+2*dy; if (e≥0) { y++; e=e-2*dx;} } }

2.2 圆弧的扫描转换算法
圆的特征 圆被定义为到给定中心位置(xc,yc)距离为 r 的点集。 圆心位于原点的圆有四 条对称轴 x=0,y=0,x=y 和 x=-y。若已知圆弧上一点(x,y),可以得到其关于四条

对称轴的其它 7 个点,这种性质称为圆的八对称性。因此,只要扫描转换八分之 一圆弧,就可以求出整个圆弧的象素集。

显示圆弧上的八个对称点的算法:
void CirclePoints(int x,int y,int color) { drawpixel(x,y,color); drawpixel(y,x,color); drawpixel(-x,y,color); drawpixel(y,-x,color); drawpixel(x,-y,color); drawpixel(-y,x,color); drawpixel(-x,-y,color); drawpixel(-y,-x,color); }

2.2 圆弧的扫描转换算法
中点画圆法 如果我们构造函数 F(x,y)=x2+y2-R2,则对于圆上的点有 F(x,y)=0,对于圆 外的点有 F(x,y)>0, 对于圆内的点 F(x,y)<0 。 与中点画线法一样, 构造判别式:

d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2

若 d<0,则应取 P1 为下一象素,而且再下一象素的判别式为:

d=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2=d+2xp+3

若 d≥0,则应取 P2 为下一象素,而且下一象素的判别式为

d=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2=d+2(xp-yp)+5

我们这里讨论的第一个象素是(0,R),判别式 d 的初始值为:

d0=F(1,R-0.5)=1.25-R

图 2.2.1 当前象素与下一象素的候选者 中点画圆算法:
MidPointCircle(int r int color) { int x,y; float d; x=0; y=r; d=1.25-r; circlepoints (x,y,color); while(x<=y) { if(d<0) else x++; circlepoints (x,y,color); } } d+=2*x+3; { d+=2*(x-y)+5; y--;}

为了进一步提高算法的效率,可以将上面的算法中的浮点数改写成整数,将 乘法运算改成加法运算,即仅用整数实现中点画圆法。

2.3 多边形的扫描转换与区域填充
多边形的扫描转换

多边形扫描转换算法对多边形的形状没有限制,但多边形的边界必须 时封闭的,且不自交。我们可以将多边形分为三种:凸多边形、凹多边 形、含内环的多边形。所谓凸多边形是指任意两顶点间的连线均在多边形 内;凹多边形是指任意两顶点间的连线有不在多边形内的部分;而含内环 的多边形则是指多边形内再套有多边形,多边形内的多边形也叫内环,内 环之间不能相交。

多边形的扫描转换

扫描线算法 扫描线算法是按扫描线顺序,计算扫描线与多边形的相交区间,再用要求的 颜色显示这些区间的象素,完成转换工作。区间的端点可以通过计算扫描线与多 边形边界线的交点获得。对于一条扫描线,多边形的扫描转换过程可以分为四个 步骤:

(1)求交:计算扫描线与多边形各边的交点;

(2)排序:把所有交点按 x 值递增顺序排序;

(3)配对:第一个与第二个,第三个与第四个等等;每对交点代表扫描线与多 边形的一个相交区间,

(4)着色:把相交区间内的象素置成多边形颜色,把相交区间外的象素置成背 景色。

图 2.3.2 一个多边形与若干扫描线

为了提高效率,在处理一条扫描线时,仅对与它相交的多边形的边进行求交 运算。我们把与当前扫描线相交的边称为活性边,并把它们按与扫描线交点 x 坐 标递增的顺序存放在一个链表中,称此链表为活性边表(AET)。

(a)扫描线 6 的活性边表

(b)扫描线 7 的活性边表

图 2.3.3 活性边表(AET)

假定当前扫描线与多边形某一条边的交点的横坐标为 x,则下一条扫描线 与该边的交点不必要重计算,只要加一个增量△x 即可,下面,我们推导这个结 论。

设该边的直线方程为:ax+by+c=0,当前扫描线及下一条扫描线与边的交点 分别为(xi,yi)、(xi+1,yi+1),则:

axi+byi+c=0

axi+1+byi+1+c=0

其中△x=-b/a 为常数,

另外使用增量法计算时,我们需要知道一条边何时不再与下一条扫描线相 交,以便及时把它从活性边表中删除出去。综上所述,活性边表的结点应为对应 边保存如下内容:第 1 项存当前扫描线与边的交点坐标 x 值;第 2 项存从当前扫 描线到下一条扫描线间 x 的增量 Dx;第 3 项存该边所交的最高扫描线号 ymax。

为了方便活性边表的建立与更新, 我们为每一条扫描线建立一个新边表 (NET) , 存放在该扫描线第一次出现的边。也就是说,若某边的较低端点为 ymin,则该边 就放在扫描线 ymin 的新边表中。

图 2.3.4 上图所示各条扫描线的新边表 NET

算法过程:

void polyfill (polygon, color)

int color;多边形 polygon;

{ for (各条扫描线 i )

{ 初始化新边表头指针 NET [i];

把 y min = i 的边放进边表 NET [i];

}

y = 最低扫描线号;

初始化活性边表 AET 为空;

for (各条扫描线 i )

{ 把新边表 NET[i]中的边结点用插入排序法插入 AET 表,使之按 x 坐标递增顺序排列;

遍历 AET 表,把配对交点区间(左闭右开)上的象素(x, y),用 drawpixel (x, y, color) 改写象素颜色值;

遍历 AET 表,把 y max= i 的结点从 AET 表中删除,并把 y max > i 结点的 x 值递增 D x;

若允许多边形的边自相交,则用冒泡排序法对 AET 表重新排序;

}

} /* polyfill */

扫描线与多边形顶点相交时,必须正确地取舍交点,如图 2.3.5 所示。

· P6。

扫描线与多边形相交的边分别位于扫描线的两侧, 则计一个交点, 如点 P5,

·

扫描线与多边形相交的边分别位于扫描线同侧,且 yi<yi-1,yi<yi+1,则计

2 个交点(填色),如 P2。若 yi>yi-1,yi>yi+1,则计 0 个交点(不填色),如 P1。

·

扫描线与多边形边界重合 (当要区分边界和边界内区域时需特殊处理), 则

计 1 个交点。

具体实现时,只需检查顶点的两条边的另外两个端点的 y 值。按这两个 y 值中 大于交点 y 值的个数是 0,1,2 来决定。

图 2.3.5 扫描线与多边形相交,特殊情况的处理

多边形的扫描转换

边界标志算法 边界标志算法的基本思想是: 在帧缓冲器中对多边形的每条边进行直线扫描 转换,亦即对多边形边界所经过的象素打上标志。然后再采用和扫描线算法类似 的方法将位于多边形内的各个区段着上所需颜色。 对每条与多边形相交的扫描线 依从左到右的顺序,逐个访问该扫描线上的象素。使用一个布尔量 inside 来指 示当前点是否在多边形内的状态。Inside 的初值为假,每当当前访问的象素为 被打上边标志的点,就把 inside 取反。对未打标志的象素,inside 不变。若访 问当前象素时,inside 为真,说明该象素在多边形内,则把该象素置为填充颜 色。

边界标志算法:

void edgemark_fill(polydef, color)

多边形定义 polydef; int color;

{

对多边形 polydef 每条边进行直线扫描转换;

inside = FALSE;

for (每条与多边形 polydef 相交的扫描线 y )

for (扫描线上每个象素 x )

{ if(象素 x 被打上边标志)inside = ! (inside);

if(inside!= FALSE)

drawpixel (x, y, color);

else

drawpixel (x, y, background);

}

}

图 2.3.6 正方形内切 n 个圆的边界标志算法 用软件实现时,扫描线算法与边界标志算法的执行速度几乎相同,但由于边 界标志算法不必建立维护边表以及对它进行排序, 所以边界标志算法更适合硬件 实现,这时它的执行速度比有序边表算法快一至两个数量级。 区域填充算法 这里讨论的区域指已经表示成点阵形式的填充图形,它是象素的集合。区域 可采用内点表示和边界表示两种表示形式。在内点表示中,区域内的所有象素着 同一颜色。在边界表示中,区域的边界点着同一颜色。区域填充指先将区域的一 点赋予指定的颜色,然后将该颜色扩展到整个区域的过程。

区域填充算法要求区域是连通的,因为只有在连通区域中,才可能将种子点 的颜色扩展到区域内的其它点。区域可分为 4 向连通区域和 8 向连通区域。4 向 连通区域指的是从区域上一点出发,可通过四个方向,即上、下、左、右移动的 组合,在不越出区域的前提下,到达区域内的任意象素;8 向连通区域指的是从 区域内每一象素出发,可通过八个方向,即上、下、左、右、左上、右上、左下、 右下这八个方向的移动的组合来到达。

四连通区域

八连通区域

图 2.3.7 四连通区域和八连通区域

图 2.3.8 区域的内点表示和边界表示 区域填充算法

区域填充的递归算法 以上讨论的多边形填充算法是按扫描线顺序进行的。 种子填充算法假设在多 边形内有一象素已知,由此出发利用连通性找到区域内的所有象素。

设(x,y)为内点表示的 4 连通区域内的一点,oldcolor 为区域的原色,要将 整个区域填充为新的颜色 newcolor。 内点表示的 4 连通区域的递归填充算法:

void FloodFill4(int x,int y,int oldcolor,int newcolor)

{ if(getpixel(x,y)==oldcolor)

{ drawpixel(x,y,newcolor);

FloodFill4(x,y+1,oldcolor,newcolor);

FloodFill4(x,y-1,oldcolor,newcolor);

FloodFill4(x-1,y,oldcolor,newcolor);

FloodFill4(x+1,y,oldcolor,newcolor);

}

}

边界表示的 4 连通区域的递归填充算法:
void BoundaryFill4(int x,int y,int boundarycolor,int newcolor)

{ int color;

if(color!=newcolor && color!=boundarycolor)

{ drawpixel(x,y,newcolor);

BoundaryFill4 (x,y+1, boundarycolor,newcolor);

BoundaryFill4 (x,y-1, boundarycolor,newcolor);

BoundaryFill4 (x-1,y, boundarycolor,newcolor);

BoundaryFill4 (x+1,y, boundarycolor,newcolor);

}

}

对于内点表示和边界表示的 8 连通区域的填充,只要将上述相应代码中递归 填充相邻的 4 个象素增加到递归填充 8 个象素即可。 区域填充的扫描线算法

区域填充的递归算法原理和程序都很简单, 但由于多次递归, 费时、 费内存, 效率不高。为了减少递归次数,提高效率可以采用扫描线算法。算法的基本过程 如下:当给定种子点(x,y)时,首先填充种子点所在扫描线上的位于给定区域的 一个区段,然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的 区段,并依次保存下来。反复这个过程,直到填充结束。

区域填充的扫描线算法可由下列四个步骤实现:

(1)初始化:堆栈置空。将种子点(x,y)入栈。

(2)出栈:若栈空则结束。否则取栈顶元素(x,y),以 y 作为当前扫描线。

(3)填充并确定种子点所在区段:从种子点(x,y)出发,沿当前扫描线向左、右两 个方向填充,直到边界。分别标记区段的左、右端点坐标为 xl 和 xr。

(4)并确定新的种子点:在区间[xl,xr]中检查与当前扫描线 y 上、下相邻的两条 扫描线上的象素。若存在非边界、未填充的象素,则把每一区间的最右象素作为 种子点压入堆栈,返回第(2)步。

区域填充的扫描线算法:

typedef struct{ //记录种子点

intx;

int y;

} Seed;

void ScanLineFill4(int x,int y,COLORREF oldcolor,COLORREF newcolor)

{

int xl,xr,i;

bool spanNeedFill;

Seed pt;

setstackempty();

pt.x =x; pt.y=y;

stackpush(pt); //将前面生成的区段压入堆栈

while(!isstackempty())

{

pt = stackpop();

y=pt.y;

x=pt.x;

while(getpixel(x,y)==oldcolor) //向右填充

{

drawpixel(x,y,newcolor);

x++;

}

xr = x-1;

x = pt.x-1;

while(getpixel(x,y)==oldcolor) //向左填充

{

drawpixel(x,y,newcolor);

x--;

}

xl = x+1;

//处理上面一条扫描线

x = xl;

y = y+1;

while(x<xr)

{

spanNeedFill=FALSE;

while(getpixel(x,y)==oldcolor)

{ spanNeedFill=TRUE;

x++;

}

if(spanNeedFill)

{ pt.x=x-1;pt.y=y;

stackpush(pt);

spanNeedFill=FALSE;

}

while(getpixel(x,y)!=oldcolor && x<xr) x++;

}//End of while(i<xr)

//处理下面一条扫描线,代码与处理上面一条扫描线类似

x = xl;

y = y-2;

while(x<xr)

{

....

}//End of while(i<xr)

}//End of while(!isstackempty())

}

上述算法对于每一个待填充区段,只需压栈一次;而在递归算法中,每个象 素都需要压栈。因此,扫描线填充算法提高了区域填充的效率。


赞助商链接
相关文章:
实验1 直线的扫描转换2003
实验1 直线的扫描转换 、实验要求基本要求 1、用直线 DDA 算法实现任何斜率、任何方向直线的绘制。 2、用直线 Bresenham 算法实现│m│<1,任何方向直线的绘制...
用中点算法扫描转换直线段
用中点算法扫描转换直线段_其它考试_资格考试/认证_教育专区。用中点算法扫描转换...line1(x0,y0,x1,y1,color); else if(y1>y0&&y1-y0>x1-x0) line2(x...
直线生成算法的实现
实验:直线生成算法班级 13 软件+道铁 1 班 学号 20132110050115 姓名 丁益 1.实验目的 a) 通过实验,进一步理解直线段扫描转换的 DDA 算法、中点画线自算法 ...
实验二 椭圆的扫描转换算法
实验 椭圆的扫描转换算法_自然科学_专业资料。西北农林科技大学实验报告学院名称...3.实验步骤: 1)对直线、圆弧的几何形状及相对位置进行分析,选定比较合适的算法...
线段的扫描转换算法
线段的扫描转换算法 摘要:本文主要讨论基本光栅图形算法中的线段图形对象的扫描...2.1 直线段的扫描转换算... 21页 免费 2.2直线扫描转换-中点算... 暂无...
计算机图形学 实验二 椭圆的扫描转换算法
计算机图形学 实验 椭圆的扫描转换算法_理学_高等教育_教育专区。了解和掌握...、实验步骤 1)对直线、圆弧的几何形状及相对位置进行分析,选定比较合适的算法...
在VC++6.0中实现直线的扫描转换算法
在VC++6.0中实现直线的扫描转换算法_计算机软件及应用_IT/计算机_专业资料。...1/2 相关文档推荐 实验一、VC++直线段的扫... 23页 1下载券 用VC 6.0...
直线段的扫描转换_计算机专业_OpenGL实验_Exp
实验目的 1、通过实验,进一步理解直线段扫描转换的 DDA 算法、中点 bresenham 算法以及改进 bresenham 算法的基本原理; 2、掌握以上算法生成直线段的基本过程; 3、...
直线扫描转换代码-MATLAB
实现直线扫描转换的 bresenham 算法 function line_Bresenham(p1,p2) XX=p2(1)-p1(1); YY=p2(2)-p1(2); XYSwitch=0;%表示 x 和 y 是否交换,1 表示...
椭圆的扫描转换算法
实验 1.实验目的: 椭圆的扫描转换算法 了解和掌握中点算法和 Bresenham 算法...3.实验步骤: 1)对直线、圆弧的几何形状及相对位置进行分析,选定比较合适的算法...
更多相关标签: