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 */