基于Bresenham算法的直线脉冲增量插补方法

基于Bresenham算法的反走样直线整数生成算法
牛连强;邵中
【期刊名称】《沈阳工业大学学报》
【年(卷),期】2009(031)006
【摘要】为了实现简单、快速的光滑直线绘制,利用修改的Bresenham直线生成算法,提出了一个完全利用整数运算实现的两点宽像素级反走样直线逐点绘制算法.该算法根据距离差控制参数产生候选点与理想直线间的精确距离,进而控制两个同时被点亮的像素点的亮度.利用区间近似消除了算法中的整数乘除法运算,并利用周期性和对称性提高了算法的效率.分析表明,新算法仅比Bresenham直线生成算法多用几次整数比较运算和簿记工作,具有较高的光滑直线生成速度,且易于硬件和算法语言的实现.
【总页数】5页(P686-690)
【作者】牛连强;邵中
【作者单位】沈阳工业大学,软件学院,沈阳,110023;沈阳工业大学,软件学院,沈阳,110023
【正文语种】中文
【中图分类】TP391
【相关文献】
1.基于Bresenham算法的整数反走样椭圆生成算法 [J], 牛连强;邵中;吴澎
2.一种基于Bresenham算法的直线快速反走样技术 [J], 舒若;张焕春;经亚枝
3.直线与典型曲线的统一反走样整数生成算法 [J], 牛连强;邵中
4.基于Bresenham算法的直线周期性生成 [J], 赵婷婷
5.基于FPGA的反走样直线生成算法研究 [J], 王文栋;李开宇;杨盛亚
因版权原因，仅展示原文概要，查看原文内容请购买。

中点Bresenham算法是一种用于计算在直线上的格点的算法。

它是由Bresenham在1965年提出的，是一种高效的计算机图形学算法，通常用于直线、圆、椭圆等形状的绘制。

通过这篇文章，我们将详细介绍中点Bresenham算法的过程。

1. 背景知识在计算机图形学中，我们经常需要在屏幕上绘制直线、圆、椭圆等形状。

而计算机屏幕上的图像是由像素组成的，因此我们需要一种算法来计算出这些形状上的像素坐标，从而进行绘制。

中点Bresenham算法就是用来解决这个问题的。

2. 中点Bresenham算法的原理中点Bresenham算法的原理是通过巧妙的数学推导，找到离直线最近的像素点，从而确定需要绘制的像素坐标。

该算法通过利用误差项来判断下一个像素点的位置，具有高效、简洁的特点。

3. 中点Bresenham算法的过程中点Bresenham算法的过程可以分为以下几个步骤：3.1 初始化变量：首先需要确定直线的起点和终点，并初始化相关变量，如起点坐标(x0, y0)、终点坐标(x1, y1)、误差项d和增量变化量dx、dy等。

3.2 计算斜率k和误差项初始值：通过计算直线的斜率k，并根据斜率确定误差项的初始值。

3.3 循环计算像素点的坐标：根据误差项的大小，确定下一个像素点的位置，并更新误差项的值，直到绘制完整条直线。

4. 中点Bresenham算法的优势* 算法简洁高效：中点Bresenham算法通过简单的数学计算，即可确定直线上的像素坐标，避免了直接计算斜率导致的浮点数运算，因此在计算速度上具有较大优势。

* 适用范围广泛：中点Bresenham算法不仅适用于直线，还可以用于绘制圆、椭圆等图形，具有良好的通用性。

5. 中点Bresenham算法的应用中点Bresenham算法广泛应用于计算机图形学中的直线、圆、椭圆等图形的绘制。

其高效、简洁的特点使得它成为了计算机图形学中不可或缺的算法之一。

中点Bresenham算法是计算机图形学中的重要算法之一，通过巧妙的数学计算，实现了高效、简洁的直线绘制。

在计算机图形学中，Bresenham算法是一种用于在离散坐标系上绘制直线段的算法。

它是一种高效的算法，能够准确地计算出直线段上的所有像素点，使得在计算机屏幕上显示出直线段来。

Bresenham算法的实现可以帮助我们更好地理解画线原理，并且在计算机视觉、图像处理等领域有着广泛的应用。

1. Bresenham算法的原理Bresenham算法是通过计算直线段的斜率来确定每个像素点的位置。

具体来说，它利用了直线的对称性和整数的特性，通过计算像素点与真实直线的距离来判断下一个像素点应该取的位置。

这样可以避免使用浮点运算，使得算法更加高效。

