git.sesse.net Git - rdpsrv/blob - Xserver/lib/font/Type1/hints.c

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