行业知识
【计算机图形学|直线生成算法】中点画线法
文章目录
- 概述
- 一、基本思想
- 二、构造判别式:
- 三、递推出增量
- 优化:
- 总结:
- 四、例题分析
- 五、伪代���
概述
中点画线法(Midpoint Line Algorithm)是一种画线(Line Drawing)算法,用来在计算机屏幕上绘制线条。
它的基本思想是从线段的起点和终点出发,按照一定的规则向终点逐步逼近,并在途中以控制变量的方式得出每个像素点的坐标,从而绘制出所需的线条。
具体实现中,中点画线法通过计算线段斜率的变化情况,来分为斜率小于1和大于等于1两种情况,并采用Bresenham的对称性原理,以中点的颜色来控制每个像素点的生长方向,从而获得较高的绘制效率和图像质量表现。
总的来说,中点画线法是一种高效且易于实现的线段绘制算法,也是计算机图形学领域最基本的算法之一。
一、基本思想
当前像素点为 ( x p , y p ) (x_p,y_p) (xp,yp),下一个像素点为 P 1 P1 P1或 P 2 P2 P2。
设 M = ( x p + 1 , y p + 0.5 ) M=(x_p+1,y_p+0.5) M=(xp+1,yp+0.5)为 P 1 P1 P1与 P 2 P2 P2之中点, Q Q Q为理想直线与 x = x p + 1 x=x_p+1 x=xp+1垂线的交点。将 Q Q Q与 M M M的 y y y坐标进行比较。
当 M M M在 Q Q Q的下方,则 P 2 P2 P2应为下一个像素点;当 M M M在 Q Q Q的上方,则 P 1 P1 P1应为下一个像素点。
二、构造判别式:
d = F ( M ) = F ( x p + 1 , y p + 0.5 ) = a ( x p + 1 ) + b ( y p + 0.5 ) + c d=F(M)=F(x_p+1,y_p+0.5)=a(x_p+1)+b(y_p+0.5)+c d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c
其中, a = y 0 − y 1 , b = x 1 − x 0 , c = x 0 y 1 − x 1 y 0 a=y_0-y_1, b=x_1-x_0, c=x_0y_1-x_1y_0 a=y0−y1,b=x1−x0,c=x0y1−x1y0.
- 当 d 0时, M M M在 L ( Q L(Q L(Q点 ) ) )上方,取右方 P 1 ( x p + 1 , y p ) P1(x_p+1,y_p) P1(xp+1,yp)为下一个像素;
- 当 d = 0 d=0 d=0时,选 P 1 P1 P1或 P 2 P2 P2均可,约定取 P 1 ( x p + 1 , y p ) P1(x_p+1,y_p) P1(xp+1,yp)为下一个像素;
三、递推出增量
若当前像素处于:
d ≥ 0 d\geq 0 d≥0情况,则取正右方像素 P 1 ( x p + 1 , y p ) P1(x_p+1, y_p) P1(xp+1,yp),要判下一个像素位置,应计算
d 1 = F ( x p + 2 , y p + 0.5 ) = a ( x p + 2 ) + b ( y p + 0.5 ) = d + a d1=F(x_p+2, y_p+0.5)=a(x_p+2)+b(y_p+0.5)=d+a d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)=d+a
增量为 a a a。
d 0,则中点 ( x , y m ) (x_, y_m) (x,ym)在 L ( Q ) L(Q) L(Q)的上方,此时应该取右边的像素点 P 1 ( x p + 1 , y p ) P1(x_p+1,y_p) P1(xp+1,yp),即 x x x加1、 y y y不变。此时, d d d的值增加 d 1 d1 d1,即 d = d + d 1 d=d+d1 d=d+d1。
如果 d 0还是 d (2, 1) -> (3, 2) -> (4, 2) -> P1 (5, 2)
如下图:
五、伪代码
/* mid PointLine */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 if (dx++, y++, d+=d2; } else {x++, d+=d1;} drawpixel (x, y, color); } /* while */ }
上一篇:怎么判断电脑主机性能好坏