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