Bresenham algorithm gives incorrect results

FlorentMasson commented 6 years ago

Issue details

The Bresenham algorithm in Bresenham2 class returns incorrect results for 2-pixels diagonal lines

Reproduction steps/code

System.out.println(new Bresenham2().line(0, 1, 1, 0));

outputs: [(0, 1), (0, 0)]

instead of [(0, 1), (1, 0)]

Version of LibGDX and/or relevant dependencies

1.9.6

FlorentMasson commented 6 years ago

Also, testing a lots of samples, the ligbdx bresenham returns significantly different results from the one at rosettacode

For instance (10,9) to (8,6) returns [(10, 9), (10, 8), (9, 7), (8, 6)] while rosetta's one returns [(10, 9), (9, 8), (9, 7), (8, 6)]

I would suggest the replace the libgdx algo by the rosetta's implementation which gives better results IMHO (that's what I'll be doing in my project)

kalexmills commented 6 years ago

~~Could you post some side-by-side example pictures so we can see the issues which you're referring to?~~

I suppose there are multiple ways to do the Bresenham algorithm. Afaik, the original goal of the algorithm is that when drawing a single-pixel line, in each row and each column there should be either zero or 1 pixels. Each drawn pixel should also be adjacent to 1 or 2 drawn pixels in any direction (incl. diagonals).

So long as this is the case, then isn't the implementation "good enough"?

EDIT: You clearly did post an example and I am dumb, but here they are in ASCII format in case anyone is a dirty rotten skimmer like me and wants to "see" the result.

libgdx:
           (11,10)
     ......
     ....#.
     ....#.
     ...#..
     ..#...
     ......
(6,5)

rossettacode:
           (11,10)
     ......
     ....#.
     ...#..
     ...#..
     ..#...
     ......
(6,5)

The apparent "bending" artifact you are seeing is "only" an issue in pixel-perfect or lo-fi games (which, to be fair, are pretty common nowadays). Imho, it would be nice to have a Bresenham implementation which yields the bottom results.

FlorentMasson commented 6 years ago

isn't the implementation "good enough"?

clearly in my cas the implementation was not good enough, because I use the algorithm not for visual display, but to populate a grid to optimize collision detection between lines. The issue with 2-pixel diagonal lines not returning the the start and end point caused a lot of mess as you can imagine... (some line cross were not detected)

Also, I think the bresenham algorithm has a certain definition and output expectation that the libgdx implementation does not respect. The libgdx algorithm is a line drawing algorithm, but it's not bresenham.

kalexmills commented 6 years ago

I think the bresenham algorithm has a certain definition and output expectation that the libgdx implementation does not respect.

You are correct. From Wikipedia:

"Bresenham's algorithm chooses the integer y corresponding to the pixel center that is closest to the ideal (fractional) y for the same x; on successive columns y can remain the same or increase by 1."

This is one way to solve the problem. Imho, it is a very good way. ~libgdx doesn't do it that way. I think we should change it.~ It appears (to me at least) that libgdx might be doing it that way, but I could be wrong or there could be a better way. I'm happy to review and comment on a PR, but I don't have power to accept changes.

On the basis of the examples posted, it seems libgdx's implementation might meet Wikipedia's definition, depending on where the line starts / ends. Or the difference could be a simple rounding difference (solely based on the posted example, I haven't reviewed either implementation.)

See below example, along with comments on what I bet libgdx is doing.

y - 9.5 = (10.5 - 6.5) / (11.5 - 8.5) (x - 8.5)
y = 1.5x - 6.25

    567890 (11,10)
     ......
   9 ....#.   center of line at (10.5, 9.5)
   8 ....#.   line crosses y = 8.5 at x = 9.833   (rounded UP to 10)
   7 ...#..   line crosses y = 7.5 at x = 9.166     (rounded DOWN to 9)
   6 ..#...   center of line at (8.5, 6.5)
     ......   
(6,5)

EDIT: Based on rosetta code, it looks like they might be using integer division or flooring the result.

EDIT2: ... or they might be using different line endpoints... also I won't post again on this issue without reviewing the code. ;-)

libgdx / libgdx