2. 实现Bresenham算法的关键步骤在实现Bresenham算法时，需要考虑以下几个关键步骤：- 初始化各个变量，包括起始点(x0, y0)和终点(x1, y1)，以及斜率的计算值，例如dx和dy。

- 根据斜率的正负情况，确定每个像素点的增量步长，以便在遍历过程中准确计算出像素点来。

- 利用对称性和整数特性，进行迭代计算，逐步确定直线段上的所有像素点的位置。

3. Bresenham算法的优缺点Bresenham算法作为一种离散直线段插值算法，具有以下几个优点：- 算法简单高效，节省存储空间和运算时间。

- 可以高效地解决像素化显示问题，避免了浮点运算的复杂性。

- 在硬件上实现时，只需少量的资源就能完成计算，适合嵌入式系统和图形处理器。

然而，Bresenham算法也存在一些缺点，比如对于曲线的绘制就不太奏效，因为它是基于直线段的形式来处理的。

4. 我对Bresenham算法的理解在我看来，Bresenham算法是一种经典的离散直线段插值算法，其思想简洁高效。

它通过逐步迭代的方式，计算出直线段上的所有像素点位置，使得在计算机屏幕上显示出直线段来更加精确。

这种算法的实现可以帮助我们更好地理解画线的原理，对于理解计算机图形学和计算机视觉都有着重要的意义。

总结起来，Bresenham算法作为一种高效的离散直线段插值算法，具有着重要的理论和实际价值。

Course PagePage 1 of 6课程首页 > 第二章 二维图形的生成 > 2.1 直线的生成 > 2.1.2 生成直线的Bresenham算法全部隐藏2.1.2 生成直线的Bresenham算法从上面介绍的DDA算法可以看到，由于在循环中涉及实型数据的加减运算，因此直线的生成速度较慢。

在生成直线的算法中，Bresenham算法是最有效的算法之一。

Bresenham算法是一种基于误差判别式来生成直线的方法。

一、直线Bresenham算法描述： 它也是采用递推步进的办法，令每次最大变化方向的坐标步进一个象素，同时另一个方向的坐标依据误差判别式的符号来决定是否也要步进一 个象素。

我们首先讨论m=△ y/△x，当0≤m≤1且x1<x2时的Bresenham算法。

从DDA直线算法可知这些条件成立时，公式(2-2)、(2-3)可写成： xi+1=x i+1 yi+1=y i+m (2－6) (2－7)有两种Bresenham算法思想，它们各自从不同角度介绍了Bresenham算法思想，得出的误差判别式都是一样的。

二、直线Bresenham算法思想之一： 由于显示直线的象素点只能取整数值坐标，可以假设直线上第i个象素点坐标为(xi，yi)，它是直线上点(xi，yi)的最佳近似，并且xi=xi(假设 m<1），如下图所示。

那么，直线上下一个象素点的可能位置是(xi+1，yi)或(xi+1，yi+1)。

由图中可以知道，在x=xi+1处，直线上点的y值是y=m(xi+1)+b，该点离象素点(xi+1，yi)和象素点(xi+1，yi+1)的距离分别是d1和d2：d1=y-yi=m(xi+1)+b-yi d2=(yi+1)-y=(yi+1)-m(xi+1)-b 这两个距离差是 d1-d2=2m(xi+1)-2yi＋2b-1(2－8) (2－9)(2－10)我们来分析公式(2-10)： (1)当此值为正时，d1>d2，说明直线上理论点离(xi+1，yi+1)象素较近，下一个象素点应取(xi+1，yi+1)。

Bresenham快速画3D直线算法--------yangzhengyun一、简述前段时间一个学弟正在做一个LED立方，说想做了送给女友。

但他说在画直线，球，波浪等图案时，总是找不到一个很好的算法，导致显示刷屏很慢甚至出现闪屏的现象，问我有没有什么好的算法。

刚好前段时间我也在弄这个，刚开始的时候，我竟然也被“如何画一条3D直线”难倒了，有的人说——画直线还不简单啊，两个点确定一条直线，那是高中数学里面最简单不过的方程式了。

没错，如果是运用高中的方程式来编程，确实很简单，但是……我们先来看一下直线的方程式吧：如我们知道了两个坐标点：A（x1,y1,z1）,B(x2,y2,z2)。

那么直线的方程是：K=(x-x1)/(x2-x1)＝(y-y1)/(y2-y1)＝(z-z1)/(z2-z1)这就不化简了，但是你们有木有发现一个问题。

对，那就是都是进行浮点运算。

我们试想想，如果是用8位的单片机来做的话，速度不知道将会慢到什么程度了。

且，画直线函数基本可以说是底层的驱动函数，如果一个驱动函数都占据了很多的运行时间的话，上层的代码写的再好也是无用的。

为此我们必须找到一个好的办法，避开浮点运算。

即把浮点数据转换成整形数据进行运算，这样速度可以得到很大的提升。

为此，我们首选的就是Bresenham算法了，它引入了一个误差常量e(即后面用到的ey,ez)，e的值为-1/2；在这个运算思路中，我们还是要用到上面的直线方程做为基础。

所以，在看这个代码的时候，你必须先有这点数学的基本知识才行，不然你看的就云里雾里，两眼冒金星了。

下面帖出的是本人经过上网预览大量资料后，写出的三维基于Bresenham算法的画直线函数，二维的就不贴出了，因为二维的在网上有大把的源码，但是三维现成源码就不多了，当然资料还是有的。

里面的算法，和二维算法的思路是一样的，具体的各位学弟们自己去网上查吧，百度一下“Bresenham算法”够你看了，要有多详细有多详细。

给定两个点起点P1(x1, y1), P2(x2, y2),如何画它们直连的直线呢，即是如何得到上图所示的蓝色的点。

假设直线的斜率0<k>0,直线在第一象限，Bresenham算法的过程如下：1.画起点(x1, y1).2.准备画下一个点，X坐标加1，判断如果达到终点，则完成。

否则找下一个点，由图可知要画的点要么为当前点的右邻接点，要么是当前点的右上邻接点。

2.1.如果线段ax+by+c=0与x=x1+1的交点y坐标大于(y+*y+1))/2则选右上那个点2.2.否则选右下那个点。

