Hook in rough distance field support for fonts

src/gpu/GrTextStrike.cpp

 /*
  * Copyright 2010 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "GrAtlas.h"
 #include "GrGpu.h"
 #include "GrRectanizer.h"
 #include "GrTextStrike.h"
 #include "GrTextStrike_impl.h"
 #include "SkString.h"
 
 SK_DEFINE_INST_COUNT(GrFontScaler)
 SK_DEFINE_INST_COUNT(GrKey)
 
 ///////////////////////////////////////////////////////////////////////////////
 
 #define FONT_CACHE_STATS 0
 #if FONT_CACHE_STATS
 static int g_PurgeCount = 0;
 #endif
 
+void edtaa2(unsigned char *img, int w, int h, short *distx, short *disty, float *dist);
+
 GrFontCache::GrFontCache(GrGpu* gpu) : fGpu(gpu) {
     gpu->ref();
     for (int i = 0; i < kMaskFormatCount; ++i) {
         fAtlasMgr[i] = NULL;
     }
 
     fHead = fTail = NULL;
 }
 
 GrFontCache::~GrFontCache() {
@@ skipping 152 matching lines @@
     ++gDumpCount;
 }
 #endif
 
 ///////////////////////////////////////////////////////////////////////////////
 
 #ifdef SK_DEBUG
     static int gCounter;
 #endif
 
+#define DISTANCE_FIELD_PAD   4
+#define DISTANCE_FIELD_RANGE (4.f)
+
 /*
     The text strike is specific to a given font/style/matrix setup, which is
     represented by the GrHostFontScaler object we are given in getGlyph().
 
     We map a 32bit glyphID to a GrGlyph record, which in turn points to a
     atlas and a position within that texture.
  */
 
 GrTextStrike::GrTextStrike(GrFontCache* cache, const GrKey* key,
                            GrMaskFormat format,
@@ skipping 33 matching lines @@
 }
 
 GrGlyph* GrTextStrike::generateGlyph(GrGlyph::PackedID packed,
                                      GrFontScaler* scaler) {
     SkIRect bounds;
     if (!scaler->getPackedGlyphBounds(packed, &bounds)) {
         return NULL;
     }
 
     GrGlyph* glyph = fPool.alloc();
+    // expand bounds to hold full distance field data
+    if (fUseDistanceField) {
+        bounds.fLeft   -= DISTANCE_FIELD_PAD;
+        bounds.fRight  += DISTANCE_FIELD_PAD;
+        bounds.fTop    -= DISTANCE_FIELD_PAD;
+        bounds.fBottom += DISTANCE_FIELD_PAD;
+    }
     glyph->init(packed, bounds);
     fCache.insert(packed, glyph);
     return glyph;
 }
 
 bool GrTextStrike::removeUnusedPlots() {
     fCache.getArray().visitAll(invalidate_glyph);
     return fAtlasMgr->removeUnusedPlots(&fAtlas);
 }
 
