/* $XConsortium: regions.c,v 1.6 94/02/06 16:22:21 gildea 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 Module - Regions Operator Handler * * This module is responsible for creating and manipulating regions. * * &author. Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com) */ /* * Include Files * * The included files are: */ #ifndef T1GST #include "global.h" #endif #include /** * Prototypes for static functions **/ static struct edgelist *NewEdge( pel xmin, int xmax, /* X extent of edge */ pel ymin, int 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 *swathxsort( struct edgelist *before0, /* edge before this swath */ struct edgelist *edge); /* input edge */ static void Unwind( struct edgelist *area); /* input area modified in place */ static void __stdargs newfilledge( struct region *R, /* region being built */ fractpel xmin, fractpel xmax, /* X range of this edge */ fractpel ymin, fractpel ymax, /* Y range of this edge */ int isdown); /* flag: TRUE means edge goes down, else up */ static struct edgelist *splitedge( struct edgelist *list, /* area to split */ pel y); /* Y value to split list at */ static void vertjoin(struct edgelist *top, struct edgelist *bottom); static int touches(int h, pel *left, pel *right); static int crosses(int h, pel *left, pel *right); static void cedgemin(int h, pel *e1, pel x); static void cedgemax(int h, pel *e1, pel x); static void edgemin(int h, pel *e1, pel *e2); static void edgemax(int h, pel *e1, pel *e2); static void discard(struct edgelist *left, struct edgelist *right); static void edgecheck(struct edgelist *edge, int oldmin, int oldmax); static void OptimizeRegion(struct region *R); /* * The ISOPTIMIZED flag tells us if we've put a permanent region in * 'optimal' form. */ #define ISOPTIMIZED(flag) ((flag)&0x10) /* * "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; /* * "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 */ 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 }; /* * 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 t1_KillRegion( struct region *area) /* area to free */ { struct edgelist *p; /* loop variable */ struct edgelist *next; /* loop variable */ if (area->references < 0) t1_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); } /* * CopyRegion() - Makes a Copy of a Region */ struct region *t1_CopyRegion( struct region *area) /* region to duplicate */ { struct region *r; /* output region built here */ struct edgelist *last; /* loop variable */ 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); } /* * 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( pel xmin, int xmax, /* X extent of edge */ pel ymin, int 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 }; struct edgelist *r; /* returned structure */ int iy; /* ymin adjusted for 'long' alignment purposes */ IfTrace2((RegionDebug), "....new edge: ymin=%d, ymax=%d ", (long)ymin, (long)ymax); if (ymin >= ymax) t1_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 - (((int)xvalues) & (sizeof(long) - 1)) / sizeof(pel); //if ((ymax-iy) < 0) // printf("EdgeList: ymax - iy < 0 : ymin=%d,ymax=%d,xvalues=%d\n",ymin,ymax,(int)xvalues); 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); } /* * Building Regions * * 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. * * "Interior" calls StepLine or StepConic or StepBezier as appropriate * to produce run ends. * * 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. * * ChangeDirection will call whatever function is in the region * structure; for Interior, this function is 'newfilledge'. * * 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". * * By making the function called by ChangeDirection be a parameter of the * region, we allow the same ChangeDirection logic to be used by stroking. */ struct region *Interior( struct segment *p, /* take interior of this path */ int fillrule) /* rule to follow if path crosses itself */ { fractpel x, y; /* keeps ending point of path segment */ fractpel lastx, lasty; /* previous x,y from path segment before */ struct region *R; /* region I will build */ 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,NULL,NULL), 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,NULL,NULL,NULL), struct region *); ARGCHECK((p->type != MOVETYPE), "Interior: path not closed", p, R, (0,NULL,NULL,NULL), 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 * * anchor = NULL * xmin, ymin, xmax, ymax, to minimum and maximum values respectively. * * Anchor = NULL is very * important to ChangeDirection. * See 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: t1_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); } /* * 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 void Unwind( struct edgelist *area) /* input area modified in place */ { struct edgelist *last, *next; /* struct before and after current one */ int y; /* ymin of current swath */ 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) t1_abort("Unwind: uneven edges"); } } /* * "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; /* * 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( int type, /* CD_FIRST, CD_CONTINUE, or CD_LAST */ struct region *R, /* region in which we are changing direction */ fractpel x, fractpel y, /* current beginning x,y */ fractpel dy) /* direction and magnitude of change in y */ { fractpel ymin, ymax; /* minimum and maximum Y since last call */ fractpel x_at_ymin, x_at_ymax; /* their respective X's */ pel iy; /* nearest integer pel to 'y' */ pel idy; /* nearest integer pel to 'dy' */ 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) t1_abort("negative sized edge?"); // (*R->newedgefcn) (R, R->edgexmin, R->edgexmax, ymin, ymax, // R->lastdy > 0, x_at_ymin, x_at_ymax); (*R->newedgefcn) (R, R->edgexmin, R->edgexmax, ymin, ymax, R->lastdy > 0); } 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; } } /* * 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( struct region *R, /* region being built */ fractpel xmin, fractpel xmax, /* X range of this edge */ fractpel ymin, fractpel ymax, /* Y range of this edge */ int isdown) /* flag: TRUE means edge goes down, else up */ { pel pelxmin, pelymin, pelxmax, pelymax; /* pel versions of bounds */ 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); } /* * Sorting Edges * * 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( struct edgelist *anchor, /* list being built */ struct edgelist *edge, /* incoming edge or pair of edges */ struct edgelist *(*swathfcn) (struct edgelist *, struct edgelist *)) /* horizontal sorter */ { 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); } /* * 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( struct edgelist *list, /* area to split */ pel y) /* Y value to split list at */ { struct edgelist *new; /* anchor for newly built list */ struct edgelist *last; /* end of newly built list */ struct edgelist *r; /* temp pointer to new structure */ 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) t1_abort("splitedge: above top of list"); if (y == list->ymin) t1_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) t1_abort("null splitedge"); lastlist->link = NULL; last->link = list; IfTrace1((RegionDebug > 1), "yields %x\n", new); return (new); } /* * vertjoin() - Join Two Disjoint Edge Lists Vertically * * The two edges must be disjoint vertically. */ static void vertjoin(struct edgelist *top, struct edgelist *bottom) { if (BOTTOM(top) > TOP(bottom)) t1_abort("vertjoin not disjoint"); for (; top->link != NULL; top = top->link) {; } top->link = bottom; return; } /* * 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( struct edgelist *before0, /* edge before this swath */ struct edgelist *edge) /* input edge */ { struct edgelist *before; struct edgelist *after; 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); } /* * 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( struct edgelist *before0, /* edge before the swath */ struct edgelist *edge) /* list of two edges to be unioned */ { int h; /* saves height of edge */ struct edgelist *rightedge; /* saves right edge of 'edge' */ 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) t1_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: * * before after * R <---L----> R L R L R * <---L---> <------R--------------------------> * edge * * 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: * * before after * R L R L R L R * L R * edge * * 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: * * before after * R L R L R L R * <---L---> <---R-------------------> * edge * * 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: * * before left after * R L R L R L R * <---L---> <---R---> * edge * * 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); } /* * 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( struct edgelist *before,/* edge before this swath */ struct edgelist *edge) /* input edge */ { struct edgelist *after; after = before->link; while (after != NULL && TOP(after) == TOP(edge)) { before = after; after = after->link; } return (before); } /* * 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(int h, pel *left, pel *right) { for (; h > 0; h--) if (*left++ >= *right++) break; return (h); } /* * crosses() - Returns the Remaining Height When Two Edges Cross * * So, it will return 0 if they never cross. */ static int crosses(int h, pel *left, pel *right) { for (; h > 0; h--) if (*left++ > *right++) break; return (h); } /* * cedgemin() - Stores the Mininum of an Edge and an X Value */ static void cedgemin(int h, pel *e1, pel x) { for (; --h >= 0; e1++) if (*e1 > x) *e1 = x; } /* * cedgemax() - Stores the Maximum of an Edge and an X Value */ static void cedgemax(int h, pel *e1, pel x) { for (; --h >= 0; e1++) if (*e1 < x) *e1 = x; } /* * edgemin() - Stores the Mininum of Two Edges in First Edge */ static void edgemin(int h, pel *e1, pel *e2) { for (; --h >= 0; e1++, e2++) if (*e1 > *e2) *e1 = *e2; } /* * edgemax() - Stores the Maximum of Two Edges in First Edge */ static void edgemax(int h, pel *e1, pel *e2) { for (; --h >= 0; e1++, e2++) if (*e1 < *e2) *e1 = *e2; } /* * 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 void discard(struct edgelist *left, struct edgelist *right) { 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) t1_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; } /* * 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( struct region *R, /* region to modify */ fractpel dx, fractpel dy) /* delta X and Y to move edge list by */ { 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; } } } /* * UnJumble() - Sort a Region Top to Bottom * * It is an open question whether it pays in general to do this. */ void UnJumble(struct region *region) { struct edgelist *anchor; /* new lists built here */ struct edgelist *edge; /* edge pointer for loop */ struct edgelist *next; /* ditto */ anchor = NULL; for (edge = region->anchor; VALIDEDGE(edge); edge = next) { if (edge->link == NULL) t1_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 void OptimizeRegion(struct region *R) { pel *xP; /* pel pointer for inner loop */ int x; /* holds X value */ int xmin, xmax; /* holds X range */ int h; /* loop counter */ 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) t1_abort("Tighten: existing edge bound was bad"); if (xmin < R->xmin || xmax > R->xmax) t1_abort("Tighten: existing region bound was bad"); e->xmin = xmin; e->xmax = xmax; } R->flag |= ISOPTIMIZED(ON); } /* * Miscellaneous Routines * * 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'. */ void MoreWorkArea( struct region *R, /* region we are generating */ fractpel x1, fractpel y1, /* starting point of line */ fractpel x2, fractpel y2) /* ending point of line */ { 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); } /* * 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( struct region *R, /* region to clip */ pel xmin, pel ymin, /* upper left hand corner of rectangle */ pel xmax, pel ymax) /* lower right hand corner */ { struct edgelist anchor; /* pretend edgelist to facilitate discards */ 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 /* * 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( struct textpath *tp) /* input TEXTTYPE */ { struct segment *path; /* temporary character path */ struct region *R; /* returned region */ R = Interior(path, EVENODDRULE); return (R); } #endif /* * RegionBounds() - Returns Bounding Box of a Region */ struct segment *t1_RegionBounds(struct region *R) { extern struct XYspace *IDENTITY; 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); } /* * Formatting/Dump Routines for Debug * * DumpArea() - Display a Region */ void DumpArea(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) /* * DumpEdges() - Display Run End Lists (Edge Lists) */ static pel RegionDebugYMin = MINPEL; static pel RegionDebugYMax = MAXPEL; void DumpEdges(struct edgelist *edges) { struct edgelist *p, *p2; pel ymin = MINPEL; pel ymax = MINPEL; 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; } } } /* * edgecheck() - For Debug, Verify that an Edge Obeys the Rules */ static void edgecheck(struct edgelist *edge, int oldmin, int oldmax) { if (edge->type != EDGETYPE) t1_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) t1_abort("EDGE ERROR: overlapping swaths"); */ }