Talk:Bresenham's line algorithm

Untitled

I miss two things in this article:

• the applications of this algorithm. I understand what the algorithm could be used for, but I'm pretty sure not everybody will
• an explanation of how it works and/or comments in the code

I don't know the algorithm myself, so I'll leave it to somebody else. Jeronimo 14:36 Jul 25, 2002 (PDT)

I agree and hope that more is contributed. I'll comment my code a little bit later and see what I can do for a small history section and applications section a bit later today. I'd add that it would be nice to see articles for other line algorithms. Rlee0001 15:20 Jul 25, 2002 (PDT)

If you want comments, try [1]. (Disclaimer, this is my own code.) Note that the article used a slope/intercept equation for the line, and therefore has some "fiddly" detail. The example I point to uses homogenous coordinates, so has no special cases. It also has at the end a common variant that directly draws anti-aliased lines. This is the variant that puts out dots on a screen. It also incorporates the change recommended by Tran Thong, to insure exactly the same dots independent of line direction that used to be needed for the "erase by drawing black in the reverse order" used in early graphics as part of dragging line segments around. Interesting how such history is being lost for something that used to be used a lot. Floating point was expensive, integer cheaper, so the standard procedure used to be to convert the points to the final integer calcomp coordinates and do as my example did. I don't think I ever saw a production version using floating point. The article could also point out the uses of the algorithm in non-graphics contexts. And people might be interested in the "restartable" variant that was used to make a exactly the same dots when putting a graphic out in strips as when done as a whole. Ahhh... history. Nahaj 23:33, 14 November 2005 (UTC)

Calcomp plotter application

Since the Bresenham algorithm is primarily applicable to raster devices, the initial use of it on Calcomp plotter devices (that can inherently draw straight lines by pen movements) is not clear. Rendering of "dotted" lines is probably the way that the algorithm was used with plotters, but I'm not sure. Can anyone provide the answer? - Bevo 13:07, 25 Jul 2004 (UTC)

It turns out that the early Calcomp plotters were "incremental" in nature, thus requiring an algorithm like Bresenham's. See http://www.pdp8.net/563/563.shtml Calcomp 563 Incremental Plotter Information - Bevo 20:52, 29 Jul 2004 (UTC)

And they could lose increments under a number of conditions. Hence the "trick" of many plot libraries of the time of drawing part of a registration symbol in some corner at the start, and the rest of it at the end of the plot. If the symbol was correct you had some assurance that the plot was plotted normally, otherwise if the parts were offset, or garbled, there was an error of SOME sort. Nahaj 23:33, 14 November 2005 (UTC)

deltaerr unnecessary

I think that after multiplying the equations by deltax the variable deltaerr becomes unneccessary, since it just equals deltay. Replacing deltaerr by deltay would simplify the code and would also bring it closer to other implementations, for example that in F.S.Hill: Computer Graphics Using OpenGL. But anyway thanks for this article, it is so far the best and simplest explanation of the algorithm I have seen.

Why is Positive Y Downwards?

X increases to the right, as is normal, but Y is increasing downwards rather than upwards. I realise it just depends on whether the origin (0, 0) is in the top-left or bottom-left corner, but it does seem that this choice is causing confusion, hence the incorrect "This first version only handles lines that ascend to the right", shouldn't it be descend? I'd suggest that +X == right, +Y == up will be more familar to the layman that comes from cartesian coordinates in maths at school without them having to mentally flip along the X axis. -- Ralph Corderoy 11:36, 3 December 2006 (UTC)

Postive y = down seems to be the dominant convention in computing. Plugwash 11:25, 4 December 2006 (UTC)

Just think of it as quadrant IV of a graph. Jamestheprogrammer 15:21, 10 March 2007 (UTC)

Plugwash is right, the Y axis increases downwards (in C++) --Shreyasjoshis 05:28, 21 April 2007 (UTC)

This standard likely arose due to the fact that standard CRT monitors render the screen from top to bottom and so implementing a graphical mode with Y rising towards the top of the screen would require--at the simplest--making X rise towards the left, and reversing the data order somewhere before it gets fed out the VGA port. A solution with +X being right and +Y being up would require some more complex method which reverses the order of lines, but not the order of pixels.Upthorn 05:37, 14 May 2007 (UTC)

It's probably also due to the fact that text is written starting at the top left hand corner of the page, going downwards as it progresses. For example consider how you initialise an array of memory in C. The first location is initialised first and the next ones across/down the page. If positive Y wasn't downwards everything would be upside down. By the way, you can easily flip between the two formats by just by doing "plot( x, (YRES-1)-y )" instead of "plot( x ,y )" 77.103.105.67 (talk) 11:54, 6 May 2020 (UTC)