3.画点4.跳回第2步5.结束具体的算法如下，原理就是比较目标直线与x+1直线交点的纵坐标，哪个离交点近就去哪个void Bresenhamline(int x0, int y0, int x1, int y1, int color){int x, y, dx, dy;float k, e;dx = x1 - x0;dy = y1 - y0;k = dy / dx;e = -0.5;x = x0;y = y0;for (x= x0;x < x1; x++){drawpixel(x, y, color);//这个是画点子函数e = e + k;if (e > 0){y++;e = e - 1;}}}上述Bresenham算法在计算直线斜率与误差项时用到小数与除法。

可以改用整数以避免除法。

等式两边同时乘以2*dx，得到2*e*dx = 2*e*dx + 2dy, 2*e*dx = 2*e*dx - 2*dx.由于算法中只用到误差项的符号，因此可作如下替换：2*e*dx.改进的Bresenham画线算法程序：将e统一乘以2*dx即变成了整数的Bresenhan算法了，^_^void InterBresenhamline (int x0, int y0, int x1, int y1, int color){int dx = x1 - x0；int dy = y1 - y0；int dx2 = dx << 1;//乘2int dy2 = dy << 1;//乘2int e = -dx;int x = x0；int y = y0;for (x = x0; x < x1; x++){drawpixel (x, y, color);e=e + dy2;if (e > 0){y++;e = e - dx2;}}}。

Bresenham算法是计算机图形学典型的直线光栅化算法。

∙从另一个角度看直线光栅化显示算法的原理o由直线的斜率确定选择在x方向或y方向上每次递增（减）1个单位，另一变量的递增（减）量为0或1，它取决于实际直线与最近光栅网格点的距离，这个距离的最大误差为0.5。

∙1)Bresenham的基本原理o假定直线斜率k在0~1之间。

此时，只需考虑x方向每次递增1个单位，决定y方向每次递增0或1。

设直线当前点为(xi,y)直线当前光栅点为(xi,yi)则下一个直线的点应为(xi+1,y+k)下一个直线的光栅点或为右光栅点(xi+1,yi)（y方向递增量0）或为右上光栅点(xi+1,yi+1)（y方向递增量1）记直线与它垂直方向最近的下光栅点的误差为d，有：d=(y+k)–yi，且0≤d≤1当d<0.5：下一个象素应取右光栅点(xi+1,yi)当d≥0.5：下一个象素应取右上光栅点(xi+1,yi+1)如果直线的（起）端点在整数点上，误差项d的初值：d0＝0，x坐标每增加1，d的值相应递增直线的斜率值k，即：d＝d + k。

一旦d≥1，就把它减去1，保证d的相对性，且在0-1之间。

令e=d-0.5，关于d的判别式和初值可简化成：e的初值e0= -0.5，增量亦为k;e<0时，取当前象素(xi,yi)的右方象素(xi+1,yi)；e>0时，取当前象素(xi,yi)的右上方象素(xi+1,yi+1)；e=0时，可任取上、下光栅点显示。

Bresenham算法的构思巧妙：它引入动态误差e，当x方向每次递增1个单位，可根据e 的符号决定y方向每次递增 0 或 1。

e<0，y方向不递增e>0，y方向递增1x方向每次递增1个单位，e = e + k因为e是相对量，所以当e>0时，表明e的计值将进入下一个参考点（上升一个光栅点），此时须：e = e - 1∙2)Bresenham算法的实施——Rogers 版o通过(0,0)的所求直线的斜率大于0.5，它与x=1直线的交点离y=1直线较近，离y=0直线较远，因此取光栅点(1,1)比(1,0)更逼近直线；o如果斜率小于0.5，则反之；o当斜率等于0.5，没有确定的选择标准，但本算法选择(1,1)（程序）▪//Bresenham's line resterization algorithm for the first octal.▪//The line end points are (xs,ys) and (xe,ye) assumed not equal.▪// Round is the integer function.▪// x,y, ∆x, ∆y are the integer, Error is the real.▪//initialize variables▪x=xs▪y=ys▪∆x = xe -xs▪∆y = ye -ys▪//initialize e to compensate for a nonzero intercept▪Error =∆y/∆x-0.5▪//begin the main loop▪for i=1 to ∆x▪ WritePixel (x, y, value)▪if (Error ≥0) then▪ y=y+1▪ Error = Error -1▪ end if▪ x=x+1▪ Error = Error +∆y/∆x▪next i▪finish∙3)整数Bresenham算法o上述Bresenham算法在计算直线斜率和误差项时要用到浮点运算和除法，采用整数算术运算和避免除法可以加快算法的速度。

基于循环减法加速的多像素Bresenham直线绘制算法李向【摘要】Line drawing algorithm is very important in the computer graphics. It is the most famous algorithm that Bresenham Algorithm uses to draw a straightness line in a smooth fashion. The advantage of classic Bresenham Algorithm is that the operations are all integer numeric without division and decimal fraction. Meanwhile, the disadvantage of the algorithm is that it can just generate one pixel in a computation time and its low in efficiency. In this paper, an accelerated algorithm was proposed, which give full attention to the initiative relation between generation model of line and its linear slope, and it does generate more than one pixel of a line through row of raster display device.The core principle of the improved algorithm is utilizing the coordinate position of both ends of line and the symmetry characteristic for segments. After discussing theory and structure of the improved algorithm, the algorithm implementation and simulation are given at last. And finally, the hardware acceleration in the use of circular subtraction technology based on shift register was briefly described.%直线生成算法是图形的基本元素,也是计算机图形学基础理论的重要内容.Bresenham算法是直线生成算法中最经典的算法,但是它一次计算只能生成一个像素点,效率低下.为了提高直线生成效率,充分利用待生成线段的起点和终点坐标及线段自身的对称性,对Bresenham 算法进行改进,一次计算生成一个像素行.讨论硬件实现该算法的加速方法.【期刊名称】《计算机系统应用》【年(卷),期】2011(020)004【总页数】4页(P245-247,230)【关键词】直线;Bresenham;计算机图形学;多像素;算法【作者】李向【作者单位】郑州航空工业管理学院,计算机科学与应用系,郑州,450015【正文语种】中文直线是图形中最基本的元素之一，直线生成算法是其他各类图形算法的基础，直线绘制算法的好坏对图形应用系统的效率和质量有直接而又重要的关系。

Bresenham算法是计算机图形学典型的直线光栅化算法。

∙从另一个角度看直线光栅化显示算法的原理o由直线的斜率确定选择在x方向或y方向上每次递增（减）1个单位，另一变量的递增（减）量为0或1，它取决于实际直线与最近光栅网格点的距离，这个距离的最大误差为0.5。

∙1)Bresenham的基本原理o假定直线斜率k在0~1之间。

