Thursday, November 5, 2009

Drawing Shapes - Silverlight WriteableBitmap Extensions III

Last week I've released the second part of my WriteableBitmap extensions methods. I've added DrawLine() methods and presented a sample application that showed that the WriteableBitmap line-drawing methods are 20-30 times faster than the UIElement Line class.

A stable and fast line-drawing algorithm is the basis for most shapes like triangles, rectangles or polylines in general. For this blog post I've extended the WriteableBitmap with some specialized methods for various shapes including a fast ellipse rasterization algorithm.


Live

The application includes various scenarios where different shapes are drawn. By default a little demo is shown that I call "Breathing Flower". Basically different sized circles rotating around a center ring are generated. The animation is done using the best trigonometric functions in the world: sine and cosine.
The scenario "Static: WriteableBitmap Draw* Shapes" presents all shape extensions currently available. From left to right: Points - SetPixel(), Line - DrawLine(), Triangle - DrawTriangle(), Quad - DrawQuad(), Rectangle - DrawRectangle(), Polyline - DrawPolyline(), closed Polyline - DrawPolyline(), Ellipse - DrawEllipse(), Circle - DrawEllipseCentered().
The other two scenes randomly draw all shapes or only ellipses and allow controlling the work load by setting the number of shapes. The Silverlight frame rate counter at the upper left side shows the current FPS in the left-most column.

How it works
Most of the new extension methods use the DrawLine() function to build up a shape. Only the DrawRectangle() method implements a simplified line drawing using some for loops which is faster than calling the DrawLine() method four times. The DrawEllipse() function implements a generalized form of the Midpoint circle algorithm. I've used "A Fast Bresenham Type Algorithm For Drawing Ellipses" from this paper by John Kennedy.
The extension methods are pretty fast and if you need to draw a lot of shapes and you don't need anti-aliasing, Brushes or other advanced UIELement properties, the WriteableBitmap and the Draw*() extensions methods are the right choice. If you don't like the sharp edges, you can apply the Silverlight 3 Blur effect to the image:




The signature of the extension methods
DrawPolyline(this WriteableBitmap bmp, int[] points, Color color);
DrawPolyline(this WriteableBitmap bmp, int[] points, int color);

DrawTriangle(this WriteableBitmap bmp, 
             int x1, int y1, int x2, int y2, int x3, int y3, Color color);
DrawTriangle(this WriteableBitmap bmp, 
             int x1, int y1, int x2, int y2, int x3, int y3, int color);

DrawQuad(this WriteableBitmap bmp, 
     int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, Color color);
DrawQuad(this WriteableBitmap bmp, 
     int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int color);

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

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

DrawEllipseCentered(this WriteableBitmap bmp, 
                    int xc, int yc, int xr, int yr, Color color);
DrawEllipseCentered(this WriteableBitmap bmp, 
                    int xc, int yc, int xr, int yr, int color);
The DrawPolyline() method uses an array of x- and y-coordinate pairs and the array is interpreted as (x1, y1, x2, y2, ..., xn, yn). If a closed polyline should be drawn, the first point must also be added at the end of the array.
The DrawTriangle() and DrawQuad() methods needs all shape points as x- and y-coordinates. The DrawRectangle() function plots a rectangle out of the points that represent the minimum and maximum of the shape. The DrawEllipse() method interprets the parameters the same way, but the DrawEllipseCentered() function takes the center of the ellipse and the radii as arguments.
All methods are available for the Color structure or an integer value as 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);


// Black triangle with the points P1(10, 5), P2(20, 40) and P3(30, 10)
writeableBmp.DrawTriangle(10, 5, 20, 40, 30, 10, Colors.Black);

// Red rectangle from the point P1(2, 4) that is 10px wide and 6px high
writeableBmp.DrawRectangle(2, 4, 12, 10, Colors.Red);

