regions.c

source code: Covert TXT to PDF

               h -= crosses(h, &before->xvalues[y], &edge->xvalues[y]);
       if (after != NULL && TOP(after) == TOP(edge))
               h -= crosses(h, &edge->xvalues[y], &after->xvalues[y]);
 
       if (h < h0) {
               SortSwath(before0->link,
                         splitedge(edge, TOP(edge) + y + h),
                         swathxsort);
 
       }
}
 
       return(before);
}
/*
:h3.SwathUnion() - Union Two Edges by X Value
 
We have a left and right edge that must be unioned into a growing
swath.  If they are totally disjoint, they are just added in.  The
fun comes in they overlap the existing edges.  Then some edges
will disappear.
*/
 
struct edgelist *SwathUnion(before0, edge)
       register struct edgelist *before0;  /* edge before the swath          */
       register struct edgelist *edge;  /* list of two edges to be unioned   */
{
       register int h;       /* saves height of edge                         */
       register struct edgelist *rightedge;  /* saves right edge of 'edge'   */
       register struct edgelist *before,*after;  /* edge before and after    */
       int h0;               /* saves initial height                         */
 
       IfTrace2((RegionDebug > 1),"SwathUnion entered, before=%p, edge=%p\n",
                      before0, edge);
 
       h0 = h = edge->ymax - edge->ymin;
       if (h <= 0)
               abort("SwathUnion:  0 height swath?", 37);
 
       before = before0;
       after = before->link;
 
       while (after != NULL && TOP(after) == TOP(edge)) {
               register struct edgelist *right;
 
               right = after->link;
               if (right->xvalues[0] >= edge->xvalues[0])
                       break;
               before = right;
               after = before->link;
       }
/*
This is the picture at this point.  'L' indicates a left hand edge,
'R' indicates the right hand edge.
'<--->' indicates the degree of uncertainty as to its placement
relative to other edges:
:xmp atomic.
   before           after
     R            <---L---->  R             L   R    L   R
              <---L--->  <------R-------------------------->
                 edge
:exmp.
In case the left of 'edge' touches 'before', we need to reduce
the height by that amount.
*/
       if (TOP(before) == TOP(edge))
               h -= touches(h, before->xvalues, edge->xvalues);
 
       rightedge = edge->link;
 
       if (after == NULL || TOP(after) != TOP(edge) ||
                   after->xvalues[0] > rightedge->xvalues[0]) {
              IfTrace2((RegionDebug > 1),
                       "SwathUnion starts disjoint: before=%p after=%p\n",
                                     before, after);
/*
On this side of the the above 'if', the new edge is disjoint from the
existing edges in the swath.  This is the picture:
:xmp atomic.
   before           after
     R                L    R     L   R    L   R
              L    R
             edge
:exmp.
We will verify it remains disjoint for the entire height.  If the
situation changes somewhere down the edge, we split the edge at that
point and recursively call ourselves (through 'SortSwath') to figure
out the new situation:
*/
               if (after != NULL && TOP(after) == TOP(edge))
                       h -= touches(h, rightedge->xvalues, after->xvalues);
               if (h < h0)
                       SortSwath(before0->link, splitedge(edge, edge->ymin + h), t1_SwathUnion);
               /* go to "return" this edge pair; it is totally disjoint */
       }
       else {
/*
At this point, at the 'else', we know that the
new edge overlaps one or more pairs in the existing swath.  Here is
a picture of our knowledge and uncertainties:
:xmp atomic.
   before       after
     R            L        R     L   R    L   R
            <---L--->   <---R------------------->
               edge
:exmp.
We need to move 'after' along until it is to the right of the
right of 'edge'.  ('After' should always point to a left edge of a pair:)
*/
               register struct edgelist *left;  /* variable to keep left edge in */
 
               do {
                        left = after;
                        after = (after->link)->link;
 
               } while  (after != NULL && TOP(after) == TOP(edge)
                               && after->xvalues[0] <= rightedge->xvalues[0]);
/*
At this point this is the picture:
:xmp atomic.
   before                 left        after
     R            L    R   L      R     L   R
            <---L--->        <---R--->
               edge
:exmp.
We need to verify that the situation stays like this all the way
down the edge.  Again, if the
situation changes somewhere down the edge, we split the edge at that
point and recursively call ourselves (through 'SortSwath') to figure
out the new situation:
*/
 
               h -= crosses(h, left->xvalues, rightedge->xvalues);
               h -= crosses(h, edge->xvalues, ((before->link)->link)->xvalues);
 
               if (after != NULL && TOP(after) == TOP(edge))
 
                       h -= touches(h, rightedge->xvalues, after->xvalues);
 
               IfTrace3((RegionDebug > 1),
                      "SwathUnion is overlapped until %d: before=%p after=%p\n",
                                          (LONG) TOP(edge) + h, before, after);
/*
OK, if we touched either of our neighbors we need to split at that point
and recursively sort the split edge onto the list.  One tricky part
is that when we recursively sort, 'after' will change if it was not
in our current swath:
*/
               if (h < h0) {
                       SortSwath(before0->link,
                                 splitedge(edge, edge->ymin + h),
                                 t1_SwathUnion);
 
                       if (after == NULL || TOP(after) != TOP(edge))
                                 for (after = before0->link;
                                      TOP(after) == TOP(edge);
                                      after = after->link) { ; }
               }
/*
Now we need to augment 'edge' by the left and right of the overlapped
swath, and to discard all edges between before and after, because they
were overlapped and have been combined with the new incoming 'edge':
*/
               edge->xmin = TYPE1_MIN(edge->xmin, (before->link)->xmin);
               edge->xmax = TYPE1_MIN(edge->xmax, (before->link)->xmax);
               edgemin(h, edge->xvalues, (before->link)->xvalues);
               rightedge->xmin = TYPE1_MAX(rightedge->xmin, (left->link)->xmin);
               rightedge->xmax = TYPE1_MAX(rightedge->xmax, (left->link)->xmax);
               edgemax(h, rightedge->xvalues, (left->link)->xvalues);
               discard(before, after);
       }
       return(before);
}
/*
:h3.swathrightmost() - Simply Sorts New Edge to Rightmost of Swath
 
Like all swath functions, this function returns a pointer to the edge
BEFORE the given edge in the sort.
*/
 
