《第2章 基本图形的生成与计算--直线、圆、椭圆的生成.ppt》由会员分享，可在线阅读，更多相关《第2章 基本图形的生成与计算--直线、圆、椭圆的生成.ppt（36页珍藏版）》请在三一文库上搜索。
1、浙江师范大学数理与信息工程学院 计算机图形学,第二章 直线、圆、椭圆生成算法,图形的扫描转换(光栅化)：确定像素、显示图形的过程。步骤如下： 确定像素 用图形属性，对像素进行写操作 一维图形，用一个像素宽的直线来显示图形 二维图形的光栅化，即区域的填充：确定像素，填色或图案。 图形的光栅化，必须显示在窗口内，否则不予显示。确定图形的哪些部分在窗口内，哪些在窗口外，即裁剪,浙江师范大学数理与信息工程学院 计算机图形学,图形显示前需要：扫描转换+裁剪 裁剪-扫描转换：最常用，节约计算时间。 扫描转换-裁剪：算法简单；,浙江师范大学数理与信息工程学院 计算机图形学,本章内容,直线的生成算法 圆的生成
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),栅格交点表示象素点位置,。,。,。,。,浙江师范大学数理与信息
3、工程学院 计算机图形学,数值微分(DDA)法,基本思想 直线的起点和终点分别为(xa,ya), (xb,yb)， 斜率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
4、1b false 1/m 1 3b false -1/m -1 2a true -1 m 4a true 1 -m 2b false -1/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算法就是一个增量算法,浙江师范大学数理与信息工程学院 计算机图形学,数值微分(D
5、DA)法,#include “stdio.h“ #include “graphics.h“ void dda_line(int xa,int ya,int xb,int yb,int c); void main() int driver=DETECT,mode; int x0,y0,x1,y1,background=WHITE,color=RED; scanf(“%d,%d,%d,%d“, ,浙江师范大学数理与信息工程学院 计算机图形学,数值微分(DDA)法,void dda_line(int xa,int ya,int xb,int yb,int c) float delta_x,delta
6、_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算法
7、可知：yi+1=yi+m。由于m不一定是整数，由此式求出的yi也不一定是整数 本算法于1965年由Bresenham提出 在直线生成的算法中，Bresenham算法是最有效的算法之一 令 m=y/x，就0m1的情况来说明Bresenham算法,浙江师范大学数理与信息工程学院 计算机图形学,Bresenham画线算法,设直线从起点(xa,ya)到终点(xb,yb)。直线可表示为方程y=mx+b，其中 b=y1-mx1, x1=xa,y1=ya m=(yb-ya)/(xb-xa)=dy/dx,浙江师范大学数理与信息工程学院 计算机图形学,Bresenham画线算法,设(xi,yi)表示直线上当前点
8、A，B是理想直线上的点，下一个表示直线的点到底取图中的C点还是D点，即当xi+1=xi+1时，yi+1取yi+1还是yi? 选择的原则取决于y与yi及yi+1的距离d1与d2。,xi,xi+1,yi,yi+1,C,D,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+2b1,A,d1,d2,浙江师范大学数理与信息工程学院 计算机图形学,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
10、-ya, 计算P1=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; putp
11、ixel(xa,ya,color); dx = xb-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值。 缺点：浮点运算、开方、 取整、不均匀,浙江师范大学数理与信息工程学
12、院 计算机图形学,极坐标法,x = x0 + Rcos y = y0 + Rsin dx = -Rsind dy = Rcosd 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的初值及d值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标 缺点：浮点运算、乘法运算、取整运算,浙江师范大学数理与信息工程学院 计算机图形学,Bresenham画圆算法,下面仅以圆心为(xc,yc)、半径R为整数的圆为例，讨论圆的生成算法 设
13、圆的半径为r，考虑圆心在(0,0)，并从x=0、y=r开始的顺时针方向的1/8圆周的生成过程 如图中的点Pi是已选中的一个表示圆弧上的点，根据弧AB的走向，下一个点应该选择H或者L。显然应选离AB最近的点作为显示弧AB的点,Pi,H,L,A,B,xi xi+1,yi y yi-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(
14、xi+1)2 + yi2 + (yi-1)2 - 2r2 pi的递归式为 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+1-yi),yi y yi-1,xi xi+1,A,B,浙江师范大学数理与信息工程学院 计算机图形学,Bresenham画圆算法,pi+1 = pi + 4xi +6+2 (yi+12-yi2) 2(yi+1-yi) 如果pi0, 则pi+1 = pi + 4xi +6, xi+1= xi+1
15、,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-2r,Pi,Hi,Li,浙江师范大学数理与信息工程学院 计算机图形学,Bresenham画圆算法,circle(int xc, int yc, int r, int c) int x,y,p; x = 0; y =
16、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(xi,yi) 向右 向圆外 Pi在圆外时 F(xi,yi)0
17、 向下 向圆内,生成圆弧的正负法,浙江师范大学数理与信息工程学院 计算机图形学,生成圆弧的正负法,即求得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 xi+1
18、 = 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,浙江师范大学数理与信息工程学院 计算机图形学,生成圆弧的多边形逼近法,? 圆的内接正多边形迫近法 ? 圆的等面积正多边形迫
19、近法,浙江师范大学数理与信息工程学院 计算机图形学,圆的内接正多边形逼近法,思想：当一个正多边形的边数足够多时，该多边形可以和圆无限接近。即 因此，在允许的误差范围内，可以用正多边形代替圆。 设内接正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 因为: 是常数，
20、 sin， cos只在开始时计算一次所以，一个顶点只需4次乘法，共4n次乘法，外加直线段的中点算法的计算量。,浙江师范大学数理与信息工程学院 计算机图形学,圆的等面积正多边形逼近法,当用内接正多边形逼近圆时，其面积要小于圆的面积；而当用圆的外切正多边形逼近圆时，其面积则要大于圆的面积。为了使近似代替圆的正多边形和圆之间在面积上相等，只有使该正多边形和圆弧相交，称之为圆的等面积正多边形。,浙江师范大学数理与信息工程学院 计算机图形学,圆的等面积正多边形逼近法,步骤： 求多边形径长，从而求所有顶点坐标值 由逼近误差值，确定边所对应的圆心角,浙江师范大学数理与信息工程学院 计算机图形学,椭圆的扫描转
21、换,椭圆方程 x2/a2+y2/b2=1 F(x,y)=b2x2+a2y2-a2b2 椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点 椭圆上一点(x,y)处的法向： N(x,y) = (F) x + (F) y = 2b2 x + 2a2 y,浙江师范大学数理与信息工程学院 计算机图形学,在上半部分,法向量的y分量大 在下半部分,法向量的x分量大,上半部分,下半部分,法向量 两分量相等,M1,M2,在上半部分的当前中点，法向量(2b2(xp+1) ，2a2(yp-0.5)的y分量比x分量大，即： b2(xp+1) a2(yp-0.5) 而在下一个中点，不等
22、式改变方向，则说明椭圆弧从上部分转入下部分,浙江师范大学数理与信息工程学院 计算机图形学,椭圆的中点画法,与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算判别式的值，由判别式的符号确定更近的点 先讨论椭圆弧的上部分 设(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(x
23、p+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的增量为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(x
24、p+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) 0) 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); /上部分 ,