Added a new function to directly generate a blurred rectangle analytically.

Added two new microbenchmarks to demonstrate speedup over existing BlurSeparable approach.

Added new GM tests for blurred rectangles. 
Review URL: https://codereview.appspot.com/7037050

git-svn-id: http://skia.googlecode.com/svn/trunk@7034 2bbb7eff-a529-9590-31e7-b0007b416f81

9 files changed, 387 insertions, 3 deletions

diff --git a/bench/BitmapRectBench.cpp b/bench/BitmapRectBench.cpp
index 4391626d89..f2f9e4c395 100644
--- a/bench/BitmapRectBench.cpp
+++ b/bench/BitmapRectBench.cpp
@@ -70,7 +70,6 @@ protected:
     }
 
     virtual void onDraw(SkCanvas* canvas) {
-        SkIPoint dim = this->getSize();
         SkRandom rand;
 
         SkPaint paint;
diff --git a/bench/BlurRectBench.cpp b/bench/BlurRectBench.cpp
new file mode 100644
index 0000000000..3e7bc8a5c3
--- /dev/null
+++ b/bench/BlurRectBench.cpp
@@ -0,0 +1,133 @@
+
+/*
+ * Copyright 2013 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "SkBenchmark.h"
+#include "SkCanvas.h"
+#include "SkPaint.h"
+#include "SkRandom.h"
+#include "SkShader.h"
+#include "SkString.h"
+#include "SkBlurMask.h"
+
+#define SMALL   SkIntToScalar(2)
+#define REAL    SkFloatToScalar(1.5f)
+#define BIG     SkIntToScalar(10)
+#define REALBIG SkFloatToScalar(30.5f)
+
+class BlurRectBench: public SkBenchmark {
+    SkScalar    fRadius;
+    SkString    fName;
+
+public:
+    BlurRectBench(void *param, SkScalar rad) : INHERITED(param) {
+        fRadius = rad;
+    }
+
+protected:
+    virtual const char* onGetName() {
+        return fName.c_str();
+    }
+    
+    SkScalar radius() const {
+        return fRadius;
+    }
+    
+    void setName( SkString name ) {
+        fName = name;
+    }
+
+    virtual void onDraw(SkCanvas* canvas) {
+        SkPaint paint;
+        this->setupPaint(&paint);
+
+        paint.setAntiAlias(true);
+
+        int pad = fRadius * 1.5 + 1;
+        SkRect r = SkRect::MakeWH(2 * pad + 1, 2 * pad + 1);
+        
+        int loop_count;
+        
+        if (fRadius > SkIntToScalar(50)) {
+          loop_count = 10;
+        } else if (fRadius > SkIntToScalar(5)) {
+          loop_count = 1000;
+        } else {
+          loop_count = 10000;
+        }
+        
+        preBenchSetup( r );
+        
+        for (int i = 0; i < SkBENCHLOOP(loop_count); i++) {
+            makeBlurryRect( r );
+        }
+    }
+    
+    virtual void makeBlurryRect( SkRect &r ) = 0;
+    virtual void preBenchSetup( SkRect &r ) {}
+private:
+    typedef SkBenchmark INHERITED;
+};
+
+
+class BlurRectDirectBench: public BlurRectBench {
+ public:
+    BlurRectDirectBench( void *param, SkScalar rad ) : BlurRectBench( param, rad ) {
+        SkString name;
+        
+        if (SkScalarFraction(rad) != 0) {
+            name.printf("blurrect_direct_%.2f", SkScalarToFloat(rad));
+        } else {
+            name.printf("blurrect_direct_%d", SkScalarRound(rad));
+        }
+        
+        setName( name );
+    }
+protected:
+    virtual void makeBlurryRect( SkRect &r ) {
+        SkMask mask;
+        SkBlurMask::BlurRect( &mask, r, radius(), SkBlurMask::kNormal_Style, SkBlurMask::kHigh_Quality );
+    }
+};
+
+class BlurRectSeparableBench: public BlurRectBench {
+    SkMask fSrcMask;
+public:
+    BlurRectSeparableBench(void *param, SkScalar rad) : BlurRectBench( param, rad ) {
+        SkString name;
+        if (SkScalarFraction(rad) != 0) {
+            name.printf("blurrect_separable_%.2f", SkScalarToFloat(rad));
+        } else {
+            name.printf("blurrect_separable_%d", SkScalarRound(rad));
+        }
+        
+        setName( name );
+    }
+
+protected:
+    virtual void preBenchSetup( SkRect &r ) {    
+        fSrcMask.fFormat = SkMask::kA8_Format;
+        fSrcMask.fRowBytes = r.width();
+        fSrcMask.fBounds = SkIRect::MakeWH(r.width(), r.height());
+        fSrcMask.fImage = SkMask::AllocImage( fSrcMask.computeTotalImageSize() );
+        
+        memset( fSrcMask.fImage, 0xff, fSrcMask.computeTotalImageSize() );
+    }
+    
+    virtual void makeBlurryRect( SkRect &r ) {
+        SkMask mask;
+        SkBlurMask::BlurSeparable( &mask, fSrcMask, radius(), SkBlurMask::kNormal_Style, SkBlurMask::kHigh_Quality );
+    }
+};
+
+DEF_BENCH(return new BlurRectSeparableBench(p, SMALL);)
+DEF_BENCH(return new BlurRectSeparableBench(p, BIG);)
+DEF_BENCH(return new BlurRectSeparableBench(p, REALBIG);)
+DEF_BENCH(return new BlurRectSeparableBench(p, REAL);)
+DEF_BENCH(return new BlurRectDirectBench(p, SMALL);)
+DEF_BENCH(return new BlurRectDirectBench(p, BIG);)
+DEF_BENCH(return new BlurRectDirectBench(p, REALBIG);)
+DEF_BENCH(return new BlurRectDirectBench(p, REAL);)
diff --git a/gm/blurrect.cpp b/gm/blurrect.cpp
index c28468acf9..fc447c8a57 100644
--- a/gm/blurrect.cpp
+++ b/gm/blurrect.cpp
@@ -7,6 +7,7 @@
 
 #include "gm.h"
 #include "SkBlurMaskFilter.h"
+#include "SkBlurMask.h"
 #include "SkCanvas.h"
 #include "SkPath.h"
 
@@ -149,6 +150,82 @@ private:
     typedef GM INHERITED;
 };
 
+class BlurRectCompareGM : public skiagm::GM {
+    SkString  fName;
+    unsigned int fRectWidth, fRectHeight;
+    float fRadius;
+public:
+    BlurRectCompareGM(const char name[], unsigned int rectWidth, unsigned int rectHeight, float radius) :
+        fName(name)
+        , fRectWidth( rectWidth )
+        , fRectHeight( rectHeight )
+        , fRadius( radius )
+    {}
+    
+  int width() const { return fRectWidth; }
+  int height() const { return fRectHeight; }
+  int radius() const { return fRadius; }
+
+protected:
+    virtual SkString onShortName() {
+        return fName;
+    }
+
+    virtual SkISize onISize() {
+        return SkISize::Make(640, 480);
+    }
+    
+    virtual void makeMask( SkMask *m, SkRect r ) = 0;
+
+    virtual void onDraw(SkCanvas* canvas) {
+      SkRect r;
+      r.setWH( fRectWidth, fRectHeight );
+
+      SkMask mask;
+
+      makeMask( &mask, r );
+
+      SkBitmap bm;
+      bm.setConfig(SkBitmap::kA8_Config, mask.fBounds.width(), mask.fBounds.height());
+      bm.setPixels(mask.fImage);
+      canvas->drawBitmap(bm, 50, 50, NULL);
+    }
+
+    virtual uint32_t onGetFlags() const { return kSkipPipe_Flag; }
+
+private:
+    typedef GM INHERITED;
+};
+
+class BlurRectFastGM: public BlurRectCompareGM {
+public:
+  BlurRectFastGM(const char name[], unsigned int rect_width, unsigned int rect_height, float blur_radius) :
+    BlurRectCompareGM( name, rect_width, rect_height, blur_radius ) {}
+protected:
+  virtual void makeMask( SkMask *m, SkRect r ) {
+    SkBlurMask::BlurRect( m, r, radius(), SkBlurMask::kNormal_Style, SkBlurMask::kHigh_Quality );
+  }
+};
+
+class BlurRectSlowGM: public BlurRectCompareGM {
+public:
+  BlurRectSlowGM(const char name[], unsigned int rect_width, unsigned int rect_height, float blur_radius) :
+    BlurRectCompareGM( name, rect_width, rect_height, blur_radius ) {}
+protected:
+  virtual void makeMask( SkMask *m, SkRect r ) {
+    SkMask src;
+    src.fFormat = SkMask::kA8_Format;
+    src.fRowBytes = r.width();
+    src.fBounds = SkIRect::MakeWH(r.width(), r.height());
+    src.fImage = SkMask::AllocImage( src.computeTotalImageSize() );
+
+    memset( src.fImage, 0xff, src.computeTotalImageSize() );
+
+    SkBlurMask::BlurSeparable( m, src, radius()/2, SkBlurMask::kNormal_Style, SkBlurMask::kHigh_Quality );    
+  }
+};
+
+
 //////////////////////////////////////////////////////////////////////////////
 
 DEF_GM(return new BlurRectGM("blurrect", NULL, 0xFF, SkBlurMaskFilter::kNormal_BlurStyle);)
@@ -156,5 +233,12 @@ DEF_GM(return new BlurRectGM("blurrect", NULL, 0xFF, SkBlurMaskFilter::kSolid_Bl
 DEF_GM(return new BlurRectGM("blurrect", NULL, 0xFF, SkBlurMaskFilter::kOuter_BlurStyle);)
 DEF_GM(return new BlurRectGM("blurrect", NULL, 0xFF, SkBlurMaskFilter::kInner_BlurStyle);)
 
-DEF_GM(return new BlurRectGM("blurrect_grad_80", setgrad, 0x80, SkBlurMaskFilter::kNormal_BlurStyle);)
+DEF_GM(return new BlurRectFastGM("blurrect_fast_100_100_10", 100, 100, 10);)
+DEF_GM(return new BlurRectFastGM("blurrect_fast_100_100_2", 100, 100, 2);)
+DEF_GM(return new BlurRectFastGM("blurrect_fast_10_10_100", 10, 10, 100);)
+DEF_GM(return new BlurRectFastGM("blurrect_fast_10_100_10", 10, 100, 10);)
 
+DEF_GM(return new BlurRectSlowGM("blurrect_slow_100_100_10", 100, 100, 10);)
+DEF_GM(return new BlurRectSlowGM("blurrect_slow_100_100_2", 100, 100, 2);)
+DEF_GM(return new BlurRectSlowGM("blurrect_slow_10_10_100", 10, 10, 100);)
+DEF_GM(return new BlurRectSlowGM("blurrect_slow_10_100_10", 10, 100, 10);)
\ No newline at end of file
diff --git a/gyp/SampleApp.gyp b/gyp/SampleApp.gyp
index a831f747e5..02405f88ba 100644
--- a/gyp/SampleApp.gyp
+++ b/gyp/SampleApp.gyp
@@ -6,6 +6,7 @@
       'mac_bundle' : 1,
       'include_dirs' : [
         '../src/core', # needed to get SkConcaveToTriangle, maybe this should be moved to include dir?
+        '../src/effects', #needed for BlurMask.h
         '../gm',       # needed to pull gm.h
         '../samplecode', # To pull SampleApp.h and SampleCode.h
         '../src/pipe/utils', # For TiledPipeController
diff --git a/gyp/bench.gyp b/gyp/bench.gyp
index 1524b72edb..0c19781488 100644
--- a/gyp/bench.gyp
+++ b/gyp/bench.gyp
@@ -25,6 +25,7 @@
           {
             'include_dirs' : [
               '../src/gpu',
+              '../src/effects',
             ],
           },
         ],
diff --git a/gyp/bench.gypi b/gyp/bench.gypi
index dbb30b6fff..3d98619e6c 100644
--- a/gyp/bench.gypi
+++ b/gyp/bench.gypi
@@ -10,6 +10,7 @@
     '../bench/BitmapBench.cpp',
     '../bench/BitmapRectBench.cpp',
     '../bench/BlurBench.cpp',
+    '../bench/BlurRectBench.cpp',
     '../bench/ChecksumBench.cpp',
     '../bench/ChromeBench.cpp',
     '../bench/DashBench.cpp',
diff --git a/gyp/gm.gyp b/gyp/gm.gyp
index 4f8637fd06..4b2b1c4b64 100644
--- a/gyp/gm.gyp
+++ b/gyp/gm.gyp
@@ -9,6 +9,7 @@
       'type': 'executable',
       'include_dirs' : [
         '../src/core',
+        '../src/effects',
         '../src/pipe/utils/',
         '../src/utils/',
       ],
diff --git a/src/effects/SkBlurMask.cpp b/src/effects/SkBlurMask.cpp
index 658b0fd47e..766da539fe 100644
--- a/src/effects/SkBlurMask.cpp
+++ b/src/effects/SkBlurMask.cpp
@@ -12,6 +12,14 @@
 #include "SkTemplates.h"
 #include "SkEndian.h"
 
+// scale factor for the blur radius to match the behavior of the all existing blur 
+// code (both on the CPU and the GPU).  This magic constant is  1/sqrt(3).
+
+// TODO: get rid of this fudge factor and move any required fudging up into 
+// the calling library
+
+#define kBlurRadiusFudgeFactor SkFloatToScalar( .57735f )
+
 #define UNROLL_SEPARABLE_LOOPS
 
 /**
@@ -866,7 +874,7 @@ bool SkBlurMask::Blur(SkMask* dst, const SkMask& src,
 
     // highQuality: use three box blur passes as a cheap way to approximate a Gaussian blur
     int passCount = (kHigh_Quality == quality) ? 3 : 1;
-    SkScalar passRadius = SkScalarDiv(radius, SkScalarSqrt(SkIntToScalar(passCount)));
+    SkScalar passRadius = (kHigh_Quality == quality) ? SkScalarMul( radius, kBlurRadiusFudgeFactor): radius;
 
     int rx = SkScalarCeil(passRadius);
     int outer_weight = 255 - SkScalarRound((SkIntToScalar(rx) - passRadius) * 255);
@@ -1021,3 +1029,155 @@ bool SkBlurMask::Blur(SkMask* dst, const SkMask& src,
 {
     return SkBlurMask::Blur(dst, src, radius, style, quality, margin, false);
 }
+
+/* Convolving a box with itself three times results in a piecewise
+   quadratic function:
+   
+   0                              x <= -1.5
+   9/8 + 3/2 x + 1/2 x^2   -1.5 < x <= 1.5
+   3/4 - x^2                -.5 < x <= .5
+   9/8 - 3/2 x + 1/2 x^2    0.5 < x <= 1.5
+   0                        1.5 < x
+   
+   To get the profile curve of the blurred step function at the rectangle
+   edge, we evaluate the indefinite integral, which is piecewise cubic:
+   
+   0                                        x <= -1.5
+   5/8 + 9/8 x + 3/4 x^2 + 1/6 x^3   -1.5 < x <= -0.5
+   1/2 + 3/4 x - 1/3 x^3              -.5 < x <= .5
+   3/8 + 9/8 x - 3/4 x^2 + 1/6 x^3     .5 < x <= 1.5
+   1                                  1.5 < x
+*/
+
+static float gaussian_integral( float x ) {
+    if ( x > 1.5f ) {
+        return 0.0f;
+    }
+    if ( x < -1.5f ) {
+        return 1.0f;
+    }
+
+    float x2 = x*x;
+    float x3 = x2*x;
+
+    if ( x > 0.5 ) {
+        return .5625 - ( x3 / 6 - 3 * x2 / 4 + 1.125 * x);
+    }
+    if ( x > -0.5 ) {
+        return 0.5 - (0.75 * x - x3 / 3);
+    }
+    return 0.4375 + (-x3 / 6 - 3 * x2 / 4 - 1.125 * x);
+}
+
+/* 
+    compute_profile allocates and fills in an array of floating
+    point values between 0 and 255 for the profile signature of 
+    a blurred half-plane with the given blur radius.  Since we're
+    going to be doing screened multiplications (i.e., 1 - (1-x)(1-y))
+    all the time, we actually fill in the profile pre-inverted
+    (already done 255-x).
+    
+    The function returns the size of the array allocated for the
+    profile.  It's the responsibility of the caller to delete the 
+    memory returned in profile_out.
+*/
+
+static int compute_profile( SkScalar radius, unsigned int **profile_out ) {
+    int size = radius * 3 + 1;
+    int center = size >> 1;
+
+    unsigned int *profile = new unsigned int [size];
+
+    float invr = 1.0f/radius;
+
+    profile[0] = 255;
+    for (int x = 1 ; x < size ; x++) {
+        float scaled_x = ( center - x ) * invr;
+        float gi = gaussian_integral( scaled_x );
+        profile[x] = 255 - (uint8_t) ( 255.f * gi );
+    }
+
+    *profile_out = profile;
+    return size;
+}
+
+// TODO MAYBE: Maintain a profile cache to avoid recomputing this for 
+// commonly used radii.  Consider baking some of the most common blur radii
+// directly in as static data?
+
+// Implementation adapted from Michael Herf's approach:
+// http://stereopsis.com/shadowrect/
+
+bool SkBlurMask::BlurRect(SkMask *dst, const SkRect &src,
+                          SkScalar provided_radius, Style style, Quality quality,
+                          SkIPoint *margin) {
+    int profile_size;
+    unsigned int *profile;
+  
+    
+    float radius = SkScalarToFloat( SkScalarMul( provided_radius, kBlurRadiusFudgeFactor ) );
+  
+    profile_size = compute_profile( radius, &profile );
+  
+    int pad = (int) (radius * 1.5f + 1);
+    if (margin) {
+        margin->set( pad, pad );
+    }
+    dst->fBounds = SkIRect::MakeWH(src.width(), src.height());
+    dst->fBounds.outset(pad, pad);
+    
+    dst->fRowBytes = dst->fBounds.width();
+    dst->fFormat = SkMask::kA8_Format;
+    dst->fImage = NULL;
+  
+    size_t dstSize = dst->computeImageSize();
+    if (0 == dstSize) {
+        return false;   // too big to allocate, abort
+    }
+  
+    int             sw = src.width();
+    int             sh = src.height();
+  
+    uint8_t*        dp = SkMask::AllocImage(dstSize);
+  
+    dst->fImage = dp;
+  
+    SkAutoTCallVProc<uint8_t, SkMask_FreeImage> autoCall(dp);
+  
+    int dst_height = dst->fBounds.height();
+    int dst_width = dst->fBounds.width();
+  
+    // nearest odd number less than the profile size represents the center
+    // of the (2x scaled) profile
+    int center = ( profile_size & ~1 ) - 1;
+  
+    int w = sw - center;
+    int h = sh - center;
+  
+    uint8_t *outptr = dp;
+  
+    for (int y = 0 ; y < dst_height ; y++)
+    {
+        // time to fill in a scanline of the blurry rectangle.
+        // to avoid floating point math, everything is multiplied by
+        // 2 where needed.  This keeps things nice and integer-oriented.
+  
+        int dy = abs((y << 1) - dst_height) - h; // how far are we from the original edge?
+        int oy = dy >> 1;
+        if (oy < 0) oy = 0;
+  
+        unsigned int profile_y = profile[oy];
+  
+        for (int x = 0 ; x < (dst_width << 1) ; x += 2) {
+            int dx = abs( x - dst_width ) - w;
+            int ox = dx >> 1;
+            if (ox < 0) ox = 0;
+  
+            unsigned int maskval = SkMulDiv255Round(profile[ox], profile_y);
+  
+            *(outptr++) = maskval;
+        }
+    }
+  
+    return true;
+}
diff --git a/src/effects/SkBlurMask.h b/src/effects/SkBlurMask.h
index cfd7e67bd0..a15dabcf05 100644
--- a/src/effects/SkBlurMask.h
+++ b/src/effects/SkBlurMask.h
@@ -28,6 +28,10 @@ public:
         kHigh_Quality   //!< three pass box blur (similar to gaussian)
     };
 
+    static bool BlurRect(SkMask *dst, const SkRect &src, 
+                         SkScalar radius, Style style, Quality quality, 
+                         SkIPoint *margin = NULL);
+
     static bool Blur(SkMask* dst, const SkMask& src,
                      SkScalar radius, Style style, Quality quality,
                      SkIPoint* margin = NULL);