计算机是如何画直线的?简单来说,如下图所示,真实的直线是连续的,但我们的计算机显示的精度有限,不可能真正显示连续的直线,于是我们用一系列离散化后的点(像素)来近似表现这条直线。
(上图来自于互联网络,《计算机图形学的概念与方法》柳朝阳,郑州大学数学系)
接下来的问题就是如何尽可能高效地找到这些离散的点,Bresenham直线算法就是一个非常不错的算法。
Bresenham直线算法是用来描绘由两点所决定的直线的算法,它会算出一条线段在 n 维光栅上最接近的点。这个算法只会用到较为快速的整数加法、减法和位元移位,常用于绘制电脑画面中的直线。是计算机图形学中最先发展出来的算法。
(引自wiki百科布雷森漢姆直線演算法)
这个算法的流程图如下:
可以看到,算法其实只考虑了斜率在 0 ~ 1 之间的直线,也就是与 x 轴夹角在 0 度到 45 度的直线。只要解决了这类直线的画法,其它角度的直线的绘制全部可以通过简单的坐标变换来实现。
下面是一个C语言实现版本。
view sourceprint?
// 交换整数 a 、b 的值
inline void swap_int(int *a, int *b)
{
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
// Bresenham's line algorithm
void draw_line(IMAGE *img, int x1, int y1, int x2, int y2, unsigned long c)
{
// 参数 c 为颜色值
int dx = abs(x2 - x1),
dy = abs(y2 - y1),
yy = 0;
if(dx < dy)
{
yy = 1;
swap_int(&x1, &y1);
swap_int(&x2, &y2);
swap_int(&dx, &dy);
}
int ix = (x2 - x1) > 0 ? 1 : -1,
iy = (y2 - y1) > 0 ? 1 : -1,
cx = x1,
cy = y1,
n2dy = dy * 2,
n2dydx = (dy - dx) * 2,
d = dy * 2 - dx;
// 如果直线与 x 轴的夹角大于45度
if(yy)
{
while(cx != x2)
{
if(d < 0)
{
d += n2dy;
}
else
{
cy += iy;
d += n2dydx;
}
putpixel(img, cy, cx, c);
cx += ix;
}
}
// 如果直线与 x 轴的夹角小于 度
else
{
while(cx != x2)
{
if(d < 0)
{
d += n2dy;
}
else
{
cy += iy;
d += n2dydx;
}
putpixel(img, cx, cy, c);
cx += ix;
}
}
}
可以看到,在画线的循环中,这个算法只用到了整数的加法,所以可以非常的高效。
接下来,我们再来看一看Bresenham画圆算法。
Bresenham画圆算法又称中点画圆算法,与Bresenham 直线算法一样,其基本的方法是利用判别变量来判断选择最近的像素点,判别变量的数值仅仅用一些加、减和移位运算就可以计算出来。为了简便起见,考虑一个圆心在坐标原点的圆,而且只计算八分圆周上的点,其余圆周上的点利用对称性就可得到。
为什么只计算八分圆周上的点就可以了呢?和上面的直线算法类似,圆也有一个“八对称性”,如下图所示。
显然,我们只需要知道了圆上的一个点的坐标 (x, y) ,利用八对称性,我们马上就能得到另外七个对称点的坐标。
和直线算法类似,Bresenham画圆算法也是用一系列离散的点来近似描述一个圆,如下图。
(上图来自于互联网络,《计算机图形学的概念与方法》柳朝阳,郑州大学数学系)
Bresenham画圆算法的流程图如下。
可以看到,与画线算法相比,画圆的循环中用到了整数的乘法,相对复杂了一些。
下面是一个C语言实现版本。
view sourceprint?
// 八对称性
inline void _draw_circle_8(IMAGE *img, int xc, int yc, int x, int y, unsigned long c)
{
// 参数 c 为颜色值
putpixel(img, xc + x, yc + y, c);
putpixel(img, xc - x, yc + y, c);
putpixel(img, xc + x, yc - y, c);
putpixel(img, xc - x, yc - y, c);
putpixel(img, xc + y, yc + x, c);
putpixel(img, xc - y, yc + x, c);
putpixel(img, xc + y, yc - x, c);
putpixel(img, xc - y, yc - x, c);
}
//Bresenham's circle algorithm
void draw_circle(IMAGE *img, int xc, int yc, int r, int fill, unsigned long c)
{
// (xc, yc) 为圆心,r 为半径
// fill 为是否填充
// c 为颜色值
// 如果圆在图片可见区域外,直接退出
if(xc + r < 0 || xc - r >= img->w || yc + r < 0 || yc - r >= img->h)
{
return;
}
int x = 0, y = r, yi, d;
d = 3 - 2 * r;
if(fill)
{
// 如果填充(画实心圆)
while(x <= y)
{
for(yi = x; yi <= y; yi ++)
{
_draw_circle_8(img, xc, yc, x, yi, c);
}
if(d < 0)
{
d = d + 4 * x + 6;
}
else
{
d = d + 4 * (x - y) + ;
y --;
}
x++;
}
}
else
{
// 如果不填充(画空心圆)
while (x <= y)
{
_draw_circle_8(img, xc, yc, x, y, c);
if(d < 0)
{
d = d + 4 * x + 6;
}
else
{
d = d + 4 * (x - y) + ;
y --;
}
x ++;
}
}
}
可以看到,Bresenham画圆算法(中点圆算法)的实现也非常简单。
- 大小: 22.3 KB
- 大小: 18.3 KB
- 大小: 8.2 KB
- 大小: 42.3 KB
- 大小: 32.2 KB
分享到:
相关推荐
特别地,Bresenham直线算法和Bresenham画圆算法分别解决了如何在二维像素屏幕上绘制直线和圆的难题,它们的核心思想在于仅使用整数运算来确定最接近理想直线或圆的像素点位置。 Bresenham直线算法专注于解决在一个...
在MFC中,你可以自定义一个类,包含起点和终点坐标,然后重载OnDraw成员函数来实现Bresenham直线算法的绘制。 Bresenham的画圆算法则利用了中心增量法,通过对半径和偏移量的迭代,决定当前像素是否应该被绘制。与...
Bresenham直线算法和画圆算法都是计算机图形学中非常重要的基础算法。它们不仅能够高效地绘制出所需的图形,而且由于采用了简单的整数运算,因此在性能上具有明显优势。通过理解和掌握这些算法,可以更好地应用于...
3、编程实现利用DDA算法、中点算法和Bresenham算法生成直线,并显示。 同时要求:(1)实现可动态修改直线的起始点坐标和终点坐标 (2)实现可动态选择线的颜色和线宽。 4、编程实现利用1/8圆中点算法和Bresenham...
在VC++下,结合OpenGL实现Bresenham画圆算法可以分为以下几个步骤: 1. **环境配置**:首先,你需要在VC++环境中设置OpenGL开发环境。这通常涉及安装OpenGL库和GLUT(OpenGL实用工具库)或者GLEW(OpenGL扩展加载器...
Bresenham直线算法的核心在于权衡错误增量。对于一条起点为(x0, y0),终点为(x1, y1)的直线,算法通过比较斜率m(y1 - y0 / x1 - x0)和1来确定是优先在x轴还是y轴上递增。如果m > 1,则优先考虑y轴;如果m ,则优先...
计算机图形学DDA、bresenham算法和中点画圆直线
在实现Bresenham画圆算法时,通常会用到两个坐标轴(x, y)的增量dx和dy。对于单位半径的圆,dx = -y,dy = x,这是因为根据勾股定理,(x+1)² + (y)² = (x)² + (y+1)²。在算法的每一步,都会计算当前点和下一个点...
画直线算法有多种,如DDA算法和Bresenham算法。DDA算法(Digital Differential Analyzer)是一种基本的画线算法,通过计算每个像素点的坐标来绘制直线。Bresenham算法是一种改进的画线算法,通过计算每个像素点的...
本知识点主要围绕“直线画法”展开,特别是针对二值图像上的直线绘制,采用了一种高效且精确的算法——Bresenham直线算法。这个算法由John E. Bresenham于1965年提出,广泛应用于计算机图形学领域,它能在像素级别上...
与中点画圆算法相比,Bresenham算法在处理精度上更胜一筹,且避免了浮点运算,使得在硬件资源有限的环境中也能快速执行。 对于椭圆的绘制,中点画圆算法可以被扩展以适应椭圆。椭圆可以被视为两个相交的同心圆,...
实验二"中点Bresenham算法画圆"可能包含了上述代码的实现,以及相关的测试用例,用于验证算法的正确性。通过运行此程序,用户可以观察到以不同半径和位置绘制的圆形图像,从而验证算法的有效性和效率。这种算法的...
Bresenham算法是计算机图形学中的一个经典算法,主要用于高效地在像素级精度下绘制直线和圆。在这个MFC(Microsoft Foundation Classes)项目中,我们利用Bresenham算法来绘制圆,这是一种在VC6.0环境下进行的编程...
中点画圆算法是Bresenham算法的扩展,用于在屏幕上快速绘制圆形。同样避免了浮点运算,它通过计算圆心到当前像素点的距离与半径的差值,决定是否填充当前像素。在`Polygon.cs`或`Circle.cs`中可能会有对应的实现。 ...
3. 中点画圆算法:该算法通过迭代计算每个像素点的坐标,确保每次只画半径为1的一圈像素。核心公式是根据x²/a² + y²/b² = 1(椭圆方程)来判断当前点是否在圆内。首先,找到圆心坐标,然后从(0, r)开始,逐渐向...
接下来是Bresenham画圆算法,它是更广泛使用的一种算法,不仅适用于画圆,还可以用于画直线和其他曲线。Bresenham算法的核心是通过对斜率的增量进行判断,决定下一个像素点应该在当前点的左边还是右边。在画圆的情况...
在这个作业中,我们关注的是几个初级但核心的图形算法:Bresenham直线算法、中点画法画圆、Bezier曲线和种子填充算法,以及如何将它们应用到动画中。 1. **Bresenham直线算法**:这是一种用于在像素化的屏幕上高效...
《小型绘图系统:Bresenham直线算法与画圆算法详解》 计算机图形学是计算机科学中的一个重要分支,它涉及到如何在屏幕上呈现各种几何形状,包括直线、曲线和复杂的图形。本文主要探讨的是Bresenham直线算法,这是一...