此时，只需考虑x方向每次递增1个单位，决定y方向每次递增0或1。

设直线当前点为(xi,y)直线当前光栅点为(xi,yi)则下一个直线的点应为(xi+1,y+k)下一个直线的光栅点或为右光栅点(xi+1,yi)（y方向递增量0）或为右上光栅点(xi+1,yi+1)（y方向递增量1）记直线与它垂直方向最近的下光栅点的误差为d，有：d=(y+k)–yi，且0≤d≤1当d<0.5：下一个象素应取右光栅点(xi+1,yi)当d≥0.5：下一个象素应取右上光栅点(xi+1,yi+1)如果直线的（起）端点在整数点上，误差项d的初值：d0＝0，x坐标每增加1，d的值相应递增直线的斜率值k，即：d＝d + k。

一旦d≥1，就把它减去1，保证d的相对性，且在0-1之间。

令e=d-0.5，关于d的判别式和初值可简化成：e的初值e0= -0.5，增量亦为k;e<0时，取当前象素(xi,yi)的右方象素(xi+1,yi)；e>0时，取当前象素(xi,yi)的右上方象素(xi+1,yi+1)；e=0时，可任取上、下光栅点显示。

Bresenham算法的构思巧妙：它引入动态误差e，当x方向每次递增1个单位，可根据e 的符号决定y方向每次递增 0 或 1。

