Thursday, October 29, 2009

Drawing Lines - Silverlight WriteableBitmap Extensions II

The WriteableBitmap class is a nice feature that was added in Silverlight 3. It could be used to generate fast procedural images by drawing directly to a bitmap. The WriteableBitmap API is very minimalistic and there's only the raw Pixels array for such operations. This Property stores a 32 bit integer as color value for each pixel of the WriteableBitmap.

A couple of months ago I've written a handful of SetPixel methods that made it easier to use the WriteableBitmap, but they only provided a better interface for the Pixels Property and had no real functionality. This time I've written a more algorithmic method which performs a rasterization of a line: The famous DrawLine(). As the name implies is it used to draw a line between two points in the bitmap. To say it in advance: This is the way for drawing huge amounts of lines in Silverlight. I've used the elegant C# 3.0 extension methods again to add this functionality to the existing WriteableBitmap class.

Live

The application includes various scenarios where line-drawing is performed and it is also possible to set the number of lines to control the work load. The Silverlight frame rate counter at the upper left side shows the current FPS in the left-most column. You can find some details about the other parameters in this excellent blog post by András Velvárt(@vbandi).
For comparison I've also added a randomized line drawing scenario using the UIElement Line.

How it works
I've implemented two common line-drawing algorithms: The well-known Bresenham algorithm that uses only cheap integer arithmetic and a Digital Differential Analyzer (DDA) which is based upon floating point arithmetic. I don't want to explain the algorithmic details that were already explained several times in the literature or on the web. The linked Wikipedia articles are a good starting point if you are interested.

The signature of the extension methods
DrawLine(this WriteableBitmap bmp, int x1, int y1, int x2, int y2, Color color);
DrawLine(this WriteableBitmap bmp, int x1, int y1, int x2, int y2, int color);

DrawLineBresenham(this WriteableBitmap bmp, 
                  int x1, int y1, int x2, int y2, int color);

Clear(this WriteableBitmap bmp, Color color);  
The default DrawLine() method uses a DDA algorithm and is available for the Color structure and an integer value as line color. Furthermore it needs the x and y coordinate of the start point (x1, y1) and the end point (x2, y2) of the line.
I have also added a Clear() method that fills the whole WriteableBitmap with a Color.

Usage
// Initialize the WriteableBitmap with size 512x512
WriteableBitmap writeableBmp = new WriteableBitmap(512, 512);

// Set it as source of an Image control
ImageControl.Source = writeableBmp;


// Fill the WriteableBitmap with white color
writeableBmp.Clear(Colors.White);

// Draw a black line from P1(10, 5) to P2(20, 40)
writeableBmp.DrawLine(10, 5, 20, 40, Colors.Black);

// Render it!
writeableBmp.Invalidate();

Results
The WriteableBitmap line-drawing approach is more than 20-30 times faster as UIElement Line. So if you need to draw many lines and don't need anti-aliasing or other UIELement properties, the DrawLine() extensions methods are the right choice.
One interesting fact: The Bresenham algorithm that uses only simple integer operations is not the fastest line-drawing algorithm anymore. It was one of the earliest computer graphics algorithms invented in the 1960s. Since then the hardware has changed dramatically and a simple floating point DDA technique gives almost the same results on modern hardware.
Please keep in mind that these results may differ depending on the used hardware.

Source code
You can download the sample application as a Visual Studio 2008 solution including the complete and documented ready-to-use WriteableBitmapExtensions class from here. Check out my Codeplex project WriteableBitmapEx for an up to date version of the extension methods.
Have fun and let me know it if you do some cool stuff with it.

To be continued...
I'm planning to write more shape extensions for the WriteableBitmap like DrawRectangle(), DrawEllipse(), DrawPolyline(), etc. I will publish them in follow-up blog posts.

Update 11-06-2009
Goto Drawing Shapes - Silverlight WriteableBitmap Extensions III

