Add new module for distance field generation.

This improves the speed over the previous method by 10x+, and makes using distance fields practical.

BUG=skia:2173
R=bsalomon@google.com, robertphillips@google.com

Author: jvanverth@google.com

Review URL: https://codereview.chromium.org/178543007

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

2 files changed, 426 insertions, 0 deletions

diff --git a/src/core/SkDistanceFieldGen.cpp b/src/core/SkDistanceFieldGen.cpp
new file mode 100755
index 0000000000..fb7131e2b9
--- /dev/null
+++ b/src/core/SkDistanceFieldGen.cpp
@@ -0,0 +1,401 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkDistanceFieldGen.h"
+#include "SkPoint.h"
+
+struct DFData {
+    float   fAlpha;      // alpha value of source texel
+    float   fDistSq;     // distance squared to nearest (so far) edge texel
+    SkPoint fDistVector; // distance vector to nearest (so far) edge texel
+};
+
+// We treat an "edge" as a place where we cross from a texel >= 128 to a texel < 128,
+// or vice versa. This means we just need to check if the MSBs are different.
+static bool found_edge(const unsigned char* imagePtr, int width) {
+    const int offsets[8] = {-1, 1, -width-1, -width, -width+1, width-1, width, width+1 };
+
+    // search for an edge
+    int checkVal = *imagePtr >> 7;
+    for (int i = 0; i < 8; ++i) {
+        const unsigned char* checkPtr = imagePtr + offsets[i];
+        if (checkVal ^ (*checkPtr >> 7)) {
+            return true;
+        }
+    }
+
+    return false;
+}
+
+static void init_glyph_data(DFData* data, char* edges, const unsigned char* image,
+                            int dataWidth, int dataHeight, 
+                            int imageWidth, int imageHeight,
+                            int pad) {
+    data += pad*dataWidth;
+    data += pad;
+    edges += (pad*dataWidth + pad);
+
+    for (int j = 0; j < imageHeight; ++j) {
+        for (int i = 0; i < imageWidth; ++i) {
+            if (255 == *image) {
+                data->fAlpha = 1.0f;
+            } else {
+                data->fAlpha = (*image)*0.00392156862f;  // 1/255
+            }
+            if (i > 0 && i < imageWidth-1 && j > 0 && j < imageHeight-1 &&
+                found_edge(image, imageWidth)) {
+                *edges = 255;  // using 255 makes for convenient debug rendering
+            }
+            ++data;
+            ++image;
+            ++edges;
+        }
+        data += 2*pad;
+        edges += 2*pad;
+    }
+}
+
+// from Gustavson (2011)
+// computes the distance to an edge given an edge normal vector and a pixel's alpha value
+// assumes that direction has been pre-normalized
+static float edge_distance(const SkPoint& direction, float alpha) {
+    float dx = direction.fX;
+    float dy = direction.fY;
+    float distance;
+    if (SkScalarNearlyZero(dx) || SkScalarNearlyZero(dy)) {
+        distance = 0.5f - alpha;
+    } else {
+        // this is easier if we treat the direction as being in the first octant
+        // (other octants are symmetrical)
+        dx = SkScalarAbs(dx);
+        dy = SkScalarAbs(dy);
+        if (dx < dy) {
+            SkTSwap(dx, dy);
+        }
+
+        // a1 = 0.5*dy/dx is the smaller fractional area chopped off by the edge
+        // to avoid the divide, we just consider the numerator
+        float a1num = 0.5f*dy;
+
+        // we now compute the approximate distance, depending where the alpha falls
+        // relative to the edge fractional area
+
+        // if 0 <= alpha < a1
+        if (alpha*dx < a1num) {
+            // TODO: find a way to do this without square roots?
+            distance = 0.5f*(dx + dy) - SkScalarSqrt(2.0f*dx*dy*alpha);
+        // if a1 <= alpha <= 1 - a1
+        } else if (alpha*dx < (dx - a1num)) {
+            distance = (0.5f - alpha)*dx;
+        // if 1 - a1 < alpha <= 1
+        } else {
+            // TODO: find a way to do this without square roots?
+            distance = -0.5f*(dx + dy) + SkScalarSqrt(2.0f*dx*dy*(1.0f - alpha));
+        }
+    }
+
+    return distance;
+}
+
+static void init_distances(DFData* data, char* edges, int width, int height) {
+    // skip one pixel border
+    DFData* currData = data;
+    DFData* prevData = data - width;
+    DFData* nextData = data + width;
+
+    for (int j = 0; j < height; ++j) {
+        for (int i = 0; i < width; ++i) {
+            if (*edges) {
+                // we should not be in the one-pixel outside band
+                SkASSERT(i > 0 && i < width-1 && j > 0 && j < height-1);
+                // gradient will point from low to high
+                // +y is down in this case
+                // i.e., if you're outside, gradient points towards edge
+                // if you're inside, gradient points away from edge
+                SkPoint currGrad;
+                currGrad.fX = (prevData+1)->fAlpha - (prevData-1)->fAlpha
+                             + SK_ScalarSqrt2*(currData+1)->fAlpha 
+                             - SK_ScalarSqrt2*(currData-1)->fAlpha
+                             + (nextData+1)->fAlpha - (nextData-1)->fAlpha;
+                currGrad.fY = (nextData-1)->fAlpha - (prevData-1)->fAlpha 
+                             + SK_ScalarSqrt2*nextData->fAlpha 
+                             - SK_ScalarSqrt2*prevData->fAlpha
+                             + (nextData+1)->fAlpha - (prevData+1)->fAlpha;
+                currGrad.setLengthFast(1.0f);
+
+                // init squared distance to edge and distance vector
+                float dist = edge_distance(currGrad, currData->fAlpha);
+                currGrad.scale(dist, &currData->fDistVector);
+                currData->fDistSq = dist*dist;
+            } else {
+                // init distance to "far away"
+                currData->fDistSq = 2000000.f;
+                currData->fDistVector.fX = 1000.f;
+                currData->fDistVector.fY = 1000.f;
+            }
+            ++currData;
+            ++prevData;
+            ++nextData;
+            ++edges;
+        }
+    }
+}
+
+// Danielsson's 8SSEDT
+
+// first stage forward pass
+// (forward in Y, forward in X)
+static void F1(DFData* curr, int width) {
+    // upper left
+    DFData* check = curr - width-1;
+    SkPoint distVec = check->fDistVector;
+    float distSq = check->fDistSq - 2.0f*(distVec.fX + distVec.fY - 1.0f);
+    if (distSq < curr->fDistSq) {
+        distVec.fX -= 1.0f;
+        distVec.fY -= 1.0f;
+        curr->fDistSq = distSq;
+        curr->fDistVector = distVec;
+    }
+
+    // up
+    check = curr - width;
+    distVec = check->fDistVector;
+    distSq = check->fDistSq - 2.0f*distVec.fY + 1.0f;
+    if (distSq < curr->fDistSq) {
+        distVec.fY -= 1.0f;
+        curr->fDistSq = distSq;
+        curr->fDistVector = distVec;
+    }
+
+    // upper right
+    check = curr - width+1;
+    distVec = check->fDistVector;
+    distSq = check->fDistSq + 2.0f*(distVec.fX - distVec.fY + 1.0f);
+    if (distSq < curr->fDistSq) {
+        distVec.fX += 1.0f;
+        distVec.fY -= 1.0f;
+        curr->fDistSq = distSq;
+        curr->fDistVector = distVec;
+    }
+
+    // left
+    check = curr - 1;
+    distVec = check->fDistVector;
+    distSq = check->fDistSq - 2.0f*distVec.fX + 1.0f;
+    if (distSq < curr->fDistSq) {
+        distVec.fX -= 1.0f;
+        curr->fDistSq = distSq;
+        curr->fDistVector = distVec;
+    }
+}
+
+// second stage forward pass
+// (forward in Y, backward in X)
+static void F2(DFData* curr, int width) {
+    // right
+    DFData* check = curr + 1;
+    float distSq = check->fDistSq;
+    SkPoint distVec = check->fDistVector;
+    distSq = check->fDistSq + 2.0f*distVec.fX + 1.0f;
+    if (distSq < curr->fDistSq) {
+        distVec.fX += 1.0f;
+        curr->fDistSq = distSq;
+        curr->fDistVector = distVec;
+    }
+}
+
+// first stage backward pass
+// (backward in Y, forward in X)
+static void B1(DFData* curr, int width) {
+    // left
+    DFData* check = curr - 1;
+    SkPoint distVec = check->fDistVector;
+    float distSq = check->fDistSq - 2.0f*distVec.fX + 1.0f;
+    if (distSq < curr->fDistSq) {
+        distVec.fX -= 1.0f;
+        curr->fDistSq = distSq;
+        curr->fDistVector = distVec;
+    }
+}
+
+// second stage backward pass
+// (backward in Y, backwards in X)
+static void B2(DFData* curr, int width) {
+    // right
+    DFData* check = curr + 1;
+    SkPoint distVec = check->fDistVector;
+    float distSq = check->fDistSq + 2.0f*distVec.fX + 1.0f;
+    if (distSq < curr->fDistSq) {
+        distVec.fX += 1.0f;
+        curr->fDistSq = distSq;
+        curr->fDistVector = distVec;
+    }
+
+    // bottom left
+    check = curr + width-1;
+    distVec = check->fDistVector;
+    distSq = check->fDistSq - 2.0f*(distVec.fX - distVec.fY - 1.0f);
+    if (distSq < curr->fDistSq) {
+        distVec.fX -= 1.0f;
+        distVec.fY += 1.0f;
+        curr->fDistSq = distSq;
+        curr->fDistVector = distVec;
+    }
+
+    // bottom
+    check = curr + width;
+    distVec = check->fDistVector;
+    distSq = check->fDistSq + 2.0f*distVec.fY + 1.0f;
+    if (distSq < curr->fDistSq) {
+        distVec.fY += 1.0f;
+        curr->fDistSq = distSq;
+        curr->fDistVector = distVec;
+    }
+
+    // bottom right
+    check = curr + width+1;
+    distVec = check->fDistVector;
+    distSq = check->fDistSq + 2.0f*(distVec.fX + distVec.fY + 1.0f);
+    if (distSq < curr->fDistSq) {
+        distVec.fX += 1.0f;
+        distVec.fY += 1.0f;
+        curr->fDistSq = distSq;
+        curr->fDistVector = distVec;
+    }
+}
+
+static unsigned char pack_distance_field_val(float dist, float distanceMagnitude) {
+    if (dist <= -distanceMagnitude) {
+        return 255;
+    } else if (dist > distanceMagnitude) {
+        return 0;
+    } else {
+        return (unsigned char)((distanceMagnitude-dist)*128.0f/distanceMagnitude);
+    }
+}
+
+// assumes an 8-bit image and distance field
+bool SkGenerateDistanceFieldFromImage(unsigned char* distanceField,
+                                      const unsigned char* image,
+                                      int width, int height,
+                                      int distanceMagnitude) {
+    SkASSERT(NULL != distanceField);
+    SkASSERT(NULL != image);
+
+    // the final distance field will have additional texels on each side to handle
+    // the maximum distance 
+    // we expand our temp data by one more on each side to simplify
+    // the scanning code -- will always be treated as infinitely far away
+    int pad = distanceMagnitude+1;
+
+    // set params for distance field data
+    int dataWidth = width + 2*pad;
+    int dataHeight = height + 2*pad;
+
+    // create temp data
+    size_t dataSize = dataWidth*dataHeight*sizeof(DFData);
+    SkAutoSMalloc<1024> dfStorage(dataSize);
+    DFData* dataPtr = (DFData*) dfStorage.get();
+    sk_bzero(dataPtr, dataSize);
+
+    SkAutoSMalloc<1024> edgeStorage(dataWidth*dataHeight*sizeof(char));
+    char* edgePtr = (char*) edgeStorage.get();
+    sk_bzero(edgePtr, dataWidth*dataHeight*sizeof(char));
+
+    // copy glyph into distance field storage
+    init_glyph_data(dataPtr, edgePtr, image,
+                    dataWidth, dataHeight,
+                    width, height, pad);
+
+    // create initial distance data, particularly at edges
+    init_distances(dataPtr, edgePtr, dataWidth, dataHeight);
+
+    // now perform Euclidean distance transform to propagate distances
+
+    // forwards in y
+    DFData* currData = dataPtr+dataWidth+1; // skip outer buffer
+    char* currEdge = edgePtr+dataWidth+1;
+    for (int j = 1; j < dataHeight-1; ++j) {
+        // forwards in x
+        for (int i = 1; i < dataWidth-1; ++i) {
+            // don't need to calculate distance for edge pixels
+            if (!*currEdge) {
+                F1(currData, dataWidth);
+            }
+            ++currData;
+            ++currEdge;
+        }
+
+        // backwards in x
+        --currData; // reset to end
+        --currEdge;
+        for (int i = 1; i < dataWidth-1; ++i) {
+            // don't need to calculate distance for edge pixels
+            if (!*currEdge) {
+                F2(currData, dataWidth);
+            }
+            --currData;
+            --currEdge;
+        }
+
+        currData += dataWidth+1;
+        currEdge += dataWidth+1;
+    }
+
+    // backwards in y
+    currData = dataPtr+dataWidth*(dataHeight-2) - 1; // skip outer buffer
+    currEdge = edgePtr+dataWidth*(dataHeight-2) - 1;
+    for (int j = 1; j < dataHeight-1; ++j) {
+        // forwards in x
+        for (int i = 1; i < dataWidth-1; ++i) {
+            // don't need to calculate distance for edge pixels
+            if (!*currEdge) {
+                B1(currData, dataWidth);
+            }
+            ++currData;
+            ++currEdge;
+        }
+
+        // backwards in x
+        --currData; // reset to end
+        --currEdge;
+        for (int i = 1; i < dataWidth-1; ++i) {
+            // don't need to calculate distance for edge pixels
+            if (!*currEdge) {
+                B2(currData, dataWidth);
+            }
+            --currData;
+            --currEdge;
+        }
+
+        currData -= dataWidth-1;
+        currEdge -= dataWidth-1;
+    }
+
+    // copy results to final distance field data
+    currData = dataPtr + dataWidth+1;
+    currEdge = edgePtr + dataWidth+1;
+    unsigned char *dfPtr = distanceField;
+    for (int j = 1; j < dataHeight-1; ++j) {
+        for (int i = 1; i < dataWidth-1; ++i) {
+            float dist;
+            if (currData->fAlpha > 0.5f) {
+                dist = -SkScalarSqrt(currData->fDistSq);
+            } else {
+                dist = SkScalarSqrt(currData->fDistSq);
+            }
+
+            *dfPtr++ = pack_distance_field_val(dist, (float)distanceMagnitude);
+            ++currData;
+            ++currEdge;
+        }
+        currData += 2;
+        currEdge += 2;
+    }
+
+    return true;
+}
diff --git a/src/core/SkDistanceFieldGen.h b/src/core/SkDistanceFieldGen.h
new file mode 100755
index 0000000000..3d2ec23b75
--- /dev/null
+++ b/src/core/SkDistanceFieldGen.h
@@ -0,0 +1,25 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#ifndef SkDistanceFieldGen_DEFINED
+#define SkDistanceFieldGen_DEFINED
+
+/** Given 8-bit mask data, generate the associated distance field
+
+ *  @param distanceField     The distance field to be generated. Should already be allocated
+ *                           by the client with the padding below.
+ *  @param image             8-bit mask we're using to generate the distance field.
+ *  @param w                 Width of the image.
+ *  @param h                 Height of the image.
+ *  @param distanceMagnitude Largest possible absolute value for the distance. The distance field
+ *                           will be padded to w + 2*distanceMagnitude, h + 2*distanceMagnitude.
+ */
+bool SkGenerateDistanceFieldFromImage(unsigned char* distanceField,
+                                      const unsigned char* image,
+                                      int w, int h,
+                                      int distanceMagnitude);
+
+#endif