Anti-aliased lines

May 11, 2011 at 8:08 PM

Hi

I have created a version of antialised lines of variable thickness that can be used in this library. Seems to work pretty good. The bad point is they cannot be used to paint rectangles and polylines when thickness > 1. If anyone has any ideas how to fix that I'd be happy to hear that.

Get the source code from here http://designleon.zapto.org:6868/x_d/rsdn/aa.zip and let me know if it works ok for you.

@Owner of the project: you are free to use my code and include it into official build if you want. :)

Coordinator
May 17, 2011 at 9:19 AM

Thanks for the code EugenUS i might consider adding it. I actually planned to use this one: http://nokola.com/blog/post/2010/10/14/Anti-aliased-Lines-And-Optimizing-Code-for-Windows-Phone-7e28093First-Look.aspx

 

 - Rene Schulte

Sep 13, 2011 at 6:11 PM

Just wondering if you still plan to include it to the library?

Developer
Sep 26, 2011 at 8:57 AM

Hi guys - yes +1 vote from me to include AntiAliased lines. I am investigating using WriteableBitmapEx for a silverlight oscilloscope-style control. So far looks very impressive !

Sep 27, 2011 at 3:36 PM

Just in case, here are the changes I've done to nokola's implementation (link above) to work with WriteableBitmap and Color structure:

/// <summary> 
/// Draws an antialiased line, using an optimized version of Gupta-Sproull algorithm 
/// http://nokola.com/blog/post/2010/10/14/Anti-aliased-Lines-And-Optimizing-Code-for-Windows-Phone-7e28093First-Look.aspx
/// </summary> 
public static void AALine(this WriteableBitmap bmp, int x0, int y0, int x1, int y1, Color color)
{
   var pixels = bmp.Pixels;
   int pixelWidth = bmp.PixelWidth;
   int pixelHeight = bmp.PixelHeight;

   if ((x0 == x1) && (y0 == y1)) return; // edge case causing invDFloat to overflow, found by Shai Rubinshtein

   if (x0 < 1) x0 = 1;
   if (x0 > pixelWidth - 2) x0 = pixelWidth - 2;
   if (y0 < 1) y0 = 1;
   if (y0 > pixelHeight - 2) y0 = pixelHeight - 2;

   if (x1 < 1) x1 = 1;
   if (x1 > pixelWidth - 2) x1 = pixelWidth - 2;
   if (y1 < 1) y1 = 1;
   if (y1 > pixelHeight - 2) y1 = pixelHeight - 2;

   int addr = y0 * pixelWidth + x0;
   int dx = x1 - x0;
   int dy = y1 - y0;

   int du;
   int dv;
   int u;
   int v;
   int uincr;
   int vincr;

   // By switching to (u,v), we combine all eight octants 
   int adx = dx, ady = dy;
   if (dx < 0) adx = -dx;
   if (dy < 0) ady = -dy;

   if (adx > ady)
   {
      du = adx;
      dv = ady;
      u = x1;
      v = y1;
      uincr = 1;
      vincr = pixelWidth;
      if (dx < 0) uincr = -uincr;
      if (dy < 0) vincr = -vincr;
   }
   else
   {
      du = ady;
      dv = adx;
      u = y1;
      v = x1;
      uincr = pixelWidth;
      vincr = 1;
      if (dy < 0) uincr = -uincr;
      if (dx < 0) vincr = -vincr;
   }

   int uend = u + du;
   int d = (dv << 1) - du;        // Initial value as in Bresenham's 
   int incrS = dv << 1;    // &#916;d for straight increments 
   int incrD = (dv - du) << 1;    // &#916;d for diagonal increments

   double invDFloat = 1.0 / (4.0 * Math.Sqrt(du * du + dv * dv));   // Precomputed inverse denominator 
   double invD2duFloat = 0.75 - 2.0 * (du * invDFloat);   // Precomputed constant

   const int PRECISION_SHIFT = 10; // result distance should be from 0 to 1 << PRECISION_SHIFT, mapping to a range of 0..1 
   const int PRECISION_MULTIPLIER = 1 << PRECISION_SHIFT;
   int invD = (int)(invDFloat * PRECISION_MULTIPLIER);
   int invD2du = (int)(invD2duFloat * PRECISION_MULTIPLIER * color.A);
   int ZeroDot75 = (int)(0.75 * PRECISION_MULTIPLIER * color.A);

   int invDMulAlpha = invD * color.A;
   int duMulInvD = du * invDMulAlpha; // used to help optimize twovdu * invD 
   int dMulInvD = d * invDMulAlpha; // used to help optimize twovdu * invD 
   //int twovdu = 0;    // Numerator of distance; starts at 0 
   int twovduMulInvD = 0; // since twovdu == 0 
   int incrSMulInvD = incrS * invDMulAlpha;
   int incrDMulInvD = incrD * invDMulAlpha;

   uint srb = (uint)(color.R << 16 | color.B);
   uint sg = color.G;

   do
   {
      AlphaBlendNormalOnPremultiplied(pixels, addr, (ZeroDot75 - twovduMulInvD) >> PRECISION_SHIFT, srb, sg);
      AlphaBlendNormalOnPremultiplied(pixels, addr + vincr, (invD2du + twovduMulInvD) >> PRECISION_SHIFT, srb, sg);
      AlphaBlendNormalOnPremultiplied(pixels, addr - vincr, (invD2du - twovduMulInvD) >> PRECISION_SHIFT, srb, sg);

      if (d < 0)
      {
         // choose straight (u direction) 
         twovduMulInvD = dMulInvD + duMulInvD;
         d += incrS;
         dMulInvD += incrSMulInvD;
      }
      else
      {
         // choose diagonal (u+v direction) 
         twovduMulInvD = dMulInvD - duMulInvD;
         d += incrD;
         dMulInvD += incrDMulInvD;
         v++;
         addr += vincr;
      }
      u++;
      addr += uincr;
   } while (u < uend);
}

