+++ /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