e<0，y方向不递增e>0，y方向递增1x方向每次递增1个单位，e = e + k因为e是相对量，所以当e>0时，表明e的计值将进入下一个参考点（上升一个光栅点），此时须：e = e - 1∙2)Bresenham算法的实施——Rogers 版o通过(0,0)的所求直线的斜率大于0.5，它与x=1直线的交点离y=1直线较近，离y=0直线较远，因此取光栅点(1,1)比(1,0)更逼近直线；o如果斜率小于0.5，则反之；o当斜率等于0.5，没有确定的选择标准，但本算法选择(1,1)（程序）▪//Bresenham's line resterization algorithm for the first octal.▪//The line end points are (xs,ys) and (xe,ye) assumed not equal.▪// Round is the integer function.▪// x,y, ∆x, ∆y are the integer, Error is the real.▪//initialize variables▪x=xs▪y=ys▪∆x = xe -xs▪∆y = ye -ys▪//initialize e to compensate for a nonzero intercept▪Error =∆y/∆x-0.5▪//begin the main loop▪for i=1 to ∆x▪ WritePixel (x, y, value)▪if (Error ≥0) then▪ y=y+1▪ Error = Error -1▪ end if▪ x=x+1▪ Error = Error +∆y/∆x▪next i▪finish∙3)整数Bresenham算法o上述Bresenham算法在计算直线斜率和误差项时要用到浮点运算和除法，采用整数算术运算和避免除法可以加快算法的速度。

中点Bresenham算法是一种用于绘制直线的光栅化算法，它可以在计算机图形学中高效地绘制直线，尤其适用于嵌入式系统和低性能设备。

本文将介绍中点Bresenham算法的基本原理和递推公式。

一、中点Bresenham算法的基本原理1.1 数值方式直线的差值算法在了解中点Bresenham算法之前，我们需要先了解数值方式直线的差值算法。

通过计算两个端点的坐标差值，可以得到直线的斜率和步长，从而在光栅化的像素网格上绘制直线。

然而，这种算法需要进行浮点数运算，对于嵌入式系统和低性能设备来说，性能较差。

1.2 中点Bresenham算法的优势中点Bresenham算法通过整数运算和递推公式来高效地绘制直线，避免了浮点数运算的开销，因此在嵌入式系统和低性能设备上具有很高的应用价值。

它利用了直线的对称性和整数坐标的特点，通过逐个像素的递推计算来实现直线的绘制。

1.3 算法的基本思想中点Bresenham算法的基本思想是从直线的起点到终点，在每一步选择最接近直线的像素作为下一个像素，从而逐步绘制整条直线。

通过比较像素的位置和理想直线的位置关系，选择最接近直线的像素进行绘制，从而得到了中点Bresenham算法的递推过程。

二、中点Bresenham算法的递推公式2.1 直线斜率的计算我们需要计算直线的斜率m。

对于给定的两个端点P1(x1, y1)和P2(x2, y2)，直线的斜率可以通过以下公式计算得到：m = (y2 - y1) / (x2 - x1)2.2 中点Bresenham算法的关键递推公式中点Bresenham算法通过比较像素的位置和理想直线的位置关系，选择最接近直线的像素进行绘制。

其关键递推公式如下：对于斜率0 ≤ m ≤ 1的直线：d = 2 * (y - y0) - (x - x0)若d < 0，则选择(x, y)为下一个像素，d = d + 2 * (y1 - y0)若d ≥ 0，则选择(x, y)为下一个像素，d = d + 2 * (y1 - y0) - 2 * (x1 - x0)对于斜率m > 1的直线：d = 2 * (x - x0) - (y - y0)若d < 0，则选择(x, y)为下一个像素，d = d + 2 * (x1 - x0)若d ≥ 0，则选择(x, y)为下一个像素，d = d + 2 * (x1 - x0) - 2 * (y1 - y0)2.3 递推过程通过以上递推公式，我们可以在每一步选择最接近直线的像素进行绘制，从而逐步绘制整条直线。