Coordinator
Oct 27, 2011 at 7:25 PM

Thanks. I just added Nokola's code to the repository. 

 

-Rene Schulte

Nov 2, 2011 at 3:11 AM

His implementation lacks proper clipping (and it looks like yours, too, at least it was the case last time I looked at the codebase). In case you find it useful, here is my implementation of the Cohen-Sutherland clipping algorithm; I can't guarantee that it is bug-free as I haven't thoroughly tested it, but it worked on the samples I had.

 

      static int GetCode(Point p, Rect r)
      {
         int i = 0;
         
         if (p.X < r.X) i++;
         else if (p.X > r.Right) i += 2;
         
         if (p.Y < r.Y) i += 4;
         else if (p.Y > r.Bottom) i += 8;
 
         return (i);
      }
 
      /// <summary>
      /// Implementation of Cohen-Sutherland algorithm
      /// http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland_algorithm
      /// </summary>
      /// <param name="r">Bounding rectangle.</param>
      /// <param name="p1">First point of the line.</param>
      /// <param name="p2">Second point of the line.</param>
      /// <returns>Flag indicating whether at least a part of the line is inside bounding rectangle.</returns>
      /// <remarks>For performance reasons, use it only when at least one point is outside the bounding rectangle.</remarks>
      public static bool ClipLine(Rect r, ref Point p1, ref Point p2)
      {
         int p1c = GetCode(p1, r);
         int p2c = GetCode(p2, r);
 
         double dx = p2.X - p1.X;
         double dy = p2.Y - p1.Y;
         double dydx = 0, dxdy = 0;
 
         if (dx != 0)
            dydx = dy / dx;
         else if (dy == 0) 
            return (p1c == 0 && p2c == 0);
         if (dy != 0)
            dxdy = dx / dy;
 
         for (int i = 0; i < 4; i++)
         {
            if ((p1c & p2c) != 0) return false;
            if ((p1c | p2c) == 0) return true;
 
            if (p2c != 0)   // Swap them so p1 would always be outside
            {
               var tmp1 = p1;
               p1 = p2;
               p2 = tmp1;
            }
 
            if ((p1c & 1) != 0)   // left edge
            {
               p1.Y += dydx * (r.Left - p1.X);
               p1.X = r.Left;
            }
            if ((p1c & 2) != 0)   // right edge
            {
               p1.Y += dydx * (r.Right - p1.X);
               p1.X = r.Right;
            }
            if ((p1c & 4) != 0)   // bottom edge
            {
               p1.X += dxdy * (r.Top - p1.Y);
               p1.Y = r.Top;
            }
            if ((p1c & 8) != 0)   // top edge
            {
               p1.X += dxdy * (r.Bottom - p1.Y);
               p1.Y = r.Bottom;
            }
 
            p1c = GetCode(p1, r);
            p2c = GetCode(p2, r);
         }
         return false;
      }
