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