+
 bool GrTextStrike::getGlyphAtlas(GrGlyph* glyph, GrFontScaler* scaler) {
 #if 0   // testing hack to force us to flush our cache often
     static int gCounter;
     if ((++gCounter % 10) == 0) return false;
 #endif
 
     SkASSERT(glyph);
     SkASSERT(scaler);
     SkASSERT(fCache.contains(glyph));
     SkASSERT(NULL == glyph->fPlot);
 
     SkAutoRef ar(scaler);
 
     int bytesPerPixel = GrMaskFormatBytesPerPixel(fMaskFormat);
-    size_t size = glyph->fBounds.area() * bytesPerPixel;
-    SkAutoSMalloc<1024> storage(size);
-    if (!scaler->getPackedGlyphImage(glyph->fPackedID, glyph->width(),
-                                     glyph->height(),
-                                     glyph->width() * bytesPerPixel,
-                                     storage.get())) {
-        return false;
+
+    GrPlot* plot;
+    if (fUseDistanceField) {
+        SkASSERT(1 == bytesPerPixel);
+
+        // we've already expanded the glyph dimensions to match the final size
+        // but must shrink back down to get the packed glyph data
+        int dfwidth = glyph->width();
+        int dfheight = glyph->height();
+        int width = dfwidth - 2*DISTANCE_FIELD_PAD;
+        int height = dfheight - 2*DISTANCE_FIELD_PAD;
+        size_t stride = width*bytesPerPixel;
+
+        size_t size = width * height * bytesPerPixel;
+        SkAutoSMalloc<1024> storage(size);
+        if (!scaler->getPackedGlyphImage(glyph->fPackedID, width, height, stride, storage.get())) {
+            return false;
+        }
+
+        // alloc storage for distance field glyph
+        size_t dfsize = dfwidth * dfheight * bytesPerPixel;
+        SkAutoSMalloc<1024> dfstorage(dfsize);
+
+        // copy glyph into distance field storage
+        memset(dfstorage.get(), 0, dfsize);
+
+        unsigned char* ptr = (unsigned char*) storage.get();
+        unsigned char* dfptr = (unsigned char*) dfstorage.get();
+        size_t dfstride = dfwidth*bytesPerPixel;
+        dfptr += DISTANCE_FIELD_PAD*dfstride;
+        dfptr += DISTANCE_FIELD_PAD*bytesPerPixel;
+
+        for (int i = 0; i < height; ++i) {
+            memcpy(dfptr, ptr, stride);
+
+            dfptr += dfstride;
+            ptr += stride;
+        }
+
+        // generate distance field data
+        short* distx = new short[dfwidth*dfheight];
+        short* disty = new short[dfwidth*dfheight];
+        float* outerdist = new float[dfwidth*dfheight];
+        dfptr = (unsigned char*) dfstorage.get();
+        edtaa2(dfptr, dfwidth, dfheight, distx, disty, outerdist);
+
+        for (int i = 0; i < dfwidth*dfheight; ++i) {
+            *dfptr++ = 255 - *dfptr;
+        }
+        float* innerdist = new float[dfwidth*dfheight];
+        dfptr = (unsigned char*) dfstorage.get();
+        edtaa2(dfptr, dfwidth, dfheight, distx, disty, innerdist);
+
+        for (int i = 0; i < dfwidth*dfheight; ++i) {
+            unsigned char val;
+            float outerval = outerdist[i];
+            if (outerval < 0.0f) { outerval = 0.0f; }
+            float innerval = innerdist[i];
+            if (innerval < 0.0f) { innerval = 0.0f; }
+            float dist = outerval - innerval;
+            if (dist <= -DISTANCE_FIELD_RANGE) {
+                val = 255;
+            } else if (dist > DISTANCE_FIELD_RANGE) {
+                val = 0;
+            } else {
+                val = (unsigned char)((DISTANCE_FIELD_RANGE-dist)*128.f/DISTANCE_FIELD_RANGE);
+            }
+            *dfptr++ = val;
+        }
+
+        delete [] distx;
+        delete [] disty;
+        delete [] innerdist;
+        delete [] outerdist;
+        
+        // copy to atlas
+        plot = fAtlasMgr->addToAtlas(&fAtlas, dfwidth, dfheight, dfstorage.get(), 
+                                             &glyph->fAtlasLocation);
+
+    } else {
+        size_t size = glyph->fBounds.area() * bytesPerPixel;
+        SkAutoSMalloc<1024> storage(size);
+        if (!scaler->getPackedGlyphImage(glyph->fPackedID, glyph->width(),
+                                         glyph->height(),
+                                         glyph->width() * bytesPerPixel,
+                                         storage.get())) {
+            return false;
+        }
+
+        plot = fAtlasMgr->addToAtlas(&fAtlas, glyph->width(), glyph->height(), storage.get(), 
+                                             &glyph->fAtlasLocation);
     }
 
-    GrPlot* plot = fAtlasMgr->addToAtlas(&fAtlas, glyph->width(),
-                                         glyph->height(), storage.get(),
-                                         &glyph->fAtlasLocation);
     if (NULL == plot) {
         return false;
     }
 
     glyph->fPlot = plot;
     return true;
 }
+
+
+//////////////////////////////////////////////////////////////////////////////////////
+
+/*
+ * A hairy function to approximate the distance to an edge in a certain pixel,
+ * with consideration to both the direction to the pixel, the local gradient
+ * at that pixel and its greyscale value.
+ * This function is complicated enough to warrant a function call for each
+ * evaluation. Inlining it with a macro would only obfuscate the code.
+ */
+static float distaa2(unsigned char *img, int w, int c, int xc, int yc, int xi, int yi)
+{
+  float di, df, gx, gy, a, a1, temp;
+
+  a = (float)(img[c-xc-yc*w])/255.f; // Grayscale value at the edge pixel pointed to
+  if(a < 0.0f) a = 0.0f; // Clip grayscale values outside the range [0,1]
+  if(a == 0.0f) return 1000000.0f; // Not an object pixel, return "very far" ("don't know yet")
+  if(a > 1.0) a = 1.0f;
+  df = 0.5f-a;  // Linear function is correct if gx==0 or gy==0
+
+  gx = (float)abs(xi); // Move to first quadrant gx>=0, gy>=0 (sign symmetry)
+  gy = (float)abs(yi);
+  di = sqrtf(gx*gx+gy*gy); // Length of integer vector, like a traditional EDT
+  if ((gx > 0) && (gy > 0)) { // Neither gx nor gy are zero
+        gx = gx / di;
+        gy = gy / di;
+    if(gx<gy) { // Move to first octant gx >= gy (transposition symmetry)
+      temp = gx;
+      gx = gy;
+      gy = temp;
+    }
+    a1 = 0.5f*gy/gx; // area of corner triangle
+    if (a < a1) // 0 <= a < a1, square root characteristic
+      df = 0.5f*(gx + gy) - sqrtf(2.0f*a*gx*gy);
+    else if (a <= (1.0f-a1)) // a1 <= a <= 1-a1, linear characteristic
+      df = (0.5f-a)*gx;
+    else // a1 < a <= 1, square root characteristic
+      df = -0.5f*(gx + gy) + sqrtf(2.0f*(1.0f-a)*gx*gy);
+  }
+  return di + df; // Negative at edge pixels (di=0) with a>0.5 (df<0)
+}
+
+// Shorthand macro: add ubiquitous parameters dist, img and w and call distaa2()
+#define DISTAA2(c,xc,yc,xi,yi) (distaa2(img, w, c, xc, yc, xi, yi))
+
+static void edtaa2(unsigned char *img, int w, int h, short *distx, short *disty, float *dist)
+{
+  int x, y, i, c;
+  int offset_u, offset_ur, offset_r, offset_rd,
+  offset_d, offset_dl, offset_l, offset_lu;
+  float olddist, newdist;
+  int cdistx, cdisty, newdistx, newdisty;
+  int changed;
+
+  /* Initialize index offsets for the current image width */
+  offset_u = -w;
+  offset_ur = -w+1;
+  offset_r = 1;
+  offset_rd = w+1;
+  offset_d = w;
+  offset_dl = w-1;
+  offset_l = -1;
+  offset_lu = -w-1;
+
+  /* Initialize the distance images */
+  for(i=0; i<w*h; i++) {
+      float val = (float)(img[i])/255.f;
+    distx[i] = 0; // At first, all pixels point to
+    disty[i] = 0; // themselves as the closest known.
+    if(val == 0)
+      {
+        dist[i]= 1000000.0f; // Big value, means "not set yet"
+      }
+    else if (val < 1.0f) {
+      dist[i] = 0.5f-val; // Reasonable local guess
+    }
+    else {
+      dist[i]= 0.0f; // Inside the object
+    }
+  }
+
+  /* Perform the transformation */
+  do
+    {
+      changed = 0;
+
+      /* Scan rows, except first row */
+      for(y=1; y<h; y++)
+        {
+
+          /* move index to leftmost pixel of current row */
+          i = y*w;
+
+          /* scan right, propagate distances from above & left */
+
+          /* Leftmost pixel is special, has no left neighbors */
+          olddist = dist[i];
+          if(olddist > 0) // If non-zero distance or not set yet
+            {
+              c = i + offset_u; // Index of candidate for testing
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx;
+              newdisty = cdisty+1;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  olddist=newdist;
+                  changed = 1;
+                }
+
+              c = i+offset_ur;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx-1;
+              newdisty = cdisty+1;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  changed = 1;
+                }
+            }
+          i++;
+
+          /* Middle pixels have all neighbors */
+          for(x=1; x<w-1; x++, i++)
+            {
+              olddist = dist[i];
+              if(olddist <= 0) continue; // No need to update further
+
+              c = i+offset_l;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx+1;
+              newdisty = cdisty;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  olddist=newdist;
+                  changed = 1;
+                }
+
+              c = i+offset_lu;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx+1;
+              newdisty = cdisty+1;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  olddist=newdist;
+                  changed = 1;
+                }
+
+              c = i+offset_u;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx;
+              newdisty = cdisty+1;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  olddist=newdist;
+                  changed = 1;
+                }
+
+              c = i+offset_ur;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx-1;
+              newdisty = cdisty+1;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  changed = 1;
+                }
+            }
+
+          /* Rightmost pixel of row is special, has no right neighbors */
+          olddist = dist[i];
+          if(olddist > 0) // If not already zero distance
+            {
+              c = i+offset_l;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx+1;
+              newdisty = cdisty;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  olddist=newdist;
+                  changed = 1;
+                }
+
+              c = i+offset_lu;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx+1;
+              newdisty = cdisty+1;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  olddist=newdist;
+                  changed = 1;
+                }
+
+              c = i+offset_u;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx;
+              newdisty = cdisty+1;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  changed = 1;
+                }
+            }
+
+          /* Move index to second rightmost pixel of current row. */
+          /* Rightmost pixel is skipped, it has no right neighbor. */
+          i = y*w + w-2;
+
+          /* scan left, propagate distance from right */
+          for(x=w-2; x>=0; x--, i--)
+            {
+              olddist = dist[i];
+              if(olddist <= 0) continue; // Already zero distance
+
+              c = i+offset_r;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx-1;
+              newdisty = cdisty;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  changed = 1;
+                }
+            }
+        }
+      
+      /* Scan rows in reverse order, except last row */
+      for(y=h-2; y>=0; y--)
+        {
+          /* move index to rightmost pixel of current row */
+          i = y*w + w-1;
+
+          /* Scan left, propagate distances from below & right */
+
+          /* Rightmost pixel is special, has no right neighbors */
+          olddist = dist[i];
+          if(olddist > 0) // If not already zero distance
+            {
+              c = i+offset_d;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx;
+              newdisty = cdisty-1;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  olddist=newdist;
+                  changed = 1;
+                }
+
+              c = i+offset_dl;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx+1;
+              newdisty = cdisty-1;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  changed = 1;
+                }
+            }
+          i--;
+
+          /* Middle pixels have all neighbors */
+          for(x=w-2; x>0; x--, i--)
+            {
+              olddist = dist[i];
+              if(olddist <= 0) continue; // Already zero distance
+
+              c = i+offset_r;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx-1;
+              newdisty = cdisty;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  olddist=newdist;
+                  changed = 1;
+                }
+
+              c = i+offset_rd;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx-1;
+              newdisty = cdisty-1;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  olddist=newdist;
+                  changed = 1;
+                }
+
+              c = i+offset_d;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx;
+              newdisty = cdisty-1;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  olddist=newdist;
+                  changed = 1;
+                }
+
+              c = i+offset_dl;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx+1;
+              newdisty = cdisty-1;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  changed = 1;
+                }
+            }
+          /* Leftmost pixel is special, has no left neighbors */
+          olddist = dist[i];
+          if(olddist > 0) // If not already zero distance
+            {
+              c = i+offset_r;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx-1;
+              newdisty = cdisty;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  olddist=newdist;
+                  changed = 1;
+                }
+
+              c = i+offset_rd;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx-1;
+              newdisty = cdisty-1;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  olddist=newdist;
+                  changed = 1;
+                }
+
+              c = i+offset_d;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx;
+              newdisty = cdisty-1;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  changed = 1;
+                }
+            }
+
+          /* Move index to second leftmost pixel of current row. */
+          /* Leftmost pixel is skipped, it has no left neighbor. */
+          i = y*w + 1;
+          for(x=1; x<w; x++, i++)
+            {
+              /* scan right, propagate distance from left */
+              olddist = dist[i];
+              if(olddist <= 0) continue; // Already zero distance
+
+              c = i+offset_l;
+              cdistx = distx[c];
+              cdisty = disty[c];
+              newdistx = cdistx+1;
+              newdisty = cdisty;
+              newdist = DISTAA2(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  changed = 1;
+                }
+            }
+        }
+    }
+  while(changed); // Sweep until no more updates are made
+
+  /* The transformation is completed. */
+
+}
+