Line drawing without a library

Okay so if you are easily bored, then stop now, if you are however interested in a rambling page on setting bits on a screen, then carry on.

Having got the basics of the graphics drawing working on the round display (see here), I looked to implement or at least repurpose some existing line drawing routines.

Initial searches online for low level 2D graphics were not very successful, although I did find a few people asking for the same type of information. Most replies however seemed to say not to bother and to just use existing drivers. Clearly the right answer if you are working on a PC or other platform, not that helpful if you are using a completely custom system.

After a bit of digging I came across a description of the “Bresenham’s Algorithm” for integer based line drawing. Which interestingly this looks to be the basis for the original sample code I found for the line drawing. If you want to look up the details, an in-depth description can be found at Wikipedia.

Clearly this routine works, but it does suffer from 2 main issues for me:

• It’s very jagged as it does not support anti-aliasing
• It’s limited to 1 pixel wide lines and I would like to have support for wider ones

So a bit more digging and I came accross an anti-aliased line routine which is known as “Xiaolin Wu’s line algorithm” which also can be found on Wikipedia. This is my main focus on this page, and I will refer to as Anti Aliasing (AA) from now on.

I took the sample code for this and converted it to work on the round display and after a bit of adjustments (and a lot of mistakes), I got this working.

Indeed it does give a much better display and is quite effective at the obvious expense of being slower.

This still doesn’t solve the 2nd issue of wide lines. More digging and the best answers I found related to drawing the outer edges as ant aliased (AA algorithm) and then “filling in the middle”. Great…

Okay time to write something new(ish), I am sure it’s been done before but here goes, lets see what we can do.

The basic idea would be to draw a number of lines parallel to the 1 pixel wide canter line, with each line being ideally 1 pixel shifted from the previous.

First pass was a simple shift in X or Y axis based on the slope of the main line.
This was relatively quick but has issues at the ends as shown in the following diagram:

For Horizontal or vertical lines this works fine, but as you can see as it gets more and more diagonal the ends start to become very distorted. This might be okay for narrow lines, but I wanted to do something better.

To get round this, the start and ends for each offset line need to be calculated in both X and Y axis. This gives a format something more like this:

However as you can see from this photo, there are some banding to the fill:

This is due to the fact that the AA process does not necessarily give solid colour but shades each pixel. This is perfect for the edges but not so for the fill.

This gives the nice solid blocks as shown:

Note the above both have the edge lines drawn using AA the photos may not show this fully.

Performance

So how fast and slow are they?

I did a simple test drawing 10,000 lines with the integer only routines and it took:

390ms

Doing the same test with the anti-aliased lines was approximatly 5 times slower at:

1930ms

For fun I also ran the wide lines doing the same lines but 10 pixels wide for each, and not suprisingly this took longer:

11610ms (over eleven and a half seconds)

So lets see if we can optimise any of the routines.

One area we can optimise is the pixel mixing routine. This was written mostly with integer maths to start with, but as most lines are of the same colour we can do some caching on the new RGB values.

Adding caching for the RGB values seemed to have marginal (if any) savings, so no need for the additional complexity. So that was a fail.

Next lets try replacing the floating point mixing value passed from the main algorithm with an unsigned short. Clearly this would not work as is, but if we use the integer as a scaled value with 256 being a nominal 1.0 then we still have 8 bits of mixing value (and since there is only 6 bits of colour information this is plenty).

Reran the test and the drawing is down to 1740 ms so that’s worth saving (10% saving).

In the main AA routine there is a lot of floating point maths, but in the main loop there is only really the iteration value and the gradient that is used. So I did the same conversion on these but using full integers and with a 65536 (16 bit) nominal 1.0. It would probably be fine with 8 bits but as the screen is 240 pixels there would be some margin for error on long lines.

This got the AA lines down to 1250ms so another saving (a further 26%).

Looking at the rest of the routine there is still some optimisations, but these are only one setup and end cases, so the savings here are not going to be as significant at the additional complexity of the code.

However I could apply the same code to the fill in line used in the wide lines, and this brought the 10,000 line test down from over 11 seconds down to 6 seconds.

For now I have uploaded the C, H and So files along with the updated clock.py and test.py code.

For now this will be it, but will probably work on the circle code to do a similar AA routine and optimisation.

Code files:

bcm_direct_c2py.c the main c file – getting a bit complex and really should be split
bcm_direct_c2py.h the main h file for both C and Python

clock.py Simple clock demo
test.py Line drawing and timing sample

Hopefully this can be of use or interest to others.