1 /* 2 * Copyright 2014 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #include "SkAutoMalloc.h" 9 #include "SkDistanceFieldGen.h" 10 #include "SkPoint.h" 11 #include "SkTemplates.h" 12 13 struct DFData { 14 float fAlpha; // alpha value of source texel 15 float fDistSq; // distance squared to nearest (so far) edge texel 16 SkPoint fDistVector; // distance vector to nearest (so far) edge texel 17 }; 18 19 enum NeighborFlags { 20 kLeft_NeighborFlag = 0x01, 21 kRight_NeighborFlag = 0x02, 22 kTopLeft_NeighborFlag = 0x04, 23 kTop_NeighborFlag = 0x08, 24 kTopRight_NeighborFlag = 0x10, 25 kBottomLeft_NeighborFlag = 0x20, 26 kBottom_NeighborFlag = 0x40, 27 kBottomRight_NeighborFlag = 0x80, 28 kAll_NeighborFlags = 0xff, 29 30 kNeighborFlagCount = 8 31 }; 32 33 // We treat an "edge" as a place where we cross from >=128 to <128, or vice versa, or 34 // where we have two non-zero pixels that are <128. 35 // 'neighborFlags' is used to limit the directions in which we test to avoid indexing 36 // outside of the image 37 static bool found_edge(const unsigned char* imagePtr, int width, int neighborFlags) { 38 // the order of these should match the neighbor flags above 39 const int kNum8ConnectedNeighbors = 8; 40 const int offsets[8] = {-1, 1, -width-1, -width, -width+1, width-1, width, width+1 }; 41 SkASSERT(kNum8ConnectedNeighbors == kNeighborFlagCount); 42 43 // search for an edge 44 unsigned char currVal = *imagePtr; 45 unsigned char currCheck = (currVal >> 7); 46 for (int i = 0; i < kNum8ConnectedNeighbors; ++i) { 47 unsigned char neighborVal; 48 if ((1 << i) & neighborFlags) { 49 const unsigned char* checkPtr = imagePtr + offsets[i]; 50 neighborVal = *checkPtr; 51 } else { 52 neighborVal = 0; 53 } 54 unsigned char neighborCheck = (neighborVal >> 7); 55 SkASSERT(currCheck == 0 || currCheck == 1); 56 SkASSERT(neighborCheck == 0 || neighborCheck == 1); 57 // if sharp transition 58 if (currCheck != neighborCheck || 59 // or both <128 and >0 60 (!currCheck && !neighborCheck && currVal && neighborVal)) { 61 return true; 62 } 63 } 64 65 return false; 66 } 67 68 static void init_glyph_data(DFData* data, unsigned char* edges, const unsigned char* image, 69 int dataWidth, int dataHeight, 70 int imageWidth, int imageHeight, 71 int pad) { 72 data += pad*dataWidth; 73 data += pad; 74 edges += (pad*dataWidth + pad); 75 76 for (int j = 0; j < imageHeight; ++j) { 77 for (int i = 0; i < imageWidth; ++i) { 78 if (255 == *image) { 79 data->fAlpha = 1.0f; 80 } else { 81 data->fAlpha = (*image)*0.00392156862f; // 1/255 82 } 83 int checkMask = kAll_NeighborFlags; 84 if (i == 0) { 85 checkMask &= ~(kLeft_NeighborFlag|kTopLeft_NeighborFlag|kBottomLeft_NeighborFlag); 86 } 87 if (i == imageWidth-1) { 88 checkMask &= ~(kRight_NeighborFlag|kTopRight_NeighborFlag|kBottomRight_NeighborFlag); 89 } 90 if (j == 0) { 91 checkMask &= ~(kTopLeft_NeighborFlag|kTop_NeighborFlag|kTopRight_NeighborFlag); 92 } 93 if (j == imageHeight-1) { 94 checkMask &= ~(kBottomLeft_NeighborFlag|kBottom_NeighborFlag|kBottomRight_NeighborFlag); 95 } 96 if (found_edge(image, imageWidth, checkMask)) { 97 *edges = 255; // using 255 makes for convenient debug rendering 98 } 99 ++data; 100 ++image; 101 ++edges; 102 } 103 data += 2*pad; 104 edges += 2*pad; 105 } 106 } 107 108 // from Gustavson (2011) 109 // computes the distance to an edge given an edge normal vector and a pixel's alpha value 110 // assumes that direction has been pre-normalized 111 static float edge_distance(const SkPoint& direction, float alpha) { 112 float dx = direction.fX; 113 float dy = direction.fY; 114 float distance; 115 if (SkScalarNearlyZero(dx) || SkScalarNearlyZero(dy)) { 116 distance = 0.5f - alpha; 117 } else { 118 // this is easier if we treat the direction as being in the first octant 119 // (other octants are symmetrical) 120 dx = SkScalarAbs(dx); 121 dy = SkScalarAbs(dy); 122 if (dx < dy) { 123 SkTSwap(dx, dy); 124 } 125 126 // a1 = 0.5*dy/dx is the smaller fractional area chopped off by the edge 127 // to avoid the divide, we just consider the numerator 128 float a1num = 0.5f*dy; 129 130 // we now compute the approximate distance, depending where the alpha falls 131 // relative to the edge fractional area 132 133 // if 0 <= alpha < a1 134 if (alpha*dx < a1num) { 135 // TODO: find a way to do this without square roots? 136 distance = 0.5f*(dx + dy) - SkScalarSqrt(2.0f*dx*dy*alpha); 137 // if a1 <= alpha <= 1 - a1 138 } else if (alpha*dx < (dx - a1num)) { 139 distance = (0.5f - alpha)*dx; 140 // if 1 - a1 < alpha <= 1 141 } else { 142 // TODO: find a way to do this without square roots? 143 distance = -0.5f*(dx + dy) + SkScalarSqrt(2.0f*dx*dy*(1.0f - alpha)); 144 } 145 } 146 147 return distance; 148 } 149 150 static void init_distances(DFData* data, unsigned char* edges, int width, int height) { 151 // skip one pixel border 152 DFData* currData = data; 153 DFData* prevData = data - width; 154 DFData* nextData = data + width; 155 156 for (int j = 0; j < height; ++j) { 157 for (int i = 0; i < width; ++i) { 158 if (*edges) { 159 // we should not be in the one-pixel outside band 160 SkASSERT(i > 0 && i < width-1 && j > 0 && j < height-1); 161 // gradient will point from low to high 162 // +y is down in this case 163 // i.e., if you're outside, gradient points towards edge 164 // if you're inside, gradient points away from edge 165 SkPoint currGrad; 166 currGrad.fX = (prevData+1)->fAlpha - (prevData-1)->fAlpha 167 + SK_ScalarSqrt2*(currData+1)->fAlpha 168 - SK_ScalarSqrt2*(currData-1)->fAlpha 169 + (nextData+1)->fAlpha - (nextData-1)->fAlpha; 170 currGrad.fY = (nextData-1)->fAlpha - (prevData-1)->fAlpha 171 + SK_ScalarSqrt2*nextData->fAlpha 172 - SK_ScalarSqrt2*prevData->fAlpha 173 + (nextData+1)->fAlpha - (prevData+1)->fAlpha; 174 currGrad.setLengthFast(1.0f); 175 176 // init squared distance to edge and distance vector 177 float dist = edge_distance(currGrad, currData->fAlpha); 178 currGrad.scale(dist, &currData->fDistVector); 179 currData->fDistSq = dist*dist; 180 } else { 181 // init distance to "far away" 182 currData->fDistSq = 2000000.f; 183 currData->fDistVector.fX = 1000.f; 184 currData->fDistVector.fY = 1000.f; 185 } 186 ++currData; 187 ++prevData; 188 ++nextData; 189 ++edges; 190 } 191 } 192 } 193 194 // Danielsson's 8SSEDT 195 196 // first stage forward pass 197 // (forward in Y, forward in X) 198 static void F1(DFData* curr, int width) { 199 // upper left 200 DFData* check = curr - width-1; 201 SkPoint distVec = check->fDistVector; 202 float distSq = check->fDistSq - 2.0f*(distVec.fX + distVec.fY - 1.0f); 203 if (distSq < curr->fDistSq) { 204 distVec.fX -= 1.0f; 205 distVec.fY -= 1.0f; 206 curr->fDistSq = distSq; 207 curr->fDistVector = distVec; 208 } 209 210 // up 211 check = curr - width; 212 distVec = check->fDistVector; 213 distSq = check->fDistSq - 2.0f*distVec.fY + 1.0f; 214 if (distSq < curr->fDistSq) { 215 distVec.fY -= 1.0f; 216 curr->fDistSq = distSq; 217 curr->fDistVector = distVec; 218 } 219 220 // upper right 221 check = curr - width+1; 222 distVec = check->fDistVector; 223 distSq = check->fDistSq + 2.0f*(distVec.fX - distVec.fY + 1.0f); 224 if (distSq < curr->fDistSq) { 225 distVec.fX += 1.0f; 226 distVec.fY -= 1.0f; 227 curr->fDistSq = distSq; 228 curr->fDistVector = distVec; 229 } 230 231 // left 232 check = curr - 1; 233 distVec = check->fDistVector; 234 distSq = check->fDistSq - 2.0f*distVec.fX + 1.0f; 235 if (distSq < curr->fDistSq) { 236 distVec.fX -= 1.0f; 237 curr->fDistSq = distSq; 238 curr->fDistVector = distVec; 239 } 240 } 241 242 // second stage forward pass 243 // (forward in Y, backward in X) 244 static void F2(DFData* curr, int width) { 245 // right 246 DFData* check = curr + 1; 247 SkPoint distVec = check->fDistVector; 248 float distSq = check->fDistSq + 2.0f*distVec.fX + 1.0f; 249 if (distSq < curr->fDistSq) { 250 distVec.fX += 1.0f; 251 curr->fDistSq = distSq; 252 curr->fDistVector = distVec; 253 } 254 } 255 256 // first stage backward pass 257 // (backward in Y, forward in X) 258 static void B1(DFData* curr, int width) { 259 // left 260 DFData* check = curr - 1; 261 SkPoint distVec = check->fDistVector; 262 float distSq = check->fDistSq - 2.0f*distVec.fX + 1.0f; 263 if (distSq < curr->fDistSq) { 264 distVec.fX -= 1.0f; 265 curr->fDistSq = distSq; 266 curr->fDistVector = distVec; 267 } 268 } 269 270 // second stage backward pass 271 // (backward in Y, backwards in X) 272 static void B2(DFData* curr, int width) { 273 // right 274 DFData* check = curr + 1; 275 SkPoint distVec = check->fDistVector; 276 float distSq = check->fDistSq + 2.0f*distVec.fX + 1.0f; 277 if (distSq < curr->fDistSq) { 278 distVec.fX += 1.0f; 279 curr->fDistSq = distSq; 280 curr->fDistVector = distVec; 281 } 282 283 // bottom left 284 check = curr + width-1; 285 distVec = check->fDistVector; 286 distSq = check->fDistSq - 2.0f*(distVec.fX - distVec.fY - 1.0f); 287 if (distSq < curr->fDistSq) { 288 distVec.fX -= 1.0f; 289 distVec.fY += 1.0f; 290 curr->fDistSq = distSq; 291 curr->fDistVector = distVec; 292 } 293 294 // bottom 295 check = curr + width; 296 distVec = check->fDistVector; 297 distSq = check->fDistSq + 2.0f*distVec.fY + 1.0f; 298 if (distSq < curr->fDistSq) { 299 distVec.fY += 1.0f; 300 curr->fDistSq = distSq; 301 curr->fDistVector = distVec; 302 } 303 304 // bottom right 305 check = curr + width+1; 306 distVec = check->fDistVector; 307 distSq = check->fDistSq + 2.0f*(distVec.fX + distVec.fY + 1.0f); 308 if (distSq < curr->fDistSq) { 309 distVec.fX += 1.0f; 310 distVec.fY += 1.0f; 311 curr->fDistSq = distSq; 312 curr->fDistVector = distVec; 313 } 314 } 315 316 // enable this to output edge data rather than the distance field 317 #define DUMP_EDGE 0 318 319 #if !DUMP_EDGE 320 template <int distanceMagnitude> 321 static unsigned char pack_distance_field_val(float dist) { 322 // The distance field is constructed as unsigned char values, so that the zero value is at 128, 323 // Beside 128, we have 128 values in range [0, 128), but only 127 values in range (128, 255]. 324 // So we multiply distanceMagnitude by 127/128 at the latter range to avoid overflow. 325 dist = SkScalarPin(-dist, -distanceMagnitude, distanceMagnitude * 127.0f / 128.0f); 326 327 // Scale into the positive range for unsigned distance. 328 dist += distanceMagnitude; 329 330 // Scale into unsigned char range. 331 // Round to place negative and positive values as equally as possible around 128 332 // (which represents zero). 333 return (unsigned char)SkScalarRoundToInt(dist / (2 * distanceMagnitude) * 256.0f); 334 } 335 #endif 336 337 // assumes a padded 8-bit image and distance field 338 // width and height are the original width and height of the image 339 static bool generate_distance_field_from_image(unsigned char* distanceField, 340 const unsigned char* copyPtr, 341 int width, int height) { 342 SkASSERT(distanceField); 343 SkASSERT(copyPtr); 344 345 // we expand our temp data by one more on each side to simplify 346 // the scanning code -- will always be treated as infinitely far away 347 int pad = SK_DistanceFieldPad + 1; 348 349 // set params for distance field data 350 int dataWidth = width + 2*pad; 351 int dataHeight = height + 2*pad; 352 353 // create zeroed temp DFData+edge storage 354 SkAutoFree storage(sk_calloc_throw(dataWidth*dataHeight*(sizeof(DFData) + 1))); 355 DFData* dataPtr = (DFData*)storage.get(); 356 unsigned char* edgePtr = (unsigned char*)storage.get() + dataWidth*dataHeight*sizeof(DFData); 357 358 // copy glyph into distance field storage 359 init_glyph_data(dataPtr, edgePtr, copyPtr, 360 dataWidth, dataHeight, 361 width+2, height+2, SK_DistanceFieldPad); 362 363 // create initial distance data, particularly at edges 364 init_distances(dataPtr, edgePtr, dataWidth, dataHeight); 365 366 // now perform Euclidean distance transform to propagate distances 367 368 // forwards in y 369 DFData* currData = dataPtr+dataWidth+1; // skip outer buffer 370 unsigned char* currEdge = edgePtr+dataWidth+1; 371 for (int j = 1; j < dataHeight-1; ++j) { 372 // forwards in x 373 for (int i = 1; i < dataWidth-1; ++i) { 374 // don't need to calculate distance for edge pixels 375 if (!*currEdge) { 376 F1(currData, dataWidth); 377 } 378 ++currData; 379 ++currEdge; 380 } 381 382 // backwards in x 383 --currData; // reset to end 384 --currEdge; 385 for (int i = 1; i < dataWidth-1; ++i) { 386 // don't need to calculate distance for edge pixels 387 if (!*currEdge) { 388 F2(currData, dataWidth); 389 } 390 --currData; 391 --currEdge; 392 } 393 394 currData += dataWidth+1; 395 currEdge += dataWidth+1; 396 } 397 398 // backwards in y 399 currData = dataPtr+dataWidth*(dataHeight-2) - 1; // skip outer buffer 400 currEdge = edgePtr+dataWidth*(dataHeight-2) - 1; 401 for (int j = 1; j < dataHeight-1; ++j) { 402 // forwards in x 403 for (int i = 1; i < dataWidth-1; ++i) { 404 // don't need to calculate distance for edge pixels 405 if (!*currEdge) { 406 B1(currData, dataWidth); 407 } 408 ++currData; 409 ++currEdge; 410 } 411 412 // backwards in x 413 --currData; // reset to end 414 --currEdge; 415 for (int i = 1; i < dataWidth-1; ++i) { 416 // don't need to calculate distance for edge pixels 417 if (!*currEdge) { 418 B2(currData, dataWidth); 419 } 420 --currData; 421 --currEdge; 422 } 423 424 currData -= dataWidth-1; 425 currEdge -= dataWidth-1; 426 } 427 428 // copy results to final distance field data 429 currData = dataPtr + dataWidth+1; 430 currEdge = edgePtr + dataWidth+1; 431 unsigned char *dfPtr = distanceField; 432 for (int j = 1; j < dataHeight-1; ++j) { 433 for (int i = 1; i < dataWidth-1; ++i) { 434 #if DUMP_EDGE 435 float alpha = currData->fAlpha; 436 float edge = 0.0f; 437 if (*currEdge) { 438 edge = 0.25f; 439 } 440 // blend with original image 441 float result = alpha + (1.0f-alpha)*edge; 442 unsigned char val = sk_float_round2int(255*result); 443 *dfPtr++ = val; 444 #else 445 float dist; 446 if (currData->fAlpha > 0.5f) { 447 dist = -SkScalarSqrt(currData->fDistSq); 448 } else { 449 dist = SkScalarSqrt(currData->fDistSq); 450 } 451 *dfPtr++ = pack_distance_field_val<SK_DistanceFieldMagnitude>(dist); 452 #endif 453 ++currData; 454 ++currEdge; 455 } 456 currData += 2; 457 currEdge += 2; 458 } 459 460 return true; 461 } 462 463 // assumes an 8-bit image and distance field 464 bool SkGenerateDistanceFieldFromA8Image(unsigned char* distanceField, 465 const unsigned char* image, 466 int width, int height, size_t rowBytes) { 467 SkASSERT(distanceField); 468 SkASSERT(image); 469 470 // create temp data 471 SkAutoSMalloc<1024> copyStorage((width+2)*(height+2)*sizeof(char)); 472 unsigned char* copyPtr = (unsigned char*) copyStorage.get(); 473 474 // we copy our source image into a padded copy to ensure we catch edge transitions 475 // around the outside 476 const unsigned char* currSrcScanLine = image; 477 sk_bzero(copyPtr, (width+2)*sizeof(char)); 478 unsigned char* currDestPtr = copyPtr + width + 2; 479 for (int i = 0; i < height; ++i) { 480 *currDestPtr++ = 0; 481 memcpy(currDestPtr, currSrcScanLine, rowBytes); 482 currSrcScanLine += rowBytes; 483 currDestPtr += width; 484 *currDestPtr++ = 0; 485 } 486 sk_bzero(currDestPtr, (width+2)*sizeof(char)); 487 488 return generate_distance_field_from_image(distanceField, copyPtr, width, height); 489 } 490 491 // assumes a 1-bit image and 8-bit distance field 492 bool SkGenerateDistanceFieldFromBWImage(unsigned char* distanceField, 493 const unsigned char* image, 494 int width, int height, size_t rowBytes) { 495 SkASSERT(distanceField); 496 SkASSERT(image); 497 498 // create temp data 499 SkAutoSMalloc<1024> copyStorage((width+2)*(height+2)*sizeof(char)); 500 unsigned char* copyPtr = (unsigned char*) copyStorage.get(); 501 502 // we copy our source image into a padded copy to ensure we catch edge transitions 503 // around the outside 504 const unsigned char* currSrcScanLine = image; 505 sk_bzero(copyPtr, (width+2)*sizeof(char)); 506 unsigned char* currDestPtr = copyPtr + width + 2; 507 for (int i = 0; i < height; ++i) { 508 *currDestPtr++ = 0; 509 int rowWritesLeft = width; 510 const unsigned char *maskPtr = currSrcScanLine; 511 while (rowWritesLeft > 0) { 512 unsigned mask = *maskPtr++; 513 for (int i = 7; i >= 0 && rowWritesLeft; --i, --rowWritesLeft) { 514 *currDestPtr++ = (mask & (1 << i)) ? 0xff : 0; 515 } 516 } 517 currSrcScanLine += rowBytes; 518 *currDestPtr++ = 0; 519 } 520 sk_bzero(currDestPtr, (width+2)*sizeof(char)); 521 522 return generate_distance_field_from_image(distanceField, copyPtr, width, height); 523 } 524