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