1 /* $XConsortium: regions.c,v 1.6 94/02/06 16:22:21 gildea Exp $ */
2 /* $XFree86: xc/lib/font/Type1/regions.c,v 3.0 1996/08/25 13:58:26 dawes Exp $ */
3 /* Copyright International Business Machines, Corp. 1991
5 * Copyright Lexmark International, Inc. 1991
8 * License to use, copy, modify, and distribute this software and its
9 * documentation for any purpose and without fee is hereby granted,
10 * provided that the above copyright notice appear in all copies and that
11 * both that copyright notice and this permission notice appear in
12 * supporting documentation, and that the name of IBM or Lexmark not be
13 * used in advertising or publicity pertaining to distribution of the
14 * software without specific, written prior permission.
16 * IBM AND LEXMARK PROVIDE THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES OF
17 * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO ANY
18 * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
19 * AND NONINFRINGEMENT OF THIRD PARTY RIGHTS. THE ENTIRE RISK AS TO THE
20 * QUALITY AND PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT
21 * OR MAINTAIN, BELONGS TO THE LICENSEE. SHOULD ANY PORTION OF THE
22 * SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM OR LEXMARK) ASSUMES THE
23 * ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION. IN NO EVENT SHALL
24 * IBM OR LEXMARK BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
25 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
26 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
27 * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
30 /* REGIONS CWEB V0023 LOTS */
32 :h1 id=regions.REGIONS Module - Regions Operator Handler
34 This module is responsible for creating and manipulating regions.
36 &author. Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com)
41 The included files are:
53 #include "strokes.h" /* to pick up 'DoStroke' */
55 static void newfilledge();
56 static struct edgelist *splitedge();
57 static void vertjoin();
60 static void edgemin();
61 static void edgemax();
64 static struct edgelist *NewEdge();
65 static struct edgelist *swathxsort(); /* 'SortSwath' function */
68 :h3.Functions Provided to the TYPE1IMAGER User
70 This module provides the following TYPE1IMAGER entry points:
73 /*SHARED LINE(S) ORIGINATED HERE*/
75 :h3.Functions Provided to Other Modules
77 This module provides the following entry points to other modules:
80 /*SHARED LINE(S) ORIGINATED HERE*/
82 :h3.Macros Provided to Other Modules
84 :h4.GOING_TO() - Macro Predicate Needed for Changing Direction, Etc.
86 The actual generation of run end lists (edge boundaries) is left
87 to the low level rasterizing modules, LINES and CURVES. There
88 are some global region-type
89 questions that occur when doing a low-level
92 :li.Did we just change direction in Y and therefore need to start
94 :li.Did we run out of allocated edge space?
95 :li.Do the minimum or maximum X values for the current edge need
98 In general the REGIONS is not smart enough to answer those questions
99 itself. (For example, determining if and when a curve changes direction
100 may need detailed curve knowledge.) Yet, this must be done efficiently.
101 We provide a macro "GOING_TO" where the invoker tells us where it is
102 heading for (x2,y2), plus where it is now (x1,y1), plus the current
103 region under construction, and the macro answers the questions above.
106 /*SHARED LINE(S) ORIGINATED HERE*/
108 :h2.Data Structures Used to Represent Regions
110 :h3.The "region" Structure
112 The region structure is an anchor for a linked list of "edgelist"
113 structures (see :hdref refid=edgelist..). It also summarizes the
114 information in the edgelist structures (for example, the bounding
115 box of the region). And, it contains scratch areas used during
116 the creation of a region.
119 /*SHARED LINE(S) ORIGINATED HERE*/
121 The ISOPTIMIZED flag tells us if we've put a permanent region in
124 #define ISOPTIMIZED(flag) ((flag)&0x10)
127 The ISRECTANGULAR flag tells us if a region is a rectangle. We don't
128 always notice rectangles--if this flag is set, the region definitely
129 is a rectangle, but some rectangular regions will not have the flag
130 set. The flag is used to optimize some paths.
133 /*SHARED LINE(S) ORIGINATED HERE*/
135 :h4."INFINITY" - A Constant Region Structure of Infinite Extent
137 Infinity is the complement of a null area:
138 Note - removed the refcount = 1 init, replaced with references = 2 3-26-91 PNM
140 static struct region infinity = { REGIONTYPE,
141 ISCOMPLEMENT(ON)+ISINFINITE(ON)+ISPERMANENT(ON)+ISIMMORTAL(ON), 2,
145 0, 0, 0, 0, 0, NULL, NULL,
146 NULL, 0, NULL, NULL };
147 struct region *INFINITY = &infinity;
150 :h4."EmptyRegion" - A Region Structure with Zero Area
152 This structure is used to initialize the region to be built in
154 Note - replaced refcount = 1 init with references = 2 3-26-91 PNM
157 /*SHARED LINE(S) ORIGINATED HERE*/
158 struct region EmptyRegion = { REGIONTYPE,
159 ISPERMANENT(ON)+ISIMMORTAL(ON), 2,
161 MAXPEL, MAXPEL, MINPEL, MINPEL,
163 0, 0, 0, 0, 0, NULL, NULL,
164 NULL, 0, NULL, NULL };
167 :h3 id=edgelist.The "edgelist" Structure
169 Regions are represented by a linked list of 'edgelist' structures.
170 When a region is complete, the structures are paired, one for the
171 left and one for the right edge. While a region is being built,
172 this rule may be violated temporarily.
174 An 'edgelist' structure contains the X values for a given span
175 of Y values. The (X,Y) pairs define an edge. We use the crack
176 and edge coordinate system, so that integer values of X and Y
177 go between pels. The edge is defined between the minimum Y and
180 The linked list is kept sorted from top to bottom, that is, in
181 increasing y. Also, if 'e1' is an edgelist structure and 'e2' is the
182 next one in the list, they must have exactly the same ymin,ymax values
183 or be totally disjoint. These two requirements mean that if e2's ymin
184 is less than e1's ymax, it must be exactly equal to e1's ymin. A
185 sublist of structures with identical ymin and ymax values is called a
188 In addition, edgelist structures are separately linked together based
189 on what subpath originally created them; each subpath is kept as a
190 separate circular linked list. This information is ignored unless
191 continuity checking is invoked. See :hdref refid=subpath. for a
192 complete description of this.
196 /*SHARED LINE(S) ORIGINATED HERE*/
199 The "edgelist" structure follows the convention of TYPE1IMAGER user
200 objects, having a type field and a flag field as the first two
201 elements. However, the user never sees "edgelist" structures
202 directly; he is given handles to "region" structures only.
204 By having a type field, we can use the "copy" feature of Allocate()
205 to duplicate edge lists quickly.
207 We also define two flag bits for this structure. The ISDOWN bit is set
208 if the edge is going in the direction of increasing Y. The ISAMBIGUOUS
209 bit is set if the edge is identical to its neighbor (edge->link); such
210 edges may be "left" when they should be "right", or vice versa,
211 unnecessarily confusing the continuity checking logic. The FixSubPaths()
212 routine in HINTS will swap ambiguous edges if that avoids crossing edges;
213 see :hdref refid=fixsubp..
216 /*SHARED LINE(S) ORIGINATED HERE*/
219 :h3.KillRegion() - Destroys a Region
221 KillRegion nominally just decrements the reference count to that region.
222 If the reference count becomes 0, all memory associated with it is
223 freed. We just follow the linked list, freeing as we go, then kill any
224 associated (thresholded) picture.
225 Note - added conditional return based on references 3-26-91 PNM
228 void KillRegion(area)
229 register struct region *area; /* area to free */
231 register struct edgelist *p; /* loop variable */
232 register struct edgelist *next; /* loop variable */
234 if (area->references < 0)
235 abort("KillRegion: negative reference count");
236 if ( (--(area->references) > 1) ||
237 ( (area->references == 1) && !ISPERMANENT(area->flag) ) )
240 for (p=area->anchor; p != NULL; p=next) {
244 if (area->thresholded != NULL)
245 KillPicture(area->thresholded);
249 :h3.CopyRegion() - Makes a Copy of a Region
251 struct region *CopyRegion(area)
252 register struct region *area; /* region to duplicate */
254 register struct region *r; /* output region built here */
255 register struct edgelist *last; /* loop variable */
256 register struct edgelist *p,*newp; /* loop variables */
258 r = (struct region *)Allocate(sizeof(struct region), area, 0);
261 for (p=area->anchor; VALIDEDGE(p); p=p->link) {
263 newp = NewEdge(p->xmin, p->xmax, p->ymin, p->ymax, p->xvalues, ISDOWN(p->flag));
264 if (r->anchor == NULL)
265 r->anchor = last = newp;
271 if (area->thresholded != NULL)
272 /* replaced DupPicture with Dup() 3-26-91 PNM */
273 r->thresholded = (struct picture *)Dup(area->thresholded);
277 :h4.NewEdge() - Allocates and Returns a New "edgelist" Structure
279 We allocate space for the X values contiguously with the 'edgelist'
280 structure that locates them. That way, we only have to free the
281 edgelist structure to free all memory associated with it. Damn
285 static struct edgelist *NewEdge(xmin, xmax, ymin, ymax, xvalues, isdown)
286 pel xmin,xmax; /* X extent of edge */
287 pel ymin,ymax; /* Y extent of edge */
288 pel *xvalues; /* list of X values for entire edge */
289 int isdown; /* flag: TRUE means edge progresses downward */
291 static struct edgelist template = {
292 EDGETYPE, 0, 1, NULL, NULL,
295 register struct edgelist *r; /* returned structure */
296 register int iy; /* ymin adjusted for 'long' alignment purposes */
298 IfTrace2((RegionDebug),"....new edge: ymin=%d, ymax=%d ",
299 (long)ymin, (long) ymax);
301 abort("newedge: height not positive");
303 We are going to copy the xvalues into a newly allocated area. It
304 helps performance if the values are all "long" aligned. We can test
305 if the xvalues are long aligned by ANDing the address with the
306 (sizeof(long) - 1)--if non zero, the xvalues are not aligned well. We
307 set 'iy' to the ymin value that would give us good alignment:
309 iy = ymin - (((unsigned long)xvalues) & (sizeof(long)-1)) / sizeof(pel);
311 r = (struct edgelist *)Allocate(sizeof(struct edgelist), &template,
312 (ymax - iy) * sizeof(pel));
314 if (isdown) r->flag = ISDOWN(ON);
320 r->xvalues = (pel *) FOLLOWING(r);
322 r->xvalues += ymin - iy;
323 xvalues -= ymin - iy;
327 We must round up (ymax - iy) so we get the ceiling of the number of
328 longs. The destination must be able to hold these extra bytes because
329 Allocate() makes everything it allocates be in multiples of longs.
331 LONGCOPY(&r[1], xvalues, (ymax - iy) * sizeof(pel) + sizeof(long) - 1);
333 IfTrace1((RegionDebug),"result=%x\n", r);
340 :h3.Interior() - Iterate Through a Path, Building a Region
342 This routine is the workhorse driver routine that iterates through a
343 path, calling the appropriate stepping routines to actually produce the
344 run end "edgelist" structures.
347 :li."Interior" calls StepLine or StepConic or StepBezier as appropriate
349 :li.Occasionally these routines will notice a change in Y direction
350 and will call ChangeDirection (through the GOING_TO macro); this is
351 a call back to the REGIONS module.
352 :li.ChangeDirection will call whatever function is in the region
353 structure; for Interior, this function is 'newfilledge'.
354 :li.Newfilledge will call NewEdge to create a new edgelist structure,
355 then, call SortSwath to sort it onto the linked list being built at
359 By making the function called by ChangeDirection be a parameter of the
360 region, we allow the same ChangeDirection logic to be used by stroking.
363 /*SHARED LINE(S) ORIGINATED HERE*/
365 struct region *Interior(p, fillrule)
366 register struct segment *p; /* take interior of this path */
367 register int fillrule; /* rule to follow if path crosses itself */
369 register fractpel x,y; /* keeps ending point of path segment */
370 fractpel lastx,lasty; /* previous x,y from path segment before */
371 register struct region *R; /* region I will build */
372 register struct segment *nextP; /* next segment of path */
373 struct fractpoint hint; /* accumulated hint value */
374 char tempflag; /* flag; is path temporary? */
375 char Cflag; /* flag; should we apply continuity? */
377 IfTrace2((MustTraceCalls),". INTERIOR(%z, %d)\n", p, (long) fillrule);
382 Establish the 'Cflag' continuity flag based on user's fill rule and
383 our own 'Continuity' pragmatic (0: never do continuity, 1: do what
384 user asked, >1: do it regardless).
387 Cflag = Continuity > 0;
388 fillrule -= CONTINUITY;
391 Cflag = Continuity > 1;
393 ARGCHECK((fillrule != WINDINGRULE && fillrule != EVENODDRULE),
394 "Interior: bad fill rule", NULL, NULL, (1,p), struct region *);
396 if (p->type == TEXTTYPE)
397 /* if (fillrule != EVENODDRULE)
399 return((struct region *)UniquePath(p));
400 if (p->type == STROKEPATHTYPE)
401 if (fillrule == WINDINGRULE)
402 return((struct region *)DoStroke(p));
406 R = (struct region *)Allocate(sizeof(struct region), &EmptyRegion, 0);
408 ARGCHECK(!ISPATHANCHOR(p), "Interior: bad path", p, R, (0), struct region *);
409 ARGCHECK((p->type != MOVETYPE), "Interior: path not closed", p, R, (0), struct region *);
412 /* changed definition from !ISPERMANENT to references <= 1 3-26-91 PNM */
413 tempflag = (p->references <= 1); /* only first segment in path is so marked */
414 if (!ISPERMANENT(p->flag)) p->references -= 1;
416 R->newedgefcn = newfilledge;
418 Believe it or not, "R" is now completely initialized. We are counting
419 on the copy of template to get other fields the way we want them,
423 :li.xmin, ymin, xmax, ymax, to minimum and maximum values respectively.
425 Anchor = NULL is very
426 important to ChangeDirection.
427 See :hdref refid=CD..
429 To minimize problems of "wrapping" in our pel arithmetic, we keep an
430 origin of the region which is the first move. Hopefully, that keeps
431 numbers within plus or minus 32K pels.
433 R->origin.x = 0/*TOFRACTPEL(NEARESTPEL(p->dest.x))*/;
434 R->origin.y = 0/*TOFRACTPEL(NEARESTPEL(p->dest.y))*/;
435 lastx = - R->origin.x;
436 lasty = - R->origin.y;
438 ChangeDirection initializes other important fields in R, such as
439 lastdy, edge, edgeYstop, edgexmin, and edgexmax. The first segment
440 is a MOVETYPE, so it will be called first.
443 The hints data structure must be initialized once for each path.
447 InitHints(); /* initialize hint data structure */
451 x = lastx + p->dest.x;
452 y = lasty + p->dest.y;
454 IfTrace2((HintDebug > 0),"Ending point = (%p,%p)\n", x, y);
459 Here we start the hints processing by initializing the hint value to
460 zero. If ProcessHints is FALSE, the value will remain zero.
461 Otherwise, hint accumulates the computed hint values.
467 If we are processing hints, and this is a MOVE segment (other than
468 the first on the path), we need to close (reverse) any open hints.
472 if ((p->type == MOVETYPE) && (p->last == NULL)) {
474 IfTrace2((HintDebug>0),"Closed point= (%p,%p)\n",
479 Next we run through all the hint segments (if any) attached to this
480 segment. If ProcessHints is TRUE, we will accumulate computed hint
481 values. In either case, nextP will be advanced to the first non-HINT
482 segment (or NULL), and each hint segment will be freed if necessary.
485 while ((nextP != NULL) && (nextP->type == HINTTYPE)) {
487 ProcessHint(nextP, x + hint.x, y + hint.y, &hint);
490 register struct segment *saveP = nextP;
499 We now apply the full hint value to the ending point of the path segment.
505 IfTrace2((HintDebug>0),"Hinted ending point = (%p,%p)\n", x, y);
510 StepLine(R, lastx, lasty, x, y);
517 For a conic curve, we apply half the hint value to the conic midpoint.
525 register struct beziersegment *bp = (struct beziersegment *) p;
528 For a Bezier curve, we apply the full hint value to the Bezier C point.
531 StepBezier(R, lastx, lasty,
532 lastx + bp->B.x, lasty + bp->B.y,
533 lastx + bp->C.x + hint.x,
534 lasty + bp->C.y + hint.y,
541 At this point we have encountered a MOVE segment. This breaks the
542 path, making it disjoint.
544 if (p->last == NULL) /* i.e., not first in path */
545 ChangeDirection(CD_LAST, R, lastx, lasty, (fractpel) 0);
547 ChangeDirection(CD_FIRST, R, x, y, (fractpel) 0);
549 We'll just double check for closure here. We forgive an appended
550 MOVETYPE at the end of the path, if it isn't closed:
552 if (!ISCLOSED(p->flag) && p->link != NULL)
553 return((struct region *)ArgErr("Fill: sub-path not closed", p, NULL));
557 abort("Interior: path type error");
560 We're done with this segment. Advance to the next path segment in
561 the list, freeing this one if necessary:
563 lastx = x; lasty = y;
569 ChangeDirection(CD_LAST, R, lastx, lasty, (fractpel) 0);
573 Finally, clean up the region's based on the user's 'fillrule' request:
577 if (fillrule == WINDINGRULE)
582 :h4.Unwind() - Discards Edges That Fail the Winding Rule Test
584 The winding rule says that upward going edges should be paired with
585 downward going edges only, and vice versa. So, if two upward edges
586 or two downward edges are nominally left/right pairs, Unwind() should
587 discard the second one. Everything should balance; we should discard
588 an even number of edges; of course, we abort if we don't.
591 register struct edgelist *area; /* input area modified in place */
593 register struct edgelist *last,*next; /* struct before and after current one */
594 register int y; /* ymin of current swath */
595 register int count,newcount; /* winding count registers */
597 IfTrace1((RegionDebug>0),"...Unwind(%z)\n", area);
599 while (VALIDEDGE(area)) {
607 if (ISDOWN(area->flag))
608 newcount = count + 1;
610 newcount = count - 1;
612 if (count == 0 || newcount == 0)
620 } while (area != NULL && area->ymin == y);
623 abort("Unwind: uneven edges");
629 This is a statically allocated array where edges are built
630 before being copied into more permanent storage by NewEdge().
637 static pel workedge[MAXEDGE];
638 static pel *currentworkarea = workedge;
639 static pel currentsize = MAXEDGE;
642 :h3 id=cd.ChangeDirection() - Called When Y Direction Changes
644 The rasterizing routines call this entry point when they detect
645 a change in Y. We then build the current edge and sort it into
646 emerging edgelist at 'anchor' by calling whatever "newedgefcn"
650 void ChangeDirection(type, R, x, y, dy)
651 int type; /* CD_FIRST, CD_CONTINUE, or CD_LAST */
652 register struct region *R; /* region in which we are changing direction */
653 fractpel x,y; /* current beginning x,y */
654 fractpel dy; /* direction and magnitude of change in y */
656 register fractpel ymin,ymax; /* minimum and maximum Y since last call */
657 register fractpel x_at_ymin,x_at_ymax; /* their respective X's */
658 register pel iy; /* nearest integer pel to 'y' */
659 register pel idy; /* nearest integer pel to 'dy' */
660 register int ydiff; /* allowed Y difference in 'currentworkarea' */
662 IfTrace4((RegionDebug>0),"Change Y direction (%d) from (%p,%p), dy=%p\n",
663 (long) type, x, y, dy);
665 if (type != CD_FIRST) {
669 x_at_ymin = R->firstx;
677 x_at_ymax = R->firstx;
681 abort("negative sized edge?");
684 (*R->newedgefcn)(R, R->edgexmin, R->edgexmax, ymin, ymax,
685 R->lastdy > 0, x_at_ymin, x_at_ymax);
694 idy = NEARESTPEL(dy);
695 if (currentworkarea != workedge && idy < MAXEDGE && idy > -MAXEDGE) {
696 NonObjectFree(currentworkarea);
697 currentworkarea = workedge;
698 currentsize = MAXEDGE;
700 ydiff = currentsize - 1;
702 R->edge = ¤tworkarea[-iy];
703 R->edgeYstop = TOFRACTPEL(ydiff + iy) + FPHALF;
706 R->edge = ¤tworkarea[ydiff - iy];
707 R->edgeYstop = TOFRACTPEL(iy - ydiff) - FPHALF;
709 R->edgexmax = R->edgexmin = x;
711 If this is the end of a subpath, we complete the subpath circular
714 if (type == CD_LAST && R->lastedge != NULL) {
715 register struct edgelist *e = R->firstedge;
717 while (e->subpath != NULL)
719 e->subpath = R->lastedge;
720 R->lastedge = R->firstedge = NULL;
724 :h3 id=newfill.newfilledge() - Called When We Have a New Edge While Filling
726 This is the prototypical "newedge" function passed to "Rasterize" and
727 stored in "newedgefcn" in the region being built.
729 If the edge is non-null, we sort it onto the list of edges we are
730 building at "anchor".
732 This function also has to keep the bounding box of the region
736 static void newfilledge(R, xmin, xmax, ymin, ymax, isdown)
737 register struct region *R; /* region being built */
738 fractpel xmin,xmax; /* X range of this edge */
739 fractpel ymin,ymax; /* Y range of this edge */
740 int isdown; /* flag: TRUE means edge goes down, else up */
743 register pel pelxmin,pelymin,pelxmax,pelymax; /* pel versions of bounds */
744 register struct edgelist *edge; /* newly created edge */
746 pelymin = NEARESTPEL(ymin);
747 pelymax = NEARESTPEL(ymax);
748 if (pelymin == pelymax)
751 pelxmin = NEARESTPEL(xmin);
752 pelxmax = NEARESTPEL(xmax);
754 if (pelxmin < R->xmin) R->xmin = pelxmin;
755 if (pelxmax > R->xmax) R->xmax = pelxmax;
756 if (pelymin < R->ymin) R->ymin = pelymin;
757 if (pelymax > R->ymax) R->ymax = pelymax;
759 edge = NewEdge(pelxmin, pelxmax, pelymin, pelymax, &R->edge[pelymin], isdown);
760 edge->subpath = R->lastedge;
762 if (R->firstedge == NULL)
765 R->anchor = SortSwath(R->anchor, edge, swathxsort);
772 :h3.SortSwath() - Vertically Sort an Edge into a Region
774 This routine sorts an edge or a pair of edges into a growing region,
775 so that the region maintains its top-to-bottom, left-to-right form.
776 The rules for sorting horizontally may vary depending on what you
777 are doing, but the rules for vertical sorting are always the same.
778 This routine is passed an argument that is a function that will
779 perform the horizontal sort on demand (for example, swathxsort() or
782 This is a recursive routine. A new edge (or edge pair) may overlap
783 the list I am building in strange and wonderful ways. Edges may
784 cross. When this happens, my strategy is to split the incoming edge
785 (or the growing list) in two at that point, execute the actual sort on
786 the top part of the split, and recursively call myself to figure out
787 exactly where the bottom part belongs.
790 #define TOP(e) ((e)->ymin) /* the top of an edge (for readability */
791 #define BOTTOM(e) ((e)->ymax) /* the bottom of an edge (for readability */
793 struct edgelist *SortSwath(anchor, edge, swathfcn)
794 struct edgelist *anchor; /* list being built */
795 register struct edgelist *edge; /* incoming edge or pair of edges */
796 struct edgelist *(*swathfcn)(); /* horizontal sorter */
798 register struct edgelist *before,*after;
799 struct edgelist base;
801 if (RegionDebug > 0) {
802 if (RegionDebug > 2) {
803 IfTrace3(TRUE,"SortSwath(anchor=%z, edge=%z, fcn=%x)\n",
804 anchor, edge, swathfcn);
807 IfTrace3(TRUE,"SortSwath(anchor=%x, edge=%x, fcn=%x)\n",
808 anchor, edge, swathfcn);
815 before->ymin = before->ymax = MINPEL;
816 before->link = after = anchor;
819 If the incoming edge is above the current list, we connect the current
820 list to the bottom of the incoming edge. One slight complication is
821 if the incoming edge overlaps into the current list. Then, we
822 first split the incoming edge in two at the point of overlap and recursively
823 call ourselves to sort the bottom of the split into the current list:
825 if (TOP(edge) < TOP(after)) {
826 if (BOTTOM(edge) > TOP(after)) {
828 after = SortSwath(after, splitedge(edge, TOP(after)), swathfcn);
830 vertjoin(edge, after);
834 At this point the top of edge is not higher than the top of the list,
835 which we keep in 'after'. We move the 'after' point down the list,
836 until the top of the edge occurs in the swath beginning with 'after'.
838 If the bottom of 'after' is below the bottom of the edge, we have to
839 split the 'after' swath into two parts, at the bottom of the edge.
840 If the bottom of 'after' is above the bottom of the swath,
843 while (VALIDEDGE(after)) {
845 if (TOP(after) == TOP(edge)) {
846 if (BOTTOM(after) > BOTTOM(edge))
847 vertjoin(after, splitedge(after, BOTTOM(edge)));
848 else if (BOTTOM(after) < BOTTOM(edge)) {
849 after = SortSwath(after,
850 splitedge(edge, BOTTOM(after)), swathfcn);
854 else if (TOP(after) > TOP(edge)) {
855 IfTrace0((BOTTOM(edge) < TOP(after) && RegionDebug > 0),
856 "SortSwath: disjoint edges\n");
857 if (BOTTOM(edge) > TOP(after)) {
858 after = SortSwath(after,
859 splitedge(edge, TOP(after)), swathfcn);
863 else if (BOTTOM(after) > TOP(edge))
864 vertjoin(after, splitedge(after, TOP(edge)));
871 At this point 'edge' exactly corresponds in height to the current
872 swath pointed to by 'after'.
874 if (after != NULL && TOP(after) == TOP(edge)) {
875 before = (*swathfcn)(before, edge);
876 after = before->link;
879 At this point 'after' contains all the edges after 'edge', and 'before'
880 contains all the edges before. Whew! A simple matter now of adding
881 'edge' to the linked list in its rightful place:
884 if (RegionDebug > 1) {
885 IfTrace3(TRUE,"SortSwath: in between %x and %x are %x",
886 before, after, edge);
887 while (edge->link != NULL) {
889 IfTrace1(TRUE," and %x", edge);
894 for (; edge->link != NULL; edge = edge->link) { ; }
901 :h3.splitedge() - Split an Edge or Swath in Two at a Given Y Value
903 This function returns the edge or swath beginning at the Y value, and
904 is guaranteed not to change the address of the old swath while splitting
908 static struct edgelist *splitedge(list, y)
909 struct edgelist *list; /* area to split */
910 register pel y; /* Y value to split list at */
912 register struct edgelist *new; /* anchor for newly built list */
913 register struct edgelist *last; /* end of newly built list */
914 register struct edgelist *r; /* temp pointer to new structure */
915 register struct edgelist *lastlist; /* temp pointer to last 'list' value */
917 IfTrace2((RegionDebug > 1),"splitedge of %x at %d ", list, (long) y);
919 lastlist = new = NULL;
921 while (list != NULL) {
925 abort("splitedge: above top of list");
927 abort("splitedge: would be null");
929 r = (struct edgelist *)Allocate(sizeof(struct edgelist), list, 0);
931 At this point 'r' points to a copy of the single structure at 'list'.
932 We will make 'r' be the new split 'edgelist'--the lower half.
933 We don't bother to correct 'xmin' and 'xmax', we'll take the
934 the pessimistic answer that results from using the old values.
937 r->xvalues = list->xvalues + (y - list->ymin);
939 Note that we do not need to allocate new memory for the X values,
940 they can remain with the old "edgelist" structure. We do have to
941 update that old structure so it is not as high:
945 Insert 'r' in the subpath chain:
947 r->subpath = list->subpath;
950 Now attach 'r' to the list we are building at 'new', and advance
951 'list' to point to the next element in the old list:
962 At this point we have a new list built at 'new'. We break the old
963 list at 'lastlist', and add the broken off part to the end of 'new'.
964 Then, we return the caller a pointer to 'new':
967 abort("null splitedge");
968 lastlist->link = NULL;
970 IfTrace1((RegionDebug > 1),"yields %x\n", new);
975 :h3.vertjoin() - Join Two Disjoint Edge Lists Vertically
977 The two edges must be disjoint vertically.
979 static void vertjoin(top, bottom)
980 register struct edgelist *top; /* uppermost region */
981 register struct edgelist *bottom; /* bottommost region */
983 if (BOTTOM(top) > TOP(bottom))
984 abort("vertjoin not disjoint");
986 for (; top->link != NULL; top=top->link) { ; }
993 :h3.swathxsort() - Sorting by X Values
995 We need to sort 'edge' into its rightful
996 place in the swath by X value, taking care that we do not accidentally
997 advance to the next swath while searching for the correct X value. Like
998 all swath functions, this function returns a pointer to the edge
999 BEFORE the given edge in the sort.
1002 static struct edgelist *swathxsort(before0, edge)
1003 register struct edgelist *before0; /* edge before this swath */
1004 register struct edgelist *edge; /* input edge */
1006 register struct edgelist *before;
1007 register struct edgelist *after;
1011 after = before->link;
1013 while (after != NULL && TOP(after) == TOP(edge)) {
1015 register pel *x1,*x2;
1018 x1 = after->xvalues;
1021 while (y < BOTTOM(edge) && *x1 == *x2) {
1024 if (y >= BOTTOM(edge)) {
1025 edge->flag |= ISAMBIGUOUS(ON);
1026 after->flag |= ISAMBIGUOUS(ON);
1034 after = after->link;
1038 At this point, 'edge' is between 'before' and 'after'. If 'edge' didn't
1039 cross either of those other edges, we would be done. We check for
1040 crossing. If it does cross, we split the problem up by calling SortSwath
1041 recursively with the part of the edge that is below the crossing point:
1044 register int h0,h; /* height of edge--number of scans */
1046 h0 = h = BOTTOM(edge) - y;
1050 IfTrace0((RegionDebug>0),"swathxsort: exactly equal edges\n");
1054 if (TOP(before) == TOP(edge))
1055 h -= crosses(h, &before->xvalues[y], &edge->xvalues[y]);
1056 if (after != NULL && TOP(after) == TOP(edge))
1057 h -= crosses(h, &edge->xvalues[y], &after->xvalues[y]);
1060 SortSwath(before0->link,
1061 splitedge(edge, TOP(edge) + y + h),
1070 :h3.SwathUnion() - Union Two Edges by X Value
1072 We have a left and right edge that must be unioned into a growing
1073 swath. If they are totally disjoint, they are just added in. The
1074 fun comes in they overlap the existing edges. Then some edges
1078 struct edgelist *SwathUnion(before0, edge)
1079 register struct edgelist *before0; /* edge before the swath */
1080 register struct edgelist *edge; /* list of two edges to be unioned */
1082 register int h; /* saves height of edge */
1083 register struct edgelist *rightedge; /* saves right edge of 'edge' */
1084 register struct edgelist *before,*after; /* edge before and after */
1085 int h0; /* saves initial height */
1087 IfTrace2((RegionDebug > 1),"SwathUnion entered, before=%x, edge=%x\n",
1090 h0 = h = edge->ymax - edge->ymin;
1092 abort("SwathUnion: 0 height swath?");
1095 after = before->link;
1097 while (after != NULL && TOP(after) == TOP(edge)) {
1098 register struct edgelist *right;
1100 right = after->link;
1101 if (right->xvalues[0] >= edge->xvalues[0])
1104 after = before->link;
1107 This is the picture at this point. 'L' indicates a left hand edge,
1108 'R' indicates the right hand edge.
1109 '<--->' indicates the degree of uncertainty as to its placement
1110 relative to other edges:
1113 R <---L----> R L R L R
1114 <---L---> <------R-------------------------->
1117 In case the left of 'edge' touches 'before', we need to reduce
1118 the height by that amount.
1120 if (TOP(before) == TOP(edge))
1121 h -= touches(h, before->xvalues, edge->xvalues);
1123 rightedge = edge->link;
1125 if (after == NULL || TOP(after) != TOP(edge) ||
1126 after->xvalues[0] > rightedge->xvalues[0]) {
1127 IfTrace2((RegionDebug > 1),
1128 "SwathUnion starts disjoint: before=%x after=%x\n",
1131 On this side of the the above 'if', the new edge is disjoint from the
1132 existing edges in the swath. This is the picture:
1139 We will verify it remains disjoint for the entire height. If the
1140 situation changes somewhere down the edge, we split the edge at that
1141 point and recursively call ourselves (through 'SortSwath') to figure
1142 out the new situation:
1144 if (after != NULL && TOP(after) == TOP(edge))
1145 h -= touches(h, rightedge->xvalues, after->xvalues);
1147 SortSwath(before0->link, splitedge(edge, edge->ymin + h), t1_SwathUnion);
1148 /* go to "return" this edge pair; it is totally disjoint */
1152 At this point, at the 'else', we know that the
1153 new edge overlaps one or more pairs in the existing swath. Here is
1154 a picture of our knowledge and uncertainties:
1158 <---L---> <---R------------------->
1161 We need to move 'after' along until it is to the right of the
1162 right of 'edge'. ('After' should always point to a left edge of a pair:)
1164 register struct edgelist *left; /* variable to keep left edge in */
1168 after = (after->link)->link;
1170 } while (after != NULL && TOP(after) == TOP(edge)
1171 && after->xvalues[0] <= rightedge->xvalues[0]);
1173 At this point this is the picture:
1180 We need to verify that the situation stays like this all the way
1181 down the edge. Again, if the
1182 situation changes somewhere down the edge, we split the edge at that
1183 point and recursively call ourselves (through 'SortSwath') to figure
1184 out the new situation:
1187 h -= crosses(h, left->xvalues, rightedge->xvalues);
1188 h -= crosses(h, edge->xvalues, ((before->link)->link)->xvalues);
1190 if (after != NULL && TOP(after) == TOP(edge))
1192 h -= touches(h, rightedge->xvalues, after->xvalues);
1194 IfTrace3((RegionDebug > 1),
1195 "SwathUnion is overlapped until %d: before=%x after=%x\n",
1196 (long) TOP(edge) + h, before, after);
1198 OK, if we touched either of our neighbors we need to split at that point
1199 and recursively sort the split edge onto the list. One tricky part
1200 is that when we recursively sort, 'after' will change if it was not
1201 in our current swath:
1204 SortSwath(before0->link,
1205 splitedge(edge, edge->ymin + h),
1208 if (after == NULL || TOP(after) != TOP(edge))
1209 for (after = before0->link;
1210 TOP(after) == TOP(edge);
1211 after = after->link) { ; }
1214 Now we need to augment 'edge' by the left and right of the overlapped
1215 swath, and to discard all edges between before and after, because they
1216 were overlapped and have been combined with the new incoming 'edge':
1218 edge->xmin = MIN(edge->xmin, (before->link)->xmin);
1219 edge->xmax = MIN(edge->xmax, (before->link)->xmax);
1220 edgemin(h, edge->xvalues, (before->link)->xvalues);
1221 rightedge->xmin = MAX(rightedge->xmin, (left->link)->xmin);
1222 rightedge->xmax = MAX(rightedge->xmax, (left->link)->xmax);
1223 edgemax(h, rightedge->xvalues, (left->link)->xvalues);
1224 discard(before, after);
1229 :h3.swathrightmost() - Simply Sorts New Edge to Rightmost of Swath
1231 Like all swath functions, this function returns a pointer to the edge
1232 BEFORE the given edge in the sort.
1235 static struct edgelist *swathrightmost(before, edge)
1236 register struct edgelist *before; /* edge before this swath */
1237 register struct edgelist *edge; /* input edge */
1239 register struct edgelist *after;
1241 after = before->link;
1243 while (after != NULL && TOP(after) == TOP(edge)) {
1245 after = after->link;
1252 :h3.touches() - Returns the Remaining Height When Two Edges Touch
1254 So, it will return 0 if they never touch. Allows incredibly(?) mnemonic
1255 if (touches(...)) construct.
1258 static int touches(h, left, right)
1260 register pel *left,*right;
1263 if (*left++ >= *right++)
1268 :h3.crosses() - Returns the Remaining Height When Two Edges Cross
1270 So, it will return 0 if they never cross.
1273 static int crosses(h, left, right)
1275 register pel *left,*right;
1278 if (*left++ > *right++)
1283 :h3.cedgemin() - Stores the Mininum of an Edge and an X Value
1286 static void cedgemin(h, e1, x)
1291 for (; --h >= 0; e1++)
1296 :h3.cedgemax() - Stores the Maximum of an Edge and an X Value
1299 static void cedgemax(h, e1, x)
1304 for (; --h >= 0; e1++)
1309 :h3.edgemin() - Stores the Mininum of Two Edges in First Edge
1312 static void edgemin(h, e1, e2)
1314 register pel *e1,*e2;
1316 for (; --h >= 0; e1++,e2++)
1321 :h3.edgemax() - Stores the Maximum of Two Edges in First Edge
1324 static void edgemax(h, e1, e2)
1326 register pel *e1,*e2;
1328 for (; --h >= 0; e1++,e2++)
1333 :h3 id=discard.discard() - Discard All Edges Between Two Edges
1335 At first glance it would seem that we could discard an edgelist
1336 structure merely by unlinking it from the list and freeing it. You are
1337 wrong, region-breath! For performance, the X values associated with an
1338 edge are allocated contiguously with it. So, we free the X values when
1339 we free a structure. However, once an edge has been split, we are no
1340 longer sure which control block actually is part of the memory block
1341 that contains the edges. Rather than trying to decide, we play it safe
1342 and never free part of a region.
1344 So, to mark a 'edgelist' structure as discarded, we move it to the end
1345 of the list and set ymin=ymax.
1348 static discard(left, right)
1349 register struct edgelist *left,*right; /* all edges between here exclusive */
1350 /* should be discarded */
1352 register struct edgelist *beg,*end,*p;
1354 IfTrace2((RegionDebug > 0),"discard: l=%x, r=%x\n", left, right);
1360 for (p = beg; p != right; p = p->link) {
1361 if (p->link == NULL && right != NULL)
1362 abort("discard(): ran off end");
1363 IfTrace1((RegionDebug > 0),"discarding %x\n", p);
1364 p->ymin = p->ymax = 32767;
1368 * now put the chain beg/end at the end of right, if it is not
1371 if (right != NULL) {
1373 while (right->link != NULL)
1374 right = right->link;
1381 :h2.Changing the Representation of Regions
1383 For convenience and/or performance, we sometimes like to change the way
1384 regions are represented. This does not change the object itself, just
1385 the representation, so these transformations can be made on a permanent
1390 void MoveEdges(R, dx, dy)
1391 register struct region *R; /* region to modify */
1392 register fractpel dx,dy; /* delta X and Y to move edge list by */
1394 register struct edgelist *edge; /* for looping through edges */
1400 if (R->thresholded != NULL) {
1401 R->thresholded->origin.x -= dx;
1402 R->thresholded->origin.y -= dy;
1405 From now on we will deal with dx and dy as integer pel values:
1407 dx = NEARESTPEL(dx);
1408 dy = NEARESTPEL(dy);
1409 if (dx == 0 && dy == 0)
1417 for (edge = R->anchor; VALIDEDGE(edge); edge = edge->link) {
1421 register int h; /* loop index; height of edge */
1422 register pel *Xp; /* loop pointer to X values */
1426 for (Xp = edge->xvalues, h = edge->ymax - edge->ymin;
1434 :h3.UnJumble() - Sort a Region Top to Bottom
1436 It is an open question whether it pays in general to do this.
1439 void UnJumble(region)
1440 struct region *region; /* region to sort */
1442 register struct edgelist *anchor; /* new lists built here */
1443 register struct edgelist *edge; /* edge pointer for loop */
1444 register struct edgelist *next; /* ditto */
1448 for (edge=region->anchor; VALIDEDGE(edge); edge=next) {
1449 if (edge->link == NULL)
1450 abort("UnJumble: unpaired edge?");
1451 next = edge->link->link;
1452 edge->link->link = NULL;
1453 anchor = SortSwath(anchor, edge, t1_SwathUnion);
1457 vertjoin(anchor, edge);
1459 region->anchor = anchor;
1460 region->flag &= ~ISJUMBLED(ON);
1466 static OptimizeRegion(R)
1467 struct region *R; /* region to optimize */
1469 register pel *xP; /* pel pointer for inner loop */
1470 register int x; /* holds X value */
1471 register int xmin,xmax; /* holds X range */
1472 register int h; /* loop counter */
1473 register struct edgelist *e; /* edgelist pointer for loop */
1475 R->flag |= ISRECTANGULAR(ON);
1477 for (e = R->anchor; VALIDEDGE(e); e=e->link) {
1480 for (h = e->ymax - e->ymin, xP = e->xvalues; --h >= 0;) {
1482 if (x < xmin) xmin = x;
1483 if (x > xmax) xmax = x;
1485 if (xmin != xmax || (xmin != R->xmin && xmax != R->xmax))
1486 R->flag &= ~ISRECTANGULAR(ON);
1487 if (xmin < e->xmin || xmax > e->xmax)
1488 abort("Tighten: existing edge bound was bad");
1489 if (xmin < R->xmin || xmax > R->xmax)
1490 abort("Tighten: existing region bound was bad");
1494 R->flag |= ISOPTIMIZED(ON);
1498 :h2.Miscelaneous Routines
1500 :h3.MoreWorkArea() - Allocate New Space for "edge"
1502 Our strategy is to temporarily allocate an array to hold this
1503 unexpectedly large edge. ChangeDirection frees this array any time
1504 it gets a shorter 'dy'.
1508 void MoreWorkArea(R, x1, y1, x2, y2)
1509 struct region *R; /* region we are generating */
1510 fractpel x1,y1; /* starting point of line */
1511 fractpel x2,y2; /* ending point of line */
1513 register int idy; /* integer dy of line */
1515 idy = NEARESTPEL(y1) - NEARESTPEL(y2);
1516 if (idy < 0) idy = - idy;
1519 * we must add one to the delta for the number of run ends we
1522 if (++idy > currentsize) {
1523 IfTrace1((RegionDebug > 0),"Allocating edge of %d pels\n", idy);
1524 if (currentworkarea != workedge)
1525 NonObjectFree(currentworkarea);
1526 currentworkarea = (pel *)Allocate(0, NULL, idy * sizeof(pel));
1529 ChangeDirection(CD_CONTINUE, R, x1, y1, y2 - y1);
1533 :h3.BoxClip() - Clip a Region to a Rectangle
1535 BoxClip also duplicates the region if it is permanent. Note the
1536 clipping box is specified in REGION coordinates, that is, in
1537 coordinates relative to the region (0,0) point
1540 struct region *BoxClip(R, xmin, ymin, xmax, ymax)
1541 register struct region *R; /* region to clip */
1542 register pel xmin,ymin; /* upper left hand corner of rectangle */
1543 register pel xmax,ymax; /* lower right hand corner */
1545 struct edgelist anchor; /* pretend edgelist to facilitate discards */
1546 register struct edgelist *e,*laste;
1548 IfTrace1((OffPageDebug),"BoxClip of %z:\n", R);
1550 R = UniqueRegion(R);
1552 if (xmin > R->xmin) {
1553 IfTrace2((OffPageDebug),"BoxClip: left clip old %d new %d\n",
1554 (long) R->xmin, (long) xmin);
1557 if (xmax < R->xmax) {
1558 IfTrace2((OffPageDebug),"BoxClip: right clip old %d new %d\n",
1559 (long) R->xmax, (long) xmax);
1563 if (ymin > R->ymin) {
1564 IfTrace2((OffPageDebug),"BoxClip: top clip old %d new %d\n",
1565 (long) R->ymin, (long) ymin);
1568 if (ymax < R->ymax) {
1569 IfTrace2((OffPageDebug),"BoxClip: bottom clip old %d new %d\n",
1570 (long) R->ymax, (long) ymax);
1576 anchor.link = R->anchor;
1578 for (e = R->anchor; VALIDEDGE(e); e = e->link) {
1579 if (TOP(e) < ymin) {
1580 e->xvalues += ymin - e->ymin;
1583 if (BOTTOM(e) > ymax)
1585 if (TOP(e) >= BOTTOM(e)) {
1586 discard(laste, e->link->link);
1590 if (e->xmin < xmin) {
1591 cedgemax(BOTTOM(e) - TOP(e), e->xvalues, xmin);
1593 e->xmax = MAX(e->xmax, xmin);
1595 if (e->xmax > xmax) {
1596 cedgemin(BOTTOM(e) - TOP(e), e->xvalues, xmax);
1597 e->xmin = MIN(e->xmin, xmax);
1603 R->anchor = anchor.link;
1610 :h3.CoerceRegion() - Force a TextPath Structure to Become a Region
1612 We also save the newly created region in the textpath structure, if the
1613 structure was permanent. Then we don't have to do this again. Why not
1614 save it all the time? Well, we certainly could, but I suspect it
1615 wouldn't pay. We would have to make this region permanent (because we
1616 couldn't have it be consumed) and this would probably require
1617 unnecessary CopyRegions in most cases.
1620 struct region *CoerceRegion(tp)
1621 register struct textpath *tp; /* input TEXTTYPE */
1623 struct segment *path; /* temporary character path */
1624 struct region *R; /* returned region */
1627 R = Interior(path, EVENODDRULE);
1633 :h3.RegionBounds() - Returns Bounding Box of a Region
1636 struct segment *RegionBounds(R)
1637 register struct region *R;
1639 extern struct XYspace *IDENTITY;
1641 register struct segment *path; /* returned path */
1643 path = BoxPath(IDENTITY, R->ymax - R->ymin, R->xmax - R->xmin);
1644 path = Join(PathSegment(MOVETYPE, R->origin.x + TOFRACTPEL(R->xmin),
1645 R->origin.y + TOFRACTPEL(R->ymin) ),
1651 :h2.Formatting/Dump Routines for Debug
1653 :h3.DumpArea() - Display a Region
1656 register struct region *area;
1658 IfTrace1(TRUE,"Dumping area %x,", area);
1659 IfTrace4(TRUE," X %d:%d Y %d:%d;", (long) area->xmin,
1660 (long) area->xmax, (long) area->ymin,(long) area->ymax);
1661 IfTrace4(TRUE," origin=(%p,%p), ending=(%p,%p)\n",
1662 area->origin.x, area->origin.y, area->ending.x, area->ending.y);
1663 DumpEdges(area->anchor);
1666 #define INSWATH(p, y0, y1) (p != NULL && p->ymin == y0 && p->ymax == y1)
1668 :h3.DumpEdges() - Display Run End Lists (Edge Lists)
1671 static pel RegionDebugYMin = MINPEL;
1672 static pel RegionDebugYMax = MAXPEL;
1674 void DumpEdges(edges)
1675 register struct edgelist *edges;
1677 register struct edgelist *p,*p2;
1678 register pel ymin = MINPEL;
1679 register pel ymax = MINPEL;
1682 if (edges == NULL) {
1683 IfTrace0(TRUE," NULL area.\n");
1686 if (RegionDebug <= 1) {
1687 for (p=edges; p != NULL; p = p->link) {
1688 edgecheck(p, ymin, ymax);
1689 ymin = p->ymin; ymax = p->ymax;
1690 IfTrace3(TRUE,". at %x type=%d flag=%x",
1691 p, (long) p->type,(long) p->flag);
1692 IfTrace4(TRUE," bounding box HxW is %dx%d at (%d,%d)\n",
1693 (long) ymax - ymin, (long) p->xmax - p->xmin,
1694 (long) p->xmin, (long) ymin);
1699 for (p2=edges; p2 != NULL; ) {
1701 edgecheck(p2, ymin, ymax);
1705 if (RegionDebug > 3 || (ymax > RegionDebugYMin
1706 && ymin < RegionDebugYMax)) {
1707 IfTrace2 (TRUE,". Swath from %d to %d:\n",
1709 for (p=p2; INSWATH(p,ymin,ymax); p = p->link) {
1710 IfTrace4(TRUE,". . at %x[%x] range %d:%d, ",
1712 (long) p->xmin, (long)p->xmax);
1713 IfTrace1(TRUE, "subpath=%x,\n", p->subpath);
1716 for (y=MAX(ymin,RegionDebugYMin); y < MIN(ymax, RegionDebugYMax); y++) {
1717 IfTrace1(TRUE,". . . Y[%5d] ", (long) y);
1718 for (p=p2; INSWATH(p,ymin,ymax); p = p->link)
1719 IfTrace1(TRUE,"%5d ",
1720 (long) p->xvalues[y - ymin]);
1721 IfTrace0(TRUE,"\n");
1723 while (INSWATH(p2, ymin, ymax))
1730 :h3.edgecheck() - For Debug, Verify that an Edge Obeys the Rules
1734 static edgecheck(edge, oldmin, oldmax)
1735 struct edgelist *edge;
1738 if (edge->type != EDGETYPE)
1739 abort("EDGE ERROR: non EDGETYPE in list");
1741 The following check is not valid if the region is jumbled so I took it
1744 /* if (edge->ymin < oldmax && edge->ymin != oldmin)
1745 abort("EDGE ERROR: overlapping swaths"); */