X-Git-Url: https://git.sesse.net/?p=rdpsrv;a=blobdiff_plain;f=Xserver%2Flib%2Ffont%2FType1%2Fregions.c;fp=Xserver%2Flib%2Ffont%2FType1%2Fregions.c;h=0000000000000000000000000000000000000000;hp=c9b0038aa0ed6e74a8e3b40ef614b21be393b9a8;hb=ce66b81460e5353db09d45c02339d4583fbda255;hpb=7772d71ffd742cfc9b7ff214659d16c5bb56a391 diff --git a/Xserver/lib/font/Type1/regions.c b/Xserver/lib/font/Type1/regions.c deleted file mode 100644 index c9b0038..0000000 --- a/Xserver/lib/font/Type1/regions.c +++ /dev/null @@ -1,1746 +0,0 @@ -/* $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"); */ -}