diff options
-rw-r--r-- | gm/gmmain.cpp | 13 | ||||
-rw-r--r-- | gyp/core.gypi | 2 | ||||
-rwxr-xr-x | gyp/edtaa.gyp | 31 | ||||
-rw-r--r-- | gyp/gpu.gyp | 1 | ||||
-rwxr-xr-x | src/core/SkDistanceFieldGen.cpp | 401 | ||||
-rwxr-xr-x | src/core/SkDistanceFieldGen.h | 25 | ||||
-rw-r--r-- | src/gpu/GrTextStrike.cpp | 108 | ||||
-rwxr-xr-x | third_party/edtaa/LICENSE | 21 | ||||
-rwxr-xr-x | third_party/edtaa/edtaa3.h | 35 | ||||
-rwxr-xr-x | third_party/edtaa/edtaa3func.cpp | 586 |
10 files changed, 473 insertions, 750 deletions
diff --git a/gm/gmmain.cpp b/gm/gmmain.cpp index 165c5affb7..de9e1a15a0 100644 --- a/gm/gmmain.cpp +++ b/gm/gmmain.cpp @@ -46,6 +46,7 @@ #ifdef SK_DEBUG static const bool kDebugOnly = true; +#define GR_DUMP_FONT_CACHE 0 #else static const bool kDebugOnly = false; #endif @@ -2408,6 +2409,18 @@ 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 a1eed0a729..cdb0bab1d7 100644 --- a/gyp/core.gypi +++ b/gyp/core.gypi @@ -70,6 +70,8 @@ '<(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 deleted file mode 100755 index 4f7272e5b2..0000000000 --- a/gyp/edtaa.gyp +++ /dev/null @@ -1,31 +0,0 @@ -# -# 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 471004cbe4..f303eb50d8 100644 --- a/gyp/gpu.gyp +++ b/gyp/gpu.gyp @@ -83,7 +83,6 @@ 'standalone_static_library': 1, 'dependencies': [ 'core.gyp:*', - 'edtaa.gyp:*', 'utils.gyp:*', ], 'includes': [ diff --git a/src/core/SkDistanceFieldGen.cpp b/src/core/SkDistanceFieldGen.cpp new file mode 100755 index 0000000000..fb7131e2b9 --- /dev/null +++ b/src/core/SkDistanceFieldGen.cpp @@ -0,0 +1,401 @@ +/* + * 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 new file mode 100755 index 0000000000..3d2ec23b75 --- /dev/null +++ b/src/core/SkDistanceFieldGen.h @@ -0,0 +1,25 @@ +/* + * 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 e303a23df8..0d7fcafe67 100644 --- a/src/gpu/GrTextStrike.cpp +++ b/src/gpu/GrTextStrike.cpp @@ -13,7 +13,7 @@ #include "SkString.h" #if SK_DISTANCEFIELD_FONTS -#include "edtaa3.h" +#include "SkDistanceFieldGen.h" #endif /////////////////////////////////////////////////////////////////////////////// @@ -199,8 +199,9 @@ void GrFontCache::dump() const { #endif #if SK_DISTANCEFIELD_FONTS -#define DISTANCE_FIELD_PAD 4 -#define DISTANCE_FIELD_RANGE (4.0) +// 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 #endif /* @@ -253,10 +254,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_PAD; - bounds.fRight += DISTANCE_FIELD_PAD; - bounds.fTop -= DISTANCE_FIELD_PAD; - bounds.fBottom += DISTANCE_FIELD_PAD; + bounds.fLeft -= DISTANCE_FIELD_RANGE; + bounds.fRight += DISTANCE_FIELD_RANGE; + bounds.fTop -= DISTANCE_FIELD_RANGE; + bounds.fBottom += DISTANCE_FIELD_RANGE; } #endif glyph->init(packed, bounds); @@ -294,15 +295,13 @@ 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_PAD; - int height = dfHeight - 2*DISTANCE_FIELD_PAD; - size_t stride = width*bytesPerPixel; + int width = dfWidth - 2*DISTANCE_FIELD_RANGE; + int height = dfHeight - 2*DISTANCE_FIELD_RANGE; + int stride = width*bytesPerPixel; size_t size = width * height * bytesPerPixel; SkAutoSMalloc<1024> storage(size); @@ -313,71 +312,28 @@ bool GrTextStrike::addGlyphToAtlas(GrGlyph* glyph, GrFontScaler* scaler) { // alloc storage for distance field glyph size_t dfSize = dfWidth * dfHeight * bytesPerPixel; SkAutoSMalloc<1024> dfStorage(dfSize); - - // 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); + + 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; } - *dfPtr++ = val; } // copy to atlas diff --git a/third_party/edtaa/LICENSE b/third_party/edtaa/LICENSE deleted file mode 100755 index a55880508a..0000000000 --- a/third_party/edtaa/LICENSE +++ /dev/null @@ -1,21 +0,0 @@ -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 deleted file mode 100755 index 4e306777ee..0000000000 --- a/third_party/edtaa/edtaa3.h +++ /dev/null @@ -1,35 +0,0 @@ -/*
- 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 deleted file mode 100755 index beed19831e..0000000000 --- a/third_party/edtaa/edtaa3func.cpp +++ /dev/null @@ -1,586 +0,0 @@ -/*
- * 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
|