1 | /**************************************************************************** |
2 | * |
3 | * ftbsdf.c |
4 | * |
5 | * Signed Distance Field support for bitmap fonts (body only). |
6 | * |
7 | * Copyright (C) 2020-2023 by |
8 | * David Turner, Robert Wilhelm, and Werner Lemberg. |
9 | * |
10 | * Written by Anuj Verma. |
11 | * |
12 | * This file is part of the FreeType project, and may only be used, |
13 | * modified, and distributed under the terms of the FreeType project |
14 | * license, LICENSE.TXT. By continuing to use, modify, or distribute |
15 | * this file you indicate that you have read the license and |
16 | * understand and accept it fully. |
17 | * |
18 | */ |
19 | |
20 | |
21 | #include <freetype/internal/ftobjs.h> |
22 | #include <freetype/internal/ftdebug.h> |
23 | #include <freetype/internal/ftmemory.h> |
24 | #include <freetype/fttrigon.h> |
25 | |
26 | #include "ftsdf.h" |
27 | #include "ftsdferrs.h" |
28 | #include "ftsdfcommon.h" |
29 | |
30 | |
31 | /************************************************************************** |
32 | * |
33 | * A brief technical overview of how the BSDF rasterizer works |
34 | * ----------------------------------------------------------- |
35 | * |
36 | * [Notes]: |
37 | * * SDF stands for Signed Distance Field everywhere. |
38 | * |
39 | * * BSDF stands for Bitmap to Signed Distance Field rasterizer. |
40 | * |
41 | * * This renderer converts rasterized bitmaps to SDF. There is another |
42 | * renderer called 'sdf', which generates SDF directly from outlines; |
43 | * see file `ftsdf.c` for more. |
44 | * |
45 | * * The idea of generating SDF from bitmaps is taken from two research |
46 | * papers, where one is dependent on the other: |
47 | * |
48 | * - Per-Erik Danielsson: Euclidean Distance Mapping |
49 | * http://webstaff.itn.liu.se/~stegu/JFA/Danielsson.pdf |
50 | * |
51 | * From this paper we use the eight-point sequential Euclidean |
52 | * distance mapping (8SED). This is the heart of the process used |
53 | * in this rasterizer. |
54 | * |
55 | * - Stefan Gustavson, Robin Strand: Anti-aliased Euclidean distance transform. |
56 | * http://weber.itn.liu.se/~stegu/aadist/edtaa_preprint.pdf |
57 | * |
58 | * The original 8SED algorithm discards the pixels' alpha values, |
59 | * which can contain information about the actual outline of the |
60 | * glyph. This paper takes advantage of those alpha values and |
61 | * approximates outline pretty accurately. |
62 | * |
63 | * * This rasterizer also works for monochrome bitmaps. However, the |
64 | * result is not as accurate since we don't have any way to |
65 | * approximate outlines from binary bitmaps. |
66 | * |
67 | * ======================================================================== |
68 | * |
69 | * Generating SDF from bitmap is done in several steps. |
70 | * |
71 | * (1) The only information we have is the bitmap itself. It can |
72 | * be monochrome or anti-aliased. If it is anti-aliased, pixel values |
73 | * are nothing but coverage values. These coverage values can be used |
74 | * to extract information about the outline of the image. For |
75 | * example, if the pixel's alpha value is 0.5, then we can safely |
76 | * assume that the outline passes through the center of the pixel. |
77 | * |
78 | * (2) Find edge pixels in the bitmap (see `bsdf_is_edge` for more). For |
79 | * all edge pixels we use the Anti-aliased Euclidean distance |
80 | * transform algorithm and compute approximate edge distances (see |
81 | * `compute_edge_distance` and/or the second paper for more). |
82 | * |
83 | * (3) Now that we have computed approximate distances for edge pixels we |
84 | * use the 8SED algorithm to basically sweep the entire bitmap and |
85 | * compute distances for the rest of the pixels. (Since the algorithm |
86 | * is pretty convoluted it is only explained briefly in a comment to |
87 | * function `edt8`. To see the actual algorithm refer to the first |
88 | * paper.) |
89 | * |
90 | * (4) Finally, compute the sign for each pixel. This is done in function |
91 | * `finalize_sdf`. The basic idea is that if a pixel's original |
92 | * alpha/coverage value is greater than 0.5 then it is 'inside' (and |
93 | * 'outside' otherwise). |
94 | * |
95 | * Pseudo Code: |
96 | * |
97 | * ``` |
98 | * b = source bitmap; |
99 | * t = target bitmap; |
100 | * dm = list of distances; // dimension equal to b |
101 | * |
102 | * foreach grid_point (x, y) in b: |
103 | * { |
104 | * if (is_edge(x, y)): |
105 | * dm = approximate_edge_distance(b, x, y); |
106 | * |
107 | * // do the 8SED on the distances |
108 | * edt8(dm); |
109 | * |
110 | * // determine the signs |
111 | * determine_signs(dm): |
112 | * |
113 | * // copy SDF data to the target bitmap |
114 | * copy(dm to t); |
115 | * } |
116 | * |
117 | */ |
118 | |
119 | |
120 | /************************************************************************** |
121 | * |
122 | * The macro FT_COMPONENT is used in trace mode. It is an implicit |
123 | * parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log |
124 | * messages during execution. |
125 | */ |
126 | #undef FT_COMPONENT |
127 | #define FT_COMPONENT bsdf |
128 | |
129 | |
130 | /************************************************************************** |
131 | * |
132 | * useful macros |
133 | * |
134 | */ |
135 | |
136 | #define ONE 65536 /* 1 in 16.16 */ |
137 | |
138 | |
139 | /************************************************************************** |
140 | * |
141 | * structs |
142 | * |
143 | */ |
144 | |
145 | |
146 | /************************************************************************** |
147 | * |
148 | * @Struct: |
149 | * BSDF_TRaster |
150 | * |
151 | * @Description: |
152 | * This struct is used in place of @FT_Raster and is stored within the |
153 | * internal FreeType renderer struct. While rasterizing this is passed |
154 | * to the @FT_Raster_RenderFunc function, which then can be used however |
155 | * we want. |
156 | * |
157 | * @Fields: |
158 | * memory :: |
159 | * Used internally to allocate intermediate memory while raterizing. |
160 | * |
161 | */ |
162 | typedef struct BSDF_TRaster_ |
163 | { |
164 | FT_Memory memory; |
165 | |
166 | } BSDF_TRaster, *BSDF_PRaster; |
167 | |
168 | |
169 | /************************************************************************** |
170 | * |
171 | * @Struct: |
172 | * ED |
173 | * |
174 | * @Description: |
175 | * Euclidean distance. It gets used for Euclidean distance transforms; |
176 | * it can also be interpreted as an edge distance. |
177 | * |
178 | * @Fields: |
179 | * dist :: |
180 | * Vector length of the `prox` parameter. Can be squared or absolute |
181 | * depending on the `USE_SQUARED_DISTANCES` macro defined in file |
182 | * `ftsdfcommon.h`. |
183 | * |
184 | * prox :: |
185 | * Vector to the nearest edge. Can also be interpreted as shortest |
186 | * distance of a point. |
187 | * |
188 | * alpha :: |
189 | * Alpha value of the original bitmap from which we generate SDF. |
190 | * Needed for computing the gradient and determining the proper sign |
191 | * of a pixel. |
192 | * |
193 | */ |
194 | typedef struct ED_ |
195 | { |
196 | FT_16D16 dist; |
197 | FT_16D16_Vec prox; |
198 | FT_Byte alpha; |
199 | |
200 | } ED; |
201 | |
202 | |
203 | /************************************************************************** |
204 | * |
205 | * @Struct: |
206 | * BSDF_Worker |
207 | * |
208 | * @Description: |
209 | * A convenience struct that is passed to functions while generating |
210 | * SDF; most of those functions require the same parameters. |
211 | * |
212 | * @Fields: |
213 | * distance_map :: |
214 | * A one-dimensional array that gets interpreted as two-dimensional |
215 | * one. It contains the Euclidean distances of all points of the |
216 | * bitmap. |
217 | * |
218 | * width :: |
219 | * Width of the above `distance_map`. |
220 | * |
221 | * rows :: |
222 | * Number of rows in the above `distance_map`. |
223 | * |
224 | * params :: |
225 | * Internal parameters and properties required by the rasterizer. See |
226 | * file `ftsdf.h` for more. |
227 | * |
228 | */ |
229 | typedef struct BSDF_Worker_ |
230 | { |
231 | ED* distance_map; |
232 | |
233 | FT_Int width; |
234 | FT_Int rows; |
235 | |
236 | SDF_Raster_Params params; |
237 | |
238 | } BSDF_Worker; |
239 | |
240 | |
241 | /************************************************************************** |
242 | * |
243 | * initializer |
244 | * |
245 | */ |
246 | |
247 | static const ED zero_ed = { 0, { 0, 0 }, 0 }; |
248 | |
249 | |
250 | /************************************************************************** |
251 | * |
252 | * rasterizer functions |
253 | * |
254 | */ |
255 | |
256 | /************************************************************************** |
257 | * |
258 | * @Function: |
259 | * bsdf_is_edge |
260 | * |
261 | * @Description: |
262 | * Check whether a pixel is an edge pixel, i.e., whether it is |
263 | * surrounded by a completely black pixel (zero alpha), and the current |
264 | * pixel is not a completely black pixel. |
265 | * |
266 | * @Input: |
267 | * dm :: |
268 | * Array of distances. The parameter must point to the current |
269 | * pixel, i.e., the pixel that is to be checked for being an edge. |
270 | * |
271 | * x :: |
272 | * The x position of the current pixel. |
273 | * |
274 | * y :: |
275 | * The y position of the current pixel. |
276 | * |
277 | * w :: |
278 | * Width of the bitmap. |
279 | * |
280 | * r :: |
281 | * Number of rows in the bitmap. |
282 | * |
283 | * @Return: |
284 | * 1~if the current pixel is an edge pixel, 0~otherwise. |
285 | * |
286 | */ |
287 | |
288 | #ifdef CHECK_NEIGHBOR |
289 | #undef CHECK_NEIGHBOR |
290 | #endif |
291 | |
292 | #define CHECK_NEIGHBOR( x_offset, y_offset ) \ |
293 | do \ |
294 | { \ |
295 | if ( x + x_offset >= 0 && x + x_offset < w && \ |
296 | y + y_offset >= 0 && y + y_offset < r ) \ |
297 | { \ |
298 | num_neighbors++; \ |
299 | \ |
300 | to_check = dm + y_offset * w + x_offset; \ |
301 | if ( to_check->alpha == 0 ) \ |
302 | { \ |
303 | is_edge = 1; \ |
304 | goto Done; \ |
305 | } \ |
306 | } \ |
307 | } while ( 0 ) |
308 | |
309 | static FT_Bool |
310 | bsdf_is_edge( ED* dm, /* distance map */ |
311 | FT_Int x, /* x index of point to check */ |
312 | FT_Int y, /* y index of point to check */ |
313 | FT_Int w, /* width */ |
314 | FT_Int r ) /* rows */ |
315 | { |
316 | FT_Bool is_edge = 0; |
317 | ED* to_check = NULL; |
318 | FT_Int num_neighbors = 0; |
319 | |
320 | |
321 | if ( dm->alpha == 0 ) |
322 | goto Done; |
323 | |
324 | if ( dm->alpha > 0 && dm->alpha < 255 ) |
325 | { |
326 | is_edge = 1; |
327 | goto Done; |
328 | } |
329 | |
330 | /* up */ |
331 | CHECK_NEIGHBOR( 0, -1 ); |
332 | |
333 | /* down */ |
334 | CHECK_NEIGHBOR( 0, 1 ); |
335 | |
336 | /* left */ |
337 | CHECK_NEIGHBOR( -1, 0 ); |
338 | |
339 | /* right */ |
340 | CHECK_NEIGHBOR( 1, 0 ); |
341 | |
342 | /* up left */ |
343 | CHECK_NEIGHBOR( -1, -1 ); |
344 | |
345 | /* up right */ |
346 | CHECK_NEIGHBOR( 1, -1 ); |
347 | |
348 | /* down left */ |
349 | CHECK_NEIGHBOR( -1, 1 ); |
350 | |
351 | /* down right */ |
352 | CHECK_NEIGHBOR( 1, 1 ); |
353 | |
354 | if ( num_neighbors != 8 ) |
355 | is_edge = 1; |
356 | |
357 | Done: |
358 | return is_edge; |
359 | } |
360 | |
361 | #undef CHECK_NEIGHBOR |
362 | |
363 | |
364 | /************************************************************************** |
365 | * |
366 | * @Function: |
367 | * compute_edge_distance |
368 | * |
369 | * @Description: |
370 | * Approximate the outline and compute the distance from `current` |
371 | * to the approximated outline. |
372 | * |
373 | * @Input: |
374 | * current :: |
375 | * Array of Euclidean distances. `current` must point to the position |
376 | * for which the distance is to be caculated. We treat this array as |
377 | * a two-dimensional array mapped to a one-dimensional array. |
378 | * |
379 | * x :: |
380 | * The x coordinate of the `current` parameter in the array. |
381 | * |
382 | * y :: |
383 | * The y coordinate of the `current` parameter in the array. |
384 | * |
385 | * w :: |
386 | * The width of the distances array. |
387 | * |
388 | * r :: |
389 | * Number of rows in the distances array. |
390 | * |
391 | * @Return: |
392 | * A vector pointing to the approximate edge distance. |
393 | * |
394 | * @Note: |
395 | * This is a computationally expensive function. Try to reduce the |
396 | * number of calls to this function. Moreover, this must only be used |
397 | * for edge pixel positions. |
398 | * |
399 | */ |
400 | static FT_16D16_Vec |
401 | compute_edge_distance( ED* current, |
402 | FT_Int x, |
403 | FT_Int y, |
404 | FT_Int w, |
405 | FT_Int r ) |
406 | { |
407 | /* |
408 | * This function, based on the paper presented by Stefan Gustavson and |
409 | * Robin Strand, gets used to approximate edge distances from |
410 | * anti-aliased bitmaps. |
411 | * |
412 | * The algorithm is as follows. |
413 | * |
414 | * (1) In anti-aliased images, the pixel's alpha value is the coverage |
415 | * of the pixel by the outline. For example, if the alpha value is |
416 | * 0.5f we can assume that the outline passes through the center of |
417 | * the pixel. |
418 | * |
419 | * (2) For this reason we can use that alpha value to approximate the real |
420 | * distance of the pixel to edge pretty accurately. A simple |
421 | * approximation is `(0.5f - alpha)`, assuming that the outline is |
422 | * parallel to the x or y~axis. However, in this algorithm we use a |
423 | * different approximation which is quite accurate even for |
424 | * non-axis-aligned edges. |
425 | * |
426 | * (3) The only remaining piece of information that we cannot |
427 | * approximate directly from the alpha is the direction of the edge. |
428 | * This is where we use Sobel's operator to compute the gradient of |
429 | * the pixel. The gradient give us a pretty good approximation of |
430 | * the edge direction. We use a 3x3 kernel filter to compute the |
431 | * gradient. |
432 | * |
433 | * (4) After the above two steps we have both the direction and the |
434 | * distance to the edge which is used to generate the Signed |
435 | * Distance Field. |
436 | * |
437 | * References: |
438 | * |
439 | * - Anti-Aliased Euclidean Distance Transform: |
440 | * http://weber.itn.liu.se/~stegu/aadist/edtaa_preprint.pdf |
441 | * - Sobel Operator: |
442 | * https://en.wikipedia.org/wiki/Sobel_operator |
443 | */ |
444 | |
445 | FT_16D16_Vec g = { 0, 0 }; |
446 | FT_16D16 dist, current_alpha; |
447 | FT_16D16 a1, temp; |
448 | FT_16D16 gx, gy; |
449 | FT_16D16 alphas[9]; |
450 | |
451 | |
452 | /* Since our spread cannot be 0, this condition */ |
453 | /* can never be true. */ |
454 | if ( x <= 0 || x >= w - 1 || |
455 | y <= 0 || y >= r - 1 ) |
456 | return g; |
457 | |
458 | /* initialize the alphas */ |
459 | alphas[0] = 256 * (FT_16D16)current[-w - 1].alpha; |
460 | alphas[1] = 256 * (FT_16D16)current[-w ].alpha; |
461 | alphas[2] = 256 * (FT_16D16)current[-w + 1].alpha; |
462 | alphas[3] = 256 * (FT_16D16)current[ -1].alpha; |
463 | alphas[4] = 256 * (FT_16D16)current[ 0].alpha; |
464 | alphas[5] = 256 * (FT_16D16)current[ 1].alpha; |
465 | alphas[6] = 256 * (FT_16D16)current[ w - 1].alpha; |
466 | alphas[7] = 256 * (FT_16D16)current[ w ].alpha; |
467 | alphas[8] = 256 * (FT_16D16)current[ w + 1].alpha; |
468 | |
469 | current_alpha = alphas[4]; |
470 | |
471 | /* Compute the gradient using the Sobel operator. */ |
472 | /* In this case we use the following 3x3 filters: */ |
473 | /* */ |
474 | /* For x: | -1 0 -1 | */ |
475 | /* | -root(2) 0 root(2) | */ |
476 | /* | -1 0 1 | */ |
477 | /* */ |
478 | /* For y: | -1 -root(2) -1 | */ |
479 | /* | 0 0 0 | */ |
480 | /* | 1 root(2) 1 | */ |
481 | /* */ |
482 | /* [Note]: 92681 is root(2) in 16.16 format. */ |
483 | g.x = -alphas[0] - |
484 | FT_MulFix( alphas[3], 92681 ) - |
485 | alphas[6] + |
486 | alphas[2] + |
487 | FT_MulFix( alphas[5], 92681 ) + |
488 | alphas[8]; |
489 | |
490 | g.y = -alphas[0] - |
491 | FT_MulFix( alphas[1], 92681 ) - |
492 | alphas[2] + |
493 | alphas[6] + |
494 | FT_MulFix( alphas[7], 92681 ) + |
495 | alphas[8]; |
496 | |
497 | FT_Vector_NormLen( &g ); |
498 | |
499 | /* The gradient gives us the direction of the */ |
500 | /* edge for the current pixel. Once we have the */ |
501 | /* approximate direction of the edge, we can */ |
502 | /* approximate the edge distance much better. */ |
503 | |
504 | if ( g.x == 0 || g.y == 0 ) |
505 | dist = ONE / 2 - alphas[4]; |
506 | else |
507 | { |
508 | gx = g.x; |
509 | gy = g.y; |
510 | |
511 | gx = FT_ABS( gx ); |
512 | gy = FT_ABS( gy ); |
513 | |
514 | if ( gx < gy ) |
515 | { |
516 | temp = gx; |
517 | gx = gy; |
518 | gy = temp; |
519 | } |
520 | |
521 | a1 = FT_DivFix( gy, gx ) / 2; |
522 | |
523 | if ( current_alpha < a1 ) |
524 | dist = ( gx + gy ) / 2 - |
525 | square_root( 2 * FT_MulFix( gx, |
526 | FT_MulFix( gy, |
527 | current_alpha ) ) ); |
528 | |
529 | else if ( current_alpha < ( ONE - a1 ) ) |
530 | dist = FT_MulFix( ONE / 2 - current_alpha, gx ); |
531 | |
532 | else |
533 | dist = -( gx + gy ) / 2 + |
534 | square_root( 2 * FT_MulFix( gx, |
535 | FT_MulFix( gy, |
536 | ONE - current_alpha ) ) ); |
537 | } |
538 | |
539 | g.x = FT_MulFix( g.x, dist ); |
540 | g.y = FT_MulFix( g.y, dist ); |
541 | |
542 | return g; |
543 | } |
544 | |
545 | |
546 | /************************************************************************** |
547 | * |
548 | * @Function: |
549 | * bsdf_approximate_edge |
550 | * |
551 | * @Description: |
552 | * Loops over all the pixels and call `compute_edge_distance` only for |
553 | * edge pixels. This maked the process a lot faster since |
554 | * `compute_edge_distance` uses functions such as `FT_Vector_NormLen', |
555 | * which are quite slow. |
556 | * |
557 | * @InOut: |
558 | * worker :: |
559 | * Contains the distance map as well as all the relevant parameters |
560 | * required by the function. |
561 | * |
562 | * @Return: |
563 | * FreeType error, 0 means success. |
564 | * |
565 | * @Note: |
566 | * The function directly manipulates `worker->distance_map`. |
567 | * |
568 | */ |
569 | static FT_Error |
570 | bsdf_approximate_edge( BSDF_Worker* worker ) |
571 | { |
572 | FT_Error error = FT_Err_Ok; |
573 | FT_Int i, j; |
574 | FT_Int index; |
575 | ED* ed; |
576 | |
577 | |
578 | if ( !worker || !worker->distance_map ) |
579 | { |
580 | error = FT_THROW( Invalid_Argument ); |
581 | goto Exit; |
582 | } |
583 | |
584 | ed = worker->distance_map; |
585 | |
586 | for ( j = 0; j < worker->rows; j++ ) |
587 | { |
588 | for ( i = 0; i < worker->width; i++ ) |
589 | { |
590 | index = j * worker->width + i; |
591 | |
592 | if ( bsdf_is_edge( worker->distance_map + index, |
593 | i, j, |
594 | worker->width, |
595 | worker->rows ) ) |
596 | { |
597 | /* approximate the edge distance for edge pixels */ |
598 | ed[index].prox = compute_edge_distance( ed + index, |
599 | i, j, |
600 | worker->width, |
601 | worker->rows ); |
602 | ed[index].dist = VECTOR_LENGTH_16D16( ed[index].prox ); |
603 | } |
604 | else |
605 | { |
606 | /* for non-edge pixels assign far away distances */ |
607 | ed[index].dist = 400 * ONE; |
608 | ed[index].prox.x = 200 * ONE; |
609 | ed[index].prox.y = 200 * ONE; |
610 | } |
611 | } |
612 | } |
613 | |
614 | Exit: |
615 | return error; |
616 | } |
617 | |
618 | |
619 | /************************************************************************** |
620 | * |
621 | * @Function: |
622 | * bsdf_init_distance_map |
623 | * |
624 | * @Description: |
625 | * Initialize the distance map according to the '8-point sequential |
626 | * Euclidean distance mapping' (8SED) algorithm. Basically it copies |
627 | * the `source` bitmap alpha values to the `distance_map->alpha` |
628 | * parameter of `worker`. |
629 | * |
630 | * @Input: |
631 | * source :: |
632 | * Source bitmap to copy the data from. |
633 | * |
634 | * @Output: |
635 | * worker :: |
636 | * Target distance map to copy the data to. |
637 | * |
638 | * @Return: |
639 | * FreeType error, 0 means success. |
640 | * |
641 | */ |
642 | static FT_Error |
643 | bsdf_init_distance_map( const FT_Bitmap* source, |
644 | BSDF_Worker* worker ) |
645 | { |
646 | FT_Error error = FT_Err_Ok; |
647 | |
648 | FT_Int x_diff, y_diff; |
649 | FT_Int t_i, t_j, s_i, s_j; |
650 | FT_Byte* s; |
651 | ED* t; |
652 | |
653 | |
654 | /* again check the parameters (probably unnecessary) */ |
655 | if ( !source || !worker ) |
656 | { |
657 | error = FT_THROW( Invalid_Argument ); |
658 | goto Exit; |
659 | } |
660 | |
661 | /* Because of the way we convert a bitmap to SDF, */ |
662 | /* i.e., aligning the source to the center of the */ |
663 | /* target, the target's width and rows must be */ |
664 | /* checked before copying. */ |
665 | if ( worker->width < (FT_Int)source->width || |
666 | worker->rows < (FT_Int)source->rows ) |
667 | { |
668 | error = FT_THROW( Invalid_Argument ); |
669 | goto Exit; |
670 | } |
671 | |
672 | /* check pixel mode */ |
673 | if ( source->pixel_mode == FT_PIXEL_MODE_NONE ) |
674 | { |
675 | FT_ERROR(( "bsdf_copy_source_to_target:" |
676 | " Invalid pixel mode of source bitmap" )); |
677 | error = FT_THROW( Invalid_Argument ); |
678 | goto Exit; |
679 | } |
680 | |
681 | #ifdef FT_DEBUG_LEVEL_TRACE |
682 | if ( source->pixel_mode == FT_PIXEL_MODE_MONO ) |
683 | { |
684 | FT_TRACE0(( "bsdf_copy_source_to_target:" |
685 | " The `bsdf' renderer can convert monochrome\n" )); |
686 | FT_TRACE0(( " " |
687 | " bitmaps to SDF but the results are not perfect\n" )); |
688 | FT_TRACE0(( " " |
689 | " because there is no way to approximate actual\n" )); |
690 | FT_TRACE0(( " " |
691 | " outlines from monochrome bitmaps. Consider\n" )); |
692 | FT_TRACE0(( " " |
693 | " using an anti-aliased bitmap instead.\n" )); |
694 | } |
695 | #endif |
696 | |
697 | /* Calculate the width and row differences */ |
698 | /* between target and source. */ |
699 | x_diff = worker->width - (int)source->width; |
700 | y_diff = worker->rows - (int)source->rows; |
701 | |
702 | x_diff /= 2; |
703 | y_diff /= 2; |
704 | |
705 | t = (ED*)worker->distance_map; |
706 | s = source->buffer; |
707 | |
708 | /* For now we only support pixel mode `FT_PIXEL_MODE_MONO` */ |
709 | /* and `FT_PIXEL_MODE_GRAY`. More will be added later. */ |
710 | /* */ |
711 | /* [NOTE]: We can also use @FT_Bitmap_Convert to convert */ |
712 | /* bitmap to 8bpp. To avoid extra allocation and */ |
713 | /* since the target bitmap can be 16bpp we manually */ |
714 | /* convert the source bitmap to the desired bpp. */ |
715 | |
716 | switch ( source->pixel_mode ) |
717 | { |
718 | case FT_PIXEL_MODE_MONO: |
719 | { |
720 | FT_Int t_width = worker->width; |
721 | FT_Int t_rows = worker->rows; |
722 | FT_Int s_width = (int)source->width; |
723 | FT_Int s_rows = (int)source->rows; |
724 | |
725 | |
726 | for ( t_j = 0; t_j < t_rows; t_j++ ) |
727 | { |
728 | for ( t_i = 0; t_i < t_width; t_i++ ) |
729 | { |
730 | FT_Int t_index = t_j * t_width + t_i; |
731 | FT_Int s_index; |
732 | FT_Int div, mod; |
733 | FT_Byte pixel, byte; |
734 | |
735 | |
736 | t[t_index] = zero_ed; |
737 | |
738 | s_i = t_i - x_diff; |
739 | s_j = t_j - y_diff; |
740 | |
741 | /* Assign 0 to padding similar to */ |
742 | /* the source bitmap. */ |
743 | if ( s_i < 0 || s_i >= s_width || |
744 | s_j < 0 || s_j >= s_rows ) |
745 | continue; |
746 | |
747 | if ( worker->params.flip_y ) |
748 | s_index = ( s_rows - s_j - 1 ) * source->pitch; |
749 | else |
750 | s_index = s_j * source->pitch; |
751 | |
752 | div = s_index + s_i / 8; |
753 | mod = 7 - s_i % 8; |
754 | |
755 | pixel = s[div]; |
756 | byte = (FT_Byte)( 1 << mod ); |
757 | |
758 | t[t_index].alpha = pixel & byte ? 255 : 0; |
759 | } |
760 | } |
761 | } |
762 | break; |
763 | |
764 | case FT_PIXEL_MODE_GRAY: |
765 | { |
766 | FT_Int t_width = worker->width; |
767 | FT_Int t_rows = worker->rows; |
768 | FT_Int s_width = (int)source->width; |
769 | FT_Int s_rows = (int)source->rows; |
770 | |
771 | |
772 | /* loop over all pixels and assign pixel values from source */ |
773 | for ( t_j = 0; t_j < t_rows; t_j++ ) |
774 | { |
775 | for ( t_i = 0; t_i < t_width; t_i++ ) |
776 | { |
777 | FT_Int t_index = t_j * t_width + t_i; |
778 | FT_Int s_index; |
779 | |
780 | |
781 | t[t_index] = zero_ed; |
782 | |
783 | s_i = t_i - x_diff; |
784 | s_j = t_j - y_diff; |
785 | |
786 | /* Assign 0 to padding similar to */ |
787 | /* the source bitmap. */ |
788 | if ( s_i < 0 || s_i >= s_width || |
789 | s_j < 0 || s_j >= s_rows ) |
790 | continue; |
791 | |
792 | if ( worker->params.flip_y ) |
793 | s_index = ( s_rows - s_j - 1 ) * s_width + s_i; |
794 | else |
795 | s_index = s_j * s_width + s_i; |
796 | |
797 | /* simply copy the alpha values */ |
798 | t[t_index].alpha = s[s_index]; |
799 | } |
800 | } |
801 | } |
802 | break; |
803 | |
804 | default: |
805 | FT_ERROR(( "bsdf_copy_source_to_target:" |
806 | " unsopported pixel mode of source bitmap\n" )); |
807 | |
808 | error = FT_THROW( Unimplemented_Feature ); |
809 | break; |
810 | } |
811 | |
812 | Exit: |
813 | return error; |
814 | } |
815 | |
816 | |
817 | /************************************************************************** |
818 | * |
819 | * @Function: |
820 | * compare_neighbor |
821 | * |
822 | * @Description: |
823 | * Compare neighbor pixel (which is defined by the offset) and update |
824 | * `current` distance if the new distance is shorter than the original. |
825 | * |
826 | * @Input: |
827 | * x_offset :: |
828 | * X offset of the neighbor to be checked. The offset is relative to |
829 | * the `current`. |
830 | * |
831 | * y_offset :: |
832 | * Y offset of the neighbor to be checked. The offset is relative to |
833 | * the `current`. |
834 | * |
835 | * width :: |
836 | * Width of the `current` array. |
837 | * |
838 | * @InOut: |
839 | * current :: |
840 | * Pointer into array of distances. This parameter must point to the |
841 | * position whose neighbor is to be checked. The array is treated as |
842 | * a two-dimensional array. |
843 | * |
844 | */ |
845 | static void |
846 | compare_neighbor( ED* current, |
847 | FT_Int x_offset, |
848 | FT_Int y_offset, |
849 | FT_Int width ) |
850 | { |
851 | ED* to_check; |
852 | FT_16D16 dist; |
853 | FT_16D16_Vec dist_vec; |
854 | |
855 | |
856 | to_check = current + ( y_offset * width ) + x_offset; |
857 | |
858 | /* |
859 | * While checking for the nearest point we first approximate the |
860 | * distance of `current` by adding the deviation (which is sqrt(2) at |
861 | * most). Only if the new value is less than the current value we |
862 | * calculate the actual distances using `FT_Vector_Length`. This last |
863 | * step can be omitted by using squared distances. |
864 | */ |
865 | |
866 | /* |
867 | * Approximate the distance. We subtract 1 to avoid precision errors, |
868 | * which could happen because the two directions can be opposite. |
869 | */ |
870 | dist = to_check->dist - ONE; |
871 | |
872 | if ( dist < current->dist ) |
873 | { |
874 | dist_vec = to_check->prox; |
875 | |
876 | dist_vec.x += x_offset * ONE; |
877 | dist_vec.y += y_offset * ONE; |
878 | dist = VECTOR_LENGTH_16D16( dist_vec ); |
879 | |
880 | if ( dist < current->dist ) |
881 | { |
882 | current->dist = dist; |
883 | current->prox = dist_vec; |
884 | } |
885 | } |
886 | } |
887 | |
888 | |
889 | /************************************************************************** |
890 | * |
891 | * @Function: |
892 | * first_pass |
893 | * |
894 | * @Description: |
895 | * First pass of the 8SED algorithm. Loop over the bitmap from top to |
896 | * bottom and scan each row left to right, updating the distances in |
897 | * `worker->distance_map`. |
898 | * |
899 | * @InOut: |
900 | * worker:: |
901 | * Contains all the relevant parameters. |
902 | * |
903 | */ |
904 | static void |
905 | first_pass( BSDF_Worker* worker ) |
906 | { |
907 | FT_Int i, j; /* iterators */ |
908 | FT_Int w, r; /* width, rows */ |
909 | ED* dm; /* distance map */ |
910 | |
911 | |
912 | dm = worker->distance_map; |
913 | w = worker->width; |
914 | r = worker->rows; |
915 | |
916 | /* Start scanning from top to bottom and sweep each */ |
917 | /* row back and forth comparing the distances of the */ |
918 | /* neighborhood. Leave the first row as it has no top */ |
919 | /* neighbor; it will be covered in the second scan of */ |
920 | /* the image (from bottom to top). */ |
921 | for ( j = 1; j < r; j++ ) |
922 | { |
923 | FT_Int index; |
924 | ED* current; |
925 | |
926 | |
927 | /* Forward pass of rows (left -> right). Leave the first */ |
928 | /* column, which gets covered in the backward pass. */ |
929 | for ( i = 1; i < w - 1; i++ ) |
930 | { |
931 | index = j * w + i; |
932 | current = dm + index; |
933 | |
934 | /* left-up */ |
935 | compare_neighbor( current, -1, -1, w ); |
936 | /* up */ |
937 | compare_neighbor( current, 0, -1, w ); |
938 | /* up-right */ |
939 | compare_neighbor( current, 1, -1, w ); |
940 | /* left */ |
941 | compare_neighbor( current, -1, 0, w ); |
942 | } |
943 | |
944 | /* Backward pass of rows (right -> left). Leave the last */ |
945 | /* column, which was already covered in the forward pass. */ |
946 | for ( i = w - 2; i >= 0; i-- ) |
947 | { |
948 | index = j * w + i; |
949 | current = dm + index; |
950 | |
951 | /* right */ |
952 | compare_neighbor( current, 1, 0, w ); |
953 | } |
954 | } |
955 | } |
956 | |
957 | |
958 | /************************************************************************** |
959 | * |
960 | * @Function: |
961 | * second_pass |
962 | * |
963 | * @Description: |
964 | * Second pass of the 8SED algorithm. Loop over the bitmap from bottom |
965 | * to top and scan each row left to right, updating the distances in |
966 | * `worker->distance_map`. |
967 | * |
968 | * @InOut: |
969 | * worker:: |
970 | * Contains all the relevant parameters. |
971 | * |
972 | */ |
973 | static void |
974 | second_pass( BSDF_Worker* worker ) |
975 | { |
976 | FT_Int i, j; /* iterators */ |
977 | FT_Int w, r; /* width, rows */ |
978 | ED* dm; /* distance map */ |
979 | |
980 | |
981 | dm = worker->distance_map; |
982 | w = worker->width; |
983 | r = worker->rows; |
984 | |
985 | /* Start scanning from bottom to top and sweep each */ |
986 | /* row back and forth comparing the distances of the */ |
987 | /* neighborhood. Leave the last row as it has no down */ |
988 | /* neighbor; it is already covered in the first scan */ |
989 | /* of the image (from top to bottom). */ |
990 | for ( j = r - 2; j >= 0; j-- ) |
991 | { |
992 | FT_Int index; |
993 | ED* current; |
994 | |
995 | |
996 | /* Forward pass of rows (left -> right). Leave the first */ |
997 | /* column, which gets covered in the backward pass. */ |
998 | for ( i = 1; i < w - 1; i++ ) |
999 | { |
1000 | index = j * w + i; |
1001 | current = dm + index; |
1002 | |
1003 | /* left-up */ |
1004 | compare_neighbor( current, -1, 1, w ); |
1005 | /* up */ |
1006 | compare_neighbor( current, 0, 1, w ); |
1007 | /* up-right */ |
1008 | compare_neighbor( current, 1, 1, w ); |
1009 | /* left */ |
1010 | compare_neighbor( current, -1, 0, w ); |
1011 | } |
1012 | |
1013 | /* Backward pass of rows (right -> left). Leave the last */ |
1014 | /* column, which was already covered in the forward pass. */ |
1015 | for ( i = w - 2; i >= 0; i-- ) |
1016 | { |
1017 | index = j * w + i; |
1018 | current = dm + index; |
1019 | |
1020 | /* right */ |
1021 | compare_neighbor( current, 1, 0, w ); |
1022 | } |
1023 | } |
1024 | } |
1025 | |
1026 | |
1027 | /************************************************************************** |
1028 | * |
1029 | * @Function: |
1030 | * edt8 |
1031 | * |
1032 | * @Description: |
1033 | * Compute the distance map of the a bitmap. Execute both first and |
1034 | * second pass of the 8SED algorithm. |
1035 | * |
1036 | * @InOut: |
1037 | * worker:: |
1038 | * Contains all the relevant parameters. |
1039 | * |
1040 | * @Return: |
1041 | * FreeType error, 0 means success. |
1042 | * |
1043 | */ |
1044 | static FT_Error |
1045 | edt8( BSDF_Worker* worker ) |
1046 | { |
1047 | FT_Error error = FT_Err_Ok; |
1048 | |
1049 | |
1050 | if ( !worker || !worker->distance_map ) |
1051 | { |
1052 | error = FT_THROW( Invalid_Argument ); |
1053 | goto Exit; |
1054 | } |
1055 | |
1056 | /* first scan of the image */ |
1057 | first_pass( worker ); |
1058 | |
1059 | /* second scan of the image */ |
1060 | second_pass( worker ); |
1061 | |
1062 | Exit: |
1063 | return error; |
1064 | } |
1065 | |
1066 | |
1067 | /************************************************************************** |
1068 | * |
1069 | * @Function: |
1070 | * finalize_sdf |
1071 | * |
1072 | * @Description: |
1073 | * Copy the SDF data from `worker->distance_map` to the `target` bitmap. |
1074 | * Also transform the data to output format, (which is 6.10 fixed-point |
1075 | * format at the moment). |
1076 | * |
1077 | * @Input: |
1078 | * worker :: |
1079 | * Contains source distance map and other SDF data. |
1080 | * |
1081 | * @Output: |
1082 | * target :: |
1083 | * Target bitmap to which the SDF data is copied to. |
1084 | * |
1085 | * @Return: |
1086 | * FreeType error, 0 means success. |
1087 | * |
1088 | */ |
1089 | static FT_Error |
1090 | finalize_sdf( BSDF_Worker* worker, |
1091 | const FT_Bitmap* target ) |
1092 | { |
1093 | FT_Error error = FT_Err_Ok; |
1094 | |
1095 | FT_Int w, r; |
1096 | FT_Int i, j; |
1097 | |
1098 | FT_SDFFormat* t_buffer; |
1099 | FT_16D16 sp_sq, spread; |
1100 | |
1101 | |
1102 | if ( !worker || !target ) |
1103 | { |
1104 | error = FT_THROW( Invalid_Argument ); |
1105 | goto Exit; |
1106 | } |
1107 | |
1108 | w = (int)target->width; |
1109 | r = (int)target->rows; |
1110 | t_buffer = (FT_SDFFormat*)target->buffer; |
1111 | |
1112 | if ( w != worker->width || |
1113 | r != worker->rows ) |
1114 | { |
1115 | error = FT_THROW( Invalid_Argument ); |
1116 | goto Exit; |
1117 | } |
1118 | |
1119 | spread = (FT_16D16)FT_INT_16D16( worker->params.spread ); |
1120 | |
1121 | #if USE_SQUARED_DISTANCES |
1122 | sp_sq = (FT_16D16)FT_INT_16D16( worker->params.spread * |
1123 | worker->params.spread ); |
1124 | #else |
1125 | sp_sq = (FT_16D16)FT_INT_16D16( worker->params.spread ); |
1126 | #endif |
1127 | |
1128 | for ( j = 0; j < r; j++ ) |
1129 | { |
1130 | for ( i = 0; i < w; i++ ) |
1131 | { |
1132 | FT_Int index; |
1133 | FT_16D16 dist; |
1134 | FT_SDFFormat final_dist; |
1135 | FT_Char sign; |
1136 | |
1137 | |
1138 | index = j * w + i; |
1139 | dist = worker->distance_map[index].dist; |
1140 | |
1141 | if ( dist < 0 || dist > sp_sq ) |
1142 | dist = sp_sq; |
1143 | |
1144 | #if USE_SQUARED_DISTANCES |
1145 | dist = square_root( dist ); |
1146 | #endif |
1147 | |
1148 | /* We assume that if the pixel is inside a contour */ |
1149 | /* its coverage value must be > 127. */ |
1150 | sign = worker->distance_map[index].alpha < 127 ? -1 : 1; |
1151 | |
1152 | /* flip the sign according to the property */ |
1153 | if ( worker->params.flip_sign ) |
1154 | sign = -sign; |
1155 | |
1156 | /* concatenate from 16.16 to appropriate format */ |
1157 | final_dist = map_fixed_to_sdf( dist * sign, spread ); |
1158 | |
1159 | t_buffer[index] = final_dist; |
1160 | } |
1161 | } |
1162 | |
1163 | Exit: |
1164 | return error; |
1165 | } |
1166 | |
1167 | |
1168 | /************************************************************************** |
1169 | * |
1170 | * interface functions |
1171 | * |
1172 | */ |
1173 | |
1174 | /* called when adding a new module through @FT_Add_Module */ |
1175 | static FT_Error |
1176 | bsdf_raster_new( void* memory_, /* FT_Memory */ |
1177 | FT_Raster* araster_ ) /* BSDF_PRaster* */ |
1178 | { |
1179 | FT_Memory memory = (FT_Memory)memory_; |
1180 | BSDF_PRaster* araster = (BSDF_PRaster*)araster_; |
1181 | |
1182 | FT_Error error; |
1183 | BSDF_PRaster raster = NULL; |
1184 | |
1185 | |
1186 | if ( !FT_NEW( raster ) ) |
1187 | raster->memory = memory; |
1188 | |
1189 | *araster = raster; |
1190 | |
1191 | return error; |
1192 | } |
1193 | |
1194 | |
1195 | /* unused */ |
1196 | static void |
1197 | bsdf_raster_reset( FT_Raster raster, |
1198 | unsigned char* pool_base, |
1199 | unsigned long pool_size ) |
1200 | { |
1201 | FT_UNUSED( raster ); |
1202 | FT_UNUSED( pool_base ); |
1203 | FT_UNUSED( pool_size ); |
1204 | } |
1205 | |
1206 | |
1207 | /* unused */ |
1208 | static FT_Error |
1209 | bsdf_raster_set_mode( FT_Raster raster, |
1210 | unsigned long mode, |
1211 | void* args ) |
1212 | { |
1213 | FT_UNUSED( raster ); |
1214 | FT_UNUSED( mode ); |
1215 | FT_UNUSED( args ); |
1216 | |
1217 | return FT_Err_Ok; |
1218 | } |
1219 | |
1220 | |
1221 | /* called while rendering through @FT_Render_Glyph */ |
1222 | static FT_Error |
1223 | bsdf_raster_render( FT_Raster raster, |
1224 | const FT_Raster_Params* params ) |
1225 | { |
1226 | FT_Error error = FT_Err_Ok; |
1227 | FT_Memory memory = NULL; |
1228 | |
1229 | const FT_Bitmap* source = NULL; |
1230 | const FT_Bitmap* target = NULL; |
1231 | |
1232 | BSDF_TRaster* bsdf_raster = (BSDF_TRaster*)raster; |
1233 | BSDF_Worker worker; |
1234 | |
1235 | const SDF_Raster_Params* sdf_params = (const SDF_Raster_Params*)params; |
1236 | |
1237 | |
1238 | worker.distance_map = NULL; |
1239 | |
1240 | /* check for valid parameters */ |
1241 | if ( !raster || !params ) |
1242 | { |
1243 | error = FT_THROW( Invalid_Argument ); |
1244 | goto Exit; |
1245 | } |
1246 | |
1247 | /* check whether the flag is set */ |
1248 | if ( sdf_params->root.flags != FT_RASTER_FLAG_SDF ) |
1249 | { |
1250 | error = FT_THROW( Raster_Corrupted ); |
1251 | goto Exit; |
1252 | } |
1253 | |
1254 | source = (const FT_Bitmap*)sdf_params->root.source; |
1255 | target = (const FT_Bitmap*)sdf_params->root.target; |
1256 | |
1257 | /* check source and target bitmap */ |
1258 | if ( !source || !target ) |
1259 | { |
1260 | error = FT_THROW( Invalid_Argument ); |
1261 | goto Exit; |
1262 | } |
1263 | |
1264 | memory = bsdf_raster->memory; |
1265 | if ( !memory ) |
1266 | { |
1267 | FT_TRACE0(( "bsdf_raster_render: Raster not set up properly,\n" )); |
1268 | FT_TRACE0(( " unable to find memory handle.\n" )); |
1269 | |
1270 | error = FT_THROW( Invalid_Handle ); |
1271 | goto Exit; |
1272 | } |
1273 | |
1274 | /* check whether spread is set properly */ |
1275 | if ( sdf_params->spread > MAX_SPREAD || |
1276 | sdf_params->spread < MIN_SPREAD ) |
1277 | { |
1278 | FT_TRACE0(( "bsdf_raster_render:" |
1279 | " The `spread' field of `SDF_Raster_Params'\n" )); |
1280 | FT_TRACE0(( " " |
1281 | " is invalid; the value of this field must be\n" )); |
1282 | FT_TRACE0(( " " |
1283 | " within [%d, %d].\n" , |
1284 | MIN_SPREAD, MAX_SPREAD )); |
1285 | FT_TRACE0(( " " |
1286 | " Also, you must pass `SDF_Raster_Params'\n" )); |
1287 | FT_TRACE0(( " " |
1288 | " instead of the default `FT_Raster_Params'\n" )); |
1289 | FT_TRACE0(( " " |
1290 | " while calling this function and set the fields\n" )); |
1291 | FT_TRACE0(( " " |
1292 | " accordingly.\n" )); |
1293 | |
1294 | error = FT_THROW( Invalid_Argument ); |
1295 | goto Exit; |
1296 | } |
1297 | |
1298 | /* set up the worker */ |
1299 | |
1300 | /* allocate the distance map */ |
1301 | if ( FT_QALLOC_MULT( worker.distance_map, target->rows, |
1302 | target->width * sizeof ( *worker.distance_map ) ) ) |
1303 | goto Exit; |
1304 | |
1305 | worker.width = (int)target->width; |
1306 | worker.rows = (int)target->rows; |
1307 | worker.params = *sdf_params; |
1308 | |
1309 | FT_CALL( bsdf_init_distance_map( source, &worker ) ); |
1310 | FT_CALL( bsdf_approximate_edge( &worker ) ); |
1311 | FT_CALL( edt8( &worker ) ); |
1312 | FT_CALL( finalize_sdf( &worker, target ) ); |
1313 | |
1314 | FT_TRACE0(( "bsdf_raster_render: Total memory used = %ld\n" , |
1315 | worker.width * worker.rows * |
1316 | (long)sizeof ( *worker.distance_map ) )); |
1317 | |
1318 | Exit: |
1319 | if ( worker.distance_map ) |
1320 | FT_FREE( worker.distance_map ); |
1321 | |
1322 | return error; |
1323 | } |
1324 | |
1325 | |
1326 | /* called while deleting `FT_Library` only if the module is added */ |
1327 | static void |
1328 | bsdf_raster_done( FT_Raster raster ) |
1329 | { |
1330 | FT_Memory memory = (FT_Memory)((BSDF_TRaster*)raster)->memory; |
1331 | |
1332 | |
1333 | FT_FREE( raster ); |
1334 | } |
1335 | |
1336 | |
1337 | FT_DEFINE_RASTER_FUNCS( |
1338 | ft_bitmap_sdf_raster, |
1339 | |
1340 | FT_GLYPH_FORMAT_BITMAP, |
1341 | |
1342 | (FT_Raster_New_Func) bsdf_raster_new, /* raster_new */ |
1343 | (FT_Raster_Reset_Func) bsdf_raster_reset, /* raster_reset */ |
1344 | (FT_Raster_Set_Mode_Func)bsdf_raster_set_mode, /* raster_set_mode */ |
1345 | (FT_Raster_Render_Func) bsdf_raster_render, /* raster_render */ |
1346 | (FT_Raster_Done_Func) bsdf_raster_done /* raster_done */ |
1347 | ) |
1348 | |
1349 | |
1350 | /* END */ |
1351 | |