《基本图形的生成与计算-直线、圆、椭圆的生成.ppt》由会员分享，可在线阅读，更多相关《基本图形的生成与计算-直线、圆、椭圆的生成.ppt（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章 直线、圆、椭圆生成算法图形的扫描转换(光栅化)：确定像素、显示图形的过程。步骤如下：1.确定像素2.用图形属性，对像素进行写操作 一维图形，用一个像素宽的直线来显示图形 二维图形的光栅化，即区域的填充：确定像素，填色或图案。3.图形的光栅化，必须显示在窗口内，否则不予显示。确定图形的哪些部分在窗口内，哪些在窗口外，即裁剪 浙江师范大学数理与信息工程学院 计算机图形学图形显示前需要：扫描转换+裁剪 裁剪-扫描转换：最常用，节约计算时间。扫描转换-裁剪：算法简单；浙江师范大学数理与信息工程学院 计算机图形学本章内容 直线的生成算法 圆的生成算法 区域填充算法 字符的生成 图形求交 图形裁剪
2、浙江师范大学数理与信息工程学院 计算机图形学直线的生成算法 确定最佳逼近该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作 三个常用算法：数字微分法(DDA)中点画线法 Bresenham算法浙江师范大学数理与信息工程学院 计算机图形学数字微分法()假定直线的起点、终点分别为：（xa,ya),(xb,yb)，则斜率m为：m=(yb-ya)/(xb-xa)=dy/dx(x i,yi)(x i+1,yi+k)(x i,int(yi+0.5)栅格交点表示象素点位置。浙江师范大学数理与信息工程学院 计算机图形学数值微分(DDA)法 基本思想 直线的起点和终点分别为(xa,ya),(xb,yb)，
3、斜率m为：m=(yb-ya)/(xb-xa)=dy/dx 直线中每个点坐标由前一点坐标加增量(Dx,Dy)而得到 xi+1=xi+Dx 其中x1=xa yi+1=yi+Dy y1=ya 并且 Dy=mDx 浙江师范大学数理与信息工程学院 计算机图形学数值微分(DDA)法 直线方向的8个象限 在1a取Dx=1,Dy=m;在1b取Dx=1/m,Dy=1;得到 象限|dx|dy|?Dx Dy 象限|dx|dy|?Dx Dy 1a true 1 m 3a true-1-m 1b false 1/m 1 3b false-1/m-1 2a true-1 m 4a true 1-m 2b false-1/
4、m 1 4b true 1/m-1 浙江师范大学数理与信息工程学院 计算机图形学数值微分(DDA)法 二个规律(1)|dx|dy|时，|Dx|=1,|Dy|=m|dx|dy|时，|Dx|=1/m,|Dy|=1(2)Dx、Dy的符号与dx、dy的符号相同 增量算法：在迭代算法中，如果每一步的x、y值是用前一步的值加上增量来获得，则称为增量算法 DDA算法就是一个增量算法浙江师范大学数理与信息工程学院 计算机图形学数值微分(DDA)法#include stdio.h#include graphics.hvoid dda_line(int xa,int ya,int xb,int yb,int c)
5、;void main()int driver=DETECT,mode;int x0,y0,x1,y1,background=WHITE,color=RED;scanf(%d,%d,%d,%d,&x0,&y0,&x1,&y1);initgraph(&driver,&mode,d:tc);setbkcolor(backround);dda_line(x0,y0,x1,y1,color);getch();closegraph();浙江师范大学数理与信息工程学院 计算机图形学数值微分(DDA)法void dda_line(int xa,int ya,int xb,int yb,int c)float
6、delta_x,delta_y,x,y;int dx,dy,steps,k;dx=xb-xa;dy=yb-ya;if(abs(dx)abs(dy)steps=abs(dx);else steps=abs(dy);delta_x=(float)dx/(float)steps;delta_y=(float)dy/(float)steps;x=xa;y=ya;putpixel(x,y,c);for(k=1;k=steps;k+)x+=delta_x;y+=delta_y;putpixel(x,y,c);浙江师范大学数理与信息工程学院 计算机图形学Bresenham画线算法 由DDA算法可知：yi+1
7、=yi+m。由于m不一定是整数，由此式求出的yi也不一定是整数 本算法于1965年由Bresenham提出 在直线生成的算法中，Bresenham算法是最有效的算法之一 令 m=y/x，就0m1的情况来说明Bresenham算法浙江师范大学数理与信息工程学院 计算机图形学Bresenham画线算法 设直线从起点(xa,ya)到终点(xb,yb)。直线可表示为方程y=mx+b，其中 b=y1-m x1,x1=xa,y1=ya m=(yb-ya)/(xb-xa)=dy/dx浙江师范大学数理与信息工程学院 计算机图形学Bresenham画线算法 设(xi,yi)表示直线上当前点A，B是理想直线上的点
8、，下一个表示直线的点到底取图中的C点还是D点，即当xi+1=xi+1时，yi+1取yi+1还是yi?选择的原则取决于y与yi及yi+1的距离d1与d2。x xi ix xi i+1+1y yi iy yi i+1+1C CD DB B y=m(xi+1)+b d1=y-yi d2=yi+1-y如果d1-d20,yi+1取D(yi+1)，否则取C(yi)。因此算法的关键在于求出d1-d2的符号。d1-d2=(y-yi)-(yi+1-y)=2y-2yi-1=2dy/dx(xi+1)-2yi+2b1A Ad1d2浙江师范大学数理与信息工程学院 计算机图形学Bresenham画线算法 取Pi=(d1-
9、d2)dx,经整理，得 Pi=2xidy-2yidx+2dy+(2b-1)dx 由于在1a象限，有dx0，故Pi仍可以用来判断符号 求递推公式 Pi+1=2xi+1dy-2yi+1dx+2dy+(2b-1)dx=2xidy+2dy-2yi+1dx+2yidx-2yidx+2dy+(2b-1)dx=Pi+2dy-2(yi+1-yi)dx 即求得 Pi+1=Pi+2dy-2(yi+1-yi)dx 求初值 Pi中代入x1和y1，得初值 P1=2dy-dx浙江师范大学数理与信息工程学院 计算机图形学Bresenham画线算法 算法思想 1.画点(x1,y1),dx=xb-xa,dy=yb-ya,计算P
10、1=2dy-dx,i=1;2.xi+1=xi+1,如果Pi0，则 yi+1=yi,Pi+1=Pi+2dy；否则 yi+1=yi+1，Pi+1=Pi+2dy-2dx；3.画点(xi+1,yi+1);4.i=i+1,如果idx+1,转2；否则结束 优点 1.不必计算斜率，无除法 2.不用浮点数，只用整数 3.只做整数加/减运算，乘2运算可用移位实现 浙江师范大学数理与信息工程学院 计算机图形学 程序如下：BresenhamLine(int xa,int ya,int xb,int yb,int color)int x,y,dx,dy,p,i;putpixel(xa,ya,color);dx=xb-
11、xa;dy=yb-ya;p=2*dy-dx;x=xa;y=ya;putpixel(x,y,color);for(i=2;i=dx;i+)if(p0)y+;p=p+2*dy;else p=p+2*dy-2*dx;x+;putpixel(x,y,color);Bresenham画线算法浙江师范大学数理与信息工程学院 计算机图形学直角坐标法给定圆心坐标(xc,yc)和半径r,则当x-xc从-r到r加1递增时，可得相应的y值。缺点：浮点运算、开方、取整、不均匀yx浙江师范大学数理与信息工程学院 计算机图形学极坐标法 x=x0+Rcos y=y0+Rsin dx=-Rsin d dy=Rcos d xn
12、+1=x n+dx=x n-Rsin d x n-(y n-y 0)d y n+1=y n+dy=y n+Rcos d y n+(x n-x 0)d 显然，确定x,y的初值及d值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标 缺点：浮点运算、乘法运算、取整运算浙江师范大学数理与信息工程学院 计算机图形学Bresenham画圆算法 下面仅以圆心为(xc,yc)、半径R为整数的圆为例，讨论圆的生成算法 设圆的半径为r，考虑圆心在(0,0)，并从x=0、y=r开始的顺时针方向的1/8圆周的生成过程 如图中的点Pi是已选中的一个表示圆弧上的点，根据弧AB的走向，下一个点应该选择H或者L。显然
13、应选离AB最近的点作为显示弧AB的点PiHLA Bxi xi+1yiyyi-1浙江师范大学数理与信息工程学院 计算机图形学Bresenham画圆算法 y2=r2-(xi+1)2 d1=yi2-y2=yi2-r2+(xi+1)2 d2=y2-(yi-1)2=r2-(xi+1)2-(yi-1)2令判别式为pi=d1-d2，并代入d1、d2，则有 pi=2(xi+1)2+yi2+(yi-1)2-2r2pi的递归式为 pi+1=2(xi+1+1)2+yi+12+(yi+1-1)2-2r2=2(xi+1+1)2+yi+12+(yi+1-1)2-2r2=pi+4xi+6+2(yi+12-yi2)2(yi+
14、1-yi)PiHLyiyyi-1xi xi+1AB浙江师范大学数理与信息工程学院 计算机图形学Bresenham画圆算法pi+1=pi+4xi+6+2(yi+12-yi2)2(yi+1-yi)如果pi0,则pi+1=pi+4xi+6,xi+1=xi+1,yi+1=yi 如果pi0,则pi+1=pi+4xi+6+2(yi+1-yi)(yi+1+yi-1)=pi+4xi+6-2(2yi-2)=pi+4(xi-yi)+10 xi+1=xi+1,yi+1=yi-1,在pi中代入xi=0，yi=r，得到pi的初值p0 p0=2(0+1)2+r2+(r-1)2-2r2=3-2rPiHiLi浙江师范大学数理
15、与信息工程学院 计算机图形学Bresenham画圆算法circle(int xc,int yc,int r,int c)int x,y,p;x=0;y=r;p=3 2*r;while(xy)plot-circle-point(xc,yc,x,y,c);if(p0)p=p+4*x+6;else p=p+4*(x-y)+10;y-=1;x+=1;if(x=y)plot-circle-point(xc,yc,x,y,c);浙江师范大学数理与信息工程学院 计算机图形学 原理：设圆的方程为X2+Y2-R2=0;记 F(x,y)=X2+Y2-R2;假设求得Pi的坐标为(xi,yi)；则当Pi在圆内时-F(
16、xi,yi)向右-向圆外 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)的计算，能否采用增量算法？浙江师范大学数理与信息工程学院 计算机图形学生成圆弧的正负法 若F(xi,yi)已知，计算F(xi+1,yi+1)可分两种情况：1、F(xi,yi)0
17、 xi+1=xi+1，yi+1=yi;F(xi+1,yi+1)=(xi+1)2+(yi+1)2-R2=(xi+1)2+yi2-R2=F(xi,yi)+2xi+1 2、F(xi,yi)0 xi+1=xi，yi+1=yi-1;F(xi+1,yi+1)=(xi+1)2+(yi+1)2-R2=xi2+(yi 1)2-R2=F(xi,yi)-2yi+1 3、初始值：F(0,r)=02+r2-r2=0浙江师范大学数理与信息工程学院 计算机图形学生成圆弧的多边形逼近法?圆的内接正多边形迫近法?圆的等面积正多边形迫近法浙江师范大学数理与信息工程学院 计算机图形学圆的内接正多边形逼近法 思想：当一个正多边形的边
18、数足够多时，该多边形可以和圆无限接近。即 因此，在允许的误差范围内，可以用正多边形代替圆。设内接正n边形的顶点为Pi(xi,yi),Pi的幅角为i,每一条边对应的圆心角为，则有 xi=Rcos i yi=Rsin i浙江师范大学数理与信息工程学院 计算机图形学圆的内接正多边形逼近法 内接正n 边形代替圆 计算多边形各顶点的递推公式 xi+1 Rcos(+i)=yi+1 Rsin(+i)xi+1 cos-sin xi=yi+1 sin cos yi 因为:是常数，sin，cos 只在开始时计算一次所以，一个顶点只需4次乘法，共4n次乘法，外加直线段的中点算法的计算量。浙江师范大学数理与信息工程学
19、院 计算机图形学圆的等面积正多边形逼近法 当用内接正多边形逼近圆时，其面积要小于圆的面积；而当用圆的外切正多边形逼近圆时，其面积则要大于圆的面积。为了使近似代替圆的正多边形和圆之间在面积上相等，只有使该正多边形和圆弧相交，称之为圆的等面积正多边形。浙江师范大学数理与信息工程学院 计算机图形学圆的等面积正多边形逼近法步骤：l求多边形径长，从而求所有顶点坐标值l由逼近误差值，确定边所对应的圆心角 浙江师范大学数理与信息工程学院 计算机图形学椭圆的扫描转换 椭圆方程 x2/a2+y2/b2=1 F(x,y)=b2x2+a2y2-a2b2 椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜
20、率为-1的点作为分界点 椭圆上一点(x,y)处的法向：N(x,y)=(F)x+(F)y=2b2 x+2a2 y浙江师范大学数理与信息工程学院 计算机图形学在上半部分,法向量的y分量大在下半部分,法向量的x分量大上半部分下半部分法向量两分量相等M1M2在上半部分的当前中点，法向量(2b2(xp+1)，2a2(yp-0.5)的y分量比x分量大，即：b2(xp+1)a2(yp-0.5)而在下一个中点，不等式改变方向，则说明椭圆弧从上部分转入下部分浙江师范大学数理与信息工程学院 计算机图形学椭圆的中点画法 与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算判别式的值，由判别式的符号确定更
21、近的点 先讨论椭圆弧的上部分设(xp,yp)已确定，则下一待选像素的中点是(xp+1,yp-0.5)，其相应的判别式为d1=F(xp+1,yp-0.5)=b2(xp+1)2+a2(yp-0.5)2-a2b2浙江师范大学数理与信息工程学院 计算机图形学 根据d1的符号来决定下一像素是取正右方的那个，还是右下方的那个。若d10，中点在椭圆内，取正右方象素，判别式更新为：d1=F(xp+2,yp-0.5)=d1+b2(2xp+3)d1的增量为b2(2xp+3)当d10，中点在椭圆外，取右下方象素，更新判别式：d1=F(xp+2,yp-1.5)=d1+b2(2xp+3)+a2(-2yp+2)d1的增量
22、为b2(2xp+3)+a2(-2yp+2)d1的初始条件：椭圆弧起点为(0，b)；第一个中点为(1,b-0.5)，初始判别式：d1=F(1,b-0.5)=b*b+a*a(-b+0.25)浙江师范大学数理与信息工程学院 计算机图形学 转入下一部分。下一象素是正下方或右下方。下部分的中点判别式及其初始化d2 d2=F(xp+0.5,yp-1)=b2(xp+0.5)2+a2(yp-1)2-a2b2 若d2=0,中点在椭圆外，取正下方像素，d2=F(xp+0.5,yp-2)=d2+a2(-2yp+3)下半部分弧的终止条件为 y=0浙江师范大学数理与信息工程学院 计算机图形学程序：MidpointEllipse(a,b,color)int a,b,color;int x,y;float d1,d2;x=0;y=b;d1=b*b+a*a*(-b+0.25);putpixel(x,y,color);while(b*b*(x+1)a*a*(y-0.5)if(d10)if(d2 0)d2+=b*b*(2*x+2)+a*a*(-2*y+3);x+;y-;else d2+=a*a*(-2*y+3);y-;putpixel(x,y,color);/上部分浙江师范大学数理与信息工程学院 计算机图形学