title: Algorithm for fast Drop shadow in GDI+
body: <p>What is an efficient way to add a drop-shadow to an image in GDI?</p>
  
  <p>Right now i start with my image:</p>
  
  <p><img src="https://i.stack.imgur.com/qOWAW.png" alt="enter image description here"></p>
  
  <p>i use ImageAttributes and a ColorMatrix to draw the image's alpha mask to a new image:</p>
  
  <pre><code>colorMatrix = (
      ( 0,  0,  0, 0, 0),
      ( 0,  0,  0, 0, 0),
      ( 0,  0,  0, 0, 0),
      (-1, -1, -1, 1, 0),
      ( 1,  1,  1, 0, 1)
      );
  </code></pre>
  
  <p><img src="https://i.stack.imgur.com/UjUFZ.png" alt="enter image description here"></p>
  
  <p>i then apply a Gaussian Blur convolution kernel, and offset it slightly:</p>
  
  <p><img src="https://i.stack.imgur.com/HbbPh.png" alt="enter image description here"></p>
  
  <p>And then i draw my original image back over top:</p>
  
  <p><img src="https://i.stack.imgur.com/H2iYJ.png" alt="enter image description here"></p>
  
  <p>Problem is that it's just too slow, it takes about 170ms to generate the image with drop-shadow, verses 2ms without the drop-shadow (70x slower):</p>
  
  <ul>
  <li>with drop shadow:   <code>171,332 µs</code></li>
  <li>without drop shadow: <code>2,457us</code></li>
  </ul>
  
  <p>When a user (e.g. me) is scrolling through a list of items, that extra 169ms delay is <em>very</em> noticeable.</p>
  
  <hr>
  
  <p>You can ignore the code below, it doesn't add anything to the question, or the answer:</p>
  
  <pre><code>class function TImageEffects.GenerateDropShadow(image: TGPImage;
          const radius: Single; const OffsetX, OffsetY: Single; const Opacity: Single): TGPBitmap;
  var
      width, height: Integer;
      alphaMask: TGPBitmap;
      shadow: TGPBitmap;
      graphics: TGPGraphics;
      imageAttributes: TGPImageAttributes;
      cm: TColorMatrix;
  begin
  {
      We generate a drop shadow by first getting the alpha mask. This will be a black
      sillouette on a transparent background. We then blur the black "shadow" by the amounts
      given.
      We then draw the original image on top of it's own shadow.
  }
  
  {
      http://msdn.microsoft.com/en-us/library/aa511280.aspx
      Windows Vista User Experience -&gt; Guidelines -&gt; Aesthetics -&gt; Icons
  
      Basic Flat Icon Shadow Ranges
  
      Flat icons
      Flat icons are generally used for file icons and flat real-world objects,
      such as a document or a piece of paper.
  
      Flat icon lighting comes from the upper-left at 130 degrees.
  
      Smaller icons (for example, 16x16 and 32x32) are simplified for readability.
      However, if they contain a reflection within the icon (often simplified),
      they may have a tight drop shadow. The drop shadow ranges in opacity from
      30-50 percent.
      Layer effects can be used for flat icons, but should be compared with other
      flat icons. The shadows for objects will vary somewhat, according to what
      looks best and is most consistent within the size set and with the other
      icons in Windows Vista. On some occasions, it may even be necessary to
      modify the shadows. This will especially be true when objects are laid over
      others.
      A subtle range of colors may be used to achieve desired outcome. Shadows help
      objects sit in space. Color impacts the perceived weight of the shadow, and
      may distort the image if it is too heavy.
  
      Blend mode: Multiply
      Opacity: 22% to 50% - depends on color of the item.
      Angle: 130 to 120, use global light
      Distance: 3 (256 thru 48x), Distance = 1 (32x, 24x)
      Spread: 0
      Size: 7 (256x thru 48x), Spread = 2 (32x, 24x)
  }
      width := image.GetWidth;
      height := image.GetHeight;
  
      //Get bitmap to hold final composited image and shadow
      Result := TGPBitmap.Create(width, height, PixelFormat32bppARGB);
  
      //Use ColorMatrix methods to "draw" the alpha image.
      alphaMask := TImageEffects.GetAlphaMask(image);
      try
          //Blur the black and white shadow image
  //      shadow := TImageEffects.BoxBlur(alphaMask, radius);
          shadow := TImageEffects.GaussianBlur(alphaMask, radius); //because Gaussian Blur is linearly-separable into two 1d kernels, it's actually faster than the box blur
      finally
          alphaMask.Free;
      end;
  
      //Draw
      graphics := TGPGraphics.Create(Result);
      try
          //Draw the "shadow", using the passed in opacity value.
          {
              Color transformations are of the form
          c =  (r, g, b, a)
          c' = (r, g, b, a)
          c' = c*M
              = (r, g, b, a, 1) * (0 0 0 0 0)  //r
                                        (0 0 0 0 0)  //g
                                        (0 0 0 0 0)  //b
                                        (1 1 1 1 0)  //a
                                        (0 0 0 0 1)  //1
          }
  
          imageAttributes := TGPImageAttributes.Create;
      {   cm := (
                  ( 1, 0, 0, 0,   0),
                  ( 0, 1, 0, 0,   0),
                  ( 0, 0, 1, 0,   0),
                  ( 0, 0, 0, 0.5, 0),
                  ( 0, 0, 0, 0,   1)
              );}
          cm[0, 0] :=  1; cm[0, 1] :=  0; cm[0, 2] :=  0; cm[0, 3] := 0;       cm[0, 4] := 0;
          cm[1, 0] :=  0; cm[1, 1] :=  1; cm[1, 2] :=  0; cm[1, 3] := 0;       cm[1, 4] := 0;
          cm[2, 0] :=  0; cm[2, 1] :=  0; cm[2, 2] :=  1; cm[2, 3] := 0;       cm[2, 4] := 0;
          cm[3, 0] :=  0; cm[3, 1] :=  0; cm[3, 2] :=  0; cm[3, 3] := Opacity; cm[3, 4] := 0;
          cm[4, 0] :=  0; cm[4, 1] :=  0; cm[4, 2] :=  0; cm[4, 3] := 0;       cm[4, 4] := 1;
  
  
          imageAttributes.SetColorMatrix(
                  cm,
                  ColorMatrixFlagsDefault,
                  ColorAdjustTypeBitmap);
          try
              graphics.DrawImage(shadow,
                          MakeRectF(OffsetX, OffsetY, width, height), //destination rectangle
                          0, 0, //source (x,y)
                          width, height, //source width, height
                          UnitPixel,
                          ImageAttributes);
  
              //Draw original image over-top of it's shadow
              graphics.DrawImage(image, 0, 0);
          finally
              imageAttributes.Free;
          end;
      finally
          graphics.Free;
      end;
  end;
  </code></pre>
  
  <p>Which uses the the function to get the grayscale alpha mask:</p>
  
  <pre><code>class function TImageEffects.GetAlphaMask(image: TGPImage): TGPBitmap;
  var
      imageAttributes: TGPImageAttributes;
      cm: TColorMatrix;
      graphics: TGPGraphics;
      Width, Height: UINT;
  begin
      {
          Color transformations are of the form
      c =  (r, g, b, a)
      c' = (r, g, b, a)
      c' = c*M
          = (r, g, b, a, 1) * (0 0 0 0 0)
                              (0 0 0 0 0)
                              (0 0 0 0 0)
                              (1 1 1 1 0)
                              (0 0 0 0 1)
      }
  
      imageAttributes := TGPImageAttributes.Create;
  
  {   cm := (
              ( 0,  0,  0, 0, 0),
              ( 0,  0,  0, 0, 0),
              ( 0,  0,  0, 0, 0),
              (-1, -1, -1, 1, 0),
              ( 1,  1,  1, 0, 1)
          );}
      cm[0, 0] :=  0; cm[0, 1] :=  0; cm[0, 2] :=  0; cm[0, 3] := 0; cm[0, 4] := 0;
      cm[1, 0] :=  0; cm[1, 1] :=  0; cm[1, 2] :=  0; cm[1, 3] := 0; cm[1, 4] := 0;
      cm[2, 0] :=  0; cm[2, 1] :=  0; cm[2, 2] :=  0; cm[2, 3] := 0; cm[2, 4] := 0;
      cm[3, 0] := -1; cm[3, 1] := -1; cm[3, 2] := -1; cm[3, 3] := 1; cm[3, 4] := 0;
      cm[4, 0] :=  1; cm[4, 1] :=  1; cm[4, 2] :=  1; cm[4, 3] := 0; cm[4, 4] := 1;
  
  
      imageAttributes.SetColorMatrix(
              cm,
              ColorMatrixFlagsDefault,
              ColorAdjustTypeBitmap);
  
      width := image.GetWidth;
      height := image.GetHeight;
  
      Result := TGPBitmap.Create(Integer(width), Integer(height));
      graphics := TGPGraphics.Create(Result);
     try
          graphics.DrawImage(
                  image,
                  MakeRect(0, 0, width, height), //destination rectangle
               0, 0, //source (x,y)
               width, height,
               UnitPixel,
                  ImageAttributes);
     finally
          graphics.Free;
      end;
  end;
  </code></pre>
  
  <p>The core is the gaussian blur:</p>
  
  <pre><code>class function TImageEffects.GaussianBlur(const bitmap: TGPBitmap;
    radius: Single): TGPBitmap;
  var
      width, height: Integer;
      tempBitmap: TGPBitmap;
      bdSource: TBitmapData;
      bdTemp: TBitmapData;
      bdDest: TBitmapData;
      pSrc: PARGBArray;
      pTemp: PARGBArray;
      pDest: PARGBArray;
      stride: Integer;
      kernel: TKernel;
  begin
  //  kernel := MakeGaussianKernel2d(radius);
      kernel := MakeGaussianKernel1d(radius);
      try
  //      Result := ConvolveBitmap(bitmap, kernel); brute 2d kernel
  
          width := bitmap.GetWidth;
          height := bitmap.GetHeight;
  
          // GDI+ still lies to us - the return format is BGR, NOT RGB.
          bitmap.LockBits(MakeRect(0, 0, width, height),
                  ImageLockModeRead,
                  PixelFormat32bppPARGB, bdSource);
  
          //intermediate bitmap
          tempBitmap := TGPBitmap.Create(width, height, PixelFormat32bppPARGB);
          tempBitmap.LockBits(MakeRect(0, 0, width, height),
                      ImageLockModeWrite,
                      PixelFormat32bppPARGB, bdTemp);
  
          //target bitmap
          Result := TGPBitmap.Create(width, height, PixelFormat32bppARGB);
          Result.LockBits(MakeRect(0, 0, width, height),
                      ImageLockModeWrite,
                      PixelFormat32bppPARGB, bdDest);
  
          pSrc := PARGBArray(bdSource.Scan0);
          pTemp := PARGBArray(bdTemp.Scan0);
          pDest := PARGBArray(bdDest.Scan0);
          stride := bdSource.Stride;
  
          ConvolveAndTranspose(kernel, pSrc^, pTemp^, width, height, stride, True, EdgeActionClampEdges);
          ConvolveAndTranspose(kernel, pTemp^, pDest^, height, width, stride, True, EdgeActionClampEdges);
  
          //Unlock source
         bitmap.UnlockBits(bdSource);
          tempBitmap.UnlockBits(bdTemp);
          Result.UnlockBits(bdDest);
  
          //get rid of temp
          tempBitmap.Free;
      finally
          kernel.Free;
      end;
  end;
  </code></pre>
  
  <p>which requires a 1-D kernel:</p>
  
  <pre><code>class function TImageEffects.MakeGaussianKernel1d(radius: Single): TKernel;
  var
      r: Integer;
      rows: Integer;
      matrix: TSingleDynArray;
      sigma: Single;
      sigma22: Single;
      sigmaPi2: Single;
      sqrtSigmaPi2: Single;
      radius2: Single;
      total: Single;
      index: Integer;
      row: Integer;
      distance: Single;
      i: Integer;
  begin
      r := Ceil(radius);
      rows := r*2+1;
  
      SetLength(matrix, rows);
      sigma := radius/3.0;
      sigma22 := 2*sigma*sigma;
      sigmaPi2 := 2*pi*sigma;
      sqrtSigmaPi2 := Sqrt(sigmaPi2);
      radius2 := radius*radius;
      total := 0;
  
      Index := 0;
      for row := -r to r do
      begin
          distance := row*row;
          if (distance &gt; radius2) then
              matrix[index] := 0
          else
          begin
              matrix[index] := Exp((-distance)/sigma22) / sqrtSigmaPi2;
              total := total + matrix[index];
              Inc(index);
          end;
      end;
  
      //Normalize the values
      for i := 0 to rows-1 do
          matrix[i] := matrix[i] / total;
  
  
      Result := TKernel.Create(rows, 1, matrix);
  end;
  </code></pre>
  
  <p>And then the magic of the gaussian function is that it is separable into two 1D convolutions:</p>
  
  <pre><code>class procedure TImageEffects.convolveAndTranspose(kernel: TKernel;
    const inPixels: array of ARGB; var outPixels: array of ARGB; width,
    height, stride: Integer; alpha: Boolean; edgeAction: TEdgeAction);
  var
      index: Integer;
      matrix: TSingleDynArray;
      rows: Integer; //number of rows in the kernel
      cols: Integer; //number of columns in the kernel
      rows2: Integer; //half row count
      cols2: Integer; //half column count
  
      x, y: Integer; //
      r, g, b, a: Single; //summed red, green, blue, alpha values
      row, col: Integer;
      ix, iy, ioffset: Integer;
      moffset: Integer;
      f: Single;
      rgb: ARGB;
      ir, ig, ib, ia: Integer;
  
     function ClampPixel(value: Single): Integer;
      begin
          Result := Trunc(value+0.5);
          if Result &lt; 0 then
              Result := 0
          else if Result &gt; 255 then
              Result := 255;
      end;
  begin
      matrix := kernel.KernelData;
      cols := kernel.Width;
      cols2 := cols div 2;
  
      for y := 0 to height-1 do
      begin
          index := y;
          ioffset := y*width;
          for x := 0 to width-1 do
          begin
              r := 0;
              g := 0;
              b := 0;
              a := 0;
  
              moffset := cols2;
              for col := -cols2 to cols2 do
              begin
                  f := matrix[moffset+col];
  
                  if (f &lt;&gt; 0) then
                  begin
                      ix := x+col;
                      if ( ix &lt; 0 ) then
                      begin
                          if ( edgeAction = EdgeActionClampEdges ) then
                              ix := 0
                          else if ( edgeAction = EdgeActionWrapEdges ) then
                              ix := (x+width) mod width;
                      end
                      else if ( ix &gt;= width) then
                      begin
                          if ( edgeAction = EdgeActionClampEdges ) then
                              ix := width-1
                          else if ( edgeAction = EdgeActionWrapEdges ) then
                              ix := (x+width) mod width;
                      end;
                      rgb := inPixels[ioffset+ix];
                      a := a + f * ((rgb shr 24) and $FF);
                      r := r + f * ((rgb shr 16) and $FF);
                      g := g + f * ((rgb shr  8) and $FF);
                      b := b + f * ((rgb       ) and $FF);
                  end;
              end;
              if alpha then
                  ia := ClampPixel(a)
           else
                  ia := $FF;
              ir := ClampPixel(r);
              ig := ClampPixel(g);
              ib := ClampPixel(b);
              outPixels[index] := MakeARGB(ia, ir, ig, ib);
  
              Inc(index, height);
          end;
      end;
  end;
  </code></pre>
  
  <p>with sample usage, on my 256x256 source images:</p>
  
  <pre><code>image := TImageEffects.GenerateDropShadow(localImage, 14, 2.12132, 2.12132, 1.0);
  </code></pre>
  
  <p>Profiling shows that 88.62% time is spent in the lines:</p>
  
  <pre><code>a := a + f * ((rgb shr 24) and $FF);
  r := r + f * ((rgb shr 16) and $FF);
  g := g + f * ((rgb shr  8) and $FF);
  b := b + f * ((rgb       ) and $FF);
  </code></pre>
  
  <p>which is the per-pixel alpha blending.</p>
  
  <p>Which makes me think that there's a better way to apply a soft drop-shadow that applying a blur effect, after all Windows and OSX apply a drop-shadow to windows in real-time.</p>