1 /* $XConsortium: hints.c,v 1.4 91/10/10 11:18:13 rws Exp $ */
2 /* Copyright International Business Machines, Corp. 1991
3 * All Rights Reserved
4 * Copyright Lexmark International, Inc. 1991
5 * All Rights Reserved
6 *
7 * License to use, copy, modify, and distribute this software and its
8 * documentation for any purpose and without fee is hereby granted,
9 * provided that the above copyright notice appear in all copies and that
10 * both that copyright notice and this permission notice appear in
11 * supporting documentation, and that the name of IBM or Lexmark not be
12 * used in advertising or publicity pertaining to distribution of the
13 * software without specific, written prior permission.
14 *
15 * IBM AND LEXMARK PROVIDE THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES OF
16 * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO ANY
17 * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
18 * AND NONINFRINGEMENT OF THIRD PARTY RIGHTS. THE ENTIRE RISK AS TO THE
19 * QUALITY AND PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT
20 * OR MAINTAIN, BELONGS TO THE LICENSEE. SHOULD ANY PORTION OF THE
21 * SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM OR LEXMARK) ASSUMES THE
22 * ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION. IN NO EVENT SHALL
23 * IBM OR LEXMARK BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
24 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
25 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
26 * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
27 * THIS SOFTWARE.
28 */
29 /* HINTS CWEB V0006 ******** */
30 /*
31 :h1.HINTS Module - Processing Rasterization Hints
32
33 &author. Sten F. Andler; continuity by Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com) and Duaine
34 W. Pryor, Jr.
35
36
37 :h3.Include Files
38
39 The included files are:
40 */
41
42 #include <stdio.h>
43
44 #include "types.h"
45 #include "objects.h"
46 #include "spaces.h"
47 #include "paths.h"
48 #include "regions.h"
49 #include "hints.h"
50
51 /*
52 :h3.Functions Provided to the TYPE1IMAGER User
53
54 None.
55 */
56
57 /*
58 :h3.Functions Provided to Other Modules
59
60 This module provides the following entry point to other modules:
61 */
62
63
64 /*SHARED LINE(S) ORIGINATED HERE*/
65
66 /*
67 :h3.Macros Provided to Other Modules
68
69 None.
70 */
71
72 /*
73 :h2.InitHints() - Initialize hint data structure
74 */
75
76 #define MAXLABEL 20
77 static struct {
78 int inuse;
79 int computed;
80 struct fractpoint hint;
81 } oldHint[MAXLABEL];
82
83 #define ODD(x) (((int)(x)) & 01)
84 #define FPFLOOR(fp) TOFRACTPEL((fp) >> FRACTBITS)
85 #define FPROUND(fp) FPFLOOR((fp) + FPHALF)
86
InitHints()87 void InitHints()
88 {
89 int i;
90
91 for (i = 0; i < MAXLABEL; i++)
92 {
93 oldHint[i].inuse = FALSE;
94 oldHint[i].computed = FALSE;
95 }
96 }
97
98 /*
99 :h3.CloseHints(hintP) - Reverse hints that are still open
100 */
101
CloseHints(hintP)102 void CloseHints(hintP)
103 struct fractpoint *hintP;
104 {
105 int i;
106
107 for (i = 0; i < MAXLABEL; i++)
108 {
109 if (oldHint[i].inuse)
110 {
111 hintP->x -= oldHint[i].hint.x;
112 hintP->y -= oldHint[i].hint.y;
113
114 oldHint[i].inuse = FALSE;
115
116 IfTrace3((HintDebug > 1)," Hint %d was open, hint=(%d,%d)\n",
117 i, hintP->x, hintP->y);
118 }
119 }
120 }
121
122 /*
123 :h3.ComputeHint(hP, currX, currY, hintP) - Compute the value of a hint
124 */
125
ComputeHint(hP,currX,currY,hintP)126 static void ComputeHint(hP, currX, currY, hintP)
127 struct hintsegment *hP;
128 fractpel currX, currY;
129 struct fractpoint *hintP;
130 {
131 fractpel currRef=0, currWidth=0;
132 int idealWidth;
133 fractpel hintValue=0;
134 char orientation;
135
136 /*
137 By construction, width is never zero. Therefore we can use the
138 width value to determine if the hint has been rotated by a
139 multiple of 90 degrees.
140 */
141
142 if (hP->width.y == 0)
143 {
144 orientation = 'v'; /* vertical */
145 IfTrace0((HintDebug > 0)," vertical hint\n");
146 }
147 else if (hP->width.x == 0)
148 {
149 orientation = 'h'; /* horizontal */
150 IfTrace0((HintDebug > 0)," horizontal hint\n");
151 }
152 else
153 {
154 IfTrace0((HintDebug > 0)," hint not vertical or horizontal\n");
155 hintP->x = hintP->y = 0;
156 return;
157 }
158
159 /* Compute currRef and currWidth with a unit of 1 pel */
160 if (orientation == 'v') /* vertical */
161 {
162 currRef = hP->ref.x + currX;
163 currWidth = TYPE1_ABS(hP->width.x);
164 }
165 else if (orientation == 'h') /* horizontal */
166 {
167 currRef = hP->ref.y + currY;
168 currWidth = TYPE1_ABS(hP->width.y);
169 }
170 else /* error */
171 {
172 abort("ComputeHint: invalid orientation", 4);
173 }
174
175 IfTrace4((HintDebug > 1),
176 " currX=%d, currY=%d, currRef=%d, currWidth=%d\n",
177 currX, currY,
178 currRef, currWidth);
179
180 if ((hP->hinttype == 'b') /* Bar or stem */
181 || (hP->hinttype == 's')) /* Serif */
182 {
183 idealWidth = NEARESTPEL(currWidth);
184 if (idealWidth == 0) idealWidth = 1;
185 if (ODD(idealWidth)) /* Is ideal width odd? */
186 {
187 /* center "ref" over pel */
188 hintValue = FPFLOOR(currRef) + FPHALF - currRef;
189 }
190 else
191 {
192 /* align "ref" on pel boundary */
193 hintValue = FPROUND(currRef) - currRef;
194 }
195 if (HintDebug > 2) {
196 IfTrace1(TRUE," idealWidth=%d, ", idealWidth);
197 }
198 }
199 else if (hP->hinttype == 'c') /* Curve extrema */
200 {
201 /* align "ref" on pel boundary */
202 hintValue = FPROUND(currRef) - currRef;
203 }
204 else /* error */
205 {
206 abort("ComputeHint: invalid hinttype", 5);
207 }
208
209 IfTrace1((HintDebug > 1)," hintValue=%d", hintValue);
210
211 if (orientation == 'v') /* vertical */
212 {
213 hintP->x = hintValue;
214 hintP->y = 0;
215 }
216 else if (orientation == 'h') /* horizontal */
217 {
218 hintP->x = 0;
219 hintP->y = hintValue;
220 }
221 else /* error */
222 {
223 abort("ComputeHint: invalid orientation", 6);
224 }
225 }
226
227 /*
228 :h3.ProcessHint(hP, currX, currY, hintP) - Process a rasterization hint
229 */
230
ProcessHint(hP,currX,currY,hintP)231 void ProcessHint(hP, currX, currY, hintP)
232 struct hintsegment *hP;
233 fractpel currX, currY;
234 struct fractpoint *hintP;
235 {
236 struct fractpoint thisHint;
237
238 IfTrace4((HintDebug > 1)," ref=(%d,%d), width=(%d,%d)",
239 hP->ref.x, hP->ref.y,
240 hP->width.x, hP->width.y);
241 IfTrace4((HintDebug > 1),", %c %c %c %c",
242 hP->orientation, hP->hinttype,
243 hP->adjusttype, hP->direction);
244 IfTrace1((HintDebug > 1),", label=%d\n", hP->label);
245
246 if ((hP->adjusttype == 'm') /* Move */
247 || (hP->adjusttype == 'a')) /* Adjust */
248 {
249 /* Look up hint in oldHint table */
250 if ((hP->label >= 0) && (hP->label < MAXLABEL))
251 {
252 if (oldHint[hP->label].computed)
253 /* Use old hint value if already computed */
254 {
255 thisHint.x = oldHint[hP->label].hint.x;
256 thisHint.y = oldHint[hP->label].hint.y;
257 oldHint[hP->label].inuse = TRUE;
258 }
259 else
260 /* Compute new value for hint and store it for future use */
261 {
262 ComputeHint(hP, currX, currY, &thisHint);
263
264 oldHint[hP->label].hint.x = thisHint.x;
265 oldHint[hP->label].hint.y = thisHint.y;
266 oldHint[hP->label].inuse = TRUE;
267 oldHint[hP->label].computed = TRUE;
268 }
269 }
270 else /* error */
271 {
272 abort("ProcessHint: invalid label", 7);
273 }
274 }
275 else if (hP->adjusttype == 'r') /* Reverse */
276 {
277 /* Use the inverse of the existing hint value to reverse hint */
278 if ((hP->label >= 0) && (hP->label < MAXLABEL))
279 {
280 if (oldHint[hP->label].inuse)
281 {
282 thisHint.x = -oldHint[hP->label].hint.x;
283 thisHint.y = -oldHint[hP->label].hint.y;
284 oldHint[hP->label].inuse = FALSE;
285 }
286 else /* error */
287 {
288 abort("ProcessHint: label is not in use", 8);
289 }
290 }
291 else /* error */
292 {
293 abort("ProcessHint: invalid label", 9);
294 }
295
296 }
297 else /* error */
298 {
299 abort("ProcessHint: invalid adjusttype", 10);
300 }
301 IfTrace3((HintDebug > 1)," label=%d, thisHint=(%d,%d)\n",
302 hP->label, thisHint.x, thisHint.y);
303
304 hintP->x += thisHint.x;
305 hintP->y += thisHint.y;
306
307 IfTrace2((HintDebug > 1)," hint=(%d,%d)\n",
308 hintP->x, hintP->y);
309 }
310
311 /*
312 :h2 id=subpath.Navigation Through Edge Lists
313
314 For continuity checking purposes, we need to navigate through edge
315 lists by the "subpath" chains and answer questions about edges. The
316 subpath chain links together edges that were part of the same subpath
317 (no intervening move segments) when the interior of the path was
318 calculated. Here we use the term "edge" to mean every edge list
319 that was created in between changes of direction.
320
321 The subpath chains are singly-linked circular chains. For the convenience
322 of building them, they direction of the list (from edge to edge) is the
323 reverse of the order in which they were built. Within any single edge,
324 the subpath chain goes from top-to-bottom. (There might be a violation
325 of this because of the way the user started the first chain; see
326 :hdref refid=fixsubp..).
327
328 :h3.ISTOP() and ISBOTTOM() - Flag Bits for Edge Lists at the Top and
329 Bottom of Their SubPaths
330 */
331
332 #define ISTOP(flag) ((flag)&0x20)
333 #define ISBOTTOM(flag) ((flag)&0x10)
334 /*
335 :h3.ISLEFT() - Flag Bit for Left Edges
336 */
337
338 #define ISLEFT(flag) ((flag)&0x08)
339
340 /*
341 :h3.XofY() - Macro to Find X Value at Given Y
342
343 This macro can only be used if it is known that the Y is within the
344 given edgelist's ymin and ymax.
345 */
346
347 #define XofY(edge, y) edge->xvalues[y - edge->ymin]
348
349 /*
350 :h3.findXofY() - Like XofY(), Except not Restricted
351
352 If the Y is out of bounds of the given edgelist, this macro will
353 call SearchXofY to search the edge's subpath chain for the correct
354 Y range. If the Y value is off the edge, MINPEL is returned.
355 */
356 #define findXofY(edge, y) ((y < edge->ymin || y >= edge->ymax) ? SearchXofY(edge, y) : XofY(edge, y))
357
358 /*
359 :h4.SearchXofY() - Routine Called by FindXofY() for Difficult Cases
360
361 The concept of this routine is to follow the subpath chain to find the
362 edge just below (i.e., next in chain) or just above (i.e., immediately
363 before in chain. It is assumed that the Y value is no more than one
364 off of the edge's range; XofY() could be replace by FindXofY() to
365 call ourselves recursively if this were not true.
366 */
367
SearchXofY(edge,y)368 static pel SearchXofY(edge, y)
369 register struct edgelist *edge; /* represents edge */
370 register pel y; /* 'y' value to find edge for */
371 {
372 register struct edgelist *e; /* loop variable */
373
374 if (y < edge->ymin) {
375 if (ISTOP(edge->flag)) {
376 return(MINPEL);
377 }
378
379 for (e = edge->subpath; e->subpath != edge; e = e->subpath) { ; }
380 if (e->ymax == edge->ymin) {
381 return(XofY(e, y));
382 }
383 }
384 else if (y >= edge->ymax) {
385 if (ISBOTTOM(edge->flag)) {
386 return(MINPEL);
387 }
388 e = edge->subpath;
389 if (e->ymin == edge->ymax) {
390 return(XofY(e, y));
391 }
392 }
393 else {
394 return(XofY(edge, y));
395 }
396
397
398 abort("bad subpath chain", 11);
399 /*NOTREACHED*/
400 /* To make ANSI-C-compiler happy: */
401 return(y);
402
403 }
404 /*
405 :h3.ISBREAK() Macro - Tests if an Edge List is at a "Break"
406
407 The subpath chains are organized top to bottom. When the bottom of
408 a given edge is reached, the subpath chain points to the top of the
409 next edge. We call this a "break" in the chain. The following macro
410 is the simple test for the break condition:
411 */
412
413 #define ISBREAK(top,bot) (top->ymax != bot->ymin)
414
415
416 /*
417 :h3.ImpliedHorizontalLine() - Tests for Horizontal Connectivity
418
419 This function returns true if two edges are connected horizontally.
420 They are connected horizontally if they are consecutive in the subpath,
421 and either we are at the bottom and the first edge is going down or we
422 are at the top and the first edge is going up.
423 */
424
425 #define BLACKABOVE -1
426 #define BLACKBELOW +1
427 #define NONE 0
428
ImpliedHorizontalLine(e1,e2,y)429 static int ImpliedHorizontalLine(e1, e2, y)
430 register struct edgelist *e1,*e2; /* two edges to check */
431 register int y; /* y where they might be connected */
432 {
433 register struct edgelist *e3,*e4;
434
435 if (ISDOWN(e1->flag) == ISDOWN(e2->flag))
436 return(NONE); /* can't be consecutive unless different directions */
437 /*
438 Now we check for consecutiveness: Can we get from 'e1' to 'e2' with
439 only one intervening break? Can we get from 'e2' to 'e1' with only one
440 intervening break? 'e3' will be as far as we can get after 'e1'; 'e4'
441 will be has far as we can get after 'e2':
442 */
443 for (e3 = e1; !ISBREAK(e3, e3->subpath); e3 = e3->subpath) { ; }
444 for (e3 = e3->subpath; e3 != e2; e3 = e3->subpath)
445 if (ISBREAK(e3, e3->subpath))
446 break;
447
448 for (e4 = e2; !ISBREAK(e4, e4->subpath); e4 = e4->subpath) { ; }
449 for (e4 = e4->subpath; e4 != e1; e4 = e4->subpath)
450 if (ISBREAK(e4, e4->subpath))
451 break;
452 /*
453 If the edges are mutually consecutive, we must have horizontal lines
454 both top and bottom:
455 */
456 if (e3 == e2 && e4 == e1)
457 return(TRUE);
458 /*
459 If the edges are not consecutive either way, no horizontal lines are
460 possible:
461 */
462 if (e3 != e2 && e4 != e1)
463 return(NONE);
464 /*
465 Now let's swap 'e1' and 'e2' if necessary to enforce the rule that 'e2'
466 follows 'e1'. Remember that subpath chains go in the opposite direction
467 from the way the subpaths were built; this led to the simplest way
468 do build them.
469 */
470 if (e4 != e1) {
471 e2 = e1;
472 e1 = e3; /* remember e3 == e2, this just swaps 'e1' and 'e2' */
473 }
474 /*
475 Now we have everything to return the answer:
476 */
477 if (ISTOP(e1->flag) && y == e1->ymin)
478 return(ISDOWN(e2->flag));
479 else if (ISBOTTOM(e1->flag) && y == e1->ymax)
480 return(!ISDOWN(e2->flag));
481 else
482 abort("ImpliedHorizontalLine: why ask?", 12);
483 /*NOTREACHED*/
484 /* To make ANSI-C-compiler happy */
485 return(0);
486
487 }
488
489 /*
490 :h3 id=fixsubp.FixSubPaths() - Must be Called to Organize Subpath Chains
491
492 The region-building code in Interior(), in particular splitedge(),
493 maintains the rule that sub-paths are linked top-to-bottom except
494 at breaks. However, it is possible that there may be a "false break"
495 because the user started the subpath in the middle of an edge (and
496 went in the "wrong" direction from there, up instead of down). This
497 routine finds and fixes false breaks.
498
499 Also, this routine sets the ISTOP and ISBOTTOM flags in the edge lists.
500 */
501
FixSubPaths(R)502 static void FixSubPaths(R)
503 register struct region *R; /* anchor of region */
504 {
505 register struct edgelist *e; /* fast loop variable */
506 register struct edgelist *edge; /* current edge in region */
507 register struct edgelist *next; /* next in subpath after 'edge' */
508 register struct edgelist *break1; /* first break after 'next' */
509 register struct edgelist *break2=NULL; /* last break before 'edge' */
510 register struct edgelist *prev; /* previous edge for fixing links */
511 int left = TRUE;
512
513 for (edge = R->anchor; edge != NULL; edge = edge->link) {
514
515 if (left)
516 edge->flag |= ISLEFT(ON);
517 left = !left;
518
519 next = edge->subpath;
520
521 if (!ISBREAK(edge, next))
522 continue;
523 if (edge->ymax < next->ymin)
524 abort("disjoint subpath?", 13);
525 /*
526 'edge' now contains an edgelist at the bottom of an edge, and 'next'
527 contains the next subsequent edgelist in the subpath, which must be at
528 the top. We refer to this a "break" in the subpath.
529 */
530 next->flag |= ISTOP(ON);
531 edge->flag |= ISBOTTOM(ON);
532
533 if (ISDOWN(edge->flag) != ISDOWN(next->flag))
534 continue;
535 /*
536 We are now in the unusual case; both edges are going in the same
537 direction so this must be a "false break" due to the way that the user
538 created the path. We'll have to fix it.
539 */
540 for (break1 = next; !ISBREAK(break1, break1->subpath); break1 = break1->subpath) { ; }
541
542 for (e = break1->subpath; e != edge; e = e->subpath)
543 if (ISBREAK(e, e->subpath))
544 break2 = e;
545 /*
546 Now we've set up 'break1' and 'break2'. I've found the following
547 diagram invaluable. 'break1' is the first break after 'next'. 'break2'
548 is the LAST break before 'edge'.
549 &drawing.
550 next
551 +------+ +---->+------+
552 +--->| >-----+ | | >-----+
553 | | | | | | | |
554 | +-------------+ | +-------------+
555 | | |break1| | | | |
556 | +->| >-------+ +->| >-----+
557 | | | | | |
558 | | | +-------------+
559 | +------+ | | |
560 | +----------------+ | | |
561 | | +------+ | +->| >-----+
562 | +->| >-----+ | | | |
563 | | | | | +-------------+
564 | +-------------+ | | | |
565 | | |edge | | | |break2|
566 | +->| >-----+ | +->| >-----+
567 | | | | | | | |
568 | | | | | | | |
569 | | | | | | | |
570 | +------+ | | +------+ |
571 | | | |
572 +---------------+ +---------------+
573
574 &edrawing.
575 We want to fix this situation by having 'edge' point to where 'break1'
576 now points, and having 'break1' point to where 'break2' now points.
577 Finally, 'break2' should point to 'next'. Also, we observe that
578 'break1' can't be a bottom, and is also not a top unless it is the same
579 as 'next':
580 */
581 edge->subpath = break1->subpath;
582
583 break1->subpath = break2->subpath;
584 if (ISBREAK(break1, break1->subpath))
585 abort("unable to fix subpath break?", 14);
586
587 break2->subpath = next;
588
589 break1->flag &= ~ISBOTTOM(ON);
590 if (break1 != next)
591 break1->flag &= ~ISTOP(ON);
592 }
593
594 /*
595 This region might contain "ambiguous" edges; edges exactly equal to
596 edge->link. Due to the random dynamics of where they get sorted into
597 the list, they can yield false crossings, where the edges appear
598 to cross. This confuses our continuity logic no end. Since we can
599 swap them without changing the region, we do.
600 */
601 for (edge = R->anchor, prev = NULL; VALIDEDGE(edge); prev = edge, edge = prev->link) {
602
603 if (! ISAMBIGUOUS(edge->flag)) {
604 continue;
605 }
606
607 next = edge->subpath;
608
609 while (ISAMBIGUOUS(next->flag) && next != edge) {
610 next = next->subpath;
611 }
612
613 /*
614 We've finally found a non-ambiguous edge; we make sure it is left/right
615 compatible with 'edge':
616 */
617 if ( (ISLEFT(edge->flag) == ISLEFT(next->flag) && ISDOWN(edge->flag) == ISDOWN(next->flag) )
618 || (ISLEFT(edge->flag) != ISLEFT(next->flag) && ISDOWN(edge->flag) != ISDOWN(next->flag) ) ) {
619 continue;
620 }
621
622 /*
623 Incompatible, we will swap 'edge' and the following edge in the list.
624 You may think that there must be a next edge in this swath. So did I.
625 No! If there is a totally ambiguous inner loop, for example, we could
626 get all the way to the outside without resolving ambiguity.
627 */
628 next = edge->link; /* note new meaning of 'next' */
629 if (next == NULL || edge->ymin != next->ymin) {
630 continue;
631 }
632
633 /*
634 printf(" Swap: \n");
635 printf(" Edge=0x%x, ymin=%d, ymax=%d, xmin=%d, xmax=%d, fpx1=%ld, fpx2=%ld\n",
636 edge, edge->ymin, edge->ymax, edge->xmin, edge->xmax, edge->fpx1, edge->fpx2);
637 printf(" Link=0x%x, ymin=%d, ymax=%d, xmin=%d, xmax=%d, fpx1=%ld, fpx2=%ld\n",
638 next, next->ymin, next->ymax, next->xmin, next->xmax, next->fpx1, next->fpx2);
639 printf(" Edge=0x%x (amb=%d), x[ymin]=%d, x[ymax]=%d, px1=%ld, px2=%ld\n",
640 edge, ISAMBIGUOUS(edge->flag), edge->xvalues[0], edge->xvalues[edge->ymax - edge->ymin],
641 edge->fpx1>>FRACTBITS, edge->fpx2>>FRACTBITS);
642 printf(" Link=0x%x (amb=%d), x[ymin]=%d, x[ymax]=%d, px1=%ld, px2=%ld\n",
643 next, ISAMBIGUOUS(next->flag), next->xvalues[0], next->xvalues[next->ymax - next->ymin],
644 next->fpx1>>FRACTBITS, next->fpx2>>FRACTBITS);
645 */
646
647 /* Check ambiguity also for link edge (RMz) */
648 if ( !ISAMBIGUOUS(next->flag) ) {
649 continue;
650 }
651
652
653 if (prev == NULL)
654 R->anchor = next;
655 else
656 prev->link = next;
657 edge->link = next->link;
658 next->link = edge;
659 edge->flag ^= ISLEFT(ON);
660 edge->flag &= ~ISAMBIGUOUS(ON);
661 next->flag ^= ISLEFT(ON);
662 next->flag &= ~ISAMBIGUOUS(ON);
663 edge = next;
664 }
665 }
666 /*
667 :h3.DumpSubPaths()
668
669 A debug tool.
670 */
671
672 static struct edgelist *before(); /* subroutine of DumpSubPaths */
673
DumpSubPaths(anchor)674 static void DumpSubPaths(anchor)
675 struct edgelist *anchor;
676 {
677
678 register struct edgelist *edge,*e,*e2;
679 pel y;
680
681 for (edge = anchor; VALIDEDGE(edge); edge = edge->link) {
682 if (ISPERMANENT(edge->flag))
683 continue;
684 IfTrace0(TRUE, "BEGIN Subpath\n");
685 for (e2 = edge; !ISPERMANENT(e2->flag);) {
686 if (ISDOWN(e2->flag)) {
687 IfTrace1(TRUE, ". Downgoing edge's top at %p\n", e2);
688 for (e = e2;; e = e->subpath) {
689 IfTrace4(TRUE, ". . [%5d] %5d @ %p[%x]\n",
690 e->ymin, *e->xvalues, e, e->flag);
691 for (y=e->ymin+1; y < e->ymax; y++)
692 IfTrace2(TRUE, ". . [%5d] %5d \"\n", y, e->xvalues[y-e->ymin]);
693 e->flag |= ISPERMANENT(ON);
694 if (ISBREAK(e, e->subpath))
695 break;
696 }
697 }
698 else {
699 IfTrace1(TRUE, ". Upgoing edge's top at %p\n", e2);
700 for (e = e2; !ISBREAK(e, e->subpath); e = e->subpath) { ; }
701 for (;; e=before(e)) {
702 IfTrace4(TRUE, ". . [%5d] %5d @ %p[%x]\n",
703 e->ymax-1, e->xvalues[e->ymax-1-e->ymin], e, e->flag);
704 for (y=e->ymax-2; y >= e->ymin; y--)
705 IfTrace2(TRUE, ". . [%5d] %5d \"\n", y, e->xvalues[y-e->ymin]);
706 e->flag |= ISPERMANENT(ON);
707 if (e == e2)
708 break;
709 }
710 }
711 do {
712 e2 = before(e2);
713 } while (!ISBREAK(before(e2), e2));
714 }
715 }
716 }
717
before(e)718 static struct edgelist *before(e)
719 struct edgelist *e;
720 {
721 struct edgelist *r;
722 for (r = e->subpath; r->subpath != e; r = r->subpath) { ; }
723 return(r);
724 }
725
726 /*
727 :h2.Fixing Region Continuity Problems
728
729 Small regions may become disconnected when their connecting segments are
730 less than a pel wide. This may be correct in some applications, but in
731 many (especially small font characters), it is more pleasing to keep
732 connectivity. ApplyContinuity() (invoked by +CONTINUITY on the
733 Interior() fill rule) fixes connection breaks. The resulting region
734 is geometrically less accurate, but may be more pleasing to the eye.
735 */
736 /*
737 Here are some macros which we will need:
738 */
739
740 #define IsValidPel(j) (j!=MINPEL)
741
742 /*
743 :h3.writeXofY() - Stuffs an X Value Into an "edgelist"
744
745 writeXofY writes an x value into an edge at position 'y'. It must
746 update the edge's xmin and xmax. If there is a possibility that this
747 new x might exceed the region's bounds, updating those are the
748 responsibility of the caller.
749 */
750
writeXofY(e,y,x)751 static void writeXofY(e, y, x)
752 struct edgelist *e; /* relevant edgelist */
753 int y; /* y value */
754 int x; /* new x value */
755 {
756 if (e->xmin > x) e->xmin = x;
757 if (e->xmax < x) e->xmax = x;
758 e->xvalues[y - e->ymin] = x;
759 }
760
761
762 /*-------------------------------------------------------------------------*/
763 /* the following three macros tell us whether we are at a birth point, a */
764 /* death point, or simply in the middle of the character */
765 /*-------------------------------------------------------------------------*/
766 #define WeAreAtTop(e,i) (ISTOP(e->flag) && e->ymin == i)
767 #define WeAreAtBottom(e,i) (ISBOTTOM(e->flag) && e->ymax-1 == i)
768 #define WeAreInMiddle(e,i) \
769 ((!ISTOP(e->flag) && !ISBOTTOM(e->flag))||(i < e->ymax-1 && i > e->ymin))
770 /*
771 The following macro tests if two "edgelist" structures are in the same
772 swath:
773 */
774 #define SAMESWATH(e1,e2) (e1->ymin == e2->ymin)
775
776 /*
777 :h3.CollapseWhiteRun() - Subroutine of ApplyContinuity()
778
779 When we have a white run with an implied horizontal line above or
780 below it, we better have black on the other side of this line. This
781 function both tests to see if black is there, and adjusts the end
782 points (collapses) the white run as necessary if it is not. The
783 goal is to collapse the white run as little as possible.
784 */
785
CollapseWhiteRun(anchor,yblack,left,right,ywhite)786 static void CollapseWhiteRun(anchor, yblack, left, right, ywhite)
787 struct edgelist *anchor; /* anchor of edge list */
788 pel yblack; /* y of (hopefully) black run above or below */
789 struct edgelist *left; /* edgelist at left of WHITE run */
790 struct edgelist *right; /* edgelist at right of WHITE run */
791 pel ywhite; /* y location of white run */
792 {
793 struct edgelist *edge;
794 struct edgelist *swathstart = anchor;
795 register pel x;
796
797 if (XofY(left, ywhite) >= XofY(right, ywhite))
798 return;
799 /*
800 Find the swath with 'yblack'. If we don't find it, completely collapse
801 the white run and return:
802 */
803 while (VALIDEDGE(swathstart)) {
804 if (yblack < swathstart->ymin) {
805 writeXofY(left, ywhite, XofY(right, ywhite));
806 return;
807 }
808 if (yblack < swathstart->ymax) break;
809 swathstart = swathstart->link->link;
810 }
811 if(!VALIDEDGE(swathstart)) {
812 writeXofY(left, ywhite, XofY(right, ywhite));
813 return;
814 }
815 /*
816 Now we are in the swath that contains 'y', the reference line above
817 or below that we are trying to maintain continuity with. If black
818 in this line begins in the middle of our white run, we must collapse
819 the white run from the left to that point. If black ends in the
820 middle of our white run, we must collapse the white run from the right
821 to that point.
822 */
823 for (edge = swathstart; VALIDEDGE(edge); edge = edge->link) {
824
825 if (!SAMESWATH(swathstart,edge))
826 break;
827 if( XofY(edge, yblack) > XofY(left, ywhite)) {
828 if (ISLEFT(edge->flag)) {
829 x = XofY(edge, yblack);
830 if (XofY(right, ywhite) < x)
831 x = XofY(right, ywhite);
832 writeXofY(left, ywhite, x);
833 }
834 else {
835 x = XofY(edge, yblack);
836 while (edge->link != NULL && SAMESWATH(edge, edge->link)
837 && x >= XofY(edge->link, yblack) ) {
838 edge = edge->link->link;
839 x = XofY(edge, yblack);
840 }
841 if (x < XofY(right, ywhite))
842 writeXofY(right, ywhite, x);
843 return;
844 }
845 }
846 }
847 writeXofY(left, ywhite, XofY(right, ywhite));
848 }
849
850 /*
851 :h3.ApplyContinuity() - Fix False Breaks in a Region
852
853 This is the externally visible routine called from the REGIONS module
854 when the +CONTINUITY flag is on the Interior() fill rule.
855 */
856
ApplyContinuity(R)857 void ApplyContinuity(R)
858 struct region *R;
859 {
860 struct edgelist *left;
861 struct edgelist *right;
862 struct edgelist *edge,*e2;
863 pel rightXabove,rightXbelow,leftXabove,leftXbelow;
864 pel leftX,rightX;
865 int i;
866 long edgecnt = 0;
867
868 fractpel xavrg = 0;
869 LONG newcenter,abovecenter,belowcenter;
870
871
872 FixSubPaths(R);
873 if ( RegionDebug >= 3)
874 DumpSubPaths(R->anchor);
875 left = R->anchor;
876
877 /* loop through and do all of the easy checking. ( no tops or bottoms) */
878 while(VALIDEDGE(left)) {
879 right = left->link;
880 for(i=left->ymin;i<left->ymax;++i) {
881 leftX = findXofY(left,i);
882 rightX = findXofY(right,i);
883 leftXbelow = findXofY(left,i+1);
884 rightXbelow = findXofY(right,i+1);
885 if(rightX <= leftX) {
886
887 /* then, we have a break in a near vertical line */
888 leftXabove = findXofY(left,i-1);
889 rightXabove = findXofY(right,i-1);
890 /* Check above current scanline */
891 if ( IsValidPel(leftXabove) && IsValidPel(rightXabove) ) {
892 abovecenter = leftXabove + rightXabove;
893 }
894 else {
895 /* We are at the top. We can assume that the current edge list is just started
896 --> Inspect the stored start fractpel values in order to decide about
897 to which side to extend. -->
898 Compute arithmetic average between left and right edge at high resolution */
899 xavrg = ((left->fpx1 + right->fpx1) >> 1);
900 /* round down to get left (not nearest!) and get right edge by adding one pel. */
901 leftXabove = (xavrg >> FRACTBITS);
902 rightXabove = leftXabove + 1;
903 abovecenter = leftXabove + rightXabove;
904 belowcenter = leftXabove + rightXabove;
905 }
906
907 /* Check below current scanline */
908 if ( IsValidPel(leftXbelow) && IsValidPel(rightXbelow) ) {
909 belowcenter = leftXbelow + rightXbelow;
910 }
911 else {
912 /* We are at the bottom. We can assume that the current edge list terminates here
913 --> Inspect the stored end fractpel values in order to decide about
914 to which side to extend. -->
915 Compute arithmetic average between left and right edge at high resolution */
916 xavrg = ((left->fpx2 + right->fpx2) >> 1);
917 /* round down to get left (not nearest!) and get right edge by adding one pel. */
918 leftXbelow = (xavrg >> FRACTBITS);
919 rightXbelow = leftXbelow + 1;
920 abovecenter = leftXbelow + rightXbelow;
921 belowcenter = leftXbelow + rightXbelow;
922 }
923
924 newcenter = abovecenter + belowcenter;
925
926 if( newcenter > 4*leftX ) {
927 rightX = rightX + 1;
928 writeXofY(right,i,rightX);
929 }
930 else if( newcenter < 4*leftX) {
931 leftX = leftX - 1;
932 writeXofY(left,i,leftX);
933 }
934 else {
935 rightX = rightX + 1;
936 writeXofY(right,i,rightX);
937 }
938
939 if ( rightX > R->xmax ) {
940 R->xmax = rightX;
941 }
942 if ( leftX < R->xmin ) {
943 R->xmin = leftX;
944 }
945 }
946 if( !WeAreAtBottom(left,i) && (leftXbelow>=rightX)) {
947 /* then we have a break in a near horizontal line in the middle */
948 writeXofY(right,i,leftXbelow);
949 }
950 if( !WeAreAtBottom(right,i) && (leftX >=rightXbelow)) {
951 /* then we have a break in a near horizontal line in the middle */
952 writeXofY(left,i,rightXbelow);
953 }
954 }
955 left = right->link;
956 ++edgecnt;
957 }
958
959 /*
960 There may be "implied horizontal lines" between edges that have
961 implications for continuity. This loop looks for white runs that
962 have implied horizontal lines on the top or bottom, and calls
963 CollapseWhiteRuns to check and fix any continuity problems from
964 them.
965 */
966 for (edge = R->anchor; VALIDEDGE(edge); edge = edge->link) {
967 if ((!ISTOP(edge->flag) && !ISBOTTOM(edge->flag)) || ISLEFT(edge->flag))
968 continue; /* at some future date we may want left edge logic here too */
969 for (e2 = edge->link; VALIDEDGE(e2) && SAMESWATH(edge,e2); e2 = e2->link) {
970 if (ISTOP(e2->flag) && ISTOP(edge->flag)
971 && NONE != ImpliedHorizontalLine(edge,e2,edge->ymin)) {
972 if (ISLEFT(e2->flag))
973 CollapseWhiteRun(R->anchor, edge->ymin-1,
974 edge, e2, edge->ymin);
975 }
976 if (ISBOTTOM(e2->flag) && ISBOTTOM(edge->flag)
977 && NONE != ImpliedHorizontalLine(edge,e2, edge->ymax)) {
978 if (ISLEFT(e2->flag))
979 CollapseWhiteRun(R->anchor, edge->ymax,
980 edge, e2, edge->ymax-1);
981 }
982 }
983 }
984 }
985