FS#9217 - Rockpaint line-drawing function

Attached to Project: Rockbox
Opened by Christopher Williams (christop) - Sunday, 27 July 2008, 07:22 GMT
Last edited by Bertrik Sikken (bertrik) - Friday, 01 August 2008, 19:34 GMT
Task Type Patches
Category Plugins
Status Closed
Assigned To No-one
Operating System All players
Severity Low
Priority Normal
Reported Version Daily build (which?)
Due in Version Undecided
Due Date Undecided
Percent Complete 100%
Votes 0
Private No


The draw_line() function in Rockpaint draws down-right (and up-left) lines off by a pixel, and it uses a multiply and a divide inside the main drawing loops.

This implementation uses Bresenham's line-drawing algorithm, so it is probably much faster (no multiplies/divides), and it draws better-looking lines at all slopes. There is still room for optimization in this newer version, particularly in terms of memory (it uses 10 local integer variables).

If anyone is also interested in a fast anti-aliasing line-drawing function, just ask me and I may port it to Rockbox. :)
This task depends upon

Closed by  Bertrik Sikken (bertrik)
Friday, 01 August 2008, 19:34 GMT
Reason for closing:  Accepted
Additional comments about closing:  Committed as 18176, thanks.
Comment by Christopher Williams (christop) - Monday, 28 July 2008, 06:48 GMT
If you're still not convinced of the difference this patch makes, take a look at the two images I attached. A picture is worth a thousand words, after all.

The first image (18139.png) is from revision 18139. All three of the lines were draw down and to the right (it makes no difference if they were drawn up and to the left instead). The top-left pixel stands alone in all three lines, and the bottom-right row of pixels is about twice as long as it should be. The middle line clearly shows this off-by-one problem, as I mentioned in my original post.

The second image (18139m.png) is my patched version. The lines look much better in this image. They are all symmetrical as much as possible (note that some pixels along a line could go either way -- up or down -- so not all lines will be exactly symmetrical). As a bonus, they were drawn faster than with the original code! To be honest, I don't actually notice any change in speed between this and the original code, but I'd be interested to see the results if someone else can perform a benchmark on both.
Comment by Christopher Williams (christop) - Monday, 28 July 2008, 20:16 GMT
Here's a second patch that I commented a bit and gave some of the variables better names. I also changed the code to use the built-in standard abs() function instead of an ABS() macro.
Comment by Bertrik Sikken (bertrik) - Wednesday, 30 July 2008, 15:41 GMT
I like it, it looks better than the old method and does not really increase the amount of code. I noticed there could be other candidates for converting to bresenham, like the oval, but this is a good start IMO.