diff options
Diffstat (limited to 'src/core/SkDistanceFieldGen.cpp')
-rwxr-xr-x | src/core/SkDistanceFieldGen.cpp | 401 |
1 files changed, 0 insertions, 401 deletions
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; -} |