struct edgelist *swathrightmost(before, edge)
       register struct edgelist *before;  /* edge before this swath         */
       register struct edgelist *edge;  /* input edge                        */
{
       register struct edgelist *after;
 
       after = before->link;
 
       while (after != NULL && TOP(after) == TOP(edge)) {
               before = after;
               after = after->link;
       }
 
       return(before);
 
}
/*
:h3.touches() - Returns the Remaining Height When Two Edges Touch
 
So, it will return 0 if they never touch.  Allows incredibly(?) mnemonic
if (touches(...)) construct.
*/
 
static int touches(h, left, right)
       register int h;
       register pel *left,*right;
{
       for (; h > 0; h--)
               if (*left++ >= *right++)
                       break;
       return(h);
}
/*
:h3.crosses() - Returns the Remaining Height When Two Edges Cross
 
So, it will return 0 if they never cross.
*/
 
static int crosses(h, left, right)
       register int h;
       register pel *left,*right;
{
       for (; h > 0; h--)
               if (*left++ > *right++)
                       break;
       return(h);
}
/*
:h3.cedgemin() - Stores the Mininum of an Edge and an X Value
*/
 
static int cedgemin(h, e1, x)
       register int h;
       register pel *e1;
       register pel x;
{
       for (; --h >= 0; e1++)
               if (*e1 > x)
                       *e1 = x;
       return(0);
       
}
/*
:h3.cedgemax() - Stores the Maximum of an Edge and an X Value
*/
 
static int cedgemax(h, e1, x)
       register int h;
       register pel *e1;
       register pel x;
{
       for (; --h >= 0; e1++)
               if (*e1 < x)
                       *e1 = x;
       return(0);
       
}
/*
:h3.edgemin() - Stores the Mininum of Two Edges in First Edge
*/
 
static int edgemin(h, e1, e2)
       register int h;
       register pel *e1,*e2;
{
       for (; --h >= 0; e1++,e2++)
               if (*e1 > *e2)
                       *e1 = *e2;
       return(0);
       
}
/*
:h3.edgemax() - Stores the Maximum of Two Edges in First Edge
*/
 
static int edgemax(h, e1, e2)
       register int h;
       register pel *e1,*e2;
{
       for (; --h >= 0; e1++,e2++)
               if (*e1 < *e2)
                       *e1 = *e2;
       return(0);
       
}
/*
:h3 id=discard.discard() - Discard All Edges Between Two Edges
 
At first glance it would seem that we could discard an edgelist
structure merely by unlinking it from the list and freeing it.  You are
wrong, region-breath!  For performance, the X values associated with an
edge are allocated contiguously with it.  So, we free the X values when
we free a structure.  However, once an edge has been split, we are no
longer sure which control block actually is part of the memory block
that contains the edges.  Rather than trying to decide, we play it safe
and never free part of a region.
 
So, to mark a 'edgelist' structure as discarded, we move it to the end
of the list and set ymin=ymax.
*/
 
static int discard(left, right)
       register struct edgelist *left,*right;  /* all edges between here exclusive */
                                       /* should be discarded */
{
       register struct edgelist *beg,*end,*p;
 
       IfTrace2((RegionDebug > 0),"discard:  l=%p, r=%p\n", left, right);
 
       beg = left->link;
       if (beg == right)
               return(0);
 
       for (p = beg; p != right; p = p->link) {
               if (p->link == NULL && right != NULL)
                       abort("discard():  ran off end", 38);
               IfTrace1((RegionDebug > 0),"discarding %p\n", p);
               p->ymin = p->ymax = 32767;
               end = p;
       }
       /*
       * now put the chain beg/end at the end of right, if it is not
       * already there:
       */
       if (right != NULL) {
               left->link = right;
               while (right->link != NULL)
                       right = right->link;
               right->link = beg;
       }
       end->link = NULL;
       return(0);
       
}
 
/*
:h2.Changing the Representation of Regions
 
For convenience and/or performance, we sometimes like to change the way
regions are represented.  This does not change the object itself, just
the representation, so these transformations can be made on a permanent
region.
 
*/
 
void MoveEdges(R, dx, dy)
       register struct region *R; /* region to modify                        */
       register fractpel dx,dy;  /* delta X and Y to move edge list by       */
{
       register struct edgelist *edge;  /* for looping through edges         */
 
       R->origin.x += dx;
       R->origin.y += dy;
       R->ending.x += dx;
       R->ending.y += dy;
       if (R->thresholded != NULL) {
               R->thresholded->origin.x -= dx;