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