1 /****************************************************************************
2 *
3 * pshints.c
4 *
5 * Adobe's code for handling CFF hints (body).
6 *
7 * Copyright 2007-2014 Adobe Systems Incorporated.
8 *
9 * This software, and all works of authorship, whether in source or
10 * object code form as indicated by the copyright notice(s) included
11 * herein (collectively, the "Work") is made available, and may only be
12 * used, modified, and distributed under the FreeType Project License,
13 * LICENSE.TXT. Additionally, subject to the terms and conditions of the
14 * FreeType Project License, each contributor to the Work hereby grants
15 * to any individual or legal entity exercising permissions granted by
16 * the FreeType Project License and this section (hereafter, "You" or
17 * "Your") a perpetual, worldwide, non-exclusive, no-charge,
18 * royalty-free, irrevocable (except as stated in this section) patent
19 * license to make, have made, use, offer to sell, sell, import, and
20 * otherwise transfer the Work, where such license applies only to those
21 * patent claims licensable by such contributor that are necessarily
22 * infringed by their contribution(s) alone or by combination of their
23 * contribution(s) with the Work to which such contribution(s) was
24 * submitted. If You institute patent litigation against any entity
25 * (including a cross-claim or counterclaim in a lawsuit) alleging that
26 * the Work or a contribution incorporated within the Work constitutes
27 * direct or contributory patent infringement, then any patent licenses
28 * granted to You under this License for that Work shall terminate as of
29 * the date such litigation is filed.
30 *
31 * By using, modifying, or distributing the Work you indicate that you
32 * have read and understood the terms and conditions of the
33 * FreeType Project License as well as those provided in this section,
34 * and you accept them fully.
35 *
36 */
37
38
39 #include "psft.h"
40 #include <freetype/internal/ftdebug.h>
41
42 #include "psglue.h"
43 #include "psfont.h"
44 #include "pshints.h"
45 #include "psintrp.h"
46
47
48 /**************************************************************************
49 *
50 * The macro FT_COMPONENT is used in trace mode. It is an implicit
51 * parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log
52 * messages during execution.
53 */
54 #undef FT_COMPONENT
55 #define FT_COMPONENT cf2hints
56
57
58 typedef struct CF2_HintMoveRec_
59 {
60 size_t j; /* index of upper hint map edge */
61 CF2_Fixed moveUp; /* adjustment to optimum position */
62
63 } CF2_HintMoveRec, *CF2_HintMove;
64
65
66 /* Compute angular momentum for winding order detection. It is called */
67 /* for all lines and curves, but not necessarily in element order. */
68 static CF2_Int
69 cf2_getWindingMomentum( CF2_Fixed x1,
70 CF2_Fixed y1,
71 CF2_Fixed x2,
72 CF2_Fixed y2 )
73 {
74 /* cross product of pt1 position from origin with pt2 position from */
75 /* pt1; we reduce the precision so that the result fits into 32 bits */
76
77 return ( x1 >> 16 ) * ( SUB_INT32( y2, y1 ) >> 16 ) -
78 ( y1 >> 16 ) * ( SUB_INT32( x2, x1 ) >> 16 );
79 }
80
81
82 /*
83 * Construct from a StemHint; this is used as a parameter to
84 * `cf2_blues_capture'.
85 * `hintOrigin' is the character space displacement of a seac accent.
86 * Adjust stem hint for darkening here.
87 *
88 */
89 static void
90 cf2_hint_init( CF2_Hint hint,
91 const CF2_ArrStack stemHintArray,
92 size_t indexStemHint,
93 const CF2_Font font,
94 CF2_Fixed hintOrigin,
95 CF2_Fixed scale,
96 FT_Bool bottom )
97 {
98 CF2_Fixed width;
99 const CF2_StemHintRec* stemHint;
100
101
102 FT_ZERO( hint );
103
104 stemHint = (const CF2_StemHintRec*)cf2_arrstack_getPointer(
105 stemHintArray,
106 indexStemHint );
107
108 width = SUB_INT32( stemHint->max, stemHint->min );
109
110 if ( width == cf2_intToFixed( -21 ) )
111 {
112 /* ghost bottom */
113
114 if ( bottom )
115 {
116 hint->csCoord = stemHint->max;
117 hint->flags = CF2_GhostBottom;
118 }
119 else
120 hint->flags = 0;
121 }
122
123 else if ( width == cf2_intToFixed( -20 ) )
124 {
125 /* ghost top */
126
127 if ( bottom )
128 hint->flags = 0;
129 else
130 {
131 hint->csCoord = stemHint->min;
132 hint->flags = CF2_GhostTop;
133 }
134 }
135
136 else if ( width < 0 )
137 {
138 /* inverted pair */
139
140 /*
141 * Hints with negative widths were produced by an early version of a
142 * non-Adobe font tool. The Type 2 spec allows edge (ghost) hints
143 * with negative widths, but says
144 *
145 * All other negative widths have undefined meaning.
146 *
147 * CoolType has a silent workaround that negates the hint width; for
148 * permissive mode, we do the same here.
149 *
150 * Note: Such fonts cannot use ghost hints, but should otherwise work.
151 * Note: Some poor hints in our faux fonts can produce negative
152 * widths at some blends. For example, see a light weight of
153 * `u' in ASerifMM.
154 *
155 */
156 if ( bottom )
157 {
158 hint->csCoord = stemHint->max;
159 hint->flags = CF2_PairBottom;
160 }
161 else
162 {
163 hint->csCoord = stemHint->min;
164 hint->flags = CF2_PairTop;
165 }
166 }
167
168 else
169 {
170 /* normal pair */
171
172 if ( bottom )
173 {
174 hint->csCoord = stemHint->min;
175 hint->flags = CF2_PairBottom;
176 }
177 else
178 {
179 hint->csCoord = stemHint->max;
180 hint->flags = CF2_PairTop;
181 }
182 }
183
184 /* Now that ghost hints have been detected, adjust this edge for */
185 /* darkening. Bottoms are not changed; tops are incremented by twice */
186 /* `darkenY'. */
187 if ( cf2_hint_isTop( hint ) )
188 hint->csCoord = ADD_INT32( hint->csCoord, 2 * font->darkenY );
189
190 hint->csCoord = ADD_INT32( hint->csCoord, hintOrigin );
191 hint->scale = scale;
192 hint->index = indexStemHint; /* index in original stem hint array */
193
194 /* if original stem hint has been used, use the same position */
195 if ( hint->flags != 0 && stemHint->used )
196 {
197 if ( cf2_hint_isTop( hint ) )
198 hint->dsCoord = stemHint->maxDS;
199 else
200 hint->dsCoord = stemHint->minDS;
201
202 cf2_hint_lock( hint );
203 }
204 else
205 hint->dsCoord = FT_MulFix( hint->csCoord, scale );
206 }
207
208
209 /* initialize an invalid hint map element */
210 static void
211 cf2_hint_initZero( CF2_Hint hint )
212 {
213 FT_ZERO( hint );
214 }
215
216
217 FT_LOCAL_DEF( FT_Bool )
218 cf2_hint_isValid( const CF2_Hint hint )
219 {
220 return FT_BOOL( hint->flags );
221 }
222
223
224 static FT_Bool
225 cf2_hint_isPair( const CF2_Hint hint )
226 {
227 return FT_BOOL( hint->flags & ( CF2_PairBottom | CF2_PairTop ) );
228 }
229
230
231 static FT_Bool
232 cf2_hint_isPairTop( const CF2_Hint hint )
233 {
234 return FT_BOOL( hint->flags & CF2_PairTop );
235 }
236
237
238 FT_LOCAL_DEF( FT_Bool )
239 cf2_hint_isTop( const CF2_Hint hint )
240 {
241 return FT_BOOL( hint->flags & ( CF2_PairTop | CF2_GhostTop ) );
242 }
243
244
245 FT_LOCAL_DEF( FT_Bool )
246 cf2_hint_isBottom( const CF2_Hint hint )
247 {
248 return FT_BOOL( hint->flags & ( CF2_PairBottom | CF2_GhostBottom ) );
249 }
250
251
252 static FT_Bool
253 cf2_hint_isLocked( const CF2_Hint hint )
254 {
255 return FT_BOOL( hint->flags & CF2_Locked );
256 }
257
258
259 static FT_Bool
260 cf2_hint_isSynthetic( const CF2_Hint hint )
261 {
262 return FT_BOOL( hint->flags & CF2_Synthetic );
263 }
264
265
266 FT_LOCAL_DEF( void )
267 cf2_hint_lock( CF2_Hint hint )
268 {
269 hint->flags |= CF2_Locked;
270 }
271
272
273 FT_LOCAL_DEF( void )
274 cf2_hintmap_init( CF2_HintMap hintmap,
275 CF2_Font font,
276 CF2_HintMap initialMap,
277 CF2_ArrStack hintMoves,
278 CF2_Fixed scale )
279 {
280 FT_ZERO( hintmap );
281
282 /* copy parameters from font instance */
283 hintmap->hinted = font->hinted;
284 hintmap->scale = scale;
285 hintmap->font = font;
286 hintmap->initialHintMap = initialMap;
287 /* will clear in `cf2_hintmap_adjustHints' */
288 hintmap->hintMoves = hintMoves;
289 }
290
291
292 static FT_Bool
293 cf2_hintmap_isValid( const CF2_HintMap hintmap )
294 {
295 return hintmap->isValid;
296 }
297
298
299 static void
300 cf2_hintmap_dump( CF2_HintMap hintmap )
301 {
302 #ifdef FT_DEBUG_LEVEL_TRACE
303 CF2_UInt i;
304
305
306 FT_TRACE6(( " index csCoord dsCoord scale flags\n" ));
307
308 for ( i = 0; i < hintmap->count; i++ )
309 {
310 CF2_Hint hint = &hintmap->edge[i];
311
312
313 FT_TRACE6(( " %3zu %7.2f %7.2f %5d %s%s%s%s\n",
314 hint->index,
315 hint->csCoord / 65536.0,
316 hint->dsCoord / ( hint->scale * 1.0 ),
317 hint->scale,
318 ( cf2_hint_isPair( hint ) ? "p" : "g" ),
319 ( cf2_hint_isTop( hint ) ? "t" : "b" ),
320 ( cf2_hint_isLocked( hint ) ? "L" : ""),
321 ( cf2_hint_isSynthetic( hint ) ? "S" : "" ) ));
322 }
323 #else
324 FT_UNUSED( hintmap );
325 #endif
326 }
327
328
329 /* transform character space coordinate to device space using hint map */
330 static CF2_Fixed
331 cf2_hintmap_map( CF2_HintMap hintmap,
332 CF2_Fixed csCoord )
333 {
334 if ( hintmap->count == 0 || !hintmap->hinted )
335 {
336 /* there are no hints; use uniform scale and zero offset */
337 return FT_MulFix( csCoord, hintmap->scale );
338 }
339 else
340 {
341 /* start linear search from last hit */
342 CF2_UInt i = hintmap->lastIndex;
343
344
345 FT_ASSERT( hintmap->lastIndex < CF2_MAX_HINT_EDGES );
346
347 /* search up */
348 while ( i < hintmap->count - 1 &&
349 csCoord >= hintmap->edge[i + 1].csCoord )
350 i += 1;
351
352 /* search down */
353 while ( i > 0 && csCoord < hintmap->edge[i].csCoord )
354 i -= 1;
355
356 hintmap->lastIndex = i;
357
358 if ( i == 0 && csCoord < hintmap->edge[0].csCoord )
359 {
360 /* special case for points below first edge: use uniform scale */
361 return ADD_INT32( FT_MulFix( SUB_INT32( csCoord,
362 hintmap->edge[0].csCoord ),
363 hintmap->scale ),
364 hintmap->edge[0].dsCoord );
365 }
366 else
367 {
368 /*
369 * Note: entries with duplicate csCoord are allowed.
370 * Use edge[i], the highest entry where csCoord >= entry[i].csCoord
371 */
372 return ADD_INT32( FT_MulFix( SUB_INT32( csCoord,
373 hintmap->edge[i].csCoord ),
374 hintmap->edge[i].scale ),
375 hintmap->edge[i].dsCoord );
376 }
377 }
378 }
379
380
381 /*
382 * This hinting policy moves a hint pair in device space so that one of
383 * its two edges is on a device pixel boundary (its fractional part is
384 * zero). `cf2_hintmap_insertHint' guarantees no overlap in CS
385 * space. Ensure here that there is no overlap in DS.
386 *
387 * In the first pass, edges are adjusted relative to adjacent hints.
388 * Those that are below have already been adjusted. Those that are
389 * above have not yet been adjusted. If a hint above blocks an
390 * adjustment to an optimal position, we will try again in a second
391 * pass. The second pass is top-down.
392 *
393 */
394
395 static void
396 cf2_hintmap_adjustHints( CF2_HintMap hintmap )
397 {
398 size_t i, j;
399
400
401 cf2_arrstack_clear( hintmap->hintMoves ); /* working storage */
402
403 /*
404 * First pass is bottom-up (font hint order) without look-ahead.
405 * Locked edges are already adjusted.
406 * Unlocked edges begin with dsCoord from `initialHintMap'.
407 * Save edges that are not optimally adjusted in `hintMoves' array,
408 * and process them in second pass.
409 */
410
411 for ( i = 0; i < hintmap->count; i++ )
412 {
413 FT_Bool isPair = cf2_hint_isPair( &hintmap->edge[i] );
414
415 /* final amount to move edge or edge pair */
416 CF2_Fixed move = 0;
417
418 CF2_Fixed dsCoord_i;
419 CF2_Fixed dsCoord_j;
420
421
422 /* index of upper edge (same value for ghost hint) */
423 j = isPair ? i + 1 : i;
424
425 FT_ASSERT( j < hintmap->count );
426 FT_ASSERT( cf2_hint_isValid( &hintmap->edge[i] ) );
427 FT_ASSERT( cf2_hint_isValid( &hintmap->edge[j] ) );
428 FT_ASSERT( cf2_hint_isLocked( &hintmap->edge[i] ) ==
429 cf2_hint_isLocked( &hintmap->edge[j] ) );
430
431 dsCoord_i = hintmap->edge[i].dsCoord;
432 dsCoord_j = hintmap->edge[j].dsCoord;
433
434 if ( !cf2_hint_isLocked( &hintmap->edge[i] ) )
435 {
436 /* hint edge is not locked, we can adjust it */
437 CF2_Fixed fracDown = cf2_fixedFraction( dsCoord_i );
438 CF2_Fixed fracUp = cf2_fixedFraction( dsCoord_j );
439
440 /* calculate all four possibilities; moves down are negative */
441 CF2_Fixed downMoveDown = 0 - fracDown;
442 CF2_Fixed upMoveDown = 0 - fracUp;
443 CF2_Fixed downMoveUp = ( fracDown == 0 )
444 ? 0
445 : cf2_intToFixed( 1 ) - fracDown;
446 CF2_Fixed upMoveUp = ( fracUp == 0 )
447 ? 0
448 : cf2_intToFixed( 1 ) - fracUp;
449
450 /* smallest move up */
451 CF2_Fixed moveUp = FT_MIN( downMoveUp, upMoveUp );
452 /* smallest move down */
453 CF2_Fixed moveDown = FT_MAX( downMoveDown, upMoveDown );
454
455 CF2_Fixed downMinCounter = CF2_MIN_COUNTER;
456 CF2_Fixed upMinCounter = CF2_MIN_COUNTER;
457 FT_Bool saveEdge = FALSE;
458
459
460 /* minimum counter constraint doesn't apply when adjacent edges */
461 /* are synthetic */
462 /* TODO: doesn't seem a big effect; for now, reduce the code */
463 #if 0
464 if ( i == 0 ||
465 cf2_hint_isSynthetic( &hintmap->edge[i - 1] ) )
466 downMinCounter = 0;
467
468 if ( j >= hintmap->count - 1 ||
469 cf2_hint_isSynthetic( &hintmap->edge[j + 1] ) )
470 upMinCounter = 0;
471 #endif
472
473 /* is there room to move up? */
474 /* there is if we are at top of array or the next edge is at or */
475 /* beyond proposed move up? */
476 if ( j >= hintmap->count - 1 ||
477 hintmap->edge[j + 1].dsCoord >=
478 ADD_INT32( dsCoord_j, moveUp + upMinCounter ) )
479 {
480 /* there is room to move up; is there also room to move down? */
481 if ( i == 0 ||
482 hintmap->edge[i - 1].dsCoord <=
483 ADD_INT32( dsCoord_i, moveDown - downMinCounter ) )
484 {
485 /* move smaller absolute amount */
486 move = ( -moveDown < moveUp ) ? moveDown : moveUp; /* optimum */
487 }
488 else
489 move = moveUp;
490 }
491 else
492 {
493 /* is there room to move down? */
494 if ( i == 0 ||
495 hintmap->edge[i - 1].dsCoord <=
496 ADD_INT32( dsCoord_i, moveDown - downMinCounter ) )
497 {
498 move = moveDown;
499 /* true if non-optimum move */
500 saveEdge = FT_BOOL( moveUp < -moveDown );
501 }
502 else
503 {
504 /* no room to move either way without overlapping or reducing */
505 /* the counter too much */
506 move = 0;
507 saveEdge = TRUE;
508 }
509 }
510
511 /* Identify non-moves and moves down that aren't optimal, and save */
512 /* them for second pass. */
513 /* Do this only if there is an unlocked edge above (which could */
514 /* possibly move). */
515 if ( saveEdge &&
516 j < hintmap->count - 1 &&
517 !cf2_hint_isLocked( &hintmap->edge[j + 1] ) )
518 {
519 CF2_HintMoveRec savedMove;
520
521
522 savedMove.j = j;
523 /* desired adjustment in second pass */
524 savedMove.moveUp = moveUp - move;
525
526 cf2_arrstack_push( hintmap->hintMoves, &savedMove );
527 }
528
529 /* move the edge(s) */
530 hintmap->edge[i].dsCoord = ADD_INT32( dsCoord_i, move );
531 if ( isPair )
532 hintmap->edge[j].dsCoord = ADD_INT32( dsCoord_j, move );
533 }
534
535 /* assert there are no overlaps in device space; */
536 /* ignore tests if there was overflow (that is, if */
537 /* operands have the same sign but the sum does not) */
538 FT_ASSERT( i == 0 ||
539 ( ( dsCoord_i ^ move ) >= 0 &&
540 ( dsCoord_i ^ hintmap->edge[i].dsCoord ) < 0 ) ||
541 hintmap->edge[i - 1].dsCoord <= hintmap->edge[i].dsCoord );
542 FT_ASSERT( i < j ||
543 ( ( dsCoord_j ^ move ) >= 0 &&
544 ( dsCoord_j ^ hintmap->edge[j].dsCoord ) < 0 ) ||
545 hintmap->edge[i].dsCoord <= hintmap->edge[j].dsCoord );
546
547 /* adjust the scales, avoiding divide by zero */
548 if ( i > 0 )
549 {
550 if ( hintmap->edge[i].csCoord != hintmap->edge[i - 1].csCoord )
551 hintmap->edge[i - 1].scale =
552 FT_DivFix( SUB_INT32( hintmap->edge[i].dsCoord,
553 hintmap->edge[i - 1].dsCoord ),
554 SUB_INT32( hintmap->edge[i].csCoord,
555 hintmap->edge[i - 1].csCoord ) );
556 }
557
558 if ( isPair )
559 {
560 if ( hintmap->edge[j].csCoord != hintmap->edge[j - 1].csCoord )
561 hintmap->edge[j - 1].scale =
562 FT_DivFix( SUB_INT32( hintmap->edge[j].dsCoord,
563 hintmap->edge[j - 1].dsCoord ),
564 SUB_INT32( hintmap->edge[j].csCoord,
565 hintmap->edge[j - 1].csCoord ) );
566
567 i += 1; /* skip upper edge on next loop */
568 }
569 }
570
571 /* second pass tries to move non-optimal hints up, in case there is */
572 /* room now */
573 for ( i = cf2_arrstack_size( hintmap->hintMoves ); i > 0; i-- )
574 {
575 CF2_HintMove hintMove = (CF2_HintMove)
576 cf2_arrstack_getPointer( hintmap->hintMoves, i - 1 );
577
578
579 j = hintMove->j;
580
581 /* this was tested before the push, above */
582 FT_ASSERT( j < hintmap->count - 1 );
583
584 /* is there room to move up? */
585 if ( hintmap->edge[j + 1].dsCoord >=
586 ADD_INT32( hintmap->edge[j].dsCoord,
587 hintMove->moveUp + CF2_MIN_COUNTER ) )
588 {
589 /* there is more room now, move edge up */
590 hintmap->edge[j].dsCoord = ADD_INT32( hintmap->edge[j].dsCoord,
591 hintMove->moveUp );
592
593 if ( cf2_hint_isPair( &hintmap->edge[j] ) )
594 {
595 FT_ASSERT( j > 0 );
596 hintmap->edge[j - 1].dsCoord =
597 ADD_INT32( hintmap->edge[j - 1].dsCoord, hintMove->moveUp );
598 }
599 }
600 }
601 }
602
603
604 /* insert hint edges into map, sorted by csCoord */
605 static void
606 cf2_hintmap_insertHint( CF2_HintMap hintmap,
607 CF2_Hint bottomHintEdge,
608 CF2_Hint topHintEdge )
609 {
610 CF2_UInt indexInsert;
611
612 /* set default values, then check for edge hints */
613 FT_Bool isPair = TRUE;
614 CF2_Hint firstHintEdge = bottomHintEdge;
615 CF2_Hint secondHintEdge = topHintEdge;
616
617
618 /* one or none of the input params may be invalid when dealing with */
619 /* edge hints; at least one edge must be valid */
620 FT_ASSERT( cf2_hint_isValid( bottomHintEdge ) ||
621 cf2_hint_isValid( topHintEdge ) );
622
623 /* determine how many and which edges to insert */
624 if ( !cf2_hint_isValid( bottomHintEdge ) )
625 {
626 /* insert only the top edge */
627 firstHintEdge = topHintEdge;
628 isPair = FALSE;
629 }
630 else if ( !cf2_hint_isValid( topHintEdge ) )
631 {
632 /* insert only the bottom edge */
633 isPair = FALSE;
634 }
635
636 /* paired edges must be in proper order */
637 if ( isPair &&
638 topHintEdge->csCoord < bottomHintEdge->csCoord )
639 return;
640
641 /* linear search to find index value of insertion point */
642 indexInsert = 0;
643 for ( ; indexInsert < hintmap->count; indexInsert++ )
644 {
645 if ( hintmap->edge[indexInsert].csCoord >= firstHintEdge->csCoord )
646 break;
647 }
648
649 FT_TRACE7(( " Got hint at %.2f (%.2f)\n",
650 firstHintEdge->csCoord / 65536.0,
651 firstHintEdge->dsCoord / 65536.0 ));
652 if ( isPair )
653 FT_TRACE7(( " Got hint at %.2f (%.2f)\n",
654 secondHintEdge->csCoord / 65536.0,
655 secondHintEdge->dsCoord / 65536.0 ));
656
657 /*
658 * Discard any hints that overlap in character space. Most often, this
659 * is while building the initial map, where captured hints from all
660 * zones are combined. Define overlap to include hints that `touch'
661 * (overlap zero). Hiragino Sans/Gothic fonts have numerous hints that
662 * touch. Some fonts have non-ideographic glyphs that overlap our
663 * synthetic hints.
664 *
665 * Overlap also occurs when darkening stem hints that are close.
666 *
667 */
668 if ( indexInsert < hintmap->count )
669 {
670 /* we are inserting before an existing edge: */
671 /* verify that an existing edge is not the same */
672 if ( hintmap->edge[indexInsert].csCoord == firstHintEdge->csCoord )
673 return; /* ignore overlapping stem hint */
674
675 /* verify that a new pair does not straddle the next edge */
676 if ( isPair &&
677 hintmap->edge[indexInsert].csCoord <= secondHintEdge->csCoord )
678 return; /* ignore overlapping stem hint */
679
680 /* verify that we are not inserting between paired edges */
681 if ( cf2_hint_isPairTop( &hintmap->edge[indexInsert] ) )
682 return; /* ignore overlapping stem hint */
683 }
684
685 /* recompute device space locations using initial hint map */
686 if ( cf2_hintmap_isValid( hintmap->initialHintMap ) &&
687 !cf2_hint_isLocked( firstHintEdge ) )
688 {
689 if ( isPair )
690 {
691 /* Use hint map to position the center of stem, and nominal scale */
692 /* to position the two edges. This preserves the stem width. */
693 CF2_Fixed midpoint =
694 cf2_hintmap_map(
695 hintmap->initialHintMap,
696 ADD_INT32(
697 firstHintEdge->csCoord,
698 SUB_INT32 ( secondHintEdge->csCoord,
699 firstHintEdge->csCoord ) / 2 ) );
700 CF2_Fixed halfWidth =
701 FT_MulFix( SUB_INT32( secondHintEdge->csCoord,
702 firstHintEdge->csCoord ) / 2,
703 hintmap->scale );
704
705
706 firstHintEdge->dsCoord = SUB_INT32( midpoint, halfWidth );
707 secondHintEdge->dsCoord = ADD_INT32( midpoint, halfWidth );
708 }
709 else
710 firstHintEdge->dsCoord = cf2_hintmap_map( hintmap->initialHintMap,
711 firstHintEdge->csCoord );
712 }
713
714 /*
715 * Discard any hints that overlap in device space; this can occur
716 * because locked hints have been moved to align with blue zones.
717 *
718 * TODO: Although we might correct this later during adjustment, we
719 * don't currently have a way to delete a conflicting hint once it has
720 * been inserted. See v2.030 MinionPro-Regular, 12 ppem darkened,
721 * initial hint map for second path, glyph 945 (the perispomeni (tilde)
722 * in U+1F6E, Greek omega with psili and perispomeni). Darkening is
723 * 25. Pair 667,747 initially conflicts in design space with top edge
724 * 660. This is because 667 maps to 7.87, and the top edge was
725 * captured by a zone at 8.0. The pair is later successfully inserted
726 * in a zone without the top edge. In this zone it is adjusted to 8.0,
727 * and no longer conflicts with the top edge in design space. This
728 * means it can be included in yet a later zone which does have the top
729 * edge hint. This produces a small mismatch between the first and
730 * last points of this path, even though the hint masks are the same.
731 * The density map difference is tiny (1/256).
732 *
733 */
734
735 if ( indexInsert > 0 )
736 {
737 /* we are inserting after an existing edge */
738 if ( firstHintEdge->dsCoord < hintmap->edge[indexInsert - 1].dsCoord )
739 return;
740 }
741
742 if ( indexInsert < hintmap->count )
743 {
744 /* we are inserting before an existing edge */
745 if ( isPair )
746 {
747 if ( secondHintEdge->dsCoord > hintmap->edge[indexInsert].dsCoord )
748 return;
749 }
750 else
751 {
752 if ( firstHintEdge->dsCoord > hintmap->edge[indexInsert].dsCoord )
753 return;
754 }
755 }
756
757 /* make room to insert */
758 {
759 CF2_UInt iSrc = hintmap->count - 1;
760 CF2_UInt iDst = isPair ? hintmap->count + 1 : hintmap->count;
761
762 CF2_UInt count = hintmap->count - indexInsert;
763
764
765 if ( iDst >= CF2_MAX_HINT_EDGES )
766 {
767 FT_TRACE4(( "cf2_hintmap_insertHint: too many hintmaps\n" ));
768 return;
769 }
770
771 while ( count-- )
772 hintmap->edge[iDst--] = hintmap->edge[iSrc--];
773
774 /* insert first edge */
775 hintmap->edge[indexInsert] = *firstHintEdge; /* copy struct */
776 hintmap->count += 1;
777
778 FT_TRACE7(( " Inserting hint %.2f (%.2f)\n",
779 firstHintEdge->csCoord / 65536.0,
780 firstHintEdge->dsCoord / 65536.0 ));
781
782 if ( isPair )
783 {
784 /* insert second edge */
785 hintmap->edge[indexInsert + 1] = *secondHintEdge; /* copy struct */
786 hintmap->count += 1;
787
788 FT_TRACE7(( " Inserting hint %.2f (%.2f)\n",
789 secondHintEdge->csCoord / 65536.0,
790 secondHintEdge->dsCoord / 65536.0 ));
791
792 }
793 }
794
795 return;
796 }
797
798
799 /*
800 * Build a map from hints and mask.
801 *
802 * This function may recur one level if `hintmap->initialHintMap' is not yet
803 * valid.
804 * If `initialMap' is true, simply build initial map.
805 *
806 * Synthetic hints are used in two ways. A hint at zero is inserted, if
807 * needed, in the initial hint map, to prevent translations from
808 * propagating across the origin. If synthetic em box hints are enabled
809 * for ideographic dictionaries, then they are inserted in all hint
810 * maps, including the initial one.
811 *
812 */
813 FT_LOCAL_DEF( void )
814 cf2_hintmap_build( CF2_HintMap hintmap,
815 CF2_ArrStack hStemHintArray,
816 CF2_ArrStack vStemHintArray,
817 CF2_HintMask hintMask,
818 CF2_Fixed hintOrigin,
819 FT_Bool initialMap )
820 {
821 FT_Byte* maskPtr;
822
823 CF2_Font font = hintmap->font;
824 CF2_HintMaskRec tempHintMask;
825
826 size_t bitCount, i;
827 FT_Byte maskByte;
828
829
830 /* check whether initial map is constructed */
831 if ( !initialMap && !cf2_hintmap_isValid( hintmap->initialHintMap ) )
832 {
833 /* make recursive call with initialHintMap and temporary mask; */
834 /* temporary mask will get all bits set, below */
835 cf2_hintmask_init( &tempHintMask, hintMask->error );
836 cf2_hintmap_build( hintmap->initialHintMap,
837 hStemHintArray,
838 vStemHintArray,
839 &tempHintMask,
840 hintOrigin,
841 TRUE );
842 }
843
844 if ( !cf2_hintmask_isValid( hintMask ) )
845 {
846 /* without a hint mask, assume all hints are active */
847 cf2_hintmask_setAll( hintMask,
848 cf2_arrstack_size( hStemHintArray ) +
849 cf2_arrstack_size( vStemHintArray ) );
850 if ( !cf2_hintmask_isValid( hintMask ) )
851 {
852 if ( font->isT1 )
853 {
854 /* no error, just continue unhinted */
855 *hintMask->error = FT_Err_Ok;
856 hintmap->hinted = FALSE;
857 }
858 return; /* too many stem hints */
859 }
860 }
861
862 /* begin by clearing the map */
863 hintmap->count = 0;
864 hintmap->lastIndex = 0;
865
866 /* make a copy of the hint mask so we can modify it */
867 tempHintMask = *hintMask;
868 maskPtr = cf2_hintmask_getMaskPtr( &tempHintMask );
869
870 /* use the hStem hints only, which are first in the mask */
871 bitCount = cf2_arrstack_size( hStemHintArray );
872
873 /* Defense-in-depth. Should never return here. */
874 if ( bitCount > hintMask->bitCount )
875 return;
876
877 /* synthetic embox hints get highest priority */
878 if ( font->blues.doEmBoxHints )
879 {
880 CF2_HintRec dummy;
881
882
883 cf2_hint_initZero( &dummy ); /* invalid hint map element */
884
885 /* ghost bottom */
886 cf2_hintmap_insertHint( hintmap,
887 &font->blues.emBoxBottomEdge,
888 &dummy );
889 /* ghost top */
890 cf2_hintmap_insertHint( hintmap,
891 &dummy,
892 &font->blues.emBoxTopEdge );
893 }
894
895 /* insert hints captured by a blue zone or already locked (higher */
896 /* priority) */
897 for ( i = 0, maskByte = 0x80; i < bitCount; i++ )
898 {
899 if ( maskByte & *maskPtr )
900 {
901 /* expand StemHint into two `CF2_Hint' elements */
902 CF2_HintRec bottomHintEdge, topHintEdge;
903
904
905 cf2_hint_init( &bottomHintEdge,
906 hStemHintArray,
907 i,
908 font,
909 hintOrigin,
910 hintmap->scale,
911 TRUE /* bottom */ );
912 cf2_hint_init( &topHintEdge,
913 hStemHintArray,
914 i,
915 font,
916 hintOrigin,
917 hintmap->scale,
918 FALSE /* top */ );
919
920 if ( cf2_hint_isLocked( &bottomHintEdge ) ||
921 cf2_hint_isLocked( &topHintEdge ) ||
922 cf2_blues_capture( &font->blues,
923 &bottomHintEdge,
924 &topHintEdge ) )
925 {
926 /* insert captured hint into map */
927 cf2_hintmap_insertHint( hintmap, &bottomHintEdge, &topHintEdge );
928
929 *maskPtr &= ~maskByte; /* turn off the bit for this hint */
930 }
931 }
932
933 if ( ( i & 7 ) == 7 )
934 {
935 /* move to next mask byte */
936 maskPtr++;
937 maskByte = 0x80;
938 }
939 else
940 maskByte >>= 1;
941 }
942
943 /* initial hint map includes only captured hints plus maybe one at 0 */
944
945 /*
946 * TODO: There is a problem here because we are trying to build a
947 * single hint map containing all captured hints. It is
948 * possible for there to be conflicts between captured hints,
949 * either because of darkening or because the hints are in
950 * separate hint zones (we are ignoring hint zones for the
951 * initial map). An example of the latter is MinionPro-Regular
952 * v2.030 glyph 883 (Greek Capital Alpha with Psili) at 15ppem.
953 * A stem hint for the psili conflicts with the top edge hint
954 * for the base character. The stem hint gets priority because
955 * of its sort order. In glyph 884 (Greek Capital Alpha with
956 * Psili and Oxia), the top of the base character gets a stem
957 * hint, and the psili does not. This creates different initial
958 * maps for the two glyphs resulting in different renderings of
959 * the base character. Will probably defer this either as not
960 * worth the cost or as a font bug. I don't think there is any
961 * good reason for an accent to be captured by an alignment
962 * zone. -darnold 2/12/10
963 */
964
965 if ( initialMap )
966 {
967 /* Apply a heuristic that inserts a point for (0,0), unless it's */
968 /* already covered by a mapping. This locks the baseline for glyphs */
969 /* that have no baseline hints. */
970
971 if ( hintmap->count == 0 ||
972 hintmap->edge[0].csCoord > 0 ||
973 hintmap->edge[hintmap->count - 1].csCoord < 0 )
974 {
975 /* all edges are above 0 or all edges are below 0; */
976 /* construct a locked edge hint at 0 */
977
978 CF2_HintRec edge, invalid;
979
980
981 cf2_hint_initZero( &edge );
982
983 edge.flags = CF2_GhostBottom |
984 CF2_Locked |
985 CF2_Synthetic;
986 edge.scale = hintmap->scale;
987
988 cf2_hint_initZero( &invalid );
989 cf2_hintmap_insertHint( hintmap, &edge, &invalid );
990 }
991 }
992 else
993 {
994 /* insert remaining hints */
995
996 maskPtr = cf2_hintmask_getMaskPtr( &tempHintMask );
997
998 for ( i = 0, maskByte = 0x80; i < bitCount; i++ )
999 {
1000 if ( maskByte & *maskPtr )
1001 {
1002 CF2_HintRec bottomHintEdge, topHintEdge;
1003
1004
1005 cf2_hint_init( &bottomHintEdge,
1006 hStemHintArray,
1007 i,
1008 font,
1009 hintOrigin,
1010 hintmap->scale,
1011 TRUE /* bottom */ );
1012 cf2_hint_init( &topHintEdge,
1013 hStemHintArray,
1014 i,
1015 font,
1016 hintOrigin,
1017 hintmap->scale,
1018 FALSE /* top */ );
1019
1020 cf2_hintmap_insertHint( hintmap, &bottomHintEdge, &topHintEdge );
1021 }
1022
1023 if ( ( i & 7 ) == 7 )
1024 {
1025 /* move to next mask byte */
1026 maskPtr++;
1027 maskByte = 0x80;
1028 }
1029 else
1030 maskByte >>= 1;
1031 }
1032 }
1033
1034 #ifdef FT_DEBUG_LEVEL_TRACE
1035 if ( initialMap )
1036 {
1037 FT_TRACE6(( "flags: [p]air [g]host [t]op"
1038 " [b]ottom [L]ocked [S]ynthetic\n" ));
1039 FT_TRACE6(( "Initial hintmap:\n" ));
1040 }
1041 else
1042 FT_TRACE6(( "Hints:\n" ));
1043 #endif
1044
1045 cf2_hintmap_dump( hintmap );
1046
1047 /*
1048 * Note: The following line is a convenient place to break when
1049 * debugging hinting. Examine `hintmap->edge' for the list of
1050 * enabled hints, then step over the call to see the effect of
1051 * adjustment. We stop here first on the recursive call that
1052 * creates the initial map, and then on each counter group and
1053 * hint zone.
1054 */
1055
1056 /* adjust positions of hint edges that are not locked to blue zones */
1057 cf2_hintmap_adjustHints( hintmap );
1058
1059 FT_TRACE6(( "Hints adjusted:\n" ));
1060 cf2_hintmap_dump( hintmap );
1061
1062 /* save the position of all hints that were used in this hint map; */
1063 /* if we use them again, we'll locate them in the same position */
1064 if ( !initialMap )
1065 {
1066 for ( i = 0; i < hintmap->count; i++ )
1067 {
1068 if ( !cf2_hint_isSynthetic( &hintmap->edge[i] ) )
1069 {
1070 /* Note: include both valid and invalid edges */
1071 /* Note: top and bottom edges are copied back separately */
1072 CF2_StemHint stemhint = (CF2_StemHint)
1073 cf2_arrstack_getPointer( hStemHintArray,
1074 hintmap->edge[i].index );
1075
1076
1077 if ( cf2_hint_isTop( &hintmap->edge[i] ) )
1078 stemhint->maxDS = hintmap->edge[i].dsCoord;
1079 else
1080 stemhint->minDS = hintmap->edge[i].dsCoord;
1081
1082 stemhint->used = TRUE;
1083 }
1084 }
1085 }
1086
1087 /* hint map is ready to use */
1088 hintmap->isValid = TRUE;
1089
1090 /* remember this mask has been used */
1091 cf2_hintmask_setNew( hintMask, FALSE );
1092 }
1093
1094
1095 FT_LOCAL_DEF( void )
1096 cf2_glyphpath_init( CF2_GlyphPath glyphpath,
1097 CF2_Font font,
1098 CF2_OutlineCallbacks callbacks,
1099 CF2_Fixed scaleY,
1100 /* CF2_Fixed hShift, */
1101 CF2_ArrStack hStemHintArray,
1102 CF2_ArrStack vStemHintArray,
1103 CF2_HintMask hintMask,
1104 CF2_Fixed hintOriginY,
1105 const CF2_Blues blues,
1106 const FT_Vector* fractionalTranslation )
1107 {
1108 FT_ZERO( glyphpath );
1109
1110 glyphpath->font = font;
1111 glyphpath->callbacks = callbacks;
1112
1113 cf2_arrstack_init( &glyphpath->hintMoves,
1114 font->memory,
1115 &font->error,
1116 sizeof ( CF2_HintMoveRec ) );
1117
1118 cf2_hintmap_init( &glyphpath->initialHintMap,
1119 font,
1120 &glyphpath->initialHintMap,
1121 &glyphpath->hintMoves,
1122 scaleY );
1123 cf2_hintmap_init( &glyphpath->firstHintMap,
1124 font,
1125 &glyphpath->initialHintMap,
1126 &glyphpath->hintMoves,
1127 scaleY );
1128 cf2_hintmap_init( &glyphpath->hintMap,
1129 font,
1130 &glyphpath->initialHintMap,
1131 &glyphpath->hintMoves,
1132 scaleY );
1133
1134 glyphpath->scaleX = font->innerTransform.a;
1135 glyphpath->scaleC = font->innerTransform.c;
1136 glyphpath->scaleY = font->innerTransform.d;
1137
1138 glyphpath->fractionalTranslation = *fractionalTranslation;
1139
1140 #if 0
1141 glyphpath->hShift = hShift; /* for fauxing */
1142 #endif
1143
1144 glyphpath->hStemHintArray = hStemHintArray;
1145 glyphpath->vStemHintArray = vStemHintArray;
1146 glyphpath->hintMask = hintMask; /* ptr to current mask */
1147 glyphpath->hintOriginY = hintOriginY;
1148 glyphpath->blues = blues;
1149 glyphpath->darken = font->darkened; /* TODO: should we make copies? */
1150 glyphpath->xOffset = font->darkenX;
1151 glyphpath->yOffset = font->darkenY;
1152 glyphpath->miterLimit = 2 * FT_MAX(
1153 cf2_fixedAbs( glyphpath->xOffset ),
1154 cf2_fixedAbs( glyphpath->yOffset ) );
1155
1156 /* .1 character space unit */
1157 glyphpath->snapThreshold = cf2_doubleToFixed( 0.1 );
1158
1159 glyphpath->moveIsPending = TRUE;
1160 glyphpath->pathIsOpen = FALSE;
1161 glyphpath->pathIsClosing = FALSE;
1162 glyphpath->elemIsQueued = FALSE;
1163 }
1164
1165
1166 FT_LOCAL_DEF( void )
1167 cf2_glyphpath_finalize( CF2_GlyphPath glyphpath )
1168 {
1169 cf2_arrstack_finalize( &glyphpath->hintMoves );
1170 }
1171
1172
1173 /*
1174 * Hint point in y-direction and apply outerTransform.
1175 * Input `current' hint map (which is actually delayed by one element).
1176 * Input x,y point in Character Space.
1177 * Output x,y point in Device Space, including translation.
1178 */
1179 static void
1180 cf2_glyphpath_hintPoint( CF2_GlyphPath glyphpath,
1181 CF2_HintMap hintmap,
1182 FT_Vector* ppt,
1183 CF2_Fixed x,
1184 CF2_Fixed y )
1185 {
1186 FT_Vector pt; /* hinted point in upright DS */
1187
1188
1189 pt.x = ADD_INT32( FT_MulFix( glyphpath->scaleX, x ),
1190 FT_MulFix( glyphpath->scaleC, y ) );
1191 pt.y = cf2_hintmap_map( hintmap, y );
1192
1193 ppt->x = ADD_INT32(
1194 FT_MulFix( glyphpath->font->outerTransform.a, pt.x ),
1195 ADD_INT32(
1196 FT_MulFix( glyphpath->font->outerTransform.c, pt.y ),
1197 glyphpath->fractionalTranslation.x ) );
1198 ppt->y = ADD_INT32(
1199 FT_MulFix( glyphpath->font->outerTransform.b, pt.x ),
1200 ADD_INT32(
1201 FT_MulFix( glyphpath->font->outerTransform.d, pt.y ),
1202 glyphpath->fractionalTranslation.y ) );
1203 }
1204
1205
1206 /*
1207 * From two line segments, (u1,u2) and (v1,v2), compute a point of
1208 * intersection on the corresponding lines.
1209 * Return false if no intersection is found, or if the intersection is
1210 * too far away from the ends of the line segments, u2 and v1.
1211 *
1212 */
1213 static FT_Bool
1214 cf2_glyphpath_computeIntersection( CF2_GlyphPath glyphpath,
1215 const FT_Vector* u1,
1216 const FT_Vector* u2,
1217 const FT_Vector* v1,
1218 const FT_Vector* v2,
1219 FT_Vector* intersection )
1220 {
1221 /*
1222 * Let `u' be a zero-based vector from the first segment, `v' from the
1223 * second segment.
1224 * Let `w 'be the zero-based vector from `u1' to `v1'.
1225 * `perp' is the `perpendicular dot product'; see
1226 * https://mathworld.wolfram.com/PerpDotProduct.html.
1227 * `s' is the parameter for the parametric line for the first segment
1228 * (`u').
1229 *
1230 * See notation in
1231 * http://geomalgorithms.com/a05-_intersect-1.html.
1232 * Calculations are done in 16.16, but must handle the squaring of
1233 * line lengths in character space. We scale all vectors by 1/32 to
1234 * avoid overflow. This allows values up to 4095 to be squared. The
1235 * scale factor cancels in the divide.
1236 *
1237 * TODO: the scale factor could be computed from UnitsPerEm.
1238 *
1239 */
1240
1241 #define cf2_perp( a, b ) \
1242 ( FT_MulFix( a.x, b.y ) - FT_MulFix( a.y, b.x ) )
1243
1244 /* round and divide by 32 */
1245 #define CF2_CS_SCALE( x ) \
1246 ( ( (x) + 0x10 ) >> 5 )
1247
1248 FT_Vector u, v, w; /* scaled vectors */
1249 CF2_Fixed denominator, s;
1250
1251
1252 u.x = CF2_CS_SCALE( SUB_INT32( u2->x, u1->x ) );
1253 u.y = CF2_CS_SCALE( SUB_INT32( u2->y, u1->y ) );
1254 v.x = CF2_CS_SCALE( SUB_INT32( v2->x, v1->x ) );
1255 v.y = CF2_CS_SCALE( SUB_INT32( v2->y, v1->y ) );
1256 w.x = CF2_CS_SCALE( SUB_INT32( v1->x, u1->x ) );
1257 w.y = CF2_CS_SCALE( SUB_INT32( v1->y, u1->y ) );
1258
1259 denominator = cf2_perp( u, v );
1260
1261 if ( denominator == 0 )
1262 return FALSE; /* parallel or coincident lines */
1263
1264 s = FT_DivFix( cf2_perp( w, v ), denominator );
1265
1266 intersection->x = ADD_INT32( u1->x,
1267 FT_MulFix( s, SUB_INT32( u2->x, u1->x ) ) );
1268 intersection->y = ADD_INT32( u1->y,
1269 FT_MulFix( s, SUB_INT32( u2->y, u1->y ) ) );
1270
1271
1272 /*
1273 * Special case snapping for horizontal and vertical lines.
1274 * This cleans up intersections and reduces problems with winding
1275 * order detection.
1276 * Sample case is sbc cd KozGoPr6N-Medium.otf 20 16685.
1277 * Note: these calculations are in character space.
1278 *
1279 */
1280
1281 if ( u1->x == u2->x &&
1282 cf2_fixedAbs( SUB_INT32( intersection->x,
1283 u1->x ) ) < glyphpath->snapThreshold )
1284 intersection->x = u1->x;
1285 if ( u1->y == u2->y &&
1286 cf2_fixedAbs( SUB_INT32( intersection->y,
1287 u1->y ) ) < glyphpath->snapThreshold )
1288 intersection->y = u1->y;
1289
1290 if ( v1->x == v2->x &&
1291 cf2_fixedAbs( SUB_INT32( intersection->x,
1292 v1->x ) ) < glyphpath->snapThreshold )
1293 intersection->x = v1->x;
1294 if ( v1->y == v2->y &&
1295 cf2_fixedAbs( SUB_INT32( intersection->y,
1296 v1->y ) ) < glyphpath->snapThreshold )
1297 intersection->y = v1->y;
1298
1299 /* limit the intersection distance from midpoint of u2 and v1 */
1300 if ( cf2_fixedAbs( intersection->x - ADD_INT32( u2->x, v1->x ) / 2 ) >
1301 glyphpath->miterLimit ||
1302 cf2_fixedAbs( intersection->y - ADD_INT32( u2->y, v1->y ) / 2 ) >
1303 glyphpath->miterLimit )
1304 return FALSE;
1305
1306 return TRUE;
1307 }
1308
1309
1310 /*
1311 * Push the cached element (glyphpath->prevElem*) to the outline
1312 * consumer. When a darkening offset is used, the end point of the
1313 * cached element may be adjusted to an intersection point or we may
1314 * synthesize a connecting line to the current element. If we are
1315 * closing a subpath, we may also generate a connecting line to the start
1316 * point.
1317 *
1318 * This is where Character Space (CS) is converted to Device Space (DS)
1319 * using a hint map. This calculation must use a HintMap that was valid
1320 * at the time the element was saved. For the first point in a subpath,
1321 * that is a saved HintMap. For most elements, it just means the caller
1322 * has delayed building a HintMap from the current HintMask.
1323 *
1324 * Transform each point with outerTransform and call the outline
1325 * callbacks. This is a general 3x3 transform:
1326 *
1327 * x' = a*x + c*y + tx, y' = b*x + d*y + ty
1328 *
1329 * but it uses 4 elements from CF2_Font and the translation part
1330 * from CF2_GlyphPath.
1331 *
1332 */
1333 static void
1334 cf2_glyphpath_pushPrevElem( CF2_GlyphPath glyphpath,
1335 CF2_HintMap hintmap,
1336 FT_Vector* nextP0,
1337 FT_Vector nextP1,
1338 FT_Bool close )
1339 {
1340 CF2_CallbackParamsRec params;
1341
1342 FT_Vector* prevP0;
1343 FT_Vector* prevP1;
1344
1345 FT_Vector intersection = { 0, 0 };
1346 FT_Bool useIntersection = FALSE;
1347
1348
1349 FT_ASSERT( glyphpath->prevElemOp == CF2_PathOpLineTo ||
1350 glyphpath->prevElemOp == CF2_PathOpCubeTo );
1351
1352 if ( glyphpath->prevElemOp == CF2_PathOpLineTo )
1353 {
1354 prevP0 = &glyphpath->prevElemP0;
1355 prevP1 = &glyphpath->prevElemP1;
1356 }
1357 else
1358 {
1359 prevP0 = &glyphpath->prevElemP2;
1360 prevP1 = &glyphpath->prevElemP3;
1361 }
1362
1363 /* optimization: if previous and next elements are offset by the same */
1364 /* amount, then there will be no gap, and no need to compute an */
1365 /* intersection. */
1366 if ( prevP1->x != nextP0->x || prevP1->y != nextP0->y )
1367 {
1368 /* previous element does not join next element: */
1369 /* adjust end point of previous element to the intersection */
1370 useIntersection = cf2_glyphpath_computeIntersection( glyphpath,
1371 prevP0,
1372 prevP1,
1373 nextP0,
1374 &nextP1,
1375 &intersection );
1376 if ( useIntersection )
1377 {
1378 /* modify the last point of the cached element (either line or */
1379 /* curve) */
1380 *prevP1 = intersection;
1381 }
1382 }
1383
1384 params.pt0 = glyphpath->currentDS;
1385
1386 switch( glyphpath->prevElemOp )
1387 {
1388 case CF2_PathOpLineTo:
1389 params.op = CF2_PathOpLineTo;
1390
1391 /* note: pt2 and pt3 are unused */
1392
1393 if ( close )
1394 {
1395 /* use first hint map if closing */
1396 cf2_glyphpath_hintPoint( glyphpath,
1397 &glyphpath->firstHintMap,
1398 ¶ms.pt1,
1399 glyphpath->prevElemP1.x,
1400 glyphpath->prevElemP1.y );
1401 }
1402 else
1403 {
1404 cf2_glyphpath_hintPoint( glyphpath,
1405 hintmap,
1406 ¶ms.pt1,
1407 glyphpath->prevElemP1.x,
1408 glyphpath->prevElemP1.y );
1409 }
1410
1411 /* output only non-zero length lines */
1412 if ( params.pt0.x != params.pt1.x || params.pt0.y != params.pt1.y )
1413 {
1414 glyphpath->callbacks->lineTo( glyphpath->callbacks, ¶ms );
1415
1416 glyphpath->currentDS = params.pt1;
1417 }
1418 break;
1419
1420 case CF2_PathOpCubeTo:
1421 params.op = CF2_PathOpCubeTo;
1422
1423 /* TODO: should we intersect the interior joins (p1-p2 and p2-p3)? */
1424 cf2_glyphpath_hintPoint( glyphpath,
1425 hintmap,
1426 ¶ms.pt1,
1427 glyphpath->prevElemP1.x,
1428 glyphpath->prevElemP1.y );
1429 cf2_glyphpath_hintPoint( glyphpath,
1430 hintmap,
1431 ¶ms.pt2,
1432 glyphpath->prevElemP2.x,
1433 glyphpath->prevElemP2.y );
1434 cf2_glyphpath_hintPoint( glyphpath,
1435 hintmap,
1436 ¶ms.pt3,
1437 glyphpath->prevElemP3.x,
1438 glyphpath->prevElemP3.y );
1439
1440 glyphpath->callbacks->cubeTo( glyphpath->callbacks, ¶ms );
1441
1442 glyphpath->currentDS = params.pt3;
1443
1444 break;
1445 }
1446
1447 if ( !useIntersection || close )
1448 {
1449 /* insert connecting line between end of previous element and start */
1450 /* of current one */
1451 /* note: at the end of a subpath, we might do both, so use `nextP0' */
1452 /* before we change it, below */
1453
1454 if ( close )
1455 {
1456 /* if we are closing the subpath, then nextP0 is in the first */
1457 /* hint zone */
1458 cf2_glyphpath_hintPoint( glyphpath,
1459 &glyphpath->firstHintMap,
1460 ¶ms.pt1,
1461 nextP0->x,
1462 nextP0->y );
1463 }
1464 else
1465 {
1466 cf2_glyphpath_hintPoint( glyphpath,
1467 hintmap,
1468 ¶ms.pt1,
1469 nextP0->x,
1470 nextP0->y );
1471 }
1472
1473 if ( params.pt1.x != glyphpath->currentDS.x ||
1474 params.pt1.y != glyphpath->currentDS.y )
1475 {
1476 /* length is nonzero */
1477 params.op = CF2_PathOpLineTo;
1478 params.pt0 = glyphpath->currentDS;
1479
1480 /* note: pt2 and pt3 are unused */
1481 glyphpath->callbacks->lineTo( glyphpath->callbacks, ¶ms );
1482
1483 glyphpath->currentDS = params.pt1;
1484 }
1485 }
1486
1487 if ( useIntersection )
1488 {
1489 /* return intersection point to caller */
1490 *nextP0 = intersection;
1491 }
1492 }
1493
1494
1495 /* push a MoveTo element based on current point and offset of current */
1496 /* element */
1497 static void
1498 cf2_glyphpath_pushMove( CF2_GlyphPath glyphpath,
1499 FT_Vector start )
1500 {
1501 CF2_CallbackParamsRec params;
1502
1503
1504 params.op = CF2_PathOpMoveTo;
1505 params.pt0 = glyphpath->currentDS;
1506
1507 /* Test if move has really happened yet; it would have called */
1508 /* `cf2_hintmap_build' to set `isValid'. */
1509 if ( !cf2_hintmap_isValid( &glyphpath->hintMap ) )
1510 {
1511 /* we are here iff first subpath is missing a moveto operator: */
1512 /* synthesize first moveTo to finish initialization of hintMap */
1513 cf2_glyphpath_moveTo( glyphpath,
1514 glyphpath->start.x,
1515 glyphpath->start.y );
1516 }
1517
1518 cf2_glyphpath_hintPoint( glyphpath,
1519 &glyphpath->hintMap,
1520 ¶ms.pt1,
1521 start.x,
1522 start.y );
1523
1524 /* note: pt2 and pt3 are unused */
1525 glyphpath->callbacks->moveTo( glyphpath->callbacks, ¶ms );
1526
1527 glyphpath->currentDS = params.pt1;
1528 glyphpath->offsetStart0 = start;
1529 }
1530
1531
1532 /*
1533 * All coordinates are in character space.
1534 * On input, (x1, y1) and (x2, y2) give line segment.
1535 * On output, (x, y) give offset vector.
1536 * We use a piecewise approximation to trig functions.
1537 *
1538 * TODO: Offset true perpendicular and proper length
1539 * supply the y-translation for hinting here, too,
1540 * that adds yOffset unconditionally to *y.
1541 */
1542 static void
1543 cf2_glyphpath_computeOffset( CF2_GlyphPath glyphpath,
1544 CF2_Fixed x1,
1545 CF2_Fixed y1,
1546 CF2_Fixed x2,
1547 CF2_Fixed y2,
1548 CF2_Fixed* x,
1549 CF2_Fixed* y )
1550 {
1551 CF2_Fixed dx = SUB_INT32( x2, x1 );
1552 CF2_Fixed dy = SUB_INT32( y2, y1 );
1553
1554
1555 /* note: negative offsets don't work here; negate deltas to change */
1556 /* quadrants, below */
1557 if ( glyphpath->font->reverseWinding )
1558 {
1559 dx = NEG_INT32( dx );
1560 dy = NEG_INT32( dy );
1561 }
1562
1563 *x = *y = 0;
1564
1565 if ( !glyphpath->darken )
1566 return;
1567
1568 /* add momentum for this path element */
1569 glyphpath->callbacks->windingMomentum =
1570 ADD_INT32( glyphpath->callbacks->windingMomentum,
1571 cf2_getWindingMomentum( x1, y1, x2, y2 ) );
1572
1573 /* note: allow mixed integer and fixed multiplication here */
1574 if ( dx >= 0 )
1575 {
1576 if ( dy >= 0 )
1577 {
1578 /* first quadrant, +x +y */
1579
1580 if ( dx > MUL_INT32( 2, dy ) )
1581 {
1582 /* +x */
1583 *x = 0;
1584 *y = 0;
1585 }
1586 else if ( dy > MUL_INT32( 2, dx ) )
1587 {
1588 /* +y */
1589 *x = glyphpath->xOffset;
1590 *y = glyphpath->yOffset;
1591 }
1592 else
1593 {
1594 /* +x +y */
1595 *x = FT_MulFix( cf2_doubleToFixed( 0.7 ),
1596 glyphpath->xOffset );
1597 *y = FT_MulFix( cf2_doubleToFixed( 1.0 - 0.7 ),
1598 glyphpath->yOffset );
1599 }
1600 }
1601 else
1602 {
1603 /* fourth quadrant, +x -y */
1604
1605 if ( dx > MUL_INT32( -2, dy ) )
1606 {
1607 /* +x */
1608 *x = 0;
1609 *y = 0;
1610 }
1611 else if ( NEG_INT32( dy ) > MUL_INT32( 2, dx ) )
1612 {
1613 /* -y */
1614 *x = NEG_INT32( glyphpath->xOffset );
1615 *y = glyphpath->yOffset;
1616 }
1617 else
1618 {
1619 /* +x -y */
1620 *x = FT_MulFix( cf2_doubleToFixed( -0.7 ),
1621 glyphpath->xOffset );
1622 *y = FT_MulFix( cf2_doubleToFixed( 1.0 - 0.7 ),
1623 glyphpath->yOffset );
1624 }
1625 }
1626 }
1627 else
1628 {
1629 if ( dy >= 0 )
1630 {
1631 /* second quadrant, -x +y */
1632
1633 if ( NEG_INT32( dx ) > MUL_INT32( 2, dy ) )
1634 {
1635 /* -x */
1636 *x = 0;
1637 *y = MUL_INT32( 2, glyphpath->yOffset );
1638 }
1639 else if ( dy > MUL_INT32( -2, dx ) )
1640 {
1641 /* +y */
1642 *x = glyphpath->xOffset;
1643 *y = glyphpath->yOffset;
1644 }
1645 else
1646 {
1647 /* -x +y */
1648 *x = FT_MulFix( cf2_doubleToFixed( 0.7 ),
1649 glyphpath->xOffset );
1650 *y = FT_MulFix( cf2_doubleToFixed( 1.0 + 0.7 ),
1651 glyphpath->yOffset );
1652 }
1653 }
1654 else
1655 {
1656 /* third quadrant, -x -y */
1657
1658 if ( NEG_INT32( dx ) > MUL_INT32( -2, dy ) )
1659 {
1660 /* -x */
1661 *x = 0;
1662 *y = MUL_INT32( 2, glyphpath->yOffset );
1663 }
1664 else if ( NEG_INT32( dy ) > MUL_INT32( -2, dx ) )
1665 {
1666 /* -y */
1667 *x = NEG_INT32( glyphpath->xOffset );
1668 *y = glyphpath->yOffset;
1669 }
1670 else
1671 {
1672 /* -x -y */
1673 *x = FT_MulFix( cf2_doubleToFixed( -0.7 ),
1674 glyphpath->xOffset );
1675 *y = FT_MulFix( cf2_doubleToFixed( 1.0 + 0.7 ),
1676 glyphpath->yOffset );
1677 }
1678 }
1679 }
1680 }
1681
1682
1683 /*
1684 * The functions cf2_glyphpath_{moveTo,lineTo,curveTo,closeOpenPath} are
1685 * called by the interpreter with Character Space (CS) coordinates. Each
1686 * path element is placed into a queue of length one to await the
1687 * calculation of the following element. At that time, the darkening
1688 * offset of the following element is known and joins can be computed,
1689 * including possible modification of this element, before mapping to
1690 * Device Space (DS) and passing it on to the outline consumer.
1691 *
1692 */
1693 FT_LOCAL_DEF( void )
1694 cf2_glyphpath_moveTo( CF2_GlyphPath glyphpath,
1695 CF2_Fixed x,
1696 CF2_Fixed y )
1697 {
1698 cf2_glyphpath_closeOpenPath( glyphpath );
1699
1700 /* save the parameters of the move for later, when we'll know how to */
1701 /* offset it; */
1702 /* also save last move point */
1703 glyphpath->currentCS.x = glyphpath->start.x = x;
1704 glyphpath->currentCS.y = glyphpath->start.y = y;
1705
1706 glyphpath->moveIsPending = TRUE;
1707
1708 /* ensure we have a valid map with current mask */
1709 if ( !cf2_hintmap_isValid( &glyphpath->hintMap ) ||
1710 cf2_hintmask_isNew( glyphpath->hintMask ) )
1711 cf2_hintmap_build( &glyphpath->hintMap,
1712 glyphpath->hStemHintArray,
1713 glyphpath->vStemHintArray,
1714 glyphpath->hintMask,
1715 glyphpath->hintOriginY,
1716 FALSE );
1717
1718 /* save a copy of current HintMap to use when drawing initial point */
1719 glyphpath->firstHintMap = glyphpath->hintMap; /* structure copy */
1720 }
1721
1722
1723 FT_LOCAL_DEF( void )
1724 cf2_glyphpath_lineTo( CF2_GlyphPath glyphpath,
1725 CF2_Fixed x,
1726 CF2_Fixed y )
1727 {
1728 CF2_Fixed xOffset, yOffset;
1729 FT_Vector P0, P1;
1730 FT_Bool newHintMap;
1731
1732 /*
1733 * New hints will be applied after cf2_glyphpath_pushPrevElem has run.
1734 * In case this is a synthesized closing line, any new hints should be
1735 * delayed until this path is closed (`cf2_hintmask_isNew' will be
1736 * called again before the next line or curve).
1737 */
1738
1739 /* true if new hint map not on close */
1740 newHintMap = cf2_hintmask_isNew( glyphpath->hintMask ) &&
1741 !glyphpath->pathIsClosing;
1742
1743 /*
1744 * Zero-length lines may occur in the charstring. Because we cannot
1745 * compute darkening offsets or intersections from zero-length lines,
1746 * it is best to remove them and avoid artifacts. However, zero-length
1747 * lines in CS at the start of a new hint map can generate non-zero
1748 * lines in DS due to hint substitution. We detect a change in hint
1749 * map here and pass those zero-length lines along.
1750 */
1751
1752 /*
1753 * Note: Find explicitly closed paths here with a conditional
1754 * breakpoint using
1755 *
1756 * !gp->pathIsClosing && gp->start.x == x && gp->start.y == y
1757 *
1758 */
1759
1760 if ( glyphpath->currentCS.x == x &&
1761 glyphpath->currentCS.y == y &&
1762 !newHintMap )
1763 /*
1764 * Ignore zero-length lines in CS where the hint map is the same
1765 * because the line in DS will also be zero length.
1766 *
1767 * Ignore zero-length lines when we synthesize a closing line because
1768 * the close will be handled in cf2_glyphPath_pushPrevElem.
1769 */
1770 return;
1771
1772 cf2_glyphpath_computeOffset( glyphpath,
1773 glyphpath->currentCS.x,
1774 glyphpath->currentCS.y,
1775 x,
1776 y,
1777 &xOffset,
1778 &yOffset );
1779
1780 /* construct offset points */
1781 P0.x = ADD_INT32( glyphpath->currentCS.x, xOffset );
1782 P0.y = ADD_INT32( glyphpath->currentCS.y, yOffset );
1783 P1.x = ADD_INT32( x, xOffset );
1784 P1.y = ADD_INT32( y, yOffset );
1785
1786 if ( glyphpath->moveIsPending )
1787 {
1788 /* emit offset 1st point as MoveTo */
1789 cf2_glyphpath_pushMove( glyphpath, P0 );
1790
1791 glyphpath->moveIsPending = FALSE; /* adjust state machine */
1792 glyphpath->pathIsOpen = TRUE;
1793
1794 glyphpath->offsetStart1 = P1; /* record second point */
1795 }
1796
1797 if ( glyphpath->elemIsQueued )
1798 {
1799 FT_ASSERT( cf2_hintmap_isValid( &glyphpath->hintMap ) ||
1800 glyphpath->hintMap.count == 0 );
1801
1802 cf2_glyphpath_pushPrevElem( glyphpath,
1803 &glyphpath->hintMap,
1804 &P0,
1805 P1,
1806 FALSE );
1807 }
1808
1809 /* queue the current element with offset points */
1810 glyphpath->elemIsQueued = TRUE;
1811 glyphpath->prevElemOp = CF2_PathOpLineTo;
1812 glyphpath->prevElemP0 = P0;
1813 glyphpath->prevElemP1 = P1;
1814
1815 /* update current map */
1816 if ( newHintMap )
1817 cf2_hintmap_build( &glyphpath->hintMap,
1818 glyphpath->hStemHintArray,
1819 glyphpath->vStemHintArray,
1820 glyphpath->hintMask,
1821 glyphpath->hintOriginY,
1822 FALSE );
1823
1824 glyphpath->currentCS.x = x; /* pre-offset current point */
1825 glyphpath->currentCS.y = y;
1826 }
1827
1828
1829 FT_LOCAL_DEF( void )
1830 cf2_glyphpath_curveTo( CF2_GlyphPath glyphpath,
1831 CF2_Fixed x1,
1832 CF2_Fixed y1,
1833 CF2_Fixed x2,
1834 CF2_Fixed y2,
1835 CF2_Fixed x3,
1836 CF2_Fixed y3 )
1837 {
1838 CF2_Fixed xOffset1, yOffset1, xOffset3, yOffset3;
1839 FT_Vector P0, P1, P2, P3;
1840
1841
1842 /* TODO: ignore zero length portions of curve?? */
1843 cf2_glyphpath_computeOffset( glyphpath,
1844 glyphpath->currentCS.x,
1845 glyphpath->currentCS.y,
1846 x1,
1847 y1,
1848 &xOffset1,
1849 &yOffset1 );
1850 cf2_glyphpath_computeOffset( glyphpath,
1851 x2,
1852 y2,
1853 x3,
1854 y3,
1855 &xOffset3,
1856 &yOffset3 );
1857
1858 /* add momentum from the middle segment */
1859 glyphpath->callbacks->windingMomentum =
1860 ADD_INT32( glyphpath->callbacks->windingMomentum,
1861 cf2_getWindingMomentum( x1, y1, x2, y2 ) );
1862
1863 /* construct offset points */
1864 P0.x = ADD_INT32( glyphpath->currentCS.x, xOffset1 );
1865 P0.y = ADD_INT32( glyphpath->currentCS.y, yOffset1 );
1866 P1.x = ADD_INT32( x1, xOffset1 );
1867 P1.y = ADD_INT32( y1, yOffset1 );
1868 /* note: preserve angle of final segment by using offset3 at both ends */
1869 P2.x = ADD_INT32( x2, xOffset3 );
1870 P2.y = ADD_INT32( y2, yOffset3 );
1871 P3.x = ADD_INT32( x3, xOffset3 );
1872 P3.y = ADD_INT32( y3, yOffset3 );
1873
1874 if ( glyphpath->moveIsPending )
1875 {
1876 /* emit offset 1st point as MoveTo */
1877 cf2_glyphpath_pushMove( glyphpath, P0 );
1878
1879 glyphpath->moveIsPending = FALSE;
1880 glyphpath->pathIsOpen = TRUE;
1881
1882 glyphpath->offsetStart1 = P1; /* record second point */
1883 }
1884
1885 if ( glyphpath->elemIsQueued )
1886 {
1887 FT_ASSERT( cf2_hintmap_isValid( &glyphpath->hintMap ) ||
1888 glyphpath->hintMap.count == 0 );
1889
1890 cf2_glyphpath_pushPrevElem( glyphpath,
1891 &glyphpath->hintMap,
1892 &P0,
1893 P1,
1894 FALSE );
1895 }
1896
1897 /* queue the current element with offset points */
1898 glyphpath->elemIsQueued = TRUE;
1899 glyphpath->prevElemOp = CF2_PathOpCubeTo;
1900 glyphpath->prevElemP0 = P0;
1901 glyphpath->prevElemP1 = P1;
1902 glyphpath->prevElemP2 = P2;
1903 glyphpath->prevElemP3 = P3;
1904
1905 /* update current map */
1906 if ( cf2_hintmask_isNew( glyphpath->hintMask ) )
1907 cf2_hintmap_build( &glyphpath->hintMap,
1908 glyphpath->hStemHintArray,
1909 glyphpath->vStemHintArray,
1910 glyphpath->hintMask,
1911 glyphpath->hintOriginY,
1912 FALSE );
1913
1914 glyphpath->currentCS.x = x3; /* pre-offset current point */
1915 glyphpath->currentCS.y = y3;
1916 }
1917
1918
1919 FT_LOCAL_DEF( void )
1920 cf2_glyphpath_closeOpenPath( CF2_GlyphPath glyphpath )
1921 {
1922 if ( glyphpath->pathIsOpen )
1923 {
1924 /*
1925 * A closing line in Character Space line is always generated below
1926 * with `cf2_glyphPath_lineTo'. It may be ignored later if it turns
1927 * out to be zero length in Device Space.
1928 */
1929 glyphpath->pathIsClosing = TRUE;
1930
1931 cf2_glyphpath_lineTo( glyphpath,
1932 glyphpath->start.x,
1933 glyphpath->start.y );
1934
1935 /* empty the final element from the queue and close the path */
1936 if ( glyphpath->elemIsQueued )
1937 cf2_glyphpath_pushPrevElem( glyphpath,
1938 &glyphpath->hintMap,
1939 &glyphpath->offsetStart0,
1940 glyphpath->offsetStart1,
1941 TRUE );
1942
1943 /* reset state machine */
1944 glyphpath->moveIsPending = TRUE;
1945 glyphpath->pathIsOpen = FALSE;
1946 glyphpath->pathIsClosing = FALSE;
1947 glyphpath->elemIsQueued = FALSE;
1948 }
1949 }
1950
1951
1952 /* END */