1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkDistanceFieldGen.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,451 @@
1.4 +/*
1.5 + * Copyright 2014 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +
1.11 +#include "SkDistanceFieldGen.h"
1.12 +#include "SkPoint.h"
1.13 +
1.14 +struct DFData {
1.15 + float fAlpha; // alpha value of source texel
1.16 + float fDistSq; // distance squared to nearest (so far) edge texel
1.17 + SkPoint fDistVector; // distance vector to nearest (so far) edge texel
1.18 +};
1.19 +
1.20 +enum NeighborFlags {
1.21 + kLeft_NeighborFlag = 0x01,
1.22 + kRight_NeighborFlag = 0x02,
1.23 + kTopLeft_NeighborFlag = 0x04,
1.24 + kTop_NeighborFlag = 0x08,
1.25 + kTopRight_NeighborFlag = 0x10,
1.26 + kBottomLeft_NeighborFlag = 0x20,
1.27 + kBottom_NeighborFlag = 0x40,
1.28 + kBottomRight_NeighborFlag = 0x80,
1.29 + kAll_NeighborFlags = 0xff,
1.30 +
1.31 + kNeighborFlagCount = 8
1.32 +};
1.33 +
1.34 +// We treat an "edge" as a place where we cross from black to non-black, or vice versa.
1.35 +// 'neighborFlags' is used to limit the directions in which we test to avoid indexing
1.36 +// outside of the image
1.37 +static bool found_edge(const unsigned char* imagePtr, int width, int neighborFlags) {
1.38 + // the order of these should match the neighbor flags above
1.39 + const int kNum8ConnectedNeighbors = 8;
1.40 + const int offsets[8] = {-1, 1, -width-1, -width, -width+1, width-1, width, width+1 };
1.41 + SkASSERT(kNum8ConnectedNeighbors == kNeighborFlagCount);
1.42 +
1.43 + // search for an edge
1.44 + bool currVal = (*imagePtr != 0);
1.45 + for (int i = 0; i < kNum8ConnectedNeighbors; ++i) {
1.46 + bool checkVal;
1.47 + if ((1 << i) & neighborFlags) {
1.48 + const unsigned char* checkPtr = imagePtr + offsets[i];
1.49 + checkVal = (*checkPtr != 0);
1.50 + } else {
1.51 + checkVal = false;
1.52 + }
1.53 + SkASSERT(checkVal == 0 || checkVal == 1);
1.54 + SkASSERT(currVal == 0 || currVal == 1);
1.55 + if (checkVal != currVal) {
1.56 + return true;
1.57 + }
1.58 + }
1.59 +
1.60 + return false;
1.61 +}
1.62 +
1.63 +static void init_glyph_data(DFData* data, unsigned char* edges, const unsigned char* image,
1.64 + int dataWidth, int dataHeight,
1.65 + int imageWidth, int imageHeight,
1.66 + int pad) {
1.67 + data += pad*dataWidth;
1.68 + data += pad;
1.69 + edges += (pad*dataWidth + pad);
1.70 +
1.71 + for (int j = 0; j < imageHeight; ++j) {
1.72 + for (int i = 0; i < imageWidth; ++i) {
1.73 + if (255 == *image) {
1.74 + data->fAlpha = 1.0f;
1.75 + } else {
1.76 + data->fAlpha = (*image)*0.00392156862f; // 1/255
1.77 + }
1.78 + int checkMask = kAll_NeighborFlags;
1.79 + if (i == 0) {
1.80 + checkMask &= ~(kLeft_NeighborFlag|kTopLeft_NeighborFlag|kBottomLeft_NeighborFlag);
1.81 + }
1.82 + if (i == imageWidth-1) {
1.83 + checkMask &= ~(kRight_NeighborFlag|kTopRight_NeighborFlag|kBottomRight_NeighborFlag);
1.84 + }
1.85 + if (j == 0) {
1.86 + checkMask &= ~(kTopLeft_NeighborFlag|kTop_NeighborFlag|kTopRight_NeighborFlag);
1.87 + }
1.88 + if (j == imageHeight-1) {
1.89 + checkMask &= ~(kBottomLeft_NeighborFlag|kBottom_NeighborFlag|kBottomRight_NeighborFlag);
1.90 + }
1.91 + if (found_edge(image, imageWidth, checkMask)) {
1.92 + *edges = 255; // using 255 makes for convenient debug rendering
1.93 + }
1.94 + ++data;
1.95 + ++image;
1.96 + ++edges;
1.97 + }
1.98 + data += 2*pad;
1.99 + edges += 2*pad;
1.100 + }
1.101 +}
1.102 +
1.103 +// from Gustavson (2011)
1.104 +// computes the distance to an edge given an edge normal vector and a pixel's alpha value
1.105 +// assumes that direction has been pre-normalized
1.106 +static float edge_distance(const SkPoint& direction, float alpha) {
1.107 + float dx = direction.fX;
1.108 + float dy = direction.fY;
1.109 + float distance;
1.110 + if (SkScalarNearlyZero(dx) || SkScalarNearlyZero(dy)) {
1.111 + distance = 0.5f - alpha;
1.112 + } else {
1.113 + // this is easier if we treat the direction as being in the first octant
1.114 + // (other octants are symmetrical)
1.115 + dx = SkScalarAbs(dx);
1.116 + dy = SkScalarAbs(dy);
1.117 + if (dx < dy) {
1.118 + SkTSwap(dx, dy);
1.119 + }
1.120 +
1.121 + // a1 = 0.5*dy/dx is the smaller fractional area chopped off by the edge
1.122 + // to avoid the divide, we just consider the numerator
1.123 + float a1num = 0.5f*dy;
1.124 +
1.125 + // we now compute the approximate distance, depending where the alpha falls
1.126 + // relative to the edge fractional area
1.127 +
1.128 + // if 0 <= alpha < a1
1.129 + if (alpha*dx < a1num) {
1.130 + // TODO: find a way to do this without square roots?
1.131 + distance = 0.5f*(dx + dy) - SkScalarSqrt(2.0f*dx*dy*alpha);
1.132 + // if a1 <= alpha <= 1 - a1
1.133 + } else if (alpha*dx < (dx - a1num)) {
1.134 + distance = (0.5f - alpha)*dx;
1.135 + // if 1 - a1 < alpha <= 1
1.136 + } else {
1.137 + // TODO: find a way to do this without square roots?
1.138 + distance = -0.5f*(dx + dy) + SkScalarSqrt(2.0f*dx*dy*(1.0f - alpha));
1.139 + }
1.140 + }
1.141 +
1.142 + return distance;
1.143 +}
1.144 +
1.145 +static void init_distances(DFData* data, unsigned char* edges, int width, int height) {
1.146 + // skip one pixel border
1.147 + DFData* currData = data;
1.148 + DFData* prevData = data - width;
1.149 + DFData* nextData = data + width;
1.150 +
1.151 + for (int j = 0; j < height; ++j) {
1.152 + for (int i = 0; i < width; ++i) {
1.153 + if (*edges) {
1.154 + // we should not be in the one-pixel outside band
1.155 + SkASSERT(i > 0 && i < width-1 && j > 0 && j < height-1);
1.156 + // gradient will point from low to high
1.157 + // +y is down in this case
1.158 + // i.e., if you're outside, gradient points towards edge
1.159 + // if you're inside, gradient points away from edge
1.160 + SkPoint currGrad;
1.161 + currGrad.fX = (prevData+1)->fAlpha - (prevData-1)->fAlpha
1.162 + + SK_ScalarSqrt2*(currData+1)->fAlpha
1.163 + - SK_ScalarSqrt2*(currData-1)->fAlpha
1.164 + + (nextData+1)->fAlpha - (nextData-1)->fAlpha;
1.165 + currGrad.fY = (nextData-1)->fAlpha - (prevData-1)->fAlpha
1.166 + + SK_ScalarSqrt2*nextData->fAlpha
1.167 + - SK_ScalarSqrt2*prevData->fAlpha
1.168 + + (nextData+1)->fAlpha - (prevData+1)->fAlpha;
1.169 + currGrad.setLengthFast(1.0f);
1.170 +
1.171 + // init squared distance to edge and distance vector
1.172 + float dist = edge_distance(currGrad, currData->fAlpha);
1.173 + currGrad.scale(dist, &currData->fDistVector);
1.174 + currData->fDistSq = dist*dist;
1.175 + } else {
1.176 + // init distance to "far away"
1.177 + currData->fDistSq = 2000000.f;
1.178 + currData->fDistVector.fX = 1000.f;
1.179 + currData->fDistVector.fY = 1000.f;
1.180 + }
1.181 + ++currData;
1.182 + ++prevData;
1.183 + ++nextData;
1.184 + ++edges;
1.185 + }
1.186 + }
1.187 +}
1.188 +
1.189 +// Danielsson's 8SSEDT
1.190 +
1.191 +// first stage forward pass
1.192 +// (forward in Y, forward in X)
1.193 +static void F1(DFData* curr, int width) {
1.194 + // upper left
1.195 + DFData* check = curr - width-1;
1.196 + SkPoint distVec = check->fDistVector;
1.197 + float distSq = check->fDistSq - 2.0f*(distVec.fX + distVec.fY - 1.0f);
1.198 + if (distSq < curr->fDistSq) {
1.199 + distVec.fX -= 1.0f;
1.200 + distVec.fY -= 1.0f;
1.201 + curr->fDistSq = distSq;
1.202 + curr->fDistVector = distVec;
1.203 + }
1.204 +
1.205 + // up
1.206 + check = curr - width;
1.207 + distVec = check->fDistVector;
1.208 + distSq = check->fDistSq - 2.0f*distVec.fY + 1.0f;
1.209 + if (distSq < curr->fDistSq) {
1.210 + distVec.fY -= 1.0f;
1.211 + curr->fDistSq = distSq;
1.212 + curr->fDistVector = distVec;
1.213 + }
1.214 +
1.215 + // upper right
1.216 + check = curr - width+1;
1.217 + distVec = check->fDistVector;
1.218 + distSq = check->fDistSq + 2.0f*(distVec.fX - distVec.fY + 1.0f);
1.219 + if (distSq < curr->fDistSq) {
1.220 + distVec.fX += 1.0f;
1.221 + distVec.fY -= 1.0f;
1.222 + curr->fDistSq = distSq;
1.223 + curr->fDistVector = distVec;
1.224 + }
1.225 +
1.226 + // left
1.227 + check = curr - 1;
1.228 + distVec = check->fDistVector;
1.229 + distSq = check->fDistSq - 2.0f*distVec.fX + 1.0f;
1.230 + if (distSq < curr->fDistSq) {
1.231 + distVec.fX -= 1.0f;
1.232 + curr->fDistSq = distSq;
1.233 + curr->fDistVector = distVec;
1.234 + }
1.235 +}
1.236 +
1.237 +// second stage forward pass
1.238 +// (forward in Y, backward in X)
1.239 +static void F2(DFData* curr, int width) {
1.240 + // right
1.241 + DFData* check = curr + 1;
1.242 + float distSq = check->fDistSq;
1.243 + SkPoint distVec = check->fDistVector;
1.244 + distSq = check->fDistSq + 2.0f*distVec.fX + 1.0f;
1.245 + if (distSq < curr->fDistSq) {
1.246 + distVec.fX += 1.0f;
1.247 + curr->fDistSq = distSq;
1.248 + curr->fDistVector = distVec;
1.249 + }
1.250 +}
1.251 +
1.252 +// first stage backward pass
1.253 +// (backward in Y, forward in X)
1.254 +static void B1(DFData* curr, int width) {
1.255 + // left
1.256 + DFData* check = curr - 1;
1.257 + SkPoint distVec = check->fDistVector;
1.258 + float distSq = check->fDistSq - 2.0f*distVec.fX + 1.0f;
1.259 + if (distSq < curr->fDistSq) {
1.260 + distVec.fX -= 1.0f;
1.261 + curr->fDistSq = distSq;
1.262 + curr->fDistVector = distVec;
1.263 + }
1.264 +}
1.265 +
1.266 +// second stage backward pass
1.267 +// (backward in Y, backwards in X)
1.268 +static void B2(DFData* curr, int width) {
1.269 + // right
1.270 + DFData* check = curr + 1;
1.271 + SkPoint distVec = check->fDistVector;
1.272 + float distSq = check->fDistSq + 2.0f*distVec.fX + 1.0f;
1.273 + if (distSq < curr->fDistSq) {
1.274 + distVec.fX += 1.0f;
1.275 + curr->fDistSq = distSq;
1.276 + curr->fDistVector = distVec;
1.277 + }
1.278 +
1.279 + // bottom left
1.280 + check = curr + width-1;
1.281 + distVec = check->fDistVector;
1.282 + distSq = check->fDistSq - 2.0f*(distVec.fX - distVec.fY - 1.0f);
1.283 + if (distSq < curr->fDistSq) {
1.284 + distVec.fX -= 1.0f;
1.285 + distVec.fY += 1.0f;
1.286 + curr->fDistSq = distSq;
1.287 + curr->fDistVector = distVec;
1.288 + }
1.289 +
1.290 + // bottom
1.291 + check = curr + width;
1.292 + distVec = check->fDistVector;
1.293 + distSq = check->fDistSq + 2.0f*distVec.fY + 1.0f;
1.294 + if (distSq < curr->fDistSq) {
1.295 + distVec.fY += 1.0f;
1.296 + curr->fDistSq = distSq;
1.297 + curr->fDistVector = distVec;
1.298 + }
1.299 +
1.300 + // bottom right
1.301 + check = curr + width+1;
1.302 + distVec = check->fDistVector;
1.303 + distSq = check->fDistSq + 2.0f*(distVec.fX + distVec.fY + 1.0f);
1.304 + if (distSq < curr->fDistSq) {
1.305 + distVec.fX += 1.0f;
1.306 + distVec.fY += 1.0f;
1.307 + curr->fDistSq = distSq;
1.308 + curr->fDistVector = distVec;
1.309 + }
1.310 +}
1.311 +
1.312 +// enable this to output edge data rather than the distance field
1.313 +#define DUMP_EDGE 0
1.314 +
1.315 +#if !DUMP_EDGE
1.316 +static unsigned char pack_distance_field_val(float dist, float distanceMagnitude) {
1.317 + if (dist <= -distanceMagnitude) {
1.318 + return 255;
1.319 + } else if (dist > distanceMagnitude) {
1.320 + return 0;
1.321 + } else {
1.322 + return (unsigned char)((distanceMagnitude-dist)*128.0f/distanceMagnitude);
1.323 + }
1.324 +}
1.325 +#endif
1.326 +
1.327 +// assumes an 8-bit image and distance field
1.328 +bool SkGenerateDistanceFieldFromImage(unsigned char* distanceField,
1.329 + const unsigned char* image,
1.330 + int width, int height,
1.331 + int distanceMagnitude) {
1.332 + SkASSERT(NULL != distanceField);
1.333 + SkASSERT(NULL != image);
1.334 +
1.335 + // the final distance field will have additional texels on each side to handle
1.336 + // the maximum distance
1.337 + // we expand our temp data by one more on each side to simplify
1.338 + // the scanning code -- will always be treated as infinitely far away
1.339 + int pad = distanceMagnitude+1;
1.340 +
1.341 + // set params for distance field data
1.342 + int dataWidth = width + 2*pad;
1.343 + int dataHeight = height + 2*pad;
1.344 +
1.345 + // create temp data
1.346 + size_t dataSize = dataWidth*dataHeight*sizeof(DFData);
1.347 + SkAutoSMalloc<1024> dfStorage(dataSize);
1.348 + DFData* dataPtr = (DFData*) dfStorage.get();
1.349 + sk_bzero(dataPtr, dataSize);
1.350 +
1.351 + SkAutoSMalloc<1024> edgeStorage(dataWidth*dataHeight*sizeof(char));
1.352 + unsigned char* edgePtr = (unsigned char*) edgeStorage.get();
1.353 + sk_bzero(edgePtr, dataWidth*dataHeight*sizeof(char));
1.354 +
1.355 + // copy glyph into distance field storage
1.356 + init_glyph_data(dataPtr, edgePtr, image,
1.357 + dataWidth, dataHeight,
1.358 + width, height, pad);
1.359 +
1.360 + // create initial distance data, particularly at edges
1.361 + init_distances(dataPtr, edgePtr, dataWidth, dataHeight);
1.362 +
1.363 + // now perform Euclidean distance transform to propagate distances
1.364 +
1.365 + // forwards in y
1.366 + DFData* currData = dataPtr+dataWidth+1; // skip outer buffer
1.367 + unsigned char* currEdge = edgePtr+dataWidth+1;
1.368 + for (int j = 1; j < dataHeight-1; ++j) {
1.369 + // forwards in x
1.370 + for (int i = 1; i < dataWidth-1; ++i) {
1.371 + // don't need to calculate distance for edge pixels
1.372 + if (!*currEdge) {
1.373 + F1(currData, dataWidth);
1.374 + }
1.375 + ++currData;
1.376 + ++currEdge;
1.377 + }
1.378 +
1.379 + // backwards in x
1.380 + --currData; // reset to end
1.381 + --currEdge;
1.382 + for (int i = 1; i < dataWidth-1; ++i) {
1.383 + // don't need to calculate distance for edge pixels
1.384 + if (!*currEdge) {
1.385 + F2(currData, dataWidth);
1.386 + }
1.387 + --currData;
1.388 + --currEdge;
1.389 + }
1.390 +
1.391 + currData += dataWidth+1;
1.392 + currEdge += dataWidth+1;
1.393 + }
1.394 +
1.395 + // backwards in y
1.396 + currData = dataPtr+dataWidth*(dataHeight-2) - 1; // skip outer buffer
1.397 + currEdge = edgePtr+dataWidth*(dataHeight-2) - 1;
1.398 + for (int j = 1; j < dataHeight-1; ++j) {
1.399 + // forwards in x
1.400 + for (int i = 1; i < dataWidth-1; ++i) {
1.401 + // don't need to calculate distance for edge pixels
1.402 + if (!*currEdge) {
1.403 + B1(currData, dataWidth);
1.404 + }
1.405 + ++currData;
1.406 + ++currEdge;
1.407 + }
1.408 +
1.409 + // backwards in x
1.410 + --currData; // reset to end
1.411 + --currEdge;
1.412 + for (int i = 1; i < dataWidth-1; ++i) {
1.413 + // don't need to calculate distance for edge pixels
1.414 + if (!*currEdge) {
1.415 + B2(currData, dataWidth);
1.416 + }
1.417 + --currData;
1.418 + --currEdge;
1.419 + }
1.420 +
1.421 + currData -= dataWidth-1;
1.422 + currEdge -= dataWidth-1;
1.423 + }
1.424 +
1.425 + // copy results to final distance field data
1.426 + currData = dataPtr + dataWidth+1;
1.427 + currEdge = edgePtr + dataWidth+1;
1.428 + unsigned char *dfPtr = distanceField;
1.429 + for (int j = 1; j < dataHeight-1; ++j) {
1.430 + for (int i = 1; i < dataWidth-1; ++i) {
1.431 +#if DUMP_EDGE
1.432 + unsigned char val = sk_float_round2int(255*currData->fAlpha);
1.433 + if (*currEdge) {
1.434 + val = 128;
1.435 + }
1.436 + *dfPtr++ = val;
1.437 +#else
1.438 + float dist;
1.439 + if (currData->fAlpha > 0.5f) {
1.440 + dist = -SkScalarSqrt(currData->fDistSq);
1.441 + } else {
1.442 + dist = SkScalarSqrt(currData->fDistSq);
1.443 + }
1.444 + *dfPtr++ = pack_distance_field_val(dist, (float)distanceMagnitude);
1.445 +#endif
1.446 + ++currData;
1.447 + ++currEdge;
1.448 + }
1.449 + currData += 2;
1.450 + currEdge += 2;
1.451 + }
1.452 +
1.453 + return true;
1.454 +}
