Revert of Add new module for distance field generation.

src/core/SkDistanceFieldGen.cpp

Index: src/core/SkDistanceFieldGen.cpp
diff --git a/src/core/SkDistanceFieldGen.cpp b/src/core/SkDistanceFieldGen.cpp
deleted file mode 100755
index fb7131e2b90e491bb4cc0a170d840013ae0b3463..0000000000000000000000000000000000000000
--- 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;
-}