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