// Blue ellipse with the center point P1(2, 2) that is 8px wide and 5px high
writeableBmp.DrawEllipseCentered(2, 2, 8, 5, Colors.Blue);

// Closed green polyline with P1(10, 5), P2(20, 40), P3(30, 30) and P4(7, 8)
int[] p = new int[] { 10, 5, 20, 40, 30, 30, 7, 8, 10, 5 };
writeableBmp.DrawPolyline(p, Colors.Green);


// Render it!
writeableBmp.Invalidate();

Source code
You can download the Silverlight application's source code including the complete and documented ready-to-use WriteableBitmapExtensions file from here. Check out my Codeplex project WriteableBitmapEx for an up to date version of the extension methods.

To be continued...
For the next part of this series I'm planning to add fill extensions methods to the WriteableBitmap like FillRectangle(), FillEllipse(), etc.

Update 11-06-2009
Nokola optimized the DrawLine() function a bit and made it 15-30% faster than the standard DDA implementation. I've replaced the DrawLine() method in the extensions with Nokola's optimized version, fixed some bugs and updated the source code. The original DDA implementation is now called DrawLineDDA().
Thanks Nikola!

Update 11-11-2009
Nokola optimized the DrawRectangle() function and I've updated the implementation of it. I've also added a faster Clear() method without parameters that fills every pixel with a transparent color. This was also proposed by Nokola.
Thanks again Nikola!

