Revert of Add new module for distance field generation. (https://codereview.chromium.org/178543007/)

Reason for revert:
multiple compile errors

Original issue's description:
> 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
>
> Committed: http://code.google.com/p/skia/source/detail?r=13729

R=bsalomon@google.com, robertphillips@google.com, jvanverth@google.com
TBR=bsalomon@google.com, jvanverth@google.com, robertphillips@google.com
NOTREECHECKS=true
NOTRY=true
BUG=skia:2173

Author: halcanary@google.com

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

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

10 files changed, 750 insertions, 473 deletions

diff --git a/gm/gmmain.cpp b/gm/gmmain.cpp
index de9e1a15a0..165c5affb7 100644
--- a/gm/gmmain.cpp
+++ b/gm/gmmain.cpp
@@ -46,7 +46,6 @@
 
 #ifdef SK_DEBUG
 static const bool kDebugOnly = true;
-#define GR_DUMP_FONT_CACHE 0
 #else
 static const bool kDebugOnly = false;
 #endif
@@ -2409,18 +2408,6 @@ int tool_main(int argc, char** argv) {
     }
 #endif
 
-#if GR_DUMP_FONT_CACHE
-    for (int i = 0; i < configs.count(); i++) {
-        ConfigData config = gRec[configs[i]];
-
-        if (kGPU_Backend == config.fBackend) {
-            GrContext* gr = grFactory->get(config.fGLContextType);
-
-           gr->dumpFontCache();
-        }
-    }
-#endif
-
     delete grFactory;
 #endif
     SkGraphics::Term();
diff --git a/gyp/core.gypi b/gyp/core.gypi
index cdb0bab1d7..a1eed0a729 100644
--- a/gyp/core.gypi
+++ b/gyp/core.gypi
@@ -70,8 +70,6 @@
         '<(skia_src_path)/core/SkDeviceProfile.cpp',
         '<(skia_src_path)/lazy/SkDiscardableMemoryPool.cpp',
         '<(skia_src_path)/lazy/SkDiscardablePixelRef.cpp',
-        '<(skia_src_path)/core/SkDistanceFieldGen.cpp',
-        '<(skia_src_path)/core/SkDistanceFieldGen.h',
         '<(skia_src_path)/core/SkDither.cpp',
         '<(skia_src_path)/core/SkDraw.cpp',
         '<(skia_src_path)/core/SkDrawLooper.cpp',
diff --git a/gyp/edtaa.gyp b/gyp/edtaa.gyp
new file mode 100755
index 0000000000..4f7272e5b2
--- /dev/null
+++ b/gyp/edtaa.gyp
@@ -0,0 +1,31 @@
+#
+# Copyright 2013 Google Inc.
+#
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+#
+
+{
+  'targets': [
+    {
+      'target_name': 'edtaa',
+      'type': 'none',
+      'conditions': [
+        [ 'skia_distancefield_fonts', {
+          'type': 'static_library',
+          'sources': [
+            '../third_party/edtaa/edtaa3func.cpp',
+          ],
+          'include_dirs': [
+            '../third_party/edtaa/',
+          ],
+          'all_dependent_settings': {
+            'include_dirs': [
+              '../third_party/edtaa/',
+            ],
+          },
+        }],
+      ],
+    },
+  ],
+}
diff --git a/gyp/gpu.gyp b/gyp/gpu.gyp
index f303eb50d8..471004cbe4 100644
--- a/gyp/gpu.gyp
+++ b/gyp/gpu.gyp
@@ -83,6 +83,7 @@
       'standalone_static_library': 1,
       'dependencies': [
         'core.gyp:*',
+        'edtaa.gyp:*',
         'utils.gyp:*',
       ],
       'includes': [
diff --git a/src/core/SkDistanceFieldGen.cpp b/src/core/SkDistanceFieldGen.cpp
deleted file mode 100755
index fb7131e2b9..0000000000
--- a/src/core/SkDistanceFieldGen.cpp
+++ /dev/null
@@ -1,401 +0,0 @@
-/*
- * 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
deleted file mode 100755
index 3d2ec23b75..0000000000
--- a/src/core/SkDistanceFieldGen.h
+++ /dev/null
@@ -1,25 +0,0 @@
-/*
- * 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
diff --git a/src/gpu/GrTextStrike.cpp b/src/gpu/GrTextStrike.cpp
index 0d7fcafe67..e303a23df8 100644
--- a/src/gpu/GrTextStrike.cpp
+++ b/src/gpu/GrTextStrike.cpp
@@ -13,7 +13,7 @@
 #include "SkString.h"
 
 #if SK_DISTANCEFIELD_FONTS
-#include "SkDistanceFieldGen.h"
+#include "edtaa3.h"
 #endif
 
 ///////////////////////////////////////////////////////////////////////////////
@@ -199,9 +199,8 @@ void GrFontCache::dump() const {
 #endif
 
 #if SK_DISTANCEFIELD_FONTS
-// this acts as the max magnitude for the distance field,
-// as well as the pad we need around the glyph
-#define DISTANCE_FIELD_RANGE   4
+#define DISTANCE_FIELD_PAD   4
+#define DISTANCE_FIELD_RANGE (4.0)
 #endif
 
 /*
@@ -254,10 +253,10 @@ GrGlyph* GrTextStrike::generateGlyph(GrGlyph::PackedID packed,
 #if SK_DISTANCEFIELD_FONTS
     // expand bounds to hold full distance field data
     if (fUseDistanceField) {
-        bounds.fLeft   -= DISTANCE_FIELD_RANGE;
-        bounds.fRight  += DISTANCE_FIELD_RANGE;
-        bounds.fTop    -= DISTANCE_FIELD_RANGE;
-        bounds.fBottom += DISTANCE_FIELD_RANGE;
+        bounds.fLeft   -= DISTANCE_FIELD_PAD;
+        bounds.fRight  += DISTANCE_FIELD_PAD;
+        bounds.fTop    -= DISTANCE_FIELD_PAD;
+        bounds.fBottom += DISTANCE_FIELD_PAD;
     }
 #endif
     glyph->init(packed, bounds);
@@ -295,13 +294,15 @@ bool GrTextStrike::addGlyphToAtlas(GrGlyph* glyph, GrFontScaler* scaler) {
     GrPlot* plot;
 #if SK_DISTANCEFIELD_FONTS
     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_RANGE;
-        int height = dfHeight - 2*DISTANCE_FIELD_RANGE;
-        int stride = width*bytesPerPixel;
+        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);
@@ -312,28 +313,71 @@ bool GrTextStrike::addGlyphToAtlas(GrGlyph* glyph, GrFontScaler* scaler) {
         // alloc storage for distance field glyph
         size_t dfSize = dfWidth * dfHeight * bytesPerPixel;
         SkAutoSMalloc<1024> dfStorage(dfSize);
-        
-        if (1 == bytesPerPixel) {
-            (void) SkGenerateDistanceFieldFromImage((unsigned char*)dfStorage.get(),
-                                                    (unsigned char*)storage.get(),
-                                                    width, height, DISTANCE_FIELD_RANGE);
-        } else {
-            // TODO: Fix color emoji
-            // for now, copy glyph into distance field storage
-            // this is not correct, but it won't crash
-            sk_bzero(dfStorage.get(), dfSize);
-            unsigned char* ptr = (unsigned char*) storage.get();
-            unsigned char* dfPtr = (unsigned char*) dfStorage.get();
-            size_t dfStride = dfWidth*bytesPerPixel;
-            dfPtr += DISTANCE_FIELD_RANGE*dfStride;
-            dfPtr += DISTANCE_FIELD_RANGE*bytesPerPixel;
-
-            for (int i = 0; i < height; ++i) {
-                memcpy(dfPtr, ptr, stride);
-
-                dfPtr += dfStride;
-                ptr += stride;
+
+        // copy glyph into distance field storage
+        sk_bzero(dfStorage.get(), 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
+        SkAutoSMalloc<1024> distXStorage(dfWidth*dfHeight*sizeof(short));
+        SkAutoSMalloc<1024> distYStorage(dfWidth*dfHeight*sizeof(short));
+        SkAutoSMalloc<1024> outerDistStorage(dfWidth*dfHeight*sizeof(double));
+        SkAutoSMalloc<1024> innerDistStorage(dfWidth*dfHeight*sizeof(double));
+        SkAutoSMalloc<1024> gxStorage(dfWidth*dfHeight*sizeof(double));
+        SkAutoSMalloc<1024> gyStorage(dfWidth*dfHeight*sizeof(double));
+
+        short* distX = (short*) distXStorage.get();
+        short* distY = (short*) distYStorage.get();
+        double* outerDist = (double*) outerDistStorage.get();
+        double* innerDist = (double*) innerDistStorage.get();
+        double* gx = (double*) gxStorage.get();
+        double* gy = (double*) gyStorage.get();
+
+        dfPtr = (unsigned char*) dfStorage.get();
+        EDTAA::computegradient(dfPtr, dfWidth, dfHeight, gx, gy);
+        EDTAA::edtaa3(dfPtr, gx, gy, dfWidth, dfHeight, distX, distY, outerDist);
+
+        for (int i = 0; i < dfWidth*dfHeight; ++i) {
+            *dfPtr = 255 - *dfPtr;
+            dfPtr++;
+        }
+        dfPtr = (unsigned char*) dfStorage.get();
+        sk_bzero(gx, sizeof(double)*dfWidth*dfHeight);
+        sk_bzero(gy, sizeof(double)*dfWidth*dfHeight);
+        EDTAA::computegradient(dfPtr, dfWidth, dfHeight, gx, gy);
+        EDTAA::edtaa3(dfPtr, gx, gy, dfWidth, dfHeight, distX, distY, innerDist);
+
+        for (int i = 0; i < dfWidth*dfHeight; ++i) {
+            unsigned char val;
+            double outerval = outerDist[i];
+            if (outerval < 0.0) {
+                outerval = 0.0;
+            }
+            double innerval = innerDist[i];
+            if (innerval < 0.0) {
+                innerval = 0.0;
+            }
+            double 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.0/DISTANCE_FIELD_RANGE);
             }
+            *dfPtr++ = val;
         }
 
         // copy to atlas
diff --git a/third_party/edtaa/LICENSE b/third_party/edtaa/LICENSE
new file mode 100755
index 0000000000..a5aa0d4c41
--- /dev/null
+++ b/third_party/edtaa/LICENSE
@@ -0,0 +1,21 @@
+The MIT License (MIT)
+
+Copyright (c) 2009-2012 Stefan Gustavson (stefan.gustavson@gmail.com)
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
diff --git a/third_party/edtaa/edtaa3.h b/third_party/edtaa/edtaa3.h
new file mode 100755
index 0000000000..9db3c6e67b
--- /dev/null
+++ b/third_party/edtaa/edtaa3.h
@@ -0,0 +1,35 @@
+/* 
+ Permission is hereby granted, free of charge, to any person obtaining a copy
+ of this software and associated documentation files (the "Software"), to deal
+ in the Software without restriction, including without limitation the rights
+ to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ copies of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+
+ The above copyright notice and this permission notice shall be included in
+ all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ THE SOFTWARE.
+ */
+
+#define EDTAA_UNSIGNED_CHAR_INPUT 1
+
+namespace EDTAA {
+
+#if EDTAA_UNSIGNED_CHAR_INPUT
+typedef unsigned char EdtaaImageType;
+#else
+typedef double EdtaaImageType;
+#endif
+
+void computegradient(EdtaaImageType *img, int w, int h, double *gx, double *gy);
+void edtaa3(EdtaaImageType *img, double *gx, double *gy, int w, int h, 
+                   short *distx, short *disty, double *dist);
+
+}
diff --git a/third_party/edtaa/edtaa3func.cpp b/third_party/edtaa/edtaa3func.cpp
new file mode 100755
index 0000000000..a09428ae52
--- /dev/null
+++ b/third_party/edtaa/edtaa3func.cpp
@@ -0,0 +1,586 @@
+/*
+ * edtaa3()
+ *
+ * Sweep-and-update Euclidean distance transform of an
+ * image. Positive pixels are treated as object pixels,
+ * zero or negative pixels are treated as background.
+ * An attempt is made to treat antialiased edges correctly.
+ * The input image must have pixels in the range [0,1],
+ * and the antialiased image should be a box-filter
+ * sampling of the ideal, crisp edge.
+ * If the antialias region is more than 1 pixel wide,
+ * the result from this transform will be inaccurate.
+ *
+ * By Stefan Gustavson (stefan.gustavson@gmail.com).
+ *
+ * Originally written in 1994, based on a verbal
+ * description of the SSED8 algorithm published in the
+ * PhD dissertation of Ingemar Ragnemalm. This is his
+ * algorithm, I only implemented it in C.
+ *
+ * Updated in 2004 to treat border pixels correctly,
+ * and cleaned up the code to improve readability.
+ *
+ * Updated in 2009 to handle anti-aliased edges.
+ *
+ * Updated in 2011 to avoid a corner case infinite loop.
+ *
+ * Updated 2012 to change license from LGPL to MIT.
+ */
+
+/*
+ Copyright (C) 2009-2012 Stefan Gustavson (stefan.gustavson@gmail.com)
+ The code in this file is distributed under the MIT license:
+
+ Permission is hereby granted, free of charge, to any person obtaining a copy
+ of this software and associated documentation files (the "Software"), to deal
+ in the Software without restriction, including without limitation the rights
+ to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ copies of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+
+ The above copyright notice and this permission notice shall be included in
+ all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ THE SOFTWARE.
+ */
+
+#include "edtaa3.h"
+
+#include <math.h>
+
+#if EDTAA_UNSIGNED_CHAR_INPUT
+#define IMG(i) ((double)(img[i] & 0xff)/256.0)
+#else
+#define IMG(i) (img[i])
+#endif
+
+namespace EDTAA {
+
+/*
+ * Compute the local gradient at edge pixels using convolution filters.
+ * The gradient is computed only at edge pixels. At other places in the
+ * image, it is never used, and it's mostly zero anyway.
+ */
+void computegradient(EdtaaImageType *img, int w, int h, double *gx, double *gy)
+{
+    int i,j,k;
+    double glength;
+#define SQRT2 1.4142136
+    for(i = 1; i < h-1; i++) { // Avoid edges where the kernels would spill over
+        for(j = 1; j < w-1; j++) {
+            k = i*w + j;
+            if((IMG(k)>0.0) && (IMG(k)<1.0)) { // Compute gradient for edge pixels only
+                gx[k] = -IMG(k-w-1) - SQRT2*IMG(k-1) - IMG(k+w-1) + IMG(k-w+1) + SQRT2*IMG(k+1) + IMG(k+w+1);
+                gy[k] = -IMG(k-w-1) - SQRT2*IMG(k-w) - IMG(k+w-1) + IMG(k-w+1) + SQRT2*IMG(k+w) + IMG(k+w+1);
+                glength = gx[k]*gx[k] + gy[k]*gy[k];
+                if(glength > 0.0) { // Avoid division by zero
+                    glength = sqrt(glength);
+                    gx[k]=gx[k]/glength;
+                    gy[k]=gy[k]/glength;
+                }
+            }
+        }
+    }
+    // TODO: Compute reasonable values for gx, gy also around the image edges.
+    // (These are zero now, which reduces the accuracy for a 1-pixel wide region
+	// around the image edge.) 2x2 kernels would be suitable for this.
+}
+
+/*
+ * A somewhat tricky function to approximate the distance to an edge in a
+ * certain pixel, with consideration to either the local gradient (gx,gy)
+ * or the direction to the pixel (dx,dy) and the pixel greyscale value a.
+ * The latter alternative, using (dx,dy), is the metric used by edtaa2().
+ * Using a local estimate of the edge gradient (gx,gy) yields much better
+ * accuracy at and near edges, and reduces the error even at distant pixels
+ * provided that the gradient direction is accurately estimated.
+ */
+static double edgedf(double gx, double gy, double a)
+{
+    double df, glength, temp, a1;
+
+    if ((gx == 0) || (gy == 0)) { // Either A) gu or gv are zero, or B) both
+        df = 0.5-a;  // Linear approximation is A) correct or B) a fair guess
+    } else {
+        glength = sqrt(gx*gx + gy*gy);
+        if(glength>0) {
+            gx = gx/glength;
+            gy = gy/glength;
+        }
+        /* Everything is symmetric wrt sign and transposition,
+         * so move to first octant (gx>=0, gy>=0, gx>=gy) to
+         * avoid handling all possible edge directions.
+         */
+        gx = fabs(gx);
+        gy = fabs(gy);
+        if(gx<gy) {
+            temp = gx;
+            gx = gy;
+            gy = temp;
+        }
+        a1 = 0.5*gy/gx;
+        if (a < a1) { // 0 <= a < a1
+            df = 0.5*(gx + gy) - sqrt(2.0*gx*gy*a);
+        } else if (a < (1.0-a1)) { // a1 <= a <= 1-a1
+            df = (0.5-a)*gx;
+        } else { // 1-a1 < a <= 1
+            df = -0.5*(gx + gy) + sqrt(2.0*gx*gy*(1.0-a));
+        }
+    }    
+    return df;
+}
+
+static double distaa3(EdtaaImageType *img, double *gximg, double *gyimg, int w, int c, int xc, int yc, int xi, int yi)
+{
+  double di, df, dx, dy, gx, gy, a;
+  int closest;
+  
+  closest = c-xc-yc*w; // Index to the edge pixel pointed to from c
+  a = IMG(closest);    // Grayscale value at the edge pixel
+  gx = gximg[closest]; // X gradient component at the edge pixel
+  gy = gyimg[closest]; // Y gradient component at the edge pixel
+  
+  if(a > 1.0) a = 1.0;
+  if(a < 0.0) a = 0.0; // Clip grayscale values outside the range [0,1]
+  if(a == 0.0) return 1000000.0; // Not an object pixel, return "very far" ("don't know yet")
+
+  dx = (double)xi;
+  dy = (double)yi;
+  di = sqrt(dx*dx + dy*dy); // Length of integer vector, like a traditional EDT
+  if(di==0) { // Use local gradient only at edges
+      // Estimate based on local gradient only
+      df = edgedf(gx, gy, a);
+  } else {
+      // Estimate gradient based on direction to edge (accurate for large di)
+      df = edgedf(dx, dy, a);
+  }
+  return di + df; // Same metric as edtaa2, except at edges (where di=0)
+}
+
+// Shorthand macro: add ubiquitous parameters dist, gx, gy, img and w and call distaa3()
+#define DISTAA(c,xc,yc,xi,yi) (distaa3(img, gx, gy, w, c, xc, yc, xi, yi))
+
+void edtaa3(EdtaaImageType *img, double *gx, double *gy, int w, int h, short *distx, short *disty, double *dist)
+{
+  int x, y, i, c;
+  int offset_u, offset_ur, offset_r, offset_rd,
+  offset_d, offset_dl, offset_l, offset_lu;
+  double olddist, newdist;
+  int cdistx, cdisty, newdistx, newdisty;
+  int changed;
+  double epsilon = 1e-3;
+  double a;
+
+  /* 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++) {
+    distx[i] = 0; // At first, all pixels point to
+    disty[i] = 0; // themselves as the closest known.
+    a = IMG(i);
+    if(a <= 0.0)
+      {
+	dist[i]= 1000000.0; // Big value, means "not set yet"
+      }
+    else if (a<1.0) {
+      dist[i] = edgedf(gx[i], gy[i], a); // Gradient-assisted estimate
+    }
+    else {
+      dist[i]= 0.0; // 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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  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 = DISTAA(c, cdistx, cdisty, newdistx, newdisty);
+              if(newdist < olddist-epsilon)
+                {
+                  distx[i]=newdistx;
+                  disty[i]=newdisty;
+                  dist[i]=newdist;
+                  changed = 1;
+                }
+            }
+        }
+    }
+  while(changed); // Sweep until no more updates are made
+
+  /* The transformation is completed. */
+
+}
+
+} // namespace EDTAA