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