在数学和计算机图形学中，直线插补算法是非常重要的技术之一。

而第一象限的直线插补算法流程则是其中的一个具体应用。

在本文中，我将详细介绍第一象限的直线插补算法的流程，并共享我对这个主题的个人观点和理解。

让我们了解一下什么是第一象限。

在二维坐标系中，第一象限是指横坐标和纵坐标都大于或等于零的区域。

在直线插补算法中，第一象限通常被用来表示两个点之间的直线路径。

这种算法可以应用在机器人运动控制、计算机数值模拟等领域。

接下来，让我们详细讨论第一象限的直线插补算法流程。

在第一象限中，我们通常使用Bresenham算法来实现直线插补。

这种算法是一种基于像素的算法，可以高效地计算出两个点之间的直线路径。

其基本思想是利用像素点的坐标来逼近真实直线的路径，从而实现直线插补的目的。

具体来说，Bresenham算法的流程包括以下几个步骤：1. 我们需要确定两个点的坐标，在第一象限中通常表示为(x0, y0)和(x1, y1)。

2. 我们计算出直线的斜率k，即k=(y1-y0)/(x1-x0)。

3. 接下来，我们根据斜率的大小来确定下一步要选择的像素点的位置。

具体来说，如果斜率小于1，我们就选择横坐标x的增量为1，纵坐标y的增量为k；如果斜率大于1，我们就选择横坐标x的增量为1/k，纵坐标y的增量为1。

4. 我们利用递归的方式来计算每个像素点的坐标，并根据误差的大小来决定下一个像素点的位置，直到终点被达到。

通过以上流程，我们可以得到第一象限内的两点之间直线插补的路径。

这种算法具有计算速度快、简单易懂的特点，在实际应用中得到了广泛的应用。

另外，我个人认为第一象限的直线插补算法流程不仅可以应用在二维平面内，也可以扩展到更高维度的空间中。

在计算机图形学中，我们经常需要在三维空间中绘制直线路径，而Bresenham算法的思想可以直接应用到三维空间中，从而实现直线路径的插补。

第一象限的直线插补算法流程是一种简单而高效的算法，可以在机器人控制、计算机图形学等领域发挥重要作用。

先标明这转载自/xxxxxx91116/article/details/6295714直线扫描算法之---bresenham改进算法(任何斜率，任何方向)by zxx图形学神马的全都是数学，看来以后我不能搞这个，伤脑筋，所以先把我现在懂得先记录下来吧。

不过呢，我的水平实在有限，对于算法这种东西实在难以说明白，请大家包涵。

书上讲的实在是太过简略，所以这里我把一些简单的推导过程都记录下来：1.重温bresenham未改进算法（斜率在0-1之间的直线）我想要记录的是bresenham改进算法，所以在讲解改进算法之前，我先用一个简单的例子说明一下未改进算法的思想：这是一个斜率k在0-1之间的一条直线，我就用斜率为0-1之间的直线来重温：首先，如图1所示，假设x列的像素已定，其坐标为（x，y），那么下一个坐标一定是：（x+1，y+1）或者（x+1，y）。

而是哪一个取决于d的值，如果d>0.5那么就是（x+1，y+1），如果d<0.5,那么就是（x+1，y），而d是什么呢？当然是斜率了。

（原因如下：y=kx+b当x增加1时：y=kx+k+b所以当x增加1是，y方向的增量是d。

）所以每次我们只需要让d=d+k（k是斜率）即可，当d>=1时，就让d减一，这样就保证了d在0-1之间。

当d>0.5,下一个点取（x+1，y+1）当d<0.5,下一个点取（x+1，y）然后呢，我们为了判断的方便，让e=d-0.5，这样就变成了：当e>0，下一个点取（x+1，y+1）当e<0，下一个点取（x+1，y）2.过渡，重温之后，我们就想要改进，为什么要改进呢？因为我们这里面有0.5，还有k，k里面有dx/dy，这些除法和小数都不是我们想要的，我们想要的是，只有整数，且只有加法的算法，下面就全面讨论一下改进算法。

3.改进算法篇（不同斜率，不同方向）这里，我们主要分为4个角度来说明：A.斜率在0-1只间B.斜率在1-无穷之间C.斜率在0-（-1）之间D.斜率在（-1）-负无穷之间E．两种特殊情况，两条直线。

文章编号:1001-2265(2006)07-0022-04收稿日期:2005-22-01;修回日期:2006-03-06作者简介:石广田(1962—)男,甘肃人,兰州交通大学教授,博士,主要研究方向为机械电子工程、CAD /CAM 等,(E -mail )shigt@mail .lzjtu .cn 。

