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