| 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, char* edges, const unsigned char* imag
e, | |
| 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, char* edges, int width, int height) { | |
| 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 char* edgePtr = (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 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 |
|---|
Chromium Code Reviews
Issue 190753015:
Revert of Add new module for distance field generation. (Closed)
Base URL: https://skia.googlesource.com/skia.git@master