michael@0: /*
michael@0:  * Copyright 2014 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: #include "SkDistanceFieldGen.h"
michael@0: #include "SkPoint.h"
michael@0: 
michael@0: struct DFData {
michael@0:     float   fAlpha;      // alpha value of source texel
michael@0:     float   fDistSq;     // distance squared to nearest (so far) edge texel
michael@0:     SkPoint fDistVector; // distance vector to nearest (so far) edge texel
michael@0: };
michael@0: 
michael@0: enum NeighborFlags {
michael@0:     kLeft_NeighborFlag        = 0x01,
michael@0:     kRight_NeighborFlag       = 0x02,
michael@0:     kTopLeft_NeighborFlag     = 0x04,
michael@0:     kTop_NeighborFlag         = 0x08,
michael@0:     kTopRight_NeighborFlag    = 0x10,
michael@0:     kBottomLeft_NeighborFlag  = 0x20,
michael@0:     kBottom_NeighborFlag      = 0x40,
michael@0:     kBottomRight_NeighborFlag = 0x80,
michael@0:     kAll_NeighborFlags        = 0xff,
michael@0: 
michael@0:     kNeighborFlagCount        = 8
michael@0: };
michael@0: 
michael@0: // We treat an "edge" as a place where we cross from black to non-black, or vice versa.
michael@0: // 'neighborFlags' is used to limit the directions in which we test to avoid indexing
michael@0: // outside of the image
michael@0: static bool found_edge(const unsigned char* imagePtr, int width, int neighborFlags) {
michael@0:     // the order of these should match the neighbor flags above
michael@0:     const int kNum8ConnectedNeighbors = 8;
michael@0:     const int offsets[8] = {-1, 1, -width-1, -width, -width+1, width-1, width, width+1 };
michael@0:     SkASSERT(kNum8ConnectedNeighbors == kNeighborFlagCount);
michael@0: 
michael@0:     // search for an edge
michael@0:     bool currVal = (*imagePtr != 0);
michael@0:     for (int i = 0; i < kNum8ConnectedNeighbors; ++i) {
michael@0:         bool checkVal;
michael@0:         if ((1 << i) & neighborFlags) {
michael@0:             const unsigned char* checkPtr = imagePtr + offsets[i];
michael@0:             checkVal = (*checkPtr != 0);
michael@0:         } else {
michael@0:             checkVal = false;
michael@0:         }
michael@0:         SkASSERT(checkVal == 0 || checkVal == 1);
michael@0:         SkASSERT(currVal == 0 || currVal == 1);
michael@0:         if (checkVal != currVal) {
michael@0:             return true;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: static void init_glyph_data(DFData* data, unsigned char* edges, const unsigned char* image,
michael@0:                             int dataWidth, int dataHeight,
michael@0:                             int imageWidth, int imageHeight,
michael@0:                             int pad) {
michael@0:     data += pad*dataWidth;
michael@0:     data += pad;
michael@0:     edges += (pad*dataWidth + pad);
michael@0: 
michael@0:     for (int j = 0; j < imageHeight; ++j) {
michael@0:         for (int i = 0; i < imageWidth; ++i) {
michael@0:             if (255 == *image) {
michael@0:                 data->fAlpha = 1.0f;
michael@0:             } else {
michael@0:                 data->fAlpha = (*image)*0.00392156862f;  // 1/255
michael@0:             }
michael@0:             int checkMask = kAll_NeighborFlags;
michael@0:             if (i == 0) {
michael@0:                 checkMask &= ~(kLeft_NeighborFlag|kTopLeft_NeighborFlag|kBottomLeft_NeighborFlag);
michael@0:             }
michael@0:             if (i == imageWidth-1) {
michael@0:                 checkMask &= ~(kRight_NeighborFlag|kTopRight_NeighborFlag|kBottomRight_NeighborFlag);
michael@0:             }
michael@0:             if (j == 0) {
michael@0:                 checkMask &= ~(kTopLeft_NeighborFlag|kTop_NeighborFlag|kTopRight_NeighborFlag);
michael@0:             }
michael@0:             if (j == imageHeight-1) {
michael@0:                 checkMask &= ~(kBottomLeft_NeighborFlag|kBottom_NeighborFlag|kBottomRight_NeighborFlag);
michael@0:             }
michael@0:             if (found_edge(image, imageWidth, checkMask)) {
michael@0:                 *edges = 255;  // using 255 makes for convenient debug rendering
michael@0:             }
michael@0:             ++data;
michael@0:             ++image;
michael@0:             ++edges;
michael@0:         }
michael@0:         data += 2*pad;
michael@0:         edges += 2*pad;
michael@0:     }
michael@0: }
michael@0: 
michael@0: // from Gustavson (2011)
michael@0: // computes the distance to an edge given an edge normal vector and a pixel's alpha value
michael@0: // assumes that direction has been pre-normalized
michael@0: static float edge_distance(const SkPoint& direction, float alpha) {
michael@0:     float dx = direction.fX;
michael@0:     float dy = direction.fY;
michael@0:     float distance;
michael@0:     if (SkScalarNearlyZero(dx) || SkScalarNearlyZero(dy)) {
michael@0:         distance = 0.5f - alpha;
michael@0:     } else {
michael@0:         // this is easier if we treat the direction as being in the first octant
michael@0:         // (other octants are symmetrical)
michael@0:         dx = SkScalarAbs(dx);
michael@0:         dy = SkScalarAbs(dy);
michael@0:         if (dx < dy) {
michael@0:             SkTSwap(dx, dy);
michael@0:         }
michael@0: 
michael@0:         // a1 = 0.5*dy/dx is the smaller fractional area chopped off by the edge
michael@0:         // to avoid the divide, we just consider the numerator
michael@0:         float a1num = 0.5f*dy;
michael@0: 
michael@0:         // we now compute the approximate distance, depending where the alpha falls
michael@0:         // relative to the edge fractional area
michael@0: 
michael@0:         // if 0 <= alpha < a1
michael@0:         if (alpha*dx < a1num) {
michael@0:             // TODO: find a way to do this without square roots?
michael@0:             distance = 0.5f*(dx + dy) - SkScalarSqrt(2.0f*dx*dy*alpha);
michael@0:         // if a1 <= alpha <= 1 - a1
michael@0:         } else if (alpha*dx < (dx - a1num)) {
michael@0:             distance = (0.5f - alpha)*dx;
michael@0:         // if 1 - a1 < alpha <= 1
michael@0:         } else {
michael@0:             // TODO: find a way to do this without square roots?
michael@0:             distance = -0.5f*(dx + dy) + SkScalarSqrt(2.0f*dx*dy*(1.0f - alpha));
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return distance;
michael@0: }
michael@0: 
michael@0: static void init_distances(DFData* data, unsigned char* edges, int width, int height) {
michael@0:     // skip one pixel border
michael@0:     DFData* currData = data;
michael@0:     DFData* prevData = data - width;
michael@0:     DFData* nextData = data + width;
michael@0: 
michael@0:     for (int j = 0; j < height; ++j) {
michael@0:         for (int i = 0; i < width; ++i) {
michael@0:             if (*edges) {
michael@0:                 // we should not be in the one-pixel outside band
michael@0:                 SkASSERT(i > 0 && i < width-1 && j > 0 && j < height-1);
michael@0:                 // gradient will point from low to high
michael@0:                 // +y is down in this case
michael@0:                 // i.e., if you're outside, gradient points towards edge
michael@0:                 // if you're inside, gradient points away from edge
michael@0:                 SkPoint currGrad;
michael@0:                 currGrad.fX = (prevData+1)->fAlpha - (prevData-1)->fAlpha
michael@0:                              + SK_ScalarSqrt2*(currData+1)->fAlpha
michael@0:                              - SK_ScalarSqrt2*(currData-1)->fAlpha
michael@0:                              + (nextData+1)->fAlpha - (nextData-1)->fAlpha;
michael@0:                 currGrad.fY = (nextData-1)->fAlpha - (prevData-1)->fAlpha
michael@0:                              + SK_ScalarSqrt2*nextData->fAlpha
michael@0:                              - SK_ScalarSqrt2*prevData->fAlpha
michael@0:                              + (nextData+1)->fAlpha - (prevData+1)->fAlpha;
michael@0:                 currGrad.setLengthFast(1.0f);
michael@0: 
michael@0:                 // init squared distance to edge and distance vector
michael@0:                 float dist = edge_distance(currGrad, currData->fAlpha);
michael@0:                 currGrad.scale(dist, &currData->fDistVector);
michael@0:                 currData->fDistSq = dist*dist;
michael@0:             } else {
michael@0:                 // init distance to "far away"
michael@0:                 currData->fDistSq = 2000000.f;
michael@0:                 currData->fDistVector.fX = 1000.f;
michael@0:                 currData->fDistVector.fY = 1000.f;
michael@0:             }
michael@0:             ++currData;
michael@0:             ++prevData;
michael@0:             ++nextData;
michael@0:             ++edges;
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: // Danielsson's 8SSEDT
michael@0: 
michael@0: // first stage forward pass
michael@0: // (forward in Y, forward in X)
michael@0: static void F1(DFData* curr, int width) {
michael@0:     // upper left
michael@0:     DFData* check = curr - width-1;
michael@0:     SkPoint distVec = check->fDistVector;
michael@0:     float distSq = check->fDistSq - 2.0f*(distVec.fX + distVec.fY - 1.0f);
michael@0:     if (distSq < curr->fDistSq) {
michael@0:         distVec.fX -= 1.0f;
michael@0:         distVec.fY -= 1.0f;
michael@0:         curr->fDistSq = distSq;
michael@0:         curr->fDistVector = distVec;
michael@0:     }
michael@0: 
michael@0:     // up
michael@0:     check = curr - width;
michael@0:     distVec = check->fDistVector;
michael@0:     distSq = check->fDistSq - 2.0f*distVec.fY + 1.0f;
michael@0:     if (distSq < curr->fDistSq) {
michael@0:         distVec.fY -= 1.0f;
michael@0:         curr->fDistSq = distSq;
michael@0:         curr->fDistVector = distVec;
michael@0:     }
michael@0: 
michael@0:     // upper right
michael@0:     check = curr - width+1;
michael@0:     distVec = check->fDistVector;
michael@0:     distSq = check->fDistSq + 2.0f*(distVec.fX - distVec.fY + 1.0f);
michael@0:     if (distSq < curr->fDistSq) {
michael@0:         distVec.fX += 1.0f;
michael@0:         distVec.fY -= 1.0f;
michael@0:         curr->fDistSq = distSq;
michael@0:         curr->fDistVector = distVec;
michael@0:     }
michael@0: 
michael@0:     // left
michael@0:     check = curr - 1;
michael@0:     distVec = check->fDistVector;
michael@0:     distSq = check->fDistSq - 2.0f*distVec.fX + 1.0f;
michael@0:     if (distSq < curr->fDistSq) {
michael@0:         distVec.fX -= 1.0f;
michael@0:         curr->fDistSq = distSq;
michael@0:         curr->fDistVector = distVec;
michael@0:     }
michael@0: }
michael@0: 
michael@0: // second stage forward pass
michael@0: // (forward in Y, backward in X)
michael@0: static void F2(DFData* curr, int width) {
michael@0:     // right
michael@0:     DFData* check = curr + 1;
michael@0:     float distSq = check->fDistSq;
michael@0:     SkPoint distVec = check->fDistVector;
michael@0:     distSq = check->fDistSq + 2.0f*distVec.fX + 1.0f;
michael@0:     if (distSq < curr->fDistSq) {
michael@0:         distVec.fX += 1.0f;
michael@0:         curr->fDistSq = distSq;
michael@0:         curr->fDistVector = distVec;
michael@0:     }
michael@0: }
michael@0: 
michael@0: // first stage backward pass
michael@0: // (backward in Y, forward in X)
michael@0: static void B1(DFData* curr, int width) {
michael@0:     // left
michael@0:     DFData* check = curr - 1;
michael@0:     SkPoint distVec = check->fDistVector;
michael@0:     float distSq = check->fDistSq - 2.0f*distVec.fX + 1.0f;
michael@0:     if (distSq < curr->fDistSq) {
michael@0:         distVec.fX -= 1.0f;
michael@0:         curr->fDistSq = distSq;
michael@0:         curr->fDistVector = distVec;
michael@0:     }
michael@0: }
michael@0: 
michael@0: // second stage backward pass
michael@0: // (backward in Y, backwards in X)
michael@0: static void B2(DFData* curr, int width) {
michael@0:     // right
michael@0:     DFData* check = curr + 1;
michael@0:     SkPoint distVec = check->fDistVector;
michael@0:     float distSq = check->fDistSq + 2.0f*distVec.fX + 1.0f;
michael@0:     if (distSq < curr->fDistSq) {
michael@0:         distVec.fX += 1.0f;
michael@0:         curr->fDistSq = distSq;
michael@0:         curr->fDistVector = distVec;
michael@0:     }
michael@0: 
michael@0:     // bottom left
michael@0:     check = curr + width-1;
michael@0:     distVec = check->fDistVector;
michael@0:     distSq = check->fDistSq - 2.0f*(distVec.fX - distVec.fY - 1.0f);
michael@0:     if (distSq < curr->fDistSq) {
michael@0:         distVec.fX -= 1.0f;
michael@0:         distVec.fY += 1.0f;
michael@0:         curr->fDistSq = distSq;
michael@0:         curr->fDistVector = distVec;
michael@0:     }
michael@0: 
michael@0:     // bottom
michael@0:     check = curr + width;
michael@0:     distVec = check->fDistVector;
michael@0:     distSq = check->fDistSq + 2.0f*distVec.fY + 1.0f;
michael@0:     if (distSq < curr->fDistSq) {
michael@0:         distVec.fY += 1.0f;
michael@0:         curr->fDistSq = distSq;
michael@0:         curr->fDistVector = distVec;
michael@0:     }
michael@0: 
michael@0:     // bottom right
michael@0:     check = curr + width+1;
michael@0:     distVec = check->fDistVector;
michael@0:     distSq = check->fDistSq + 2.0f*(distVec.fX + distVec.fY + 1.0f);
michael@0:     if (distSq < curr->fDistSq) {
michael@0:         distVec.fX += 1.0f;
michael@0:         distVec.fY += 1.0f;
michael@0:         curr->fDistSq = distSq;
michael@0:         curr->fDistVector = distVec;
michael@0:     }
michael@0: }
michael@0: 
michael@0: // enable this to output edge data rather than the distance field
michael@0: #define DUMP_EDGE 0
michael@0: 
michael@0: #if !DUMP_EDGE
michael@0: static unsigned char pack_distance_field_val(float dist, float distanceMagnitude) {
michael@0:     if (dist <= -distanceMagnitude) {
michael@0:         return 255;
michael@0:     } else if (dist > distanceMagnitude) {
michael@0:         return 0;
michael@0:     } else {
michael@0:         return (unsigned char)((distanceMagnitude-dist)*128.0f/distanceMagnitude);
michael@0:     }
michael@0: }
michael@0: #endif
michael@0: 
michael@0: // assumes an 8-bit image and distance field
michael@0: bool SkGenerateDistanceFieldFromImage(unsigned char* distanceField,
michael@0:                                       const unsigned char* image,
michael@0:                                       int width, int height,
michael@0:                                       int distanceMagnitude) {
michael@0:     SkASSERT(NULL != distanceField);
michael@0:     SkASSERT(NULL != image);
michael@0: 
michael@0:     // the final distance field will have additional texels on each side to handle
michael@0:     // the maximum distance
michael@0:     // we expand our temp data by one more on each side to simplify
michael@0:     // the scanning code -- will always be treated as infinitely far away
michael@0:     int pad = distanceMagnitude+1;
michael@0: 
michael@0:     // set params for distance field data
michael@0:     int dataWidth = width + 2*pad;
michael@0:     int dataHeight = height + 2*pad;
michael@0: 
michael@0:     // create temp data
michael@0:     size_t dataSize = dataWidth*dataHeight*sizeof(DFData);
michael@0:     SkAutoSMalloc<1024> dfStorage(dataSize);
michael@0:     DFData* dataPtr = (DFData*) dfStorage.get();
michael@0:     sk_bzero(dataPtr, dataSize);
michael@0: 
michael@0:     SkAutoSMalloc<1024> edgeStorage(dataWidth*dataHeight*sizeof(char));
michael@0:     unsigned char* edgePtr = (unsigned char*) edgeStorage.get();
michael@0:     sk_bzero(edgePtr, dataWidth*dataHeight*sizeof(char));
michael@0: 
michael@0:     // copy glyph into distance field storage
michael@0:     init_glyph_data(dataPtr, edgePtr, image,
michael@0:                     dataWidth, dataHeight,
michael@0:                     width, height, pad);
michael@0: 
michael@0:     // create initial distance data, particularly at edges
michael@0:     init_distances(dataPtr, edgePtr, dataWidth, dataHeight);
michael@0: 
michael@0:     // now perform Euclidean distance transform to propagate distances
michael@0: 
michael@0:     // forwards in y
michael@0:     DFData* currData = dataPtr+dataWidth+1; // skip outer buffer
michael@0:     unsigned char* currEdge = edgePtr+dataWidth+1;
michael@0:     for (int j = 1; j < dataHeight-1; ++j) {
michael@0:         // forwards in x
michael@0:         for (int i = 1; i < dataWidth-1; ++i) {
michael@0:             // don't need to calculate distance for edge pixels
michael@0:             if (!*currEdge) {
michael@0:                 F1(currData, dataWidth);
michael@0:             }
michael@0:             ++currData;
michael@0:             ++currEdge;
michael@0:         }
michael@0: 
michael@0:         // backwards in x
michael@0:         --currData; // reset to end
michael@0:         --currEdge;
michael@0:         for (int i = 1; i < dataWidth-1; ++i) {
michael@0:             // don't need to calculate distance for edge pixels
michael@0:             if (!*currEdge) {
michael@0:                 F2(currData, dataWidth);
michael@0:             }
michael@0:             --currData;
michael@0:             --currEdge;
michael@0:         }
michael@0: 
michael@0:         currData += dataWidth+1;
michael@0:         currEdge += dataWidth+1;
michael@0:     }
michael@0: 
michael@0:     // backwards in y
michael@0:     currData = dataPtr+dataWidth*(dataHeight-2) - 1; // skip outer buffer
michael@0:     currEdge = edgePtr+dataWidth*(dataHeight-2) - 1;
michael@0:     for (int j = 1; j < dataHeight-1; ++j) {
michael@0:         // forwards in x
michael@0:         for (int i = 1; i < dataWidth-1; ++i) {
michael@0:             // don't need to calculate distance for edge pixels
michael@0:             if (!*currEdge) {
michael@0:                 B1(currData, dataWidth);
michael@0:             }
michael@0:             ++currData;
michael@0:             ++currEdge;
michael@0:         }
michael@0: 
michael@0:         // backwards in x
michael@0:         --currData; // reset to end
michael@0:         --currEdge;
michael@0:         for (int i = 1; i < dataWidth-1; ++i) {
michael@0:             // don't need to calculate distance for edge pixels
michael@0:             if (!*currEdge) {
michael@0:                 B2(currData, dataWidth);
michael@0:             }
michael@0:             --currData;
michael@0:             --currEdge;
michael@0:         }
michael@0: 
michael@0:         currData -= dataWidth-1;
michael@0:         currEdge -= dataWidth-1;
michael@0:     }
michael@0: 
michael@0:     // copy results to final distance field data
michael@0:     currData = dataPtr + dataWidth+1;
michael@0:     currEdge = edgePtr + dataWidth+1;
michael@0:     unsigned char *dfPtr = distanceField;
michael@0:     for (int j = 1; j < dataHeight-1; ++j) {
michael@0:         for (int i = 1; i < dataWidth-1; ++i) {
michael@0: #if DUMP_EDGE
michael@0:             unsigned char val = sk_float_round2int(255*currData->fAlpha);
michael@0:             if (*currEdge) {
michael@0:                 val = 128;
michael@0:             }
michael@0:             *dfPtr++ = val;
michael@0: #else
michael@0:             float dist;
michael@0:             if (currData->fAlpha > 0.5f) {
michael@0:                 dist = -SkScalarSqrt(currData->fDistSq);
michael@0:             } else {
michael@0:                 dist = SkScalarSqrt(currData->fDistSq);
michael@0:             }
michael@0:             *dfPtr++ = pack_distance_field_val(dist, (float)distanceMagnitude);
michael@0: #endif
michael@0:             ++currData;
michael@0:             ++currEdge;
michael@0:         }
michael@0:         currData += 2;
michael@0:         currEdge += 2;
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }