计算机图形学——基本图形算法

光栅图形中点的表示

屏幕坐标系在左上角

地址=（Xmax-Xmin)[每行像素点数]*(Y-Ymin)[行数]+(X-Xmin)[行中位置]+基地址

直线扫描转换算法

假设前提：像素间均匀网格，整型坐标系，直线段斜率0<k<1；对于k>1，x，y互换；

数值微分算法（DDA）

y = m x + b y=mx+b y=mx+b

m = ( y 2 − y 1 ) / ( x 2 − x 1 ) , b = ( x 2 y 1 − x 1 y 2 ) / ( x 2 − x 1 ) m=(y2-y1)/(x2-x1),b=(x2y1-x1y2)/(x2-x1) m=(y2−y1)/(x2−x1),b=(x2y1−x1y2)/(x2−x1)

数值微分：

m = △ y / △ x = ( y i + 1 − y i ) / ( x i + 1 − x i ) m=△y/△x=(yi+1-yi)/(xi+1-xi) m=△y/△x=(yi+1−yi)/(xi+1−xi)

void DDALine(int x1,int y1,int x2,int y2){double dx,dy,e,x,y;dx=x2-x1;dy=y2-y1;e=(fabs(dx)>fabs(dy))?fabs(dx):fabs(dy);dx/=e;dy/=e;x=x1;y=y1;for(int i=1;i<=e;i++){SetPixel((int)(x+0.5),(int)(y+0.5));x+=dx;y+=dy;}}

中点画线法

F ( x , y ) = a x + b y + c = 0 F(x,y)=ax+by+c=0 F(x,y)=ax+by+c=0

a = y 0 − y 1 ; b = x 1 − x 0 ; c = x 0 y 1 − x 1 y 0 a=y0-y1;b=x1-x0;c=x0y1-x1y0 a=y0−y1;b=x1−x0;c=x0y1−x1y0

d 0 : F ( x 0 + 1 , y 0 + 0.5 ) , d 0 = a + 0.5 b ; d ≥ 0 : F ( x i + 2 , y + 0.5 ) , 2 d 0 + 2 a ; d < 0 : F ( x i + 2 , y + 1.5 ) , 2 d 0 + 2 a + 2 b d0:F(x0+1,y0+0.5),d0=a+0.5b;d≥0:F(xi+2,y+0.5),2d0+2a;d<0:F(xi+2,y+1.5),2d0+2a+2b d0:F(x0+1,y0+0.5),d0=a+0.5b;d≥0:F(xi+2,y+0.5),2d0+2a;d<0:F(xi+2,y+1.5),2d0+2a+2b

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){x++,y++,d+=d2;}else{x++;d+d1;}drawpixel(x,y,color);}}

Bresenham画线算法

算法与推理与中线画线法类似

void BresenhamLine(int x1,int y1,int x2,int y2){int x,y,dx,dy,p;x=x1;y=y1;dx=x2-x1;dy=y2-y1;p=2*dy-dx;for(;x<=x2;x++){SetPixel(x,y);if(p>=0){y++;p+=2*(dx-dy);}else{p+=2*dy;}}}

圆的扫描转换算法

基本原理：假设已选取Pi-1为第i-1个像素，若Pi-1在圆内，就要向圆外方向走一步；若已在圆外就要向圆内走一步。总之，尽量贴近圆的轮廓线。

基本算法：圆的表示：设圆的圆心为(0,0),半径为R，则圆的方程为：

F ( x , y ) = x 2 + y 2 − R 2 = 0 F(x,y)=x^2+y^2-R^2=0 F(x,y)=x2+y2−R2=0

当点(x,y)在圆内时，F(x,y)<0

当点(x,y)在圆外时，F(x,y)>0

步骤：1. x0=0，y0=R；2. 求得Pi（xi，yi）后找Pi+1的原则：

① 当Pi在圆内时(F(xi,yi)≤0)，要向右走一步得Pi+1，这是向圆外方向走去。取xi+1= xi+1, yi+1= yi

② 当Pi在圆外时(F(xi,yi)>0)，要向下走一步得Pi+1，这是向圆内方向走去，取xi+1= xi, yi+1= yi-1

递推式为：

void Posandneg methods(int R,int p1,int p2,int color){int x,y,x0,y0;x0=p1;y0=p2+R;x=x0;y=y0;int F0=(x0-p1)*(x0-p1)+(y0-p2)*(y0-p2)-R*R;int F1=F0;int F2;while(x<=y){if(F1<=0){F2=F1+2x+1;x=x+1; }else{F2=F1-2y+1;y=y+1;}drawpixel(x,y,color);}}

Bresenham画圆算法

基本原理：假设圆心(0,0)为原点，考虑AB弧的画法，显示一个整圆时，只要在显示AB上任一点(x,y)时，同时显示在圆周上其它七个对称点(y,x), (y,-x), (x,-y), (-x,-y),(-y,-x), (-y,x), (-x,y)。

基本算法：

void BresenhamCircle(int R){int x,y,p;int x=0;int y=R;p=3-2*R;for(;x<=y;x++){SetPixel(x,y);if(p>=0){p+=4*(x-y)+10;y--;}else{p+=4*x+6;}}}

圆的多边形迫近法

基本思想：将整个圆弧等分成一段段的短直线，用这些短直线形成的折线来逼近圆弧。为了获得这些短直线，只需按一定的方式计算给定圆弧轨迹上一系列顶点，短直线的绘制可采用直线的生成算法，如果将圆弧分割的足够密，则短直线将足够短，形成的折线将可以和圆弧接近到任意程度，因此在允许的误差范围内，可以用显示折线代替显示圆弧。

基本算法：

void approachPolygon (int R){int x0,y0,x1,y1,n;double θi,α;θi=0;x0=Rcos(θi)*180/3.14;y0=Rsin(θi)*180/3.14;g.drawpoint(x0,y0);for(α=0.1;α<=1;α=α+0.1){n++;x1=x0cos(α)*180/3.14-y0sin(α)*180/3.14;y1=x0cos(α)*180/3.14-y0sin(α)*180/3.14;g.drawpoint(x1,y1);if(α>=1) α=α-1;if(n>=3600) break;}}

椭圆圆扫描转换算法※

void MidpointEllipse(int a,int b){int x,y;double d1,d2;x=0;y=b;d1=b*b+a*a*(-b+0.25);SetPixel(x,y);while(b*b*(x+1)<a*a*(y-0.5)){if(d1<0){d1+=b*b*(2*x+3);x++;}else{d1+=(b*b*(2*x+3)+a*a*(-2*y+2));x++;y--;}SetPixel(x,y);}d2=b*b*(x+0.5)*(x+0.5)+a*a*(-2*y+3);while(y>0){if(d2>0){d2+=a*a*(-2*y+3);y--;}else{d2+=b*b*(2*x+2)+a*a*(-2*y+3);x++;y--;}SetPixel(x,y);}}