| /* |
| * 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 |
| }; |
| |
| enum NeighborFlags { |
| kLeft_NeighborFlag = 0x01, |
| kRight_NeighborFlag = 0x02, |
| kTopLeft_NeighborFlag = 0x04, |
| kTop_NeighborFlag = 0x08, |
| kTopRight_NeighborFlag = 0x10, |
| kBottomLeft_NeighborFlag = 0x20, |
| kBottom_NeighborFlag = 0x40, |
| kBottomRight_NeighborFlag = 0x80, |
| kAll_NeighborFlags = 0xff, |
| |
| kNeighborFlagCount = 8 |
| }; |
| |
| // We treat an "edge" as a place where we cross from >=128 to <128, or vice versa, or |
| // where we have two non-zero pixels that are <128. |
| // 'neighborFlags' is used to limit the directions in which we test to avoid indexing |
| // outside of the image |
| static bool found_edge(const unsigned char* imagePtr, int width, int neighborFlags) { |
| // the order of these should match the neighbor flags above |
| const int kNum8ConnectedNeighbors = 8; |
| const int offsets[8] = {-1, 1, -width-1, -width, -width+1, width-1, width, width+1 }; |
| SkASSERT(kNum8ConnectedNeighbors == kNeighborFlagCount); |
| |
| // search for an edge |
| unsigned char currVal = *imagePtr; |
| unsigned char currCheck = (currVal >> 7); |
| for (int i = 0; i < kNum8ConnectedNeighbors; ++i) { |
| unsigned char neighborVal; |
| if ((1 << i) & neighborFlags) { |
| const unsigned char* checkPtr = imagePtr + offsets[i]; |
| neighborVal = *checkPtr; |
| } else { |
| neighborVal = 0; |
| } |
| unsigned char neighborCheck = (neighborVal >> 7); |
| SkASSERT(currCheck == 0 || currCheck == 1); |
| SkASSERT(neighborCheck == 0 || neighborCheck == 1); |
| // if sharp transition |
| if (currCheck != neighborCheck || |
| // or both <128 and >0 |
| (!currCheck && !neighborCheck && currVal && neighborVal)) { |
| return true; |
| } |
| } |
| |
| return false; |
| } |
| |
| static void init_glyph_data(DFData* data, unsigned 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 |
| } |
| int checkMask = kAll_NeighborFlags; |
| if (i == 0) { |
| checkMask &= ~(kLeft_NeighborFlag|kTopLeft_NeighborFlag|kBottomLeft_NeighborFlag); |
| } |
| if (i == imageWidth-1) { |
| checkMask &= ~(kRight_NeighborFlag|kTopRight_NeighborFlag|kBottomRight_NeighborFlag); |
| } |
| if (j == 0) { |
| checkMask &= ~(kTopLeft_NeighborFlag|kTop_NeighborFlag|kTopRight_NeighborFlag); |
| } |
| if (j == imageHeight-1) { |
| checkMask &= ~(kBottomLeft_NeighborFlag|kBottom_NeighborFlag|kBottomRight_NeighborFlag); |
| } |
| if (found_edge(image, imageWidth, checkMask)) { |
| *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, unsigned 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; |
| } |
| } |
| |
| // enable this to output edge data rather than the distance field |
| #define DUMP_EDGE 0 |
| |
| #if !DUMP_EDGE |
| 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); |
| } |
| } |
| #endif |
| |
| // assumes a padded 8-bit image and distance field |
| // width and height are the original width and height of the image |
| static bool generate_distance_field_from_image(unsigned char* distanceField, |
| const unsigned char* copyPtr, |
| int width, int height) { |
| SkASSERT(NULL != distanceField); |
| SkASSERT(NULL != copyPtr); |
| |
| // 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 = SK_DistanceFieldPad + 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)); |
| unsigned char* edgePtr = (unsigned char*) edgeStorage.get(); |
| sk_bzero(edgePtr, dataWidth*dataHeight*sizeof(char)); |
| |
| // copy glyph into distance field storage |
| init_glyph_data(dataPtr, edgePtr, copyPtr, |
| dataWidth, dataHeight, |
| width+2, height+2, SK_DistanceFieldPad); |
| |
| // 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 |
| unsigned 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) { |
| #if DUMP_EDGE |
| float alpha = currData->fAlpha; |
| float edge = 0.0f; |
| if (*currEdge) { |
| edge = 0.25f; |
| } |
| // blend with original image |
| float result = alpha + (1.0f-alpha)*edge; |
| unsigned char val = sk_float_round2int(255*result); |
| *dfPtr++ = val; |
| #else |
| float dist; |
| if (currData->fAlpha > 0.5f) { |
| dist = -SkScalarSqrt(currData->fDistSq); |
| } else { |
| dist = SkScalarSqrt(currData->fDistSq); |
| } |
| *dfPtr++ = pack_distance_field_val(dist, (float)SK_DistanceFieldMagnitude); |
| #endif |
| ++currData; |
| ++currEdge; |
| } |
| currData += 2; |
| currEdge += 2; |
| } |
| |
| return true; |
| } |
| |
| // assumes an 8-bit image and distance field |
| bool SkGenerateDistanceFieldFromA8Image(unsigned char* distanceField, |
| const unsigned char* image, |
| int width, int height, int rowBytes) { |
| SkASSERT(NULL != distanceField); |
| SkASSERT(NULL != image); |
| |
| // create temp data |
| SkAutoSMalloc<1024> copyStorage((width+2)*(height+2)*sizeof(char)); |
| unsigned char* copyPtr = (unsigned char*) copyStorage.get(); |
| |
| // we copy our source image into a padded copy to ensure we catch edge transitions |
| // around the outside |
| const unsigned char* currSrcScanLine = image; |
| sk_bzero(copyPtr, (width+2)*sizeof(char)); |
| unsigned char* currDestPtr = copyPtr + width + 2; |
| for (int i = 0; i < height; ++i) { |
| *currDestPtr++ = 0; |
| memcpy(currDestPtr, currSrcScanLine, rowBytes); |
| currSrcScanLine += rowBytes; |
| currDestPtr += width; |
| *currDestPtr++ = 0; |
| } |
| sk_bzero(currDestPtr, (width+2)*sizeof(char)); |
| |
| return generate_distance_field_from_image(distanceField, copyPtr, width, height); |
| } |
| |
| // assumes a 1-bit image and 8-bit distance field |
| bool SkGenerateDistanceFieldFromBWImage(unsigned char* distanceField, |
| const unsigned char* image, |
| int width, int height, int rowBytes) { |
| SkASSERT(NULL != distanceField); |
| SkASSERT(NULL != image); |
| |
| // create temp data |
| SkAutoSMalloc<1024> copyStorage((width+2)*(height+2)*sizeof(char)); |
| unsigned char* copyPtr = (unsigned char*) copyStorage.get(); |
| |
| // we copy our source image into a padded copy to ensure we catch edge transitions |
| // around the outside |
| const unsigned char* currSrcScanLine = image; |
| sk_bzero(copyPtr, (width+2)*sizeof(char)); |
| unsigned char* currDestPtr = copyPtr + width + 2; |
| for (int i = 0; i < height; ++i) { |
| *currDestPtr++ = 0; |
| int rowWritesLeft = width; |
| const unsigned char *maskPtr = currSrcScanLine; |
| while (rowWritesLeft > 0) { |
| unsigned mask = *maskPtr++; |
| for (int i = 7; i >= 0 && rowWritesLeft; --i, --rowWritesLeft) { |
| *currDestPtr++ = (mask & (1 << i)) ? 0xff : 0; |
| } |
| } |
| currSrcScanLine += rowBytes; |
| *currDestPtr++ = 0; |
| } |
| sk_bzero(currDestPtr, (width+2)*sizeof(char)); |
| |
| return generate_distance_field_from_image(distanceField, copyPtr, width, height); |
| } |
