Line rendering optimization

Question

I spent the past hour trying to optimize a block of code I wrote that renders a simple coloured line directly to a backbuffer.

I've compared it with one of the DrawLine method implementations of the WriteableBitmapEx project, and found that my algorithm isn't quite as fast (unless I use Parallel).

public static unsafe void DrawLineVector(this IntPtr target, Line2D line, int colour, int width, int height)
{
 var buf = (int*) target;
 var start = line.Start;
 var lineVector = line.Stop - start;
 var steps = (int)lineVector.Magnitude();
 var uX = lineVector.X / steps;
 var uY = lineVector.Y / steps;
 var col = colour;
 Parallel.For(0, steps, i =>
 //for (var i = 0; i != steps; ++i)
 {
 var x = start.X + uX * i;
 var y = start.Y + uY * i;
 if (x > -1 && y > -1 && x < width && y < height)
 buf[(int)y * width + (int)x] = col;
 //x += uX;
 //y += uY;
 }
 );
}

Note, the Line2D object is basically just a container for two VectorD objects (which are my own implementation of vectors).

Running this as it is currently, will get me, on my machine, roughly 300MPixels per second, while the "default" DrawLine method from WriteableBitmapEx gets me around 170MPixels per second. If I use the 'serial' version of this (i.e. not use Parallel), I get around 100MPixels per second.

Is there any way I can optimize this further?

• Harald Scheirich: You should probably check out the bresenham line drawing algorithm, it’s a classic in computer graphics and unless you want to do anti aliasing I think it’s still the go to for line rasterization en.m.wikipedia.org/wiki/Bresenham's_line_algorithm

Answer 1

Because you're comparing your performance with that of the WriteableBitmapEx project, you might like to compare your algorithm with theirs, which is here on github: WriteableBitmapShapeExtensions.cs

You say your performance isn't much slower than theirs (100 versus 170 MPixels/second).

A difference between yours and there's might be that yours is using float or double arithmetic, whereas theirs is using int arithmetic.

Their code is much longer (more lines of code) than yours, but their inner loop is something like this:

 for (int x = x1; x <= x2; ++x)
 {
 pixels[index] = color;
 ys += incy;
 y = ys >> PRECISION_SHIFT;
 if (y != previousY)
 {
 previousY = y;
 index += k;
 }
 else
 {
 ++index;
 }
 }

Note:

• Only int (not double)
• Few branches
• Every write is to a significant pixels (in your algorithm if you write a line at 45 degrees then you do 1.414 writes per pixels).

• t0yk4t: Yeah, I did think about that. I'm not sure if there's any 'smart' way of avoiding the overdraw of my algorithm, at least not right now. - Thanks again for your time, and your analysis :)
• ChrisW: Instead of var steps = (int)lineVector.Magnitude(); would it work to do var steps = (int)Math.Max(lineVector.X,lineVector.Y;? That would be fewer steps (if it's a slanted line) but still every pixel.
• t0yk4t: The line wouldn't be long enough if it is angled. If we assume we have a line from 0,0 to 5,5 then the actual length would need to be about 7.07 pixels to cover the distance (Hypothenuse), while the "Max" approach would only draw 5 pixels.
• ChrisW: @MelanieSchmidt But IMO you should only want to draw 5 pixels, i.e. [0,0], [1,1], etc., through [5,5]
• t0yk4t: Right, didn't realize that. One modification though. (int)Math.Max(Math.Abs(lineVector.X), Math.Abs(lineVector.Y)) - Since x and y can be negative.

Answer 2

I'm curious about why the code starts with if (x > -1

Doesn't that mean you need to scan values of i which end up doing nothing?

Perhaps you could skip those stages; something like:

var initial_i = 0;
if (start.X < 0)
 // need a bigger i to make it visible
 initial_i = -start.X / uX;

The above needs to be changed in uX can be negative, and beware floating point and divide by zero.

Do something similar (i.e. increase initial_i) to ensure that y is visible.

Then do something similar to ensure that i is not too large.

Then you ought to be able to have code like,

Parallel.For(initial_i, ending_i, i =>
//for (var i = 0; i != steps; ++i)
{
 var x = start.X + uX * i;
 var y = start.Y + uY * i;
 // if (x > -1 && y > -1 && x < width && y < height)
 buf[(int)y * width + (int)x] = col;
}

• t0yk4t: The problem with that would be to take in to account all the four 'sides' of the backbuffer, meaning I'd have to check both negative x, negative y, and positive x and positive y. Since a line can be both from -x to +x, and from +x to -x (And the same for y). But thanks for the suggestion!
• ChrisW: A 'branch' i.e. a conditional jump is slow because of CPU branch prediction, so I was hoping that removing all those if expressions would make it faster.
• t0yk4t: Yeah, I figured - I'll try tinkering with it a bit, see if I can't get that "iffy" branch out of the loop. Would require more complexity before the loop though, I think... Unless I can figure out a way to do the 'offsetting' correctly, with a bit of maths. The other thing I'd have to take in to consideration in that case, would be lines that don't ever intersect with the backbuffer at all. I'd initially done some nasty intersection checking in a method that uses this one, but decided not to do that here, yet.
• t0yk4t: Minor update: I've tried just removing the branch from the loop, and the improvement is marginal at best. It would of course be great to not step through the points outside the backbuffer, but the branch itself doesn't appear to be very expensive.