regions.c

source code: Covert TXT to PDF

               currentsize = MAXEDGE;
       }
       ydiff = currentsize - 1;
       if (dy > 0) {
               R->edge = &currentworkarea[-iy];
               R->edgeYstop = TOFRACTPEL(ydiff + iy) + FPHALF;
       }
       else {
               R->edge = &currentworkarea[ydiff - iy];
               R->edgeYstop = TOFRACTPEL(iy - ydiff) - FPHALF;
       }
       R->edgexmax = R->edgexmin = x;
/*
If this is the end of a subpath, we complete the subpath circular
chain:
*/
       if (type == CD_LAST && R->lastedge != NULL) {
               register struct edgelist *e = R->firstedge;
 
               while (e->subpath != NULL)
                       e = e->subpath;
               e->subpath = R->lastedge;
               R->lastedge = R->firstedge = NULL;
       }
}
/*
:h3 id=newfill.newfilledge() - Called When We Have a New Edge While Filling
 
This is the prototypical "newedge" function passed to "Rasterize" and
stored in "newedgefcn" in the region being built.
 
If the edge is non-null, we sort it onto the list of edges we are
building at "anchor".
 
This function also has to keep the bounding box of the region
up to date.
*/
 
static int newfilledge(R, xmin, xmax, ymin, ymax, isdown)
       register struct region *R;  /* region being built                     */
       fractpel xmin,xmax;   /* X range of this edge                         */
       fractpel ymin,ymax;   /* Y range of this edge                         */
       int isdown;           /* flag:  TRUE means edge goes down, else up    */
{
 
       register pel pelxmin,pelymin,pelxmax,pelymax;  /* pel versions of bounds */
       register struct edgelist *edge;  /* newly created edge                */
 
       pelymin = NEARESTPEL(ymin);
       pelymax = NEARESTPEL(ymax);
       if (pelymin == pelymax)
               return(0);
 
       pelxmin = NEARESTPEL(xmin);
       pelxmax = NEARESTPEL(xmax);
 
       if (pelxmin < R->xmin)  R->xmin = pelxmin;
       if (pelxmax > R->xmax)  R->xmax = pelxmax;
       if (pelymin < R->ymin)  R->ymin = pelymin;
       if (pelymax > R->ymax)  R->ymax = pelymax;
 
       edge = NewEdge(pelxmin, pelxmax, pelymin, pelymax, &R->edge[pelymin], isdown);
       edge->subpath = R->lastedge;
       R->lastedge = edge;
       if (R->firstedge == NULL)
               R->firstedge = edge;
 
       R->anchor = SortSwath(R->anchor, edge, swathxsort);
       return(0);
}
 
/*
:h2.Sorting Edges
 
:h3.SortSwath() - Vertically Sort an Edge into a Region
 
This routine sorts an edge or a pair of edges into a growing region,
so that the region maintains its top-to-bottom, left-to-right form.
The rules for sorting horizontally may vary depending on what you
are doing, but the rules for vertical sorting are always the same.
This routine is passed an argument that is a function that will
perform the horizontal sort on demand (for example, swathxsort() or
SwathUnion()).
 
This is a recursive routine.  A new edge (or edge pair) may overlap
the list I am building in strange and wonderful ways.  Edges may
cross.  When this happens, my strategy is to split the incoming edge
(or the growing list) in two at that point, execute the actual sort on
the top part of the split, and recursively call myself to figure out
exactly where the bottom part belongs.
*/
 
#define   TOP(e)      ((e)->ymin)  /* the top of an edge (for readability    */
#define   BOTTOM(e)   ((e)->ymax)  /* the bottom of an edge (for readability */
 
struct edgelist *SortSwath(anchor, edge, swathfcn)
       struct edgelist *anchor;  /* list being built                         */
       register struct edgelist *edge;  /* incoming edge or pair of edges    */
       struct edgelist *(*swathfcn)();  /* horizontal sorter                 */
{
       register struct edgelist *before,*after;
       struct edgelist base;
 