18 comments:

  1. Nice!, great work as usual! :)
    Thanks for adding these!

    btw, Rene I tried subscribing to your blog from IE 8...but didn't find the RSS feed. When clicking the Subscribe link, I get to http://feeds2.feedburner.com/Kodierer, but IE does not recognize it as valid RSS feed.

    Do you have some other link to the RSS that might work?
    (e.g. the link to the .axd like this: http://nokola.com/blog/syndication.axd)

    ReplyDelete
  2. Hello Nikola,

    Thanks for your compliment I really appreciate that. :)

    When I open this website here and click on the little RSS icon in IE8, it finds the feed and I can subscribe to it. The same works for when I open the FeedBurner URL (http://feeds2.feedburner.com/Kodierer). So it seems to work for me. Strange...

    ReplyDelete
  3. Figured it out!

    This works in my IE8: http://feeds.feedburner.com/Kodierer

    This doesn't:
    http://feeds2.feedburner.com/Kodierer

    Not sure why - haven't looked at the source

    ReplyDelete
  4. Good. Thanks for subscribing and the info.

    I've changed the link to http://feeds.feedburner.com/Kodierer

    ReplyDelete
  5. Hi Rene,

    I looked at your DrawLine() code and optimized it a bit :)

    The new version runs 2x faster, feel free to use the code in your library!
    http://nokola.com/blog/post/2009/11/06/Faster-DrawLine()-in-Silverlight-(400000-linessec).aspx

    Drawing stuff is pretty exciting!

    ReplyDelete
  6. sorry, it's only 30% faster (I was comparing with the DDA extension, not Bresenhaim)

    ReplyDelete
  7. also noticed a bug: you have to multiply y * PixelWidth (not PixelHeight) in all the Line() (maybe other as well?) functions

    ReplyDelete
  8. Hello Nikola,

    thanks for the info about the offset calculation bug. It was spread everywhere thanks to copy & paste. :( And thanks for your optimizations, although the difference is "only" 17% here.
    I've replaced the default DrawLine() function with your optimized DDA implementation and updated this blog post and the source code (see above).

    I should create a Codeplex project and host the extensions there. I might actually do that when I'm back from Berlin after next week. What do you think?

    ReplyDelete
  9. You really should make a project on codeplex. Your effort deserves a lot more attention. By creating a project you can acomplish this and it's also better for the quality of the code as people can contribute to it. Keep up the great work!

    ReplyDelete
  10. yes I think it's a great idea too! :)
    have fun in Berlin! I've never been there but it might be good to go sometime

    ReplyDelete
  11. Thanks Alex.
    Before I setup a Codeplex project I want to finish the parts I've planned so far (2 more at the moment).

    @Nokola:
    Berlin is always great. You should really come and see it and while you are in Germany, you should also visit Dresden. It's only a 2 hour drive from Berlin away. :)
    Todays TechEd sessions were not the best for me. The good stuff will hopefully follow the next days.

    ReplyDelete
  12. I think although having the class as extension is great, it is much better for perf if it's not using extensions, but the int[] pixels object directly. that's because even a single WriteableBitmap.Pixels per shape incurs significant cost, due to thread-safe checks.
    I tried drawing rectangles with and without calling .Pixels on every call and the perf goes up from 16 to 20 FPS with 10000 rectangles!!! :)

    btw, here's a rectangle routine that's improved a bit (no multiplication in the second for() and the cycles are consolidated which also saves time with managed code):
    public static void DrawRectangle(int[] pixels, int w, int x1, int y1, int x2, int y2, int color)
    {
    // First scanline
    int startY = y1 * w;
    int startOffset = startY + x1;
    int startOffset1 = startOffset + (y2 - y1) * w;

    // top and bottom scanlines
    for (int x = x1; x <= x2; x++)
    {
    pixels[startOffset] = color;
    pixels[startOffset1] = color;
    startOffset++;
    startOffset1++;
    }

    // vertical scanlines
    startOffset = startY + x1;
    startOffset1 = startY + x2;
    for (int y = y1 + 1; y < y2; y++)
    {
    pixels[startOffset] = color;
    pixels[startOffset1] = color;
    startOffset += w;
    startOffset1 += w;
    }
    }

    ReplyDelete
  13. nevermind the previous DrawRectangle(), this one squeezes additional 2 FPS (about 10%) on my PC. The change is in how I use the for() loops
    public static void DrawRectangle(int[] pixels, int w, int x1, int y1, int x2, int y2, int color)
    {
    int startY = y1 * w;
    int endY = y2 * w;

    int offset2 = endY + x1;
    int endOffset = startY + x2;
    int startYPlusX1 = startY + x1;

    // top and bottom horizontal scanlines
    for (int x = startYPlusX1; x <= endOffset; x++)
    {
    pixels[x] = color; // top horizontal line
    pixels[offset2] = color; // bottom horizontal line
    offset2++;
    }

    // offset2 == endY + x2

    // vertical scanlines
    endOffset = startYPlusX1 + w;
    offset2 -= w;

    for (int y = startY + x2 + w; y < offset2; y += w)
    {
    pixels[y] = color; // right vertical line
    pixels[endOffset] = color; // left vertical line
    endOffset += w;
    }
    }

    ReplyDelete
  14. another idea: check this out :)
    http://nokola.com/blog/post/2009/11/11/Best-Way-To-Clear-WriteableBitmap.aspx
    It's a 4 times faster than for() loop ClearScreen() routine for WriteableBitmap

    ReplyDelete
  15. Thanks Nikola that you optimized my naïve DrawRectangle() implementation. It was just a quick hack and fast enough, except if one only wants to draw thousands of rectangles.
    Your comment about the the direct usage of pixels[] as paramter is also absolutely right and I encountered the same, but I wanted to provide WriteableBitmap extension methods.
    I will create a Codeplex project and after that add methods that use an int[] array directly. This will make it also easier for optimization addicts like you to contribute. :)

    I've updated this blog post and the source code (see above).

    ReplyDelete
  16. no problem :) I knew you did the original DrawRectangle() for the sake of the clean sample.
    Thanks a lot for the updates!

    ReplyDelete
  17. hi is it suppord wp7 or just desktop applications?

    ReplyDelete
  18. For almost all .NET-related platforms nowadays.
    See the CodePlex site:

    http://writeablebitmapex.codeplex.com

    ReplyDelete