13 comments:

  1. This is good stuff, and I like where you plan to take this.

    However, there is two requests that I have. Could you add a DrawTriangle, and a fill function? It may be a bit more difficult, but having a fill opens the door for some interesting activity on the bitmap surface.

    Thanks!

    ReplyDelete
  2. Thanks!
    I'm planning these extensions for the next blog posts. :) Do you have something certain in mind where you want to use the extensions?

    ReplyDelete
  3. Yes, Gouraud shading of surfaces.

    BTW, I'm glad to hear you say that, and a bit shocked that this implementation is so much faster than the UIElement Line.

    I guess I didn't think anti-aliasing was that intensive.

    ReplyDelete
  4. The Silverlight Shapes (UIElement) not only support anti-aliasing. There's a lot more. For example: Brushes, Width, Events, Binding, ... All that costs performance.

    I'm afraid you won't be able to implement Gouraud shading with my upcoming extensions mathods. They won't interpolate the colors between the vertices (points). The triangle / polygon will be filled with a constant color. You can only use it for Flat / Constant shading, then.
    Such things like Gouraud shading would be out of the extension methods scope. If you want to use lightning you should try a full 3D engine like Balder (http://balder.codeplex.com).

    ReplyDelete
  5. Rene, my mistake, I did mean flat shading, however I had Gouraud on my mind. Gouraud will require setting pixels to interpolated color intensities.

    Still, your implementation will be the first step in that process. I am looking forward to see what Balder becomes, and am not looking for it to solve some of the simpler UI problems that your code can solve.

    Even with flat shading, your code will have to be extended to account for a light source, which should be easy.

    Thanks, and I look forward to your next post.

    ReplyDelete
  6. Great article Rene. Inspired me to get lines implemented in Balder, its been one of those things I've never prioritized.

    Fallon: As for Gouraud shading, Balder has full support for Gouraud Shading, Flat Shading and Texture Mapping. We're hard at work these days getting more features and optimizations into the engine. The engine supports multiple lightsources as well.

    ReplyDelete
  7. Thanks Einar! Good to hear that it inspired you. :) I'm really looking forward to a release of Balder that supports dynamically generated vertex arrays. Keep up the great work!

    ReplyDelete
  8. Would it be possible to implement a fast color replacement function using the writeablebitmap?

    ReplyDelete
  9. Sure, you can render an Image to the Bitmap and manipulate the pixels, but it would be faster and better with a pixel shader. :)

    ReplyDelete
  10. Hey, I just downloaded your library - it's really cool. I wanted to know if there's a way to adjust the thickness of the DrawLine() ?

    ReplyDelete
  11. Hello Anonymous,

    it's not possible at the moment. This is planned for a future release. See this feature: http://writeablebitmapex.codeplex.com/workitem/11438

    However, this won't be implemented by me anytime soon. I'm busy with other projects ATM.

    ReplyDelete
  12. Hi, i´ve downloaded your class, it´s fantastic.

    I´m translating to visual basic, but i´m having a problem in this line:

    int col = (color.A << 24) | (color.R << 16) | (color.G << 8) | color.B;

    I´m sorry but I don´t know what does this line. You use it to convert a color into a int32.

    Could you explain me what does this line?

    thanks.

    PD: I´ve done the method "fillEllipse" and "loadFromWriteableBitmap". I hope this is helpful

    public static void fillEllipse(this WriteableBitmap bmp, int xC, int yC, int xR, int yR, int color)
    {
    // Use refs for faster access (really important!) speeds up a lot!
    int w = bmp.PixelWidth;
    int[] pixels = bmp.Pixels;

    for (int i0 = 0; i0 <= xR; i0++)
    {
    for (int i1 = 0; i1 <= yR; i1++)
    {
    if (Math.Pow((double)(i0) / xR, 2) + Math.Pow((double)(i1) / yR, 2) <= 1)
    {
    pixels[xC + i0 + (yC + i1) * w] = color;
    pixels[xC - i0 + (yC + i1) * w] = color;
    pixels[xC + i0 + (yC - i1) * w] = color;
    pixels[xC - i0 + (yC - i1) * w] = color;
    }
    }
    }
    }
    public static void fillEllipse(this WriteableBitmap bmp, int xC, int yC, int xR, int yR, Color color) {
    bmp.fillEllipse(xC, yC, xR, yR, (color.A << 24) | (color.R << 16) | (color.G << 8) | color.B);
    }
    public static void loadFromWriteableBitmap(this WriteableBitmap bmp, WriteableBitmap img, int xP, int yP) {
    // Use refs for faster access (really important!) speeds up a lot!
    int w = bmp.PixelWidth;
    int w2 = img.PixelWidth;
    int h2 = img.PixelHeight;
    int[] pixels = bmp.Pixels;
    int[] pixels2 = img.Pixels;

    for (int i = 0; i < w2; i++)
    {
    for (int j = 0; j < h2; j++)
    {
    pixels[xP + i + w * (yP + j)] = pixels2[i + w2 * j];
    }
    }
    }

    ReplyDelete
  13. > int col = (color.A << 24) | (color.R << 16) | (color.G << 8) | color.B;

    The WB uses the color as 32 bit ARGB values -> alpha, red, green, blue. This line combines the byte elements of a color struct into a single 32 bit integer using some bit twiddling.

    There's actually already a FillEllipse in the WBX lib and the "loadFromWriteableBitmap" you poster is the WBX' Clone(), Crop() or Blit() method if you will.

    ReplyDelete