       if (RegionDebug > 0) {
               if (RegionDebug > 2)  {
                       IfTrace3(TRUE,"SortSwath(anchor=%p, edge=%p, fcn=%p)\n",
                            anchor, edge, swathfcn);
               }
               else  {
                       IfTrace3(TRUE,"SortSwath(anchor=%p, edge=%p, fcn=%p)\n",
                            anchor, edge, swathfcn);
               }
       }
       if (anchor == NULL)
               return(edge);
 
       before = &base;
       before->ymin = before->ymax = MINPEL;
       before->link = after = anchor;
 
/*
If the incoming edge is above the current list, we connect the current
list to the bottom of the incoming edge.  One slight complication is
if the incoming edge overlaps into the current list.  Then, we
first split the incoming edge in two at the point of overlap and recursively
call ourselves to sort the bottom of the split into the current list:
*/
       if (TOP(edge) < TOP(after)) {
               if (BOTTOM(edge) > TOP(after)) {
 
                       after = SortSwath(after, splitedge(edge, TOP(after)), swathfcn);
               }
               vertjoin(edge, after);
               return(edge);
       }
/*
At this point the top of edge is not higher than the top of the list,
which we keep in 'after'.  We move the 'after' point down the list,
until the top of the edge occurs in the swath beginning with 'after'.
 
If the bottom of 'after' is below the bottom of the edge, we have to
split the 'after' swath into two parts, at the bottom of the edge.
If the bottom of 'after' is above the bottom of the swath,
*/
 
       while (VALIDEDGE(after)) {
 
               if (TOP(after) == TOP(edge)) {
                       if (BOTTOM(after) > BOTTOM(edge))
                               vertjoin(after, splitedge(after, BOTTOM(edge)));
                       else if (BOTTOM(after) < BOTTOM(edge)) {
                               after = SortSwath(after,
                                     splitedge(edge, BOTTOM(after)), swathfcn);
                       }
                       break;
               }
               else if (TOP(after) > TOP(edge)) {
                       IfTrace0((BOTTOM(edge) < TOP(after) && RegionDebug > 0),
                                                "SortSwath:  disjoint edges\n");
                       if (BOTTOM(edge) > TOP(after)) {
                               after = SortSwath(after,
                                         splitedge(edge, TOP(after)), swathfcn);
                       }
                       break;
               }
               else if (BOTTOM(after) > TOP(edge))
                       vertjoin(after, splitedge(after, TOP(edge)));
 
               before = after;
               after = after->link;
       }
 
/*
At this point 'edge' exactly corresponds in height to the current
swath pointed to by 'after'.
*/
       if (after != NULL && TOP(after) == TOP(edge)) {
               before = (*swathfcn)(before, edge);
               after = before->link;
       }
/*
At this point 'after' contains all the edges after 'edge', and 'before'
contains all the edges before.  Whew!  A simple matter now of adding
'edge' to the linked list in its rightful place:
*/
       before->link = edge;
       if (RegionDebug > 1) {
               IfTrace3(TRUE,"SortSwath:  in between %p and %p are %p",
                                                before, after, edge);
               while (edge->link != NULL) {
                       edge = edge->link;
                       IfTrace1(TRUE," and %p", edge);
               }
               IfTrace0(TRUE,"\n");
       }
       else
               for (; edge->link != NULL; edge = edge->link) { ; }
 
       edge->link = after;
       return(base.link);
}
 
/*
:h3.splitedge() - Split an Edge or Swath in Two at a Given Y Value
 
This function returns the edge or swath beginning at the Y value, and
is guaranteed not to change the address of the old swath while splitting
it.
*/
 