Computer language

What computer language is the code in this article in? — Brim 07:59, Feb 9, 2005 (UTC)

It is written in a pseudocode called Wikicode. Is there any part that isn't clear to you? Deco 18:23, 9 Feb 2005 (UTC)

Thank you for the explanation. The pseudocode examples are clear and easy to follow. I just wasn't sure if the examples on this page were supposed to be in a specific computer language or what since I had never encountered Wikicode before. Now I understand. Perhaps it would be more clear if we said somewhere in the article "This is a Wikicode example," but I looked at other articles implementing Wikicode and the precedent seems to be not to make a statement like that. — Brim 18:45, Feb 9, 2005 (UTC)

The template {{wikicode}} placed in each of these articles used to say exactly this. I removed the message from the template due to political pressure — there was violent objection to the concept of a standard pseudocode. If you feel it's appropriate, you may re-add the message yourself at Template: Wikicode. Deco 07:36, 10 Feb 2005 (UTC)

Floating point

in the line drawing algorithm article it is claimed that this avoids floating point arithmetic yet the code here clearly doesn't. Please clarify. Plugwash 21:44, 20 March 2006 (UTC)

Ahh just noticed the last section "optimising", i think i'll clarify things a bit so others don't miss it though. Plugwash 22:19, 20 March 2006 (UTC)

Hm.. I see that it could be confusing. The first version is only there for pedagogical purposes, as it illustrates the algorithm better. I hope you don't mind I've moved your clarification down a little bit, as I think the intro should probably just give a highlevel overview. Henrik 13:57, 21 March 2006 (UTC)

Final Optimized Code

For what it's worth, I converted the final optimized pseudo-code into a C++ routine. Did a faithful line-by-line implementation, I believe. Bottom line: it didn't work. Some octants of the plane worked fine. Others would only produce 45-degree lines. Went back and checked and re-checked my implementation. It was doing everything the pseudo-code said to do, and in the same order (as far as I could tell).

Went to a different website and converted their pseudo-code version into a C++ implementation. It works perfectly. Might want to double check this Wiki's pseudo-code to see if it really is correct.

It should be noted that the supplied algorithm only works when (x1, y1) specifies the top left point of the line and (x2, y2) the bottom right. Reference implementation below should be a 1:1 port of the pseudo code (to C++). PrisonerOfPain 23:32, 20 September 2006 (UTC)

The C code currently on the article didn't work for me either, with the same problem you described. Why does the code below say it's incorrect? Does it not work either? Dood77 (talk) 18:12, 29 November 2007 (UTC)

I haven't actually tested the code, but I'm pretty sure the main error comes from the ABS abd SWAP; try using functions instead of macros, or at least put brackets, e.g.

1. define ABS(x) ((x) < 0?-(x):(x))

-ElNinyo, 28. April 2008 —Preceding unsigned comment added by 87.126.153.152 (talk) 11:43, 28 April 2008 (UTC)

I think you must read the SWAP bug reported to gcc at [2] —Preceding unsigned comment added by 193.147.222.244 (talk) 18:00, 10 February 2009 (UTC)

// NOTE: THIS IMPLEMENTATION IS INCORRECT!

#define ABS(x) (x < 0 ? -x : x)
#define SWAP(x, y) (x ^= y ^= x ^= y)
void LineDrawer_Bresenham::Draw(int x1, int y1, int x2, int y2, int color){
	bool steep = ABS(y2 - y1) > ABS(x2 - x1);

	if(steep){
		SWAP(x1, y1);
		SWAP(x2, y2);
	}

	if(x1 > x2){
		SWAP(x1, x2);
		SWAP(y1, y2);
	} 

	int dx = x2 - x1;
	int dy = ABS(y2 - y1);
	int error = 0;
	int ystep;
	int y = y1;

	if(y1 < y2){
		ystep = 1;
	}else{
		ystep = -1;
	}

	for(int x = x1; x < x2; x++){
		if(steep){
			buffer[y + x * SCRWIDTH] = color;
		}else{
		 	buffer[x + y * SCRWIDTH] = color;
		} 

		error += dy;
		if(2 * error >= dx){
			y += ystep;
			error -= dx;
		}
	}
}

-- anonymous

The implementation of the "SWAP" macro in the above code is incorrect, as explained in XOR swap algorithm and [3]. Some good C compilers will compile that implementation into something that does not give the expected results.

