1 | /**************************************************************************** |
2 | * |
3 | * ftsdf.c |
4 | * |
5 | * Signed Distance Field support for outline fonts (body). |
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/ftoutln.h> |
24 | #include <freetype/fttrigon.h> |
25 | #include <freetype/ftbitmap.h> |
26 | #include "ftsdf.h" |
27 | |
28 | #include "ftsdferrs.h" |
29 | |
30 | |
31 | /************************************************************************** |
32 | * |
33 | * A brief technical overview of how the SDF rasterizer works |
34 | * ---------------------------------------------------------- |
35 | * |
36 | * [Notes]: |
37 | * * SDF stands for Signed Distance Field everywhere. |
38 | * |
39 | * * This renderer generates SDF directly from outlines. There is |
40 | * another renderer called 'bsdf', which converts bitmaps to SDF; see |
41 | * file `ftbsdf.c` for more. |
42 | * |
43 | * * The basic idea of generating the SDF is taken from Viktor Chlumsky's |
44 | * research paper. The paper explains both single and multi-channel |
45 | * SDF, however, this implementation only generates single-channel SDF. |
46 | * |
47 | * Chlumsky, Viktor: Shape Decomposition for Multi-channel Distance |
48 | * Fields. Master's thesis. Czech Technical University in Prague, |
49 | * Faculty of InformationTechnology, 2015. |
50 | * |
51 | * For more information: https://github.com/Chlumsky/msdfgen |
52 | * |
53 | * ======================================================================== |
54 | * |
55 | * Generating SDF from outlines is pretty straightforward. |
56 | * |
57 | * (1) We have a set of contours that make the outline of a shape/glyph. |
58 | * Each contour comprises of several edges, with three types of edges. |
59 | * |
60 | * * line segments |
61 | * * conic Bezier curves |
62 | * * cubic Bezier curves |
63 | * |
64 | * (2) Apart from the outlines we also have a two-dimensional grid, namely |
65 | * the bitmap that is used to represent the final SDF data. |
66 | * |
67 | * (3) In order to generate SDF, our task is to find shortest signed |
68 | * distance from each grid point to the outline. The 'signed |
69 | * distance' means that if the grid point is filled by any contour |
70 | * then its sign is positive, otherwise it is negative. The pseudo |
71 | * code is as follows. |
72 | * |
73 | * ``` |
74 | * foreach grid_point (x, y): |
75 | * { |
76 | * int min_dist = INT_MAX; |
77 | * |
78 | * foreach contour in outline: |
79 | * { |
80 | * foreach edge in contour: |
81 | * { |
82 | * // get shortest distance from point (x, y) to the edge |
83 | * d = get_min_dist(x, y, edge); |
84 | * |
85 | * if (d < min_dist) |
86 | * min_dist = d; |
87 | * } |
88 | * |
89 | * bitmap[x, y] = min_dist; |
90 | * } |
91 | * } |
92 | * ``` |
93 | * |
94 | * (4) After running this algorithm the bitmap contains information about |
95 | * the shortest distance from each point to the outline of the shape. |
96 | * Of course, while this is the most straightforward way of generating |
97 | * SDF, we use various optimizations in our implementation. See the |
98 | * `sdf_generate_*' functions in this file for all details. |
99 | * |
100 | * The optimization currently used by default is subdivision; see |
101 | * function `sdf_generate_subdivision` for more. |
102 | * |
103 | * Also, to see how we compute the shortest distance from a point to |
104 | * each type of edge, check out the `get_min_distance_*' functions. |
105 | * |
106 | */ |
107 | |
108 | |
109 | /************************************************************************** |
110 | * |
111 | * The macro FT_COMPONENT is used in trace mode. It is an implicit |
112 | * parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log |
113 | * messages during execution. |
114 | */ |
115 | #undef FT_COMPONENT |
116 | #define FT_COMPONENT sdf |
117 | |
118 | |
119 | /************************************************************************** |
120 | * |
121 | * definitions |
122 | * |
123 | */ |
124 | |
125 | /* |
126 | * If set to 1, the rasterizer uses Newton-Raphson's method for finding |
127 | * the shortest distance from a point to a conic curve. |
128 | * |
129 | * If set to 0, an analytical method gets used instead, which computes the |
130 | * roots of a cubic polynomial to find the shortest distance. However, |
131 | * the analytical method can currently underflow; we thus use Newton's |
132 | * method by default. |
133 | */ |
134 | #ifndef USE_NEWTON_FOR_CONIC |
135 | #define USE_NEWTON_FOR_CONIC 1 |
136 | #endif |
137 | |
138 | /* |
139 | * The number of intervals a Bezier curve gets sampled and checked to find |
140 | * the shortest distance. |
141 | */ |
142 | #define MAX_NEWTON_DIVISIONS 4 |
143 | |
144 | /* |
145 | * The number of steps of Newton's iterations in each interval of the |
146 | * Bezier curve. Basically, we run Newton's approximation |
147 | * |
148 | * x -= Q(t) / Q'(t) |
149 | * |
150 | * for each division to get the shortest distance. |
151 | */ |
152 | #define MAX_NEWTON_STEPS 4 |
153 | |
154 | /* |
155 | * The epsilon distance (in 16.16 fractional units) used for corner |
156 | * resolving. If the difference of two distances is less than this value |
157 | * they will be checked for a corner if they are ambiguous. |
158 | */ |
159 | #define CORNER_CHECK_EPSILON 32 |
160 | |
161 | #if 0 |
162 | /* |
163 | * Coarse grid dimension. Will probably be removed in the future because |
164 | * coarse grid optimization is the slowest algorithm. |
165 | */ |
166 | #define CG_DIMEN 8 |
167 | #endif |
168 | |
169 | |
170 | /************************************************************************** |
171 | * |
172 | * macros |
173 | * |
174 | */ |
175 | |
176 | #define MUL_26D6( a, b ) ( ( ( a ) * ( b ) ) / 64 ) |
177 | #define VEC_26D6_DOT( p, q ) ( MUL_26D6( p.x, q.x ) + \ |
178 | MUL_26D6( p.y, q.y ) ) |
179 | |
180 | |
181 | /************************************************************************** |
182 | * |
183 | * structures and enums |
184 | * |
185 | */ |
186 | |
187 | /************************************************************************** |
188 | * |
189 | * @Struct: |
190 | * SDF_TRaster |
191 | * |
192 | * @Description: |
193 | * This struct is used in place of @FT_Raster and is stored within the |
194 | * internal FreeType renderer struct. While rasterizing it is passed to |
195 | * the @FT_Raster_RenderFunc function, which then can be used however we |
196 | * want. |
197 | * |
198 | * @Fields: |
199 | * memory :: |
200 | * Used internally to allocate intermediate memory while raterizing. |
201 | * |
202 | */ |
203 | typedef struct SDF_TRaster_ |
204 | { |
205 | FT_Memory memory; |
206 | |
207 | } SDF_TRaster, *SDF_PRaster; |
208 | |
209 | |
210 | /************************************************************************** |
211 | * |
212 | * @Enum: |
213 | * SDF_Edge_Type |
214 | * |
215 | * @Description: |
216 | * Enumeration of all curve types present in fonts. |
217 | * |
218 | * @Fields: |
219 | * SDF_EDGE_UNDEFINED :: |
220 | * Undefined edge, simply used to initialize and detect errors. |
221 | * |
222 | * SDF_EDGE_LINE :: |
223 | * Line segment with start and end point. |
224 | * |
225 | * SDF_EDGE_CONIC :: |
226 | * A conic/quadratic Bezier curve with start, end, and one control |
227 | * point. |
228 | * |
229 | * SDF_EDGE_CUBIC :: |
230 | * A cubic Bezier curve with start, end, and two control points. |
231 | * |
232 | */ |
233 | typedef enum SDF_Edge_Type_ |
234 | { |
235 | SDF_EDGE_UNDEFINED = 0, |
236 | SDF_EDGE_LINE = 1, |
237 | SDF_EDGE_CONIC = 2, |
238 | SDF_EDGE_CUBIC = 3 |
239 | |
240 | } SDF_Edge_Type; |
241 | |
242 | |
243 | /************************************************************************** |
244 | * |
245 | * @Enum: |
246 | * SDF_Contour_Orientation |
247 | * |
248 | * @Description: |
249 | * Enumeration of all orientation values of a contour. We determine the |
250 | * orientation by calculating the area covered by a contour. Contrary |
251 | * to values returned by @FT_Outline_Get_Orientation, |
252 | * `SDF_Contour_Orientation` is independent of the fill rule, which can |
253 | * be different for different font formats. |
254 | * |
255 | * @Fields: |
256 | * SDF_ORIENTATION_NONE :: |
257 | * Undefined orientation, used for initialization and error detection. |
258 | * |
259 | * SDF_ORIENTATION_CW :: |
260 | * Clockwise orientation (positive area covered). |
261 | * |
262 | * SDF_ORIENTATION_CCW :: |
263 | * Counter-clockwise orientation (negative area covered). |
264 | * |
265 | * @Note: |
266 | * See @FT_Outline_Get_Orientation for more details. |
267 | * |
268 | */ |
269 | typedef enum SDF_Contour_Orientation_ |
270 | { |
271 | SDF_ORIENTATION_NONE = 0, |
272 | SDF_ORIENTATION_CW = 1, |
273 | SDF_ORIENTATION_CCW = 2 |
274 | |
275 | } SDF_Contour_Orientation; |
276 | |
277 | |
278 | /************************************************************************** |
279 | * |
280 | * @Struct: |
281 | * SDF_Edge |
282 | * |
283 | * @Description: |
284 | * Represent an edge of a contour. |
285 | * |
286 | * @Fields: |
287 | * start_pos :: |
288 | * Start position of an edge. Valid for all types of edges. |
289 | * |
290 | * end_pos :: |
291 | * Etart position of an edge. Valid for all types of edges. |
292 | * |
293 | * control_a :: |
294 | * A control point of the edge. Valid only for `SDF_EDGE_CONIC` |
295 | * and `SDF_EDGE_CUBIC`. |
296 | * |
297 | * control_b :: |
298 | * Another control point of the edge. Valid only for |
299 | * `SDF_EDGE_CONIC`. |
300 | * |
301 | * edge_type :: |
302 | * Type of the edge, see @SDF_Edge_Type for all possible edge types. |
303 | * |
304 | * next :: |
305 | * Used to create a singly linked list, which can be interpreted |
306 | * as a contour. |
307 | * |
308 | */ |
309 | typedef struct SDF_Edge_ |
310 | { |
311 | FT_26D6_Vec start_pos; |
312 | FT_26D6_Vec end_pos; |
313 | FT_26D6_Vec control_a; |
314 | FT_26D6_Vec control_b; |
315 | |
316 | SDF_Edge_Type edge_type; |
317 | |
318 | struct SDF_Edge_* next; |
319 | |
320 | } SDF_Edge; |
321 | |
322 | |
323 | /************************************************************************** |
324 | * |
325 | * @Struct: |
326 | * SDF_Contour |
327 | * |
328 | * @Description: |
329 | * Represent a complete contour, which contains a list of edges. |
330 | * |
331 | * @Fields: |
332 | * last_pos :: |
333 | * Contains the value of `end_pos' of the last edge in the list of |
334 | * edges. Useful while decomposing the outline with |
335 | * @FT_Outline_Decompose. |
336 | * |
337 | * edges :: |
338 | * Linked list of all the edges that make the contour. |
339 | * |
340 | * next :: |
341 | * Used to create a singly linked list, which can be interpreted as a |
342 | * complete shape or @FT_Outline. |
343 | * |
344 | */ |
345 | typedef struct SDF_Contour_ |
346 | { |
347 | FT_26D6_Vec last_pos; |
348 | SDF_Edge* edges; |
349 | |
350 | struct SDF_Contour_* next; |
351 | |
352 | } SDF_Contour; |
353 | |
354 | |
355 | /************************************************************************** |
356 | * |
357 | * @Struct: |
358 | * SDF_Shape |
359 | * |
360 | * @Description: |
361 | * Represent a complete shape, which is the decomposition of |
362 | * @FT_Outline. |
363 | * |
364 | * @Fields: |
365 | * memory :: |
366 | * Used internally to allocate memory. |
367 | * |
368 | * contours :: |
369 | * Linked list of all the contours that make the shape. |
370 | * |
371 | */ |
372 | typedef struct SDF_Shape_ |
373 | { |
374 | FT_Memory memory; |
375 | SDF_Contour* contours; |
376 | |
377 | } SDF_Shape; |
378 | |
379 | |
380 | /************************************************************************** |
381 | * |
382 | * @Struct: |
383 | * SDF_Signed_Distance |
384 | * |
385 | * @Description: |
386 | * Represent signed distance of a point, i.e., the distance of the edge |
387 | * nearest to the point. |
388 | * |
389 | * @Fields: |
390 | * distance :: |
391 | * Distance of the point from the nearest edge. Can be squared or |
392 | * absolute depending on the `USE_SQUARED_DISTANCES` macro defined in |
393 | * file `ftsdfcommon.h`. |
394 | * |
395 | * cross :: |
396 | * Cross product of the shortest distance vector (i.e., the vector |
397 | * from the point to the nearest edge) and the direction of the edge |
398 | * at the nearest point. This is used to resolve ambiguities of |
399 | * `sign`. |
400 | * |
401 | * sign :: |
402 | * A value used to indicate whether the distance vector is outside or |
403 | * inside the contour corresponding to the edge. |
404 | * |
405 | * @Note: |
406 | * `sign` may or may not be correct, therefore it must be checked |
407 | * properly in case there is an ambiguity. |
408 | * |
409 | */ |
410 | typedef struct SDF_Signed_Distance_ |
411 | { |
412 | FT_16D16 distance; |
413 | FT_16D16 cross; |
414 | FT_Char sign; |
415 | |
416 | } SDF_Signed_Distance; |
417 | |
418 | |
419 | /************************************************************************** |
420 | * |
421 | * @Struct: |
422 | * SDF_Params |
423 | * |
424 | * @Description: |
425 | * Yet another internal parameters required by the rasterizer. |
426 | * |
427 | * @Fields: |
428 | * orientation :: |
429 | * This is not the @SDF_Contour_Orientation value but @FT_Orientation, |
430 | * which determines whether clockwise-oriented outlines are to be |
431 | * filled or counter-clockwise-oriented ones. |
432 | * |
433 | * flip_sign :: |
434 | * If set to true, flip the sign. By default the points filled by the |
435 | * outline are positive. |
436 | * |
437 | * flip_y :: |
438 | * If set to true the output bitmap is upside-down. Can be useful |
439 | * because OpenGL and DirectX use different coordinate systems for |
440 | * textures. |
441 | * |
442 | * overload_sign :: |
443 | * In the subdivision and bounding box optimization, the default |
444 | * outside sign is taken as -1. This parameter can be used to modify |
445 | * that behaviour. For example, while generating SDF for a single |
446 | * counter-clockwise contour, the outside sign should be 1. |
447 | * |
448 | */ |
449 | typedef struct SDF_Params_ |
450 | { |
451 | FT_Orientation orientation; |
452 | FT_Bool flip_sign; |
453 | FT_Bool flip_y; |
454 | |
455 | FT_Int overload_sign; |
456 | |
457 | } SDF_Params; |
458 | |
459 | |
460 | /************************************************************************** |
461 | * |
462 | * constants, initializer, and destructor |
463 | * |
464 | */ |
465 | |
466 | static |
467 | const FT_Vector zero_vector = { 0, 0 }; |
468 | |
469 | static |
470 | const SDF_Edge null_edge = { { 0, 0 }, { 0, 0 }, |
471 | { 0, 0 }, { 0, 0 }, |
472 | SDF_EDGE_UNDEFINED, NULL }; |
473 | |
474 | static |
475 | const SDF_Contour null_contour = { { 0, 0 }, NULL, NULL }; |
476 | |
477 | static |
478 | const SDF_Shape null_shape = { NULL, NULL }; |
479 | |
480 | static |
481 | const SDF_Signed_Distance max_sdf = { INT_MAX, 0, 0 }; |
482 | |
483 | |
484 | /* Create a new @SDF_Edge on the heap and assigns the `edge` */ |
485 | /* pointer to the newly allocated memory. */ |
486 | static FT_Error |
487 | sdf_edge_new( FT_Memory memory, |
488 | SDF_Edge** edge ) |
489 | { |
490 | FT_Error error = FT_Err_Ok; |
491 | SDF_Edge* ptr = NULL; |
492 | |
493 | |
494 | if ( !memory || !edge ) |
495 | { |
496 | error = FT_THROW( Invalid_Argument ); |
497 | goto Exit; |
498 | } |
499 | |
500 | if ( !FT_QNEW( ptr ) ) |
501 | { |
502 | *ptr = null_edge; |
503 | *edge = ptr; |
504 | } |
505 | |
506 | Exit: |
507 | return error; |
508 | } |
509 | |
510 | |
511 | /* Free the allocated `edge` variable. */ |
512 | static void |
513 | sdf_edge_done( FT_Memory memory, |
514 | SDF_Edge** edge ) |
515 | { |
516 | if ( !memory || !edge || !*edge ) |
517 | return; |
518 | |
519 | FT_FREE( *edge ); |
520 | } |
521 | |
522 | |
523 | /* Create a new @SDF_Contour on the heap and assign */ |
524 | /* the `contour` pointer to the newly allocated memory. */ |
525 | static FT_Error |
526 | sdf_contour_new( FT_Memory memory, |
527 | SDF_Contour** contour ) |
528 | { |
529 | FT_Error error = FT_Err_Ok; |
530 | SDF_Contour* ptr = NULL; |
531 | |
532 | |
533 | if ( !memory || !contour ) |
534 | { |
535 | error = FT_THROW( Invalid_Argument ); |
536 | goto Exit; |
537 | } |
538 | |
539 | if ( !FT_QNEW( ptr ) ) |
540 | { |
541 | *ptr = null_contour; |
542 | *contour = ptr; |
543 | } |
544 | |
545 | Exit: |
546 | return error; |
547 | } |
548 | |
549 | |
550 | /* Free the allocated `contour` variable. */ |
551 | /* Also free the list of edges. */ |
552 | static void |
553 | sdf_contour_done( FT_Memory memory, |
554 | SDF_Contour** contour ) |
555 | { |
556 | SDF_Edge* edges; |
557 | SDF_Edge* temp; |
558 | |
559 | |
560 | if ( !memory || !contour || !*contour ) |
561 | return; |
562 | |
563 | edges = (*contour)->edges; |
564 | |
565 | /* release all edges */ |
566 | while ( edges ) |
567 | { |
568 | temp = edges; |
569 | edges = edges->next; |
570 | |
571 | sdf_edge_done( memory, &temp ); |
572 | } |
573 | |
574 | FT_FREE( *contour ); |
575 | } |
576 | |
577 | |
578 | /* Create a new @SDF_Shape on the heap and assign */ |
579 | /* the `shape` pointer to the newly allocated memory. */ |
580 | static FT_Error |
581 | sdf_shape_new( FT_Memory memory, |
582 | SDF_Shape** shape ) |
583 | { |
584 | FT_Error error = FT_Err_Ok; |
585 | SDF_Shape* ptr = NULL; |
586 | |
587 | |
588 | if ( !memory || !shape ) |
589 | { |
590 | error = FT_THROW( Invalid_Argument ); |
591 | goto Exit; |
592 | } |
593 | |
594 | if ( !FT_QNEW( ptr ) ) |
595 | { |
596 | *ptr = null_shape; |
597 | ptr->memory = memory; |
598 | *shape = ptr; |
599 | } |
600 | |
601 | Exit: |
602 | return error; |
603 | } |
604 | |
605 | |
606 | /* Free the allocated `shape` variable. */ |
607 | /* Also free the list of contours. */ |
608 | static void |
609 | sdf_shape_done( SDF_Shape** shape ) |
610 | { |
611 | FT_Memory memory; |
612 | SDF_Contour* contours; |
613 | SDF_Contour* temp; |
614 | |
615 | |
616 | if ( !shape || !*shape ) |
617 | return; |
618 | |
619 | memory = (*shape)->memory; |
620 | contours = (*shape)->contours; |
621 | |
622 | if ( !memory ) |
623 | return; |
624 | |
625 | /* release all contours */ |
626 | while ( contours ) |
627 | { |
628 | temp = contours; |
629 | contours = contours->next; |
630 | |
631 | sdf_contour_done( memory, &temp ); |
632 | } |
633 | |
634 | /* release the allocated shape struct */ |
635 | FT_FREE( *shape ); |
636 | } |
637 | |
638 | |
639 | /************************************************************************** |
640 | * |
641 | * shape decomposition functions |
642 | * |
643 | */ |
644 | |
645 | /* This function is called when starting a new contour at `to`, */ |
646 | /* which gets added to the shape's list. */ |
647 | static FT_Error |
648 | sdf_move_to( const FT_26D6_Vec* to, |
649 | void* user ) |
650 | { |
651 | SDF_Shape* shape = ( SDF_Shape* )user; |
652 | SDF_Contour* contour = NULL; |
653 | |
654 | FT_Error error = FT_Err_Ok; |
655 | FT_Memory memory = shape->memory; |
656 | |
657 | |
658 | if ( !to || !user ) |
659 | { |
660 | error = FT_THROW( Invalid_Argument ); |
661 | goto Exit; |
662 | } |
663 | |
664 | FT_CALL( sdf_contour_new( memory, &contour ) ); |
665 | |
666 | contour->last_pos = *to; |
667 | contour->next = shape->contours; |
668 | shape->contours = contour; |
669 | |
670 | Exit: |
671 | return error; |
672 | } |
673 | |
674 | |
675 | /* This function is called when there is a line in the */ |
676 | /* contour. The line starts at the previous edge point and */ |
677 | /* stops at `to`. */ |
678 | static FT_Error |
679 | sdf_line_to( const FT_26D6_Vec* to, |
680 | void* user ) |
681 | { |
682 | SDF_Shape* shape = ( SDF_Shape* )user; |
683 | SDF_Edge* edge = NULL; |
684 | SDF_Contour* contour = NULL; |
685 | |
686 | FT_Error error = FT_Err_Ok; |
687 | FT_Memory memory = shape->memory; |
688 | |
689 | |
690 | if ( !to || !user ) |
691 | { |
692 | error = FT_THROW( Invalid_Argument ); |
693 | goto Exit; |
694 | } |
695 | |
696 | contour = shape->contours; |
697 | |
698 | if ( contour->last_pos.x == to->x && |
699 | contour->last_pos.y == to->y ) |
700 | goto Exit; |
701 | |
702 | FT_CALL( sdf_edge_new( memory, &edge ) ); |
703 | |
704 | edge->edge_type = SDF_EDGE_LINE; |
705 | edge->start_pos = contour->last_pos; |
706 | edge->end_pos = *to; |
707 | |
708 | edge->next = contour->edges; |
709 | contour->edges = edge; |
710 | contour->last_pos = *to; |
711 | |
712 | Exit: |
713 | return error; |
714 | } |
715 | |
716 | |
717 | /* This function is called when there is a conic Bezier curve */ |
718 | /* in the contour. The curve starts at the previous edge point */ |
719 | /* and stops at `to`, with control point `control_1`. */ |
720 | static FT_Error |
721 | sdf_conic_to( const FT_26D6_Vec* control_1, |
722 | const FT_26D6_Vec* to, |
723 | void* user ) |
724 | { |
725 | SDF_Shape* shape = ( SDF_Shape* )user; |
726 | SDF_Edge* edge = NULL; |
727 | SDF_Contour* contour = NULL; |
728 | |
729 | FT_Error error = FT_Err_Ok; |
730 | FT_Memory memory = shape->memory; |
731 | |
732 | |
733 | if ( !control_1 || !to || !user ) |
734 | { |
735 | error = FT_THROW( Invalid_Argument ); |
736 | goto Exit; |
737 | } |
738 | |
739 | contour = shape->contours; |
740 | |
741 | /* If the control point coincides with any of the end points */ |
742 | /* then it is a line and should be treated as one to avoid */ |
743 | /* unnecessary complexity later in the algorithm. */ |
744 | if ( ( contour->last_pos.x == control_1->x && |
745 | contour->last_pos.y == control_1->y ) || |
746 | ( control_1->x == to->x && |
747 | control_1->y == to->y ) ) |
748 | { |
749 | sdf_line_to( to, user ); |
750 | goto Exit; |
751 | } |
752 | |
753 | FT_CALL( sdf_edge_new( memory, &edge ) ); |
754 | |
755 | edge->edge_type = SDF_EDGE_CONIC; |
756 | edge->start_pos = contour->last_pos; |
757 | edge->control_a = *control_1; |
758 | edge->end_pos = *to; |
759 | |
760 | edge->next = contour->edges; |
761 | contour->edges = edge; |
762 | contour->last_pos = *to; |
763 | |
764 | Exit: |
765 | return error; |
766 | } |
767 | |
768 | |
769 | /* This function is called when there is a cubic Bezier curve */ |
770 | /* in the contour. The curve starts at the previous edge point */ |
771 | /* and stops at `to`, with two control points `control_1` and */ |
772 | /* `control_2`. */ |
773 | static FT_Error |
774 | sdf_cubic_to( const FT_26D6_Vec* control_1, |
775 | const FT_26D6_Vec* control_2, |
776 | const FT_26D6_Vec* to, |
777 | void* user ) |
778 | { |
779 | SDF_Shape* shape = ( SDF_Shape* )user; |
780 | SDF_Edge* edge = NULL; |
781 | SDF_Contour* contour = NULL; |
782 | |
783 | FT_Error error = FT_Err_Ok; |
784 | FT_Memory memory = shape->memory; |
785 | |
786 | |
787 | if ( !control_2 || !control_1 || !to || !user ) |
788 | { |
789 | error = FT_THROW( Invalid_Argument ); |
790 | goto Exit; |
791 | } |
792 | |
793 | contour = shape->contours; |
794 | |
795 | FT_CALL( sdf_edge_new( memory, &edge ) ); |
796 | |
797 | edge->edge_type = SDF_EDGE_CUBIC; |
798 | edge->start_pos = contour->last_pos; |
799 | edge->control_a = *control_1; |
800 | edge->control_b = *control_2; |
801 | edge->end_pos = *to; |
802 | |
803 | edge->next = contour->edges; |
804 | contour->edges = edge; |
805 | contour->last_pos = *to; |
806 | |
807 | Exit: |
808 | return error; |
809 | } |
810 | |
811 | |
812 | /* Construct the structure to hold all four outline */ |
813 | /* decomposition functions. */ |
814 | FT_DEFINE_OUTLINE_FUNCS( |
815 | sdf_decompose_funcs, |
816 | |
817 | (FT_Outline_MoveTo_Func) sdf_move_to, /* move_to */ |
818 | (FT_Outline_LineTo_Func) sdf_line_to, /* line_to */ |
819 | (FT_Outline_ConicTo_Func)sdf_conic_to, /* conic_to */ |
820 | (FT_Outline_CubicTo_Func)sdf_cubic_to, /* cubic_to */ |
821 | |
822 | 0, /* shift */ |
823 | 0 /* delta */ |
824 | ) |
825 | |
826 | |
827 | /* Decompose `outline` and put it into the `shape` structure. */ |
828 | static FT_Error |
829 | sdf_outline_decompose( FT_Outline* outline, |
830 | SDF_Shape* shape ) |
831 | { |
832 | FT_Error error = FT_Err_Ok; |
833 | |
834 | |
835 | if ( !outline || !shape ) |
836 | { |
837 | error = FT_THROW( Invalid_Argument ); |
838 | goto Exit; |
839 | } |
840 | |
841 | error = FT_Outline_Decompose( outline, |
842 | &sdf_decompose_funcs, |
843 | (void*)shape ); |
844 | |
845 | Exit: |
846 | return error; |
847 | } |
848 | |
849 | |
850 | /************************************************************************** |
851 | * |
852 | * utility functions |
853 | * |
854 | */ |
855 | |
856 | /* Return the control box of an edge. The control box is a rectangle */ |
857 | /* in which all the control points can fit tightly. */ |
858 | static FT_CBox |
859 | get_control_box( SDF_Edge edge ) |
860 | { |
861 | FT_CBox cbox = { 0, 0, 0, 0 }; |
862 | FT_Bool is_set = 0; |
863 | |
864 | |
865 | switch ( edge.edge_type ) |
866 | { |
867 | case SDF_EDGE_CUBIC: |
868 | cbox.xMin = edge.control_b.x; |
869 | cbox.xMax = edge.control_b.x; |
870 | cbox.yMin = edge.control_b.y; |
871 | cbox.yMax = edge.control_b.y; |
872 | |
873 | is_set = 1; |
874 | FALL_THROUGH; |
875 | |
876 | case SDF_EDGE_CONIC: |
877 | if ( is_set ) |
878 | { |
879 | cbox.xMin = edge.control_a.x < cbox.xMin |
880 | ? edge.control_a.x |
881 | : cbox.xMin; |
882 | cbox.xMax = edge.control_a.x > cbox.xMax |
883 | ? edge.control_a.x |
884 | : cbox.xMax; |
885 | |
886 | cbox.yMin = edge.control_a.y < cbox.yMin |
887 | ? edge.control_a.y |
888 | : cbox.yMin; |
889 | cbox.yMax = edge.control_a.y > cbox.yMax |
890 | ? edge.control_a.y |
891 | : cbox.yMax; |
892 | } |
893 | else |
894 | { |
895 | cbox.xMin = edge.control_a.x; |
896 | cbox.xMax = edge.control_a.x; |
897 | cbox.yMin = edge.control_a.y; |
898 | cbox.yMax = edge.control_a.y; |
899 | |
900 | is_set = 1; |
901 | } |
902 | FALL_THROUGH; |
903 | |
904 | case SDF_EDGE_LINE: |
905 | if ( is_set ) |
906 | { |
907 | cbox.xMin = edge.start_pos.x < cbox.xMin |
908 | ? edge.start_pos.x |
909 | : cbox.xMin; |
910 | cbox.xMax = edge.start_pos.x > cbox.xMax |
911 | ? edge.start_pos.x |
912 | : cbox.xMax; |
913 | |
914 | cbox.yMin = edge.start_pos.y < cbox.yMin |
915 | ? edge.start_pos.y |
916 | : cbox.yMin; |
917 | cbox.yMax = edge.start_pos.y > cbox.yMax |
918 | ? edge.start_pos.y |
919 | : cbox.yMax; |
920 | } |
921 | else |
922 | { |
923 | cbox.xMin = edge.start_pos.x; |
924 | cbox.xMax = edge.start_pos.x; |
925 | cbox.yMin = edge.start_pos.y; |
926 | cbox.yMax = edge.start_pos.y; |
927 | } |
928 | |
929 | cbox.xMin = edge.end_pos.x < cbox.xMin |
930 | ? edge.end_pos.x |
931 | : cbox.xMin; |
932 | cbox.xMax = edge.end_pos.x > cbox.xMax |
933 | ? edge.end_pos.x |
934 | : cbox.xMax; |
935 | |
936 | cbox.yMin = edge.end_pos.y < cbox.yMin |
937 | ? edge.end_pos.y |
938 | : cbox.yMin; |
939 | cbox.yMax = edge.end_pos.y > cbox.yMax |
940 | ? edge.end_pos.y |
941 | : cbox.yMax; |
942 | |
943 | break; |
944 | |
945 | default: |
946 | break; |
947 | } |
948 | |
949 | return cbox; |
950 | } |
951 | |
952 | |
953 | /* Return orientation of a single contour. */ |
954 | /* Note that the orientation is independent of the fill rule! */ |
955 | /* So, for TTF a clockwise-oriented contour has to be filled */ |
956 | /* and the opposite for OTF fonts. */ |
957 | static SDF_Contour_Orientation |
958 | get_contour_orientation ( SDF_Contour* contour ) |
959 | { |
960 | SDF_Edge* head = NULL; |
961 | FT_26D6 area = 0; |
962 | |
963 | |
964 | /* return none if invalid parameters */ |
965 | if ( !contour || !contour->edges ) |
966 | return SDF_ORIENTATION_NONE; |
967 | |
968 | head = contour->edges; |
969 | |
970 | /* Calculate the area of the control box for all edges. */ |
971 | while ( head ) |
972 | { |
973 | switch ( head->edge_type ) |
974 | { |
975 | case SDF_EDGE_LINE: |
976 | area += MUL_26D6( ( head->end_pos.x - head->start_pos.x ), |
977 | ( head->end_pos.y + head->start_pos.y ) ); |
978 | break; |
979 | |
980 | case SDF_EDGE_CONIC: |
981 | area += MUL_26D6( head->control_a.x - head->start_pos.x, |
982 | head->control_a.y + head->start_pos.y ); |
983 | area += MUL_26D6( head->end_pos.x - head->control_a.x, |
984 | head->end_pos.y + head->control_a.y ); |
985 | break; |
986 | |
987 | case SDF_EDGE_CUBIC: |
988 | area += MUL_26D6( head->control_a.x - head->start_pos.x, |
989 | head->control_a.y + head->start_pos.y ); |
990 | area += MUL_26D6( head->control_b.x - head->control_a.x, |
991 | head->control_b.y + head->control_a.y ); |
992 | area += MUL_26D6( head->end_pos.x - head->control_b.x, |
993 | head->end_pos.y + head->control_b.y ); |
994 | break; |
995 | |
996 | default: |
997 | return SDF_ORIENTATION_NONE; |
998 | } |
999 | |
1000 | head = head->next; |
1001 | } |
1002 | |
1003 | /* Clockwise contours cover a positive area, and counter-clockwise */ |
1004 | /* contours cover a negative area. */ |
1005 | if ( area > 0 ) |
1006 | return SDF_ORIENTATION_CW; |
1007 | else |
1008 | return SDF_ORIENTATION_CCW; |
1009 | } |
1010 | |
1011 | |
1012 | /* This function is exactly the same as the one */ |
1013 | /* in the smooth renderer. It splits a conic */ |
1014 | /* into two conics exactly half way at t = 0.5. */ |
1015 | static void |
1016 | split_conic( FT_26D6_Vec* base ) |
1017 | { |
1018 | FT_26D6 a, b; |
1019 | |
1020 | |
1021 | base[4].x = base[2].x; |
1022 | a = base[0].x + base[1].x; |
1023 | b = base[1].x + base[2].x; |
1024 | base[3].x = b / 2; |
1025 | base[2].x = ( a + b ) / 4; |
1026 | base[1].x = a / 2; |
1027 | |
1028 | base[4].y = base[2].y; |
1029 | a = base[0].y + base[1].y; |
1030 | b = base[1].y + base[2].y; |
1031 | base[3].y = b / 2; |
1032 | base[2].y = ( a + b ) / 4; |
1033 | base[1].y = a / 2; |
1034 | } |
1035 | |
1036 | |
1037 | /* This function is exactly the same as the one */ |
1038 | /* in the smooth renderer. It splits a cubic */ |
1039 | /* into two cubics exactly half way at t = 0.5. */ |
1040 | static void |
1041 | split_cubic( FT_26D6_Vec* base ) |
1042 | { |
1043 | FT_26D6 a, b, c; |
1044 | |
1045 | |
1046 | base[6].x = base[3].x; |
1047 | a = base[0].x + base[1].x; |
1048 | b = base[1].x + base[2].x; |
1049 | c = base[2].x + base[3].x; |
1050 | base[5].x = c / 2; |
1051 | c += b; |
1052 | base[4].x = c / 4; |
1053 | base[1].x = a / 2; |
1054 | a += b; |
1055 | base[2].x = a / 4; |
1056 | base[3].x = ( a + c ) / 8; |
1057 | |
1058 | base[6].y = base[3].y; |
1059 | a = base[0].y + base[1].y; |
1060 | b = base[1].y + base[2].y; |
1061 | c = base[2].y + base[3].y; |
1062 | base[5].y = c / 2; |
1063 | c += b; |
1064 | base[4].y = c / 4; |
1065 | base[1].y = a / 2; |
1066 | a += b; |
1067 | base[2].y = a / 4; |
1068 | base[3].y = ( a + c ) / 8; |
1069 | } |
1070 | |
1071 | |
1072 | /* Split a conic Bezier curve into a number of lines */ |
1073 | /* and add them to `out'. */ |
1074 | /* */ |
1075 | /* This function uses recursion; we thus need */ |
1076 | /* parameter `max_splits' for stopping. */ |
1077 | static FT_Error |
1078 | split_sdf_conic( FT_Memory memory, |
1079 | FT_26D6_Vec* control_points, |
1080 | FT_UInt max_splits, |
1081 | SDF_Edge** out ) |
1082 | { |
1083 | FT_Error error = FT_Err_Ok; |
1084 | FT_26D6_Vec cpos[5]; |
1085 | SDF_Edge* left,* right; |
1086 | |
1087 | |
1088 | if ( !memory || !out ) |
1089 | { |
1090 | error = FT_THROW( Invalid_Argument ); |
1091 | goto Exit; |
1092 | } |
1093 | |
1094 | /* split conic outline */ |
1095 | cpos[0] = control_points[0]; |
1096 | cpos[1] = control_points[1]; |
1097 | cpos[2] = control_points[2]; |
1098 | |
1099 | split_conic( cpos ); |
1100 | |
1101 | /* If max number of splits is done */ |
1102 | /* then stop and add the lines to */ |
1103 | /* the list. */ |
1104 | if ( max_splits <= 2 ) |
1105 | goto Append; |
1106 | |
1107 | /* Otherwise keep splitting. */ |
1108 | FT_CALL( split_sdf_conic( memory, &cpos[0], max_splits / 2, out ) ); |
1109 | FT_CALL( split_sdf_conic( memory, &cpos[2], max_splits / 2, out ) ); |
1110 | |
1111 | /* [NOTE]: This is not an efficient way of */ |
1112 | /* splitting the curve. Check the deviation */ |
1113 | /* instead and stop if the deviation is less */ |
1114 | /* than a pixel. */ |
1115 | |
1116 | goto Exit; |
1117 | |
1118 | Append: |
1119 | /* Do allocation and add the lines to the list. */ |
1120 | |
1121 | FT_CALL( sdf_edge_new( memory, &left ) ); |
1122 | FT_CALL( sdf_edge_new( memory, &right ) ); |
1123 | |
1124 | left->start_pos = cpos[0]; |
1125 | left->end_pos = cpos[2]; |
1126 | left->edge_type = SDF_EDGE_LINE; |
1127 | |
1128 | right->start_pos = cpos[2]; |
1129 | right->end_pos = cpos[4]; |
1130 | right->edge_type = SDF_EDGE_LINE; |
1131 | |
1132 | left->next = right; |
1133 | right->next = (*out); |
1134 | *out = left; |
1135 | |
1136 | Exit: |
1137 | return error; |
1138 | } |
1139 | |
1140 | |
1141 | /* Split a cubic Bezier curve into a number of lines */ |
1142 | /* and add them to `out`. */ |
1143 | /* */ |
1144 | /* This function uses recursion; we thus need */ |
1145 | /* parameter `max_splits' for stopping. */ |
1146 | static FT_Error |
1147 | split_sdf_cubic( FT_Memory memory, |
1148 | FT_26D6_Vec* control_points, |
1149 | FT_UInt max_splits, |
1150 | SDF_Edge** out ) |
1151 | { |
1152 | FT_Error error = FT_Err_Ok; |
1153 | FT_26D6_Vec cpos[7]; |
1154 | SDF_Edge* left, *right; |
1155 | const FT_26D6 threshold = ONE_PIXEL / 4; |
1156 | |
1157 | |
1158 | if ( !memory || !out ) |
1159 | { |
1160 | error = FT_THROW( Invalid_Argument ); |
1161 | goto Exit; |
1162 | } |
1163 | |
1164 | /* split the cubic */ |
1165 | cpos[0] = control_points[0]; |
1166 | cpos[1] = control_points[1]; |
1167 | cpos[2] = control_points[2]; |
1168 | cpos[3] = control_points[3]; |
1169 | |
1170 | /* If the segment is flat enough we won't get any benefit by */ |
1171 | /* splitting it further, so we can just stop splitting. */ |
1172 | /* */ |
1173 | /* Check the deviation of the Bezier curve and stop if it is */ |
1174 | /* smaller than the pre-defined `threshold` value. */ |
1175 | if ( FT_ABS( 2 * cpos[0].x - 3 * cpos[1].x + cpos[3].x ) < threshold && |
1176 | FT_ABS( 2 * cpos[0].y - 3 * cpos[1].y + cpos[3].y ) < threshold && |
1177 | FT_ABS( cpos[0].x - 3 * cpos[2].x + 2 * cpos[3].x ) < threshold && |
1178 | FT_ABS( cpos[0].y - 3 * cpos[2].y + 2 * cpos[3].y ) < threshold ) |
1179 | { |
1180 | split_cubic( cpos ); |
1181 | goto Append; |
1182 | } |
1183 | |
1184 | split_cubic( cpos ); |
1185 | |
1186 | /* If max number of splits is done */ |
1187 | /* then stop and add the lines to */ |
1188 | /* the list. */ |
1189 | if ( max_splits <= 2 ) |
1190 | goto Append; |
1191 | |
1192 | /* Otherwise keep splitting. */ |
1193 | FT_CALL( split_sdf_cubic( memory, &cpos[0], max_splits / 2, out ) ); |
1194 | FT_CALL( split_sdf_cubic( memory, &cpos[3], max_splits / 2, out ) ); |
1195 | |
1196 | /* [NOTE]: This is not an efficient way of */ |
1197 | /* splitting the curve. Check the deviation */ |
1198 | /* instead and stop if the deviation is less */ |
1199 | /* than a pixel. */ |
1200 | |
1201 | goto Exit; |
1202 | |
1203 | Append: |
1204 | /* Do allocation and add the lines to the list. */ |
1205 | |
1206 | FT_CALL( sdf_edge_new( memory, &left) ); |
1207 | FT_CALL( sdf_edge_new( memory, &right) ); |
1208 | |
1209 | left->start_pos = cpos[0]; |
1210 | left->end_pos = cpos[3]; |
1211 | left->edge_type = SDF_EDGE_LINE; |
1212 | |
1213 | right->start_pos = cpos[3]; |
1214 | right->end_pos = cpos[6]; |
1215 | right->edge_type = SDF_EDGE_LINE; |
1216 | |
1217 | left->next = right; |
1218 | right->next = (*out); |
1219 | *out = left; |
1220 | |
1221 | Exit: |
1222 | return error; |
1223 | } |
1224 | |
1225 | |
1226 | /* Subdivide an entire shape into line segments */ |
1227 | /* such that it doesn't look visually different */ |
1228 | /* from the original curve. */ |
1229 | static FT_Error |
1230 | split_sdf_shape( SDF_Shape* shape ) |
1231 | { |
1232 | FT_Error error = FT_Err_Ok; |
1233 | FT_Memory memory; |
1234 | |
1235 | SDF_Contour* contours; |
1236 | SDF_Contour* new_contours = NULL; |
1237 | |
1238 | |
1239 | if ( !shape || !shape->memory ) |
1240 | { |
1241 | error = FT_THROW( Invalid_Argument ); |
1242 | goto Exit; |
1243 | } |
1244 | |
1245 | contours = shape->contours; |
1246 | memory = shape->memory; |
1247 | |
1248 | /* for each contour */ |
1249 | while ( contours ) |
1250 | { |
1251 | SDF_Edge* edges = contours->edges; |
1252 | SDF_Edge* new_edges = NULL; |
1253 | |
1254 | SDF_Contour* tempc; |
1255 | |
1256 | |
1257 | /* for each edge */ |
1258 | while ( edges ) |
1259 | { |
1260 | SDF_Edge* edge = edges; |
1261 | SDF_Edge* temp; |
1262 | |
1263 | switch ( edge->edge_type ) |
1264 | { |
1265 | case SDF_EDGE_LINE: |
1266 | /* Just create a duplicate edge in case */ |
1267 | /* it is a line. We can use the same edge. */ |
1268 | FT_CALL( sdf_edge_new( memory, &temp ) ); |
1269 | |
1270 | ft_memcpy( temp, edge, sizeof ( *edge ) ); |
1271 | |
1272 | temp->next = new_edges; |
1273 | new_edges = temp; |
1274 | break; |
1275 | |
1276 | case SDF_EDGE_CONIC: |
1277 | /* Subdivide the curve and add it to the list. */ |
1278 | { |
1279 | FT_26D6_Vec ctrls[3]; |
1280 | FT_26D6 dx, dy; |
1281 | FT_UInt num_splits; |
1282 | |
1283 | |
1284 | ctrls[0] = edge->start_pos; |
1285 | ctrls[1] = edge->control_a; |
1286 | ctrls[2] = edge->end_pos; |
1287 | |
1288 | dx = FT_ABS( ctrls[2].x + ctrls[0].x - 2 * ctrls[1].x ); |
1289 | dy = FT_ABS( ctrls[2].y + ctrls[0].y - 2 * ctrls[1].y ); |
1290 | if ( dx < dy ) |
1291 | dx = dy; |
1292 | |
1293 | /* Calculate the number of necessary bisections. Each */ |
1294 | /* bisection causes a four-fold reduction of the deviation, */ |
1295 | /* hence we bisect the Bezier curve until the deviation */ |
1296 | /* becomes less than 1/8 of a pixel. For more details */ |
1297 | /* check file `ftgrays.c`. */ |
1298 | num_splits = 1; |
1299 | while ( dx > ONE_PIXEL / 8 ) |
1300 | { |
1301 | dx >>= 2; |
1302 | num_splits <<= 1; |
1303 | } |
1304 | |
1305 | error = split_sdf_conic( memory, ctrls, num_splits, &new_edges ); |
1306 | } |
1307 | break; |
1308 | |
1309 | case SDF_EDGE_CUBIC: |
1310 | /* Subdivide the curve and add it to the list. */ |
1311 | { |
1312 | FT_26D6_Vec ctrls[4]; |
1313 | |
1314 | |
1315 | ctrls[0] = edge->start_pos; |
1316 | ctrls[1] = edge->control_a; |
1317 | ctrls[2] = edge->control_b; |
1318 | ctrls[3] = edge->end_pos; |
1319 | |
1320 | error = split_sdf_cubic( memory, ctrls, 32, &new_edges ); |
1321 | } |
1322 | break; |
1323 | |
1324 | default: |
1325 | error = FT_THROW( Invalid_Argument ); |
1326 | } |
1327 | |
1328 | if ( error != FT_Err_Ok ) |
1329 | goto Exit; |
1330 | |
1331 | edges = edges->next; |
1332 | } |
1333 | |
1334 | /* add to the contours list */ |
1335 | FT_CALL( sdf_contour_new( memory, &tempc ) ); |
1336 | |
1337 | tempc->next = new_contours; |
1338 | tempc->edges = new_edges; |
1339 | new_contours = tempc; |
1340 | new_edges = NULL; |
1341 | |
1342 | /* deallocate the contour */ |
1343 | tempc = contours; |
1344 | contours = contours->next; |
1345 | |
1346 | sdf_contour_done( memory, &tempc ); |
1347 | } |
1348 | |
1349 | shape->contours = new_contours; |
1350 | |
1351 | Exit: |
1352 | return error; |
1353 | } |
1354 | |
1355 | |
1356 | /************************************************************************** |
1357 | * |
1358 | * for debugging |
1359 | * |
1360 | */ |
1361 | |
1362 | #ifdef FT_DEBUG_LEVEL_TRACE |
1363 | |
1364 | static void |
1365 | sdf_shape_dump( SDF_Shape* shape ) |
1366 | { |
1367 | FT_UInt num_contours = 0; |
1368 | |
1369 | FT_UInt total_edges = 0; |
1370 | FT_UInt total_lines = 0; |
1371 | FT_UInt total_conic = 0; |
1372 | FT_UInt total_cubic = 0; |
1373 | |
1374 | SDF_Contour* contour_list; |
1375 | |
1376 | |
1377 | if ( !shape ) |
1378 | { |
1379 | FT_TRACE5(( "sdf_shape_dump: null shape\n" )); |
1380 | return; |
1381 | } |
1382 | |
1383 | contour_list = shape->contours; |
1384 | |
1385 | FT_TRACE5(( "sdf_shape_dump (values are in 26.6 format):\n" )); |
1386 | |
1387 | while ( contour_list ) |
1388 | { |
1389 | FT_UInt num_edges = 0; |
1390 | SDF_Edge* edge_list; |
1391 | SDF_Contour* contour = contour_list; |
1392 | |
1393 | |
1394 | FT_TRACE5(( " Contour %d\n" , num_contours )); |
1395 | |
1396 | edge_list = contour->edges; |
1397 | |
1398 | while ( edge_list ) |
1399 | { |
1400 | SDF_Edge* edge = edge_list; |
1401 | |
1402 | |
1403 | FT_TRACE5(( " %3d: " , num_edges )); |
1404 | |
1405 | switch ( edge->edge_type ) |
1406 | { |
1407 | case SDF_EDGE_LINE: |
1408 | FT_TRACE5(( "Line: (%ld, %ld) -- (%ld, %ld)\n" , |
1409 | edge->start_pos.x, edge->start_pos.y, |
1410 | edge->end_pos.x, edge->end_pos.y )); |
1411 | total_lines++; |
1412 | break; |
1413 | |
1414 | case SDF_EDGE_CONIC: |
1415 | FT_TRACE5(( "Conic: (%ld, %ld) .. (%ld, %ld) .. (%ld, %ld)\n" , |
1416 | edge->start_pos.x, edge->start_pos.y, |
1417 | edge->control_a.x, edge->control_a.y, |
1418 | edge->end_pos.x, edge->end_pos.y )); |
1419 | total_conic++; |
1420 | break; |
1421 | |
1422 | case SDF_EDGE_CUBIC: |
1423 | FT_TRACE5(( "Cubic: (%ld, %ld) .. (%ld, %ld)" |
1424 | " .. (%ld, %ld) .. (%ld %ld)\n" , |
1425 | edge->start_pos.x, edge->start_pos.y, |
1426 | edge->control_a.x, edge->control_a.y, |
1427 | edge->control_b.x, edge->control_b.y, |
1428 | edge->end_pos.x, edge->end_pos.y )); |
1429 | total_cubic++; |
1430 | break; |
1431 | |
1432 | default: |
1433 | break; |
1434 | } |
1435 | |
1436 | num_edges++; |
1437 | total_edges++; |
1438 | edge_list = edge_list->next; |
1439 | } |
1440 | |
1441 | num_contours++; |
1442 | contour_list = contour_list->next; |
1443 | } |
1444 | |
1445 | FT_TRACE5(( "\n" )); |
1446 | FT_TRACE5(( " total number of contours = %d\n" , num_contours )); |
1447 | FT_TRACE5(( " total number of edges = %d\n" , total_edges )); |
1448 | FT_TRACE5(( " |__lines = %d\n" , total_lines )); |
1449 | FT_TRACE5(( " |__conic = %d\n" , total_conic )); |
1450 | FT_TRACE5(( " |__cubic = %d\n" , total_cubic )); |
1451 | } |
1452 | |
1453 | #endif /* FT_DEBUG_LEVEL_TRACE */ |
1454 | |
1455 | |
1456 | /************************************************************************** |
1457 | * |
1458 | * math functions |
1459 | * |
1460 | */ |
1461 | |
1462 | #if !USE_NEWTON_FOR_CONIC |
1463 | |
1464 | /* [NOTE]: All the functions below down until rasterizer */ |
1465 | /* can be avoided if we decide to subdivide the */ |
1466 | /* curve into lines. */ |
1467 | |
1468 | /* This function uses Newton's iteration to find */ |
1469 | /* the cube root of a fixed-point integer. */ |
1470 | static FT_16D16 |
1471 | cube_root( FT_16D16 val ) |
1472 | { |
1473 | /* [IMPORTANT]: This function is not good as it may */ |
1474 | /* not break, so use a lookup table instead. Or we */ |
1475 | /* can use an algorithm similar to `square_root`. */ |
1476 | |
1477 | FT_Int v, g, c; |
1478 | |
1479 | |
1480 | if ( val == 0 || |
1481 | val == -FT_INT_16D16( 1 ) || |
1482 | val == FT_INT_16D16( 1 ) ) |
1483 | return val; |
1484 | |
1485 | v = val < 0 ? -val : val; |
1486 | g = square_root( v ); |
1487 | c = 0; |
1488 | |
1489 | while ( 1 ) |
1490 | { |
1491 | c = FT_MulFix( FT_MulFix( g, g ), g ) - v; |
1492 | c = FT_DivFix( c, 3 * FT_MulFix( g, g ) ); |
1493 | |
1494 | g -= c; |
1495 | |
1496 | if ( ( c < 0 ? -c : c ) < 30 ) |
1497 | break; |
1498 | } |
1499 | |
1500 | return val < 0 ? -g : g; |
1501 | } |
1502 | |
1503 | |
1504 | /* Calculate the perpendicular by using '1 - base^2'. */ |
1505 | /* Then use arctan to compute the angle. */ |
1506 | static FT_16D16 |
1507 | arc_cos( FT_16D16 val ) |
1508 | { |
1509 | FT_16D16 p; |
1510 | FT_16D16 b = val; |
1511 | FT_16D16 one = FT_INT_16D16( 1 ); |
1512 | |
1513 | |
1514 | if ( b > one ) |
1515 | b = one; |
1516 | if ( b < -one ) |
1517 | b = -one; |
1518 | |
1519 | p = one - FT_MulFix( b, b ); |
1520 | p = square_root( p ); |
1521 | |
1522 | return FT_Atan2( b, p ); |
1523 | } |
1524 | |
1525 | |
1526 | /* Compute roots of a quadratic polynomial, assign them to `out`, */ |
1527 | /* and return number of real roots. */ |
1528 | /* */ |
1529 | /* The procedure can be found at */ |
1530 | /* */ |
1531 | /* https://mathworld.wolfram.com/QuadraticFormula.html */ |
1532 | static FT_UShort |
1533 | solve_quadratic_equation( FT_26D6 a, |
1534 | FT_26D6 b, |
1535 | FT_26D6 c, |
1536 | FT_16D16 out[2] ) |
1537 | { |
1538 | FT_16D16 discriminant = 0; |
1539 | |
1540 | |
1541 | a = FT_26D6_16D16( a ); |
1542 | b = FT_26D6_16D16( b ); |
1543 | c = FT_26D6_16D16( c ); |
1544 | |
1545 | if ( a == 0 ) |
1546 | { |
1547 | if ( b == 0 ) |
1548 | return 0; |
1549 | else |
1550 | { |
1551 | out[0] = FT_DivFix( -c, b ); |
1552 | |
1553 | return 1; |
1554 | } |
1555 | } |
1556 | |
1557 | discriminant = FT_MulFix( b, b ) - 4 * FT_MulFix( a, c ); |
1558 | |
1559 | if ( discriminant < 0 ) |
1560 | return 0; |
1561 | else if ( discriminant == 0 ) |
1562 | { |
1563 | out[0] = FT_DivFix( -b, 2 * a ); |
1564 | |
1565 | return 1; |
1566 | } |
1567 | else |
1568 | { |
1569 | discriminant = square_root( discriminant ); |
1570 | |
1571 | out[0] = FT_DivFix( -b + discriminant, 2 * a ); |
1572 | out[1] = FT_DivFix( -b - discriminant, 2 * a ); |
1573 | |
1574 | return 2; |
1575 | } |
1576 | } |
1577 | |
1578 | |
1579 | /* Compute roots of a cubic polynomial, assign them to `out`, */ |
1580 | /* and return number of real roots. */ |
1581 | /* */ |
1582 | /* The procedure can be found at */ |
1583 | /* */ |
1584 | /* https://mathworld.wolfram.com/CubicFormula.html */ |
1585 | static FT_UShort |
1586 | solve_cubic_equation( FT_26D6 a, |
1587 | FT_26D6 b, |
1588 | FT_26D6 c, |
1589 | FT_26D6 d, |
1590 | FT_16D16 out[3] ) |
1591 | { |
1592 | FT_16D16 q = 0; /* intermediate */ |
1593 | FT_16D16 r = 0; /* intermediate */ |
1594 | |
1595 | FT_16D16 a2 = b; /* x^2 coefficients */ |
1596 | FT_16D16 a1 = c; /* x coefficients */ |
1597 | FT_16D16 a0 = d; /* constant */ |
1598 | |
1599 | FT_16D16 q3 = 0; |
1600 | FT_16D16 r2 = 0; |
1601 | FT_16D16 a23 = 0; |
1602 | FT_16D16 a22 = 0; |
1603 | FT_16D16 a1x2 = 0; |
1604 | |
1605 | |
1606 | /* cutoff value for `a` to be a cubic, otherwise solve quadratic */ |
1607 | if ( a == 0 || FT_ABS( a ) < 16 ) |
1608 | return solve_quadratic_equation( b, c, d, out ); |
1609 | |
1610 | if ( d == 0 ) |
1611 | { |
1612 | out[0] = 0; |
1613 | |
1614 | return solve_quadratic_equation( a, b, c, out + 1 ) + 1; |
1615 | } |
1616 | |
1617 | /* normalize the coefficients; this also makes them 16.16 */ |
1618 | a2 = FT_DivFix( a2, a ); |
1619 | a1 = FT_DivFix( a1, a ); |
1620 | a0 = FT_DivFix( a0, a ); |
1621 | |
1622 | /* compute intermediates */ |
1623 | a1x2 = FT_MulFix( a1, a2 ); |
1624 | a22 = FT_MulFix( a2, a2 ); |
1625 | a23 = FT_MulFix( a22, a2 ); |
1626 | |
1627 | q = ( 3 * a1 - a22 ) / 9; |
1628 | r = ( 9 * a1x2 - 27 * a0 - 2 * a23 ) / 54; |
1629 | |
1630 | /* [BUG]: `q3` and `r2` still cause underflow. */ |
1631 | |
1632 | q3 = FT_MulFix( q, q ); |
1633 | q3 = FT_MulFix( q3, q ); |
1634 | |
1635 | r2 = FT_MulFix( r, r ); |
1636 | |
1637 | if ( q3 < 0 && r2 < -q3 ) |
1638 | { |
1639 | FT_16D16 t = 0; |
1640 | |
1641 | |
1642 | q3 = square_root( -q3 ); |
1643 | t = FT_DivFix( r, q3 ); |
1644 | |
1645 | if ( t > ( 1 << 16 ) ) |
1646 | t = ( 1 << 16 ); |
1647 | if ( t < -( 1 << 16 ) ) |
1648 | t = -( 1 << 16 ); |
1649 | |
1650 | t = arc_cos( t ); |
1651 | a2 /= 3; |
1652 | q = 2 * square_root( -q ); |
1653 | |
1654 | out[0] = FT_MulFix( q, FT_Cos( t / 3 ) ) - a2; |
1655 | out[1] = FT_MulFix( q, FT_Cos( ( t + FT_ANGLE_PI * 2 ) / 3 ) ) - a2; |
1656 | out[2] = FT_MulFix( q, FT_Cos( ( t + FT_ANGLE_PI * 4 ) / 3 ) ) - a2; |
1657 | |
1658 | return 3; |
1659 | } |
1660 | |
1661 | else if ( r2 == -q3 ) |
1662 | { |
1663 | FT_16D16 s = 0; |
1664 | |
1665 | |
1666 | s = cube_root( r ); |
1667 | a2 /= -3; |
1668 | |
1669 | out[0] = a2 + ( 2 * s ); |
1670 | out[1] = a2 - s; |
1671 | |
1672 | return 2; |
1673 | } |
1674 | |
1675 | else |
1676 | { |
1677 | FT_16D16 s = 0; |
1678 | FT_16D16 t = 0; |
1679 | FT_16D16 dis = 0; |
1680 | |
1681 | |
1682 | if ( q3 == 0 ) |
1683 | dis = FT_ABS( r ); |
1684 | else |
1685 | dis = square_root( q3 + r2 ); |
1686 | |
1687 | s = cube_root( r + dis ); |
1688 | t = cube_root( r - dis ); |
1689 | a2 /= -3; |
1690 | out[0] = ( a2 + ( s + t ) ); |
1691 | |
1692 | return 1; |
1693 | } |
1694 | } |
1695 | |
1696 | #endif /* !USE_NEWTON_FOR_CONIC */ |
1697 | |
1698 | |
1699 | /*************************************************************************/ |
1700 | /*************************************************************************/ |
1701 | /** **/ |
1702 | /** RASTERIZER **/ |
1703 | /** **/ |
1704 | /*************************************************************************/ |
1705 | /*************************************************************************/ |
1706 | |
1707 | /************************************************************************** |
1708 | * |
1709 | * @Function: |
1710 | * resolve_corner |
1711 | * |
1712 | * @Description: |
1713 | * At some places on the grid two edges can give opposite directions; |
1714 | * this happens when the closest point is on one of the endpoint. In |
1715 | * that case we need to check the proper sign. |
1716 | * |
1717 | * This can be visualized by an example: |
1718 | * |
1719 | * ``` |
1720 | * x |
1721 | * |
1722 | * o |
1723 | * ^ \ |
1724 | * / \ |
1725 | * / \ |
1726 | * (a) / \ (b) |
1727 | * / \ |
1728 | * / \ |
1729 | * / v |
1730 | * ``` |
1731 | * |
1732 | * Suppose `x` is the point whose shortest distance from an arbitrary |
1733 | * contour we want to find out. It is clear that `o` is the nearest |
1734 | * point on the contour. Now to determine the sign we do a cross |
1735 | * product of the shortest distance vector and the edge direction, i.e., |
1736 | * |
1737 | * ``` |
1738 | * => sign = cross(x - o, direction(a)) |
1739 | * ``` |
1740 | * |
1741 | * Using the right hand thumb rule we can see that the sign will be |
1742 | * positive. |
1743 | * |
1744 | * If we use `b', however, we have |
1745 | * |
1746 | * ``` |
1747 | * => sign = cross(x - o, direction(b)) |
1748 | * ``` |
1749 | * |
1750 | * In this case the sign will be negative. To determine the correct |
1751 | * sign we thus divide the plane in two halves and check which plane the |
1752 | * point lies in. |
1753 | * |
1754 | * ``` |
1755 | * | |
1756 | * x | |
1757 | * | |
1758 | * o |
1759 | * ^|\ |
1760 | * / | \ |
1761 | * / | \ |
1762 | * (a) / | \ (b) |
1763 | * / | \ |
1764 | * / \ |
1765 | * / v |
1766 | * ``` |
1767 | * |
1768 | * We can see that `x` lies in the plane of `a`, so we take the sign |
1769 | * determined by `a`. This test can be easily done by calculating the |
1770 | * orthogonality and taking the greater one. |
1771 | * |
1772 | * The orthogonality is simply the sinus of the two vectors (i.e., |
1773 | * x - o) and the corresponding direction. We efficiently pre-compute |
1774 | * the orthogonality with the corresponding `get_min_distance_*` |
1775 | * functions. |
1776 | * |
1777 | * @Input: |
1778 | * sdf1 :: |
1779 | * First signed distance (can be any of `a` or `b`). |
1780 | * |
1781 | * sdf1 :: |
1782 | * Second signed distance (can be any of `a` or `b`). |
1783 | * |
1784 | * @Return: |
1785 | * The correct signed distance, which is computed by using the above |
1786 | * algorithm. |
1787 | * |
1788 | * @Note: |
1789 | * The function does not care about the actual distance, it simply |
1790 | * returns the signed distance which has a larger cross product. As a |
1791 | * consequence, this function should not be used if the two distances |
1792 | * are fairly apart. In that case simply use the signed distance with |
1793 | * a shorter absolute distance. |
1794 | * |
1795 | */ |
1796 | static SDF_Signed_Distance |
1797 | resolve_corner( SDF_Signed_Distance sdf1, |
1798 | SDF_Signed_Distance sdf2 ) |
1799 | { |
1800 | return FT_ABS( sdf1.cross ) > FT_ABS( sdf2.cross ) ? sdf1 : sdf2; |
1801 | } |
1802 | |
1803 | |
1804 | /************************************************************************** |
1805 | * |
1806 | * @Function: |
1807 | * get_min_distance_line |
1808 | * |
1809 | * @Description: |
1810 | * Find the shortest distance from the `line` segment to a given `point` |
1811 | * and assign it to `out`. Use it for line segments only. |
1812 | * |
1813 | * @Input: |
1814 | * line :: |
1815 | * The line segment to which the shortest distance is to be computed. |
1816 | * |
1817 | * point :: |
1818 | * Point from which the shortest distance is to be computed. |
1819 | * |
1820 | * @Output: |
1821 | * out :: |
1822 | * Signed distance from `point` to `line`. |
1823 | * |
1824 | * @Return: |
1825 | * FreeType error, 0 means success. |
1826 | * |
1827 | * @Note: |
1828 | * The `line' parameter must have an edge type of `SDF_EDGE_LINE`. |
1829 | * |
1830 | */ |
1831 | static FT_Error |
1832 | get_min_distance_line( SDF_Edge* line, |
1833 | FT_26D6_Vec point, |
1834 | SDF_Signed_Distance* out ) |
1835 | { |
1836 | /* |
1837 | * In order to calculate the shortest distance from a point to |
1838 | * a line segment, we do the following. Let's assume that |
1839 | * |
1840 | * ``` |
1841 | * a = start point of the line segment |
1842 | * b = end point of the line segment |
1843 | * p = point from which shortest distance is to be calculated |
1844 | * ``` |
1845 | * |
1846 | * (1) Write the parametric equation of the line. |
1847 | * |
1848 | * ``` |
1849 | * point_on_line = a + (b - a) * t (t is the factor) |
1850 | * ``` |
1851 | * |
1852 | * (2) Find the projection of point `p` on the line. The projection |
1853 | * will be perpendicular to the line, which allows us to get the |
1854 | * solution by making the dot product zero. |
1855 | * |
1856 | * ``` |
1857 | * (point_on_line - a) . (p - point_on_line) = 0 |
1858 | * |
1859 | * (point_on_line) |
1860 | * (a) x-------o----------------x (b) |
1861 | * |_| |
1862 | * | |
1863 | * | |
1864 | * (p) |
1865 | * ``` |
1866 | * |
1867 | * (3) Simplification of the above equation yields the factor of |
1868 | * `point_on_line`: |
1869 | * |
1870 | * ``` |
1871 | * t = ((p - a) . (b - a)) / |b - a|^2 |
1872 | * ``` |
1873 | * |
1874 | * (4) We clamp factor `t` between [0.0f, 1.0f] because `point_on_line` |
1875 | * can be outside of the line segment: |
1876 | * |
1877 | * ``` |
1878 | * (point_on_line) |
1879 | * (a) x------------------------x (b) -----o--- |
1880 | * |_| |
1881 | * | |
1882 | * | |
1883 | * (p) |
1884 | * ``` |
1885 | * |
1886 | * (5) Finally, the distance we are interested in is |
1887 | * |
1888 | * ``` |
1889 | * |point_on_line - p| |
1890 | * ``` |
1891 | */ |
1892 | |
1893 | FT_Error error = FT_Err_Ok; |
1894 | |
1895 | FT_Vector a; /* start position */ |
1896 | FT_Vector b; /* end position */ |
1897 | FT_Vector p; /* current point */ |
1898 | |
1899 | FT_26D6_Vec line_segment; /* `b` - `a` */ |
1900 | FT_26D6_Vec p_sub_a; /* `p` - `a` */ |
1901 | |
1902 | FT_26D6 sq_line_length; /* squared length of `line_segment` */ |
1903 | FT_16D16 factor; /* factor of the nearest point */ |
1904 | FT_26D6 cross; /* used to determine sign */ |
1905 | |
1906 | FT_16D16_Vec nearest_point; /* `point_on_line` */ |
1907 | FT_16D16_Vec nearest_vector; /* `p` - `nearest_point` */ |
1908 | |
1909 | |
1910 | if ( !line || !out ) |
1911 | { |
1912 | error = FT_THROW( Invalid_Argument ); |
1913 | goto Exit; |
1914 | } |
1915 | |
1916 | if ( line->edge_type != SDF_EDGE_LINE ) |
1917 | { |
1918 | error = FT_THROW( Invalid_Argument ); |
1919 | goto Exit; |
1920 | } |
1921 | |
1922 | a = line->start_pos; |
1923 | b = line->end_pos; |
1924 | p = point; |
1925 | |
1926 | line_segment.x = b.x - a.x; |
1927 | line_segment.y = b.y - a.y; |
1928 | |
1929 | p_sub_a.x = p.x - a.x; |
1930 | p_sub_a.y = p.y - a.y; |
1931 | |
1932 | sq_line_length = ( line_segment.x * line_segment.x ) / 64 + |
1933 | ( line_segment.y * line_segment.y ) / 64; |
1934 | |
1935 | /* currently factor is 26.6 */ |
1936 | factor = ( p_sub_a.x * line_segment.x ) / 64 + |
1937 | ( p_sub_a.y * line_segment.y ) / 64; |
1938 | |
1939 | /* now factor is 16.16 */ |
1940 | factor = FT_DivFix( factor, sq_line_length ); |
1941 | |
1942 | /* clamp the factor between 0.0 and 1.0 in fixed-point */ |
1943 | if ( factor > FT_INT_16D16( 1 ) ) |
1944 | factor = FT_INT_16D16( 1 ); |
1945 | if ( factor < 0 ) |
1946 | factor = 0; |
1947 | |
1948 | nearest_point.x = FT_MulFix( FT_26D6_16D16( line_segment.x ), |
1949 | factor ); |
1950 | nearest_point.y = FT_MulFix( FT_26D6_16D16( line_segment.y ), |
1951 | factor ); |
1952 | |
1953 | nearest_point.x = FT_26D6_16D16( a.x ) + nearest_point.x; |
1954 | nearest_point.y = FT_26D6_16D16( a.y ) + nearest_point.y; |
1955 | |
1956 | nearest_vector.x = nearest_point.x - FT_26D6_16D16( p.x ); |
1957 | nearest_vector.y = nearest_point.y - FT_26D6_16D16( p.y ); |
1958 | |
1959 | cross = FT_MulFix( nearest_vector.x, line_segment.y ) - |
1960 | FT_MulFix( nearest_vector.y, line_segment.x ); |
1961 | |
1962 | /* assign the output */ |
1963 | out->sign = cross < 0 ? 1 : -1; |
1964 | out->distance = VECTOR_LENGTH_16D16( nearest_vector ); |
1965 | |
1966 | /* Instead of finding `cross` for checking corner we */ |
1967 | /* directly set it here. This is more efficient */ |
1968 | /* because if the distance is perpendicular we can */ |
1969 | /* directly set it to 1. */ |
1970 | if ( factor != 0 && factor != FT_INT_16D16( 1 ) ) |
1971 | out->cross = FT_INT_16D16( 1 ); |
1972 | else |
1973 | { |
1974 | /* [OPTIMIZATION]: Pre-compute this direction. */ |
1975 | /* If not perpendicular then compute `cross`. */ |
1976 | FT_Vector_NormLen( &line_segment ); |
1977 | FT_Vector_NormLen( &nearest_vector ); |
1978 | |
1979 | out->cross = FT_MulFix( line_segment.x, nearest_vector.y ) - |
1980 | FT_MulFix( line_segment.y, nearest_vector.x ); |
1981 | } |
1982 | |
1983 | Exit: |
1984 | return error; |
1985 | } |
1986 | |
1987 | |
1988 | /************************************************************************** |
1989 | * |
1990 | * @Function: |
1991 | * get_min_distance_conic |
1992 | * |
1993 | * @Description: |
1994 | * Find the shortest distance from the `conic` Bezier curve to a given |
1995 | * `point` and assign it to `out`. Use it for conic/quadratic curves |
1996 | * only. |
1997 | * |
1998 | * @Input: |
1999 | * conic :: |
2000 | * The conic Bezier curve to which the shortest distance is to be |
2001 | * computed. |
2002 | * |
2003 | * point :: |
2004 | * Point from which the shortest distance is to be computed. |
2005 | * |
2006 | * @Output: |
2007 | * out :: |
2008 | * Signed distance from `point` to `conic`. |
2009 | * |
2010 | * @Return: |
2011 | * FreeType error, 0 means success. |
2012 | * |
2013 | * @Note: |
2014 | * The `conic` parameter must have an edge type of `SDF_EDGE_CONIC`. |
2015 | * |
2016 | */ |
2017 | |
2018 | #if !USE_NEWTON_FOR_CONIC |
2019 | |
2020 | /* |
2021 | * The function uses an analytical method to find the shortest distance |
2022 | * which is faster than the Newton-Raphson method, but has underflows at |
2023 | * the moment. Use Newton's method if you can see artifacts in the SDF. |
2024 | */ |
2025 | static FT_Error |
2026 | get_min_distance_conic( SDF_Edge* conic, |
2027 | FT_26D6_Vec point, |
2028 | SDF_Signed_Distance* out ) |
2029 | { |
2030 | /* |
2031 | * The procedure to find the shortest distance from a point to a |
2032 | * quadratic Bezier curve is similar to the line segment algorithm. The |
2033 | * shortest distance is perpendicular to the Bezier curve; the only |
2034 | * difference from line is that there can be more than one |
2035 | * perpendicular, and we also have to check the endpoints, because the |
2036 | * perpendicular may not be the shortest. |
2037 | * |
2038 | * Let's assume that |
2039 | * ``` |
2040 | * p0 = first endpoint |
2041 | * p1 = control point |
2042 | * p2 = second endpoint |
2043 | * p = point from which shortest distance is to be calculated |
2044 | * ``` |
2045 | * |
2046 | * (1) The equation of a quadratic Bezier curve can be written as |
2047 | * |
2048 | * ``` |
2049 | * B(t) = (1 - t)^2 * p0 + 2(1 - t)t * p1 + t^2 * p2 |
2050 | * ``` |
2051 | * |
2052 | * with `t` a factor in the range [0.0f, 1.0f]. This equation can |
2053 | * be rewritten as |
2054 | * |
2055 | * ``` |
2056 | * B(t) = t^2 * (p0 - 2p1 + p2) + 2t * (p1 - p0) + p0 |
2057 | * ``` |
2058 | * |
2059 | * With |
2060 | * |
2061 | * ``` |
2062 | * A = p0 - 2p1 + p2 |
2063 | * B = p1 - p0 |
2064 | * ``` |
2065 | * |
2066 | * we have |
2067 | * |
2068 | * ``` |
2069 | * B(t) = t^2 * A + 2t * B + p0 |
2070 | * ``` |
2071 | * |
2072 | * (2) The derivative of the last equation above is |
2073 | * |
2074 | * ``` |
2075 | * B'(t) = 2 *(tA + B) |
2076 | * ``` |
2077 | * |
2078 | * (3) To find the shortest distance from `p` to `B(t)` we find the |
2079 | * point on the curve at which the shortest distance vector (i.e., |
2080 | * `B(t) - p`) and the direction (i.e., `B'(t)`) make 90 degrees. |
2081 | * In other words, we make the dot product zero. |
2082 | * |
2083 | * ``` |
2084 | * (B(t) - p) . (B'(t)) = 0 |
2085 | * (t^2 * A + 2t * B + p0 - p) . (2 * (tA + B)) = 0 |
2086 | * ``` |
2087 | * |
2088 | * After simplifying we get a cubic equation |
2089 | * |
2090 | * ``` |
2091 | * at^3 + bt^2 + ct + d = 0 |
2092 | * ``` |
2093 | * |
2094 | * with |
2095 | * |
2096 | * ``` |
2097 | * a = A.A |
2098 | * b = 3A.B |
2099 | * c = 2B.B + A.p0 - A.p |
2100 | * d = p0.B - p.B |
2101 | * ``` |
2102 | * |
2103 | * (4) Now the roots of the equation can be computed using 'Cardano's |
2104 | * Cubic formula'; we clamp the roots in the range [0.0f, 1.0f]. |
2105 | * |
2106 | * [note]: `B` and `B(t)` are different in the above equations. |
2107 | */ |
2108 | |
2109 | FT_Error error = FT_Err_Ok; |
2110 | |
2111 | FT_26D6_Vec aA, bB; /* A, B in the above comment */ |
2112 | FT_26D6_Vec nearest_point = { 0, 0 }; |
2113 | /* point on curve nearest to `point` */ |
2114 | FT_26D6_Vec direction; /* direction of curve at `nearest_point` */ |
2115 | |
2116 | FT_26D6_Vec p0, p1, p2; /* control points of a conic curve */ |
2117 | FT_26D6_Vec p; /* `point` to which shortest distance */ |
2118 | |
2119 | FT_26D6 a, b, c, d; /* cubic coefficients */ |
2120 | |
2121 | FT_16D16 roots[3] = { 0, 0, 0 }; /* real roots of the cubic eq. */ |
2122 | FT_16D16 min_factor; /* factor at `nearest_point` */ |
2123 | FT_16D16 cross; /* to determine the sign */ |
2124 | FT_16D16 min = FT_INT_MAX; /* shortest squared distance */ |
2125 | |
2126 | FT_UShort num_roots; /* number of real roots of cubic */ |
2127 | FT_UShort i; |
2128 | |
2129 | |
2130 | if ( !conic || !out ) |
2131 | { |
2132 | error = FT_THROW( Invalid_Argument ); |
2133 | goto Exit; |
2134 | } |
2135 | |
2136 | if ( conic->edge_type != SDF_EDGE_CONIC ) |
2137 | { |
2138 | error = FT_THROW( Invalid_Argument ); |
2139 | goto Exit; |
2140 | } |
2141 | |
2142 | p0 = conic->start_pos; |
2143 | p1 = conic->control_a; |
2144 | p2 = conic->end_pos; |
2145 | p = point; |
2146 | |
2147 | /* compute substitution coefficients */ |
2148 | aA.x = p0.x - 2 * p1.x + p2.x; |
2149 | aA.y = p0.y - 2 * p1.y + p2.y; |
2150 | |
2151 | bB.x = p1.x - p0.x; |
2152 | bB.y = p1.y - p0.y; |
2153 | |
2154 | /* compute cubic coefficients */ |
2155 | a = VEC_26D6_DOT( aA, aA ); |
2156 | |
2157 | b = 3 * VEC_26D6_DOT( aA, bB ); |
2158 | |
2159 | c = 2 * VEC_26D6_DOT( bB, bB ) + |
2160 | VEC_26D6_DOT( aA, p0 ) - |
2161 | VEC_26D6_DOT( aA, p ); |
2162 | |
2163 | d = VEC_26D6_DOT( p0, bB ) - |
2164 | VEC_26D6_DOT( p, bB ); |
2165 | |
2166 | /* find the roots */ |
2167 | num_roots = solve_cubic_equation( a, b, c, d, roots ); |
2168 | |
2169 | if ( num_roots == 0 ) |
2170 | { |
2171 | roots[0] = 0; |
2172 | roots[1] = FT_INT_16D16( 1 ); |
2173 | num_roots = 2; |
2174 | } |
2175 | |
2176 | /* [OPTIMIZATION]: Check the roots, clamp them and discard */ |
2177 | /* duplicate roots. */ |
2178 | |
2179 | /* convert these values to 16.16 for further computation */ |
2180 | aA.x = FT_26D6_16D16( aA.x ); |
2181 | aA.y = FT_26D6_16D16( aA.y ); |
2182 | |
2183 | bB.x = FT_26D6_16D16( bB.x ); |
2184 | bB.y = FT_26D6_16D16( bB.y ); |
2185 | |
2186 | p0.x = FT_26D6_16D16( p0.x ); |
2187 | p0.y = FT_26D6_16D16( p0.y ); |
2188 | |
2189 | p.x = FT_26D6_16D16( p.x ); |
2190 | p.y = FT_26D6_16D16( p.y ); |
2191 | |
2192 | for ( i = 0; i < num_roots; i++ ) |
2193 | { |
2194 | FT_16D16 t = roots[i]; |
2195 | FT_16D16 t2 = 0; |
2196 | FT_16D16 dist = 0; |
2197 | |
2198 | FT_16D16_Vec curve_point; |
2199 | FT_16D16_Vec dist_vector; |
2200 | |
2201 | /* |
2202 | * Ideally we should discard the roots which are outside the range |
2203 | * [0.0, 1.0] and check the endpoints of the Bezier curve, but Behdad |
2204 | * Esfahbod proved the following lemma. |
2205 | * |
2206 | * Lemma: |
2207 | * |
2208 | * (1) If the closest point on the curve [0, 1] is to the endpoint at |
2209 | * `t` = 1 and the cubic has no real roots at `t` = 1 then the |
2210 | * cubic must have a real root at some `t` > 1. |
2211 | * |
2212 | * (2) Similarly, if the closest point on the curve [0, 1] is to the |
2213 | * endpoint at `t` = 0 and the cubic has no real roots at `t` = 0 |
2214 | * then the cubic must have a real root at some `t` < 0. |
2215 | * |
2216 | * Now because of this lemma we only need to clamp the roots and that |
2217 | * will take care of the endpoints. |
2218 | * |
2219 | * For more details see |
2220 | * |
2221 | * https://lists.nongnu.org/archive/html/freetype-devel/2020-06/msg00147.html |
2222 | */ |
2223 | |
2224 | if ( t < 0 ) |
2225 | t = 0; |
2226 | if ( t > FT_INT_16D16( 1 ) ) |
2227 | t = FT_INT_16D16( 1 ); |
2228 | |
2229 | t2 = FT_MulFix( t, t ); |
2230 | |
2231 | /* B(t) = t^2 * A + 2t * B + p0 - p */ |
2232 | curve_point.x = FT_MulFix( aA.x, t2 ) + |
2233 | 2 * FT_MulFix( bB.x, t ) + p0.x; |
2234 | curve_point.y = FT_MulFix( aA.y, t2 ) + |
2235 | 2 * FT_MulFix( bB.y, t ) + p0.y; |
2236 | |
2237 | /* `curve_point` - `p` */ |
2238 | dist_vector.x = curve_point.x - p.x; |
2239 | dist_vector.y = curve_point.y - p.y; |
2240 | |
2241 | dist = VECTOR_LENGTH_16D16( dist_vector ); |
2242 | |
2243 | if ( dist < min ) |
2244 | { |
2245 | min = dist; |
2246 | nearest_point = curve_point; |
2247 | min_factor = t; |
2248 | } |
2249 | } |
2250 | |
2251 | /* B'(t) = 2 * (tA + B) */ |
2252 | direction.x = 2 * FT_MulFix( aA.x, min_factor ) + 2 * bB.x; |
2253 | direction.y = 2 * FT_MulFix( aA.y, min_factor ) + 2 * bB.y; |
2254 | |
2255 | /* determine the sign */ |
2256 | cross = FT_MulFix( nearest_point.x - p.x, direction.y ) - |
2257 | FT_MulFix( nearest_point.y - p.y, direction.x ); |
2258 | |
2259 | /* assign the values */ |
2260 | out->distance = min; |
2261 | out->sign = cross < 0 ? 1 : -1; |
2262 | |
2263 | if ( min_factor != 0 && min_factor != FT_INT_16D16( 1 ) ) |
2264 | out->cross = FT_INT_16D16( 1 ); /* the two are perpendicular */ |
2265 | else |
2266 | { |
2267 | /* convert to nearest vector */ |
2268 | nearest_point.x -= FT_26D6_16D16( p.x ); |
2269 | nearest_point.y -= FT_26D6_16D16( p.y ); |
2270 | |
2271 | /* compute `cross` if not perpendicular */ |
2272 | FT_Vector_NormLen( &direction ); |
2273 | FT_Vector_NormLen( &nearest_point ); |
2274 | |
2275 | out->cross = FT_MulFix( direction.x, nearest_point.y ) - |
2276 | FT_MulFix( direction.y, nearest_point.x ); |
2277 | } |
2278 | |
2279 | Exit: |
2280 | return error; |
2281 | } |
2282 | |
2283 | #else /* USE_NEWTON_FOR_CONIC */ |
2284 | |
2285 | /* |
2286 | * The function uses Newton's approximation to find the shortest distance, |
2287 | * which is a bit slower than the analytical method but doesn't cause |
2288 | * underflow. |
2289 | */ |
2290 | static FT_Error |
2291 | get_min_distance_conic( SDF_Edge* conic, |
2292 | FT_26D6_Vec point, |
2293 | SDF_Signed_Distance* out ) |
2294 | { |
2295 | /* |
2296 | * This method uses Newton-Raphson's approximation to find the shortest |
2297 | * distance from a point to a conic curve. It does not involve solving |
2298 | * any cubic equation, that is why there is no risk of underflow. |
2299 | * |
2300 | * Let's assume that |
2301 | * |
2302 | * ``` |
2303 | * p0 = first endpoint |
2304 | * p1 = control point |
2305 | * p3 = second endpoint |
2306 | * p = point from which shortest distance is to be calculated |
2307 | * ``` |
2308 | * |
2309 | * (1) The equation of a quadratic Bezier curve can be written as |
2310 | * |
2311 | * ``` |
2312 | * B(t) = (1 - t)^2 * p0 + 2(1 - t)t * p1 + t^2 * p2 |
2313 | * ``` |
2314 | * |
2315 | * with `t` the factor in the range [0.0f, 1.0f]. The above |
2316 | * equation can be rewritten as |
2317 | * |
2318 | * ``` |
2319 | * B(t) = t^2 * (p0 - 2p1 + p2) + 2t * (p1 - p0) + p0 |
2320 | * ``` |
2321 | * |
2322 | * With |
2323 | * |
2324 | * ``` |
2325 | * A = p0 - 2p1 + p2 |
2326 | * B = 2 * (p1 - p0) |
2327 | * ``` |
2328 | * |
2329 | * we have |
2330 | * |
2331 | * ``` |
2332 | * B(t) = t^2 * A + t * B + p0 |
2333 | * ``` |
2334 | * |
2335 | * (2) The derivative of the above equation is |
2336 | * |
2337 | * ``` |
2338 | * B'(t) = 2t * A + B |
2339 | * ``` |
2340 | * |
2341 | * (3) The second derivative of the above equation is |
2342 | * |
2343 | * ``` |
2344 | * B''(t) = 2A |
2345 | * ``` |
2346 | * |
2347 | * (4) The equation `P(t)` of the distance from point `p` to the curve |
2348 | * can be written as |
2349 | * |
2350 | * ``` |
2351 | * P(t) = t^2 * A + t^2 * B + p0 - p |
2352 | * ``` |
2353 | * |
2354 | * With |
2355 | * |
2356 | * ``` |
2357 | * C = p0 - p |
2358 | * ``` |
2359 | * |
2360 | * we have |
2361 | * |
2362 | * ``` |
2363 | * P(t) = t^2 * A + t * B + C |
2364 | * ``` |
2365 | * |
2366 | * (5) Finally, the equation of the angle between `B(t)` and `P(t)` can |
2367 | * be written as |
2368 | * |
2369 | * ``` |
2370 | * Q(t) = P(t) . B'(t) |
2371 | * ``` |
2372 | * |
2373 | * (6) Our task is to find a value of `t` such that the above equation |
2374 | * `Q(t)` becomes zero, that is, the point-to-curve vector makes |
2375 | * 90~degrees with the curve. We solve this with the Newton-Raphson |
2376 | * method. |
2377 | * |
2378 | * (7) We first assume an arbitrary value of factor `t`, which we then |
2379 | * improve. |
2380 | * |
2381 | * ``` |
2382 | * t := Q(t) / Q'(t) |
2383 | * ``` |
2384 | * |
2385 | * Putting the value of `Q(t)` from the above equation gives |
2386 | * |
2387 | * ``` |
2388 | * t := P(t) . B'(t) / derivative(P(t) . B'(t)) |
2389 | * t := P(t) . B'(t) / |
2390 | * (P'(t) . B'(t) + P(t) . B''(t)) |
2391 | * ``` |
2392 | * |
2393 | * Note that `P'(t)` is the same as `B'(t)` because the constant is |
2394 | * gone due to the derivative. |
2395 | * |
2396 | * (8) Finally we get the equation to improve the factor as |
2397 | * |
2398 | * ``` |
2399 | * t := P(t) . B'(t) / |
2400 | * (B'(t) . B'(t) + P(t) . B''(t)) |
2401 | * ``` |
2402 | * |
2403 | * [note]: `B` and `B(t)` are different in the above equations. |
2404 | */ |
2405 | |
2406 | FT_Error error = FT_Err_Ok; |
2407 | |
2408 | FT_26D6_Vec aA, bB, cC; /* A, B, C in the above comment */ |
2409 | FT_26D6_Vec nearest_point = { 0, 0 }; |
2410 | /* point on curve nearest to `point` */ |
2411 | FT_26D6_Vec direction; /* direction of curve at `nearest_point` */ |
2412 | |
2413 | FT_26D6_Vec p0, p1, p2; /* control points of a conic curve */ |
2414 | FT_26D6_Vec p; /* `point` to which shortest distance */ |
2415 | |
2416 | FT_16D16 min_factor = 0; /* factor at `nearest_point' */ |
2417 | FT_16D16 cross; /* to determine the sign */ |
2418 | FT_16D16 min = FT_INT_MAX; /* shortest squared distance */ |
2419 | |
2420 | FT_UShort iterations; |
2421 | FT_UShort steps; |
2422 | |
2423 | |
2424 | if ( !conic || !out ) |
2425 | { |
2426 | error = FT_THROW( Invalid_Argument ); |
2427 | goto Exit; |
2428 | } |
2429 | |
2430 | if ( conic->edge_type != SDF_EDGE_CONIC ) |
2431 | { |
2432 | error = FT_THROW( Invalid_Argument ); |
2433 | goto Exit; |
2434 | } |
2435 | |
2436 | p0 = conic->start_pos; |
2437 | p1 = conic->control_a; |
2438 | p2 = conic->end_pos; |
2439 | p = point; |
2440 | |
2441 | /* compute substitution coefficients */ |
2442 | aA.x = p0.x - 2 * p1.x + p2.x; |
2443 | aA.y = p0.y - 2 * p1.y + p2.y; |
2444 | |
2445 | bB.x = 2 * ( p1.x - p0.x ); |
2446 | bB.y = 2 * ( p1.y - p0.y ); |
2447 | |
2448 | cC.x = p0.x; |
2449 | cC.y = p0.y; |
2450 | |
2451 | /* do Newton's iterations */ |
2452 | for ( iterations = 0; iterations <= MAX_NEWTON_DIVISIONS; iterations++ ) |
2453 | { |
2454 | FT_16D16 factor = FT_INT_16D16( iterations ) / MAX_NEWTON_DIVISIONS; |
2455 | FT_16D16 factor2; |
2456 | FT_16D16 length; |
2457 | |
2458 | FT_16D16_Vec curve_point; /* point on the curve */ |
2459 | FT_16D16_Vec dist_vector; /* `curve_point` - `p` */ |
2460 | |
2461 | FT_26D6_Vec d1; /* first derivative */ |
2462 | FT_26D6_Vec d2; /* second derivative */ |
2463 | |
2464 | FT_16D16 temp1; |
2465 | FT_16D16 temp2; |
2466 | |
2467 | |
2468 | for ( steps = 0; steps < MAX_NEWTON_STEPS; steps++ ) |
2469 | { |
2470 | factor2 = FT_MulFix( factor, factor ); |
2471 | |
2472 | /* B(t) = t^2 * A + t * B + p0 */ |
2473 | curve_point.x = FT_MulFix( aA.x, factor2 ) + |
2474 | FT_MulFix( bB.x, factor ) + cC.x; |
2475 | curve_point.y = FT_MulFix( aA.y, factor2 ) + |
2476 | FT_MulFix( bB.y, factor ) + cC.y; |
2477 | |
2478 | /* convert to 16.16 */ |
2479 | curve_point.x = FT_26D6_16D16( curve_point.x ); |
2480 | curve_point.y = FT_26D6_16D16( curve_point.y ); |
2481 | |
2482 | /* P(t) in the comment */ |
2483 | dist_vector.x = curve_point.x - FT_26D6_16D16( p.x ); |
2484 | dist_vector.y = curve_point.y - FT_26D6_16D16( p.y ); |
2485 | |
2486 | length = VECTOR_LENGTH_16D16( dist_vector ); |
2487 | |
2488 | if ( length < min ) |
2489 | { |
2490 | min = length; |
2491 | min_factor = factor; |
2492 | nearest_point = curve_point; |
2493 | } |
2494 | |
2495 | /* This is Newton's approximation. */ |
2496 | /* */ |
2497 | /* t := P(t) . B'(t) / */ |
2498 | /* (B'(t) . B'(t) + P(t) . B''(t)) */ |
2499 | |
2500 | /* B'(t) = 2tA + B */ |
2501 | d1.x = FT_MulFix( aA.x, 2 * factor ) + bB.x; |
2502 | d1.y = FT_MulFix( aA.y, 2 * factor ) + bB.y; |
2503 | |
2504 | /* B''(t) = 2A */ |
2505 | d2.x = 2 * aA.x; |
2506 | d2.y = 2 * aA.y; |
2507 | |
2508 | dist_vector.x /= 1024; |
2509 | dist_vector.y /= 1024; |
2510 | |
2511 | /* temp1 = P(t) . B'(t) */ |
2512 | temp1 = VEC_26D6_DOT( dist_vector, d1 ); |
2513 | |
2514 | /* temp2 = B'(t) . B'(t) + P(t) . B''(t) */ |
2515 | temp2 = VEC_26D6_DOT( d1, d1 ) + |
2516 | VEC_26D6_DOT( dist_vector, d2 ); |
2517 | |
2518 | factor -= FT_DivFix( temp1, temp2 ); |
2519 | |
2520 | if ( factor < 0 || factor > FT_INT_16D16( 1 ) ) |
2521 | break; |
2522 | } |
2523 | } |
2524 | |
2525 | /* B'(t) = 2t * A + B */ |
2526 | direction.x = 2 * FT_MulFix( aA.x, min_factor ) + bB.x; |
2527 | direction.y = 2 * FT_MulFix( aA.y, min_factor ) + bB.y; |
2528 | |
2529 | /* determine the sign */ |
2530 | cross = FT_MulFix( nearest_point.x - FT_26D6_16D16( p.x ), |
2531 | direction.y ) - |
2532 | FT_MulFix( nearest_point.y - FT_26D6_16D16( p.y ), |
2533 | direction.x ); |
2534 | |
2535 | /* assign the values */ |
2536 | out->distance = min; |
2537 | out->sign = cross < 0 ? 1 : -1; |
2538 | |
2539 | if ( min_factor != 0 && min_factor != FT_INT_16D16( 1 ) ) |
2540 | out->cross = FT_INT_16D16( 1 ); /* the two are perpendicular */ |
2541 | else |
2542 | { |
2543 | /* convert to nearest vector */ |
2544 | nearest_point.x -= FT_26D6_16D16( p.x ); |
2545 | nearest_point.y -= FT_26D6_16D16( p.y ); |
2546 | |
2547 | /* compute `cross` if not perpendicular */ |
2548 | FT_Vector_NormLen( &direction ); |
2549 | FT_Vector_NormLen( &nearest_point ); |
2550 | |
2551 | out->cross = FT_MulFix( direction.x, nearest_point.y ) - |
2552 | FT_MulFix( direction.y, nearest_point.x ); |
2553 | } |
2554 | |
2555 | Exit: |
2556 | return error; |
2557 | } |
2558 | |
2559 | |
2560 | #endif /* USE_NEWTON_FOR_CONIC */ |
2561 | |
2562 | |
2563 | /************************************************************************** |
2564 | * |
2565 | * @Function: |
2566 | * get_min_distance_cubic |
2567 | * |
2568 | * @Description: |
2569 | * Find the shortest distance from the `cubic` Bezier curve to a given |
2570 | * `point` and assigns it to `out`. Use it for cubic curves only. |
2571 | * |
2572 | * @Input: |
2573 | * cubic :: |
2574 | * The cubic Bezier curve to which the shortest distance is to be |
2575 | * computed. |
2576 | * |
2577 | * point :: |
2578 | * Point from which the shortest distance is to be computed. |
2579 | * |
2580 | * @Output: |
2581 | * out :: |
2582 | * Signed distance from `point` to `cubic`. |
2583 | * |
2584 | * @Return: |
2585 | * FreeType error, 0 means success. |
2586 | * |
2587 | * @Note: |
2588 | * The function uses Newton's approximation to find the shortest |
2589 | * distance. Another way would be to divide the cubic into conic or |
2590 | * subdivide the curve into lines, but that is not implemented. |
2591 | * |
2592 | * The `cubic` parameter must have an edge type of `SDF_EDGE_CUBIC`. |
2593 | * |
2594 | */ |
2595 | static FT_Error |
2596 | get_min_distance_cubic( SDF_Edge* cubic, |
2597 | FT_26D6_Vec point, |
2598 | SDF_Signed_Distance* out ) |
2599 | { |
2600 | /* |
2601 | * The procedure to find the shortest distance from a point to a cubic |
2602 | * Bezier curve is similar to quadratic curve algorithm. The only |
2603 | * difference is that while calculating factor `t`, instead of a cubic |
2604 | * polynomial equation we have to find the roots of a 5th degree |
2605 | * polynomial equation. Solving this would require a significant amount |
2606 | * of time, and still the results may not be accurate. We are thus |
2607 | * going to directly approximate the value of `t` using the Newton-Raphson |
2608 | * method. |
2609 | * |
2610 | * Let's assume that |
2611 | * |
2612 | * ``` |
2613 | * p0 = first endpoint |
2614 | * p1 = first control point |
2615 | * p2 = second control point |
2616 | * p3 = second endpoint |
2617 | * p = point from which shortest distance is to be calculated |
2618 | * ``` |
2619 | * |
2620 | * (1) The equation of a cubic Bezier curve can be written as |
2621 | * |
2622 | * ``` |
2623 | * B(t) = (1 - t)^3 * p0 + 3(1 - t)^2 t * p1 + |
2624 | * 3(1 - t)t^2 * p2 + t^3 * p3 |
2625 | * ``` |
2626 | * |
2627 | * The equation can be expanded and written as |
2628 | * |
2629 | * ``` |
2630 | * B(t) = t^3 * (-p0 + 3p1 - 3p2 + p3) + |
2631 | * 3t^2 * (p0 - 2p1 + p2) + 3t * (-p0 + p1) + p0 |
2632 | * ``` |
2633 | * |
2634 | * With |
2635 | * |
2636 | * ``` |
2637 | * A = -p0 + 3p1 - 3p2 + p3 |
2638 | * B = 3(p0 - 2p1 + p2) |
2639 | * C = 3(-p0 + p1) |
2640 | * ``` |
2641 | * |
2642 | * we have |
2643 | * |
2644 | * ``` |
2645 | * B(t) = t^3 * A + t^2 * B + t * C + p0 |
2646 | * ``` |
2647 | * |
2648 | * (2) The derivative of the above equation is |
2649 | * |
2650 | * ``` |
2651 | * B'(t) = 3t^2 * A + 2t * B + C |
2652 | * ``` |
2653 | * |
2654 | * (3) The second derivative of the above equation is |
2655 | * |
2656 | * ``` |
2657 | * B''(t) = 6t * A + 2B |
2658 | * ``` |
2659 | * |
2660 | * (4) The equation `P(t)` of the distance from point `p` to the curve |
2661 | * can be written as |
2662 | * |
2663 | * ``` |
2664 | * P(t) = t^3 * A + t^2 * B + t * C + p0 - p |
2665 | * ``` |
2666 | * |
2667 | * With |
2668 | * |
2669 | * ``` |
2670 | * D = p0 - p |
2671 | * ``` |
2672 | * |
2673 | * we have |
2674 | * |
2675 | * ``` |
2676 | * P(t) = t^3 * A + t^2 * B + t * C + D |
2677 | * ``` |
2678 | * |
2679 | * (5) Finally the equation of the angle between `B(t)` and `P(t)` can |
2680 | * be written as |
2681 | * |
2682 | * ``` |
2683 | * Q(t) = P(t) . B'(t) |
2684 | * ``` |
2685 | * |
2686 | * (6) Our task is to find a value of `t` such that the above equation |
2687 | * `Q(t)` becomes zero, that is, the point-to-curve vector makes |
2688 | * 90~degree with curve. We solve this with the Newton-Raphson |
2689 | * method. |
2690 | * |
2691 | * (7) We first assume an arbitrary value of factor `t`, which we then |
2692 | * improve. |
2693 | * |
2694 | * ``` |
2695 | * t := Q(t) / Q'(t) |
2696 | * ``` |
2697 | * |
2698 | * Putting the value of `Q(t)` from the above equation gives |
2699 | * |
2700 | * ``` |
2701 | * t := P(t) . B'(t) / derivative(P(t) . B'(t)) |
2702 | * t := P(t) . B'(t) / |
2703 | * (P'(t) . B'(t) + P(t) . B''(t)) |
2704 | * ``` |
2705 | * |
2706 | * Note that `P'(t)` is the same as `B'(t)` because the constant is |
2707 | * gone due to the derivative. |
2708 | * |
2709 | * (8) Finally we get the equation to improve the factor as |
2710 | * |
2711 | * ``` |
2712 | * t := P(t) . B'(t) / |
2713 | * (B'(t) . B'( t ) + P(t) . B''(t)) |
2714 | * ``` |
2715 | * |
2716 | * [note]: `B` and `B(t)` are different in the above equations. |
2717 | */ |
2718 | |
2719 | FT_Error error = FT_Err_Ok; |
2720 | |
2721 | FT_26D6_Vec aA, bB, cC, dD; /* A, B, C, D in the above comment */ |
2722 | FT_16D16_Vec nearest_point = { 0, 0 }; |
2723 | /* point on curve nearest to `point` */ |
2724 | FT_16D16_Vec direction; /* direction of curve at `nearest_point` */ |
2725 | |
2726 | FT_26D6_Vec p0, p1, p2, p3; /* control points of a cubic curve */ |
2727 | FT_26D6_Vec p; /* `point` to which shortest distance */ |
2728 | |
2729 | FT_16D16 min_factor = 0; /* factor at shortest distance */ |
2730 | FT_16D16 min_factor_sq = 0; /* factor at shortest distance */ |
2731 | FT_16D16 cross; /* to determine the sign */ |
2732 | FT_16D16 min = FT_INT_MAX; /* shortest distance */ |
2733 | |
2734 | FT_UShort iterations; |
2735 | FT_UShort steps; |
2736 | |
2737 | |
2738 | if ( !cubic || !out ) |
2739 | { |
2740 | error = FT_THROW( Invalid_Argument ); |
2741 | goto Exit; |
2742 | } |
2743 | |
2744 | if ( cubic->edge_type != SDF_EDGE_CUBIC ) |
2745 | { |
2746 | error = FT_THROW( Invalid_Argument ); |
2747 | goto Exit; |
2748 | } |
2749 | |
2750 | p0 = cubic->start_pos; |
2751 | p1 = cubic->control_a; |
2752 | p2 = cubic->control_b; |
2753 | p3 = cubic->end_pos; |
2754 | p = point; |
2755 | |
2756 | /* compute substitution coefficients */ |
2757 | aA.x = -p0.x + 3 * ( p1.x - p2.x ) + p3.x; |
2758 | aA.y = -p0.y + 3 * ( p1.y - p2.y ) + p3.y; |
2759 | |
2760 | bB.x = 3 * ( p0.x - 2 * p1.x + p2.x ); |
2761 | bB.y = 3 * ( p0.y - 2 * p1.y + p2.y ); |
2762 | |
2763 | cC.x = 3 * ( p1.x - p0.x ); |
2764 | cC.y = 3 * ( p1.y - p0.y ); |
2765 | |
2766 | dD.x = p0.x; |
2767 | dD.y = p0.y; |
2768 | |
2769 | for ( iterations = 0; iterations <= MAX_NEWTON_DIVISIONS; iterations++ ) |
2770 | { |
2771 | FT_16D16 factor = FT_INT_16D16( iterations ) / MAX_NEWTON_DIVISIONS; |
2772 | |
2773 | FT_16D16 factor2; /* factor^2 */ |
2774 | FT_16D16 factor3; /* factor^3 */ |
2775 | FT_16D16 length; |
2776 | |
2777 | FT_16D16_Vec curve_point; /* point on the curve */ |
2778 | FT_16D16_Vec dist_vector; /* `curve_point' - `p' */ |
2779 | |
2780 | FT_26D6_Vec d1; /* first derivative */ |
2781 | FT_26D6_Vec d2; /* second derivative */ |
2782 | |
2783 | FT_16D16 temp1; |
2784 | FT_16D16 temp2; |
2785 | |
2786 | |
2787 | for ( steps = 0; steps < MAX_NEWTON_STEPS; steps++ ) |
2788 | { |
2789 | factor2 = FT_MulFix( factor, factor ); |
2790 | factor3 = FT_MulFix( factor2, factor ); |
2791 | |
2792 | /* B(t) = t^3 * A + t^2 * B + t * C + D */ |
2793 | curve_point.x = FT_MulFix( aA.x, factor3 ) + |
2794 | FT_MulFix( bB.x, factor2 ) + |
2795 | FT_MulFix( cC.x, factor ) + dD.x; |
2796 | curve_point.y = FT_MulFix( aA.y, factor3 ) + |
2797 | FT_MulFix( bB.y, factor2 ) + |
2798 | FT_MulFix( cC.y, factor ) + dD.y; |
2799 | |
2800 | /* convert to 16.16 */ |
2801 | curve_point.x = FT_26D6_16D16( curve_point.x ); |
2802 | curve_point.y = FT_26D6_16D16( curve_point.y ); |
2803 | |
2804 | /* P(t) in the comment */ |
2805 | dist_vector.x = curve_point.x - FT_26D6_16D16( p.x ); |
2806 | dist_vector.y = curve_point.y - FT_26D6_16D16( p.y ); |
2807 | |
2808 | length = VECTOR_LENGTH_16D16( dist_vector ); |
2809 | |
2810 | if ( length < min ) |
2811 | { |
2812 | min = length; |
2813 | min_factor = factor; |
2814 | min_factor_sq = factor2; |
2815 | nearest_point = curve_point; |
2816 | } |
2817 | |
2818 | /* This the Newton's approximation. */ |
2819 | /* */ |
2820 | /* t := P(t) . B'(t) / */ |
2821 | /* (B'(t) . B'(t) + P(t) . B''(t)) */ |
2822 | |
2823 | /* B'(t) = 3t^2 * A + 2t * B + C */ |
2824 | d1.x = FT_MulFix( aA.x, 3 * factor2 ) + |
2825 | FT_MulFix( bB.x, 2 * factor ) + cC.x; |
2826 | d1.y = FT_MulFix( aA.y, 3 * factor2 ) + |
2827 | FT_MulFix( bB.y, 2 * factor ) + cC.y; |
2828 | |
2829 | /* B''(t) = 6t * A + 2B */ |
2830 | d2.x = FT_MulFix( aA.x, 6 * factor ) + 2 * bB.x; |
2831 | d2.y = FT_MulFix( aA.y, 6 * factor ) + 2 * bB.y; |
2832 | |
2833 | dist_vector.x /= 1024; |
2834 | dist_vector.y /= 1024; |
2835 | |
2836 | /* temp1 = P(t) . B'(t) */ |
2837 | temp1 = VEC_26D6_DOT( dist_vector, d1 ); |
2838 | |
2839 | /* temp2 = B'(t) . B'(t) + P(t) . B''(t) */ |
2840 | temp2 = VEC_26D6_DOT( d1, d1 ) + |
2841 | VEC_26D6_DOT( dist_vector, d2 ); |
2842 | |
2843 | factor -= FT_DivFix( temp1, temp2 ); |
2844 | |
2845 | if ( factor < 0 || factor > FT_INT_16D16( 1 ) ) |
2846 | break; |
2847 | } |
2848 | } |
2849 | |
2850 | /* B'(t) = 3t^2 * A + 2t * B + C */ |
2851 | direction.x = FT_MulFix( aA.x, 3 * min_factor_sq ) + |
2852 | FT_MulFix( bB.x, 2 * min_factor ) + cC.x; |
2853 | direction.y = FT_MulFix( aA.y, 3 * min_factor_sq ) + |
2854 | FT_MulFix( bB.y, 2 * min_factor ) + cC.y; |
2855 | |
2856 | /* determine the sign */ |
2857 | cross = FT_MulFix( nearest_point.x - FT_26D6_16D16( p.x ), |
2858 | direction.y ) - |
2859 | FT_MulFix( nearest_point.y - FT_26D6_16D16( p.y ), |
2860 | direction.x ); |
2861 | |
2862 | /* assign the values */ |
2863 | out->distance = min; |
2864 | out->sign = cross < 0 ? 1 : -1; |
2865 | |
2866 | if ( min_factor != 0 && min_factor != FT_INT_16D16( 1 ) ) |
2867 | out->cross = FT_INT_16D16( 1 ); /* the two are perpendicular */ |
2868 | else |
2869 | { |
2870 | /* convert to nearest vector */ |
2871 | nearest_point.x -= FT_26D6_16D16( p.x ); |
2872 | nearest_point.y -= FT_26D6_16D16( p.y ); |
2873 | |
2874 | /* compute `cross` if not perpendicular */ |
2875 | FT_Vector_NormLen( &direction ); |
2876 | FT_Vector_NormLen( &nearest_point ); |
2877 | |
2878 | out->cross = FT_MulFix( direction.x, nearest_point.y ) - |
2879 | FT_MulFix( direction.y, nearest_point.x ); |
2880 | } |
2881 | |
2882 | Exit: |
2883 | return error; |
2884 | } |
2885 | |
2886 | |
2887 | /************************************************************************** |
2888 | * |
2889 | * @Function: |
2890 | * sdf_edge_get_min_distance |
2891 | * |
2892 | * @Description: |
2893 | * Find shortest distance from `point` to any type of `edge`. It checks |
2894 | * the edge type and then calls the relevant `get_min_distance_*` |
2895 | * function. |
2896 | * |
2897 | * @Input: |
2898 | * edge :: |
2899 | * An edge to which the shortest distance is to be computed. |
2900 | * |
2901 | * point :: |
2902 | * Point from which the shortest distance is to be computed. |
2903 | * |
2904 | * @Output: |
2905 | * out :: |
2906 | * Signed distance from `point` to `edge`. |
2907 | * |
2908 | * @Return: |
2909 | * FreeType error, 0 means success. |
2910 | * |
2911 | */ |
2912 | static FT_Error |
2913 | sdf_edge_get_min_distance( SDF_Edge* edge, |
2914 | FT_26D6_Vec point, |
2915 | SDF_Signed_Distance* out ) |
2916 | { |
2917 | FT_Error error = FT_Err_Ok; |
2918 | |
2919 | |
2920 | if ( !edge || !out ) |
2921 | { |
2922 | error = FT_THROW( Invalid_Argument ); |
2923 | goto Exit; |
2924 | } |
2925 | |
2926 | /* edge-specific distance calculation */ |
2927 | switch ( edge->edge_type ) |
2928 | { |
2929 | case SDF_EDGE_LINE: |
2930 | get_min_distance_line( edge, point, out ); |
2931 | break; |
2932 | |
2933 | case SDF_EDGE_CONIC: |
2934 | get_min_distance_conic( edge, point, out ); |
2935 | break; |
2936 | |
2937 | case SDF_EDGE_CUBIC: |
2938 | get_min_distance_cubic( edge, point, out ); |
2939 | break; |
2940 | |
2941 | default: |
2942 | error = FT_THROW( Invalid_Argument ); |
2943 | } |
2944 | |
2945 | Exit: |
2946 | return error; |
2947 | } |
2948 | |
2949 | |
2950 | /* `sdf_generate' is not used at the moment */ |
2951 | #if 0 |
2952 | |
2953 | #error "DO NOT USE THIS!" |
2954 | #error "The function still outputs 16-bit data, which might cause memory" |
2955 | #error "corruption. If required I will add this later." |
2956 | |
2957 | /************************************************************************** |
2958 | * |
2959 | * @Function: |
2960 | * sdf_contour_get_min_distance |
2961 | * |
2962 | * @Description: |
2963 | * Iterate over all edges that make up the contour, find the shortest |
2964 | * distance from a point to this contour, and assigns result to `out`. |
2965 | * |
2966 | * @Input: |
2967 | * contour :: |
2968 | * A contour to which the shortest distance is to be computed. |
2969 | * |
2970 | * point :: |
2971 | * Point from which the shortest distance is to be computed. |
2972 | * |
2973 | * @Output: |
2974 | * out :: |
2975 | * Signed distance from the `point' to the `contour'. |
2976 | * |
2977 | * @Return: |
2978 | * FreeType error, 0 means success. |
2979 | * |
2980 | * @Note: |
2981 | * The function does not return a signed distance for each edge which |
2982 | * makes up the contour, it simply returns the shortest of all the |
2983 | * edges. |
2984 | * |
2985 | */ |
2986 | static FT_Error |
2987 | sdf_contour_get_min_distance( SDF_Contour* contour, |
2988 | FT_26D6_Vec point, |
2989 | SDF_Signed_Distance* out ) |
2990 | { |
2991 | FT_Error error = FT_Err_Ok; |
2992 | SDF_Signed_Distance min_dist = max_sdf; |
2993 | SDF_Edge* edge_list; |
2994 | |
2995 | |
2996 | if ( !contour || !out ) |
2997 | { |
2998 | error = FT_THROW( Invalid_Argument ); |
2999 | goto Exit; |
3000 | } |
3001 | |
3002 | edge_list = contour->edges; |
3003 | |
3004 | /* iterate over all the edges manually */ |
3005 | while ( edge_list ) |
3006 | { |
3007 | SDF_Signed_Distance current_dist = max_sdf; |
3008 | FT_16D16 diff; |
3009 | |
3010 | |
3011 | FT_CALL( sdf_edge_get_min_distance( edge_list, |
3012 | point, |
3013 | ¤t_dist ) ); |
3014 | |
3015 | if ( current_dist.distance >= 0 ) |
3016 | { |
3017 | diff = current_dist.distance - min_dist.distance; |
3018 | |
3019 | |
3020 | if ( FT_ABS( diff ) < CORNER_CHECK_EPSILON ) |
3021 | min_dist = resolve_corner( min_dist, current_dist ); |
3022 | else if ( diff < 0 ) |
3023 | min_dist = current_dist; |
3024 | } |
3025 | else |
3026 | FT_TRACE0(( "sdf_contour_get_min_distance: Overflow.\n" )); |
3027 | |
3028 | edge_list = edge_list->next; |
3029 | } |
3030 | |
3031 | *out = min_dist; |
3032 | |
3033 | Exit: |
3034 | return error; |
3035 | } |
3036 | |
3037 | |
3038 | /************************************************************************** |
3039 | * |
3040 | * @Function: |
3041 | * sdf_generate |
3042 | * |
3043 | * @Description: |
3044 | * This is the main function that is responsible for generating signed |
3045 | * distance fields. The function does not align or compute the size of |
3046 | * `bitmap`; therefore the calling application must set up `bitmap` |
3047 | * properly and transform the `shape' appropriately in advance. |
3048 | * |
3049 | * Currently we check all pixels against all contours and all edges. |
3050 | * |
3051 | * @Input: |
3052 | * internal_params :: |
3053 | * Internal parameters and properties required by the rasterizer. See |
3054 | * @SDF_Params for more. |
3055 | * |
3056 | * shape :: |
3057 | * A complete shape which is used to generate SDF. |
3058 | * |
3059 | * spread :: |
3060 | * Maximum distances to be allowed in the output bitmap. |
3061 | * |
3062 | * @Output: |
3063 | * bitmap :: |
3064 | * The output bitmap which will contain the SDF information. |
3065 | * |
3066 | * @Return: |
3067 | * FreeType error, 0 means success. |
3068 | * |
3069 | */ |
3070 | static FT_Error |
3071 | sdf_generate( const SDF_Params internal_params, |
3072 | const SDF_Shape* shape, |
3073 | FT_UInt spread, |
3074 | const FT_Bitmap* bitmap ) |
3075 | { |
3076 | FT_Error error = FT_Err_Ok; |
3077 | |
3078 | FT_UInt width = 0; |
3079 | FT_UInt rows = 0; |
3080 | FT_UInt x = 0; /* used to loop in x direction, i.e., width */ |
3081 | FT_UInt y = 0; /* used to loop in y direction, i.e., rows */ |
3082 | FT_UInt sp_sq = 0; /* `spread` [* `spread`] as a 16.16 fixed value */ |
3083 | |
3084 | FT_Short* buffer; |
3085 | |
3086 | |
3087 | if ( !shape || !bitmap ) |
3088 | { |
3089 | error = FT_THROW( Invalid_Argument ); |
3090 | goto Exit; |
3091 | } |
3092 | |
3093 | if ( spread < MIN_SPREAD || spread > MAX_SPREAD ) |
3094 | { |
3095 | error = FT_THROW( Invalid_Argument ); |
3096 | goto Exit; |
3097 | } |
3098 | |
3099 | width = bitmap->width; |
3100 | rows = bitmap->rows; |
3101 | buffer = (FT_Short*)bitmap->buffer; |
3102 | |
3103 | if ( USE_SQUARED_DISTANCES ) |
3104 | sp_sq = FT_INT_16D16( spread * spread ); |
3105 | else |
3106 | sp_sq = FT_INT_16D16( spread ); |
3107 | |
3108 | if ( width == 0 || rows == 0 ) |
3109 | { |
3110 | FT_TRACE0(( "sdf_generate:" |
3111 | " Cannot render glyph with width/height == 0\n" )); |
3112 | FT_TRACE0(( " " |
3113 | " (width, height provided [%d, %d])\n" , |
3114 | width, rows )); |
3115 | |
3116 | error = FT_THROW( Cannot_Render_Glyph ); |
3117 | goto Exit; |
3118 | } |
3119 | |
3120 | /* loop over all rows */ |
3121 | for ( y = 0; y < rows; y++ ) |
3122 | { |
3123 | /* loop over all pixels of a row */ |
3124 | for ( x = 0; x < width; x++ ) |
3125 | { |
3126 | /* `grid_point` is the current pixel position; */ |
3127 | /* our task is to find the shortest distance */ |
3128 | /* from this point to the entire shape. */ |
3129 | FT_26D6_Vec grid_point = zero_vector; |
3130 | SDF_Signed_Distance min_dist = max_sdf; |
3131 | SDF_Contour* contour_list; |
3132 | |
3133 | FT_UInt index; |
3134 | FT_Short value; |
3135 | |
3136 | |
3137 | grid_point.x = FT_INT_26D6( x ); |
3138 | grid_point.y = FT_INT_26D6( y ); |
3139 | |
3140 | /* This `grid_point' is at the corner, but we */ |
3141 | /* use the center of the pixel. */ |
3142 | grid_point.x += FT_INT_26D6( 1 ) / 2; |
3143 | grid_point.y += FT_INT_26D6( 1 ) / 2; |
3144 | |
3145 | contour_list = shape->contours; |
3146 | |
3147 | /* iterate over all contours manually */ |
3148 | while ( contour_list ) |
3149 | { |
3150 | SDF_Signed_Distance current_dist = max_sdf; |
3151 | |
3152 | |
3153 | FT_CALL( sdf_contour_get_min_distance( contour_list, |
3154 | grid_point, |
3155 | ¤t_dist ) ); |
3156 | |
3157 | if ( current_dist.distance < min_dist.distance ) |
3158 | min_dist = current_dist; |
3159 | |
3160 | contour_list = contour_list->next; |
3161 | } |
3162 | |
3163 | /* [OPTIMIZATION]: if (min_dist > sp_sq) then simply clamp */ |
3164 | /* the value to spread to avoid square_root */ |
3165 | |
3166 | /* clamp the values to spread */ |
3167 | if ( min_dist.distance > sp_sq ) |
3168 | min_dist.distance = sp_sq; |
3169 | |
3170 | /* square_root the values and fit in a 6.10 fixed-point */ |
3171 | if ( USE_SQUARED_DISTANCES ) |
3172 | min_dist.distance = square_root( min_dist.distance ); |
3173 | |
3174 | if ( internal_params.orientation == FT_ORIENTATION_FILL_LEFT ) |
3175 | min_dist.sign = -min_dist.sign; |
3176 | if ( internal_params.flip_sign ) |
3177 | min_dist.sign = -min_dist.sign; |
3178 | |
3179 | min_dist.distance /= 64; /* convert from 16.16 to 22.10 */ |
3180 | |
3181 | value = min_dist.distance & 0x0000FFFF; /* truncate to 6.10 */ |
3182 | value *= min_dist.sign; |
3183 | |
3184 | if ( internal_params.flip_y ) |
3185 | index = y * width + x; |
3186 | else |
3187 | index = ( rows - y - 1 ) * width + x; |
3188 | |
3189 | buffer[index] = value; |
3190 | } |
3191 | } |
3192 | |
3193 | Exit: |
3194 | return error; |
3195 | } |
3196 | |
3197 | #endif /* 0 */ |
3198 | |
3199 | |
3200 | /************************************************************************** |
3201 | * |
3202 | * @Function: |
3203 | * sdf_generate_bounding_box |
3204 | * |
3205 | * @Description: |
3206 | * This function does basically the same thing as `sdf_generate` above |
3207 | * but more efficiently. |
3208 | * |
3209 | * Instead of checking all pixels against all edges, we loop over all |
3210 | * edges and only check pixels around the control box of the edge; the |
3211 | * control box is increased by the spread in all directions. Anything |
3212 | * outside of the control box that exceeds `spread` doesn't need to be |
3213 | * computed. |
3214 | * |
3215 | * Lastly, to determine the sign of unchecked pixels, we do a single |
3216 | * pass of all rows starting with a '+' sign and flipping when we come |
3217 | * across a '-' sign and continue. This also eliminates the possibility |
3218 | * of overflow because we only check the proximity of the curve. |
3219 | * Therefore we can use squared distanced safely. |
3220 | * |
3221 | * @Input: |
3222 | * internal_params :: |
3223 | * Internal parameters and properties required by the rasterizer. |
3224 | * See @SDF_Params for more. |
3225 | * |
3226 | * shape :: |
3227 | * A complete shape which is used to generate SDF. |
3228 | * |
3229 | * spread :: |
3230 | * Maximum distances to be allowed in the output bitmap. |
3231 | * |
3232 | * @Output: |
3233 | * bitmap :: |
3234 | * The output bitmap which will contain the SDF information. |
3235 | * |
3236 | * @Return: |
3237 | * FreeType error, 0 means success. |
3238 | * |
3239 | */ |
3240 | static FT_Error |
3241 | sdf_generate_bounding_box( const SDF_Params internal_params, |
3242 | const SDF_Shape* shape, |
3243 | FT_UInt spread, |
3244 | const FT_Bitmap* bitmap ) |
3245 | { |
3246 | FT_Error error = FT_Err_Ok; |
3247 | FT_Memory memory = NULL; |
3248 | |
3249 | FT_Int width, rows, i, j; |
3250 | FT_Int sp_sq; /* max value to check */ |
3251 | |
3252 | SDF_Contour* contours; /* list of all contours */ |
3253 | FT_SDFFormat* buffer; /* the bitmap buffer */ |
3254 | |
3255 | /* This buffer has the same size in indices as the */ |
3256 | /* bitmap buffer. When we check a pixel position for */ |
3257 | /* a shortest distance we keep it in this buffer. */ |
3258 | /* This way we can find out which pixel is set, */ |
3259 | /* and also determine the signs properly. */ |
3260 | SDF_Signed_Distance* dists = NULL; |
3261 | |
3262 | const FT_16D16 fixed_spread = (FT_16D16)FT_INT_16D16( spread ); |
3263 | |
3264 | |
3265 | if ( !shape || !bitmap ) |
3266 | { |
3267 | error = FT_THROW( Invalid_Argument ); |
3268 | goto Exit; |
3269 | } |
3270 | |
3271 | if ( spread < MIN_SPREAD || spread > MAX_SPREAD ) |
3272 | { |
3273 | error = FT_THROW( Invalid_Argument ); |
3274 | goto Exit; |
3275 | } |
3276 | |
3277 | memory = shape->memory; |
3278 | if ( !memory ) |
3279 | { |
3280 | error = FT_THROW( Invalid_Argument ); |
3281 | goto Exit; |
3282 | } |
3283 | |
3284 | if ( FT_ALLOC( dists, |
3285 | bitmap->width * bitmap->rows * sizeof ( *dists ) ) ) |
3286 | goto Exit; |
3287 | |
3288 | contours = shape->contours; |
3289 | width = (FT_Int)bitmap->width; |
3290 | rows = (FT_Int)bitmap->rows; |
3291 | buffer = (FT_SDFFormat*)bitmap->buffer; |
3292 | |
3293 | if ( USE_SQUARED_DISTANCES ) |
3294 | sp_sq = FT_INT_16D16( (FT_Int)( spread * spread ) ); |
3295 | else |
3296 | sp_sq = fixed_spread; |
3297 | |
3298 | if ( width == 0 || rows == 0 ) |
3299 | { |
3300 | FT_TRACE0(( "sdf_generate:" |
3301 | " Cannot render glyph with width/height == 0\n" )); |
3302 | FT_TRACE0(( " " |
3303 | " (width, height provided [%d, %d])" , width, rows )); |
3304 | |
3305 | error = FT_THROW( Cannot_Render_Glyph ); |
3306 | goto Exit; |
3307 | } |
3308 | |
3309 | /* loop over all contours */ |
3310 | while ( contours ) |
3311 | { |
3312 | SDF_Edge* edges = contours->edges; |
3313 | |
3314 | |
3315 | /* loop over all edges */ |
3316 | while ( edges ) |
3317 | { |
3318 | FT_CBox cbox; |
3319 | FT_Int x, y; |
3320 | |
3321 | |
3322 | /* get the control box and increase it by `spread' */ |
3323 | cbox = get_control_box( *edges ); |
3324 | |
3325 | cbox.xMin = ( cbox.xMin - 63 ) / 64 - ( FT_Pos )spread; |
3326 | cbox.xMax = ( cbox.xMax + 63 ) / 64 + ( FT_Pos )spread; |
3327 | cbox.yMin = ( cbox.yMin - 63 ) / 64 - ( FT_Pos )spread; |
3328 | cbox.yMax = ( cbox.yMax + 63 ) / 64 + ( FT_Pos )spread; |
3329 | |
3330 | /* now loop over the pixels in the control box. */ |
3331 | for ( y = cbox.yMin; y < cbox.yMax; y++ ) |
3332 | { |
3333 | for ( x = cbox.xMin; x < cbox.xMax; x++ ) |
3334 | { |
3335 | FT_26D6_Vec grid_point = zero_vector; |
3336 | SDF_Signed_Distance dist = max_sdf; |
3337 | FT_UInt index = 0; |
3338 | FT_16D16 diff = 0; |
3339 | |
3340 | |
3341 | if ( x < 0 || x >= width ) |
3342 | continue; |
3343 | if ( y < 0 || y >= rows ) |
3344 | continue; |
3345 | |
3346 | grid_point.x = FT_INT_26D6( x ); |
3347 | grid_point.y = FT_INT_26D6( y ); |
3348 | |
3349 | /* This `grid_point` is at the corner, but we */ |
3350 | /* use the center of the pixel. */ |
3351 | grid_point.x += FT_INT_26D6( 1 ) / 2; |
3352 | grid_point.y += FT_INT_26D6( 1 ) / 2; |
3353 | |
3354 | FT_CALL( sdf_edge_get_min_distance( edges, |
3355 | grid_point, |
3356 | &dist ) ); |
3357 | |
3358 | if ( internal_params.orientation == FT_ORIENTATION_FILL_LEFT ) |
3359 | dist.sign = -dist.sign; |
3360 | |
3361 | /* ignore if the distance is greater than spread; */ |
3362 | /* otherwise it creates artifacts due to the wrong sign */ |
3363 | if ( dist.distance > sp_sq ) |
3364 | continue; |
3365 | |
3366 | /* take the square root of the distance if required */ |
3367 | if ( USE_SQUARED_DISTANCES ) |
3368 | dist.distance = square_root( dist.distance ); |
3369 | |
3370 | if ( internal_params.flip_y ) |
3371 | index = (FT_UInt)( y * width + x ); |
3372 | else |
3373 | index = (FT_UInt)( ( rows - y - 1 ) * width + x ); |
3374 | |
3375 | /* check whether the pixel is set or not */ |
3376 | if ( dists[index].sign == 0 ) |
3377 | dists[index] = dist; |
3378 | else |
3379 | { |
3380 | diff = FT_ABS( dists[index].distance - dist.distance ); |
3381 | |
3382 | if ( diff <= CORNER_CHECK_EPSILON ) |
3383 | dists[index] = resolve_corner( dists[index], dist ); |
3384 | else if ( dists[index].distance > dist.distance ) |
3385 | dists[index] = dist; |
3386 | } |
3387 | } |
3388 | } |
3389 | |
3390 | edges = edges->next; |
3391 | } |
3392 | |
3393 | contours = contours->next; |
3394 | } |
3395 | |
3396 | /* final pass */ |
3397 | for ( j = 0; j < rows; j++ ) |
3398 | { |
3399 | /* We assume the starting pixel of each row is outside. */ |
3400 | FT_Char current_sign = -1; |
3401 | FT_UInt index; |
3402 | |
3403 | |
3404 | if ( internal_params.overload_sign != 0 ) |
3405 | current_sign = internal_params.overload_sign < 0 ? -1 : 1; |
3406 | |
3407 | for ( i = 0; i < width; i++ ) |
3408 | { |
3409 | index = (FT_UInt)( j * width + i ); |
3410 | |
3411 | /* if the pixel is not set */ |
3412 | /* its shortest distance is more than `spread` */ |
3413 | if ( dists[index].sign == 0 ) |
3414 | dists[index].distance = fixed_spread; |
3415 | else |
3416 | current_sign = dists[index].sign; |
3417 | |
3418 | /* clamp the values */ |
3419 | if ( dists[index].distance > fixed_spread ) |
3420 | dists[index].distance = fixed_spread; |
3421 | |
3422 | /* flip sign if required */ |
3423 | dists[index].distance *= internal_params.flip_sign ? -current_sign |
3424 | : current_sign; |
3425 | |
3426 | /* concatenate to appropriate format */ |
3427 | buffer[index] = map_fixed_to_sdf( dists[index].distance, |
3428 | fixed_spread ); |
3429 | } |
3430 | } |
3431 | |
3432 | Exit: |
3433 | FT_FREE( dists ); |
3434 | return error; |
3435 | } |
3436 | |
3437 | |
3438 | /************************************************************************** |
3439 | * |
3440 | * @Function: |
3441 | * sdf_generate_subdivision |
3442 | * |
3443 | * @Description: |
3444 | * Subdivide the shape into a number of straight lines, then use the |
3445 | * above `sdf_generate_bounding_box` function to generate the SDF. |
3446 | * |
3447 | * Note: After calling this function `shape` no longer has the original |
3448 | * edges, it only contains lines. |
3449 | * |
3450 | * @Input: |
3451 | * internal_params :: |
3452 | * Internal parameters and properties required by the rasterizer. |
3453 | * See @SDF_Params for more. |
3454 | * |
3455 | * shape :: |
3456 | * A complete shape which is used to generate SDF. |
3457 | * |
3458 | * spread :: |
3459 | * Maximum distances to be allowed inthe output bitmap. |
3460 | * |
3461 | * @Output: |
3462 | * bitmap :: |
3463 | * The output bitmap which will contain the SDF information. |
3464 | * |
3465 | * @Return: |
3466 | * FreeType error, 0 means success. |
3467 | * |
3468 | */ |
3469 | static FT_Error |
3470 | sdf_generate_subdivision( const SDF_Params internal_params, |
3471 | SDF_Shape* shape, |
3472 | FT_UInt spread, |
3473 | const FT_Bitmap* bitmap ) |
3474 | { |
3475 | /* |
3476 | * Thanks to Alexei for providing the idea of this optimization. |
3477 | * |
3478 | * We take advantage of two facts. |
3479 | * |
3480 | * (1) Computing the shortest distance from a point to a line segment is |
3481 | * very fast. |
3482 | * (2) We don't have to compute the shortest distance for the entire |
3483 | * two-dimensional grid. |
3484 | * |
3485 | * Both ideas lead to the following optimization. |
3486 | * |
3487 | * (1) Split the outlines into a number of line segments. |
3488 | * |
3489 | * (2) For each line segment, only process its neighborhood. |
3490 | * |
3491 | * (3) Compute the closest distance to the line only for neighborhood |
3492 | * grid points. |
3493 | * |
3494 | * This greatly reduces the number of grid points to check. |
3495 | */ |
3496 | |
3497 | FT_Error error = FT_Err_Ok; |
3498 | |
3499 | |
3500 | FT_CALL( split_sdf_shape( shape ) ); |
3501 | FT_CALL( sdf_generate_bounding_box( internal_params, |
3502 | shape, spread, bitmap ) ); |
3503 | |
3504 | Exit: |
3505 | return error; |
3506 | } |
3507 | |
3508 | |
3509 | /************************************************************************** |
3510 | * |
3511 | * @Function: |
3512 | * sdf_generate_with_overlaps |
3513 | * |
3514 | * @Description: |
3515 | * This function can be used to generate SDF for glyphs with overlapping |
3516 | * contours. The function generates SDF for contours separately on |
3517 | * separate bitmaps (to generate SDF it uses |
3518 | * `sdf_generate_subdivision`). At the end it simply combines all the |
3519 | * SDF into the output bitmap; this fixes all the signs and removes |
3520 | * overlaps. |
3521 | * |
3522 | * @Input: |
3523 | * internal_params :: |
3524 | * Internal parameters and properties required by the rasterizer. See |
3525 | * @SDF_Params for more. |
3526 | * |
3527 | * shape :: |
3528 | * A complete shape which is used to generate SDF. |
3529 | * |
3530 | * spread :: |
3531 | * Maximum distances to be allowed in the output bitmap. |
3532 | * |
3533 | * @Output: |
3534 | * bitmap :: |
3535 | * The output bitmap which will contain the SDF information. |
3536 | * |
3537 | * @Return: |
3538 | * FreeType error, 0 means success. |
3539 | * |
3540 | * @Note: |
3541 | * The function cannot generate a proper SDF for glyphs with |
3542 | * self-intersecting contours because we cannot separate them into two |
3543 | * separate bitmaps. In case of self-intersecting contours it is |
3544 | * necessary to remove the overlaps before generating the SDF. |
3545 | * |
3546 | */ |
3547 | static FT_Error |
3548 | sdf_generate_with_overlaps( SDF_Params internal_params, |
3549 | SDF_Shape* shape, |
3550 | FT_UInt spread, |
3551 | const FT_Bitmap* bitmap ) |
3552 | { |
3553 | FT_Error error = FT_Err_Ok; |
3554 | |
3555 | FT_Int num_contours; /* total number of contours */ |
3556 | FT_Int i, j; /* iterators */ |
3557 | FT_Int width, rows; /* width and rows of the bitmap */ |
3558 | FT_Bitmap* bitmaps; /* separate bitmaps for contours */ |
3559 | |
3560 | SDF_Contour* contour; /* temporary variable to iterate */ |
3561 | SDF_Contour* temp_contour; /* temporary contour */ |
3562 | SDF_Contour* head; /* head of the contour list */ |
3563 | SDF_Shape temp_shape; /* temporary shape */ |
3564 | |
3565 | FT_Memory memory; /* to allocate memory */ |
3566 | FT_SDFFormat* t; /* target bitmap buffer */ |
3567 | FT_Bool flip_sign; /* flip sign? */ |
3568 | |
3569 | /* orientation of all the separate contours */ |
3570 | SDF_Contour_Orientation* orientations; |
3571 | |
3572 | |
3573 | bitmaps = NULL; |
3574 | orientations = NULL; |
3575 | head = NULL; |
3576 | |
3577 | if ( !shape || !bitmap || !shape->memory ) |
3578 | return FT_THROW( Invalid_Argument ); |
3579 | |
3580 | /* Disable `flip_sign` to avoid extra complication */ |
3581 | /* during the combination phase. */ |
3582 | flip_sign = internal_params.flip_sign; |
3583 | internal_params.flip_sign = 0; |
3584 | |
3585 | contour = shape->contours; |
3586 | memory = shape->memory; |
3587 | temp_shape.memory = memory; |
3588 | width = (FT_Int)bitmap->width; |
3589 | rows = (FT_Int)bitmap->rows; |
3590 | num_contours = 0; |
3591 | |
3592 | /* find the number of contours in the shape */ |
3593 | while ( contour ) |
3594 | { |
3595 | num_contours++; |
3596 | contour = contour->next; |
3597 | } |
3598 | |
3599 | /* allocate the bitmaps to generate SDF for separate contours */ |
3600 | if ( FT_ALLOC( bitmaps, |
3601 | (FT_UInt)num_contours * sizeof ( *bitmaps ) ) ) |
3602 | goto Exit; |
3603 | |
3604 | /* allocate array to hold orientation for all contours */ |
3605 | if ( FT_ALLOC( orientations, |
3606 | (FT_UInt)num_contours * sizeof ( *orientations ) ) ) |
3607 | goto Exit; |
3608 | |
3609 | contour = shape->contours; |
3610 | |
3611 | /* Iterate over all contours and generate SDF separately. */ |
3612 | for ( i = 0; i < num_contours; i++ ) |
3613 | { |
3614 | /* initialize the corresponding bitmap */ |
3615 | FT_Bitmap_Init( &bitmaps[i] ); |
3616 | |
3617 | bitmaps[i].width = bitmap->width; |
3618 | bitmaps[i].rows = bitmap->rows; |
3619 | bitmaps[i].pitch = bitmap->pitch; |
3620 | bitmaps[i].num_grays = bitmap->num_grays; |
3621 | bitmaps[i].pixel_mode = bitmap->pixel_mode; |
3622 | |
3623 | /* allocate memory for the buffer */ |
3624 | if ( FT_ALLOC( bitmaps[i].buffer, |
3625 | bitmap->rows * (FT_UInt)bitmap->pitch ) ) |
3626 | goto Exit; |
3627 | |
3628 | /* determine the orientation */ |
3629 | orientations[i] = get_contour_orientation( contour ); |
3630 | |
3631 | /* The `overload_sign` property is specific to */ |
3632 | /* `sdf_generate_bounding_box`. This basically */ |
3633 | /* overloads the default sign of the outside */ |
3634 | /* pixels, which is necessary for */ |
3635 | /* counter-clockwise contours. */ |
3636 | if ( orientations[i] == SDF_ORIENTATION_CCW && |
3637 | internal_params.orientation == FT_ORIENTATION_FILL_RIGHT ) |
3638 | internal_params.overload_sign = 1; |
3639 | else if ( orientations[i] == SDF_ORIENTATION_CW && |
3640 | internal_params.orientation == FT_ORIENTATION_FILL_LEFT ) |
3641 | internal_params.overload_sign = 1; |
3642 | else |
3643 | internal_params.overload_sign = 0; |
3644 | |
3645 | /* Make `contour->next` NULL so that there is */ |
3646 | /* one contour in the list. Also hold the next */ |
3647 | /* contour in a temporary variable so as to */ |
3648 | /* restore the original value. */ |
3649 | temp_contour = contour->next; |
3650 | contour->next = NULL; |
3651 | |
3652 | /* Use `temp_shape` to hold the new contour. */ |
3653 | /* Now, `temp_shape` has only one contour. */ |
3654 | temp_shape.contours = contour; |
3655 | |
3656 | /* finally generate the SDF */ |
3657 | FT_CALL( sdf_generate_subdivision( internal_params, |
3658 | &temp_shape, |
3659 | spread, |
3660 | &bitmaps[i] ) ); |
3661 | |
3662 | /* Restore the original `next` variable. */ |
3663 | contour->next = temp_contour; |
3664 | |
3665 | /* Since `split_sdf_shape` deallocated the original */ |
3666 | /* contours list we need to assign the new value to */ |
3667 | /* the shape's contour. */ |
3668 | temp_shape.contours->next = head; |
3669 | head = temp_shape.contours; |
3670 | |
3671 | /* Simply flip the orientation in case of post-script fonts */ |
3672 | /* so as to avoid modificatons in the combining phase. */ |
3673 | if ( internal_params.orientation == FT_ORIENTATION_FILL_LEFT ) |
3674 | { |
3675 | if ( orientations[i] == SDF_ORIENTATION_CW ) |
3676 | orientations[i] = SDF_ORIENTATION_CCW; |
3677 | else if ( orientations[i] == SDF_ORIENTATION_CCW ) |
3678 | orientations[i] = SDF_ORIENTATION_CW; |
3679 | } |
3680 | |
3681 | contour = contour->next; |
3682 | } |
3683 | |
3684 | /* assign the new contour list to `shape->contours` */ |
3685 | shape->contours = head; |
3686 | |
3687 | /* cast the output bitmap buffer */ |
3688 | t = (FT_SDFFormat*)bitmap->buffer; |
3689 | |
3690 | /* Iterate over all pixels and combine all separate */ |
3691 | /* contours. These are the rules for combining: */ |
3692 | /* */ |
3693 | /* (1) For all clockwise contours, compute the largest */ |
3694 | /* value. Name this as `val_c`. */ |
3695 | /* (2) For all counter-clockwise contours, compute the */ |
3696 | /* smallest value. Name this as `val_ac`. */ |
3697 | /* (3) Now, finally use the smaller value of `val_c' */ |
3698 | /* and `val_ac'. */ |
3699 | for ( j = 0; j < rows; j++ ) |
3700 | { |
3701 | for ( i = 0; i < width; i++ ) |
3702 | { |
3703 | FT_Int id = j * width + i; /* index of current pixel */ |
3704 | FT_Int c; /* contour iterator */ |
3705 | |
3706 | FT_SDFFormat val_c = 0; /* max clockwise value */ |
3707 | FT_SDFFormat val_ac = UCHAR_MAX; /* min counter-clockwise val */ |
3708 | |
3709 | |
3710 | /* iterate through all the contours */ |
3711 | for ( c = 0; c < num_contours; c++ ) |
3712 | { |
3713 | /* current contour value */ |
3714 | FT_SDFFormat temp = ( (FT_SDFFormat*)bitmaps[c].buffer )[id]; |
3715 | |
3716 | |
3717 | if ( orientations[c] == SDF_ORIENTATION_CW ) |
3718 | val_c = FT_MAX( val_c, temp ); /* clockwise */ |
3719 | else |
3720 | val_ac = FT_MIN( val_ac, temp ); /* counter-clockwise */ |
3721 | } |
3722 | |
3723 | /* Finally find the smaller of the two and assign to output. */ |
3724 | /* Also apply `flip_sign` if set. */ |
3725 | t[id] = FT_MIN( val_c, val_ac ); |
3726 | |
3727 | if ( flip_sign ) |
3728 | t[id] = invert_sign( t[id] ); |
3729 | } |
3730 | } |
3731 | |
3732 | Exit: |
3733 | /* deallocate orientations array */ |
3734 | if ( orientations ) |
3735 | FT_FREE( orientations ); |
3736 | |
3737 | /* deallocate temporary bitmaps */ |
3738 | if ( bitmaps ) |
3739 | { |
3740 | if ( num_contours == 0 ) |
3741 | error = FT_THROW( Raster_Corrupted ); |
3742 | else |
3743 | { |
3744 | for ( i = 0; i < num_contours; i++ ) |
3745 | FT_FREE( bitmaps[i].buffer ); |
3746 | |
3747 | FT_FREE( bitmaps ); |
3748 | } |
3749 | } |
3750 | |
3751 | /* restore the `flip_sign` property */ |
3752 | internal_params.flip_sign = flip_sign; |
3753 | |
3754 | return error; |
3755 | } |
3756 | |
3757 | |
3758 | /************************************************************************** |
3759 | * |
3760 | * interface functions |
3761 | * |
3762 | */ |
3763 | |
3764 | static FT_Error |
3765 | sdf_raster_new( void* memory_, /* FT_Memory */ |
3766 | FT_Raster* araster_ ) /* SDF_PRaster* */ |
3767 | { |
3768 | FT_Memory memory = (FT_Memory)memory_; |
3769 | SDF_PRaster* araster = (SDF_PRaster*)araster_; |
3770 | |
3771 | |
3772 | FT_Error error; |
3773 | SDF_PRaster raster = NULL; |
3774 | |
3775 | |
3776 | if ( !FT_NEW( raster ) ) |
3777 | raster->memory = memory; |
3778 | |
3779 | *araster = raster; |
3780 | |
3781 | return error; |
3782 | } |
3783 | |
3784 | |
3785 | static void |
3786 | sdf_raster_reset( FT_Raster raster, |
3787 | unsigned char* pool_base, |
3788 | unsigned long pool_size ) |
3789 | { |
3790 | FT_UNUSED( raster ); |
3791 | FT_UNUSED( pool_base ); |
3792 | FT_UNUSED( pool_size ); |
3793 | } |
3794 | |
3795 | |
3796 | static FT_Error |
3797 | sdf_raster_set_mode( FT_Raster raster, |
3798 | unsigned long mode, |
3799 | void* args ) |
3800 | { |
3801 | FT_UNUSED( raster ); |
3802 | FT_UNUSED( mode ); |
3803 | FT_UNUSED( args ); |
3804 | |
3805 | return FT_Err_Ok; |
3806 | } |
3807 | |
3808 | |
3809 | static FT_Error |
3810 | sdf_raster_render( FT_Raster raster, |
3811 | const FT_Raster_Params* params ) |
3812 | { |
3813 | FT_Error error = FT_Err_Ok; |
3814 | SDF_TRaster* sdf_raster = (SDF_TRaster*)raster; |
3815 | FT_Outline* outline = NULL; |
3816 | const SDF_Raster_Params* sdf_params = (const SDF_Raster_Params*)params; |
3817 | |
3818 | FT_Memory memory = NULL; |
3819 | SDF_Shape* shape = NULL; |
3820 | SDF_Params internal_params; |
3821 | |
3822 | |
3823 | /* check for valid arguments */ |
3824 | if ( !sdf_raster || !sdf_params ) |
3825 | { |
3826 | error = FT_THROW( Invalid_Argument ); |
3827 | goto Exit; |
3828 | } |
3829 | |
3830 | outline = (FT_Outline*)sdf_params->root.source; |
3831 | |
3832 | /* check whether outline is valid */ |
3833 | if ( !outline ) |
3834 | { |
3835 | error = FT_THROW( Invalid_Outline ); |
3836 | goto Exit; |
3837 | } |
3838 | |
3839 | /* if the outline is empty, return */ |
3840 | if ( outline->n_points <= 0 || outline->n_contours <= 0 ) |
3841 | goto Exit; |
3842 | |
3843 | /* check whether the outline has valid fields */ |
3844 | if ( !outline->contours || !outline->points ) |
3845 | { |
3846 | error = FT_THROW( Invalid_Outline ); |
3847 | goto Exit; |
3848 | } |
3849 | |
3850 | /* check whether spread is set properly */ |
3851 | if ( sdf_params->spread > MAX_SPREAD || |
3852 | sdf_params->spread < MIN_SPREAD ) |
3853 | { |
3854 | FT_TRACE0(( "sdf_raster_render:" |
3855 | " The `spread' field of `SDF_Raster_Params' is invalid,\n" )); |
3856 | FT_TRACE0(( " " |
3857 | " the value of this field must be within [%d, %d].\n" , |
3858 | MIN_SPREAD, MAX_SPREAD )); |
3859 | FT_TRACE0(( " " |
3860 | " Also, you must pass `SDF_Raster_Params' instead of\n" )); |
3861 | FT_TRACE0(( " " |
3862 | " the default `FT_Raster_Params' while calling\n" )); |
3863 | FT_TRACE0(( " " |
3864 | " this function and set the fields properly.\n" )); |
3865 | |
3866 | error = FT_THROW( Invalid_Argument ); |
3867 | goto Exit; |
3868 | } |
3869 | |
3870 | memory = sdf_raster->memory; |
3871 | if ( !memory ) |
3872 | { |
3873 | FT_TRACE0(( "sdf_raster_render:" |
3874 | " Raster not setup properly,\n" )); |
3875 | FT_TRACE0(( " " |
3876 | " unable to find memory handle.\n" )); |
3877 | |
3878 | error = FT_THROW( Invalid_Handle ); |
3879 | goto Exit; |
3880 | } |
3881 | |
3882 | /* set up the parameters */ |
3883 | internal_params.orientation = FT_Outline_Get_Orientation( outline ); |
3884 | internal_params.flip_sign = sdf_params->flip_sign; |
3885 | internal_params.flip_y = sdf_params->flip_y; |
3886 | internal_params.overload_sign = 0; |
3887 | |
3888 | FT_CALL( sdf_shape_new( memory, &shape ) ); |
3889 | |
3890 | FT_CALL( sdf_outline_decompose( outline, shape ) ); |
3891 | |
3892 | if ( sdf_params->overlaps ) |
3893 | FT_CALL( sdf_generate_with_overlaps( internal_params, |
3894 | shape, sdf_params->spread, |
3895 | sdf_params->root.target ) ); |
3896 | else |
3897 | FT_CALL( sdf_generate_subdivision( internal_params, |
3898 | shape, sdf_params->spread, |
3899 | sdf_params->root.target ) ); |
3900 | |
3901 | if ( shape ) |
3902 | sdf_shape_done( &shape ); |
3903 | |
3904 | Exit: |
3905 | return error; |
3906 | } |
3907 | |
3908 | |
3909 | static void |
3910 | sdf_raster_done( FT_Raster raster ) |
3911 | { |
3912 | FT_Memory memory = (FT_Memory)((SDF_TRaster*)raster)->memory; |
3913 | |
3914 | |
3915 | FT_FREE( raster ); |
3916 | } |
3917 | |
3918 | |
3919 | FT_DEFINE_RASTER_FUNCS( |
3920 | ft_sdf_raster, |
3921 | |
3922 | FT_GLYPH_FORMAT_OUTLINE, |
3923 | |
3924 | (FT_Raster_New_Func) sdf_raster_new, /* raster_new */ |
3925 | (FT_Raster_Reset_Func) sdf_raster_reset, /* raster_reset */ |
3926 | (FT_Raster_Set_Mode_Func)sdf_raster_set_mode, /* raster_set_mode */ |
3927 | (FT_Raster_Render_Func) sdf_raster_render, /* raster_render */ |
3928 | (FT_Raster_Done_Func) sdf_raster_done /* raster_done */ |
3929 | ) |
3930 | |
3931 | |
3932 | /* END */ |
3933 | |