gfx/skia/trunk/src/core/SkDistanceFieldGen.cpp@129ffea94266
gfx/skia/trunk/src/core/SkDistanceFieldGen.cpp
Sat, 03 Jan 2015 20:18:00 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Sat, 03 Jan 2015 20:18:00 +0100
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
- permissions
- -rwxr-xr-x
Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.
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 */
8 #include "SkDistanceFieldGen.h"
9 #include "SkPoint.h"
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 };
17 enum NeighborFlags {
18 kLeft_NeighborFlag = 0x01,
19 kRight_NeighborFlag = 0x02,
20 kTopLeft_NeighborFlag = 0x04,
21 kTop_NeighborFlag = 0x08,
22 kTopRight_NeighborFlag = 0x10,
23 kBottomLeft_NeighborFlag = 0x20,
24 kBottom_NeighborFlag = 0x40,
25 kBottomRight_NeighborFlag = 0x80,
26 kAll_NeighborFlags = 0xff,
28 kNeighborFlagCount = 8
29 };
31 // We treat an "edge" as a place where we cross from black to non-black, or vice versa.
32 // 'neighborFlags' is used to limit the directions in which we test to avoid indexing
33 // outside of the image
34 static bool found_edge(const unsigned char* imagePtr, int width, int neighborFlags) {
35 // the order of these should match the neighbor flags above
36 const int kNum8ConnectedNeighbors = 8;
37 const int offsets[8] = {-1, 1, -width-1, -width, -width+1, width-1, width, width+1 };
38 SkASSERT(kNum8ConnectedNeighbors == kNeighborFlagCount);
40 // search for an edge
41 bool currVal = (*imagePtr != 0);
42 for (int i = 0; i < kNum8ConnectedNeighbors; ++i) {
43 bool checkVal;
44 if ((1 << i) & neighborFlags) {
45 const unsigned char* checkPtr = imagePtr + offsets[i];
46 checkVal = (*checkPtr != 0);
47 } else {
48 checkVal = false;
49 }
50 SkASSERT(checkVal == 0 || checkVal == 1);
51 SkASSERT(currVal == 0 || currVal == 1);
52 if (checkVal != currVal) {
53 return true;
54 }
55 }
57 return false;
58 }
60 static void init_glyph_data(DFData* data, unsigned char* edges, const unsigned char* image,
61 int dataWidth, int dataHeight,
62 int imageWidth, int imageHeight,
63 int pad) {
64 data += pad*dataWidth;
65 data += pad;
66 edges += (pad*dataWidth + pad);
68 for (int j = 0; j < imageHeight; ++j) {
69 for (int i = 0; i < imageWidth; ++i) {
70 if (255 == *image) {
71 data->fAlpha = 1.0f;
72 } else {
73 data->fAlpha = (*image)*0.00392156862f; // 1/255
74 }
75 int checkMask = kAll_NeighborFlags;
76 if (i == 0) {
77 checkMask &= ~(kLeft_NeighborFlag|kTopLeft_NeighborFlag|kBottomLeft_NeighborFlag);
78 }
79 if (i == imageWidth-1) {
80 checkMask &= ~(kRight_NeighborFlag|kTopRight_NeighborFlag|kBottomRight_NeighborFlag);
81 }
82 if (j == 0) {
83 checkMask &= ~(kTopLeft_NeighborFlag|kTop_NeighborFlag|kTopRight_NeighborFlag);
84 }
85 if (j == imageHeight-1) {
86 checkMask &= ~(kBottomLeft_NeighborFlag|kBottom_NeighborFlag|kBottomRight_NeighborFlag);
87 }
88 if (found_edge(image, imageWidth, checkMask)) {
89 *edges = 255; // using 255 makes for convenient debug rendering
90 }
91 ++data;
92 ++image;
93 ++edges;
94 }
95 data += 2*pad;
96 edges += 2*pad;
97 }
98 }
100 // from Gustavson (2011)
101 // computes the distance to an edge given an edge normal vector and a pixel's alpha value
102 // assumes that direction has been pre-normalized
103 static float edge_distance(const SkPoint& direction, float alpha) {
104 float dx = direction.fX;
105 float dy = direction.fY;
106 float distance;
107 if (SkScalarNearlyZero(dx) || SkScalarNearlyZero(dy)) {
108 distance = 0.5f - alpha;
109 } else {
110 // this is easier if we treat the direction as being in the first octant
111 // (other octants are symmetrical)
112 dx = SkScalarAbs(dx);
113 dy = SkScalarAbs(dy);
114 if (dx < dy) {
115 SkTSwap(dx, dy);
116 }
118 // a1 = 0.5*dy/dx is the smaller fractional area chopped off by the edge
119 // to avoid the divide, we just consider the numerator
120 float a1num = 0.5f*dy;
122 // we now compute the approximate distance, depending where the alpha falls
123 // relative to the edge fractional area
125 // if 0 <= alpha < a1
126 if (alpha*dx < a1num) {
127 // TODO: find a way to do this without square roots?
128 distance = 0.5f*(dx + dy) - SkScalarSqrt(2.0f*dx*dy*alpha);
129 // if a1 <= alpha <= 1 - a1
130 } else if (alpha*dx < (dx - a1num)) {
131 distance = (0.5f - alpha)*dx;
132 // if 1 - a1 < alpha <= 1
133 } else {
134 // TODO: find a way to do this without square roots?
135 distance = -0.5f*(dx + dy) + SkScalarSqrt(2.0f*dx*dy*(1.0f - alpha));
136 }
137 }
139 return distance;
140 }
142 static void init_distances(DFData* data, unsigned char* edges, int width, int height) {
143 // skip one pixel border
144 DFData* currData = data;
145 DFData* prevData = data - width;
146 DFData* nextData = data + width;
148 for (int j = 0; j < height; ++j) {
149 for (int i = 0; i < width; ++i) {
150 if (*edges) {
151 // we should not be in the one-pixel outside band
152 SkASSERT(i > 0 && i < width-1 && j > 0 && j < height-1);
153 // gradient will point from low to high
154 // +y is down in this case
155 // i.e., if you're outside, gradient points towards edge
156 // if you're inside, gradient points away from edge
157 SkPoint currGrad;
158 currGrad.fX = (prevData+1)->fAlpha - (prevData-1)->fAlpha
159 + SK_ScalarSqrt2*(currData+1)->fAlpha
160 - SK_ScalarSqrt2*(currData-1)->fAlpha
161 + (nextData+1)->fAlpha - (nextData-1)->fAlpha;
162 currGrad.fY = (nextData-1)->fAlpha - (prevData-1)->fAlpha
163 + SK_ScalarSqrt2*nextData->fAlpha
164 - SK_ScalarSqrt2*prevData->fAlpha
165 + (nextData+1)->fAlpha - (prevData+1)->fAlpha;
166 currGrad.setLengthFast(1.0f);
168 // init squared distance to edge and distance vector
169 float dist = edge_distance(currGrad, currData->fAlpha);
170 currGrad.scale(dist, &currData->fDistVector);
171 currData->fDistSq = dist*dist;
172 } else {
173 // init distance to "far away"
174 currData->fDistSq = 2000000.f;
175 currData->fDistVector.fX = 1000.f;
176 currData->fDistVector.fY = 1000.f;
177 }
178 ++currData;
179 ++prevData;
180 ++nextData;
181 ++edges;
182 }
183 }
184 }
186 // Danielsson's 8SSEDT
188 // first stage forward pass
189 // (forward in Y, forward in X)
190 static void F1(DFData* curr, int width) {
191 // upper left
192 DFData* check = curr - width-1;
193 SkPoint distVec = check->fDistVector;
194 float distSq = check->fDistSq - 2.0f*(distVec.fX + distVec.fY - 1.0f);
195 if (distSq < curr->fDistSq) {
196 distVec.fX -= 1.0f;
197 distVec.fY -= 1.0f;
198 curr->fDistSq = distSq;
199 curr->fDistVector = distVec;
200 }
202 // up
203 check = curr - width;
204 distVec = check->fDistVector;
205 distSq = check->fDistSq - 2.0f*distVec.fY + 1.0f;
206 if (distSq < curr->fDistSq) {
207 distVec.fY -= 1.0f;
208 curr->fDistSq = distSq;
209 curr->fDistVector = distVec;
210 }
212 // upper right
213 check = curr - width+1;
214 distVec = check->fDistVector;
215 distSq = check->fDistSq + 2.0f*(distVec.fX - distVec.fY + 1.0f);
216 if (distSq < curr->fDistSq) {
217 distVec.fX += 1.0f;
218 distVec.fY -= 1.0f;
219 curr->fDistSq = distSq;
220 curr->fDistVector = distVec;
221 }
223 // left
224 check = curr - 1;
225 distVec = check->fDistVector;
226 distSq = check->fDistSq - 2.0f*distVec.fX + 1.0f;
227 if (distSq < curr->fDistSq) {
228 distVec.fX -= 1.0f;
229 curr->fDistSq = distSq;
230 curr->fDistVector = distVec;
231 }
232 }
234 // second stage forward pass
235 // (forward in Y, backward in X)
236 static void F2(DFData* curr, int width) {
237 // right
238 DFData* check = curr + 1;
239 float distSq = check->fDistSq;
240 SkPoint distVec = check->fDistVector;
241 distSq = check->fDistSq + 2.0f*distVec.fX + 1.0f;
242 if (distSq < curr->fDistSq) {
243 distVec.fX += 1.0f;
244 curr->fDistSq = distSq;
245 curr->fDistVector = distVec;
246 }
247 }
249 // first stage backward pass
250 // (backward in Y, forward in X)
251 static void B1(DFData* curr, int width) {
252 // left
253 DFData* check = curr - 1;
254 SkPoint distVec = check->fDistVector;
255 float distSq = check->fDistSq - 2.0f*distVec.fX + 1.0f;
256 if (distSq < curr->fDistSq) {
257 distVec.fX -= 1.0f;
258 curr->fDistSq = distSq;
259 curr->fDistVector = distVec;
260 }
261 }
263 // second stage backward pass
264 // (backward in Y, backwards in X)
265 static void B2(DFData* curr, int width) {
266 // right
267 DFData* check = curr + 1;
268 SkPoint distVec = check->fDistVector;
269 float distSq = check->fDistSq + 2.0f*distVec.fX + 1.0f;
270 if (distSq < curr->fDistSq) {
271 distVec.fX += 1.0f;
272 curr->fDistSq = distSq;
273 curr->fDistVector = distVec;
274 }
276 // bottom left
277 check = curr + width-1;
278 distVec = check->fDistVector;
279 distSq = check->fDistSq - 2.0f*(distVec.fX - distVec.fY - 1.0f);
280 if (distSq < curr->fDistSq) {
281 distVec.fX -= 1.0f;
282 distVec.fY += 1.0f;
283 curr->fDistSq = distSq;
284 curr->fDistVector = distVec;
285 }
287 // bottom
288 check = curr + width;
289 distVec = check->fDistVector;
290 distSq = check->fDistSq + 2.0f*distVec.fY + 1.0f;
291 if (distSq < curr->fDistSq) {
292 distVec.fY += 1.0f;
293 curr->fDistSq = distSq;
294 curr->fDistVector = distVec;
295 }
297 // bottom right
298 check = curr + width+1;
299 distVec = check->fDistVector;
300 distSq = check->fDistSq + 2.0f*(distVec.fX + distVec.fY + 1.0f);
301 if (distSq < curr->fDistSq) {
302 distVec.fX += 1.0f;
303 distVec.fY += 1.0f;
304 curr->fDistSq = distSq;
305 curr->fDistVector = distVec;
306 }
307 }
309 // enable this to output edge data rather than the distance field
310 #define DUMP_EDGE 0
312 #if !DUMP_EDGE
313 static unsigned char pack_distance_field_val(float dist, float distanceMagnitude) {
314 if (dist <= -distanceMagnitude) {
315 return 255;
316 } else if (dist > distanceMagnitude) {
317 return 0;
318 } else {
319 return (unsigned char)((distanceMagnitude-dist)*128.0f/distanceMagnitude);
320 }
321 }
322 #endif
324 // assumes an 8-bit image and distance field
325 bool SkGenerateDistanceFieldFromImage(unsigned char* distanceField,
326 const unsigned char* image,
327 int width, int height,
328 int distanceMagnitude) {
329 SkASSERT(NULL != distanceField);
330 SkASSERT(NULL != image);
332 // the final distance field will have additional texels on each side to handle
333 // the maximum distance
334 // we expand our temp data by one more on each side to simplify
335 // the scanning code -- will always be treated as infinitely far away
336 int pad = distanceMagnitude+1;
338 // set params for distance field data
339 int dataWidth = width + 2*pad;
340 int dataHeight = height + 2*pad;
342 // create temp data
343 size_t dataSize = dataWidth*dataHeight*sizeof(DFData);
344 SkAutoSMalloc<1024> dfStorage(dataSize);
345 DFData* dataPtr = (DFData*) dfStorage.get();
346 sk_bzero(dataPtr, dataSize);
348 SkAutoSMalloc<1024> edgeStorage(dataWidth*dataHeight*sizeof(char));
349 unsigned char* edgePtr = (unsigned char*) edgeStorage.get();
350 sk_bzero(edgePtr, dataWidth*dataHeight*sizeof(char));
352 // copy glyph into distance field storage
353 init_glyph_data(dataPtr, edgePtr, image,
354 dataWidth, dataHeight,
355 width, height, pad);
357 // create initial distance data, particularly at edges
358 init_distances(dataPtr, edgePtr, dataWidth, dataHeight);
360 // now perform Euclidean distance transform to propagate distances
362 // forwards in y
363 DFData* currData = dataPtr+dataWidth+1; // skip outer buffer
364 unsigned char* currEdge = edgePtr+dataWidth+1;
365 for (int j = 1; j < dataHeight-1; ++j) {
366 // forwards in x
367 for (int i = 1; i < dataWidth-1; ++i) {
368 // don't need to calculate distance for edge pixels
369 if (!*currEdge) {
370 F1(currData, dataWidth);
371 }
372 ++currData;
373 ++currEdge;
374 }
376 // backwards in x
377 --currData; // reset to end
378 --currEdge;
379 for (int i = 1; i < dataWidth-1; ++i) {
380 // don't need to calculate distance for edge pixels
381 if (!*currEdge) {
382 F2(currData, dataWidth);
383 }
384 --currData;
385 --currEdge;
386 }
388 currData += dataWidth+1;
389 currEdge += dataWidth+1;
390 }
392 // backwards in y
393 currData = dataPtr+dataWidth*(dataHeight-2) - 1; // skip outer buffer
394 currEdge = edgePtr+dataWidth*(dataHeight-2) - 1;
395 for (int j = 1; j < dataHeight-1; ++j) {
396 // forwards in x
397 for (int i = 1; i < dataWidth-1; ++i) {
398 // don't need to calculate distance for edge pixels
399 if (!*currEdge) {
400 B1(currData, dataWidth);
401 }
402 ++currData;
403 ++currEdge;
404 }
406 // backwards in x
407 --currData; // reset to end
408 --currEdge;
409 for (int i = 1; i < dataWidth-1; ++i) {
410 // don't need to calculate distance for edge pixels
411 if (!*currEdge) {
412 B2(currData, dataWidth);
413 }
414 --currData;
415 --currEdge;
416 }
418 currData -= dataWidth-1;
419 currEdge -= dataWidth-1;
420 }
422 // copy results to final distance field data
423 currData = dataPtr + dataWidth+1;
424 currEdge = edgePtr + dataWidth+1;
425 unsigned char *dfPtr = distanceField;
426 for (int j = 1; j < dataHeight-1; ++j) {
427 for (int i = 1; i < dataWidth-1; ++i) {
428 #if DUMP_EDGE
429 unsigned char val = sk_float_round2int(255*currData->fAlpha);
430 if (*currEdge) {
431 val = 128;
432 }
433 *dfPtr++ = val;
434 #else
435 float dist;
436 if (currData->fAlpha > 0.5f) {
437 dist = -SkScalarSqrt(currData->fDistSq);
438 } else {
439 dist = SkScalarSqrt(currData->fDistSq);
440 }
441 *dfPtr++ = pack_distance_field_val(dist, (float)distanceMagnitude);
442 #endif
443 ++currData;
444 ++currEdge;
445 }
446 currData += 2;
447 currEdge += 2;
448 }
450 return true;
451 }