The implementation of the "ABS" macro in the above code is incorrect, as explained in Wikibooks: C Programming/Preprocessor#.23define. A good C compiler will always compile that implementation into something that returns "-3" when given "1-2", which is not what we want.

There are many ways to implement "SWAP" and "ABS" correctly. For example, in C++,

#define SWAP(x, y) std::swap(x,y)
#define ABS(x) std::abs(x)

or, in C,

#define ABS( x ) ( ((x) < 0) ? -(x) : (x) )
#define SWAP(x, y) { int temp = x; x = y; y = temp; } /* assume x and y are int */

or, if you insist on being "clever",

#define ABS( x ) ( ((x) < 0) ? -(x) : (x) )
#define SWAP(x, y) { x ^= y; y ^= x; x ^= y; } /* assume x and y do not refer to the same memory location */

Once those are fixed, a 1:1 translation of the "optimized" pseudo-code currently in the article to C seems to give the correct results for me.

Resolved

--68.0.124.33 (talk) 19:06, 23 November 2010 (UTC)

Circle Variant

I felt so free to add this chapter as a direct translation from the german version, where I also contributed this and some other parts. As my mother tongue is not English, someone might want to go over the wording of this new chapter and turn it more into real English... Also the initial description of the algorithm and the illustration differs severely in the german version, perhaps we can throw it all together and extract the best of both. de:PeterFrankfurt, 4 February 2007 —The preceding unsigned comment was added by 84.177.118.110 (talk) 15:08, 4 February 2007 (UTC).

I think the C code should have this at the end instead of what is there:

 if (y>=x){
    setPixel(x0 + x, y0 + y);
    setPixel(x0 - x, y0 + y);
    setPixel(x0 + x, y0 - y);
    setPixel(x0 - x, y0 - y);
    if (y>x){
        setPixel(x0 + y, y0 + x);
        setPixel(x0 - y, y0 + x);
        setPixel(x0 + y, y0 - x);
        setPixel(x0 - y, y0 - x);
    }
 }

This prevents pixels from being plotted twice. I'm not sure if it causes any problems though, that's why I added it here.

Well, this is only a problem for (maximum) 4 pixels in the whole circle (in 50 % of the cases 0 pixels), I for my person can live with this redundancy. --PeterFrankfurt 17:19, 10 March 2007 (UTC)

Not about Bresenham's Algorithm

Most of this article is NOT about Bresenham's algorithm, but about various other DDA algorithms that are variations of it, or generalizations of it. I would recommend that this article be renamed DDA or Digital Differential Analyzers, and it be made clear which algorithms are actually Bresenhams (mostly just the first bit), and which, such as the midpoint generalization are due to later computer scientists.

For example the "Different Approach" is the midpoint DDA algorithm and is due to Pitteway: Pitteway, M.L.V., "Algorithm for Drawing Ellipses or Hyperbolae with a Digital Plotter", Computer J., 10(3) November 1967, pp 282-289

Van Aken (Van Aken, J.R., "An Efficient Ellipse Drawing Algorithm", CG&A, 4(9), September 1984, pp 24-35) showed that the midpoint algorithm produces the same output as Bresenham's. Swestrup 17:59, 28 February 2007 (UTC)

Ok, so I changed this and tried to attribute these parts more correctly. Yet I think we should leave this together under the label Bresenham, because this is what will be searched for by interested people. --PeterFrankfurt 14:03, 2 March 2007 (UTC)

I think the original point still stands. The title of the article is "Bresenham's line algorithm". I don't see a problem with including the other content on the work by Pitteway and Van Aken in some other, more general article on line and circle drawing (or, given the level of technical detail, perhaps in their own articles). Those articles could certainly be linked from here. But I don't think that stuff belongs in this article. "Interested people" will still be able to find the other algorithms via the in-article wikilinks, while this article will regain some focus. --Allan McInnes (talk) 06:36, 18 May 2007 (UTC)

Computing the decision parameter

UNderstanding the Computation of the decision parameter that the mid point circle, ellipse algorithms use is very important to grasp the algorithm fully, and for completeness.-Weedrat 16:23, 29 April 2007 (UTC)

Changed Circle Pseudo Basic example

Having implemented the circle variant in AVR assembler, using the BASIC example as a starting point I find two interesting things (both proven by running the example code in BBC Basic for windows as well):

First, calculating Y^2 and X^2 is totally redundant; OK it shows how the calculated values relate back to Pythagorus' theorem, but they are a waste of processor time if people understand this as a real-world example.

