1

While doing some graphics programming, I was surprised to learn the typical implementation of the Bresenham line plotting algorithm gives different results when the endpoints are reversed. For example, a line drawn with MoveTo(20,50) LineTo(80,122) differs from MoveTo(80,122) LineTo(20,50) twelve times, each mismatch spaced six pixels apart, such as hitting pixel (78,119) when drawing in one direction while drawing in the other direction hits (77,119).

A very simple case is plotting (0,0) to (2,1), which hits (0,0), (1,0), (2,1), while plotting (2,1) to (0,0) hits (2,1), (1,1), (0,0), differing in the middle pixel.

Is there a version of Bresenham that hits all the same pixels regardless of drawing direction between endpoints, and is still fast and efficient? None of my online searches have turned up any discussion of this issue.

The code that ran into this problem was trying to solve the problem where a moving pixel stopped on its way from (X0,Y0) to (X1,Y1). Would another pixel moving in the opposite direction from (X1,Y1) to (X0,Y0) land on the stopped pixel? Using Bresenham to calculate the pixel positions fails for many cases.

joe snyder
  • 3,629
  • 2
  • 21
  • 13
  • 1
    Simplest way to solve this problem: Check the two end points and swap them if drawing direction is not from left to right (if x0=x1 force y0<=y1). – MrSmith42 Mar 09 '22 at 17:42
  • Per the last paragraph, no drawing is being done. Essentially a pixel trajectory from one point is trying to detect a collision with another pixel already plotted from the other endpoint. It’s too late to reverse anything. Being able to hit all the same pixels regardless of starting endpoint is still the desired solution. – joe snyder Mar 09 '22 at 20:19
  • If reversal is not an option (I do deal with trajectories too btw.) then the only "possible" solutions I can think of is to a) divide the remainder error to half and star with it (non zero error at start) 2. change rounding rules and or pixel center position c) test collision with 1px radius or render thicker lines but this will result in false positives, I never tested a),b) I just feel it might help maybe not completely but still a lot. Btw you know you can reverse the rendering iteration store resulting points in list and then render them in reverse order unless resolution/memory is problem – Spektre Mar 10 '22 at 08:34
  • 1
    Also why Bresenham and not [integer DDA](https://stackoverflow.com/a/24682318/2521214) ? its simpler easily portable to ND and faster since x386 or you are on some different platform like MCU or DSP ? – Spektre Mar 10 '22 at 08:37
  • Kept finding DDA code that was buggy, or restricted to some slopes, or poorly documented, etc., so gave up on it. Hoped floats wouldn't be necessary. Maybe a robust version does hit the same pixels computed from either end. The "subpixel" code in your link does overlaps, so pixels moving from either end can pass each other without collision. Continued... – joe snyder Mar 12 '22 at 05:30
  • ...Saving all pixels from one end to compare with coming from the other end wasn't considered practical. For now the solution has been to allow adjacent pixels to be considered a collision, which has been working good enough, though it would still be nice to see simple, fast code that generates the same pixels from either endpoint. – joe snyder Mar 12 '22 at 05:30

1 Answers1

0

The difference in pixels is due to rounding behavior. If you draw a line from low X to high X, then when the "real" Y is 0.5, it will round up. If you draw the line the other way, then it will round down.

The solution (as MrSmith42 mentions in comment) is to always draw the same line in the same direction.

An implementation of Bresenham's must first determine which axis is the major axis, and it will then iterate along the major axis in the loop.

After determining the major axis, you should reverse the line if necessary to ensure that the major axis will be traversed in the positive direction.

This will simplify your code as well as ensuring that you get the same results no matter what order the input points are in.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87