Fast DrawLine() in Silverlight

Nov 6, 2009

How fast can you make it go?

How about this loop that draws the line:


int inc = incy1 * w + incx;
for (int i = 0; i < lenY; i++) {
    pixels[index >> PRECISION_SHIFT] = color;
    index += inc;
}

40FPS * 10000 lines = 400,000 lines/sec

Note: in my perf tests I did a single-threaded version, so if you have multiple cores (2-4), you might be able to get to more than 0.4mln lines/sec :)

I looked at the excellent posts from Rene about Drawing Shapes in Silverlight, and decided to give the DrawLine() code a whirl :) After trying to optimize it for some time, I ended up with code that runs twice as fast!

There is no sample here, because I expect that Rene will integrate it/try it out in his library (that’s really the best place for the code now to avoid multiple sample DLLs)

Here is the complete DrawLine() with my optimizations:

public static void DrawLineFast(this WriteableBitmap bmp, int x1, int y1, int x2, int y2, int color)
{
    // Use refs for faster access (really important!) speeds up a lot! 

    int w = bmp.PixelWidth;
    int[] pixels = bmp.Pixels;

    // Distance start and end point

    int dx = x2 - x1;
    int dy = y2 - y1;

    const int PRECISION_SHIFT = 8;
    const int PRECISION_VALUE = 1 << PRECISION_SHIFT;

    // Determine slope (absoulte value)

    int lenX, lenY;
    int incy1;
    if (dy >= 0)
    {
        incy1 = PRECISION_VALUE;
        lenY = dy;
    }
    else
    {
        incy1 = -PRECISION_VALUE;
        lenY = -dy;
    }

    int incx1;
    if (dx >= 0)
    {
        incx1 = 1;
        lenX = dx;
    }
    else
    {
        incx1 = -1;
        lenX = -dx;
    }

    if (lenX > lenY)
    { // x increases by +/- 1

        // Init steps and start

        int incy = (dy << PRECISION_SHIFT) / lenX;
        int y = y1 << PRECISION_SHIFT;

        // Walk the line!

        for (int i = 0; i < lenX; i++)
        {
            pixels[(y >> PRECISION_SHIFT) * w + x1] = color;
            x1 += incx1;
            y += incy;
        }
    }
    else
    { // since y increases by +/-1, we can safely add (*h) before the for() loop, since there is no fractional value for y
        // Prevent divison by zero

        if (lenY == 0)
        {
            return;
        }

        // Init steps and start

        int incx = (dx << PRECISION_SHIFT) / lenY;
        int index = (x1 + y1 * w) << PRECISION_SHIFT;

        // Walk the line!

        int inc = incy1 * w + incx;
        for (int i = 0; i < lenY; i++)
        {
            pixels[index >> PRECISION_SHIFT] = color;
            index += inc;
        }
    }
}

Summary of Optimizations Done

  • Moved from using float to using fixed point
  • Took advantage of the fact that if the line is longer in the y direction, vs the x direction (vertically-looking line), y will change by 1 on each iteration. This allows me to remove the multiplication in the innermost line drawing loop
  • Removed extra variables, so that remaining variables can be optimized by the JIT compiler, hopefully in CPU registers

Hope you like it! Please comment! Also, if you can make it faster, please do!

 

    

Comments

11/7/2009 12:05:38 AM #

Rene Schulte

Great stuff Nikola!
Thanks for your optimizations, although I wasn't able to reproduce a performance boost of 200% here, actually I've measured 17%. The Nevertheless I've replaced the default DrawLine() function with your optimized DDA implementation and updated the blog post and the source code (see kodierer.blogspot.com/.../...es-silverlight.html). Thanks again!

Rene Schulte | Reply

11/9/2009 9:54:38 PM #

nokola

Thanks...I actually measured about 30%. The 200% was comparing to the DDA algorithm, not Bresenhaim.
It probably depends on how the CPU caches if()-s vs multiples. My algorithm has less if-s that Bresenhaim's but more multiplies Smile

nokola | Reply

11/10/2009 3:39:28 PM #

Tommi Pirttiniemi

One thing you can do to improve the performance even further is to use int array all the way and passing width as an parameter. DrawLine performance got 4x faster, my computer can render 2 million lines per sec and DrawEllipseCentered is 2x faster

For example

public static void DrawLine(this int[] pixels, int w, int x1, int y1, int x2, int y2, int color)
{
...
}


And change calling methods to

pixelArray.DrawEllipseCentered(w, 150, 150, 50, 50, -40000000);

or

pixelArray.DrawLine(w, 0, 0, 150, 150, -40000000);

And remember to init variables somewhere:

int w = 0;
int[] pixelArray;

private void Init()
{
  writeableBmp = new WriteableBitmap((int)ViewPortContainer.Width, (int)ViewPortContainer.Height);
  w = writeableBmp.PixelWidth;
  pixelArray = writeableBmp.Pixels;
  ..
}


Tommi Pirttiniemi | Reply

11/12/2009 7:23:15 PM #

nokola

Thanks Tommi! You're absolutely right Smile
I sent this comment to Rene as well, and he was aware about it already, but for the sake of the sample and having nice bitmap extensions, we used the other syntax for now. I'll use the direct int[] pixels from now on..
I will be much better if we have a wrapper class e.g. OptimizedBitmap that takes WriteableBitmap and caches all these Smile

nokola | Reply

12/6/2009 10:52:20 PM #

Rene Schulte

I have finally put my WriteableBitmap extensions up on Codeplex:
http://writeablebitmapex.codeplex.com
See the credits. Smile

Rene Schulte | Reply

Add comment




  Country flag

biuquote
  • Comment
  • Preview
Loading



nokola.com | Terms | Log in