Back to index

tetex-bin  3.0
regions.c
Go to the documentation of this file.
00001 /* $XConsortium: regions.c,v 1.4 91/10/10 11:18:57 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  /* REGIONS  CWEB         V0023 LOTS                                 */
00030 /*
00031 :h1 id=regions.REGIONS Module - Regions Operator Handler
00032  
00033 This module is responsible for creating and manipulating regions.
00034  
00035 &author. Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com)
00036  
00037  
00038 :h3.Include Files
00039  
00040 The included files are:
00041 */
00042  
00043 #include  "types.h"
00044 #include  "objects.h"
00045 #include  "spaces.h"
00046 #include  "regions.h"
00047 #include  "paths.h"
00048 #include  "curves.h"
00049 #include  "lines.h"
00050 #include  "pictures.h"
00051 #include  "fonts.h"
00052 #include  "hints.h"
00053 #include  "strokes.h"      /* to pick up 'DoStroke'                        */
00054 static int Unwind();
00055 #ifdef HAVE_PROTOTYPES
00056 static void newfilledge(register struct region *, fractpel, fractpel,
00057                      fractpel, fractpel, int);
00058 static void vertjoin(register struct edgelist *, register struct edgelist *);
00059 static void discard(register struct edgelist *, register struct edgelist *);
00060 static void cedgemin(register int, register pel *, register pel);
00061 static void cedgemax(register int, register pel *, register pel);
00062 static void edgemin(register int, register pel *, register pel *);
00063 static void edgemax(register int, register pel *, register pel *);
00064 #else
00065 static int newfilledge();
00066 static int vertjoin();
00067 static discard();
00068 static int edgemin();
00069 static int edgemax();
00070 #endif
00071 static struct edgelist *splitedge();
00072 static int touches();
00073 static int crosses();
00074 static int edgecheck();
00075 static struct edgelist *NewEdge();
00076  
00077 /*
00078 :h3.Functions Provided to the TYPE1IMAGER User
00079  
00080 This module provides the following TYPE1IMAGER entry points:
00081 */
00082  
00083 /*SHARED LINE(S) ORIGINATED HERE*/
00084 /*
00085 :h3.Functions Provided to Other Modules
00086  
00087 This module provides the following entry points to other modules:
00088 */
00089  
00090 /*SHARED LINE(S) ORIGINATED HERE*/
00091 /*
00092 :h3.Macros Provided to Other Modules
00093  
00094 :h4.GOING_TO() - Macro Predicate Needed for Changing Direction, Etc.
00095  
00096 The actual generation of run end lists (edge boundaries) is left
00097 to the low level rasterizing modules, LINES and CURVES.  There
00098 are some global region-type
00099 questions that occur when doing a low-level
00100 rasterization:
00101 :ol.
00102 :li.Did we just change direction in Y and therefore need to start
00103 a new edge?
00104 :li.Did we run out of allocated edge space?
00105 :li.Do the minimum or maximum X values for the current edge need
00106 updating?
00107 :eol.
00108 In general the REGIONS is not smart enough to answer those questions
00109 itself.  (For example, determining if and when a curve changes direction
00110 may need detailed curve knowledge.)  Yet, this must be done efficiently.
00111 We provide a macro "GOING_TO" where the invoker tells us where it is
00112 heading for (x2,y2), plus where it is now (x1,y1), plus the current
00113 region under construction, and the macro answers the questions above.
00114 */
00115  
00116 /*SHARED LINE(S) ORIGINATED HERE*/
00117 /*
00118 :h2.Data Structures Used to Represent Regions
00119  
00120 :h3.The "region" Structure
00121  
00122 The region structure is an anchor for a linked list of "edgelist"
00123 structures (see :hdref refid=edgelist..).  It also summarizes the
00124 information in the edgelist structures (for example, the bounding
00125 box of the region).  And, it contains scratch areas used during
00126 the creation of a region.
00127 */
00128  
00129 /*SHARED LINE(S) ORIGINATED HERE*/
00130 /*
00131 The ISOPTIMIZED flag tells us if we've put a permanent region in
00132 'optimal' form.
00133 */
00134 #define   ISOPTIMIZED(flag)    ((flag)&0x10)
00135  
00136 /*
00137 The ISRECTANGULAR flag tells us if a region is a rectangle.  We don't
00138 always notice rectangles--if this flag is set, the region definitely
00139 is a rectangle, but some rectangular regions will not have the flag
00140 set.  The flag is used to optimize some paths.
00141 */
00142  
00143 /*SHARED LINE(S) ORIGINATED HERE*/
00144 /*
00145 :h4."INFINITY" - A Constant Region Structure of Infinite Extent
00146  
00147 Infinity is the complement of a null area:
00148 Note - removed the refcount = 1 init, replaced with references = 2 3-26-91 PNM
00149 */
00150 static struct region t1_infinity = { REGIONTYPE,
00151                            ISCOMPLEMENT(ON)+ISINFINITE(ON)+ISPERMANENT(ON)+ISIMMORTAL(ON), 2,
00152                            0, 0, 0, 0,
00153                            0, 0, 0, 0,
00154                            NULL, NULL,
00155                            0, 0, 0, 0, 0, NULL, NULL,
00156                            NULL, 0, NULL, NULL };
00157 struct region *INFINITY = &t1_infinity;
00158  
00159 /*
00160 :h4."EmptyRegion" - A Region Structure with Zero Area
00161  
00162 This structure is used to initialize the region to be built in
00163 Interior():
00164 Note - replaced refcount = 1 init with references = 2 3-26-91 PNM
00165 */
00166  
00167 /*SHARED LINE(S) ORIGINATED HERE*/
00168 struct region EmptyRegion = { REGIONTYPE,
00169                            ISPERMANENT(ON)+ISIMMORTAL(ON), 2,
00170                            0, 0, 0, 0,
00171                            MAXPEL, MAXPEL, MINPEL, MINPEL,
00172                            NULL, NULL,
00173                            0, 0, 0, 0, 0, NULL, NULL,
00174                            NULL, 0, NULL, NULL };
00175  
00176 /*
00177 :h3 id=edgelist.The "edgelist" Structure
00178  
00179 Regions are represented by a linked list of 'edgelist' structures.
00180 When a region is complete, the structures are paired, one for the
00181 left and one for the right edge.  While a region is being built,
00182 this rule may be violated temporarily.
00183  
00184 An 'edgelist' structure contains the X values for a given span
00185 of Y values.  The (X,Y) pairs define an edge.  We use the crack
00186 and edge coordinate system, so that integer values of X and Y
00187 go between pels.  The edge is defined between the minimum Y and
00188 maximum Y.
00189  
00190 The linked list is kept sorted from top to bottom, that is, in
00191 increasing y.  Also, if 'e1' is an edgelist structure and 'e2' is the
00192 next one in the list, they must have exactly the same ymin,ymax values
00193 or be totally disjoint.  These two requirements mean that if e2's ymin
00194 is less than e1's ymax, it must be exactly equal to e1's ymin.  A
00195 sublist of structures with identical ymin and ymax values is called a
00196 'swath'.
00197  
00198 In addition, edgelist structures are separately linked together based
00199 on what subpath originally created them; each subpath is kept as a
00200 separate circular linked list.  This information is ignored unless
00201 continuity checking is invoked.  See :hdref refid=subpath. for a
00202 complete description of this.
00203 */
00204  
00205  
00206 /*SHARED LINE(S) ORIGINATED HERE*/
00207  
00208 /*
00209 The "edgelist" structure follows the convention of TYPE1IMAGER user
00210 objects, having a type field and a flag field as the first two
00211 elements.  However, the user never sees "edgelist" structures
00212 directly; he is given handles to "region" structures only.
00213  
00214 By having a type field, we can use the "copy" feature of Allocate()
00215 to duplicate edge lists quickly.
00216  
00217 We also define two flag bits for this structure.  The ISDOWN bit is set
00218 if the edge is going in the direction of increasing Y. The ISAMBIGUOUS
00219 bit is set if the edge is identical to its neighbor (edge->link); such
00220 edges may be "left" when they should be "right", or vice versa,
00221 unnecessarily confusing the continuity checking logic.  The FixSubPaths()
00222 routine in HINTS will swap ambiguous edges if that avoids crossing edges;
00223 see :hdref refid=fixsubp..
00224 */
00225  
00226 /*SHARED LINE(S) ORIGINATED HERE*/
00227  
00228 /*
00229 :h3.KillRegion() - Destroys a Region
00230  
00231 KillRegion nominally just decrements the reference count to that region.
00232 If the reference count becomes 0, all memory associated with it is
00233 freed.  We just follow the linked list, freeing as we go, then kill any
00234 associated (thresholded) picture.
00235 Note - added conditional return based on references 3-26-91 PNM
00236 */
00237  
00238 void KillRegion(area)
00239         register struct region *area;  /* area to free                       */
00240 {
00241         register struct edgelist *p;  /* loop variable                       */
00242         register struct edgelist *next;  /* loop variable                    */
00243  
00244         if (area->references < 0)
00245                t1_abort("KillRegion:  negative reference count");
00246         if ( (--(area->references) > 1) ||
00247            ( (area->references == 1) && !ISPERMANENT(area->flag) ) )
00248             return;
00249  
00250         for (p=area->anchor; p != NULL; p=next) {
00251                next = p->link;
00252                Free(p);
00253         }
00254         if (area->thresholded != NULL)
00255                  KillPicture(area->thresholded);
00256         Free(area);
00257 }
00258 /*
00259 :h3.CopyRegion() - Makes a Copy of a Region
00260 */
00261 struct region *CopyRegion(area)
00262         register struct region *area;  /* region to duplicate                */
00263 {
00264         register struct region *r;  /* output region built here              */
00265         register struct edgelist *last;  /* loop variable                    */
00266         register struct edgelist *p,*newp;  /* loop variables                */
00267  
00268         r = (struct region *)Allocate(sizeof(struct region), area, 0);
00269         r->anchor = NULL;
00270  
00271         for (p=area->anchor; VALIDEDGE(p); p=p->link) {
00272  
00273                newp = NewEdge(p->xmin, p->xmax, p->ymin, p->ymax, p->xvalues, ISDOWN(p->flag));
00274                if (r->anchor == NULL)
00275                        r->anchor = last = newp;
00276                else
00277                        last->link = newp;
00278  
00279                last = newp;
00280         }
00281         if (area->thresholded != NULL)
00282     /* replaced DupPicture with Dup() 3-26-91 PNM */
00283                r->thresholded = (struct picture *)Dup(area->thresholded);
00284         return(r);
00285 }
00286 /*
00287 :h4.NewEdge() - Allocates and Returns a New "edgelist" Structure
00288  
00289 We allocate space for the X values contiguously with the 'edgelist'
00290 structure that locates them.  That way, we only have to free the
00291 edgelist structure to free all memory associated with it.  Damn
00292 clever, huh?
00293 */
00294  
00295 static struct edgelist *NewEdge(xmin, xmax, ymin, ymax, xvalues, isdown)
00296        pel xmin,xmax;        /* X extent of edge                             */
00297        pel ymin,ymax;        /* Y extent of edge                             */
00298        pel *xvalues;         /* list of X values for entire edge             */
00299        int isdown;           /* flag:  TRUE means edge progresses downward   */
00300 {
00301        static struct edgelist template = {
00302                  EDGETYPE, 0, 1, NULL, NULL,
00303                  0, 0, 0, 0, NULL };
00304  
00305        register struct edgelist *r;  /* returned structure                   */
00306        register int iy;      /* ymin adjusted for 'long' alignment purposes  */
00307  
00308        IfTrace2((RegionDebug),"....new edge: ymin=%d, ymax=%d ",
00309                                               (LONG)ymin, (LONG) ymax);
00310        if (ymin >= ymax)
00311                t1_abort("newedge: height not positive");
00312 /*
00313 We are going to copy the xvalues into a newly allocated area.  It
00314 helps performance if the values are all "long" aligned.  We can test
00315 if the xvalues are long aligned by ANDing the address with the
00316 (sizeof(long) - 1)--if non zero, the xvalues are not aligned well.  We
00317 set 'iy' to the ymin value that would give us good alignment:
00318 */
00319 #if defined (__alpha)
00320        iy = ymin - (((long) xvalues) & (sizeof(LONG) - 1)) / sizeof(pel);
00321 #else
00322        iy = ymin - (((int) xvalues) & (sizeof(LONG) - 1)) / sizeof(pel);
00323 #endif 
00324        r = (struct edgelist *)Allocate(sizeof(struct edgelist), &template,
00325                              (ymax - iy) * sizeof(pel));
00326  
00327        if (isdown) r->flag = ISDOWN(ON);
00328        r->xmin = xmin;
00329        r->xmax = xmax;
00330        r->ymin = ymin;
00331        r->ymax = ymax;
00332  
00333        r->xvalues = (pel *) FOLLOWING(r);
00334        if (ymin != iy) {
00335                r->xvalues += ymin - iy;
00336                xvalues -= ymin - iy;
00337        }
00338  
00339 /*
00340 We must round up (ymax - iy) so we get the ceiling of the number of
00341 longs.  The destination must be able to hold these extra bytes because
00342 Allocate() makes everything it allocates be in multiples of longs.
00343 */
00344        LONGCOPY(&r[1], xvalues, (ymax - iy) * sizeof(pel) + sizeof(LONG) - 1);
00345  
00346        IfTrace1((RegionDebug),"result=%x\n", r);
00347        return(r);
00348 }
00349  
00350 /*
00351 :h2.Building Regions
00352  
00353 :h3.Interior() - Iterate Through a Path, Building a Region
00354  
00355 This routine is the workhorse driver routine that iterates through a
00356 path, calling the appropriate stepping routines to actually produce the
00357 run end "edgelist" structures.
00358  
00359 :ol.
00360 :li."Interior" calls StepLine or StepConic or StepBezier as appropriate
00361 to produce run ends.
00362 :li.Occasionally these routines will notice a change in Y direction
00363 and will call ChangeDirection (through the GOING_TO macro); this is
00364 a call back to the REGIONS module.
00365 :li.ChangeDirection will call whatever function is in the region
00366 structure; for Interior, this function is 'newfilledge'.
00367 :li.Newfilledge will call NewEdge to create a new edgelist structure,
00368 then, call SortSwath to sort it onto the linked list being built at
00369 the region "anchor".
00370 :eol.
00371  
00372 By making the function called by ChangeDirection be a parameter of the
00373 region, we allow the same ChangeDirection logic to be used by stroking.
00374 */
00375  
00376 /*SHARED LINE(S) ORIGINATED HERE*/
00377  
00378 struct region *Interior(p, fillrule)
00379        register struct segment *p;    /* take interior of this path          */
00380        register int fillrule;         /* rule to follow if path crosses itself */
00381 {
00382        register fractpel x,y;  /* keeps ending point of path segment         */
00383        fractpel lastx,lasty; /* previous x,y from path segment before        */
00384        register struct region *R;  /* region I will build                    */
00385        register struct segment *nextP; /* next segment of path */
00386        struct fractpoint hint; /* accumulated hint value */
00387        char tempflag;        /* flag; is path temporary?                     */
00388        char Cflag;           /* flag; should we apply continuity?            */
00389  
00390        IfTrace2((MustTraceCalls),".  INTERIOR(%x, %d)\n", p, (LONG) fillrule);
00391  
00392        if (p == NULL)
00393                return(NULL);
00394 /*
00395 Establish the 'Cflag' continuity flag based on user's fill rule and
00396 our own 'Continuity' pragmatic (0: never do continuity, 1: do what
00397 user asked, >1: do it regardless).
00398 */
00399        if (fillrule > 0) {
00400                Cflag = Continuity > 0;
00401                fillrule -= CONTINUITY;
00402        }
00403        else
00404                Cflag = Continuity > 1;
00405  
00406        ARGCHECK((fillrule != WINDINGRULE && fillrule != EVENODDRULE),
00407                        "Interior: bad fill rule", NULL, NULL, (1,p), struct region *);
00408  
00409        if (p->type == TEXTTYPE)
00410 /*             if (fillrule != EVENODDRULE)
00411                else */
00412                        return((struct region *)UniquePath(p));
00413        if (p->type == STROKEPATHTYPE)
00414                if (fillrule == WINDINGRULE)
00415                        return((struct region *)DoStroke(p));
00416                else
00417                        p = CoercePath(p);
00418  
00419        R = (struct region *)Allocate(sizeof(struct region), &EmptyRegion, 0);
00420  
00421        ARGCHECK(!ISPATHANCHOR(p), "Interior:  bad path", p, R, (0), struct region *);
00422        ARGCHECK((p->type != MOVETYPE), "Interior:  path not closed", p, R, (0), struct region *);
00423  
00424  
00425 /* changed definition from !ISPERMANENT to references <= 1 3-26-91 PNM */
00426        tempflag =  (p->references <= 1); /* only first segment in path is so marked */
00427        if (!ISPERMANENT(p->flag)) p->references -= 1;
00428  
00429        R->newedgefcn = newfilledge;
00430 /*
00431 Believe it or not, "R" is now completely initialized.  We are counting
00432 on the copy of template to get other fields the way we want them,
00433 namely
00434 :ol.
00435 :li.anchor = NULL
00436 :li.xmin, ymin, xmax, ymax, to minimum and maximum values respectively.
00437 :eol.
00438 Anchor = NULL is very
00439 important to ChangeDirection.
00440 See :hdref refid=CD..
00441  
00442 To minimize problems of "wrapping" in our pel arithmetic, we keep an
00443 origin of the region which is the first move.  Hopefully, that keeps
00444 numbers within plus or minus 32K pels.
00445 */
00446        R->origin.x = 0/*TOFRACTPEL(NEARESTPEL(p->dest.x))*/;
00447        R->origin.y = 0/*TOFRACTPEL(NEARESTPEL(p->dest.y))*/;
00448        lastx = - R->origin.x;
00449        lasty = - R->origin.y;
00450 /*
00451 ChangeDirection initializes other important fields in R, such as
00452 lastdy, edge, edgeYstop, edgexmin, and edgexmax.  The first segment
00453 is a MOVETYPE, so it will be called first.
00454 */
00455 /*
00456 The hints data structure must be initialized once for each path.
00457 */
00458  
00459        if (ProcessHints)
00460                InitHints(); /* initialize hint data structure */
00461  
00462        while (p != NULL)  {
00463  
00464                x = lastx + p->dest.x;
00465                y = lasty + p->dest.y;
00466  
00467                IfTrace2((HintDebug > 0),"Ending point = (%p,%p)\n", x, y);
00468  
00469                nextP = p->link;
00470  
00471 /*
00472 Here we start the hints processing by initializing the hint value to
00473 zero.  If ProcessHints is FALSE, the value will remain zero.
00474 Otherwise, hint accumulates the computed hint values.
00475 */
00476  
00477                hint.x = hint.y = 0;
00478  
00479 /*
00480 If we are processing hints, and this is a MOVE segment (other than
00481 the first on the path), we need to close (reverse) any open hints.
00482 */
00483  
00484                if (ProcessHints)
00485                        if ((p->type == MOVETYPE) && (p->last == NULL)) {
00486                                CloseHints(&hint);
00487                                IfTrace2((HintDebug>0),"Closed point= (%p,%p)\n",
00488                                                x+hint.x, y+hint.y);
00489                        }
00490  
00491 /*
00492 Next we run through all the hint segments (if any) attached to this
00493 segment.  If ProcessHints is TRUE, we will accumulate computed hint
00494 values.  In either case, nextP will be advanced to the first non-HINT
00495 segment (or NULL), and each hint segment will be freed if necessary.
00496 */
00497  
00498                while ((nextP != NULL) && (nextP->type == HINTTYPE))  {
00499                        if (ProcessHints)
00500                                ProcessHint(nextP, x + hint.x, y + hint.y, &hint);
00501  
00502                        {
00503                                register struct segment *saveP = nextP;
00504  
00505                                nextP = nextP->link;
00506                                if (tempflag)
00507                                        Free(saveP);
00508                        }
00509                }
00510  
00511 /*
00512 We now apply the full hint value to the ending point of the path segment.
00513 */
00514  
00515                x += hint.x;
00516                y += hint.y;
00517  
00518                IfTrace2((HintDebug>0),"Hinted ending point = (%p,%p)\n", x, y);
00519  
00520                switch(p->type) {
00521  
00522                    case LINETYPE:
00523                        StepLine(R, lastx, lasty, x, y);
00524                        break;
00525  
00526                    case CONICTYPE:
00527                    {
00528  
00529 /*
00530 For a conic curve, we apply half the hint value to the conic midpoint.
00531 */
00532  
00533                    }
00534                        break;
00535  
00536                    case BEZIERTYPE:
00537                    {
00538                        register struct beziersegment *bp = (struct beziersegment *) p;
00539  
00540 /*
00541 For a Bezier curve, we apply the full hint value to the Bezier C point.
00542 */
00543  
00544                        StepBezier(R, lastx, lasty,
00545                                  lastx + bp->B.x, lasty + bp->B.y,
00546                                  lastx + bp->C.x + hint.x,
00547                                  lasty + bp->C.y + hint.y,
00548                                  x, y);
00549                    }
00550                        break;
00551  
00552                    case MOVETYPE:
00553 /*
00554 At this point we have encountered a MOVE segment.  This breaks the
00555 path, making it disjoint.
00556 */
00557                        if (p->last == NULL) /* i.e., not first in path */
00558                                ChangeDirection(CD_LAST, R, lastx, lasty, (fractpel) 0);
00559  
00560                        ChangeDirection(CD_FIRST, R, x, y, (fractpel) 0);
00561 /*
00562 We'll just double check for closure here.  We forgive an appended
00563 MOVETYPE at the end of the path, if it isn't closed:
00564 */
00565                        if (!ISCLOSED(p->flag) && p->link != NULL)
00566                                return((struct region *)ArgErr("Fill: sub-path not closed", p, NULL));
00567                        break;
00568  
00569                    default:
00570                        t1_abort("Interior: path type error");
00571                }
00572 /*
00573 We're done with this segment.  Advance to the next path segment in
00574 the list, freeing this one if necessary:
00575 */
00576                lastx = x;  lasty = y;
00577  
00578                if (tempflag)
00579                        Free(p);
00580                p = nextP;
00581        }
00582        ChangeDirection(CD_LAST, R, lastx, lasty, (fractpel) 0);
00583        R->ending.x = lastx;
00584        R->ending.y = lasty;
00585 /*
00586 Finally, clean up the region's based on the user's 'fillrule' request:
00587 */
00588        if (Cflag)
00589              ApplyContinuity(R);
00590        if (fillrule == WINDINGRULE)
00591              Unwind(R->anchor);
00592        return(R);
00593 }
00594 /*
00595 :h4.Unwind() - Discards Edges That Fail the Winding Rule Test
00596  
00597 The winding rule says that upward going edges should be paired with
00598 downward going edges only, and vice versa.  So, if two upward edges
00599 or two downward edges are nominally left/right pairs, Unwind() should
00600 discard the second one.  Everything should balance; we should discard
00601 an even number of edges; of course, we abort if we don't.
00602 */
00603 static int Unwind(area)
00604        register struct edgelist *area;  /* input area modified in place      */
00605 {
00606        register struct edgelist *last,*next;  /* struct before and after current one */
00607        register int y;       /* ymin of current swath                        */
00608        register int count,newcount;  /* winding count registers              */
00609  
00610        IfTrace1((RegionDebug>0),"...Unwind(%x)\n", area);
00611  
00612        while (VALIDEDGE(area)) {
00613  
00614                count = 0;
00615                y = area->ymin;
00616  
00617                do {
00618                        next = area->link;
00619  
00620                        if (ISDOWN(area->flag))
00621                                newcount = count + 1;
00622                        else
00623                                newcount = count - 1;
00624  
00625                        if (count == 0 || newcount == 0)
00626                                last = area;
00627                        else
00628                                discard(last, next);
00629  
00630                        count = newcount;
00631                        area = next;
00632  
00633                } while (area != NULL && area->ymin == y);
00634  
00635                if (count != 0)
00636                        t1_abort("Unwind:  uneven edges");
00637        }
00638 }
00639 /*
00640 :h3."workedge" Array
00641  
00642 This is a statically allocated array where edges are built
00643 before being copied into more permanent storage by NewEdge().
00644 */
00645  
00646 #ifndef   MAXEDGE
00647 #define   MAXEDGE     1000
00648 #endif
00649  
00650 static pel workedge[MAXEDGE];
00651 static pel *currentworkarea = workedge;
00652 static pel currentsize = MAXEDGE;
00653  
00654 /*
00655 :h3 id=cd.ChangeDirection() - Called When Y Direction Changes
00656  
00657 The rasterizing routines call this entry point when they detect
00658 a change in Y.  We then build the current edge and sort it into
00659 emerging edgelist at 'anchor' by calling whatever "newedgefcn"
00660 is appropriate.
00661 */
00662  
00663 void ChangeDirection(type, R, x, y, dy)
00664        int type;             /* CD_FIRST, CD_CONTINUE, or CD_LAST            */
00665        register struct region *R;  /* region in which we are changing direction */
00666        fractpel x,y;         /* current beginning x,y                        */
00667        fractpel dy;          /* direction and magnitude of change in y       */
00668 {
00669        register fractpel ymin,ymax;  /* minimum and maximum Y since last call */
00670        register fractpel x_at_ymin,x_at_ymax;  /* their respective X's       */
00671        register pel iy;      /* nearest integer pel to 'y'                   */
00672        register pel idy;     /* nearest integer pel to 'dy'                  */
00673        register int ydiff;   /* allowed Y difference in 'currentworkarea'    */
00674  
00675        IfTrace4((RegionDebug>0),"Change Y direction (%d) from (%p,%p), dy=%p\n",
00676                                          (LONG) type, x, y, dy);
00677  
00678        if (type != CD_FIRST) {
00679  
00680                if (R->lastdy > 0) {
00681                        ymin = R->firsty;
00682                        x_at_ymin = R->firstx;
00683                        ymax = y;
00684                        x_at_ymax = x;
00685                }
00686                else {
00687                        ymin = y;
00688                        x_at_ymin = x;
00689                        ymax = R->firsty;
00690                        x_at_ymax = R->firstx;
00691                }
00692  
00693                if (ymax < ymin)
00694                        t1_abort("negative sized edge?");
00695  
00696  
00697               /* FIXME: there are not as much parameters as here. */
00698                (*R->newedgefcn)(R, R->edgexmin, R->edgexmax, ymin, ymax,
00699                                    R->lastdy > 0 /*, x_at_ymin, x_at_ymax */);
00700  
00701        }
00702  
00703        R->firsty = y;
00704        R->firstx = x;
00705        R->lastdy = dy;
00706  
00707        iy = NEARESTPEL(y);
00708        idy = NEARESTPEL(dy);
00709        if (currentworkarea != workedge && idy < MAXEDGE && idy > -MAXEDGE) {
00710                NonObjectFree(currentworkarea);
00711                currentworkarea = workedge;
00712                currentsize = MAXEDGE;
00713        }
00714        ydiff = currentsize - 1;
00715        if (dy > 0) {
00716                R->edge = &currentworkarea[-iy];
00717                R->edgeYstop = TOFRACTPEL(ydiff + iy) + FPHALF;
00718        }
00719        else {
00720                R->edge = &currentworkarea[ydiff - iy];
00721                R->edgeYstop = TOFRACTPEL(iy - ydiff) - FPHALF;
00722        }
00723        R->edgexmax = R->edgexmin = x;
00724 /*
00725 If this is the end of a subpath, we complete the subpath circular
00726 chain:
00727 */
00728        if (type == CD_LAST && R->lastedge != NULL) {
00729                register struct edgelist *e = R->firstedge;
00730  
00731                while (e->subpath != NULL)
00732                        e = e->subpath;
00733                e->subpath = R->lastedge;
00734                R->lastedge = R->firstedge = NULL;
00735        }
00736 }
00737 /*
00738 :h3 id=newfill.newfilledge() - Called When We Have a New Edge While Filling
00739  
00740 This is the prototypical "newedge" function passed to "Rasterize" and
00741 stored in "newedgefcn" in the region being built.
00742  
00743 If the edge is non-null, we sort it onto the list of edges we are
00744 building at "anchor".
00745  
00746 This function also has to keep the bounding box of the region
00747 up to date.
00748 */
00749  
00750 #ifdef HAVE_PROTOTYPES
00751 static void newfilledge(register struct region *R,
00752   fractpel xmin, fractpel xmax, fractpel ymin, fractpel ymax, int isdown)
00753 #else
00754 static int newfilledge(R, xmin, xmax, ymin, ymax, isdown)
00755        register struct region *R;  /* region being built                     */
00756        fractpel xmin,xmax;   /* X range of this edge                         */
00757        fractpel ymin,ymax;   /* Y range of this edge                         */
00758        int isdown;           /* flag:  TRUE means edge goes down, else up    */
00759 #endif
00760 {
00761        struct edgelist *swathxsort();  /* 'SortSwath' function               */
00762  
00763        register pel pelxmin,pelymin,pelxmax,pelymax;  /* pel versions of bounds */
00764        register struct edgelist *edge;  /* newly created edge                */
00765  
00766        pelymin = NEARESTPEL(ymin);
00767        pelymax = NEARESTPEL(ymax);
00768        if (pelymin == pelymax)
00769                return;
00770  
00771        pelxmin = NEARESTPEL(xmin);
00772        pelxmax = NEARESTPEL(xmax);
00773  
00774        if (pelxmin < R->xmin)  R->xmin = pelxmin;
00775        if (pelxmax > R->xmax)  R->xmax = pelxmax;
00776        if (pelymin < R->ymin)  R->ymin = pelymin;
00777        if (pelymax > R->ymax)  R->ymax = pelymax;
00778  
00779        edge = NewEdge(pelxmin, pelxmax, pelymin, pelymax, &R->edge[pelymin], isdown);
00780        edge->subpath = R->lastedge;
00781        R->lastedge = edge;
00782        if (R->firstedge == NULL)
00783                R->firstedge = edge;
00784  
00785        R->anchor = SortSwath(R->anchor, edge, swathxsort);
00786  
00787 }
00788  
00789 /*
00790 :h2.Sorting Edges
00791  
00792 :h3.SortSwath() - Vertically Sort an Edge into a Region
00793  
00794 This routine sorts an edge or a pair of edges into a growing region,
00795 so that the region maintains its top-to-bottom, left-to-right form.
00796 The rules for sorting horizontally may vary depending on what you
00797 are doing, but the rules for vertical sorting are always the same.
00798 This routine is passed an argument that is a function that will
00799 perform the horizontal sort on demand (for example, swathxsort() or
00800 SwathUnion()).
00801  
00802 This is a recursive routine.  A new edge (or edge pair) may overlap
00803 the list I am building in strange and wonderful ways.  Edges may
00804 cross.  When this happens, my strategy is to split the incoming edge
00805 (or the growing list) in two at that point, execute the actual sort on
00806 the top part of the split, and recursively call myself to figure out
00807 exactly where the bottom part belongs.
00808 */
00809  
00810 #define   TOP(e)      ((e)->ymin)  /* the top of an edge (for readability    */
00811 #define   BOTTOM(e)   ((e)->ymax)  /* the bottom of an edge (for readability */
00812  
00813 struct edgelist *SortSwath(anchor, edge, swathfcn)
00814        struct edgelist *anchor;  /* list being built                         */
00815        register struct edgelist *edge;  /* incoming edge or pair of edges    */
00816        struct edgelist *(*swathfcn)();  /* horizontal sorter                 */
00817 {
00818        register struct edgelist *before,*after;
00819        struct edgelist base;
00820  
00821        if (RegionDebug > 0) {
00822                if (RegionDebug > 2)  {
00823                        IfTrace3(TRUE,"SortSwath(anchor=%x, edge=%x, fcn=%x)\n",
00824                             anchor, edge, swathfcn);
00825                }
00826                else  {
00827                        IfTrace3(TRUE,"SortSwath(anchor=%x, edge=%x, fcn=%x)\n",
00828                             anchor, edge, swathfcn);
00829                }
00830        }
00831        if (anchor == NULL)
00832                return(edge);
00833  
00834        before = &base;
00835        before->ymin = before->ymax = MINPEL;
00836        before->link = after = anchor;
00837  
00838 /*
00839 If the incoming edge is above the current list, we connect the current
00840 list to the bottom of the incoming edge.  One slight complication is
00841 if the incoming edge overlaps into the current list.  Then, we
00842 first split the incoming edge in two at the point of overlap and recursively
00843 call ourselves to sort the bottom of the split into the current list:
00844 */
00845        if (TOP(edge) < TOP(after)) {
00846                if (BOTTOM(edge) > TOP(after)) {
00847  
00848                        after = SortSwath(after, splitedge(edge, TOP(after)), swathfcn);
00849                }
00850                vertjoin(edge, after);
00851                return(edge);
00852        }
00853 /*
00854 At this point the top of edge is not higher than the top of the list,
00855 which we keep in 'after'.  We move the 'after' point down the list,
00856 until the top of the edge occurs in the swath beginning with 'after'.
00857  
00858 If the bottom of 'after' is below the bottom of the edge, we have to
00859 split the 'after' swath into two parts, at the bottom of the edge.
00860 If the bottom of 'after' is above the bottom of the swath,
00861 */
00862  
00863        while (VALIDEDGE(after)) {
00864  
00865                if (TOP(after) == TOP(edge)) {
00866                        if (BOTTOM(after) > BOTTOM(edge))
00867                                vertjoin(after, splitedge(after, BOTTOM(edge)));
00868                        else if (BOTTOM(after) < BOTTOM(edge)) {
00869                                after = SortSwath(after,
00870                                      splitedge(edge, BOTTOM(after)), swathfcn);
00871                        }
00872                        break;
00873                }
00874                else if (TOP(after) > TOP(edge)) {
00875                        IfTrace0((BOTTOM(edge) < TOP(after) && RegionDebug > 0),
00876                                                 "SortSwath:  disjoint edges\n");
00877                        if (BOTTOM(edge) > TOP(after)) {
00878                                after = SortSwath(after,
00879                                          splitedge(edge, TOP(after)), swathfcn);
00880                        }
00881                        break;
00882                }
00883                else if (BOTTOM(after) > TOP(edge))
00884                        vertjoin(after, splitedge(after, TOP(edge)));
00885  
00886                before = after;
00887                after = after->link;
00888        }
00889  
00890 /*
00891 At this point 'edge' exactly corresponds in height to the current
00892 swath pointed to by 'after'.
00893 */
00894        if (after != NULL && TOP(after) == TOP(edge)) {
00895                before = (*swathfcn)(before, edge);
00896                after = before->link;
00897        }
00898 /*
00899 At this point 'after' contains all the edges after 'edge', and 'before'
00900 contains all the edges before.  Whew!  A simple matter now of adding
00901 'edge' to the linked list in its rightful place:
00902 */
00903        before->link = edge;
00904        if (RegionDebug > 1) {
00905                IfTrace3(TRUE,"SortSwath:  in between %x and %x are %x",
00906                                                 before, after, edge);
00907                while (edge->link != NULL) {
00908                        edge = edge->link;
00909                        IfTrace1(TRUE," and %x", edge);
00910                }
00911                IfTrace0(TRUE,"\n");
00912        }
00913        else
00914                for (; edge->link != NULL; edge = edge->link) { ; }
00915  
00916        edge->link = after;
00917        return(base.link);
00918 }
00919  
00920 /*
00921 :h3.splitedge() - Split an Edge or Swath in Two at a Given Y Value
00922  
00923 This function returns the edge or swath beginning at the Y value, and
00924 is guaranteed not to change the address of the old swath while splitting
00925 it.
00926 */
00927  
00928 static struct edgelist *splitedge(list, y)
00929        struct edgelist *list;  /* area to split                              */
00930        register pel y;       /* Y value to split list at                     */
00931 {
00932        register struct edgelist *new;  /* anchor for newly built list        */
00933        register struct edgelist *last;  /* end of newly built list           */
00934        register struct edgelist *r;  /* temp pointer to new structure        */
00935        register struct edgelist *lastlist;  /* temp pointer to last 'list' value */
00936  
00937        IfTrace2((RegionDebug > 1),"splitedge of %x at %d ", list, (LONG) y);
00938  
00939        lastlist = new = NULL;
00940  
00941        while (list != NULL) {
00942                if (y < list->ymin)
00943                        break;
00944                if (y >= list->ymax)
00945                        t1_abort("splitedge: above top of list");
00946                if (y == list->ymin)
00947                        t1_abort("splitedge: would be null");
00948  
00949                r = (struct edgelist *)Allocate(sizeof(struct edgelist), list, 0);
00950 /*
00951 At this point 'r' points to a copy of the single structure at 'list'.
00952 We will make 'r' be the new split 'edgelist'--the lower half.
00953 We don't bother to correct 'xmin' and 'xmax', we'll take the
00954 the pessimistic answer that results from using the old values.
00955 */
00956                r->ymin = y;
00957                r->xvalues = list->xvalues + (y - list->ymin);
00958 /*
00959 Note that we do not need to allocate new memory for the X values,
00960 they can remain with the old "edgelist" structure.  We do have to
00961 update that old structure so it is not as high:
00962 */
00963                list->ymax = y;
00964 /*
00965 Insert 'r' in the subpath chain:
00966 */
00967                r->subpath = list->subpath;
00968                list->subpath = r;
00969 /*
00970 Now attach 'r' to the list we are building at 'new', and advance
00971 'list' to point to the next element in the old list:
00972 */
00973                if (new == NULL)
00974                        new = r;
00975                else
00976                        last->link = r;
00977                last = r;
00978                lastlist = list;
00979                list = list->link;
00980        }
00981 /*
00982 At this point we have a new list built at 'new'.  We break the old
00983 list at 'lastlist', and add the broken off part to the end of 'new'.
00984 Then, we return the caller a pointer to 'new':
00985 */
00986        if (new == NULL)
00987                t1_abort("null splitedge");
00988        lastlist->link = NULL;
00989        last->link = list;
00990        IfTrace1((RegionDebug > 1),"yields %x\n", new);
00991        return(new);
00992 }
00993  
00994 /*
00995 :h3.vertjoin() - Join Two Disjoint Edge Lists Vertically
00996  
00997 The two edges must be disjoint vertically.
00998 */
00999 #ifdef HAVE_PROTOTYPES
01000 static void vertjoin(register struct edgelist *top,
01001                      register struct edgelist *bottom)
01002 #else
01003 static int vertjoin(top, bottom)
01004        register struct edgelist *top;  /* uppermost region                   */
01005        register struct edgelist *bottom;  /* bottommost region               */
01006 #endif
01007 {
01008        if (BOTTOM(top) > TOP(bottom))
01009                t1_abort("vertjoin not disjoint");
01010  
01011        for (; top->link != NULL; top=top->link) { ; }
01012  
01013        top->link = bottom;
01014        return;
01015 }
01016  
01017 /*
01018 :h3.swathxsort() - Sorting by X Values
01019  
01020 We need to sort 'edge' into its rightful
01021 place in the swath by X value, taking care that we do not accidentally
01022 advance to the next swath while searching for the correct X value.  Like
01023 all swath functions, this function returns a pointer to the edge
01024 BEFORE the given edge in the sort.
01025 */
01026  
01027 struct edgelist *swathxsort(before0, edge)
01028        register struct edgelist *before0;  /* edge before this swath         */
01029        register struct edgelist *edge;  /* input edge                        */
01030 {
01031        register struct edgelist *before;
01032        register struct edgelist *after;
01033        register pel y;
01034  
01035        before = before0;
01036        after = before->link;
01037  
01038        while (after != NULL && TOP(after) == TOP(edge)) {
01039  
01040                register pel *x1,*x2;
01041  
01042                y = TOP(edge);
01043                x1 = after->xvalues;
01044                x2 = edge->xvalues;
01045  
01046                while (y < BOTTOM(edge) && *x1 == *x2) {
01047                        x1++; x2++; y++;
01048                }
01049                if (y >= BOTTOM(edge)) {
01050                        edge->flag |= ISAMBIGUOUS(ON);
01051                        after->flag |= ISAMBIGUOUS(ON);
01052                        break;
01053                }
01054  
01055                if (*x1 >= *x2)
01056                        break;
01057  
01058                before = after;
01059                after = after->link;
01060        }
01061  
01062 /*
01063 At this point, 'edge' is between 'before' and 'after'.  If 'edge' didn't
01064 cross either of those other edges, we would be done.  We check for
01065 crossing.  If it does cross, we split the problem up by calling SortSwath
01066 recursively with the part of the edge that is below the crossing point:
01067 */
01068 {
01069        register int h0,h;    /* height of edge--number of scans              */
01070  
01071        h0 = h = BOTTOM(edge) - y;
01072        y -= TOP(edge);
01073  
01074        if (h0 <= 0) {
01075                IfTrace0((RegionDebug>0),"swathxsort: exactly equal edges\n");
01076                return(before);
01077        }
01078  
01079        if (TOP(before) == TOP(edge))
01080                h -= crosses(h, &before->xvalues[y], &edge->xvalues[y]);
01081        if (after != NULL && TOP(after) == TOP(edge))
01082                h -= crosses(h, &edge->xvalues[y], &after->xvalues[y]);
01083  
01084        if (h < h0) {
01085                SortSwath(before0->link,
01086                          splitedge(edge, TOP(edge) + y + h),
01087                          swathxsort);
01088  
01089        }
01090 }
01091  
01092        return(before);
01093 }
01094 /*
01095 :h3.SwathUnion() - Union Two Edges by X Value
01096  
01097 We have a left and right edge that must be unioned into a growing
01098 swath.  If they are totally disjoint, they are just added in.  The
01099 fun comes in they overlap the existing edges.  Then some edges
01100 will disappear.
01101 */
01102  
01103 struct edgelist *SwathUnion(before0, edge)
01104        register struct edgelist *before0;  /* edge before the swath          */
01105        register struct edgelist *edge;  /* list of two edges to be unioned   */
01106 {
01107        register int h;       /* saves height of edge                         */
01108        register struct edgelist *rightedge;  /* saves right edge of 'edge'   */
01109        register struct edgelist *before,*after;  /* edge before and after    */
01110        int h0;               /* saves initial height                         */
01111  
01112        IfTrace2((RegionDebug > 1),"SwathUnion entered, before=%x, edge=%x\n",
01113                       before0, edge);
01114  
01115        h0 = h = edge->ymax - edge->ymin;
01116        if (h <= 0)
01117                t1_abort("SwathUnion:  0 height swath?");
01118  
01119        before = before0;
01120        after = before->link;
01121  
01122        while (after != NULL && TOP(after) == TOP(edge)) {
01123                register struct edgelist *right;
01124  
01125                right = after->link;
01126                if (right->xvalues[0] >= edge->xvalues[0])
01127                        break;
01128                before = right;
01129                after = before->link;
01130        }
01131 /*
01132 This is the picture at this point.  'L' indicates a left hand edge,
01133 'R' indicates the right hand edge.
01134 '<--->' indicates the degree of uncertainty as to its placement
01135 relative to other edges:
01136 :xmp atomic.
01137    before           after
01138      R            <---L---->  R             L   R    L   R
01139               <---L--->  <------R-------------------------->
01140                  edge
01141 :exmp.
01142 In case the left of 'edge' touches 'before', we need to reduce
01143 the height by that amount.
01144 */
01145        if (TOP(before) == TOP(edge))
01146                h -= touches(h, before->xvalues, edge->xvalues);
01147  
01148        rightedge = edge->link;
01149  
01150        if (after == NULL || TOP(after) != TOP(edge) ||
01151                    after->xvalues[0] > rightedge->xvalues[0]) {
01152               IfTrace2((RegionDebug > 1),
01153                        "SwathUnion starts disjoint: before=%x after=%x\n",
01154                                      before, after);
01155 /*
01156 On this side of the the above 'if', the new edge is disjoint from the
01157 existing edges in the swath.  This is the picture:
01158 :xmp atomic.
01159    before           after
01160      R                L    R     L   R    L   R
01161               L    R
01162              edge
01163 :exmp.
01164 We will verify it remains disjoint for the entire height.  If the
01165 situation changes somewhere down the edge, we split the edge at that
01166 point and recursively call ourselves (through 'SortSwath') to figure
01167 out the new situation:
01168 */
01169                if (after != NULL && TOP(after) == TOP(edge))
01170                        h -= touches(h, rightedge->xvalues, after->xvalues);
01171                if (h < h0)
01172                        SortSwath(before0->link, splitedge(edge, edge->ymin + h), t1_SwathUnion);
01173                /* go to "return" this edge pair; it is totally disjoint */
01174        }
01175        else {
01176 /*
01177 At this point, at the 'else', we know that the
01178 new edge overlaps one or more pairs in the existing swath.  Here is
01179 a picture of our knowledge and uncertainties:
01180 :xmp atomic.
01181    before       after
01182      R            L        R     L   R    L   R
01183             <---L--->   <---R------------------->
01184                edge
01185 :exmp.
01186 We need to move 'after' along until it is to the right of the
01187 right of 'edge'.  ('After' should always point to a left edge of a pair:)
01188 */
01189                register struct edgelist *left;  /* variable to keep left edge in */
01190  
01191                do {
01192                         left = after;
01193                         after = (after->link)->link;
01194  
01195                } while  (after != NULL && TOP(after) == TOP(edge)
01196                                && after->xvalues[0] <= rightedge->xvalues[0]);
01197 /*
01198 At this point this is the picture:
01199 :xmp atomic.
01200    before                 left        after
01201      R            L    R   L      R     L   R
01202             <---L--->        <---R--->
01203                edge
01204 :exmp.
01205 We need to verify that the situation stays like this all the way
01206 down the edge.  Again, if the
01207 situation changes somewhere down the edge, we split the edge at that
01208 point and recursively call ourselves (through 'SortSwath') to figure
01209 out the new situation:
01210 */
01211  
01212                h -= crosses(h, left->xvalues, rightedge->xvalues);
01213                h -= crosses(h, edge->xvalues, ((before->link)->link)->xvalues);
01214  
01215                if (after != NULL && TOP(after) == TOP(edge))
01216  
01217                        h -= touches(h, rightedge->xvalues, after->xvalues);
01218  
01219                IfTrace3((RegionDebug > 1),
01220                       "SwathUnion is overlapped until %d: before=%x after=%x\n",
01221                                           (LONG) TOP(edge) + h, before, after);
01222 /*
01223 OK, if we touched either of our neighbors we need to split at that point
01224 and recursively sort the split edge onto the list.  One tricky part
01225 is that when we recursively sort, 'after' will change if it was not
01226 in our current swath:
01227 */
01228                if (h < h0) {
01229                        SortSwath(before0->link,
01230                                  splitedge(edge, edge->ymin + h),
01231                                  t1_SwathUnion);
01232  
01233                        if (after == NULL || TOP(after) != TOP(edge))
01234                                  for (after = before0->link;
01235                                       TOP(after) == TOP(edge);
01236                                       after = after->link) { ; }
01237                }
01238 /*
01239 Now we need to augment 'edge' by the left and right of the overlapped
01240 swath, and to discard all edges between before and after, because they
01241 were overlapped and have been combined with the new incoming 'edge':
01242 */
01243                edge->xmin = MIN(edge->xmin, (before->link)->xmin);
01244                edge->xmax = MIN(edge->xmax, (before->link)->xmax);
01245                edgemin(h, edge->xvalues, (before->link)->xvalues);
01246                rightedge->xmin = MAX(rightedge->xmin, (left->link)->xmin);
01247                rightedge->xmax = MAX(rightedge->xmax, (left->link)->xmax);
01248                edgemax(h, rightedge->xvalues, (left->link)->xvalues);
01249                discard(before, after);
01250        }
01251        return(before);
01252 }
01253 /*
01254 :h3.swathrightmost() - Simply Sorts New Edge to Rightmost of Swath
01255  
01256 Like all swath functions, this function returns a pointer to the edge
01257 BEFORE the given edge in the sort.
01258 */
01259  
01260 struct edgelist *swathrightmost(before, edge)
01261        register struct edgelist *before;  /* edge before this swath         */
01262        register struct edgelist *edge;  /* input edge                        */
01263 {
01264        register struct edgelist *after;
01265  
01266        after = before->link;
01267  
01268        while (after != NULL && TOP(after) == TOP(edge)) {
01269                before = after;
01270                after = after->link;
01271        }
01272  
01273        return(before);
01274  
01275 }
01276 /*
01277 :h3.touches() - Returns the Remaining Height When Two Edges Touch
01278  
01279 So, it will return 0 if they never touch.  Allows incredibly(?) mnemonic
01280 if (touches(...)) construct.
01281 */
01282  
01283 static int touches(h, left, right)
01284        register int h;
01285        register pel *left,*right;
01286 {
01287        for (; h > 0; h--)
01288                if (*left++ >= *right++)
01289                        break;
01290        return(h);
01291 }
01292 /*
01293 :h3.crosses() - Returns the Remaining Height When Two Edges Cross
01294  
01295 So, it will return 0 if they never cross.
01296 */
01297  
01298 static int crosses(h, left, right)
01299        register int h;
01300        register pel *left,*right;
01301 {
01302        for (; h > 0; h--)
01303                if (*left++ > *right++)
01304                        break;
01305        return(h);
01306 }
01307 /*
01308 :h3.cedgemin() - Stores the Mininum of an Edge and an X Value
01309 */
01310  
01311 static void cedgemin(register int h, register pel *e1, register pel x)
01312 {
01313        for (; --h >= 0; e1++)
01314                if (*e1 > x)
01315                        *e1 = x;
01316 }
01317 /*
01318 :h3.cedgemax() - Stores the Maximum of an Edge and an X Value
01319 */
01320  
01321 static void cedgemax(register int h, register pel *e1, register pel x)
01322 {
01323        for (; --h >= 0; e1++)
01324                if (*e1 < x)
01325                        *e1 = x;
01326 }
01327 /*
01328 :h3.edgemin() - Stores the Mininum of Two Edges in First Edge
01329 */
01330  
01331 static void edgemin(register int h, register pel *e1, register pel *e2)
01332 {
01333        for (; --h >= 0; e1++,e2++)
01334                if (*e1 > *e2)
01335                        *e1 = *e2;
01336 }
01337 /*
01338 :h3.edgemax() - Stores the Maximum of Two Edges in First Edge
01339 */
01340  
01341 static void edgemax(register int h, register pel *e1, register pel *e2)
01342 {
01343        for (; --h >= 0; e1++,e2++)
01344                if (*e1 < *e2)
01345                        *e1 = *e2;
01346 }
01347 /*
01348 :h3 id=discard.discard() - Discard All Edges Between Two Edges
01349  
01350 At first glance it would seem that we could discard an edgelist
01351 structure merely by unlinking it from the list and freeing it.  You are
01352 wrong, region-breath!  For performance, the X values associated with an
01353 edge are allocated contiguously with it.  So, we free the X values when
01354 we free a structure.  However, once an edge has been split, we are no
01355 longer sure which control block actually is part of the memory block
01356 that contains the edges.  Rather than trying to decide, we play it safe
01357 and never free part of a region.
01358  
01359 So, to mark a 'edgelist' structure as discarded, we move it to the end
01360 of the list and set ymin=ymax.
01361 */
01362  
01363 #ifdef HAVE_PROTOTYPES
01364 static void discard(register struct edgelist *left, register struct edgelist *right)
01365 #else
01366 static discard(left, right)
01367        register struct edgelist *left,*right;  /* all edges between here exclusive */
01368                                        /* should be discarded */
01369 #endif
01370 {
01371        register struct edgelist *beg,*end,*p;
01372  
01373        IfTrace2((RegionDebug > 0),"discard:  l=%x, r=%x\n", left, right);
01374  
01375        beg = left->link;
01376        if (beg == right)
01377                return;
01378  
01379        for (p = beg; p != right; p = p->link) {
01380                if (p->link == NULL && right != NULL)
01381                        t1_abort("discard():  ran off end");
01382                IfTrace1((RegionDebug > 0),"discarding %x\n", p);
01383                p->ymin = p->ymax = 32767;
01384                end = p;
01385        }
01386        /*
01387        * now put the chain beg/end at the end of right, if it is not
01388        * already there:
01389        */
01390        if (right != NULL) {
01391                left->link = right;
01392                while (right->link != NULL)
01393                        right = right->link;
01394                right->link = beg;
01395        }
01396        end->link = NULL;
01397 }
01398  
01399 /*
01400 :h2.Changing the Representation of Regions
01401  
01402 For convenience and/or performance, we sometimes like to change the way
01403 regions are represented.  This does not change the object itself, just
01404 the representation, so these transformations can be made on a permanent
01405 region.
01406  
01407 */
01408  
01409 void MoveEdges(R, dx, dy)
01410        register struct region *R; /* region to modify                        */
01411        register fractpel dx,dy;  /* delta X and Y to move edge list by       */
01412 {
01413        register struct edgelist *edge;  /* for looping through edges         */
01414  
01415        R->origin.x += dx;
01416        R->origin.y += dy;
01417        R->ending.x += dx;
01418        R->ending.y += dy;
01419        if (R->thresholded != NULL) {
01420                R->thresholded->origin.x -= dx;
01421                R->thresholded->origin.y -= dy;
01422        }
01423 /*
01424 From now on we will deal with dx and dy as integer pel values:
01425 */
01426        dx = NEARESTPEL(dx);
01427        dy = NEARESTPEL(dy);
01428        if (dx == 0 && dy == 0)
01429                return;
01430  
01431        R->xmin += dx;
01432        R->xmax += dx;
01433        R->ymin += dy;
01434        R->ymax += dy;
01435  
01436        for (edge = R->anchor; VALIDEDGE(edge); edge = edge->link) {
01437                edge->ymin += dy;
01438                edge->ymax += dy;
01439                if (dx != 0) {
01440                        register int h;  /* loop index; height of edge        */
01441                        register pel *Xp;  /* loop pointer to X values        */
01442  
01443                        edge->xmin += dx;
01444                        edge->xmax += dx;
01445                        for (Xp = edge->xvalues, h = edge->ymax - edge->ymin;
01446                                      --h >= 0; )
01447                                *Xp++ += dx;
01448                }
01449        }
01450 }
01451  
01452 /*
01453 :h3.UnJumble() - Sort a Region Top to Bottom
01454  
01455 It is an open question whether it pays in general to do this.
01456 */
01457  
01458 void UnJumble(region)
01459        struct region *region;  /* region to sort                             */
01460 {
01461        register struct edgelist *anchor;  /* new lists built here            */
01462        register struct edgelist *edge;  /* edge pointer for loop             */
01463        register struct edgelist *next;  /* ditto                             */
01464  
01465        anchor = NULL;
01466  
01467        for (edge=region->anchor; VALIDEDGE(edge); edge=next) {
01468                if (edge->link == NULL)
01469                        t1_abort("UnJumble:  unpaired edge?");
01470                next = edge->link->link;
01471                edge->link->link = NULL;
01472                anchor = SortSwath(anchor, edge, t1_SwathUnion);
01473        }
01474  
01475        if (edge != NULL)
01476                vertjoin(anchor, edge);
01477  
01478        region->anchor = anchor;
01479        region->flag &= ~ISJUMBLED(ON);
01480 }
01481  
01482 /*
01483 */
01484  
01485 static OptimizeRegion(R)
01486        struct region *R;     /* region to optimize                           */
01487 {
01488        register pel *xP;     /* pel pointer for inner loop                   */
01489        register int x;       /* holds X value                                */
01490        register int xmin,xmax;  /* holds X range                             */
01491        register int h;       /* loop counter                                 */
01492        register struct edgelist *e;  /* edgelist pointer for loop            */
01493  
01494        R->flag |= ISRECTANGULAR(ON);
01495  
01496        for (e = R->anchor; VALIDEDGE(e); e=e->link) {
01497                xmin = MAXPEL;
01498                xmax = MINPEL;
01499                for (h = e->ymax - e->ymin, xP = e->xvalues; --h >= 0;) {
01500                          x = *xP++;
01501                          if (x < xmin)  xmin = x;
01502                          if (x > xmax)  xmax = x;
01503                }
01504                if (xmin != xmax || (xmin != R->xmin && xmax != R->xmax))
01505                        R->flag &= ~ISRECTANGULAR(ON);
01506                if (xmin < e->xmin || xmax > e->xmax)
01507                        t1_abort("Tighten: existing edge bound was bad");
01508                if (xmin < R->xmin || xmax > R->xmax)
01509                        t1_abort("Tighten: existing region bound was bad");
01510                e->xmin = xmin;
01511                e->xmax = xmax;
01512        }
01513        R->flag |= ISOPTIMIZED(ON);
01514 }
01515  
01516 /*
01517 :h2.Miscelaneous Routines
01518  
01519 :h3.MoreWorkArea() - Allocate New Space for "edge"
01520  
01521 Our strategy is to temporarily allocate an array to hold this
01522 unexpectedly large edge.  ChangeDirection frees this array any time
01523 it gets a shorter 'dy'.
01524 */
01525  
01526 /*ARGSUSED*/
01527 void MoreWorkArea(R, x1, y1, x2, y2)
01528        struct region *R;     /* region we are generating                     */
01529        fractpel x1,y1;       /* starting point of line                       */
01530        fractpel x2,y2;       /* ending point of line                         */
01531 {
01532        register int idy;     /* integer dy of line                           */
01533  
01534        idy = NEARESTPEL(y1) - NEARESTPEL(y2);
01535        if (idy < 0)  idy = - idy;
01536  
01537        /*
01538        * we must add one to the delta for the number of run ends we
01539        * need to store:
01540        */
01541        if (++idy > currentsize) {
01542                IfTrace1((RegionDebug > 0),"Allocating edge of %d pels\n", idy);
01543                if (currentworkarea != workedge)
01544                        NonObjectFree(currentworkarea);
01545                currentworkarea = (pel *)Allocate(0, NULL, idy * sizeof(pel));
01546                currentsize = idy;
01547        }
01548        ChangeDirection(CD_CONTINUE, R, x1, y1, y2 - y1);
01549 }
01550  
01551 /*
01552 :h3.BoxClip() - Clip a Region to a Rectangle
01553  
01554 BoxClip also duplicates the region if it is permanent.  Note the
01555 clipping box is specified in REGION coordinates, that is, in
01556 coordinates relative to the region (0,0) point
01557 */
01558  
01559 struct region *BoxClip(R, xmin, ymin, xmax, ymax)
01560        register struct region *R;  /* region to clip                         */
01561        register pel xmin,ymin;  /* upper left hand corner of rectangle       */
01562        register pel xmax,ymax;  /* lower right hand corner                   */
01563 {
01564        struct edgelist anchor;  /* pretend edgelist to facilitate discards   */
01565        register struct edgelist *e,*laste;
01566  
01567        IfTrace1((OffPageDebug),"BoxClip of %x:\n", R);
01568  
01569        R = UniqueRegion(R);
01570  
01571        if (xmin > R->xmin) {
01572                IfTrace2((OffPageDebug),"BoxClip:  left clip old %d new %d\n",
01573                                             (LONG) R->xmin, (LONG) xmin);
01574                R->xmin = xmin;
01575        }
01576        if (xmax < R->xmax) {
01577                IfTrace2((OffPageDebug),"BoxClip:  right clip old %d new %d\n",
01578                                             (LONG) R->xmax, (LONG) xmax);
01579                R->xmax = xmax;
01580        }
01581  
01582        if (ymin > R->ymin) {
01583                IfTrace2((OffPageDebug),"BoxClip:  top clip old %d new %d\n",
01584                                             (LONG) R->ymin, (LONG) ymin);
01585                R->ymin = ymin;
01586        }
01587        if (ymax < R->ymax) {
01588                IfTrace2((OffPageDebug),"BoxClip:  bottom clip old %d new %d\n",
01589                                             (LONG) R->ymax, (LONG) ymax);
01590                R->ymax = ymax;
01591        }
01592  
01593  
01594        laste = &anchor;
01595        anchor.link = R->anchor;
01596  
01597        for (e = R->anchor; VALIDEDGE(e); e = e->link) {
01598                if (TOP(e) < ymin) {
01599                        e->xvalues += ymin - e->ymin;
01600                        e->ymin = ymin;
01601                }
01602                if (BOTTOM(e) > ymax)
01603                        e->ymax = ymax;
01604                if (TOP(e) >= BOTTOM(e)) {
01605                        discard(laste, e->link->link);
01606                        e = laste;
01607                        continue;
01608                }
01609                if (e->xmin < xmin) {
01610                        cedgemax(BOTTOM(e) - TOP(e), e->xvalues, xmin);
01611                        e->xmin = xmin;
01612                        e->xmax = MAX(e->xmax, xmin);
01613                }
01614                if (e->xmax > xmax) {
01615                        cedgemin(BOTTOM(e) - TOP(e), e->xvalues, xmax);
01616                        e->xmin = MIN(e->xmin, xmax);
01617                        e->xmax = xmax;
01618                }
01619                laste = e;
01620        }
01621  
01622        R->anchor = anchor.link;
01623  
01624        return(R);
01625 }
01626  
01627 #ifdef notdef
01628 /*
01629 :h3.CoerceRegion() - Force a TextPath Structure to Become a Region
01630  
01631 We also save the newly created region in the textpath structure, if the
01632 structure was permanent.  Then we don't have to do this again.  Why not
01633 save it all the time?  Well, we certainly could, but I suspect it
01634 wouldn't pay.  We would have to make this region permanent (because we
01635 couldn't have it be consumed) and this would probably require
01636 unnecessary CopyRegions in most cases.
01637 */
01638  
01639 struct region *CoerceRegion(tp)
01640        register struct textpath *tp;  /* input TEXTTYPE                     */
01641 {
01642        struct segment *path; /* temporary character path                     */
01643        struct region *R;     /* returned region                              */
01644  
01645  
01646        R = Interior(path, EVENODDRULE);
01647        return(R);
01648 }
01649 #endif
01650  
01651 /*
01652 :h3.RegionBounds() - Returns Bounding Box of a Region
01653 */
01654  
01655 struct segment *RegionBounds(R)
01656        register struct region *R;
01657 {
01658        extern struct XYspace *IDENTITY;
01659  
01660        register struct segment *path;  /* returned path                      */
01661  
01662        path = BoxPath(IDENTITY, R->ymax - R->ymin, R->xmax - R->xmin);
01663        path = Join(PathSegment(MOVETYPE, R->origin.x + TOFRACTPEL(R->xmin),
01664                                          R->origin.y + TOFRACTPEL(R->ymin) ),
01665                    path);
01666        return(path);
01667 }
01668  
01669 /*
01670 :h2.Formatting/Dump Routines for Debug
01671  
01672 :h3.DumpArea() - Display a Region
01673 */
01674 void DumpArea(area)
01675        register struct region *area;
01676 {
01677        IfTrace1(TRUE,"Dumping area %x,", area);
01678        IfTrace4(TRUE," X %d:%d Y %d:%d;", (LONG) area->xmin,
01679                       (LONG) area->xmax, (LONG) area->ymin,(LONG) area->ymax);
01680        IfTrace4(TRUE," origin=(%p,%p), ending=(%p,%p)\n",
01681                area->origin.x, area->origin.y, area->ending.x, area->ending.y);
01682        DumpEdges(area->anchor);
01683 }
01684  
01685 #define  INSWATH(p, y0, y1)  (p != NULL && p->ymin == y0 && p->ymax == y1)
01686 /*
01687 :h3.DumpEdges() - Display Run End Lists (Edge Lists)
01688 */
01689  
01690 static pel RegionDebugYMin = MINPEL;
01691 static pel RegionDebugYMax = MAXPEL;
01692  
01693 void DumpEdges(edges)
01694        register struct edgelist *edges;
01695 {
01696        register struct edgelist *p,*p2;
01697        register pel ymin = MINPEL;
01698        register pel ymax = MINPEL;
01699        register int y;
01700  
01701        if (edges == NULL) {
01702                IfTrace0(TRUE,"    NULL area.\n");
01703                return;
01704        }
01705        if (RegionDebug <= 1) {
01706                for (p=edges; p != NULL; p = p->link) {
01707                        edgecheck(p, ymin, ymax);
01708                        ymin = p->ymin;  ymax = p->ymax;
01709                        IfTrace3(TRUE,". at %x type=%d flag=%x",
01710                                         p, (LONG) p->type,(LONG) p->flag);
01711                        IfTrace4(TRUE," bounding box HxW is %dx%d at (%d,%d)\n",
01712                                (LONG) ymax - ymin, (LONG) p->xmax - p->xmin,
01713                                (LONG) p->xmin, (LONG) ymin);
01714                }
01715        }
01716        else {
01717  
01718                for (p2=edges; p2 != NULL; ) {
01719  
01720                        edgecheck(p2, ymin, ymax);
01721                        ymin = p2->ymin;
01722                        ymax = p2->ymax;
01723  
01724                        if (RegionDebug > 3 || (ymax > RegionDebugYMin
01725                                    && ymin < RegionDebugYMax)) {
01726                                IfTrace2 (TRUE,". Swath from %d to %d:\n",
01727                                                               ymin, ymax);
01728                                for (p=p2; INSWATH(p,ymin,ymax); p = p->link) {
01729                                        IfTrace4(TRUE,". . at %x[%x] range %d:%d, ",
01730                                                  p, (LONG) p->flag,
01731                                                  (LONG) p->xmin, (LONG)p->xmax);
01732                                        IfTrace1(TRUE, "subpath=%x,\n", p->subpath);
01733                                }
01734                        }
01735                        for (y=MAX(ymin,RegionDebugYMin); y < MIN(ymax, RegionDebugYMax); y++) {
01736                                IfTrace1(TRUE,". . . Y[%5d] ", (LONG) y);
01737                                for (p=p2; INSWATH(p,ymin,ymax); p = p->link)
01738                                        IfTrace1(TRUE,"%5d ",
01739                                                 (LONG) p->xvalues[y - ymin]);
01740                                IfTrace0(TRUE,"\n");
01741                        }
01742                        while (INSWATH(p2, ymin, ymax))
01743                                p2 = p2->link;
01744                }
01745        }
01746 }
01747  
01748 /*
01749 :h3.edgecheck() - For Debug, Verify that an Edge Obeys the Rules
01750 */
01751  
01752 /*ARGSUSED*/
01753 static int edgecheck(edge, oldmin, oldmax)
01754        struct edgelist *edge;
01755        int oldmin,oldmax;
01756 {
01757        if (edge->type != EDGETYPE)
01758                t1_abort("EDGE ERROR: non EDGETYPE in list");
01759 /*
01760 The following check is not valid if the region is jumbled so I took it
01761 out:
01762 */
01763 /*     if (edge->ymin < oldmax && edge->ymin != oldmin)
01764                t1_abort("EDGE ERROR: overlapping swaths"); */
01765 }