基于B resenha m 的高效直线生成集成算法石广田1,翟文正2,周维琴3(兰州交通大学信息与电气工程学院,兰州　730070)摘要:在分析传统的B resenha m 画线算法及直线扫描转换的具体要求后,为避开传统算法对整条线段逐点计算、判别的弊端,提出以B resenha m 算法为基础,充分利用直线的对称性、方向性和扫描转换的分段性,设计了一种更具一般性、高效率的直线生成集成算法,提高了各类直线的生成速度。

关键词:计算机图形学;B resenha m 算法;分段扫描;集成算法中图分类号:TP391.4 文献标识码:AA Bresenham —Ba sed I n tegra ted Eff i c i en t L i n e 2Genera ti n g A lgor ith mSH I Guang 2tian,ZHA IW en 2zheng,ZHOU W ei 2qing(I nfor mati on &Electr onic Engineering Depart m ent ,Lanzhou J iaot ong University,Lanzhou 730070,China )Abstract:I n order t o avoid shortcom ings of computati on and measure ment of every p ixel of whole line in B resenha m algorithm ,a ne w line -generating alg orithm based on B resenha m algorithm is br ought f or ward in this paper after the analysis of the traditi onal B resenha m algorithm and require ments in the line scan -conversi on .The ne w algorithm makes full use of the sy mmetry,directi on and p r operty of seg ment in the line -generating p r ocess .A s a ne w integrated algorith m ,it appears general and efficient in every line 2generating app licati on .Key words:computer graphics;bresenha m algorithm;seg ment 2scan;integrated algorith m0　引言图形的生成(亦称扫描转换)是在光栅显示器等数字设备上确定一个最佳逼近于该图形像素集的过程,其本质是将连续量向离散量的转换。

1 引言1.1 各种插补算法的简介1.1.1 脉冲增量插补算法脉冲增量插补又称基准脉冲插补或行程标量插补，其特点是数控装置在每次插补结束时向各个运动坐标轴输出一个基准脉冲序列，控制机床坐标轴做相互协调的运动，从而加工出具有一定形状的零件轮廓的算法。

每个脉冲代表了刀具或工件的最小位移，脉冲的数量代表了刀具或工件移动的位移量，脉冲序列的频率代表了刀具或工件运动的速度。

显然易见，脉冲增量插补算法的输出是脉冲形式，并且每次仅产生一个单位的行程增量，故称之为脉冲增量插补。

而每个单位脉冲对应坐标轴的位移大小，称之为脉冲当量，一般用&表示或BLU表示。

脉冲当量是脉冲分配的基本单位，也对应于内部数据处理的一个二进制位，它决定了数控机床的加工精度，对于普通数控机床一般δ=0.01mm，对于较为精密的数控机床一般取δ=0.005mm、0.0025mm或0.001mm等。

这类插补算法比较简单，通常仅需几次加法和移位操作就可完成，比较容易用硬件实现，这也正是硬件数控系统较多采用这种算法的主要原因。

当然，也可用软件来模拟硬件实现这类咋不运算。

通常，属于这类插补算法的有：数字脉冲乘法器、逐点比较法、数字积分法以及一些相应的改进算法等。

一般来讲，脉冲增量插补算法较适合于中等精度（如0.1mm）和中等速度（如1～3m/min）的机床数控系统中。

由于脉冲增量插补误差不大于一个脉冲当量，并且其输出地脉冲频率主要受插补程序所用时间的限制，所以，数控系统精度与切削速度之间是相互影响的。

例如实现某脉冲增量插补算法大约需要40us的处理时间，当系统脉冲当量为0.001mm时，就可求得单个运动坐标轴的极限速度约为1.5m/min。

进一步当要求控制两个或两个以上坐标轴时，所获得的轮廓速度还将进一步降低。

反之，如果将系统单轴极限速度提高到15m/min，则要求将脉冲当量增大到0.01mm[1]。

1.1.2 数据采样插补法随着数控系统中计算机的引入，大大缓解了插补运算时间和计算机复杂性之间存在的矛盾，特别是高性能直流伺服系统和交流伺服系统的研制成功，为提高现代数控系统的综合性能创造了充分的条件。

第13卷　第1期2008年1月中国图象图形学报Journal of I m age and GraphicsVol .13,No .1Jan .,2008收稿日期622;改回日期622第一作者简介贾银亮(～　)男。

年获南京航空航天大学测试计量技术及仪器专业硕士学位。

