Back to index

tetex-bin  3.0
hints.c
Go to the documentation of this file.
00001 /* $XConsortium: hints.c,v 1.4 91/10/10 11:18:13 rws Exp $ */
00002 /* Copyright International Business Machines, Corp. 1991
00003  * All Rights Reserved
00004  * Copyright Lexmark International, Inc. 1991
00005  * All Rights Reserved
00006  *
00007  * License to use, copy, modify, and distribute this software and its
00008  * documentation for any purpose and without fee is hereby granted,
00009  * provided that the above copyright notice appear in all copies and that
00010  * both that copyright notice and this permission notice appear in
00011  * supporting documentation, and that the name of IBM or Lexmark not be
00012  * used in advertising or publicity pertaining to distribution of the
00013  * software without specific, written prior permission.
00014  *
00015  * IBM AND LEXMARK PROVIDE THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES OF
00016  * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO ANY
00017  * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
00018  * AND NONINFRINGEMENT OF THIRD PARTY RIGHTS.  THE ENTIRE RISK AS TO THE
00019  * QUALITY AND PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT
00020  * OR MAINTAIN, BELONGS TO THE LICENSEE.  SHOULD ANY PORTION OF THE
00021  * SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM OR LEXMARK) ASSUMES THE
00022  * ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION.  IN NO EVENT SHALL
00023  * IBM OR LEXMARK BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
00024  * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
00025  * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
00026  * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
00027  * THIS SOFTWARE.
00028  */
00029  /* HINTS    CWEB         V0006 ********                             */
00030 /*
00031 :h1.HINTS Module - Processing Rasterization Hints
00032  
00033 &author. Sten F. Andler; continuity by Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com) and Duaine
00034 W. Pryor, Jr.
00035  
00036  
00037 :h3.Include Files
00038  
00039 The included files are:
00040 */
00041  
00042 #include "types.h"
00043 #include "objects.h"
00044 #include "spaces.h"
00045 #include "paths.h"
00046 #include "regions.h"
00047 #include "hints.h"
00048  
00049 /*
00050 :h3.Functions Provided to the TYPE1IMAGER User
00051  
00052 None.
00053 */
00054  
00055 /*
00056 :h3.Functions Provided to Other Modules
00057  
00058 This module provides the following entry point to other modules:
00059 */
00060  
00061  
00062 /*SHARED LINE(S) ORIGINATED HERE*/
00063  
00064 /*
00065 :h3.Macros Provided to Other Modules
00066  
00067 None.
00068 */
00069  
00070 /*
00071 :h2.InitHints() - Initialize hint data structure
00072 */
00073  
00074 #define MAXLABEL 20
00075 static struct {
00076   int inuse;
00077   int computed;
00078   struct fractpoint hint;
00079 } oldHint[MAXLABEL];
00080  
00081 #define ODD(x) (((int)(x)) & 01)
00082 #define FPFLOOR(fp) TOFRACTPEL((fp) >> FRACTBITS)
00083 #define FPROUND(fp) FPFLOOR((fp) + FPHALF)
00084  
00085 void InitHints()
00086 {
00087   int i;
00088  
00089   for (i = 0; i < MAXLABEL; i++)
00090     {
00091     oldHint[i].inuse    = FALSE;
00092     oldHint[i].computed = FALSE;
00093     }
00094 }
00095  
00096 /*
00097 :h3.CloseHints(hintP) - Reverse hints that are still open
00098 */
00099  
00100 void CloseHints(hintP)
00101   struct fractpoint *hintP;
00102 {
00103   int i;
00104  
00105   for (i = 0; i < MAXLABEL; i++)
00106     {
00107     if (oldHint[i].inuse)
00108       {
00109       hintP->x -= oldHint[i].hint.x;
00110       hintP->y -= oldHint[i].hint.y;
00111  
00112       oldHint[i].inuse = FALSE;
00113  
00114       IfTrace3((HintDebug > 1),"  Hint %d was open, hint=(%dl,%dl)\n",
00115                 i, hintP->x, hintP->y);
00116       }
00117     }
00118 }
00119  
00120 /*
00121 :h3.ComputeHint(hP, currX, currY, hintP) - Compute the value of a hint
00122 */
00123  
00124 static void ComputeHint(hP, currX, currY, hintP)
00125   struct hintsegment *hP;
00126   fractpel currX, currY;
00127   struct fractpoint *hintP;
00128 {
00129   fractpel currRef = 0, currWidth = 0;
00130   int idealWidth;
00131   fractpel hintValue = 0;
00132   char orientation;
00133  
00134 /*
00135 By construction, width is never zero.  Therefore we can use the
00136 width value to determine if the hint has been rotated by a
00137 multiple of 90 degrees.
00138 */
00139  
00140   if (hP->width.y == 0)
00141     {
00142     orientation = 'v';  /* vertical */
00143     IfTrace0((HintDebug > 0),"  vertical hint\n");
00144     }
00145   else if (hP->width.x == 0)
00146     {
00147     orientation = 'h';  /* horizontal */
00148     IfTrace0((HintDebug > 0),"  horizontal hint\n");
00149     }
00150   else
00151     {
00152     IfTrace0((HintDebug > 0),"  hint not vertical or horizontal\n");
00153     hintP->x = hintP->y = 0;
00154     return;
00155     }
00156  
00157   /* Compute currRef and currWidth with a unit of 1 pel */
00158   if (orientation == 'v')      /* vertical */
00159     {
00160     currRef = hP->ref.x + currX;
00161     currWidth = ABS(hP->width.x);
00162     }
00163   else if (orientation == 'h') /* horizontal */
00164     {
00165     currRef = hP->ref.y + currY;
00166     currWidth = ABS(hP->width.y);
00167     }
00168   else                             /* error */
00169     {
00170     t1_abort("ComputeHint: invalid orientation");
00171     }
00172  
00173   IfTrace4((HintDebug > 1),
00174     "  currX=%dl, currY=%dl, currRef=%dl, currWidth=%dl\n",
00175     currX, currY,
00176     currRef, currWidth);
00177  
00178   if ((hP->hinttype == 'b')      /* Bar or stem */
00179     || (hP->hinttype == 's'))    /* Serif */
00180     {
00181     idealWidth = NEARESTPEL(currWidth);
00182     if (idealWidth == 0) idealWidth = 1;
00183     if (ODD(idealWidth))         /* Is ideal width odd? */
00184       {
00185       /* center "ref" over pel */
00186       hintValue = FPFLOOR(currRef) + FPHALF - currRef;
00187       }
00188     else
00189       {
00190       /* align "ref" on pel boundary */
00191       hintValue = FPROUND(currRef) - currRef;
00192       }
00193     if (HintDebug > 2) {
00194           IfTrace1(TRUE,"  idealWidth=%d, ", idealWidth);
00195       }
00196     }
00197   else if (hP->hinttype == 'c')  /* Curve extrema */
00198     {
00199     /* align "ref" on pel boundary */
00200     hintValue = FPROUND(currRef) - currRef;
00201     }
00202   else                           /* error */
00203     {
00204     t1_abort("ComputeHint: invalid hinttype");
00205     }
00206  
00207   IfTrace1((HintDebug > 1),"  hintValue=%dl", hintValue);
00208  
00209   if (orientation == 'v')      /* vertical */
00210     {
00211     hintP->x = hintValue;
00212     hintP->y = 0;
00213     }
00214   else if (orientation == 'h') /* horizontal */
00215     {
00216     hintP->x = 0;
00217     hintP->y = hintValue;
00218     }
00219   else                             /* error */
00220     {
00221     t1_abort("ComputeHint: invalid orientation");
00222     }
00223 }
00224  
00225 /*
00226 :h3.ProcessHint(hP, currX, currY, hintP) - Process a rasterization hint
00227 */
00228  
00229 void ProcessHint(hP, currX, currY, hintP)
00230   struct hintsegment *hP;
00231   fractpel currX, currY;
00232   struct fractpoint *hintP;
00233 {
00234   struct fractpoint thisHint;
00235  
00236   IfTrace4((HintDebug > 1),"  ref=(%dl,%dl), width=(%dl,%dl)",
00237       hP->ref.x, hP->ref.y,
00238       hP->width.x, hP->width.y);
00239   IfTrace4((HintDebug > 1),", %c %c %c %c",
00240       hP->orientation, hP->hinttype,
00241       hP->adjusttype, hP->direction);
00242   IfTrace1((HintDebug > 1),", label=%d\n", hP->label);
00243  
00244   if ((hP->adjusttype == 'm')      /* Move */
00245     || (hP->adjusttype == 'a'))    /* Adjust */
00246     {
00247     /* Look up hint in oldHint table */
00248     if ((hP->label >= 0) && (hP->label < MAXLABEL))
00249       {
00250       if (oldHint[hP->label].computed)
00251         /* Use old hint value if already computed */
00252         {
00253         thisHint.x = oldHint[hP->label].hint.x;
00254         thisHint.y = oldHint[hP->label].hint.y;
00255         oldHint[hP->label].inuse    = TRUE;
00256         }
00257       else
00258         /* Compute new value for hint and store it for future use */
00259         {
00260         ComputeHint(hP, currX, currY, &thisHint);
00261  
00262         oldHint[hP->label].hint.x = thisHint.x;
00263         oldHint[hP->label].hint.y = thisHint.y;
00264         oldHint[hP->label].inuse    = TRUE;
00265         oldHint[hP->label].computed = TRUE;
00266         }
00267       }
00268     else                             /* error */
00269       {
00270       t1_abort("ProcessHint: invalid label");
00271       }
00272     }
00273   else if (hP->adjusttype == 'r')  /* Reverse */
00274     {
00275     /* Use the inverse of the existing hint value to reverse hint */
00276     if ((hP->label >= 0) && (hP->label < MAXLABEL))
00277       {
00278       if (oldHint[hP->label].inuse)
00279         {
00280         thisHint.x = -oldHint[hP->label].hint.x;
00281         thisHint.y = -oldHint[hP->label].hint.y;
00282         oldHint[hP->label].inuse = FALSE;
00283         }
00284       else                           /* error */
00285         {
00286         t1_abort("ProcessHint: label is not in use");
00287         }
00288       }
00289     else                           /* error */
00290       {
00291       t1_abort("ProcessHint: invalid label");
00292       }
00293  
00294     }
00295   else                           /* error */
00296     {
00297     t1_abort("ProcessHint: invalid adjusttype");
00298     }
00299   IfTrace3((HintDebug > 1),"  label=%d, thisHint=(%dl,%dl)\n",
00300     hP->label, thisHint.x, thisHint.y);
00301  
00302   hintP->x += thisHint.x;
00303   hintP->y += thisHint.y;
00304  
00305   IfTrace2((HintDebug > 1),"  hint=(%dl,%dl)\n",
00306     hintP->x, hintP->y);
00307 }
00308  
00309 /*
00310 :h2 id=subpath.Navigation Through Edge Lists
00311  
00312 For continuity checking purposes, we need to navigate through edge
00313 lists by the "subpath" chains and answer questions about edges.  The
00314 subpath chain links together edges that were part of the same subpath
00315 (no intervening move segments) when the interior of the path was
00316 calculated.  Here we use the term "edge" to mean every edge list
00317 that was created in between changes of direction.
00318  
00319 The subpath chains are singly-linked circular chains.  For the convenience
00320 of building them, they direction of the list (from edge to edge) is the
00321 reverse of the order in which they were built.  Within any single edge,
00322 the subpath chain goes from top-to-bottom.  (There might be a violation
00323 of this because of the way the user started the first chain; see
00324 :hdref refid=fixsubp..).
00325  
00326 :h3.ISTOP() and ISBOTTOM() - Flag Bits for Edge Lists at the Top and
00327 Bottom of Their SubPaths
00328 */
00329  
00330 #define   ISTOP(flag)     ((flag)&0x20)
00331 #define   ISBOTTOM(flag)  ((flag)&0x10)
00332 /*
00333 :h3.ISLEFT() - Flag Bit for Left Edges
00334 */
00335  
00336 #define   ISLEFT(flag)    ((flag)&0x08)
00337  
00338 /*
00339 :h3.XofY() - Macro to Find X Value at Given Y
00340  
00341 This macro can only be used if it is known that the Y is within the
00342 given edgelist's ymin and ymax.
00343 */
00344  
00345 #define   XofY(edge, y)   edge->xvalues[y - edge->ymin]
00346  
00347 /*
00348 :h3.findXofY() - Like XofY(), Except not Restricted
00349  
00350 If the Y is out of bounds of the given edgelist, this macro will
00351 call SearchXofY to search the edge's subpath chain for the correct
00352 Y range.  If the Y value is off the edge, MINPEL is returned.
00353 */
00354 #define   findXofY(edge, y)  ((y < edge->ymin || y >= edge->ymax) ? SearchXofY(edge, y) : XofY(edge, y))
00355  
00356 /*
00357 :h4.SearchXofY() - Routine Called by FindXofY() for Difficult Cases
00358  
00359 The concept of this routine is to follow the subpath chain to find the
00360 edge just below (i.e., next in chain) or just above (i.e., immediately
00361 before in chain.  It is assumed that the Y value is no more than one
00362 off of the edge's range; XofY() could be replace by FindXofY() to
00363 call ourselves recursively if this were not true.
00364 */
00365  
00366 static pel SearchXofY(edge, y)
00367        register struct edgelist *edge;  /* represents edge                   */
00368        register pel y;       /* 'y' value to find edge for                   */
00369 {
00370        register struct edgelist *e;  /* loop variable                        */
00371  
00372        if (y < edge->ymin) {
00373                if (ISTOP(edge->flag))
00374                        return(MINPEL);
00375                for (e = edge->subpath; e->subpath != edge; e = e->subpath) { ; }
00376                if (e->ymax == edge->ymin)
00377                         return(XofY(e, y));
00378        }
00379        else if (y >= edge->ymax) {
00380                if (ISBOTTOM(edge->flag))
00381                        return(MINPEL);
00382                e = edge->subpath;
00383                if (e->ymin == edge->ymax)
00384                          return(XofY(e, y));
00385        }
00386        else
00387                return(XofY(edge, y));
00388  
00389        t1_abort("bad subpath chain");
00390 
00391        /*NOTREACHED*/
00392        return MINPEL;
00393 }
00394 /*
00395 :h3.ISBREAK() Macro - Tests if an Edge List is at a "Break"
00396  
00397 The subpath chains are organized top to bottom.  When the bottom of
00398 a given edge is reached, the subpath chain points to the top of the
00399 next edge.  We call this a "break" in the chain.  The following macro
00400 is the simple test for the break condition:
00401 */
00402  
00403 #define  ISBREAK(top,bot) (top->ymax != bot->ymin)
00404  
00405  
00406 /*
00407 :h3.ImpliedHorizontalLine() - Tests for Horizontal Connectivity
00408  
00409 This function returns true if two edges are connected horizontally.
00410 They are connected horizontally if they are consecutive in the subpath,
00411 and either we are at the bottom and the first edge is going down or we
00412 are at the top and the first edge is going up.
00413 */
00414  
00415 #define  BLACKABOVE  -1
00416 #define  BLACKBELOW  +1
00417 #define  NONE         0
00418  
00419 static int ImpliedHorizontalLine(e1, e2, y)
00420        register struct edgelist *e1,*e2;  /* two edges to check              */
00421        register int y;       /* y where they might be connected              */
00422 {
00423        register struct edgelist *e3,*e4;
00424  
00425        if (ISDOWN(e1->flag) == ISDOWN(e2->flag))
00426                return(NONE);  /* can't be consecutive unless different directions */
00427 /*
00428 Now we check for consecutiveness:  Can we get from 'e1' to 'e2' with
00429 only one intervening break?  Can we get from 'e2' to 'e1' with only one
00430 intervening break?  'e3' will be as far as we can get after 'e1'; 'e4'
00431 will be has far as we can get after 'e2':
00432 */
00433        for (e3 = e1; !ISBREAK(e3, e3->subpath); e3 = e3->subpath) { ; }
00434        for (e3 = e3->subpath; e3 != e2; e3 = e3->subpath)
00435                if (ISBREAK(e3, e3->subpath))
00436                        break;
00437  
00438        for (e4 = e2; !ISBREAK(e4, e4->subpath); e4 = e4->subpath) { ; }
00439        for (e4 = e4->subpath; e4 != e1; e4 = e4->subpath)
00440                if (ISBREAK(e4, e4->subpath))
00441                        break;
00442 /*
00443 If the edges are mutually consecutive, we must have horizontal lines
00444 both top and bottom:
00445 */
00446        if (e3 == e2 && e4 == e1)
00447                return(TRUE);
00448 /*
00449 If the edges are not consecutive either way, no horizontal lines are
00450 possible:
00451 */
00452        if (e3 != e2 && e4 != e1)
00453                return(NONE);
00454 /*
00455 Now let's swap 'e1' and 'e2' if necessary to enforce the rule that 'e2'
00456 follows 'e1'.  Remember that subpath chains go in the opposite direction
00457 from the way the subpaths were built; this led to the simplest way
00458 do build them.
00459 */
00460        if (e4 != e1) {
00461                e2 = e1;
00462                e1 = e3;  /* remember e3 == e2, this just swaps 'e1' and 'e2' */
00463        }
00464 /*
00465 Now we have everything to return the answer:
00466 */
00467        if (ISTOP(e1->flag) && y == e1->ymin)
00468                return(ISDOWN(e2->flag));
00469        else if (ISBOTTOM(e1->flag) && y == e1->ymax)
00470                return(!ISDOWN(e2->flag));
00471        else
00472                t1_abort("ImpliedHorizontalLine:  why ask?");
00473        /*NOTREACHED*/
00474        return 0;
00475 }
00476  
00477 /*
00478 :h3 id=fixsubp.FixSubPaths() - Must be Called to Organize Subpath Chains
00479  
00480 The region-building code in Interior(), in particular splitedge(),
00481 maintains the rule that sub-paths are linked top-to-bottom except
00482 at breaks.  However, it is possible that there may be a "false break"
00483 because the user started the subpath in the middle of an edge (and
00484 went in the "wrong" direction from there, up instead of down).  This
00485 routine finds and fixes false breaks.
00486  
00487 Also, this routine sets the ISTOP and ISBOTTOM flags in the edge lists.
00488 */
00489  
00490 static void FixSubPaths(R)
00491        register struct region *R;       /* anchor of region                */
00492 {
00493        register struct edgelist *e;     /* fast loop variable                */
00494        register struct edgelist *edge;  /* current edge in region            */
00495        register struct edgelist *next;  /* next in subpath after 'edge'      */
00496        register struct edgelist *break1;  /* first break after 'next'        */
00497        register struct edgelist *break2 = NULL;  /* last break before 'edge'        */
00498        register struct edgelist *prev;    /* previous edge for fixing links  */
00499        int left = TRUE;
00500  
00501        for (edge = R->anchor; edge != NULL; edge = edge->link) {
00502  
00503                if (left)
00504                        edge->flag |= ISLEFT(ON);
00505                left = !left;
00506  
00507                next = edge->subpath;
00508  
00509                if (!ISBREAK(edge, next))
00510                        continue;
00511                if (edge->ymax < next->ymin)
00512                        t1_abort("disjoint subpath?");
00513 /*
00514 'edge' now contains an edgelist at the bottom of an edge, and 'next'
00515 contains the next subsequent edgelist in the subpath, which must be at
00516 the top.  We refer to this a "break" in the subpath.
00517 */
00518                next->flag |= ISTOP(ON);
00519                edge->flag |= ISBOTTOM(ON);
00520  
00521                if (ISDOWN(edge->flag) != ISDOWN(next->flag))
00522                        continue;
00523 /*
00524 We are now in the unusual case; both edges are going in the same
00525 direction so this must be a "false break" due to the way that the user
00526 created the path.  We'll have to fix it.
00527 */
00528                for (break1 = next; !ISBREAK(break1, break1->subpath); break1 = break1->subpath) { ; }
00529  
00530                for (e = break1->subpath; e != edge; e = e->subpath)
00531                        if (ISBREAK(e, e->subpath))
00532                                break2 = e;
00533 /*
00534 Now we've set up 'break1' and 'break2'.  I've found the following
00535 diagram invaluable.  'break1' is the first break after 'next'.  'break2'
00536 is the LAST break before 'edge'.
00537 &drawing.
00538          next
00539         +------+     +---->+------+
00540    +--->|    >-----+ |     |    >-----+
00541    |    |      |   | |     |      |   |
00542    | +-------------+ |  +-------------+
00543    | |  |break1|     |  |  |      |
00544    | +->|    >-------+  +->|    >-----+
00545    |    |      |           |      |   |
00546    |    |      |        +-------------+
00547    |    +------+        |  |      |
00548    | +----------------+ |  |      |
00549    | |  +------+      | +->|    >-----+
00550    | +->|    >-----+  |    |      |   |
00551    |    |      |   |  | +-------------+
00552    | +-------------+  | |  |      |
00553    | |  |edge  |      | |  |break2|
00554    | +->|    >-----+  | +->|    >-----+
00555    |    |      |   |  |    |      |   |
00556    |    |      |   |  |    |      |   |
00557    |    |      |   |  |    |      |   |
00558    |    +------+   |  |    +------+   |
00559    |               |  |               |
00560    +---------------+  +---------------+
00561  
00562 &edrawing.
00563 We want to fix this situation by having 'edge' point to where 'break1'
00564 now points, and having 'break1' point to where 'break2' now points.
00565 Finally, 'break2' should point to 'next'.  Also, we observe that
00566 'break1' can't be a bottom, and is also not a top unless it is the same
00567 as 'next':
00568 */
00569                edge->subpath = break1->subpath;
00570  
00571                break1->subpath = break2->subpath;
00572                if (ISBREAK(break1, break1->subpath))
00573                        t1_abort("unable to fix subpath break?");
00574  
00575                break2->subpath = next;
00576  
00577                break1->flag &= ~ISBOTTOM(ON);
00578                if (break1 != next)
00579                        break1->flag &= ~ISTOP(ON);
00580        }
00581 /*
00582 This region might contain "ambiguous" edges; edges exactly equal to
00583 edge->link.  Due to the random dynamics of where they get sorted into
00584 the list, they can yield false crossings, where the edges appear
00585 to cross.  This confuses our continuity logic no end.  Since we can
00586 swap them without changing the region, we do.
00587 */
00588        for (edge = R->anchor, prev = NULL; VALIDEDGE(edge); prev = edge, edge = prev->link) {
00589  
00590                if (! ISAMBIGUOUS(edge->flag))
00591                        continue;
00592  
00593                next = edge->subpath;
00594  
00595                while (ISAMBIGUOUS(next->flag) && next != edge)
00596                        next = next->subpath;
00597 /*
00598 We've finally found a non-ambiguous edge; we make sure it is left/right
00599 compatible with 'edge':
00600 */
00601                if ( (ISLEFT(edge->flag) == ISLEFT(next->flag) && ISDOWN(edge->flag) == ISDOWN(next->flag) )
00602                     || (ISLEFT(edge->flag) != ISLEFT(next->flag) && ISDOWN(edge->flag) != ISDOWN(next->flag) ) )
00603                        continue;
00604  
00605 /*
00606 Incompatible, we will swap 'edge' and the following edge in the list.
00607 You may think that there must be a next edge in this swath.  So did I.
00608 No!  If there is a totally ambiguous inner loop, for example, we could
00609 get all the way to the outside without resolving ambiguity.
00610 */
00611                next = edge->link;  /* note new meaning of 'next' */
00612                if (next == NULL || edge->ymin != next->ymin)
00613                        continue;
00614                if (prev == NULL)
00615                        R->anchor = next;
00616                else
00617                        prev->link = next;
00618                edge->link = next->link;
00619                next->link = edge;
00620                edge->flag ^= ISLEFT(ON);
00621                edge->flag &= ~ISAMBIGUOUS(ON);
00622                next->flag ^= ISLEFT(ON);
00623                next->flag &= ~ISAMBIGUOUS(ON);
00624                edge = next;
00625        }
00626 }
00627 /*
00628 :h3.DumpSubPaths()
00629  
00630 A debug tool.
00631 */
00632  
00633 static struct edgelist *before();  /* subroutine of DumpSubPaths             */
00634  
00635 static void DumpSubPaths(anchor)
00636        struct edgelist *anchor;
00637 {
00638  
00639        register struct edgelist *edge,*e,*e2;
00640        pel y;
00641  
00642        for (edge = anchor; VALIDEDGE(edge); edge = edge->link) {
00643                if (ISPERMANENT(edge->flag))
00644                        continue;
00645                IfTrace0(TRUE, "BEGIN Subpath\n");
00646                for (e2 = edge; !ISPERMANENT(e2->flag);) {
00647                        if (ISDOWN(e2->flag)) {
00648                                IfTrace1(TRUE, ". Downgoing edge's top at %p\n", e2);
00649                                for (e = e2;; e = e->subpath) {
00650                                        IfTrace4(TRUE, ". . [%5d] %5d    @ %p[%x]\n",
00651                                                 e->ymin, *e->xvalues, e, e->flag);
00652                                        for (y=e->ymin+1; y < e->ymax; y++)
00653                                                IfTrace2(TRUE, ". . [%5d] %5d     \"\n", y, e->xvalues[y-e->ymin]);
00654                                        e->flag |= ISPERMANENT(ON);
00655                                        if (ISBREAK(e, e->subpath))
00656                                                break;
00657                                }
00658                        }
00659                        else {
00660                                IfTrace1(TRUE, ". Upgoing edge's top at %p\n", e2);
00661                                for (e = e2; !ISBREAK(e, e->subpath); e = e->subpath) { ; }
00662                                for (;; e=before(e)) {
00663                                        IfTrace4(TRUE, ". . [%5d] %5d    @ %p[%x]\n",
00664                                                 e->ymax-1, e->xvalues[e->ymax-1-e->ymin], e, e->flag);
00665                                        for (y=e->ymax-2; y >= e->ymin; y--)
00666                                                IfTrace2(TRUE, ". . [%5d] %5d      \"\n", y, e->xvalues[y-e->ymin]);
00667                                        e->flag |= ISPERMANENT(ON);
00668                                        if (e == e2)
00669                                                break;
00670                                }
00671                        }
00672                        do {
00673                                e2 = before(e2);
00674                        } while (!ISBREAK(before(e2), e2));
00675                }
00676        }
00677 }
00678  
00679 static struct edgelist *before(e)
00680        struct edgelist *e;
00681 {
00682        struct edgelist *r;
00683        for (r = e->subpath; r->subpath != e; r = r->subpath) { ; }
00684        return(r);
00685 }
00686  
00687 /*
00688 :h2.Fixing Region Continuity Problems
00689  
00690 Small regions may become disconnected when their connecting segments are
00691 less than a pel wide.  This may be correct in some applications, but in
00692 many (especially small font characters), it is more pleasing to keep
00693 connectivity.  ApplyContinuity() (invoked by +CONTINUITY on the
00694 Interior() fill rule) fixes connection breaks.  The resulting region
00695 is geometrically less accurate, but may be more pleasing to the eye.
00696 */
00697 /*
00698 Here are some macros which we will need:
00699 */
00700  
00701 #define IsValidPel(j) (j!=MINPEL)
00702  
00703 /*
00704 :h3.writeXofY() - Stuffs an X Value Into an "edgelist"
00705  
00706 writeXofY writes an x value into an edge at position 'y'.  It must
00707 update the edge's xmin and xmax.  If there is a possibility that this
00708 new x might exceed the region's bounds, updating those are the
00709 responsibility of the caller.
00710 */
00711  
00712 static void writeXofY(e, y, x)
00713        struct edgelist *e;   /* relevant edgelist                            */
00714        int y;                /* y value                                      */
00715        int x;                /* new x value                                  */
00716 {
00717        if (e->xmin > x)  e->xmin = x;
00718        if (e->xmax < x)  e->xmax = x;
00719        e->xvalues[y - e->ymin] = x;
00720 }
00721  
00722 /*-------------------------------------------------------------------------*/
00723 /* the following three macros tell us whether we are at a birth point, a    */
00724 /* death point, or simply in the middle of the character                */
00725 /*-------------------------------------------------------------------------*/
00726 #define WeAreAtTop(e,i) (ISTOP(e->flag) && e->ymin == i)
00727 #define WeAreAtBottom(e,i) (ISBOTTOM(e->flag) && e->ymax-1 == i)
00728 #define WeAreInMiddle(e,i) \
00729       ((!ISTOP(e->flag) && !ISBOTTOM(e->flag))||(i < e->ymax-1 && i > e->ymin))
00730 /*
00731 The following macro tests if two "edgelist" structures are in the same
00732 swath:
00733 */
00734 #define SAMESWATH(e1,e2)  (e1->ymin == e2->ymin)
00735  
00736 /*
00737 :h3.CollapseWhiteRun() - Subroutine of ApplyContinuity()
00738  
00739 When we have a white run with an implied horizontal line above or
00740 below it, we better have black on the other side of this line.  This
00741 function both tests to see if black is there, and adjusts the end
00742 points (collapses) the white run as necessary if it is not.  The
00743 goal is to collapse the white run as little as possible.
00744 */
00745  
00746 static void CollapseWhiteRun(anchor, yblack, left, right, ywhite)
00747         struct edgelist *anchor;  /* anchor of edge list                     */
00748         pel yblack;          /* y of (hopefully) black run above or below    */
00749         struct edgelist *left;  /* edgelist at left of WHITE run             */
00750         struct edgelist *right;  /* edgelist at right of WHITE run           */
00751         pel ywhite;          /* y location of white run                      */
00752 {
00753        struct edgelist *edge;
00754        struct edgelist *swathstart = anchor;
00755        register pel x;
00756  
00757        if (XofY(left, ywhite) >= XofY(right, ywhite))
00758                return;
00759 /*
00760 Find the swath with 'yblack'.  If we don't find it, completely collapse
00761 the white run and return:
00762 */
00763        while (VALIDEDGE(swathstart)) {
00764                if (yblack < swathstart->ymin)  {
00765                       writeXofY(left, ywhite, XofY(right, ywhite));
00766                       return;
00767                }
00768                if (yblack < swathstart->ymax) break;
00769                swathstart = swathstart->link->link;
00770        }
00771        if(!VALIDEDGE(swathstart)) {
00772                writeXofY(left, ywhite, XofY(right, ywhite));
00773                return;
00774        }
00775 /*
00776 Now we are in the swath that contains 'y', the reference line above
00777 or below that we are trying to maintain continuity with.  If black
00778 in this line begins in the middle of our white run, we must collapse
00779 the white run from the left to that point.  If black ends in the
00780 middle of our white run, we must collapse the white run from the right
00781 to that point.
00782 */
00783        for (edge = swathstart; VALIDEDGE(edge); edge = edge->link) {
00784  
00785                if (!SAMESWATH(swathstart,edge))
00786                        break;
00787                if( XofY(edge, yblack) > XofY(left, ywhite)) {
00788                        if (ISLEFT(edge->flag)) {
00789                                 x = XofY(edge, yblack);
00790                                 if (XofY(right, ywhite) < x)
00791                                        x = XofY(right, ywhite);
00792                                 writeXofY(left, ywhite, x);
00793                        }
00794                        else {
00795                                 x = XofY(edge, yblack);
00796                                 while (edge->link != NULL && SAMESWATH(edge, edge->link)
00797                                        && x >= XofY(edge->link, yblack) ) {
00798                                        edge = edge->link->link;
00799                                        x = XofY(edge, yblack);
00800                                 }
00801                                 if (x < XofY(right, ywhite))
00802                                        writeXofY(right, ywhite, x);
00803                                 return;
00804                        }
00805                }
00806        }
00807        writeXofY(left, ywhite, XofY(right, ywhite));
00808 }
00809  
00810 /*
00811 :h3.ApplyContinuity() - Fix False Breaks in a Region
00812  
00813 This is the externally visible routine called from the REGIONS module
00814 when the +CONTINUITY flag is on the Interior() fill rule.
00815 */
00816  
00817 void ApplyContinuity(R)
00818 struct region *R;
00819 {
00820  struct edgelist *left;
00821  struct edgelist *right;
00822  struct edgelist *edge,*e2;
00823  pel rightXabove,rightXbelow,leftXabove,leftXbelow;
00824  pel leftX,rightX;
00825  int i;
00826  LONG newcenter,abovecenter,belowcenter;
00827  
00828  FixSubPaths(R);
00829  if (RegionDebug >= 3)
00830         DumpSubPaths(R->anchor);
00831  left = R->anchor;
00832 /* loop through and do all of the easy checking. ( no tops or bottoms) */
00833  while(VALIDEDGE(left))
00834  {
00835   right = left->link;
00836   for(i=left->ymin;i<left->ymax;++i)
00837   {
00838    leftX       = findXofY(left,i);
00839    rightX      = findXofY(right,i);
00840    leftXbelow  = findXofY(left,i+1);
00841    rightXbelow = findXofY(right,i+1);
00842    if(rightX <= leftX)
00843    {
00844 /* then, we have a break in a near vertical line */
00845      leftXabove  = findXofY(left,i-1);
00846      rightXabove = findXofY(right,i-1);
00847      if( IsValidPel(leftXabove) && IsValidPel(rightXabove) )
00848      {
00849       abovecenter = leftXabove + rightXabove;
00850      }
00851      else
00852      {
00853       abovecenter = leftX + rightX;
00854      }
00855      if( IsValidPel(leftXbelow) && IsValidPel(rightXbelow) )
00856      {
00857       belowcenter = leftXbelow + rightXbelow;
00858      }
00859      else
00860      {
00861       belowcenter = leftX + rightX;
00862      }
00863      newcenter = abovecenter + belowcenter;
00864      if( newcenter > 4*leftX )
00865      {
00866       rightX = rightX + 1;
00867      }
00868      else if( newcenter < 4*leftX)
00869      {
00870       leftX = leftX - 1;
00871      }
00872      else
00873      {
00874       rightX = rightX + 1;
00875      }
00876      writeXofY(right,i,rightX);
00877      writeXofY(left,i,leftX);
00878      if(rightX > R->xmax) {R->xmax = rightX;}
00879      if(leftX < R->xmin) {R->xmin = leftX;}
00880    }
00881    if( !WeAreAtBottom(left,i) && (leftXbelow>=rightX))
00882    {
00883 /* then we have a break in a near horizontal line in the middle */
00884     writeXofY(right,i,leftXbelow);
00885    }
00886    if( !WeAreAtBottom(right,i) && (leftX >=rightXbelow))
00887    {
00888 /* then we have a break in a near horizontal line in the middle */
00889     writeXofY(left,i,rightXbelow);
00890    }
00891   }
00892   left = right->link;
00893  }
00894 /*
00895 There may be "implied horizontal lines" between edges that have
00896 implications for continuity.  This loop looks for white runs that
00897 have implied horizontal lines on the top or bottom, and calls
00898 CollapseWhiteRuns to check and fix any continuity problems from
00899 them.
00900 */
00901       for (edge = R->anchor; VALIDEDGE(edge); edge = edge->link) {
00902               if ((!ISTOP(edge->flag) && !ISBOTTOM(edge->flag)) || ISLEFT(edge->flag))
00903                       continue;  /* at some future date we may want left edge logic here too */
00904               for (e2 = edge->link; VALIDEDGE(e2) && SAMESWATH(edge,e2); e2 = e2->link) {
00905                       if (ISTOP(e2->flag) && ISTOP(edge->flag)
00906                           && NONE != ImpliedHorizontalLine(edge,e2,edge->ymin)) {
00907                               if (ISLEFT(e2->flag))
00908                                       CollapseWhiteRun(R->anchor, edge->ymin-1,
00909                                                        edge, e2, edge->ymin);
00910                       }
00911                       if (ISBOTTOM(e2->flag) && ISBOTTOM(edge->flag)
00912                           && NONE != ImpliedHorizontalLine(edge,e2, edge->ymax)) {
00913                               if (ISLEFT(e2->flag))
00914                                       CollapseWhiteRun(R->anchor, edge->ymax,
00915                                                        edge, e2, edge->ymax-1);
00916                       }
00917               }
00918       }
00919 }
00920  
00921  
00922  
00923