Second, in porting to a non-floating point environment I calculated Y-end by multiplying r by root-2 * 65536, then discarding the lowest two bytes of the result. Fair enough, but the end point of the octant is the point where increasing y and decreasing x become equal. yend need not be calculated and the while-wend loop test can be y<=x. This avoids any floating-point calculation at all, indeed it avoids the calculation of a surplus value altogether.

I can't see any issues with this any comments? (Other than my bad spelling, now corrected)

You are completely right, the calculations of Y^2 and X^2 are unnecessary, and yend can be replaced by the test for y<=x. Let's see what optimizations will come next. Good point. --PeterFrankfurt 00:08, 9 May 2007 (UTC)

Even faster version of circle drawing

I have added some stuff relating computing square of number by sum of N odd number, counting from 1. See square_number. I found mention on this technique on folklore.org. Macintosh stories site. There was mentioned that this idea lied behind implementation of circle routine. I believe that Bill_Atkinson stayed behind it.

I tried to implement it myself. Came with some code. Then tried to find some way to save threshold $r*r-y*y$. I came only with computing y the same way as x. By sum of odd series. It must be possible to do it even better, i told myself.

Seeing what was on this page gave me more insight. That it relates to bresenham.

 void raster_circle(int x0, int y0, int radius)
 {
  int error = 1 - radius;
  int nextodd_x = 0;
  int nextodd_y = -2 * radius - 1;
  int x = 0;
  int y = radius;

  draw initial quad of pixels
  while ( x < y ) {

I realized that in y cycle it is about getting odd numbers from this seria from far end.

   /* prepare next odd from far end and decrease by it */
    if ( error >= 0 ) {
      y--;
      nextodd_y += 2;
      f += nextodd_y;
    }
    x++;

I also realized that in x cycle it is about gettin just next odd number.

    /* increase by next od from */
    nextodd_x += 2;
    f += nextodd_x;
 
    draw proper eight pixels
  }
}

I conclude this by giving my pseudo relation. This one $x(ydelta)=y(xdelta)$ can be composed to $x(nextodd_{y})=y(nextodd_{x})$.

The slope of the line is wrong

The article assumes an inverted coördinate system, a line going slightly downward, and it says "(that is, the line has a slope greater than -1 and less than 0.)". These three assertions cannot all be true.

• If the first two are true, then the slope must be in <0, 1>
• If the first and last are ture, the line must go slightly upward.
• If the last two are true, the coördinate system must not be inverted.

Make up your mind and fix it. Cheers, Shinobu 15:56, 19 May 2007 (UTC)

As of Apr 12, 2017 the slope is still claimed to be negative when y1 > y0 (and x1>x0). This occurred in the 3rd paragraph of the Method section. The offending line was:"...(the line has a negative slope whose absolute value is less than 1)." I am correcting it. For writers who are unable to grasp the fact that increasing y as x increases always means the slope is POSITIVE (in this coordinate system this means as x increases to the right →, y increases downward ↓ ) then please refrain from editing it. Thanks98.21.215.86 (talk) 19:22, 12 April 2017 (UTC)

It won't even work for some lines going to the right down

I'd like to note that these line drawing algorithms posted by PrisonerOfPain and the Bresenham's line algorithm discussed in the article will not even work for some lines going right down. Here is an example, line start at [1,1] and ends at [3, 25] the line is going right down(in the raster coordinate system), as you will see you'll loop only 2 times drawing only two pixs. There should be another loop for drawing all the Y axis pixs or you might want to calculate the ratio of the dx/dy and take that into account when looping from x1 to x2. I'm in the middle of the exams right now so I'll through my line drawing algorithm a bit later.

Fomas 02:03, 24 May 2007 (UTC)

The article now specifically points out that the first pseudo-code example does not properly handle those cases. The "generalized" and "optimized" pseudo-code examples currently in the article use a "steep" flag, and as far as I can tell have been fixed-up to handle all the cases you mention.

Resolved

--68.0.124.33 (talk) 19:06, 23 November 2010 (UTC)

General Line drawing algorithm

The following algorithm allows you to draw any straight line with any slope. Note that it can be optimised by drawing pixels from both ends to the middle.

Function drawLine(x1, y1, x2, y2)
   int dX = Abs(x2 - x1)
   int dY = Abs(y2 - y1)
   int x = x1
   int y = y1

   If (x1 > x2) Then offsetX = -1 Else offsetX = 1
   If (y1 > y2) Then offsetY = -1 Else offsetY = 1

   SetPixel(x,y)

   If (dX > dY) Then
       int error = dX / 2

       While (x != x2)
           error = error - dY

           If (error < 0)
               y = y + offsetY
               error = error + dX
           End If

           x = x + offsetX

           SetPixel(x,y)
       Wend
   Else
       int error = dY / 2

       While (y != y2)
           error = error - dX

           If (error < 0)
               x = x + offsetX
               error = error + dY
           End If

           y = y + offsetY

           SetPixel(x,y)
       Wend
   End IF
   End If
