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 |