Developer
Jan 31, 2012 at 8:06 AM

Hey everyone. In the WPF version of WriteableBitmapEx the above AA line renders with poor quality if the line is a light colour overlaid on dark background. I will try to knock up an example. Curiously the silverlight version looks just fine even though the code paths for both appear to be the same!

This is something I'm looking into now as I am using WriteableBitmapEx as part of a .NET component library.

I'm also looking into adding width to lines and AA lines. Any help would be appreciated as of course, google searches for "Anti-aliased line with width" return plenty of GDI+ examples ;-)

Developer
Apr 23, 2012 at 8:50 PM
Edited Apr 23, 2012 at 8:52 PM

Guys, I have implemented a workaround to acheive variable thickness lines. It's not an algorithmic solution but provides reasonable quality lines and reasonable performance. I have no doubt it could be improved immensely.

Here's the code:

Firstly, I create a pen, which is basically a small bitmap of an ellipse of the required color blitted:

 

 

         private void UpdatePen()
        {
            // member variable: BitmapContext _pen;
            if (_pen.WriteableBitmap != null)
            {
                // Dispose the old pen
                _pen.Dispose();
                _pen = default(BitmapContext);
            }

            int strokeThickness = StrokeThickness;

            if (strokeThickness != 1)
            {
                var ellipse = new Ellipse();
                ellipse.Width = strokeThickness;
                ellipse.Height = strokeThickness;
                ellipse.Fill = new SolidColorBrush(SeriesColor);
                ellipse.Arrange(new Rect(0, 0, strokeThickness, strokeThickness));
                var bmp = ellipse.RenderToBitmap(strokeThickness, strokeThickness);
                _pen = bmp.GetBitmapContext();
            }
        }

 


Where the extension method RenderToBitmap is defined as

 

 

        public static WriteableBitmap RenderToBitmap(this FrameworkElement element, int width, int height)
        {
#if SILVERLIGHT
            var result = new WriteableBitmap(width, height);
            result.Render(element, new TranslateTransform());
            result.Invalidate();
            return result;
#else
            var bmp = new RenderTargetBitmap(width, height, 96, 96, PixelFormats.Pbgra32);

            bmp.Render(element);
            return new WriteableBitmap(bmp);
#endif
        }

 

I then created a modified Bresenham line which performs a blit of the "pen" at each pixel:

 

internal
#if !SILVERLIGHT 
    unsafe 
