From b5f3b35645ce5335021ecb8c34b486a3db9554eb Mon Sep 17 00:00:00 2001 From: "commit-bot@chromium.org" Date: Mon, 10 Mar 2014 20:37:54 +0000 Subject: [PATCH] Revert of Add new module for distance field generation. (https://codereview.chromium.org/178543007/) Reason for revert: multiple compile errors Original issue's description: > Add new module for distance field generation. > > This improves the speed over the previous method by 10x+, and makes using distance fields practical. > > BUG=skia:2173 > > Committed: http://code.google.com/p/skia/source/detail?r=13729 R=bsalomon@google.com, robertphillips@google.com, jvanverth@google.com TBR=bsalomon@google.com, jvanverth@google.com, robertphillips@google.com NOTREECHECKS=true NOTRY=true BUG=skia:2173 Author: halcanary@google.com Review URL: https://codereview.chromium.org/190753015 git-svn-id: http://skia.googlecode.com/svn/trunk@13732 2bbb7eff-a529-9590-31e7-b0007b416f81 --- gm/gmmain.cpp | 13 - gyp/core.gypi | 2 - gyp/edtaa.gyp | 31 ++ gyp/gpu.gyp | 1 + src/core/SkDistanceFieldGen.cpp | 401 --------------------- src/core/SkDistanceFieldGen.h | 25 -- src/gpu/GrTextStrike.cpp | 108 ++++-- third_party/edtaa/LICENSE | 21 ++ third_party/edtaa/edtaa3.h | 35 ++ third_party/edtaa/edtaa3func.cpp | 586 +++++++++++++++++++++++++++++++ 10 files changed, 750 insertions(+), 473 deletions(-) create mode 100755 gyp/edtaa.gyp delete mode 100755 src/core/SkDistanceFieldGen.cpp delete mode 100755 src/core/SkDistanceFieldGen.h create mode 100755 third_party/edtaa/LICENSE create mode 100755 third_party/edtaa/edtaa3.h create mode 100755 third_party/edtaa/edtaa3func.cpp diff --git a/gm/gmmain.cpp b/gm/gmmain.cpp index de9e1a15a0..165c5affb7 100644 --- a/gm/gmmain.cpp +++ b/gm/gmmain.cpp @@ -46,7 +46,6 @@ #ifdef SK_DEBUG static const bool kDebugOnly = true; -#define GR_DUMP_FONT_CACHE 0 #else static const bool kDebugOnly = false; #endif @@ -2409,18 +2408,6 @@ 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 cdb0bab1d7..a1eed0a729 100644 --- a/gyp/core.gypi +++ b/gyp/core.gypi @@ -70,8 +70,6 @@ '<(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 new file mode 100755 index 0000000000..4f7272e5b2 --- /dev/null +++ b/gyp/edtaa.gyp @@ -0,0 +1,31 @@ +# +# 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 f303eb50d8..471004cbe4 100644 --- a/gyp/gpu.gyp +++ b/gyp/gpu.gyp @@ -83,6 +83,7 @@ 'standalone_static_library': 1, 'dependencies': [ 'core.gyp:*', + 'edtaa.gyp:*', 'utils.gyp:*', ], 'includes': [ 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; -} diff --git a/src/core/SkDistanceFieldGen.h b/src/core/SkDistanceFieldGen.h deleted file mode 100755 index 3d2ec23b75..0000000000 --- a/src/core/SkDistanceFieldGen.h +++ /dev/null @@ -1,25 +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. - */ -#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 0d7fcafe67..e303a23df8 100644 --- a/src/gpu/GrTextStrike.cpp +++ b/src/gpu/GrTextStrike.cpp @@ -13,7 +13,7 @@ #include "SkString.h" #if SK_DISTANCEFIELD_FONTS -#include "SkDistanceFieldGen.h" +#include "edtaa3.h" #endif /////////////////////////////////////////////////////////////////////////////// @@ -199,9 +199,8 @@ void GrFontCache::dump() const { #endif #if SK_DISTANCEFIELD_FONTS -// 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 +#define DISTANCE_FIELD_PAD 4 +#define DISTANCE_FIELD_RANGE (4.0) #endif /* @@ -254,10 +253,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_RANGE; - bounds.fRight += DISTANCE_FIELD_RANGE; - bounds.fTop -= DISTANCE_FIELD_RANGE; - bounds.fBottom += DISTANCE_FIELD_RANGE; + bounds.fLeft -= DISTANCE_FIELD_PAD; + bounds.fRight += DISTANCE_FIELD_PAD; + bounds.fTop -= DISTANCE_FIELD_PAD; + bounds.fBottom += DISTANCE_FIELD_PAD; } #endif glyph->init(packed, bounds); @@ -295,13 +294,15 @@ 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_RANGE; - int height = dfHeight - 2*DISTANCE_FIELD_RANGE; - int stride = width*bytesPerPixel; + int width = dfWidth - 2*DISTANCE_FIELD_PAD; + int height = dfHeight - 2*DISTANCE_FIELD_PAD; + size_t stride = width*bytesPerPixel; size_t size = width * height * bytesPerPixel; SkAutoSMalloc<1024> storage(size); @@ -312,28 +313,71 @@ bool GrTextStrike::addGlyphToAtlas(GrGlyph* glyph, GrFontScaler* scaler) { // alloc storage for distance field glyph size_t dfSize = dfWidth * dfHeight * bytesPerPixel; SkAutoSMalloc<1024> dfStorage(dfSize); - - 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; + + // 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); } + *dfPtr++ = val; } // copy to atlas diff --git a/third_party/edtaa/LICENSE b/third_party/edtaa/LICENSE new file mode 100755 index 0000000000..a5aa0d4c41 --- /dev/null +++ b/third_party/edtaa/LICENSE @@ -0,0 +1,21 @@ +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 new file mode 100755 index 0000000000..9db3c6e67b --- /dev/null +++ b/third_party/edtaa/edtaa3.h @@ -0,0 +1,35 @@ +/* + 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 new file mode 100755 index 0000000000..a09428ae52 --- /dev/null +++ b/third_party/edtaa/edtaa3func.cpp @@ -0,0 +1,586 @@ +/* + * 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 + +#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 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 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 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