End Function

Fomas 00:00, 26 May 2007 (UTC)

This does actually seem to work, tested by converting it to x86 assembly. 83.21.28.61 (talk) 11:16, 10 March 2008 (UTC)

Works for me too.. converted to C. Thanks! --JeffryJohnston (talk) 22:42, 4 May 2008 (UTC)

The above does NOT work! It is not even syntactically correct as there is an extra END IF before the END FUNCTION. Also there is an extra section in the Java below for the case where dX = dY which is missing from the above. When you document algorithms, you need to make sure that the documentation is correct or it is pointless. This is the best reason for using a real language rather than a pseudo code. Real languages have implementations so that things written in them can be tested. The better ones have formal semantic definitions and can be reasoned about mathematically. Pseudo codes tend to have neither of these things. —Preceding unsigned comment added by 86.138.15.151 (talk) 22:31, 28 March 2010 (UTC)

This is the java version, for anyone who's interested...

public void  drawLine(int x1, int y1, int x2, int y2){
	   Point2D.Double[] pixels = new Point2D.Double[Math.abs(x1 - x2) + Math.abs(y1 - y2)];
	   int dX = Math.abs(x2 - x1);
	   int dY = Math.abs(y2 - y1);
	   int x = x1;
	   int y = y1;
	   int offsetY;
	   int offsetX;
	   int counter = 0;
	   
	   
	   
	if (x1 > x2)  offsetX = -1; 
	else if(x2 > x1) offsetX = 1;
	else offsetX = 0;
	   
	if (y1 > y2)  offsetY = -1; 
	else if(y2 > y1) offsetY = 1;
	else offsetY = 0;

		pixels[counter] = new Point2D.Double(x, y);


	   if (dX > dY){
	       int error = dX / 2;

	       while (x != x2){
	    	   counter ++;
	           error = error - dY;

	           if (error < 0){
	               y = y + offsetY;
	               error = error + dX;
	           }

	           x = x + offsetX;

	           pixels[counter] = new Point2D.Double(x, y);
	       }
	   }
	   else if(dY > dX){
	       int error = dY / 2;

	       while (y != y2){
	    	   counter ++;
	           error = error - dX;

	           if (error < 0){
	               x = x + offsetX;
	               error = error + dY;
	           }

	           y = y + offsetY;

	           pixels[counter] = new Point2D.Double(x, y);
	       }
	   }
	   else if(dX == dY){
		   while(x != x2){
			   x++;
			   y++;
	           pixels[counter] = new Point2D.Double(x, y);
		   }
	   }

	}

Please note that the array limits are not by any means accurate; however, they are large enough to contain the line. 192.84.113.70 (talk) 17:34, 14 July 2008 (UTC)Me,Myself,andI

Sum of First n Odd Numbers

Is that discussion particularly relevant? I'd opt for deletion... semanticprecision 15:53, 6 July 2007 (UTC)

Sorry state of article

This article is a mess now - We have two alternate descriptions of the same algorithm, a better approach would have been to instead modify the original content to incorporate the new info. So now we have what basically is a content fork in the same page. I'm tempted to move the second description into a sandbox, so we can move the useful bits back into the article piece by piece. If no one objects, I'll most likely do this in a day or two. henrik•talk 11:28, 9 August 2007 (UTC)

Errata

The C version of the algorithm is incorrect. It cannot draw lines where dy > dx. That's due to the simple fact that it's not including the "steep" variable which is used in the code above it. 91.89.169.47 (talk) 23:51, 10 January 2008 (UTC)

Moved the removed circle algorithm

Midpoint circle algorithm used to point to the "Circle variant" section in this article. The section was removed but I now moved that section to a new article. Not sure if that is the most used name for that algorithm so please make appropriate changes if you know better. Lakeworks (talk) 20:56, 12 January 2008 (UTC)

For more information on this topic click on the link below http://signalspot.com/2008/01/14/a-novel-and-accurate-method-for-circular-object-identification-combined-approach-of-hough-transform-eigen-values-and/#more-264 —Preceding unsigned comment added by 117.198.96.60 (talk) 19:58, 13 January 2008 (UTC)

This Article is NOT Bresenham Algorithm