static struct edgelist *splitedge(list, y)
       struct edgelist *list;  /* area to split                              */
       register pel y;       /* Y value to split list at                     */
{
       register struct edgelist *new;  /* anchor for newly built list        */
       register struct edgelist *last=NULL;  /* end of newly built list           */
       register struct edgelist *r;  /* temp pointer to new structure        */
       register struct edgelist *lastlist;  /* temp pointer to last 'list' value */
 
       IfTrace2((RegionDebug > 1),"splitedge of %p at %d ", list, (LONG) y);
 
       lastlist = new = NULL;
 
       while (list != NULL) {
               if (y < list->ymin)
                       break;
               if (y >= list->ymax)
                       abort("splitedge: above top of list", 33);
               if (y == list->ymin)
                       abort("splitedge: would be null", 34);
 
               r = (struct edgelist *)Allocate(sizeof(struct edgelist), list, 0);
/*
At this point 'r' points to a copy of the single structure at 'list'.
We will make 'r' be the new split 'edgelist'--the lower half.
We don't bother to correct 'xmin' and 'xmax', we'll take the
the pessimistic answer that results from using the old values.
*/
               r->ymin = y;
               r->xvalues = list->xvalues + (y - list->ymin);
/*
Note that we do not need to allocate new memory for the X values,
they can remain with the old "edgelist" structure.  We do have to
update that old structure so it is not as high:
*/
               list->ymax = y;
/*
Insert 'r' in the subpath chain:
*/
               r->subpath = list->subpath;
               list->subpath = r;
/*
Now attach 'r' to the list we are building at 'new', and advance
'list' to point to the next element in the old list:
*/
               if (new == NULL)
                       new = r;
               else
                       last->link = r;
               last = r;
               lastlist = list;
               list = list->link;
       }
/*
At this point we have a new list built at 'new'.  We break the old
list at 'lastlist', and add the broken off part to the end of 'new'.
Then, we return the caller a pointer to 'new':
*/
       if (new == NULL)
               abort("null splitedge", 35);
       lastlist->link = NULL;
       last->link = list;
       IfTrace1((RegionDebug > 1),"yields %p\n", new);
       return(new);
}
 
/*
:h3.vertjoin() - Join Two Disjoint Edge Lists Vertically
 
The two edges must be disjoint vertically.
*/
static int vertjoin(top, bottom)
       register struct edgelist *top;  /* uppermost region                   */
       register struct edgelist *bottom;  /* bottommost region               */
{
       if (BOTTOM(top) > TOP(bottom))
               abort("vertjoin not disjoint", 36);
 
       for (; top->link != NULL; top=top->link) { ; }
 
       top->link = bottom;
       return(0);
}
 
/*
:h3.swathxsort() - Sorting by X Values
 
We need to sort 'edge' into its rightful
place in the swath by X value, taking care that we do not accidentally
advance to the next swath while searching for the correct X value.  Like
all swath functions, this function returns a pointer to the edge
BEFORE the given edge in the sort.
*/
 
struct edgelist *swathxsort(before0, edge)
       register struct edgelist *before0;  /* edge before this swath         */
       register struct edgelist *edge;  /* input edge                        */
{
       register struct edgelist *before;
       register struct edgelist *after;
       register pel y=0;
 
       before = before0;
       after = before->link;
 
       while (after != NULL && TOP(after) == TOP(edge)) {
 
               register pel *x1,*x2;
 
               y = TOP(edge);
               x1 = after->xvalues;
               x2 = edge->xvalues;
 
               while (y < BOTTOM(edge) && *x1 == *x2) {
                       x1++; x2++; y++;
               }
               if (y >= BOTTOM(edge)) {
                       edge->flag |= ISAMBIGUOUS(ON);
                       after->flag |= ISAMBIGUOUS(ON);
                       break;
               }
 
               if (*x1 >= *x2)
                       break;
 
               before = after;
               after = after->link;
       }
 
/*
At this point, 'edge' is between 'before' and 'after'.  If 'edge' didn't
cross either of those other edges, we would be done.  We check for
crossing.  If it does cross, we split the problem up by calling SortSwath
recursively with the part of the edge that is below the crossing point:
*/
{
       register int h0,h;    /* height of edge--number of scans              */
 
       h0 = h = BOTTOM(edge) - y;
       y -= TOP(edge);
 
       if (h0 <= 0) {
               IfTrace0((RegionDebug>0),"swathxsort: exactly equal edges\n");
               return(before);
       }
 
       if (TOP(before) == TOP(edge))