Talk:Bresenham's line algorithm

From Wikipedia, the free encyclopedia

You have new messages (last change).

Bresenham's line algorithm

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)


Contents

[edit] 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)

[edit] 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.

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)
// 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;
                }
        }
}

[edit] 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)

[edit] 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)
Retrieved from "http://en.wikipedia.org../../../b/r/e/Talk%7EBresenham%27s_line_algorithm_9942.html"