I was just doing a bit of revision for the Graphics module that I am doing and I stumbled on this and from what I know from lectures and so on this is NOT Bresenham Algorithm this is DDA. Bresenham is very subtly different it involves more pre-computation and no division in calculating decision parameter, therefore faster and better. Plus different calculations for decision parameter depending on value <0 or >0. It is very misleading to call article something that it is not describing. —Preceding unsigned comment added by Leshiy uk (talk • contribs) 21:38, 11 May 2008 (UTC)

this is true, this is not Bressenham algorithm but "midpoint line" algorithm

93.184.73.10 (talk) 01:15, 24 May 2014 (UTC)

Source code license

Can I use the source code of C implementation given on the page in my MIT/X11 licensed software? 149.156.160.140 (talk) 08:04, 22 January 2009 (UTC)

C99/C++ implementation cannot draw horizontal lines

The C99/C++ implementation does not draw a complete horizontal line. When given as input (0,0), (2,0), it only plots pixels (0,0) and (1,0), and (2,0) remains blank.

Should this line:

for (int x = x0; x != x1; x += xstep) {

be changed for this one?

for (int x = x0; x <= x1; x += xstep) {

--155.210.155.136 (talk) 08:35, 17 July 2009 (UTC)

Source code removed

I've removed the implementation code from the article. We don't need this; the pseudocode is enough. As can be seen from the discussions above, the implementation code is error prone, and worse yet, it's original research. There's a related discussion at [4]. The consensus was, that we don't really need implementation code, pseudocode is enough. Offliner (talk) 16:01, 9 August 2009 (UTC)

is first algorithm correct ?

I think following algorihm is wrong. I'm not quite sure so I better leave it alone.

 function line(x0, x1, y0, y1)
     int deltax := x1 - x0
     int deltay := y1 - y0
     real error := 0
     real deltaerr := deltay / deltax    // Assume deltax != 0 (line is not vertical),
           // note that this division needs to be done in a way that preserves the fractional part
     int y := y0
     for x from x0 to x1
         plot(x,y)
         error := error + deltaerr
    
         if abs(error) ≥ 0.5 then
             y := y + 1
             error := error - 1.0

I'm concerned about this line

         if abs(error) ≥ 0.5 then

'abs' is quite wrong here because if deltaerr is exactly 0.5 the contition will always pass decrementing error by 0.5 each turn.

And yes, this is my original reserach :) Miko3k (talk) 23:16, 12 August 2009 (UTC)

I agree with your main conclusion -- the "abs()" in the first pseudocode example of the article should be taken out, since it is not necessary for the specific octant that first example is designed to handle.

However, I don't see what the problem is with the case where deltaerr is exactly 0.5 .

In the case where deltaerr is exactly 0.5, it increments y every other time it increments x -- isn't that what we want?

just before the first time through the loop: error = 0.

During the first time through the loop: we set error to +0.5, then the "if" statement is true (with or without the abs), and error ends up with the value -0.5.

just before the second time through the loop: error = -0.5.

During the second time through the loop: we set error to 0, then the "if" statement fails -- with or without the abs, zero is not greater than 0.5 -- so the error value remains at 0.

just before the third time through the loop: error = 0.

During the third time through the loop: we repeat exactly like the first time.

It seems to me that the current pseudocode (with or without the abs) works everywhere in the first octant, i.e., for every possible value of the deltaerr slope from 0 to 1.0. --68.0.124.33 (talk) 05:25, 24 November 2010 (UTC)

Test in octave

I think the following Octave code maps the pseudocode given here

function [indx indy]=bresenham(x,y)
% x, y vectors in screen coordinates

x = round(x);
y = round(y);

% whether the line is above the diagonal
steep = abs(y(2) - y(1)) > abs(x(2) - x(1));
if steep 
% reflect along diagonal
  y_new = x;
  x = y;
  y = y_new;
  clear y_new;
end

reverse = x(1) > x(2);
if reverse
% reverse slope
x = x([2 1]);
y = y([2 1]);
end

deltax = x(2) - x(1);
deltay = abs(y(2) - y(1));

if deltax ~=0
    deltaerr = deltay / deltax;
else
% return a vertical list of indexes
disp('vertical line')
end

if y(1) < y(2) 
% positive slope
 ystep = 1; 
else 
 ystep = -1;
end

% initialize
indy = zeros(deltax+1,1);
indx=indy;

j = 0;
err = floor(deltax / 2);

for i=0:deltax
  if steep 
   indx(i+1)=j+y(1);
   indy(i+1)=i+x(1);
  else 
   indx(i+1)=i+x(1);
   indy(i+1)=j+y(1);
  end
  
  err = err - deltay;
  if err < 0
     j = j + ystep;
     err = err + deltax;
  end
end

Here is a test script

% Script
figure(1,'Position',[0 200 0 200]);

screenx=20;
screeny=20;

x=linspace(0,1,100)*10 + 3; 
y = 2*x - 3;
y2 = -1.5*x + 22;
y3 = .6342*x + 3;

[indx,indy] = bresenham(x([1 end]),y([1 end]));
[indx2,indy2] = bresenham(x([1 end]),y2([1 end]));
[indx3,indy3] = bresenham(x([1 end])+5,y3([1 end]));

h=plot(indx,indy,'bo',...
indx2,indy2,'ro',...
indx3,indy3,'go');
set(h,'markersize',12);

hold on
plot(x,y,'-b',x,y2,'-r',x+5,y3,'-g')
hold off

set(gca,'xtick',(1:screenx)-0.5,'ytick',(1:screeny)-0.5,'yticklabel',[],
'xticklabel',[]);
grid

axis([1 screenx 1 screeny])
axis equal

The output is shown in the Image on the right.

Output of the test code. Circles indicate the pixels to be drawn on the screen. The lines are the reference lines. Some drawing decisions are not correct.

I think you can see there, that decision are wrongly taken for two of the lines. This is probably not Bresenham's algorithm. Kakila 17:22(CEST) Sunday, June 06 2010 —Preceding undated comment added 15:31, 6 June 2010 (UTC).

Nicely done. Could someone see if changing

 err = floor(deltax / 2);

to

 err = round(deltax / 2);

fixes this glitch? What do we need to do to fix the pseudo-code in the article? --68.0.124.33 (talk) 19:06, 23 November 2010 (UTC)

The move from fractional to integer numbers

In the Optimization section of the main article, I just can't understand why the hell all fractional numbers are multiplied by 'deltax'. Are we allowed to perform such multiplication anywhere we need it? And why error is set to deltax/2, it can also be a fractional number if expressed so. —Preceding unsigned comment added by Jaybhanderi (talk • contribs) 17:24, 9 June 2010 (UTC)

We do this because, on the hardware Mr. Bresenham used, as well as other hardware still being used today[5], a floating-point "divide" operation is so slow that it makes our hardware move noticeably slower. A floating-point divide on such slow hardware takes hundreds of times as many cycles as multiply and divide on integer numbers.

This optimization allows us to get exactly the same results as the previous algorithm (that uses a single floating-point divide per line segment), but using only fast integer math.

Alas, when we use fast integer math, none of our values can be a fractional number.

I don't know why the "optimized" algorithm in the current version of the article seems to imply that "error" can be a fractional number when it says

 int error := deltax / 2

Would it be better to change that to

 int error := round( deltax / 2 )

or

 int error := floor( deltax / 2 )

? --68.0.124.33 (talk) 20:19, 23 November 2010 (UTC)

I don't understand how multiplying by deltax results in a floating point division inside the main loop. The only division I could come up with is that in the inequality it will say:

 error > deltax/2

But deltax/2 will remain constant throughout the loop, such that it can easily be computed before entering the loop. Am I missing something? — Preceding unsigned comment added by 87.161.171.40 (talk) 21:48, 9 February 2013 (UTC)

Java Implementation

The other implementation I saw is CRAZY slow so here is one I wrote, basically just converted the pseudo-code under the 'Optimization' header:

	public static final void lineAlgorithm(int x0, int y0, int x1, int y1) { // Bresenham's line algorithm
	boolean steep = Math.abs(y1 - y0) > Math.abs(x1 - x0);
	if (steep) {
		int tmp = x0;
		x0 = y0;
		y0 = tmp;
		tmp = x1;
		x1 = y1;
		y1 = tmp;
	}
	if (x0 > x1) {
		int tmp = x0;
		x0 = x1;
		x1 = tmp;
		tmp = y0;
		y0 = y1;
		y1 = tmp;
	}
	int deltax = x1 - x0;
	int deltay = Math.abs(y1 - y0);
	int error = deltax / 2;
	int ystep = -1;
	int y = y0;
	if (y0 < y1)
		ystep = 1;
	for (int x = x0; x <= x1; x++) {
		error -= deltay;
		if (error < 0) {
			y += ystep;
			error += deltax;
		}
	 }
    }

And is it just me or is the 'Simplification' version of the algorithm much slower than the initial optimized one? 24.193.99.41 (talk) 19:33, 8 August 2011 (UTC)

-- maybe because the 'simplified' algo has 3 'if' statements in the inner loop, but the 'optimized' algo has only 2 ? ..actually, scrub that: i hadn't counted the 'for' loop which is also technically an 'if'

Clashing algorithms

The "Derivation" part of the article doesn't really harmonize with the earlier segments. In the introduction of the algorithm it is assumed "that the pixel centers have integer coordinates." However, in the derivation part, the graphs seem to suggest that it is the top-left corner of the pixel that have integer coordinates. My mind is a hash salad right now after going through the algorithms, but it seems to me this ought to have some consequences. It's very confusing that the way the error accumulating variable is initialized is so different.

Also, the "Simplification" of the first algorithm to one that doesn't perform any swaps is impressive and I would really appreciate some pedagogic steps for its derivation. I think there could be some overall pedagogic value to this as well. Also, how does this relate to the other ones in terms of performance? I'm not sure simplification is the right word either. — Preceding unsigned comment added by Arketyp (talk • contribs) 13:52, 14 March 2012 (UTC)

Lost of incoherent mumbo-jumbo

This is unreadable for any reader who actually cares to understand what is being said.

The "Optimization" section states "This results in a divide inside the main loop, however...". What? What "divide" are you talking about? Where do you see a "divide" there? There's absolutely no meaningful explanation for why we switched from counting the errors from zero and up to counting it from deltax and down. Why, really?

The "Derivation" section begins with reinventing the canonical line equation in 2D. And it does it from scratch. Why??? Why not just use the Ax+By+C=0 as a commonly known basic fact?

The next "Algorithm" section is incomplete. It leads nowhere. The next "Algorithm with Integer Arithmetic" section is completely incoherent. It presents two formulas for the second point, but provides no explanation for what these equations are doing there. It speaks about the "difference D" but does not explain what that "difference D" is for the second point. What is D for the second point? What are those two formulas doing there?

50.242.89.251 (talk) 20:28, 26 April 2014 (UTC)

I've removed the optimisation section. It was based on inaccurate and/or badly out of date information. It's no longer true that floating point numbers are slow, hasn't been for many years; on many modern CPUs and GPUs they're faster. And FP errors are not an issue. With just float (never mind double) you'd need to be drawing images millions if not billions of pixels wide for typical FP errors to be noticeable. Finally having multiple source samples is excessive; for the same reason I removed the following section which was just another optimisation based on it.--JohnBlackburne^words_deeds 02:09, 21 September 2014 (UTC)

Last pseudo-code implementation can be factorized

The following block is repeated before and at the end of the loop: if D > 0

   y = y+1
   D = D - (2*dx)

But actually, its last execution is useless, so we could instead put it only at the beginning of the loop, hence simplifying the code:

plotLine(x0,y0, x1,y1)

 dx=x1-x0
 dy=y1-y0

 D = 2*dy - dx
 plot(x0,y0)
 y=y0
 for x from x0+1 to x1
   if D > 0
     y = y+1
     D = D - (2*dx)
   plot(x,y)
   D = D + (2*dy)

Some thoughts to improve the article quality

1. As I understand it the algorithm works by assuming the centers of pixels have integer coordinates - not the corners. In discord with this, some images and paragraphs give the idea that the corners of pixels have integer coordinates.

2. In my opinion the animated image that is a screen capture of someone's unique implementation of Bresenham's line algorithm is unhelpful.

3. The method to generalize the algorithm to all 8 octants can be simplified and presented more clearly.

72.229.111.192 (talk) 20:30, 24 May 2017 (UTC)

Regarding point 1: It's still wrong. There are some basic misconceptions here. A pixel does not have a center, and it certainly does not have corners. There's even a link to the main article about pixels behind the words "pixel center". Apparently the person who did this did not read the pixel article. To be fair, it's not explicitly clear about this. If you want to educate yourself (and perhaps improve this article), I recommend reading the paper "A Pixel Is Not A Little Square" by Alvy Ray Smith from 1995. In short, a pixel is a sample point. It has a position, but it does not have an extent. 2001:16B8:4870:FD00:DD8E:E505:61A7:D939 (talk) 14:41, 20 October 2019 (UTC)

Lua 5.2 code

-- See also: https://en.wikipedia.org/wiki/%3F:#Lua
function bline(x0, y0, x1, y1)
 
  local dx, sx = math.abs(x1 - x0), x0 < x1 and 1 or -1
  local dy, sy = math.abs(y1 - y0), y0 < y1 and 1 or -1
  local err, e2 = (dx>dy and dx or -dy)/2
 
  while true do
    setPixel(x0,y0);
    if x0 == x1 and y0 == y1 then break end
    e2 = err
    if e2 > -dx then err -= dy; x0 += sx end
    if e2 <  dy then err += dx; y0 += sy end
  end
end