OLD | NEW |
(Empty) | |
| 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 |
| 11 struct 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 |
| 17 // We treat an "edge" as a place where we cross from a texel >= 128 to a texel <
128, |
| 18 // or vice versa. This means we just need to check if the MSBs are different. |
| 19 static bool found_edge(const unsigned char* imagePtr, int width) { |
| 20 const int offsets[8] = {-1, 1, -width-1, -width, -width+1, width-1, width, w
idth+1 }; |
| 21 |
| 22 // search for an edge |
| 23 int checkVal = *imagePtr >> 7; |
| 24 for (int i = 0; i < 8; ++i) { |
| 25 const unsigned char* checkPtr = imagePtr + offsets[i]; |
| 26 if (checkVal ^ (*checkPtr >> 7)) { |
| 27 return true; |
| 28 } |
| 29 } |
| 30 |
| 31 return false; |
| 32 } |
| 33 |
| 34 static void init_glyph_data(DFData* data, unsigned char* edges, const unsigned c
har* image, |
| 35 int dataWidth, int dataHeight, |
| 36 int imageWidth, int imageHeight, |
| 37 int pad) { |
| 38 data += pad*dataWidth; |
| 39 data += pad; |
| 40 edges += (pad*dataWidth + pad); |
| 41 |
| 42 for (int j = 0; j < imageHeight; ++j) { |
| 43 for (int i = 0; i < imageWidth; ++i) { |
| 44 if (255 == *image) { |
| 45 data->fAlpha = 1.0f; |
| 46 } else { |
| 47 data->fAlpha = (*image)*0.00392156862f; // 1/255 |
| 48 } |
| 49 if (i > 0 && i < imageWidth-1 && j > 0 && j < imageHeight-1 && |
| 50 found_edge(image, imageWidth)) { |
| 51 *edges = 255; // using 255 makes for convenient debug rendering |
| 52 } |
| 53 ++data; |
| 54 ++image; |
| 55 ++edges; |
| 56 } |
| 57 data += 2*pad; |
| 58 edges += 2*pad; |
| 59 } |
| 60 } |
| 61 |
| 62 // from Gustavson (2011) |
| 63 // computes the distance to an edge given an edge normal vector and a pixel's al
pha value |
| 64 // assumes that direction has been pre-normalized |
| 65 static float edge_distance(const SkPoint& direction, float alpha) { |
| 66 float dx = direction.fX; |
| 67 float dy = direction.fY; |
| 68 float distance; |
| 69 if (SkScalarNearlyZero(dx) || SkScalarNearlyZero(dy)) { |
| 70 distance = 0.5f - alpha; |
| 71 } else { |
| 72 // this is easier if we treat the direction as being in the first octant |
| 73 // (other octants are symmetrical) |
| 74 dx = SkScalarAbs(dx); |
| 75 dy = SkScalarAbs(dy); |
| 76 if (dx < dy) { |
| 77 SkTSwap(dx, dy); |
| 78 } |
| 79 |
| 80 // a1 = 0.5*dy/dx is the smaller fractional area chopped off by the edge |
| 81 // to avoid the divide, we just consider the numerator |
| 82 float a1num = 0.5f*dy; |
| 83 |
| 84 // we now compute the approximate distance, depending where the alpha fa
lls |
| 85 // relative to the edge fractional area |
| 86 |
| 87 // if 0 <= alpha < a1 |
| 88 if (alpha*dx < a1num) { |
| 89 // TODO: find a way to do this without square roots? |
| 90 distance = 0.5f*(dx + dy) - SkScalarSqrt(2.0f*dx*dy*alpha); |
| 91 // if a1 <= alpha <= 1 - a1 |
| 92 } else if (alpha*dx < (dx - a1num)) { |
| 93 distance = (0.5f - alpha)*dx; |
| 94 // if 1 - a1 < alpha <= 1 |
| 95 } else { |
| 96 // TODO: find a way to do this without square roots? |
| 97 distance = -0.5f*(dx + dy) + SkScalarSqrt(2.0f*dx*dy*(1.0f - alpha))
; |
| 98 } |
| 99 } |
| 100 |
| 101 return distance; |
| 102 } |
| 103 |
| 104 static void init_distances(DFData* data, unsigned char* edges, int width, int he
ight) { |
| 105 // skip one pixel border |
| 106 DFData* currData = data; |
| 107 DFData* prevData = data - width; |
| 108 DFData* nextData = data + width; |
| 109 |
| 110 for (int j = 0; j < height; ++j) { |
| 111 for (int i = 0; i < width; ++i) { |
| 112 if (*edges) { |
| 113 // we should not be in the one-pixel outside band |
| 114 SkASSERT(i > 0 && i < width-1 && j > 0 && j < height-1); |
| 115 // gradient will point from low to high |
| 116 // +y is down in this case |
| 117 // i.e., if you're outside, gradient points towards edge |
| 118 // if you're inside, gradient points away from edge |
| 119 SkPoint currGrad; |
| 120 currGrad.fX = (prevData+1)->fAlpha - (prevData-1)->fAlpha |
| 121 + SK_ScalarSqrt2*(currData+1)->fAlpha |
| 122 - SK_ScalarSqrt2*(currData-1)->fAlpha |
| 123 + (nextData+1)->fAlpha - (nextData-1)->fAlpha; |
| 124 currGrad.fY = (nextData-1)->fAlpha - (prevData-1)->fAlpha |
| 125 + SK_ScalarSqrt2*nextData->fAlpha |
| 126 - SK_ScalarSqrt2*prevData->fAlpha |
| 127 + (nextData+1)->fAlpha - (prevData+1)->fAlpha; |
| 128 currGrad.setLengthFast(1.0f); |
| 129 |
| 130 // init squared distance to edge and distance vector |
| 131 float dist = edge_distance(currGrad, currData->fAlpha); |
| 132 currGrad.scale(dist, &currData->fDistVector); |
| 133 currData->fDistSq = dist*dist; |
| 134 } else { |
| 135 // init distance to "far away" |
| 136 currData->fDistSq = 2000000.f; |
| 137 currData->fDistVector.fX = 1000.f; |
| 138 currData->fDistVector.fY = 1000.f; |
| 139 } |
| 140 ++currData; |
| 141 ++prevData; |
| 142 ++nextData; |
| 143 ++edges; |
| 144 } |
| 145 } |
| 146 } |
| 147 |
| 148 // Danielsson's 8SSEDT |
| 149 |
| 150 // first stage forward pass |
| 151 // (forward in Y, forward in X) |
| 152 static void F1(DFData* curr, int width) { |
| 153 // upper left |
| 154 DFData* check = curr - width-1; |
| 155 SkPoint distVec = check->fDistVector; |
| 156 float distSq = check->fDistSq - 2.0f*(distVec.fX + distVec.fY - 1.0f); |
| 157 if (distSq < curr->fDistSq) { |
| 158 distVec.fX -= 1.0f; |
| 159 distVec.fY -= 1.0f; |
| 160 curr->fDistSq = distSq; |
| 161 curr->fDistVector = distVec; |
| 162 } |
| 163 |
| 164 // up |
| 165 check = curr - width; |
| 166 distVec = check->fDistVector; |
| 167 distSq = check->fDistSq - 2.0f*distVec.fY + 1.0f; |
| 168 if (distSq < curr->fDistSq) { |
| 169 distVec.fY -= 1.0f; |
| 170 curr->fDistSq = distSq; |
| 171 curr->fDistVector = distVec; |
| 172 } |
| 173 |
| 174 // upper right |
| 175 check = curr - width+1; |
| 176 distVec = check->fDistVector; |
| 177 distSq = check->fDistSq + 2.0f*(distVec.fX - distVec.fY + 1.0f); |
| 178 if (distSq < curr->fDistSq) { |
| 179 distVec.fX += 1.0f; |
| 180 distVec.fY -= 1.0f; |
| 181 curr->fDistSq = distSq; |
| 182 curr->fDistVector = distVec; |
| 183 } |
| 184 |
| 185 // left |
| 186 check = curr - 1; |
| 187 distVec = check->fDistVector; |
| 188 distSq = check->fDistSq - 2.0f*distVec.fX + 1.0f; |
| 189 if (distSq < curr->fDistSq) { |
| 190 distVec.fX -= 1.0f; |
| 191 curr->fDistSq = distSq; |
| 192 curr->fDistVector = distVec; |
| 193 } |
| 194 } |
| 195 |
| 196 // second stage forward pass |
| 197 // (forward in Y, backward in X) |
| 198 static void F2(DFData* curr, int width) { |
| 199 // right |
| 200 DFData* check = curr + 1; |
| 201 float distSq = check->fDistSq; |
| 202 SkPoint distVec = check->fDistVector; |
| 203 distSq = check->fDistSq + 2.0f*distVec.fX + 1.0f; |
| 204 if (distSq < curr->fDistSq) { |
| 205 distVec.fX += 1.0f; |
| 206 curr->fDistSq = distSq; |
| 207 curr->fDistVector = distVec; |
| 208 } |
| 209 } |
| 210 |
| 211 // first stage backward pass |
| 212 // (backward in Y, forward in X) |
| 213 static void B1(DFData* curr, int width) { |
| 214 // left |
| 215 DFData* check = curr - 1; |
| 216 SkPoint distVec = check->fDistVector; |
| 217 float distSq = check->fDistSq - 2.0f*distVec.fX + 1.0f; |
| 218 if (distSq < curr->fDistSq) { |
| 219 distVec.fX -= 1.0f; |
| 220 curr->fDistSq = distSq; |
| 221 curr->fDistVector = distVec; |
| 222 } |
| 223 } |
| 224 |
| 225 // second stage backward pass |
| 226 // (backward in Y, backwards in X) |
| 227 static void B2(DFData* curr, int width) { |
| 228 // right |
| 229 DFData* check = curr + 1; |
| 230 SkPoint distVec = check->fDistVector; |
| 231 float distSq = check->fDistSq + 2.0f*distVec.fX + 1.0f; |
| 232 if (distSq < curr->fDistSq) { |
| 233 distVec.fX += 1.0f; |
| 234 curr->fDistSq = distSq; |
| 235 curr->fDistVector = distVec; |
| 236 } |
| 237 |
| 238 // bottom left |
| 239 check = curr + width-1; |
| 240 distVec = check->fDistVector; |
| 241 distSq = check->fDistSq - 2.0f*(distVec.fX - distVec.fY - 1.0f); |
| 242 if (distSq < curr->fDistSq) { |
| 243 distVec.fX -= 1.0f; |
| 244 distVec.fY += 1.0f; |
| 245 curr->fDistSq = distSq; |
| 246 curr->fDistVector = distVec; |
| 247 } |
| 248 |
| 249 // bottom |
| 250 check = curr + width; |
| 251 distVec = check->fDistVector; |
| 252 distSq = check->fDistSq + 2.0f*distVec.fY + 1.0f; |
| 253 if (distSq < curr->fDistSq) { |
| 254 distVec.fY += 1.0f; |
| 255 curr->fDistSq = distSq; |
| 256 curr->fDistVector = distVec; |
| 257 } |
| 258 |
| 259 // bottom right |
| 260 check = curr + width+1; |
| 261 distVec = check->fDistVector; |
| 262 distSq = check->fDistSq + 2.0f*(distVec.fX + distVec.fY + 1.0f); |
| 263 if (distSq < curr->fDistSq) { |
| 264 distVec.fX += 1.0f; |
| 265 distVec.fY += 1.0f; |
| 266 curr->fDistSq = distSq; |
| 267 curr->fDistVector = distVec; |
| 268 } |
| 269 } |
| 270 |
| 271 static unsigned char pack_distance_field_val(float dist, float distanceMagnitude
) { |
| 272 if (dist <= -distanceMagnitude) { |
| 273 return 255; |
| 274 } else if (dist > distanceMagnitude) { |
| 275 return 0; |
| 276 } else { |
| 277 return (unsigned char)((distanceMagnitude-dist)*128.0f/distanceMagnitude
); |
| 278 } |
| 279 } |
| 280 |
| 281 // assumes an 8-bit image and distance field |
| 282 bool SkGenerateDistanceFieldFromImage(unsigned char* distanceField, |
| 283 const unsigned char* image, |
| 284 int width, int height, |
| 285 int distanceMagnitude) { |
| 286 SkASSERT(NULL != distanceField); |
| 287 SkASSERT(NULL != image); |
| 288 |
| 289 // the final distance field will have additional texels on each side to hand
le |
| 290 // the maximum distance |
| 291 // we expand our temp data by one more on each side to simplify |
| 292 // the scanning code -- will always be treated as infinitely far away |
| 293 int pad = distanceMagnitude+1; |
| 294 |
| 295 // set params for distance field data |
| 296 int dataWidth = width + 2*pad; |
| 297 int dataHeight = height + 2*pad; |
| 298 |
| 299 // create temp data |
| 300 size_t dataSize = dataWidth*dataHeight*sizeof(DFData); |
| 301 SkAutoSMalloc<1024> dfStorage(dataSize); |
| 302 DFData* dataPtr = (DFData*) dfStorage.get(); |
| 303 sk_bzero(dataPtr, dataSize); |
| 304 |
| 305 SkAutoSMalloc<1024> edgeStorage(dataWidth*dataHeight*sizeof(char)); |
| 306 unsigned char* edgePtr = (unsigned char*) edgeStorage.get(); |
| 307 sk_bzero(edgePtr, dataWidth*dataHeight*sizeof(char)); |
| 308 |
| 309 // copy glyph into distance field storage |
| 310 init_glyph_data(dataPtr, edgePtr, image, |
| 311 dataWidth, dataHeight, |
| 312 width, height, pad); |
| 313 |
| 314 // create initial distance data, particularly at edges |
| 315 init_distances(dataPtr, edgePtr, dataWidth, dataHeight); |
| 316 |
| 317 // now perform Euclidean distance transform to propagate distances |
| 318 |
| 319 // forwards in y |
| 320 DFData* currData = dataPtr+dataWidth+1; // skip outer buffer |
| 321 unsigned char* currEdge = edgePtr+dataWidth+1; |
| 322 for (int j = 1; j < dataHeight-1; ++j) { |
| 323 // forwards in x |
| 324 for (int i = 1; i < dataWidth-1; ++i) { |
| 325 // don't need to calculate distance for edge pixels |
| 326 if (!*currEdge) { |
| 327 F1(currData, dataWidth); |
| 328 } |
| 329 ++currData; |
| 330 ++currEdge; |
| 331 } |
| 332 |
| 333 // backwards in x |
| 334 --currData; // reset to end |
| 335 --currEdge; |
| 336 for (int i = 1; i < dataWidth-1; ++i) { |
| 337 // don't need to calculate distance for edge pixels |
| 338 if (!*currEdge) { |
| 339 F2(currData, dataWidth); |
| 340 } |
| 341 --currData; |
| 342 --currEdge; |
| 343 } |
| 344 |
| 345 currData += dataWidth+1; |
| 346 currEdge += dataWidth+1; |
| 347 } |
| 348 |
| 349 // backwards in y |
| 350 currData = dataPtr+dataWidth*(dataHeight-2) - 1; // skip outer buffer |
| 351 currEdge = edgePtr+dataWidth*(dataHeight-2) - 1; |
| 352 for (int j = 1; j < dataHeight-1; ++j) { |
| 353 // forwards in x |
| 354 for (int i = 1; i < dataWidth-1; ++i) { |
| 355 // don't need to calculate distance for edge pixels |
| 356 if (!*currEdge) { |
| 357 B1(currData, dataWidth); |
| 358 } |
| 359 ++currData; |
| 360 ++currEdge; |
| 361 } |
| 362 |
| 363 // backwards in x |
| 364 --currData; // reset to end |
| 365 --currEdge; |
| 366 for (int i = 1; i < dataWidth-1; ++i) { |
| 367 // don't need to calculate distance for edge pixels |
| 368 if (!*currEdge) { |
| 369 B2(currData, dataWidth); |
| 370 } |
| 371 --currData; |
| 372 --currEdge; |
| 373 } |
| 374 |
| 375 currData -= dataWidth-1; |
| 376 currEdge -= dataWidth-1; |
| 377 } |
| 378 |
| 379 // copy results to final distance field data |
| 380 currData = dataPtr + dataWidth+1; |
| 381 currEdge = edgePtr + dataWidth+1; |
| 382 unsigned char *dfPtr = distanceField; |
| 383 for (int j = 1; j < dataHeight-1; ++j) { |
| 384 for (int i = 1; i < dataWidth-1; ++i) { |
| 385 float dist; |
| 386 if (currData->fAlpha > 0.5f) { |
| 387 dist = -SkScalarSqrt(currData->fDistSq); |
| 388 } else { |
| 389 dist = SkScalarSqrt(currData->fDistSq); |
| 390 } |
| 391 |
| 392 *dfPtr++ = pack_distance_field_val(dist, (float)distanceMagnitude); |
| 393 ++currData; |
| 394 ++currEdge; |
| 395 } |
| 396 currData += 2; |
| 397 currEdge += 2; |
| 398 } |
| 399 |
| 400 return true; |
| 401 } |
OLD | NEW |