




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第三章第三章 直线、圆、椭圆生成算法直线、圆、椭圆生成算法 图形的扫描转换(光栅化):确定一个像素集合,用图形的扫描转换(光栅化):确定一个像素集合,用 于显示一个图形的过程。步骤如下:于显示一个图形的过程。步骤如下: 1、确定有关像素、确定有关像素 2、用图形的颜色或其它属性,对像素进行写操作。、用图形的颜色或其它属性,对像素进行写操作。 对一维图形,不考虑线宽,则用一个像素宽的直线来对一维图形,不考虑线宽,则用一个像素宽的直线来 显示图形。二维图形的光栅化,即区域的填充:确定显示图形。二维图形的光栅化,即区域的填充:确定 像素集,填色或图案。像素集,填色或图案。 任何图形的光栅化,必须显示
2、在一个窗口内,否则不任何图形的光栅化,必须显示在一个窗口内,否则不 予显示。即确定一个图形的哪些部分在窗口内,哪些予显示。即确定一个图形的哪些部分在窗口内,哪些 在窗口外,即裁剪。在窗口外,即裁剪。 图形显示前需要:扫描转换图形显示前需要:扫描转换+裁剪裁剪 裁剪裁剪-扫描转换:最常用,节约计算时间。扫描转换:最常用,节约计算时间。 扫描转换扫描转换-裁剪:算法简单;裁剪:算法简单; 本章内容本章内容 ?扫描转换直线段?扫描转换直线段 DDA算法算法 中点画线法中点画线法 Bresenham画线算法画线算法 ?圆弧、椭圆弧扫描转换?圆弧、椭圆弧扫描转换 中点算法中点算法 内接正多边形迫近法内接
3、正多边形迫近法 等面积正多边形逼近法等面积正多边形逼近法 生成圆弧的正负法生成圆弧的正负法 直线段的扫描转换算法直线段的扫描转换算法 n直线的扫描转换直线的扫描转换: 确定最佳逼近于该直线确定最佳逼近于该直线 的一组象素,并且按扫描线顺序,对这的一组象素,并且按扫描线顺序,对这 些象素进行写操作。些象素进行写操作。 n三个常用算法:三个常用算法: 数值微分法(数值微分法(DDA) 中点画线法中点画线法 Bresenham算法。算法。 数值微分法()数值微分法() 假定直线的起点、终点分别为:(假定直线的起点、终点分别为:(x0,y0), (x1,y1),且都为整数。,且都为整数。 (X i+1
4、 ,Yi + k) (X i , Int(Yi +0.5) (X i , Yi) 栅格交点表示象素点位置栅格交点表示象素点位置 。 。 。 。 数值微分数值微分(DDA)法法 n基本思想基本思想 已知过端点已知过端点P0 (x0, y0), P1(x1, y1)的直线段的直线段L y=kx+b 直线斜率为直线斜率为 这种方法直观,但效率太低,因为每一步需要一次浮点乘法这种方法直观,但效率太低,因为每一步需要一次浮点乘法 和一次舍入运算。和一次舍入运算。 01 01 xx yy k )(, ; 10 yroundx bkxy stepxxxxxx 令 数值微分数值微分(DDA)法法 计算计算yi
5、+1 i+1= kxi+1i+1+b = kxi i+b+k x = yi i+k x 当当 x =1;yi+1 i+1 = yi i+k n即:当即:当x每递增每递增1,y递增递增k(即直线斜率即直线斜率); n注意上述分析的算法仅适用于注意上述分析的算法仅适用于 k 1的情的情 形。在这种情况下,形。在这种情况下,x每增加每增加1,y最多增加最多增加 1。 n当当 k 1时,必须把时,必须把x,y地位互换地位互换 数值微分数值微分(DDA)法法 n增量算法:在一个迭代算法中,如果每增量算法:在一个迭代算法中,如果每 一步的一步的x、y值是用前一步的值加上一个值是用前一步的值加上一个 增量来
6、获得,则称为增量算法。增量来获得,则称为增量算法。 nDDA算法就是一个增量算法。算法就是一个增量算法。 数值微分(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; xx1, x+) drawpixel (x, int(y+0.5), color); y=y+k; 数值微分(DDA)法 n例:画直线段P0(0,0)-P1(5,2) x int(y+0.5) y+0.5 000+0.5
7、 100.4+0.5 210.8+0.5 311.2+0.5 421.6+0.5 522.0+0.5 0 1 2 3 4 5 3 2 1 Line: P0(0, 0)- P1(5, 2) 数值微分数值微分(DDA)法法 n缺点:缺点: 在此算法中,在此算法中,y、k必须是必须是float,且,且 每一步都必须对每一步都必须对y进行舍入取整,不利于硬件进行舍入取整,不利于硬件 实现。实现。 中点画线法中点画线法 n原理:原理: 假定直线斜率假定直线斜率0K1,且已确,且已确 定点亮象素点定点亮象素点P(Xp ,Yp ),则则 下一个与直线最接近的像素只下一个与直线最接近的像素只 能是能是P1点或
8、点或P2点。设点。设M为中点,为中点, Q为交点为交点 现需确定下一个点亮的象素。现需确定下一个点亮的象素。 P=(xp,yp) Q P2 P1 M 中点画线法中点画线法 n当当M在在Q的下方时,的下方时, P2 2离直线更近更近,取离直线更近更近,取 P2 2 。 。 nM在在Q的上方时,的上方时, P1 1离直线更近更近,取离直线更近更近,取P1 1 nM与与Q重合,重合, P1 1、P2 2任取一点。任取一点。 n 问题:如何判断问题:如何判断M与与Q点的关系?点的关系? P=(xp,yp) Q P2 P1 M 中点画线法 假设直线方程为:ax+by+c=0 其中a=y0-y1, b=x
9、1-x0, c=x0y1-x1y0 由常识知,令F(x,y)=ax+by+c: 将任意(x,y)代入F(x,y) 欲判断M点是在Q点上方还是在Q点下方,只需把 M代入F(x,y),并检查它的符号。 点在直线下方 点在直线上方 点在直线上面 0, 0, 0, yxF yxF yxF P=(xp,yp) Q P2 P1 中点画线法 构造判别式:d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c 当d0,M在直线(Q点)上方,取右方P1; 当d=0,选P1或P2均可,约定取P1; 能否采用增量算法呢? P=(xp,yp) Q P2 P1 中点画线法 若d0,则M在直
10、线上方,取P1; 此时再下一个象素的判别式为 d1=F(xp+2, yp+0.5) =a(xp+2)+b(yp+0.5)+c =a(xp +1)+b(yp +0.5)+c +a =d+a; 增量为a P=(xp,yp) Q P2 P1 中点画线法 n若d0,则M在直线下方,取P2; n此时再下一个象素的判别式为 d2= F(xp+2, yp+1.5) =a(xp+2)+b(yp+1.5)+c = a(xp +1)+b(yp +0.5)+c +a +b =d+a+b ; 增量为ab P=(xp,yp) Q P2 P1 中点画线法 n画线从(x0, y0)开始,d的初值 d0=F(x0+1, y0
11、+0.5)= a(x0 +1)+b(y0 +0.5)+c = F(x0, y0)+a+0.5b = a+0.5b 由于只用d 的符号作判断,为了只包含整数运算, 可以用2d代替d来摆脱小数,提高效率。 公式:已知两个端点P0(x0,y0),P1(x1,y1) a=y0-y1, b=x1-x0, c=x0y1-x1y0 d0 =2a+b d=d+a d 0,x=x+1 d=d+a+b d0,x=x+1,y=y+1 X从x0变化到x1 中点画线法 void Midpoint Line (int x0,int y0,int x1, int y1,int color) int a, b, d1, d2
12、, 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 (xx1) if (d0) x+; y+; d+=d2; else x+; d+=d1; drawpixel (x, y, color); /* while */ /* mid PointLine */ 中点画线法 n例:用中点画线法P0(0,0) P1(5,2) a=y0-y1=-2 b=x1-x0=5 d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6 i xiyid 1 001
13、2 10-3 3 213 4 31-1 5 425 0 1 2 3 4 5 3 2 1 Bresenham画线算法 在直线生成的算法中在直线生成的算法中BresenhamBresenham算法是最有算法是最有 效的算法之一。令效的算法之一。令 k=y/x k=y/x,就,就 0k10k1的情况来说明的情况来说明BresenhamBresenham算法。算法。 由由DDADDA算法可知:算法可知: y yi+1 i+1=y =yi i+k (1)+k (1) 由于由于k k不一定是整数,由此式求出的不一定是整数,由此式求出的y yi i也也 不一定是整数,因此要用坐标为(不一定是整数,因此要用坐
14、标为(x xi i,y,yir ir) ) 的象素来表示直线上的点,其中的象素来表示直线上的点,其中y yir ir表示 表示 最靠近最靠近y yi i的整数。的整数。 Bresenham画线算法 设图中xi列上已用(xi,yir)作为表示直线的点, 又设B点是直线上的点,其坐标为(xi+1,yi+1),显然 下一个表示直线的点( xi+1,yi+1,r)只能从图中的C或 者D点中去选。设A为CD边的中点。 若B在A点上面则 应取D点作为( xi+1,yi+1,r),否则应取C点。 (x)的几何意义 为能确定B在A点上面或下面,令 (xi+1)=yi+1-yir-0.5 (2) 若B在A的下面
15、,则有(xi+1)0。由图可知 yi+1,r=yir+1,若(xi+1)0 (3) yi+1,r=yir, 若(xi+1)0 Bresenham画线算法 由式(2)和式(3)可得到 (xi+2)=yi+2 - yi+1,r - 0.5 =yi+1 + k - yi+1,r - 0.5 (4) yi+1 - yir -0.5 + k - 1,当(xi+1)0 yi+1 - yir -0.5 + k, 当(xi+1)0 (xi+2)= (xi+1) + k -1 ,当(xi+1)0 (xi+2)= (xi+1) + k , 当(xi+1)0 由式(1)和式(2)可得到 (x2)= k - 0.5
16、(5) 程序如下: BresenhamLine(x0,y0,x1,y1,color) int x0,y0,x1,y1,color; int x,y,dx,dy; float k,e; int e; dx = x1-x0; dy = y1-y0; k = dy/dx; e = -0.5; x=x0; y=y0; e = - dx; for( i=0; i 0) e = e - 1; e = e - 2*dx; if(e =0) y+; Bresenham画线算法 圆的扫描转换算法 下面仅以圆心在原点、半径R为整数的圆为 例,讨论圆的生成算法。 假设圆的方程为: X 2 + Y2 = R2 圆弧扫
17、描算法 nX 2 + Y2 = R2 Y = Sqrt(R 2 - X2) 在一定范围内,每给定一 X值,可得一Y值。 当X取整数时,Y须取整。 缺点:浮点运算,开方, 取整,不均匀。 y x 角度DDA法 x = x0 + Rcos y = y0 + Rsin dx =- Rsind dy = Rcosd xn+1 =x n + dx y n+1 =y n + dy xn+1 = x n + dx = x n - Rsind =x n - (y n - y 0 )d y n+1 = y n + dy = y n + Rcosd =y n + (x n - x 0 )d 显然,确定x,y的初值
18、及d值后,即可以增量方式获 得圆周上的坐标,然后取整可得象素坐标。但要 采用浮点运算、乘法运算、取整运算。 中点画圆法 利用圆的对称性,只须讨论1/8圆。第二个8分圆 P为当前点亮象素,那么,下一个点亮的象素可 能是P1(Xp+1,Yp)或P2(Xp +1,Yp +1)。 M P1 P2 P(Xp ,Yp ) 中点画圆法 构造函数:F(X,Y)=X 2 + Y2 - R2 ;则 F(X,Y)= 0 (X,Y)在圆上; F(X,Y) 0 (X,Y)在圆外。 设M为P1、P2间的中点,M=(Xp+1,Yp-0.5) M P1 P2 中点画圆法 有如下结论: F(M)M在圆内- 取P1 F(M)=
19、0 -M在圆外- 取P2 为此,可采用如下判别式: M P1 P2 中点画圆法 d = F(M) = F(xp + 1, yp - 0.5) =(xp + 1) 2 + (y p - 0.5) 2 - R2 若d=0, 则P2 为下一个象素,那么再下一个象素的判 别式为: d1 = F(xp + 2, yp - 1.5) = (xp + 2) 2 + (y p - 1.5) 2 - R2 = d + (2x p + 3)+(-2 yp + 2) 即d 的增量为 2 (xp - yp) +5. d的初值:d0 = F(1, R-0.5)= 1 + (R-0.5) 2 - R2 = 1.25 -
20、R M P1 P2 中点画圆法 MidpointCircle(int r, int color) int x,y; float d; x=0; y=r; d=1.25-r; drawpixel(x,y,color); while(xy) if(d0) d+ = 2*x+3; x+ elsed+ = 2*(x-y) + 5; x+;y-; 中点画圆法 n为了进一步提高算法的效率,可以将上 面的算法中的浮点数改写成整数,将乘 法运算改成加法运算,即仅用整数实现 中点画圆法。 n使用e=d-0.25代替d ne0=1-R 中点画圆法 n上述算法能否再改进呢? n注意到d的增量是x,y的线性函数, n
21、每当x递增1,则d的增量递增x=2 n每当y递减1,则d的增量递增y=2 nx初始值=3;y初始值=-2r+2 n见173页算法。 Bresenham画圆算法 Bresenham画圆算法 现在从A点开始向右下方逐点来寻找 弧AB要用的点。如图中点Pi-1是已 选中的一个表示圆弧上的点,根 据弧AB的走向,下一个点应该从 Hi或者Li中选择。显然应选离AB最 近的点作为显示弧AB的点。 假设圆的半径为R,显然,当 xhi2 + yhi2 -R2 R2 - (xli2 + yli2)时,应该取Li。否则取Hi。 令di = xhi2 + yhi2 + xli2 + yli2 - 2R2 显然,当d
22、i 0 时应该 取Li。否则取Hi。 Pi-1Hi Li 应取Hi还是取Li Bresenham画圆算法 剩下的问题是如何快速的计算di。设图中 Pi-1的坐标为(xi-1,yi-1),则Hi和Li的坐 标为(xi,yi-1)和(xi,yi-1-1 ) di = xi2 + yi-12 + xi2 + (yi-1-1)2 - 2R2 =2xi2 + 2yi-12 - 2yi-1 - 2R2 di+1 = (xi + 1)2 + yi2 + (xi + 1)2 + (yi - 1)2 - 2R2 =2xi2 + 4xi + 2yi2 - 2yi - 2R2 + 3 Pi-1Hi Li 应取Hi还
23、是取Li Bresenham画圆算法 当di取Hi - yi=yi-1,则 di+1 = di + 4xi-1 + 6 当di 0时-取Li - yi=yi-1-1,则 di+1 = di + 4(xi-1-yi-1) + 10 易知 x0=0,y0=R,x1=x0+1 因此 d0=12 + y02 + 12 +(y0 - 1)2 - 2R2 = 3 - 2y0 = 3 - 2R Pi-1Hi Li 应取Hi还是取Li 生成圆弧的正负法 原理: 设圆的方程为F(x,y)=X 2 + Y2 - R2=0; 假设求得Pi的坐标为(xi,yi); 则当Pi在圆内时- F(xi,yi) 向右- 向圆外
24、 Pi在圆外时- F(xi,yi)0 - 向下- 向圆内 生成圆弧的正负法 即求得Pi点后选择下一个象素点Pi+1的规则为: 当F(xi,yi) 0 取xi+1 = xi+1,yi+1 = yi; 当F(xi,yi) 0 取xi+1 = xi, yi+1 = yi - 1; 这样用于表示圆弧的点均在圆弧附近,且使 F(xi,yi) 时正时负,故称正负法。 快速计算的关键是F(xi,yi) 的计算,能否采用增 量算法? 生成圆弧的正负法 n若F(xi,yi) 已知,计算F(xi+1,yi+1) 可分两种 情况: n1、F(xi,yi)0- xi+1 = xi+1,yi+1 = yi; n - F
25、(xi+1,yi+1)= (xi+1 ) 2 +(y i+1 ) 2 -R2 n - = (x i+1) 2+ y i 2 -R 2 = F(x i,yi) +2xi +1 n2、 F(xi,yi)0- xi+1 = xi,yi+1 = yi -1; n - F(xi+1,yi+1)= (xi+1 ) 2 +(y i+1 ) 2 -R2 n - = x i 2+(y i 1) 2-R2 = F(x i,yi) - 2yi +1 n3、初始值:略 生成圆弧的多边形逼近法 ? 圆的内接正多边形迫近法 ? 圆的等面积正多边形迫近法 圆的内接正多边形逼近法 n思想:当一个正多边形的边数足够多时, 该多
26、边形可以和圆无限接近。即 n因此,在允许的误差范围内,可以用正 多边形代替圆。 n设内接正n边形的顶点为Pi(xi,yi), Pi的幅 角为i ,每一条边对应的圆心角为a,则有 nxi =Rcos i nyi =Rsin i 圆边正内接多边形) n n (lim 圆的内接正多边形逼近法 内接正内接正n边形代替圆边形代替圆 n计算多边形各顶点的递推公式计算多边形各顶点的递推公式 Xi+1 Rcos( a+ i) = Yi +1 Rsin (a+ i) Xi+1 cos a- sin a Xi = Yi +1 sin a cosa Yi 因为: a是常数, sin a, cosa只在开始时计算一
27、次所以,一个顶点只需4次乘法,共4n次乘法, 外加直线段的中点算法的计算量。 圆的等面积正多边形逼近 法 n当用内接正多边形逼近圆时,其面积要 小于圆的面积;而当用圆的外切正多边 形逼近圆时,其面积则要大于圆的面积。 为了使近似代替圆的正多边形和圆之间 在面积上相等,只有使该正多边形和圆 弧相交,称之为圆的等面积正多边形。 圆的等面积正多边形逼近法 步骤: l求多边形径 长,从而求 所有顶点坐 标值 l由逼近误差 值,确定边 所对应的圆 心角 椭圆的扫描转换 nF(x,y)=b2x2+a2y2-a2b2=0 n椭圆的对称性,只考虑第一象限椭圆弧生成, 分上下两部分,以切线斜率为-1的点作为分 界点。 n椭圆上一点处的法向: N(x,y) = (F) x i + (F) y j = 2b2 x i + 2a2 y j 在上半部分,法向量的y分量大 在下半部分,法向量的x分量大 上半部分 下半部分 法向量 两分量相等 M1 M2 在当前中点处,法向量( 2b2 (Xp+1) ,2a2 (Yp-0.5)的y分量比x分 量大, 即: b2
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025-2030中国体积密度测试仪行业市场现状供需分析及投资评估规划分析研究报告
- 安全文明教育讲座
- 2025-2030中国产权交易行业竞争格局分析及投资前景与战略规划研究报告
- 2025-2030中国交流弧焊机行业市场深度调研及发展趋势与投资前景预测研究报告
- 2025-2030中国云POS市场运营格局与前景战略分析研究报告
- 2025-2030中国二手房行业市场深度调研及竞争格局与投资发展潜力研究报告
- 2025-2030中国乳房美学行业市场现状供需分析及投资评估规划分析研究报告
- 2025-2030中国中药化妆品行业市场现状供需分析及投资评估规划分析研究报告
- 2025-2030中国中小企业服务行业市场竞争格局与发展前景预测研究报告
- 2025-2030中国个人护理紧固件行业市场发展趋势与前景展望战略研究报告
- 沪教版八年级数学-代数方程1-学生
- 第8章-轴测图课件
- 艺术概论考试试题和答案
- 烫伤的护理课件
- 2022应急指挥中心基础设施与支撑系统建设规范
- 煤矿调度专业培训课件
- 幼儿园美工区指导方法
- 新纲要云南省实验教材信息技术五年级下册(第二版1-7课)
- 国家治理现代化场景下协同治理理论框架的构建
- 优甲乐服用方法
- 漂流项目规划设计方案
评论
0/150
提交评论