An idea how to speed up the drawing of lines

[GeorgHelmut]

Hi, I just joining the community, hence be patient....

Since some days I'm diving into the world of TFT's, hardware and software. Looking into the standard method of drawing free lines by using Bresenham Algorithm I got an idea how to simplify and speed up this time consuming routine. Finally - why not to share the solution with the community for discussion.

Line_en.pdf

[GeorgHelmut]

By the way:
While developing this Line Code I came across that my ILI 9486 chip has a glitch at column 255. When drawing a H-Line at this position two ascending pixels are highlighted. I got close to crazy as I thought it's caused by my coding. But multiple tests have proven that the chip has a glitch. There is no manufacturer code readable from this chip. May be, a copied design?
Did anyone else come across such a issue?

[Bodmer]

Hi, thanks for the suggestion. I will move to the "Discussions" area as it is more of a topic of interest than an issue.

The algorithm works well and runs fast. I usually run the "graphicstest" sketch to check for performance deltas on the algorithms.

There are a few anomlies in the line at the ends, I think this may be because the end pixels should be excluded in calculations.

Existing algorithm plot from graphicstest:

The suggested code output:

These look very similar until the bottom and right edges are inspected closely where there is a large final adjustment to the line in the new algorithm:

[Bodmer]

Tricky to see without zooming in:

[Bodmer]

The "near" 45 deg angle also has the correction at the end. The line should consist of single pixels with the small discontinuity in the middle:

I think a simple tweak to the algorithm is all that is needed.

[GeorgHelmut]

Here is the improved code. Major change besides some small adjustments is the change to 32 bit variables for the calculation loop and change from shift 5 to shift 20. This will eat some of the speed, but the result is very good. I extensively tested the code from shortest lines to longest. All is fine.

Code:

void DISP595::Line(int16_t xs, int16_t ys, int16_t xe, int16_t ye, uint16_t color) {
{
int32_t repeat, steps, n;
int16_t x, y, m, under, add, lang;
if (((xs >= xe) && (ys >= ye)) || ((xs >= xe) && (ys < ye)))
{
m = xs, xs = xe, xe = m, m = ys, ys = ye, ye = m;
}
if ((xe - xs) > (abs(ye - ys))) {
steps = abs(ye - ys) + 1;
lang = (abs(xe - xs) + 1) / (steps);
under = abs(xe - xs) + 1 - lang * (steps);
if (under) repeat = ((steps << 20) ) / (under); else repeat = 0xffff;
y = ys, x = xs, n = 0, m = 0;
while (y != ye)
{
if ((n++ << 20) > m * repeat && under)
{
m++;
add = 1;
}
else add = 0;
if (x + lang + add <= xe)
{
HLine(x, y, lang + add, color);
x += lang + add;
}
if (ye >= ys)y++; else y--;
}
HLine(x, y, xe - x + 1, color);
}
else
{
steps = abs(xe - xs) + 1;
lang = (abs(ye - ys) + 1) / (steps);
under = abs(ye - ys) + 1 - lang * (steps);
if (under) repeat = ((steps << 20) ) / (under); else repeat = 0xffff;
x = xs, y = ys, n = 0, m = 0;
while ((x < xe))
{
if ((n++ << 20) > m * repeat && under && n)
{
m++;
add = 1;
} else add = 0;
if (ye > ys && y + lang + add <= ye && x < xe)
{
VLine(x, y, lang + add, color);
y += lang + add;
}
if (ye <= ys && y - lang - add >= ye && x <= xe) {
VLine(x, y - lang - add + 1 , lang + add, color);
y -= (lang + add);
}
x++;
}
if (ye > ys)VLine(x, y, ye - y + 1, color); else VLine(x, ye, y - ye + 1, color);
}
}

[Bodmer]

The results look very good now. It's great to see new algorithms being developed.

With arbitrary line drawing on a typical SPI TFT the time taken is primarily driven by the pixel plotting time, with a 45 deg. angle being the worst case due to having to move the address window for every pixel.

FYI I ran the graphices test with the proposed algorithm on a 40MHz 16 bit colour SPI, FYI here are the results:

// New proposed algorithm
// Screen size                          Time to complete (μs)
//   50 x  50  Lines,                    1831
// 240 x 240 Lines,                    38375
// 480 x 320 Lines,                    101589

// Existing library optimised bressenham algorithm
// Screen size                          Time to complete (μs)
//   50 x  50 Lines,                    1740
// 240 x 240 Lines,                    36607
// 480 x 320 Lines,                    97277

This shows that the new algorithm is very good. I think your algorithm would be very good for lines that start or end off screen as the bresenham algorithm has to iterate along the line for the off screen pixels, whereas your algorithm could calculate the on screen start end end points.

[GeorgHelmut]

Thanks for conducting the tests. Even the code is not faster than the existing routine, at least it is in the same range. Hence in some cases it might be an option .

[Bodmer]

Your code does work well and is likely to outperform code in other libraries, the existing code in the TFT_eSPI library has been through a few stages of optimisation so sets a high bar for performance.

[GeorgHelmut]

Please feel free for using the code. I would be happy if it's helpful for someone.

[GeorgHelmut]

Thank you for the discussion. I'm working on the tweak. Looks promising. But optimizing and testing all cases will take some time.

[Bodmer]

You were right to be suspicious of a glitch at 255. This is a byte roll over point so can be in code or hardware. At the hardware level a bus transition from 0xFF to 0x00 tests the grounding and signal integrity. Try a quickly drawn alternating black and white pixel chequerboard to test the display and interface. Write a dedicated fill algorithm rather than draw single pixels since single pixels require address window commands for every pixel.

I have only had one defective screen and that was duff pixels that showed in all screen operations.

[GeorgHelmut]

I tested again. It's the chip (see photo).

[Bodmer]

How odd, so drawing 2 pixels at 254,258 causes 4 pixels to be plotted!

I would expect the line to slope the other way since x and y are both increasing.