#endif
 static partial class WriteableBitmapExtensions
    {
        internal static void DrawPennedLine(BitmapContext context, int w, int h, int x1, int y1, int x2, int y2, BitmapContext pen)
        {
            // Edge case where lines that went out of vertical bounds clipped instead of dissapear
            if ((y1 < 0 && y2 < 0) || (y1 > h && y2 > h))
                return;

            int size = pen.WriteableBitmap.PixelWidth;
            int pw = size;
            var srcRect = new Rect(0, 0, size, size);
            if (x1 == x2 && y1 == y2)
            {
                return;
            }

            var pixels = context.Pixels;

            // Distance start and end point
            int dx = x2 - x1;
            int dy = y2 - y1;

            // Determine sign for direction x
            int incx = 0;
            if (dx < 0)
            {
                dx = -dx;
                incx = -1;
            }
            else if (dx > 0)
            {
                incx = 1;
            }

            // Determine sign for direction y
            int incy = 0;
            if (dy < 0)
            {
                dy = -dy;
                incy = -1;
            }
            else if (dy > 0)
            {
                incy = 1;
            }

            // Which gradient is larger
            int pdx, pdy, odx, ody, es, el;
            if (dx > dy)
            {
                pdx = incx;
                pdy = 0;
                odx = incx;
                ody = incy;
                es = dy;
                el = dx;
            }
            else
            {
                pdx = 0;
                pdy = incy;
                odx = incx;
                ody = incy;
                es = dx;
                el = dy;
            }

            // Init start
            int x = x1;
            int y = y1;
            int error = el >> 1;            

            var destRect = new Rect(x, y, size, size);

            if (y < h && y >= 0 && x < w && x >= 0)
            {
                //Blit(context.WriteableBitmap, new Rect(x,y,3,3), pen.WriteableBitmap, new Rect(0,0,3,3));
                Blit(context, w, h, destRect, pen, srcRect, pw);
                //pixels[y * w + x] = color;
            }

            // Walk the line!
            for (int i = 0; i < el; i++)
            {
                // Update error term
                error -= es;

                // Decide which coord to use
                if (error < 0)
                {
                    error += el;
                    x += odx;
                    y += ody;
                }
                else
                {
                    x += pdx;
                    y += pdy;
                }

                // Set pixel
                if (y < h && y >= 0 && x < w && x >= 0)
                {
                    //Blit(context, w, h, destRect, pen, srcRect, pw);
                    Blit(context, w, h, new Rect(x, y, size, size), pen, srcRect, pw);
                    //Blit(context.WriteableBitmap, destRect, pen.WriteableBitmap, srcRect);
                    //pixels[y * w + x] = color;
                }
            }
        }

 

I've tested this and it works. It's not super fast, there is noticeable slowdown if you draw 4,000 short lines of 3 pixel thickness, but it does work and its "ok". Also there is some minor aliasing but quality is good enough.

If you want to see it in action go to http://www.scichart.com/demo/, click on "Launch silverlight demo" and select the performance demo, then change Stroke Thickness to 2, 3, 4, 5 (limited to 5 for performance reasons).

I'd be interested to hear from anyone who has any improvements, especially algorithmic methods to improve performance or quality!

Developer
Apr 23, 2012 at 8:55 PM
Edited Apr 23, 2012 at 8:56 PM

FYI the poor quality antialiasing for WPF version is also fixed, this was the change

 

 

    /// <summary>
    /// Cross-platform factory for WriteableBitmaps
    /// </summary>
    public static class BitmapFactory
    {
        /// <summary>
        /// Creates a new WriteableBitmap of the specified width and height
        /// </summary>
        /// <remarks>For WPF the default DPI is 96x96 and PixelFormat is BGRA32</remarks>
        /// <param name="pixelWidth"></param>
        /// <param name="pixelHeight"></param>
        /// <returns></returns>
        public static WriteableBitmap New(int pixelWidth, int pixelHeight)
        {
#if SILVERLIGHT
            return new WriteableBitmap(pixelWidth, pixelHeight);
#else
            return new WriteableBitmap(pixelWidth, pixelHeight, 96.0, 96.0, PixelFormats.Pbgra32, null);
#endif
        }        
    }

 

Previously this class had PIxelFormats.Bgra32 for WPF, however silverlight uses PixelFormats.Pbgra32 which has pre-multiplied alpha, so the blending for AA didn't work. Changing WPF to produce a PixelFormats.Pbgra32 bitmap improved AA visual quality dramatically in the WPF version.

Jul 2, 2012 at 11:49 PM

Anybody tested EugenUS code above for WPF? I used it but the line rendered seems broken.  Any plan for this library support line width?

Coordinator
Jul 3, 2012 at 7:51 AM

Yes, line width is totally planned, but honestly I can't say when it will happen. I guess without a contribution I won't have the time to implement it myself anytime soon.

For Anti-Aliasing please use the method andyb1979 contributed and which is integrated into the library: DrawLineAa

 

-  René Schulte

Jul 23, 2012 at 8:44 PM
teichgraf wrote:

For Anti-Aliasing please use the method andyb1979 contributed and which is integrated into the library: DrawLineAa

Hi René,

Not that it really matters, but I believe you got it mixed up a bit, andyb1979 has proposed a method for rendering thick antialised lines by bit-blitting an ellipse; DrawLineAa was contributed by me (I based my code on nokola's implementation). 

Cheers,
Andrew