--- /dev/null
+/* $XConsortium: regions.c,v 1.6 94/02/06 16:22:21 gildea Exp $ */
+/* $XFree86: xc/lib/font/Type1/regions.c,v 3.0 1996/08/25 13:58:26 dawes Exp $ */
+/* Copyright International Business Machines, Corp. 1991
+ * All Rights Reserved
+ * Copyright Lexmark International, Inc. 1991
+ * All Rights Reserved
+ *
+ * License to use, copy, modify, and distribute this software and its
+ * documentation for any purpose and without fee is hereby granted,
+ * provided that the above copyright notice appear in all copies and that
+ * both that copyright notice and this permission notice appear in
+ * supporting documentation, and that the name of IBM or Lexmark not be
+ * used in advertising or publicity pertaining to distribution of the
+ * software without specific, written prior permission.
+ *
+ * IBM AND LEXMARK PROVIDE THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES OF
+ * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO ANY
+ * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
+ * AND NONINFRINGEMENT OF THIRD PARTY RIGHTS. THE ENTIRE RISK AS TO THE
+ * QUALITY AND PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT
+ * OR MAINTAIN, BELONGS TO THE LICENSEE. SHOULD ANY PORTION OF THE
+ * SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM OR LEXMARK) ASSUMES THE
+ * ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION. IN NO EVENT SHALL
+ * IBM OR LEXMARK BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
+ * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
+ * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
+ * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
+ * THIS SOFTWARE.
+ */
+ /* REGIONS CWEB V0023 LOTS */
+/*
+:h1 id=regions.REGIONS Module - Regions Operator Handler
+
+This module is responsible for creating and manipulating regions.
+
+&author. Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com)
+
+
+:h3.Include Files
+
+The included files are:
+*/
+
+#include "objects.h"
+#include "spaces.h"
+#include "regions.h"
+#include "paths.h"
+#include "curves.h"
+#include "lines.h"
+#include "pictures.h"
+#include "fonts.h"
+#include "hints.h"
+#include "strokes.h" /* to pick up 'DoStroke' */
+static Unwind();
+static void newfilledge();
+static struct edgelist *splitedge();
+static void vertjoin();
+static int touches();
+static int crosses();
+static void edgemin();
+static void edgemax();
+static discard();
+static edgecheck();
+static struct edgelist *NewEdge();
+static struct edgelist *swathxsort(); /* 'SortSwath' function */
+
+/*
+:h3.Functions Provided to the TYPE1IMAGER User
+
+This module provides the following TYPE1IMAGER entry points:
+*/
+
+/*SHARED LINE(S) ORIGINATED HERE*/
+/*
+:h3.Functions Provided to Other Modules
+
+This module provides the following entry points to other modules:
+*/
+
+/*SHARED LINE(S) ORIGINATED HERE*/
+/*
+:h3.Macros Provided to Other Modules
+
+:h4.GOING_TO() - Macro Predicate Needed for Changing Direction, Etc.
+
+The actual generation of run end lists (edge boundaries) is left
+to the low level rasterizing modules, LINES and CURVES. There
+are some global region-type
+questions that occur when doing a low-level
+rasterization:
+:ol.
+:li.Did we just change direction in Y and therefore need to start
+a new edge?
+:li.Did we run out of allocated edge space?
+:li.Do the minimum or maximum X values for the current edge need
+updating?
+:eol.
+In general the REGIONS is not smart enough to answer those questions
+itself. (For example, determining if and when a curve changes direction
+may need detailed curve knowledge.) Yet, this must be done efficiently.
+We provide a macro "GOING_TO" where the invoker tells us where it is
+heading for (x2,y2), plus where it is now (x1,y1), plus the current
+region under construction, and the macro answers the questions above.
+*/
+
+/*SHARED LINE(S) ORIGINATED HERE*/
+/*
+:h2.Data Structures Used to Represent Regions
+
+:h3.The "region" Structure
+
+The region structure is an anchor for a linked list of "edgelist"
+structures (see :hdref refid=edgelist..). It also summarizes the
+information in the edgelist structures (for example, the bounding
+box of the region). And, it contains scratch areas used during
+the creation of a region.
+*/
+
+/*SHARED LINE(S) ORIGINATED HERE*/
+/*
+The ISOPTIMIZED flag tells us if we've put a permanent region in
+'optimal' form.
+*/
+#define ISOPTIMIZED(flag) ((flag)&0x10)
+
+/*
+The ISRECTANGULAR flag tells us if a region is a rectangle. We don't
+always notice rectangles--if this flag is set, the region definitely
+is a rectangle, but some rectangular regions will not have the flag
+set. The flag is used to optimize some paths.
+*/
+
+/*SHARED LINE(S) ORIGINATED HERE*/
+/*
+:h4."INFINITY" - A Constant Region Structure of Infinite Extent
+
+Infinity is the complement of a null area:
+Note - removed the refcount = 1 init, replaced with references = 2 3-26-91 PNM
+*/
+static struct region infinity = { REGIONTYPE,
+ ISCOMPLEMENT(ON)+ISINFINITE(ON)+ISPERMANENT(ON)+ISIMMORTAL(ON), 2,
+ 0, 0, 0, 0,
+ 0, 0, 0, 0,
+ NULL, NULL,
+ 0, 0, 0, 0, 0, NULL, NULL,
+ NULL, 0, NULL, NULL };
+struct region *INFINITY = &infinity;
+
+/*
+:h4."EmptyRegion" - A Region Structure with Zero Area
+
+This structure is used to initialize the region to be built in
+Interior():
+Note - replaced refcount = 1 init with references = 2 3-26-91 PNM
+*/
+
+/*SHARED LINE(S) ORIGINATED HERE*/
+struct region EmptyRegion = { REGIONTYPE,
+ ISPERMANENT(ON)+ISIMMORTAL(ON), 2,
+ 0, 0, 0, 0,
+ MAXPEL, MAXPEL, MINPEL, MINPEL,
+ NULL, NULL,
+ 0, 0, 0, 0, 0, NULL, NULL,
+ NULL, 0, NULL, NULL };
+
+/*
+:h3 id=edgelist.The "edgelist" Structure
+
+Regions are represented by a linked list of 'edgelist' structures.
+When a region is complete, the structures are paired, one for the
+left and one for the right edge. While a region is being built,
+this rule may be violated temporarily.
+
+An 'edgelist' structure contains the X values for a given span
+of Y values. The (X,Y) pairs define an edge. We use the crack
+and edge coordinate system, so that integer values of X and Y
+go between pels. The edge is defined between the minimum Y and
+maximum Y.
+
+The linked list is kept sorted from top to bottom, that is, in
+increasing y. Also, if 'e1' is an edgelist structure and 'e2' is the
+next one in the list, they must have exactly the same ymin,ymax values
+or be totally disjoint. These two requirements mean that if e2's ymin
+is less than e1's ymax, it must be exactly equal to e1's ymin. A
+sublist of structures with identical ymin and ymax values is called a
+'swath'.
+
+In addition, edgelist structures are separately linked together based
+on what subpath originally created them; each subpath is kept as a
+separate circular linked list. This information is ignored unless
+continuity checking is invoked. See :hdref refid=subpath. for a
+complete description of this.
+*/
+
+
+/*SHARED LINE(S) ORIGINATED HERE*/
+
+/*
+The "edgelist" structure follows the convention of TYPE1IMAGER user
+objects, having a type field and a flag field as the first two
+elements. However, the user never sees "edgelist" structures
+directly; he is given handles to "region" structures only.
+
+By having a type field, we can use the "copy" feature of Allocate()
+to duplicate edge lists quickly.
+
+We also define two flag bits for this structure. The ISDOWN bit is set
+if the edge is going in the direction of increasing Y. The ISAMBIGUOUS
+bit is set if the edge is identical to its neighbor (edge->link); such
+edges may be "left" when they should be "right", or vice versa,
+unnecessarily confusing the continuity checking logic. The FixSubPaths()
+routine in HINTS will swap ambiguous edges if that avoids crossing edges;
+see :hdref refid=fixsubp..
+*/
+
+/*SHARED LINE(S) ORIGINATED HERE*/
+
+/*
+:h3.KillRegion() - Destroys a Region
+
+KillRegion nominally just decrements the reference count to that region.
+If the reference count becomes 0, all memory associated with it is
+freed. We just follow the linked list, freeing as we go, then kill any
+associated (thresholded) picture.
+Note - added conditional return based on references 3-26-91 PNM
+*/
+
+void KillRegion(area)
+ register struct region *area; /* area to free */
+{
+ register struct edgelist *p; /* loop variable */
+ register struct edgelist *next; /* loop variable */
+
+ if (area->references < 0)
+ abort("KillRegion: negative reference count");
+ if ( (--(area->references) > 1) ||
+ ( (area->references == 1) && !ISPERMANENT(area->flag) ) )
+ return;
+
+ for (p=area->anchor; p != NULL; p=next) {
+ next = p->link;
+ Free(p);
+ }
+ if (area->thresholded != NULL)
+ KillPicture(area->thresholded);
+ Free(area);
+}
+/*
+:h3.CopyRegion() - Makes a Copy of a Region
+*/
+struct region *CopyRegion(area)
+ register struct region *area; /* region to duplicate */
+{
+ register struct region *r; /* output region built here */
+ register struct edgelist *last; /* loop variable */
+ register struct edgelist *p,*newp; /* loop variables */
+
+ r = (struct region *)Allocate(sizeof(struct region), area, 0);
+ r->anchor = NULL;
+
+ for (p=area->anchor; VALIDEDGE(p); p=p->link) {
+
+ newp = NewEdge(p->xmin, p->xmax, p->ymin, p->ymax, p->xvalues, ISDOWN(p->flag));
+ if (r->anchor == NULL)
+ r->anchor = last = newp;
+ else
+ last->link = newp;
+
+ last = newp;
+ }
+ if (area->thresholded != NULL)
+ /* replaced DupPicture with Dup() 3-26-91 PNM */
+ r->thresholded = (struct picture *)Dup(area->thresholded);
+ return(r);
+}
+/*
+:h4.NewEdge() - Allocates and Returns a New "edgelist" Structure
+
+We allocate space for the X values contiguously with the 'edgelist'
+structure that locates them. That way, we only have to free the
+edgelist structure to free all memory associated with it. Damn
+clever, huh?
+*/
+
+static struct edgelist *NewEdge(xmin, xmax, ymin, ymax, xvalues, isdown)
+ pel xmin,xmax; /* X extent of edge */
+ pel ymin,ymax; /* Y extent of edge */
+ pel *xvalues; /* list of X values for entire edge */
+ int isdown; /* flag: TRUE means edge progresses downward */
+{
+ static struct edgelist template = {
+ EDGETYPE, 0, 1, NULL, NULL,
+ 0, 0, 0, 0, NULL };
+
+ register struct edgelist *r; /* returned structure */
+ register int iy; /* ymin adjusted for 'long' alignment purposes */
+
+ IfTrace2((RegionDebug),"....new edge: ymin=%d, ymax=%d ",
+ (long)ymin, (long) ymax);
+ if (ymin >= ymax)
+ abort("newedge: height not positive");
+/*
+We are going to copy the xvalues into a newly allocated area. It
+helps performance if the values are all "long" aligned. We can test
+if the xvalues are long aligned by ANDing the address with the
+(sizeof(long) - 1)--if non zero, the xvalues are not aligned well. We
+set 'iy' to the ymin value that would give us good alignment:
+*/
+ iy = ymin - (((unsigned long)xvalues) & (sizeof(long)-1)) / sizeof(pel);
+
+ r = (struct edgelist *)Allocate(sizeof(struct edgelist), &template,
+ (ymax - iy) * sizeof(pel));
+
+ if (isdown) r->flag = ISDOWN(ON);
+ r->xmin = xmin;
+ r->xmax = xmax;
+ r->ymin = ymin;
+ r->ymax = ymax;
+
+ r->xvalues = (pel *) FOLLOWING(r);
+ if (ymin != iy) {
+ r->xvalues += ymin - iy;
+ xvalues -= ymin - iy;
+ }
+
+/*
+We must round up (ymax - iy) so we get the ceiling of the number of
+longs. The destination must be able to hold these extra bytes because
+Allocate() makes everything it allocates be in multiples of longs.
+*/
+ LONGCOPY(&r[1], xvalues, (ymax - iy) * sizeof(pel) + sizeof(long) - 1);
+
+ IfTrace1((RegionDebug),"result=%x\n", r);
+ return(r);
+}
+
+/*
+:h2.Building Regions
+
+:h3.Interior() - Iterate Through a Path, Building a Region
+
+This routine is the workhorse driver routine that iterates through a
+path, calling the appropriate stepping routines to actually produce the
+run end "edgelist" structures.
+
+:ol.
+:li."Interior" calls StepLine or StepConic or StepBezier as appropriate
+to produce run ends.
+:li.Occasionally these routines will notice a change in Y direction
+and will call ChangeDirection (through the GOING_TO macro); this is
+a call back to the REGIONS module.
+:li.ChangeDirection will call whatever function is in the region
+structure; for Interior, this function is 'newfilledge'.
+:li.Newfilledge will call NewEdge to create a new edgelist structure,
+then, call SortSwath to sort it onto the linked list being built at
+the region "anchor".
+:eol.
+
+By making the function called by ChangeDirection be a parameter of the
+region, we allow the same ChangeDirection logic to be used by stroking.
+*/
+
+/*SHARED LINE(S) ORIGINATED HERE*/
+
+struct region *Interior(p, fillrule)
+ register struct segment *p; /* take interior of this path */
+ register int fillrule; /* rule to follow if path crosses itself */
+{
+ register fractpel x,y; /* keeps ending point of path segment */
+ fractpel lastx,lasty; /* previous x,y from path segment before */
+ register struct region *R; /* region I will build */
+ register struct segment *nextP; /* next segment of path */
+ struct fractpoint hint; /* accumulated hint value */
+ char tempflag; /* flag; is path temporary? */
+ char Cflag; /* flag; should we apply continuity? */
+
+ IfTrace2((MustTraceCalls),". INTERIOR(%z, %d)\n", p, (long) fillrule);
+
+ if (p == NULL)
+ return(NULL);
+/*
+Establish the 'Cflag' continuity flag based on user's fill rule and
+our own 'Continuity' pragmatic (0: never do continuity, 1: do what
+user asked, >1: do it regardless).
+*/
+ if (fillrule > 0) {
+ Cflag = Continuity > 0;
+ fillrule -= CONTINUITY;
+ }
+ else
+ Cflag = Continuity > 1;
+
+ ARGCHECK((fillrule != WINDINGRULE && fillrule != EVENODDRULE),
+ "Interior: bad fill rule", NULL, NULL, (1,p), struct region *);
+
+ if (p->type == TEXTTYPE)
+/* if (fillrule != EVENODDRULE)
+ else */
+ return((struct region *)UniquePath(p));
+ if (p->type == STROKEPATHTYPE)
+ if (fillrule == WINDINGRULE)
+ return((struct region *)DoStroke(p));
+ else
+ p = CoercePath(p);
+
+ R = (struct region *)Allocate(sizeof(struct region), &EmptyRegion, 0);
+
+ ARGCHECK(!ISPATHANCHOR(p), "Interior: bad path", p, R, (0), struct region *);
+ ARGCHECK((p->type != MOVETYPE), "Interior: path not closed", p, R, (0), struct region *);
+
+
+/* changed definition from !ISPERMANENT to references <= 1 3-26-91 PNM */
+ tempflag = (p->references <= 1); /* only first segment in path is so marked */
+ if (!ISPERMANENT(p->flag)) p->references -= 1;
+
+ R->newedgefcn = newfilledge;
+/*
+Believe it or not, "R" is now completely initialized. We are counting
+on the copy of template to get other fields the way we want them,
+namely
+:ol.
+:li.anchor = NULL
+:li.xmin, ymin, xmax, ymax, to minimum and maximum values respectively.
+:eol.
+Anchor = NULL is very
+important to ChangeDirection.
+See :hdref refid=CD..
+
+To minimize problems of "wrapping" in our pel arithmetic, we keep an
+origin of the region which is the first move. Hopefully, that keeps
+numbers within plus or minus 32K pels.
+*/
+ R->origin.x = 0/*TOFRACTPEL(NEARESTPEL(p->dest.x))*/;
+ R->origin.y = 0/*TOFRACTPEL(NEARESTPEL(p->dest.y))*/;
+ lastx = - R->origin.x;
+ lasty = - R->origin.y;
+/*
+ChangeDirection initializes other important fields in R, such as
+lastdy, edge, edgeYstop, edgexmin, and edgexmax. The first segment
+is a MOVETYPE, so it will be called first.
+*/
+/*
+The hints data structure must be initialized once for each path.
+*/
+
+ if (ProcessHints)
+ InitHints(); /* initialize hint data structure */
+
+ while (p != NULL) {
+
+ x = lastx + p->dest.x;
+ y = lasty + p->dest.y;
+
+ IfTrace2((HintDebug > 0),"Ending point = (%p,%p)\n", x, y);
+
+ nextP = p->link;
+
+/*
+Here we start the hints processing by initializing the hint value to
+zero. If ProcessHints is FALSE, the value will remain zero.
+Otherwise, hint accumulates the computed hint values.
+*/
+
+ hint.x = hint.y = 0;
+
+/*
+If we are processing hints, and this is a MOVE segment (other than
+the first on the path), we need to close (reverse) any open hints.
+*/
+
+ if (ProcessHints)
+ if ((p->type == MOVETYPE) && (p->last == NULL)) {
+ CloseHints(&hint);
+ IfTrace2((HintDebug>0),"Closed point= (%p,%p)\n",
+ x+hint.x, y+hint.y);
+ }
+
+/*
+Next we run through all the hint segments (if any) attached to this
+segment. If ProcessHints is TRUE, we will accumulate computed hint
+values. In either case, nextP will be advanced to the first non-HINT
+segment (or NULL), and each hint segment will be freed if necessary.
+*/
+
+ while ((nextP != NULL) && (nextP->type == HINTTYPE)) {
+ if (ProcessHints)
+ ProcessHint(nextP, x + hint.x, y + hint.y, &hint);
+
+ {
+ register struct segment *saveP = nextP;
+
+ nextP = nextP->link;
+ if (tempflag)
+ Free(saveP);
+ }
+ }
+
+/*
+We now apply the full hint value to the ending point of the path segment.
+*/
+
+ x += hint.x;
+ y += hint.y;
+
+ IfTrace2((HintDebug>0),"Hinted ending point = (%p,%p)\n", x, y);
+
+ switch(p->type) {
+
+ case LINETYPE:
+ StepLine(R, lastx, lasty, x, y);
+ break;
+
+ case CONICTYPE:
+ {
+
+/*
+For a conic curve, we apply half the hint value to the conic midpoint.
+*/
+
+ }
+ break;
+
+ case BEZIERTYPE:
+ {
+ register struct beziersegment *bp = (struct beziersegment *) p;
+
+/*
+For a Bezier curve, we apply the full hint value to the Bezier C point.
+*/
+
+ StepBezier(R, lastx, lasty,
+ lastx + bp->B.x, lasty + bp->B.y,
+ lastx + bp->C.x + hint.x,
+ lasty + bp->C.y + hint.y,
+ x, y);
+ }
+ break;
+
+ case MOVETYPE:
+/*
+At this point we have encountered a MOVE segment. This breaks the
+path, making it disjoint.
+*/
+ if (p->last == NULL) /* i.e., not first in path */
+ ChangeDirection(CD_LAST, R, lastx, lasty, (fractpel) 0);
+
+ ChangeDirection(CD_FIRST, R, x, y, (fractpel) 0);
+/*
+We'll just double check for closure here. We forgive an appended
+MOVETYPE at the end of the path, if it isn't closed:
+*/
+ if (!ISCLOSED(p->flag) && p->link != NULL)
+ return((struct region *)ArgErr("Fill: sub-path not closed", p, NULL));
+ break;
+
+ default:
+ abort("Interior: path type error");
+ }
+/*
+We're done with this segment. Advance to the next path segment in
+the list, freeing this one if necessary:
+*/
+ lastx = x; lasty = y;
+
+ if (tempflag)
+ Free(p);
+ p = nextP;
+ }
+ ChangeDirection(CD_LAST, R, lastx, lasty, (fractpel) 0);
+ R->ending.x = lastx;
+ R->ending.y = lasty;
+/*
+Finally, clean up the region's based on the user's 'fillrule' request:
+*/
+ if (Cflag)
+ ApplyContinuity(R);
+ if (fillrule == WINDINGRULE)
+ Unwind(R->anchor);
+ return(R);
+}
+/*
+:h4.Unwind() - Discards Edges That Fail the Winding Rule Test
+
+The winding rule says that upward going edges should be paired with
+downward going edges only, and vice versa. So, if two upward edges
+or two downward edges are nominally left/right pairs, Unwind() should
+discard the second one. Everything should balance; we should discard
+an even number of edges; of course, we abort if we don't.
+*/
+static Unwind(area)
+ register struct edgelist *area; /* input area modified in place */
+{
+ register struct edgelist *last,*next; /* struct before and after current one */
+ register int y; /* ymin of current swath */
+ register int count,newcount; /* winding count registers */
+
+ IfTrace1((RegionDebug>0),"...Unwind(%z)\n", area);
+
+ while (VALIDEDGE(area)) {
+
+ count = 0;
+ y = area->ymin;
+
+ do {
+ next = area->link;
+
+ if (ISDOWN(area->flag))
+ newcount = count + 1;
+ else
+ newcount = count - 1;
+
+ if (count == 0 || newcount == 0)
+ last = area;
+ else
+ discard(last, next);
+
+ count = newcount;
+ area = next;
+
+ } while (area != NULL && area->ymin == y);
+
+ if (count != 0)
+ abort("Unwind: uneven edges");
+ }
+}
+/*
+:h3."workedge" Array
+
+This is a statically allocated array where edges are built
+before being copied into more permanent storage by NewEdge().
+*/
+
+#ifndef MAXEDGE
+#define MAXEDGE 1000
+#endif
+
+static pel workedge[MAXEDGE];
+static pel *currentworkarea = workedge;
+static pel currentsize = MAXEDGE;
+
+/*
+:h3 id=cd.ChangeDirection() - Called When Y Direction Changes
+
+The rasterizing routines call this entry point when they detect
+a change in Y. We then build the current edge and sort it into
+emerging edgelist at 'anchor' by calling whatever "newedgefcn"
+is appropriate.
+*/
+
+void ChangeDirection(type, R, x, y, dy)
+ int type; /* CD_FIRST, CD_CONTINUE, or CD_LAST */
+ register struct region *R; /* region in which we are changing direction */
+ fractpel x,y; /* current beginning x,y */
+ fractpel dy; /* direction and magnitude of change in y */
+{
+ register fractpel ymin,ymax; /* minimum and maximum Y since last call */
+ register fractpel x_at_ymin,x_at_ymax; /* their respective X's */
+ register pel iy; /* nearest integer pel to 'y' */
+ register pel idy; /* nearest integer pel to 'dy' */
+ register int ydiff; /* allowed Y difference in 'currentworkarea' */
+
+ IfTrace4((RegionDebug>0),"Change Y direction (%d) from (%p,%p), dy=%p\n",
+ (long) type, x, y, dy);
+
+ if (type != CD_FIRST) {
+
+ if (R->lastdy > 0) {
+ ymin = R->firsty;
+ x_at_ymin = R->firstx;
+ ymax = y;
+ x_at_ymax = x;
+ }
+ else {
+ ymin = y;
+ x_at_ymin = x;
+ ymax = R->firsty;
+ x_at_ymax = R->firstx;
+ }
+
+ if (ymax < ymin)
+ abort("negative sized edge?");
+
+
+ (*R->newedgefcn)(R, R->edgexmin, R->edgexmax, ymin, ymax,
+ R->lastdy > 0, x_at_ymin, x_at_ymax);
+
+ }
+
+ R->firsty = y;
+ R->firstx = x;
+ R->lastdy = dy;
+
+ iy = NEARESTPEL(y);
+ idy = NEARESTPEL(dy);
+ if (currentworkarea != workedge && idy < MAXEDGE && idy > -MAXEDGE) {
+ NonObjectFree(currentworkarea);
+ currentworkarea = workedge;
+ currentsize = MAXEDGE;
+ }
+ ydiff = currentsize - 1;
+ if (dy > 0) {
+ R->edge = ¤tworkarea[-iy];
+ R->edgeYstop = TOFRACTPEL(ydiff + iy) + FPHALF;
+ }
+ else {
+ R->edge = ¤tworkarea[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 void 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;
+
+ 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);
+
+}
+
+/*
+: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=%z, edge=%z, fcn=%x)\n",
+ anchor, edge, swathfcn);
+ }
+ else {
+ IfTrace3(TRUE,"SortSwath(anchor=%x, edge=%x, fcn=%x)\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 %x and %x are %x",
+ before, after, edge);
+ while (edge->link != NULL) {
+ edge = edge->link;
+ IfTrace1(TRUE," and %x", 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; /* 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 %x 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");
+ if (y == list->ymin)
+ abort("splitedge: would be null");
+
+ 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");
+ lastlist->link = NULL;
+ last->link = list;
+ IfTrace1((RegionDebug > 1),"yields %x\n", new);
+ return(new);
+}
+
+/*
+:h3.vertjoin() - Join Two Disjoint Edge Lists Vertically
+
+The two edges must be disjoint vertically.
+*/
+static void vertjoin(top, bottom)
+ register struct edgelist *top; /* uppermost region */
+ register struct edgelist *bottom; /* bottommost region */
+{
+ if (BOTTOM(top) > TOP(bottom))
+ abort("vertjoin not disjoint");
+
+ for (; top->link != NULL; top=top->link) { ; }
+
+ top->link = bottom;
+ return;
+}
+
+/*
+: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.
+*/
+
+static 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;
+
+ 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))
+ 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=%x, edge=%x\n",
+ before0, edge);
+
+ h0 = h = edge->ymax - edge->ymin;
+ if (h <= 0)
+ abort("SwathUnion: 0 height swath?");
+
+ 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=%x after=%x\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=%x after=%x\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 = MIN(edge->xmin, (before->link)->xmin);
+ edge->xmax = MIN(edge->xmax, (before->link)->xmax);
+ edgemin(h, edge->xvalues, (before->link)->xvalues);
+ rightedge->xmin = MAX(rightedge->xmin, (left->link)->xmin);
+ rightedge->xmax = 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.
+*/
+
+static 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 void cedgemin(h, e1, x)
+ register int h;
+ register pel *e1;
+ register pel x;
+{
+ for (; --h >= 0; e1++)
+ if (*e1 > x)
+ *e1 = x;
+}
+/*
+:h3.cedgemax() - Stores the Maximum of an Edge and an X Value
+*/
+
+static void cedgemax(h, e1, x)
+ register int h;
+ register pel *e1;
+ register pel x;
+{
+ for (; --h >= 0; e1++)
+ if (*e1 < x)
+ *e1 = x;
+}
+/*
+:h3.edgemin() - Stores the Mininum of Two Edges in First Edge
+*/
+
+static void edgemin(h, e1, e2)
+ register int h;
+ register pel *e1,*e2;
+{
+ for (; --h >= 0; e1++,e2++)
+ if (*e1 > *e2)
+ *e1 = *e2;
+}
+/*
+:h3.edgemax() - Stores the Maximum of Two Edges in First Edge
+*/
+
+static void edgemax(h, e1, e2)
+ register int h;
+ register pel *e1,*e2;
+{
+ for (; --h >= 0; e1++,e2++)
+ if (*e1 < *e2)
+ *e1 = *e2;
+}
+/*
+: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 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=%x, r=%x\n", left, right);
+
+ beg = left->link;
+ if (beg == right)
+ return;
+
+ for (p = beg; p != right; p = p->link) {
+ if (p->link == NULL && right != NULL)
+ abort("discard(): ran off end");
+ IfTrace1((RegionDebug > 0),"discarding %x\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;
+}
+
+/*
+: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;
+ R->thresholded->origin.y -= dy;
+ }
+/*
+From now on we will deal with dx and dy as integer pel values:
+*/
+ dx = NEARESTPEL(dx);
+ dy = NEARESTPEL(dy);
+ if (dx == 0 && dy == 0)
+ return;
+
+ R->xmin += dx;
+ R->xmax += dx;
+ R->ymin += dy;
+ R->ymax += dy;
+
+ for (edge = R->anchor; VALIDEDGE(edge); edge = edge->link) {
+ edge->ymin += dy;
+ edge->ymax += dy;
+ if (dx != 0) {
+ register int h; /* loop index; height of edge */
+ register pel *Xp; /* loop pointer to X values */
+
+ edge->xmin += dx;
+ edge->xmax += dx;
+ for (Xp = edge->xvalues, h = edge->ymax - edge->ymin;
+ --h >= 0; )
+ *Xp++ += dx;
+ }
+ }
+}
+
+/*
+:h3.UnJumble() - Sort a Region Top to Bottom
+
+It is an open question whether it pays in general to do this.
+*/
+
+void UnJumble(region)
+ struct region *region; /* region to sort */
+{
+ register struct edgelist *anchor; /* new lists built here */
+ register struct edgelist *edge; /* edge pointer for loop */
+ register struct edgelist *next; /* ditto */
+
+ anchor = NULL;
+
+ for (edge=region->anchor; VALIDEDGE(edge); edge=next) {
+ if (edge->link == NULL)
+ abort("UnJumble: unpaired edge?");
+ next = edge->link->link;
+ edge->link->link = NULL;
+ anchor = SortSwath(anchor, edge, t1_SwathUnion);
+ }
+
+ if (edge != NULL)
+ vertjoin(anchor, edge);
+
+ region->anchor = anchor;
+ region->flag &= ~ISJUMBLED(ON);
+}
+
+/*
+*/
+
+static OptimizeRegion(R)
+ struct region *R; /* region to optimize */
+{
+ register pel *xP; /* pel pointer for inner loop */
+ register int x; /* holds X value */
+ register int xmin,xmax; /* holds X range */
+ register int h; /* loop counter */
+ register struct edgelist *e; /* edgelist pointer for loop */
+
+ R->flag |= ISRECTANGULAR(ON);
+
+ for (e = R->anchor; VALIDEDGE(e); e=e->link) {
+ xmin = MAXPEL;
+ xmax = MINPEL;
+ for (h = e->ymax - e->ymin, xP = e->xvalues; --h >= 0;) {
+ x = *xP++;
+ if (x < xmin) xmin = x;
+ if (x > xmax) xmax = x;
+ }
+ if (xmin != xmax || (xmin != R->xmin && xmax != R->xmax))
+ R->flag &= ~ISRECTANGULAR(ON);
+ if (xmin < e->xmin || xmax > e->xmax)
+ abort("Tighten: existing edge bound was bad");
+ if (xmin < R->xmin || xmax > R->xmax)
+ abort("Tighten: existing region bound was bad");
+ e->xmin = xmin;
+ e->xmax = xmax;
+ }
+ R->flag |= ISOPTIMIZED(ON);
+}
+
+/*
+:h2.Miscelaneous Routines
+
+:h3.MoreWorkArea() - Allocate New Space for "edge"
+
+Our strategy is to temporarily allocate an array to hold this
+unexpectedly large edge. ChangeDirection frees this array any time
+it gets a shorter 'dy'.
+*/
+
+/*ARGSUSED*/
+void MoreWorkArea(R, x1, y1, x2, y2)
+ struct region *R; /* region we are generating */
+ fractpel x1,y1; /* starting point of line */
+ fractpel x2,y2; /* ending point of line */
+{
+ register int idy; /* integer dy of line */
+
+ idy = NEARESTPEL(y1) - NEARESTPEL(y2);
+ if (idy < 0) idy = - idy;
+
+ /*
+ * we must add one to the delta for the number of run ends we
+ * need to store:
+ */
+ if (++idy > currentsize) {
+ IfTrace1((RegionDebug > 0),"Allocating edge of %d pels\n", idy);
+ if (currentworkarea != workedge)
+ NonObjectFree(currentworkarea);
+ currentworkarea = (pel *)Allocate(0, NULL, idy * sizeof(pel));
+ currentsize = idy;
+ }
+ ChangeDirection(CD_CONTINUE, R, x1, y1, y2 - y1);
+}
+
+/*
+:h3.BoxClip() - Clip a Region to a Rectangle
+
+BoxClip also duplicates the region if it is permanent. Note the
+clipping box is specified in REGION coordinates, that is, in
+coordinates relative to the region (0,0) point
+*/
+
+struct region *BoxClip(R, xmin, ymin, xmax, ymax)
+ register struct region *R; /* region to clip */
+ register pel xmin,ymin; /* upper left hand corner of rectangle */
+ register pel xmax,ymax; /* lower right hand corner */
+{
+ struct edgelist anchor; /* pretend edgelist to facilitate discards */
+ register struct edgelist *e,*laste;
+
+ IfTrace1((OffPageDebug),"BoxClip of %z:\n", R);
+
+ R = UniqueRegion(R);
+
+ if (xmin > R->xmin) {
+ IfTrace2((OffPageDebug),"BoxClip: left clip old %d new %d\n",
+ (long) R->xmin, (long) xmin);
+ R->xmin = xmin;
+ }
+ if (xmax < R->xmax) {
+ IfTrace2((OffPageDebug),"BoxClip: right clip old %d new %d\n",
+ (long) R->xmax, (long) xmax);
+ R->xmax = xmax;
+ }
+
+ if (ymin > R->ymin) {
+ IfTrace2((OffPageDebug),"BoxClip: top clip old %d new %d\n",
+ (long) R->ymin, (long) ymin);
+ R->ymin = ymin;
+ }
+ if (ymax < R->ymax) {
+ IfTrace2((OffPageDebug),"BoxClip: bottom clip old %d new %d\n",
+ (long) R->ymax, (long) ymax);
+ R->ymax = ymax;
+ }
+
+
+ laste = &anchor;
+ anchor.link = R->anchor;
+
+ for (e = R->anchor; VALIDEDGE(e); e = e->link) {
+ if (TOP(e) < ymin) {
+ e->xvalues += ymin - e->ymin;
+ e->ymin = ymin;
+ }
+ if (BOTTOM(e) > ymax)
+ e->ymax = ymax;
+ if (TOP(e) >= BOTTOM(e)) {
+ discard(laste, e->link->link);
+ e = laste;
+ continue;
+ }
+ if (e->xmin < xmin) {
+ cedgemax(BOTTOM(e) - TOP(e), e->xvalues, xmin);
+ e->xmin = xmin;
+ e->xmax = MAX(e->xmax, xmin);
+ }
+ if (e->xmax > xmax) {
+ cedgemin(BOTTOM(e) - TOP(e), e->xvalues, xmax);
+ e->xmin = MIN(e->xmin, xmax);
+ e->xmax = xmax;
+ }
+ laste = e;
+ }
+
+ R->anchor = anchor.link;
+
+ return(R);
+}
+
+#ifdef notdef
+/*
+:h3.CoerceRegion() - Force a TextPath Structure to Become a Region
+
+We also save the newly created region in the textpath structure, if the
+structure was permanent. Then we don't have to do this again. Why not
+save it all the time? Well, we certainly could, but I suspect it
+wouldn't pay. We would have to make this region permanent (because we
+couldn't have it be consumed) and this would probably require
+unnecessary CopyRegions in most cases.
+*/
+
+struct region *CoerceRegion(tp)
+ register struct textpath *tp; /* input TEXTTYPE */
+{
+ struct segment *path; /* temporary character path */
+ struct region *R; /* returned region */
+
+
+ R = Interior(path, EVENODDRULE);
+ return(R);
+}
+#endif
+
+/*
+:h3.RegionBounds() - Returns Bounding Box of a Region
+*/
+
+struct segment *RegionBounds(R)
+ register struct region *R;
+{
+ extern struct XYspace *IDENTITY;
+
+ register struct segment *path; /* returned path */
+
+ path = BoxPath(IDENTITY, R->ymax - R->ymin, R->xmax - R->xmin);
+ path = Join(PathSegment(MOVETYPE, R->origin.x + TOFRACTPEL(R->xmin),
+ R->origin.y + TOFRACTPEL(R->ymin) ),
+ path);
+ return(path);
+}
+
+/*
+:h2.Formatting/Dump Routines for Debug
+
+:h3.DumpArea() - Display a Region
+*/
+void DumpArea(area)
+ register struct region *area;
+{
+ IfTrace1(TRUE,"Dumping area %x,", area);
+ IfTrace4(TRUE," X %d:%d Y %d:%d;", (long) area->xmin,
+ (long) area->xmax, (long) area->ymin,(long) area->ymax);
+ IfTrace4(TRUE," origin=(%p,%p), ending=(%p,%p)\n",
+ area->origin.x, area->origin.y, area->ending.x, area->ending.y);
+ DumpEdges(area->anchor);
+}
+
+#define INSWATH(p, y0, y1) (p != NULL && p->ymin == y0 && p->ymax == y1)
+/*
+:h3.DumpEdges() - Display Run End Lists (Edge Lists)
+*/
+
+static pel RegionDebugYMin = MINPEL;
+static pel RegionDebugYMax = MAXPEL;
+
+void DumpEdges(edges)
+ register struct edgelist *edges;
+{
+ register struct edgelist *p,*p2;
+ register pel ymin = MINPEL;
+ register pel ymax = MINPEL;
+ register int y;
+
+ if (edges == NULL) {
+ IfTrace0(TRUE," NULL area.\n");
+ return;
+ }
+ if (RegionDebug <= 1) {
+ for (p=edges; p != NULL; p = p->link) {
+ edgecheck(p, ymin, ymax);
+ ymin = p->ymin; ymax = p->ymax;
+ IfTrace3(TRUE,". at %x type=%d flag=%x",
+ p, (long) p->type,(long) p->flag);
+ IfTrace4(TRUE," bounding box HxW is %dx%d at (%d,%d)\n",
+ (long) ymax - ymin, (long) p->xmax - p->xmin,
+ (long) p->xmin, (long) ymin);
+ }
+ }
+ else {
+
+ for (p2=edges; p2 != NULL; ) {
+
+ edgecheck(p2, ymin, ymax);
+ ymin = p2->ymin;
+ ymax = p2->ymax;
+
+ if (RegionDebug > 3 || (ymax > RegionDebugYMin
+ && ymin < RegionDebugYMax)) {
+ IfTrace2 (TRUE,". Swath from %d to %d:\n",
+ ymin, ymax);
+ for (p=p2; INSWATH(p,ymin,ymax); p = p->link) {
+ IfTrace4(TRUE,". . at %x[%x] range %d:%d, ",
+ p, (long) p->flag,
+ (long) p->xmin, (long)p->xmax);
+ IfTrace1(TRUE, "subpath=%x,\n", p->subpath);
+ }
+ }
+ for (y=MAX(ymin,RegionDebugYMin); y < MIN(ymax, RegionDebugYMax); y++) {
+ IfTrace1(TRUE,". . . Y[%5d] ", (long) y);
+ for (p=p2; INSWATH(p,ymin,ymax); p = p->link)
+ IfTrace1(TRUE,"%5d ",
+ (long) p->xvalues[y - ymin]);
+ IfTrace0(TRUE,"\n");
+ }
+ while (INSWATH(p2, ymin, ymax))
+ p2 = p2->link;
+ }
+ }
+}
+
+/*
+:h3.edgecheck() - For Debug, Verify that an Edge Obeys the Rules
+*/
+
+/*ARGSUSED*/
+static edgecheck(edge, oldmin, oldmax)
+ struct edgelist *edge;
+ int oldmin,oldmax;
+{
+ if (edge->type != EDGETYPE)
+ abort("EDGE ERROR: non EDGETYPE in list");
+/*
+The following check is not valid if the region is jumbled so I took it
+out:
+*/
+/* if (edge->ymin < oldmax && edge->ymin != oldmin)
+ abort("EDGE ERROR: overlapping swaths"); */
+}
projects / rdpsrv / blobdiff