资源预览内容
第1页 / 共54页
第2页 / 共54页
第3页 / 共54页
第4页 / 共54页
第5页 / 共54页
第6页 / 共54页
第7页 / 共54页
第8页 / 共54页
第9页 / 共54页
第10页 / 共54页
亲,该文档总共54页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
2019/11/6,浙江大学计算机图形学,1,第二章 直线、圆、椭圆生成算法,图形的扫描转换(光栅化):确定一个像素集合,用于显示一个图形的过程。步骤如下: 1、确定有关像素 2、用图形的颜色或其它属性,对像素进行写操作。 对一维图形,不考虑线宽,则用一个像素宽的直线来显示图形。二维图形的光栅化,即区域的填充:确定像素集,填色或图案。 任何图形的光栅化,必须显示在一个窗口内,否则不予显示。即确定一个图形的哪些部分在窗口内,哪些在窗口外,即裁剪。,2019/11/6,浙江大学计算机图形学,2,图形显示前需要:扫描转换+裁剪 裁剪-扫描转换:最常用,节约计算时间。 扫描转换-裁剪:算法简单;,2019/11/6,浙江大学计算机图形学,3,本章内容,扫描转换直线段 DDA算法 中点画线法 Bresenham画线算法 圆弧、椭圆弧扫描转换 中点算法 内接正多边形迫近法 等面积正多边形逼近法 生成圆弧的正负法,2019/11/6,浙江大学计算机图形学,4,直线段的扫描转换算法,直线的扫描转换: 确定最佳逼近于该直线的一组象素,并且按扫描线顺序,对这些象素进行写操作。 三个常用算法: 数值微分法(DDA) 中点画线法 Bresenham算法。,2019/11/6,浙江大学计算机图形学,5,数值微分法(),假定直线的起点、终点分别为:(x0,y0), (x1,y1),且都为整数。,(X i+1 ,Yi + k),(X i , Int(Yi +0.5),(X i , Yi),栅格交点表示象素点位置,。,。,。,。,2019/11/6,浙江大学计算机图形学,6,数值微分(DDA)法,基本思想 已知过端点P0 (x0, y0), P1(x1, y1)的直线段L y=kx+b 直线斜率为 这种方法直观,但效率太低,因为每一步需要一次浮点乘法和一次舍入运算。,2019/11/6,浙江大学计算机图形学,7,数值微分(DDA)法,计算yi+1= kxi+1+b = kxi+b+kx = yi+kx 当x =1; yi+1 = yi+k 即:当x每递增1,y递增k(即直线斜率); 注意上述分析的算法仅适用于k 1的情形。在这种情况下,x每增加1,y最多增加1。 当 k 1时,必须把x,y地位互换,2019/11/6,浙江大学计算机图形学,8,数值微分(DDA)法,增量算法:在一个迭代算法中,如果每一步的x、y值是用前一步的值加上一个增量来获得,则称为增量算法。 DDA算法就是一个增量算法。,2019/11/6,浙江大学计算机图形学,9,数值微分(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; ,2019/11/6,浙江大学计算机图形学,10,数值微分(DDA)法,例:画直线段P0(0,0)-P1(5,2) x int(y+0.5) y+0.5 0 0 0+0.5 1 0 0.4+0.5 2 1 0.8+0.5 3 1 1.2+0.5 4 2 1.6+0.5 5 2 2.0+0.5,0 1 2 3 4 5,3,2,1,Line: P0(0, 0)- P1(5, 2),2019/11/6,浙江大学计算机图形学,11,数值微分(DDA)法,缺点: 在此算法中,y、k必须是float,且每一步都必须对y进行舍入取整,不利于硬件实现。,2019/11/6,浙江大学计算机图形学,12,中点画线法,原理:,假定直线斜率0K1,且已确定点亮象素点P(Xp ,Yp ),则下一个与直线最接近的像素只能是P1点或P2点。设M为中点,Q为交点 现需确定下一个点亮的象素。,P=(,x,p,y,p,),Q,P2,P1,2019/11/6,浙江大学计算机图形学,13,中点画线法,当M在Q的下方- P2离直线更近更近-取P2 。 M在Q的上方- P1离直线更近更近-取P1 M与Q重合, P1、P2任取一点。 问题:如何判断M与Q点的关系?,P=(,x,p,y,p,),Q,P2,P1,2019/11/6,浙江大学计算机图形学,14,中点画线法,假设直线方程为:ax+by+c=0 其中a=y0-y1, b=x1-x0, c=x0y1-x1y0 由常识知: 欲判断中点M点是在Q点上方还是在Q点下方,只需把M代入F(x,y),并检查它的符号。,P=(,x,p,y,p,),Q,P2,P1,2019/11/6,浙江大学计算机图形学,15,中点画线法,构造判别式: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=(,x,p,y,p,),Q,P2,P1,2019/11/6,浙江大学计算机图形学,16,中点画线法,若d0 -M在直线上方-取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=(,x,p,y,p,),Q,P2,P1,2019/11/6,浙江大学计算机图形学,17,中点画线法,若dM在直线下方-取P2; 此时再下一个象素的判别式为 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=(,x,p,y,p,),Q,P2,P1,2019/11/6,浙江大学计算机图形学,18,中点画线法,画线从(x0, y0)开始,d的初值 d0=F(x0+1, y0+0.5)= a(x0 +1)+b(y0 +0.5)+c = F(x0, y0)+a+0.5b = a+0.5b 由于只用d 的符号作判断,为了只包含整数运算, 可以用2d代替d来摆脱小数,提高效率。,2019/11/6,浙江大学计算机图形学,19,中点画线法,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 (xx1) if (d0) x+; y+; d+=d2; else x+; d+=d1; drawpixel (x, y, color); /* while */ /* mid PointLine */,2019/11/6,浙江大学计算机图形学,20,中点画线法,例:用中点画线法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 xi yi d 1 0 0 1 2 1 0 -3 3 2 1 3 4 3 1 -1 5 4 2 5,0 1 2 3 4 5,3,2,1,2019/11/6,浙江大学计算机图形学,21,Jack Elton Bresenham,Bresenham算法最初是为数字绘图仪提出,但同样适用于CRT光栅显示器。,2019/11/6,浙江大学计算机图形学,22,Bresenham画线算法,在直线生成的算法中Bresenham算法是最有效的算法之一。令 k=y/x,就0k1的情况来说明Bresenham算法。由DDA算法可知: yi+1=yi+k (1) 由于k不一定是整数,由此式求出的yi也不一定是整数,因此要用坐标为(xi,yir)的象素来表示直线上的点,其中yir表示最靠近yi的整数。,2019/11/6,浙江大学计算机图形学,23,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点。,xi,Xi+1,Yi,r,Yi+1,r,C,D,B,A,(x)的几何意义,为能确定B在A点上面或下面,令 (xi+1)=yi+1-yir-0.5 (2) 若B在A的下面,则有(xi+1)0。由图可知 yi+1,r=yir+1,若(xi+1)0 (3) yi+1,r=yir, 若(xi+1)0,2019/11/6,浙江大学计算机图形学,24,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 (5),2019/11/6,浙江大学计算机图形学,25,程序如下: 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画线算法,2019/11/6,浙江大学计算机图形学,26,圆的扫描转换算法,下面仅以圆心在原点、半径R为整数的圆为例,讨论圆的生成算法。 假设圆的方程为: X2 + Y2 = R2,2019/11/6,浙江大学计算机图形学,27,圆弧扫描算法,X2 + Y2 = R2 Y = Sqrt(R2 - X2) 在一定范围内,每给定一 X值,可得一Y值。 当X取整数时,Y须取整。 缺点:浮点运算,开方, 取整,不均匀。,2019/11/6,浙江大学计算机图形学,28,角度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 )
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号