现为南京航空航天大学自动化学院测试工程系讲师,在职博士研究生。

主要从事计算机图形学和总线技术方面的研究。

2f y @63Br esenham 直线生成算法的改进贾银亮　张焕春　经亚枝(南京航空航天大学自动化学院,南京　210016)摘　要　直线是图形的基本元素,研究其生成算法具有重要意义。

由于经典的B resenha m 直线生成算法一次计算只能生成一个像素点,效率较低。

为了提高直线生成效率,通过对其进行改进,提出了一种利用直线前两行像素行的像素点数目来计算其余各像素行的像素点数目的算法。

该算法在保持B re s enham 算法不使用取整和小数运算的优点下,还提高了直线生成效率,一次计算可以生成一个像素行。

关键词　计算机图形学　B resenham 算法　判定变量中图法分类号:TP391.41 文献标识码:A 文章编号:100628961(2008)0120158204A M od i f i ed Br esenham A lgor ith m of L i n e Dra w i n gJ IA Yin 2liang,ZHANG Huan 2chun,J ING Ya 2zhi(Nanjing U niv ersity of Aeronaut i cs &Astronautic s,Nanji ng 210016)Ab stra ct B re senham alg orit hm is the most fundamental algorith m for drawing line seg ments in co mputer graphic s .Canoni 2cal B re senham alg orith m can only g enerate one pixel of a line each ti m e .We proposed a new method by i m p r oving it i n a nove l way,which can gene ra te p ix e l of a line r ow by ro w according t o the first and second r ow of a line and i nhe rit the ad 2vantage s of B resenham alg orith m with out divisi on and dec i m al fracti on .F inally,its efficiency has been proved to be much bette r than thos e existing m ethods .Keywor ds co mputer graph i c s,B re senham alg orith m,de ter m inant va riable1　引　言由于直线是生成各种图形的基本元素,且直线生成算法是其他各类图形算法的基础,因此,目前直线的生成算法已得到了人们广泛的研究,并已出现了许多有效的算法。

直线的中点Bresenham算法
王芳;王正兰
【期刊名称】《电脑知识与技术》
【年(卷),期】2011(007)004
【摘要】直线Bresenham算法的基本原理是采取对整型参量的符号进行检测,整型参量的值正比于两像素与实际线段之间的偏移.直线的中点Bresenham算法是依据下一个点可能出现的两个点的中间点处在直线的位置来判断下一个点的取舍.【总页数】2页(P825-826)
【作者】王芳;王正兰
【作者单位】工程兵指挥学院,江苏徐州221004;工程兵指挥学院,江苏徐州221004
【正文语种】中文
【中图分类】TP312
【相关文献】
1.基于Bresenham算法的反走样直线整数生成算法 [J], 牛连强;邵中
2.基于Bresenham算法的数控打标机中直线运动控制的实现 [J], 杨月婷;陈昕;任哲平
3.抛物线的中点Bresenham算法 [J], 孙靖
4.基于Bresenham算法的快速直线脉冲增量插补算法 [J], 王宝仁;李金松;吕国娜;董洁
5.串联型机械臂直线轨迹规划Bresenham算法应用与改进 [J], 张岩;过仕安;李争;安国庆;薛智宏;盖祥虎
因版权原因，仅展示原文概要，查看原文内容请购买。

一种快速直线脉冲增量插补算法
张庆丰;周继鹏
【期刊名称】《计算机应用》
【年(卷),期】2005(025)006
【摘要】提出了一种应用于数控加工的快速空间直线脉冲增量插补算法.该算法在插补过程中只进行整数运算,每次插补计算可以得到两个进给步的三坐标轴进给脉冲增量.提高了直线插补的运算效率,而误差小于O.707个脉冲当量.
【总页数】2页(P1420-1421)
【作者】张庆丰;周继鹏
【作者单位】暨南大学,计算机系,广东,广州,510632;暨南大学,计算机系,广东,广州,510632
【正文语种】中文
【中图分类】TP391.41
【相关文献】
1.一种简捷的快速直线插补新算法 [J], 叶秀云;朱文;田刚
2.基于Bresenham算法的直线脉冲增量插补方法 [J], 郭晋峰;吴寒;刘雄伟
3.一种快速高精度的直线插补算法—网格法 [J], 谭翰墨;钟应善
4.脉冲增量法直线插补算法的改进 [J], 徐建方
5.基于Bresenham算法的快速直线脉冲增量插补算法 [J], 王宝仁;李金松;吕国娜;董洁
因版权原因，仅展示原文概要，查看原文内容请购买。