1 /* $XConsortium: regions.c,v 1.4 91/10/10 11:18:57 rws Exp $ */
2 /* Copyright International Business Machines, Corp. 1991
3 * All Rights Reserved
4 * Copyright Lexmark International, Inc. 1991
5 * All Rights Reserved
6 *
7 * License to use, copy, modify, and distribute this software and its
8 * documentation for any purpose and without fee is hereby granted,
9 * provided that the above copyright notice appear in all copies and that
10 * both that copyright notice and this permission notice appear in
11 * supporting documentation, and that the name of IBM or Lexmark not be
12 * used in advertising or publicity pertaining to distribution of the
13 * software without specific, written prior permission.
14 *
15 * IBM AND LEXMARK PROVIDE THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES OF
16 * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO ANY
17 * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
18 * AND NONINFRINGEMENT OF THIRD PARTY RIGHTS. THE ENTIRE RISK AS TO THE
19 * QUALITY AND PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT
20 * OR MAINTAIN, BELONGS TO THE LICENSEE. SHOULD ANY PORTION OF THE
21 * SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM OR LEXMARK) ASSUMES THE
22 * ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION. IN NO EVENT SHALL
23 * IBM OR LEXMARK BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
24 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
25 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
26 * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
27 * THIS SOFTWARE.
28 */
29 /* REGIONS CWEB V0023 LOTS */
30 /*
31 :h1 id=regions.REGIONS Module - Regions Operator Handler
32
33 This module is responsible for creating and manipulating regions.
34
35 &author. Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com)
36
37
38 :h3.Include Files
39
40 The included files are:
41 */
42
43 #include <stdio.h>
44 #include <stdlib.h>
45
46 #include "types.h"
47 #include "objects.h"
48 #include "spaces.h"
49 #include "paths.h"
50 #include "regions.h"
51 #include "curves.h"
52 #include "lines.h"
53 #include "pictures.h"
54 #include "fonts.h"
55 #include "hints.h"
56 #include "strokes.h" /* to pick up 'DoStroke' */
57 static int Unwind();
58 static int newfilledge();
59 static struct edgelist *splitedge();
60 static int vertjoin();
61 static int touches();
62 static int crosses();
63 static int edgemin();
64 static int edgemax();
65 static int discard();
66 static int edgecheck();
67 static struct edgelist *NewEdge();
68 struct edgelist *swathxsort(); /* 'SortSwath' function */
69 extern struct XYspace *IDENTITY;
70
71 /*
72 :h3.Functions Provided to the TYPE1IMAGER User
73
74 This module provides the following TYPE1IMAGER entry points:
75 */
76
77 /*SHARED LINE(S) ORIGINATED HERE*/
78 /*
79 :h3.Functions Provided to Other Modules
80
81 This module provides the following entry points to other modules:
82 */
83
84 /*SHARED LINE(S) ORIGINATED HERE*/
85 /*
86 :h3.Macros Provided to Other Modules
87
88 :h4.GOING_TO() - Macro Predicate Needed for Changing Direction, Etc.
89
90 The actual generation of run end lists (edge boundaries) is left
91 to the low level rasterizing modules, LINES and CURVES. There
92 are some global region-type
93 questions that occur when doing a low-level
94 rasterization:
95 :ol.
96 :li.Did we just change direction in Y and therefore need to start
97 a new edge?
98 :li.Did we run out of allocated edge space?
99 :li.Do the minimum or maximum X values for the current edge need
100 updating?
101 :eol.
102 In general the REGIONS is not smart enough to answer those questions
103 itself. (For example, determining if and when a curve changes direction
104 may need detailed curve knowledge.) Yet, this must be done efficiently.
105 We provide a macro "GOING_TO" where the invoker tells us where it is
106 heading for (x2,y2), plus where it is now (x1,y1), plus the current
107 region under construction, and the macro answers the questions above.
108 */
109
110 /*SHARED LINE(S) ORIGINATED HERE*/
111 /*
112 :h2.Data Structures Used to Represent Regions
113
114 :h3.The "region" Structure
115
116 The region structure is an anchor for a linked list of "edgelist"
117 structures (see :hdref refid=edgelist..). It also summarizes the
118 information in the edgelist structures (for example, the bounding
119 box of the region). And, it contains scratch areas used during
120 the creation of a region.
121 */
122
123 /*SHARED LINE(S) ORIGINATED HERE*/
124 /*
125 The ISOPTIMIZED flag tells us if we've put a permanent region in
126 'optimal' form.
127 */
128 #define ISOPTIMIZED(flag) ((flag)&0x10)
129
130 /*
131 The ISRECTANGULAR flag tells us if a region is a rectangle. We don't
132 always notice rectangles--if this flag is set, the region definitely
133 is a rectangle, but some rectangular regions will not have the flag
134 set. The flag is used to optimize some paths.
135 */
136
137 /*SHARED LINE(S) ORIGINATED HERE*/
138 /*
139 :h4."INFINITY" - A Constant Region Structure of Infinite Extent
140
141 Infinity is the complement of a null area:
142 Note - removed the refcount = 1 init, replaced with references = 2 3-26-91 PNM
143 */
144 static struct region infinity = { REGIONTYPE,
145 ISCOMPLEMENT(ON)+ISINFINITE(ON)+ISPERMANENT(ON)+ISIMMORTAL(ON), 2,
146 {0, 0}, {0, 0},
147 0, 0, 0, 0,
148 NULL, NULL,
149 0, 0, 0, 0, 0, NULL, NULL,
150 NULL, 0, NULL, NULL };
151 /* we rename INFINITY to T1_INFINITY. Anyhow it is currently not used */
152 struct region *T1_INFINITY = &infinity;
153
154 /*
155 :h4."EmptyRegion" - A Region Structure with Zero Area
156
157 This structure is used to initialize the region to be built in
158 Interior():
159 Note - replaced refcount = 1 init with references = 2 3-26-91 PNM
160 */
161
162 /*SHARED LINE(S) ORIGINATED HERE*/
163 struct region EmptyRegion = { REGIONTYPE,
164 ISPERMANENT(ON)+ISIMMORTAL(ON), 2,
165 {0, 0}, {0, 0},
166 MAXPEL, MAXPEL, MINPEL, MINPEL,
167 NULL, NULL,
168 0, 0, 0, 0, 0, NULL, NULL,
169 NULL, 0, NULL, NULL };
170
171 /*
172 :h3 id=edgelist.The "edgelist" Structure
173
174 Regions are represented by a linked list of 'edgelist' structures.
175 When a region is complete, the structures are paired, one for the
176 left and one for the right edge. While a region is being built,
177 this rule may be violated temporarily.
178
179 An 'edgelist' structure contains the X values for a given span
180 of Y values. The (X,Y) pairs define an edge. We use the crack
181 and edge coordinate system, so that integer values of X and Y
182 go between pels. The edge is defined between the minimum Y and
183 maximum Y.
184
185 The linked list is kept sorted from top to bottom, that is, in
186 increasing y. Also, if 'e1' is an edgelist structure and 'e2' is the
187 next one in the list, they must have exactly the same ymin,ymax values
188 or be totally disjoint. These two requirements mean that if e2's ymin
189 is less than e1's ymax, it must be exactly equal to e1's ymin. A
190 sublist of structures with identical ymin and ymax values is called a
191 'swath'.
192
193 In addition, edgelist structures are separately linked together based
194 on what subpath originally created them; each subpath is kept as a
195 separate circular linked list. This information is ignored unless
196 continuity checking is invoked. See :hdref refid=subpath. for a
197 complete description of this.
198 */
199
200
201 /*SHARED LINE(S) ORIGINATED HERE*/
202
203 /*
204 The "edgelist" structure follows the convention of TYPE1IMAGER user
205 objects, having a type field and a flag field as the first two
206 elements. However, the user never sees "edgelist" structures
207 directly; he is given handles to "region" structures only.
208
209 By having a type field, we can use the "copy" feature of Allocate()
210 to duplicate edge lists quickly.
211
212 We also define two flag bits for this structure. The ISDOWN bit is set
213 if the edge is going in the direction of increasing Y. The ISAMBIGUOUS
214 bit is set if the edge is identical to its neighbor (edge->link); such
215 edges may be "left" when they should be "right", or vice versa,
216 unnecessarily confusing the continuity checking logic. The FixSubPaths()
217 routine in HINTS will swap ambiguous edges if that avoids crossing edges;
218 see :hdref refid=fixsubp..
219 */
220
221 /*SHARED LINE(S) ORIGINATED HERE*/
222
223 /*
224 :h3.KillRegion() - Destroys a Region
225
226 KillRegion nominally just decrements the reference count to that region.
227 If the reference count becomes 0, all memory associated with it is
228 freed. We just follow the linked list, freeing as we go, then kill any
229 associated (thresholded) picture.
230 Note - added conditional return based on references 3-26-91 PNM
231 */
232
KillRegion(area)233 void KillRegion(area)
234 register struct region *area; /* area to free */
235 {
236 register struct edgelist *p; /* loop variable */
237 register struct edgelist *next; /* loop variable */
238
239 if (area->references < 0)
240 abort("KillRegion: negative reference count", 28);
241 if ( (--(area->references) > 1) ||
242 ( (area->references == 1) && !ISPERMANENT(area->flag) ) )
243 return;
244
245 for (p=area->anchor; p != NULL; p=next) {
246 next = p->link;
247 Free(p);
248 }
249 /* KillPicture-macro removed from sources (RMz, 2001-04-01)
250 if (area->thresholded != NULL)
251 KillPicture(area->thresholded);
252 */
253 Free(area);
254 }
255 /*
256 :h3.CopyRegion() - Makes a Copy of a Region
257 */
CopyRegion(area)258 struct region *CopyRegion(area)
259 register struct region *area; /* region to duplicate */
260 {
261 register struct region *r; /* output region built here */
262 register struct edgelist *last=NULL; /* loop variable */
263 register struct edgelist *p,*newp; /* loop variables */
264
265 r = (struct region *)Allocate(sizeof(struct region), area, 0);
266 r->anchor = NULL;
267
268 for (p=area->anchor; VALIDEDGE(p); p=p->link) {
269
270 newp = NewEdge(p->xmin, p->xmax, p->ymin, p->ymax, p->xvalues, ISDOWN(p->flag));
271 newp->fpx1 = p->fpx1;
272 newp->fpx2 = p->fpx2;
273 newp->fpy1 = p->fpy1;
274 newp->fpy2 = p->fpy2;
275
276 if (r->anchor == NULL)
277 r->anchor = last = newp;
278 else
279 last->link = newp;
280
281 last = newp;
282 }
283 if (area->thresholded != NULL)
284 /* replaced DupPicture with Dup() 3-26-91 PNM */
285 r->thresholded = (struct picture *)Dup(area->thresholded);
286 return(r);
287 }
288 /*
289 :h4.NewEdge() - Allocates and Returns a New "edgelist" Structure
290
291 We allocate space for the X values contiguously with the 'edgelist'
292 structure that locates them. That way, we only have to free the
293 edgelist structure to free all memory associated with it. Damn
294 clever, huh?
295 */
296
NewEdge(xmin,xmax,ymin,ymax,xvalues,isdown)297 static struct edgelist *NewEdge(xmin, xmax, ymin, ymax, xvalues, isdown)
298 pel xmin,xmax; /* X extent of edge */
299 pel ymin,ymax; /* Y extent of edge */
300 pel *xvalues; /* list of X values for entire edge */
301 int isdown; /* flag: TRUE means edge progresses downward */
302 {
303 static struct edgelist template = {
304 EDGETYPE, 0, 1, NULL, NULL,
305 0, 0, 0, 0, NULL };
306
307 register struct edgelist *r; /* returned structure */
308 register int iy; /* ymin adjusted for 'long' alignment purposes */
309
310 IfTrace2((RegionDebug),"....new edge: ymin=%d, ymax=%d ",
311 (LONG)ymin, (LONG) ymax);
312 if (ymin >= ymax)
313 abort("newedge: height not positive", 29);
314 /*
315 We are going to copy the xvalues into a newly allocated area. It
316 helps performance if the values are all "long" aligned. We can test
317 if the xvalues are long aligned by ANDing the address with the
318 (sizeof(long) - 1)--if non zero, the xvalues are not aligned well. We
319 set 'iy' to the ymin value that would give us good alignment:
320 */
321 iy = ymin - (((unsigned long) xvalues) & (sizeof(LONG) - 1)) / sizeof(pel);
322
323 r = (struct edgelist *)Allocate(sizeof(struct edgelist), &template,
324 (ymax - iy) * sizeof(pel));
325
326 if (isdown) r->flag = ISDOWN(ON);
327 r->xmin = xmin;
328 r->xmax = xmax;
329 r->ymin = ymin;
330 r->ymax = ymax;
331
332 r->xvalues = (pel *) FOLLOWING(r);
333 if (ymin != iy) {
334 r->xvalues += ymin - iy;
335 xvalues -= ymin - iy;
336 }
337
338 /*
339 We must round up (ymax - iy) so we get the ceiling of the number of
340 longs. The destination must be able to hold these extra bytes because
341 Allocate() makes everything it allocates be in multiples of longs.
342 */
343 LONGCOPY(&r[1], xvalues, (ymax - iy) * sizeof(pel) + sizeof(LONG) - 1);
344
345 IfTrace1((RegionDebug),"result=%p\n", r);
346 return(r);
347 }
348
349 /*
350 :h2.Building Regions
351
352 :h3.Interior() - Iterate Through a Path, Building a Region
353
354 This routine is the workhorse driver routine that iterates through a
355 path, calling the appropriate stepping routines to actually produce the
356 run end "edgelist" structures.
357
358 :ol.
359 :li."Interior" calls StepLine or StepConic or StepBezier as appropriate
360 to produce run ends.
361 :li.Occasionally these routines will notice a change in Y direction
362 and will call ChangeDirection (through the GOING_TO macro); this is
363 a call back to the REGIONS module.
364 :li.ChangeDirection will call whatever function is in the region
365 structure; for Interior, this function is 'newfilledge'.
366 :li.Newfilledge will call NewEdge to create a new edgelist structure,
367 then, call SortSwath to sort it onto the linked list being built at
368 the region "anchor".
369 :eol.
370
371 By making the function called by ChangeDirection be a parameter of the
372 region, we allow the same ChangeDirection logic to be used by stroking.
373 */
374
375 /*SHARED LINE(S) ORIGINATED HERE*/
376
Interior(p,fillrule)377 struct region *Interior(p, fillrule)
378 register struct segment *p; /* take interior of this path */
379 register int fillrule; /* rule to follow if path crosses itself */
380 {
381 register fractpel x,y; /* keeps ending point of path segment */
382 fractpel lastx,lasty; /* previous x,y from path segment before */
383 register struct region *R; /* region I will build */
384 register struct segment *nextP; /* next segment of path */
385 char tempflag; /* flag; is path temporary? */
386 char Cflag; /* flag; should we apply continuity? */
387
388 IfTrace2((MustTraceCalls),". INTERIOR(%p, %d)\n", p, (LONG) fillrule);
389
390 if (p == NULL)
391 return(NULL);
392 /*
393 Establish the 'Cflag' continuity flag based on user's fill rule and
394 our own 'Continuity' pragmatic (0: never do continuity, 1: do what
395 user asked, >1: do it regardless).
396 */
397 if (fillrule > 0) {
398 Cflag = Continuity > 0;
399 fillrule -= CONTINUITY;
400 }
401 else
402 Cflag = Continuity > 1;
403
404 ARGCHECK((fillrule != WINDINGRULE && fillrule != EVENODDRULE),
405 "Interior: bad fill rule", NULL, NULL, (1,p), struct region *);
406
407 if (p->type == TEXTTYPE)
408 /* if (fillrule != EVENODDRULE)
409 else */
410 return((struct region *)UniquePath(p));
411 if (p->type == STROKEPATHTYPE){
412 if (fillrule == WINDINGRULE)
413 return((struct region *)DoStroke(p));
414 else
415 p = CoercePath(p);
416 }
417
418
419 R = (struct region *)Allocate(sizeof(struct region), &EmptyRegion, 0);
420
421 ARGCHECK(!ISPATHANCHOR(p), "Interior: bad path", p, R, (0), struct region *);
422 ARGCHECK((p->type != MOVETYPE), "Interior: path not closed", p, R, (0), struct region *);
423
424
425 /* changed definition from !ISPERMANENT to references <= 1 3-26-91 PNM */
426 tempflag = (p->references <= 1); /* only first segment in path is so marked */
427 if (!ISPERMANENT(p->flag)) p->references -= 1;
428
429 R->newedgefcn = newfilledge;
430 /*
431 Believe it or not, "R" is now completely initialized. We are counting
432 on the copy of template to get other fields the way we want them,
433 namely
434 :ol.
435 :li.anchor = NULL
436 :li.xmin, ymin, xmax, ymax, to minimum and maximum values respectively.
437 :eol.
438 Anchor = NULL is very
439 important to ChangeDirection.
440 See :hdref refid=CD..
441
442 To minimize problems of "wrapping" in our pel arithmetic, we keep an
443 origin of the region which is the first move. Hopefully, that keeps
444 numbers within plus or minus 32K pels.
445 */
446 R->origin.x = 0/*TOFRACTPEL(NEARESTPEL(p->dest.x))*/;
447 R->origin.y = 0/*TOFRACTPEL(NEARESTPEL(p->dest.y))*/;
448 lastx = - R->origin.x;
449 lasty = - R->origin.y;
450 /*
451 ChangeDirection initializes other important fields in R, such as
452 lastdy, edge, edgeYstop, edgexmin, and edgexmax. The first segment
453 is a MOVETYPE, so it will be called first.
454 */
455 /*
456 Note: Hinting is completely performed in charspace coordinates
457 in the Type 1 module. Therefore, I have removed the code
458 to handle hint segments. (2002-08-11)
459 */
460
461 while (p != NULL) {
462
463 x = lastx + p->dest.x;
464 y = lasty + p->dest.y;
465
466 nextP = p->link;
467
468 switch(p->type) {
469
470 case LINETYPE:
471 StepLine(R, lastx, lasty, x, y);
472 break;
473
474 case CONICTYPE:
475 /* 2nd order Beziers not implemented! */
476 break;
477
478 case BEZIERTYPE:
479 {
480 register struct beziersegment *bp = (struct beziersegment *) p;
481
482 StepBezier(R, lastx, lasty,
483 lastx + bp->B.x, lasty + bp->B.y,
484 lastx + bp->C.x,
485 lasty + bp->C.y,
486 x, y);
487 }
488 break;
489
490 case MOVETYPE:
491 /* At this point we have encountered a MOVE segment. This breaks the
492 path, making it disjoint. */
493 if (p->last == NULL) /* i.e., not first in path */
494 ChangeDirection(CD_LAST, R, lastx, lasty, (fractpel) 0, (fractpel) 0, (fractpel) 0);
495
496 ChangeDirection(CD_FIRST, R, x, y, (fractpel) 0, (fractpel) 0, (fractpel) 0);
497 /* We'll just double check for closure here. We forgive an appended
498 MOVETYPE at the end of the path, if it isn't closed: */
499 if (!ISCLOSED(p->flag) && p->link != NULL)
500 return((struct region *)ArgErr("Fill: sub-path not closed", p, NULL));
501 break;
502
503 default:
504 abort("Interior: path type error", 30);
505 }
506 /* We're done with this segment. Advance to the next path segment in
507 the list, freeing this one if necessary: */
508 lastx = x; lasty = y;
509
510 if (tempflag)
511 Free(p);
512 p = nextP;
513 }
514 ChangeDirection(CD_LAST, R, lastx, lasty, (fractpel) 0, (fractpel) 0, (fractpel) 0);
515 R->ending.x = lastx;
516 R->ending.y = lasty;
517
518
519 /* Finally, clean up the region's based on the user's 'fillrule' request: */
520 if (Cflag)
521 ApplyContinuity(R);
522
523 if (fillrule == WINDINGRULE)
524 Unwind(R->anchor);
525
526 return R;
527 }
528
529
530 /*
531 :h4.Unwind() - Discards Edges That Fail the Winding Rule Test
532
533 The winding rule says that upward going edges should be paired with
534 downward going edges only, and vice versa. So, if two upward edges
535 or two downward edges are nominally left/right pairs, Unwind() should
536 discard the second one. Everything should balance; we should discard
537 an even number of edges; of course, we abort if we don't.
538 */
Unwind(area)539 static int Unwind(area)
540 register struct edgelist *area; /* input area modified in place */
541 {
542 register struct edgelist *last=NULL,*next; /* struct before and after current one */
543 register int y; /* ymin of current swath */
544 register int count,newcount; /* winding count registers */
545
546 IfTrace1((RegionDebug>0),"...Unwind(%p)\n", area);
547
548 while (VALIDEDGE(area)) {
549
550 count = 0;
551 y = area->ymin;
552
553 do {
554 next = area->link;
555
556 if (ISDOWN(area->flag))
557 newcount = count + 1;
558 else
559 newcount = count - 1;
560
561 if (count == 0 || newcount == 0)
562 last = area;
563 else
564 discard(last, next);
565
566 count = newcount;
567 area = next;
568
569 } while (area != NULL && area->ymin == y);
570
571 if (count != 0)
572 abort("Unwind: uneven edges", 31);
573 }
574 /* We retunr a value for ANSI-C-compiler */
575 return(0);
576
577 }
578 /*
579 :h3."workedge" Array
580
581 This is a statically allocated array where edges are built
582 before being copied into more permanent storage by NewEdge().
583 */
584
585 #ifndef MAXEDGE
586 #define MAXEDGE 1000
587 #endif
588
589 static pel workedge[MAXEDGE];
590 static pel *currentworkarea = workedge;
591 static pel currentsize = MAXEDGE;
592
593 /*
594 :h3 id=cd.ChangeDirection() - Called When Y Direction Changes
595
596 The rasterizing routines call this entry point when they detect
597 a change in Y. We then build the current edge and sort it into
598 emerging edgelist at 'anchor' by calling whatever "newedgefcn"
599 is appropriate.
600 */
601
ChangeDirection(type,R,x,y,dy,x2,y2)602 void ChangeDirection(type, R, x, y, dy, x2, y2)
603 int type; /* CD_FIRST, CD_CONTINUE, or CD_LAST */
604 register struct region *R; /* region in which we are changing direction */
605 fractpel x,y; /* current beginning x,y */
606 fractpel dy; /* direction and magnitude of change in y */
607 {
608 register fractpel ymin,ymax; /* minimum and maximum Y since last call */
609 register fractpel x_at_ymin,x_at_ymax; /* their respective X's */
610 register pel iy; /* nearest integer pel to 'y' */
611 register pel idy; /* nearest integer pel to 'dy' */
612 register int ydiff; /* allowed Y difference in 'currentworkarea' */
613
614 IfTrace4((RegionDebug>0),"Change Y direction (%d) from (%d,%d), dy=%d\n",
615 (LONG) type, x, y, dy);
616
617 if (type != CD_FIRST) {
618
619 if (R->lastdy > 0) {
620 ymin = R->firsty;
621 x_at_ymin = R->firstx;
622 ymax = y;
623 x_at_ymax = x;
624 }
625 else {
626 ymin = y;
627 x_at_ymin = x;
628 ymax = R->firsty;
629 x_at_ymax = R->firstx;
630 }
631
632 if (ymax < ymin)
633 abort("negative sized edge?", 32);
634
635
636 (*R->newedgefcn)(R, R->edgexmin, R->edgexmax, ymin, ymax,
637 R->lastdy > 0, x_at_ymin, x_at_ymax,
638 x, y, x2, y2);
639
640 }
641
642 R->firsty = y;
643 R->firstx = x;
644 R->lastdy = dy;
645
646 iy = NEARESTPEL(y);
647 idy = NEARESTPEL(dy);
648 if (currentworkarea != workedge && idy < MAXEDGE && idy > -MAXEDGE) {
649 NonObjectFree(currentworkarea);
650 currentworkarea = workedge;
651 currentsize = MAXEDGE;
652 }
653 ydiff = currentsize - 1;
654 if (dy > 0) {
655 R->edge = ¤tworkarea[-iy];
656 R->edgeYstop = TOFRACTPEL(ydiff + iy) + FPHALF;
657 }
658 else {
659 R->edge = ¤tworkarea[ydiff - iy];
660 R->edgeYstop = TOFRACTPEL(iy - ydiff) - FPHALF;
661 }
662 R->edgexmax = R->edgexmin = x;
663 /*
664 If this is the end of a subpath, we complete the subpath circular
665 chain:
666 */
667 if (type == CD_LAST && R->lastedge != NULL) {
668 register struct edgelist *e = R->firstedge;
669
670 while (e->subpath != NULL)
671 e = e->subpath;
672 e->subpath = R->lastedge;
673 R->lastedge = R->firstedge = NULL;
674 }
675 }
676 /*
677 :h3 id=newfill.newfilledge() - Called When We Have a New Edge While Filling
678
679 This is the prototypical "newedge" function passed to "Rasterize" and
680 stored in "newedgefcn" in the region being built.
681
682 If the edge is non-null, we sort it onto the list of edges we are
683 building at "anchor".
684
685 This function also has to keep the bounding box of the region
686 up to date.
687 */
688
newfilledge(R,xmin,xmax,ymin,ymax,isdown,x1,y1,x2,y2)689 static int newfilledge(R, xmin, xmax, ymin, ymax, isdown, x1, y1, x2, y2)
690 register struct region *R; /* region being built */
691 fractpel xmin,xmax; /* X range of this edge */
692 fractpel ymin,ymax; /* Y range of this edge */
693 int isdown; /* flag: TRUE means edge goes down, else up */
694 fractpel x1;
695 fractpel y1;
696 fractpel x2;
697 fractpel y2;
698 {
699
700 register pel pelxmin,pelymin,pelxmax,pelymax; /* pel versions of bounds */
701 register struct edgelist *edge; /* newly created edge */
702
703 pelymin = NEARESTPEL(ymin);
704 pelymax = NEARESTPEL(ymax);
705 if (pelymin == pelymax)
706 return(0);
707
708 pelxmin = NEARESTPEL(xmin);
709 pelxmax = NEARESTPEL(xmax);
710
711 if (pelxmin < R->xmin) R->xmin = pelxmin;
712 if (pelxmax > R->xmax) R->xmax = pelxmax;
713 if (pelymin < R->ymin) R->ymin = pelymin;
714 if (pelymax > R->ymax) R->ymax = pelymax;
715
716 edge = NewEdge(pelxmin, pelxmax, pelymin, pelymax, &R->edge[pelymin], isdown);
717
718 /* Save maximum and minimum values of edge in order to be able to
719 use them in ApplyContinity. */
720 edge->fpx1 = x1;
721 edge->fpy1 = y1;
722 edge->fpx2 = x2;
723 edge->fpy2 = y2;
724
725 edge->subpath = R->lastedge;
726 R->lastedge = edge;
727 if (R->firstedge == NULL)
728 R->firstedge = edge;
729
730 R->anchor = SortSwath(R->anchor, edge, swathxsort);
731
732 /*
733 {
734 struct region* r = (struct region*) R;
735 struct edgelist* el = (struct edgelist*) (r->anchor);
736
737 while ( el != 0 )
738 {
739 long i = 0;
740 short int* spl;
741 short int* spr;
742 int xl;
743 int xr;
744
745 printf( "Region after Sort (NE=%ld) : ymin=%d, ymax=%d, xmin=%d, xmax=%d\n",
746 callcount, el->ymin, el->ymax, el->xmin, el->xmax);
747 for ( i=0; i<((el->ymax)-(el->ymin)); i++ ) {
748 spl = el->xvalues;
749 if ( el->link != NULL ) {
750 spr = el->link->xvalues;
751 xl = spl[i];
752 xr = spr[i];
753 printf( "Region after Sort (NE=%ld): y=%ld xleft=%d, xright=%d\n",
754 callcount, el->ymin + i, xl, xr);
755 }
756 else {
757 printf( "Region after Sort (NE=%ld): y=%ld xval=%d\n",
758 callcount, el->ymin + i, spl[i]);
759 }
760 }
761 if ( el->link != 0 )
762 el = el->link->link;
763 else
764 break;
765 }
766 }
767
768 ++callcount;
769 */
770
771 return 0;
772 }
773
774 /*
775 :h2.Sorting Edges
776
777 :h3.SortSwath() - Vertically Sort an Edge into a Region
778
779 This routine sorts an edge or a pair of edges into a growing region,
780 so that the region maintains its top-to-bottom, left-to-right form.
781 The rules for sorting horizontally may vary depending on what you
782 are doing, but the rules for vertical sorting are always the same.
783 This routine is passed an argument that is a function that will
784 perform the horizontal sort on demand (for example, swathxsort() or
785 SwathUnion()).
786
787 This is a recursive routine. A new edge (or edge pair) may overlap
788 the list I am building in strange and wonderful ways. Edges may
789 cross. When this happens, my strategy is to split the incoming edge
790 (or the growing list) in two at that point, execute the actual sort on
791 the top part of the split, and recursively call myself to figure out
792 exactly where the bottom part belongs.
793 */
794
795 #define TOP(e) ((e)->ymin) /* the top of an edge (for readability */
796 #define BOTTOM(e) ((e)->ymax) /* the bottom of an edge (for readability */
797
SortSwath(anchor,edge,swathfcn)798 struct edgelist *SortSwath(anchor, edge, swathfcn)
799 struct edgelist *anchor; /* list being built */
800 register struct edgelist *edge; /* incoming edge or pair of edges */
801 struct edgelist *(*swathfcn)(); /* horizontal sorter */
802 {
803 register struct edgelist *before,*after;
804 struct edgelist base;
805
806 if (RegionDebug > 0) {
807 if (RegionDebug > 2) {
808 IfTrace3(TRUE,"SortSwath(anchor=%p, edge=%p, fcn=%p)\n",
809 anchor, edge, swathfcn);
810 }
811 else {
812 IfTrace3(TRUE,"SortSwath(anchor=%p, edge=%p, fcn=%p)\n",
813 anchor, edge, swathfcn);
814 }
815 }
816 if (anchor == NULL)
817 return(edge);
818
819 before = &base;
820 before->ymin = before->ymax = MINPEL;
821 before->link = after = anchor;
822
823 /*
824 If the incoming edge is above the current list, we connect the current
825 list to the bottom of the incoming edge. One slight complication is
826 if the incoming edge overlaps into the current list. Then, we
827 first split the incoming edge in two at the point of overlap and recursively
828 call ourselves to sort the bottom of the split into the current list:
829 */
830 if (TOP(edge) < TOP(after)) {
831 if (BOTTOM(edge) > TOP(after)) {
832 after = SortSwath(after, splitedge(edge, TOP(after)), swathfcn);
833 }
834 vertjoin(edge, after);
835 return(edge);
836 }
837
838 /*
839 At this point the top of edge is not higher than the top of the list,
840 which we keep in 'after'. We move the 'after' point down the list,
841 until the top of the edge occurs in the swath beginning with 'after'.
842
843 If the bottom of 'after' is below the bottom of the edge, we have to
844 split the 'after' swath into two parts, at the bottom of the edge.
845 If the bottom of 'after' is above the bottom of the swath,
846 */
847
848 while (VALIDEDGE(after)) {
849
850 if (TOP(after) == TOP(edge)) {
851 if (BOTTOM(after) > BOTTOM(edge))
852 vertjoin(after, splitedge(after, BOTTOM(edge)));
853 else if (BOTTOM(after) < BOTTOM(edge)) {
854 after = SortSwath(after,
855 splitedge(edge, BOTTOM(after)), swathfcn);
856 }
857 break;
858 }
859 else if (TOP(after) > TOP(edge)) {
860 IfTrace0((BOTTOM(edge) < TOP(after) && RegionDebug > 0),
861 "SortSwath: disjoint edges\n");
862 if (BOTTOM(edge) > TOP(after)) {
863 after = SortSwath(after,
864 splitedge(edge, TOP(after)), swathfcn);
865 }
866 break;
867 }
868 else if (BOTTOM(after) > TOP(edge))
869 vertjoin(after, splitedge(after, TOP(edge)));
870
871 before = after;
872 after = after->link;
873 }
874
875 /*
876 At this point 'edge' exactly corresponds in height to the current
877 swath pointed to by 'after'.
878 */
879 if (after != NULL && TOP(after) == TOP(edge)) {
880 before = (*swathfcn)(before, edge);
881 after = before->link;
882 }
883 /*
884 At this point 'after' contains all the edges after 'edge', and 'before'
885 contains all the edges before. Whew! A simple matter now of adding
886 'edge' to the linked list in its rightful place:
887 */
888 before->link = edge;
889 if (RegionDebug > 1) {
890 IfTrace3(TRUE,"SortSwath: in between %p and %p are %p",
891 before, after, edge);
892 while (edge->link != NULL) {
893 edge = edge->link;
894 IfTrace1(TRUE," and %p", edge);
895 }
896 IfTrace0(TRUE,"\n");
897 }
898 else
899 for (; edge->link != NULL; edge = edge->link) { ; }
900
901 edge->link = after;
902
903 return base.link;
904
905 }
906
907 /*
908 :h3.splitedge() - Split an Edge or Swath in Two at a Given Y Value
909
910 This function returns the edge or swath beginning at the Y value, and
911 is guaranteed not to change the address of the old swath while splitting
912 it.
913 */
914
splitedge(list,y)915 static struct edgelist *splitedge(list, y)
916 struct edgelist *list; /* area to split */
917 register pel y; /* Y value to split list at */
918 {
919 register struct edgelist *new; /* anchor for newly built list */
920 register struct edgelist *last=NULL; /* end of newly built list */
921 register struct edgelist *r; /* temp pointer to new structure */
922 register struct edgelist *lastlist; /* temp pointer to last 'list' value */
923
924 IfTrace2((RegionDebug > 1),"splitedge of %p at %d ", list, (LONG) y);
925
926 lastlist = new = NULL;
927
928 while (list != NULL) {
929 if (y < list->ymin)
930 break;
931
932 if (y >= list->ymax)
933 abort("splitedge: above top of list", 33);
934 if (y == list->ymin)
935 abort("splitedge: would be null", 34);
936
937 r = (struct edgelist *)Allocate(sizeof(struct edgelist), list, 0);
938 /*
939 At this point 'r' points to a copy of the single structure at 'list'.
940 We will make 'r' be the new split 'edgelist'--the lower half.
941 We don't bother to correct 'xmin' and 'xmax', we'll take the
942 the pessimistic answer that results from using the old values.
943 */
944 r->ymin = y;
945 r->xvalues = list->xvalues + (y - list->ymin);
946
947 /*
948 Update the fpx values so that ApplyContinuity() will continue
949 to work. Note that high precision is a fake, here!
950 */
951 r->fpx1 = (r->xvalues[0]) << FRACTBITS;
952 r->fpx2 = (list->xvalues[list->ymax - list->ymin - 1]) << FRACTBITS;
953 list->fpx2 = (list->xvalues[y - list->ymin -1]) << FRACTBITS;
954
955 /*
956 Note that we do not need to allocate new memory for the X values,
957 they can remain with the old "edgelist" structure. We do have to
958 update that old structure so it is not as high:
959 */
960 list->ymax = y;
961
962 /*
963 Insert 'r' in the subpath chain:
964 */
965 r->subpath = list->subpath;
966 list->subpath = r;
967 /*
968 Now attach 'r' to the list we are building at 'new', and advance
969 'list' to point to the next element in the old list:
970 */
971 if (new == NULL) {
972 new = r;
973 }
974 else
975 last->link = r;
976 last = r;
977 lastlist = list;
978 list = list->link;
979 }
980 /*
981 At this point we have a new list built at 'new'. We break the old
982 list at 'lastlist', and add the broken off part to the end of 'new'.
983 Then, we return the caller a pointer to 'new':
984 */
985 if (new == NULL)
986 abort("null splitedge", 35);
987 lastlist->link = NULL;
988 last->link = list;
989 IfTrace1((RegionDebug > 1),"yields %p\n", new);
990 return(new);
991 }
992
993 /*
994 :h3.vertjoin() - Join Two Disjoint Edge Lists Vertically
995
996 The two edges must be disjoint vertically.
997 */
vertjoin(top,bottom)998 static int vertjoin(top, bottom)
999 register struct edgelist *top; /* uppermost region */
1000 register struct edgelist *bottom; /* bottommost region */
1001 {
1002 if (BOTTOM(top) > TOP(bottom))
1003 abort("vertjoin not disjoint", 36);
1004
1005 for (; top->link != NULL; top=top->link) { ; }
1006
1007 top->link = bottom;
1008 return(0);
1009 }
1010
1011 /*
1012 :h3.swathxsort() - Sorting by X Values
1013
1014 We need to sort 'edge' into its rightful
1015 place in the swath by X value, taking care that we do not accidentally
1016 advance to the next swath while searching for the correct X value. Like
1017 all swath functions, this function returns a pointer to the edge
1018 BEFORE the given edge in the sort.
1019 */
1020
swathxsort(before0,edge)1021 struct edgelist *swathxsort(before0, edge)
1022 register struct edgelist *before0; /* edge before this swath */
1023 register struct edgelist *edge; /* input edge */
1024 {
1025 register struct edgelist *before;
1026 register struct edgelist *after;
1027 register pel y=0;
1028
1029 before = before0;
1030 after = before->link;
1031
1032 while (after != NULL && TOP(after) == TOP(edge)) {
1033
1034 register pel *x1,*x2;
1035
1036 y = TOP(edge);
1037 x1 = after->xvalues;
1038 x2 = edge->xvalues;
1039
1040 while (y < BOTTOM(edge) && *x1 == *x2) {
1041 x1++; x2++; y++;
1042 }
1043 if (y >= BOTTOM(edge)) {
1044 edge->flag |= ISAMBIGUOUS(ON);
1045 after->flag |= ISAMBIGUOUS(ON);
1046 break;
1047 }
1048
1049 if (*x1 >= *x2)
1050 break;
1051
1052 before = after;
1053 after = after->link;
1054 }
1055
1056 /*
1057 At this point, 'edge' is between 'before' and 'after'. If 'edge' didn't
1058 cross either of those other edges, we would be done. We check for
1059 crossing. If it does cross, we split the problem up by calling SortSwath
1060 recursively with the part of the edge that is below the crossing point:
1061 */
1062 {
1063 register int h0,h; /* height of edge--number of scans */
1064
1065 h0 = h = BOTTOM(edge) - y;
1066 y -= TOP(edge);
1067
1068 if (h0 <= 0) {
1069 IfTrace0((RegionDebug>0),"swathxsort: exactly equal edges\n");
1070 return(before);
1071 }
1072
1073 if (TOP(before) == TOP(edge))
1074 h -= crosses(h, &before->xvalues[y], &edge->xvalues[y]);
1075 if (after != NULL && TOP(after) == TOP(edge))
1076 h -= crosses(h, &edge->xvalues[y], &after->xvalues[y]);
1077
1078 if (h < h0) {
1079 SortSwath(before0->link,
1080 splitedge(edge, TOP(edge) + y + h),
1081 swathxsort);
1082
1083 }
1084 }
1085
1086 return(before);
1087 }
1088 /*
1089 :h3.SwathUnion() - Union Two Edges by X Value
1090
1091 We have a left and right edge that must be unioned into a growing
1092 swath. If they are totally disjoint, they are just added in. The
1093 fun comes in they overlap the existing edges. Then some edges
1094 will disappear.
1095 */
1096
SwathUnion(before0,edge)1097 struct edgelist *SwathUnion(before0, edge)
1098 register struct edgelist *before0; /* edge before the swath */
1099 register struct edgelist *edge; /* list of two edges to be unioned */
1100 {
1101 register int h; /* saves height of edge */
1102 register struct edgelist *rightedge; /* saves right edge of 'edge' */
1103 register struct edgelist *before,*after; /* edge before and after */
1104 int h0; /* saves initial height */
1105
1106 IfTrace2((RegionDebug > 1),"SwathUnion entered, before=%p, edge=%p\n",
1107 before0, edge);
1108
1109 h0 = h = edge->ymax - edge->ymin;
1110 if (h <= 0)
1111 abort("SwathUnion: 0 height swath?", 37);
1112
1113 before = before0;
1114 after = before->link;
1115
1116 while (after != NULL && TOP(after) == TOP(edge)) {
1117 register struct edgelist *right;
1118
1119 right = after->link;
1120 if (right->xvalues[0] >= edge->xvalues[0])
1121 break;
1122 before = right;
1123 after = before->link;
1124 }
1125 /*
1126 This is the picture at this point. 'L' indicates a left hand edge,
1127 'R' indicates the right hand edge.
1128 '<--->' indicates the degree of uncertainty as to its placement
1129 relative to other edges:
1130 :xmp atomic.
1131 before after
1132 R <---L----> R L R L R
1133 <---L---> <------R-------------------------->
1134 edge
1135 :exmp.
1136 In case the left of 'edge' touches 'before', we need to reduce
1137 the height by that amount.
1138 */
1139 if (TOP(before) == TOP(edge))
1140 h -= touches(h, before->xvalues, edge->xvalues);
1141
1142 rightedge = edge->link;
1143
1144 if (after == NULL || TOP(after) != TOP(edge) ||
1145 after->xvalues[0] > rightedge->xvalues[0]) {
1146 IfTrace2((RegionDebug > 1),
1147 "SwathUnion starts disjoint: before=%p after=%p\n",
1148 before, after);
1149 /*
1150 On this side of the the above 'if', the new edge is disjoint from the
1151 existing edges in the swath. This is the picture:
1152 :xmp atomic.
1153 before after
1154 R L R L R L R
1155 L R
1156 edge
1157 :exmp.
1158 We will verify it remains disjoint for the entire height. If the
1159 situation changes somewhere down the edge, we split the edge at that
1160 point and recursively call ourselves (through 'SortSwath') to figure
1161 out the new situation:
1162 */
1163 if (after != NULL && TOP(after) == TOP(edge))
1164 h -= touches(h, rightedge->xvalues, after->xvalues);
1165 if (h < h0)
1166 SortSwath(before0->link, splitedge(edge, edge->ymin + h), t1_SwathUnion);
1167 /* go to "return" this edge pair; it is totally disjoint */
1168 }
1169 else {
1170 /*
1171 At this point, at the 'else', we know that the
1172 new edge overlaps one or more pairs in the existing swath. Here is
1173 a picture of our knowledge and uncertainties:
1174 :xmp atomic.
1175 before after
1176 R L R L R L R
1177 <---L---> <---R------------------->
1178 edge
1179 :exmp.
1180 We need to move 'after' along until it is to the right of the
1181 right of 'edge'. ('After' should always point to a left edge of a pair:)
1182 */
1183 register struct edgelist *left; /* variable to keep left edge in */
1184
1185 do {
1186 left = after;
1187 after = (after->link)->link;
1188
1189 } while (after != NULL && TOP(after) == TOP(edge)
1190 && after->xvalues[0] <= rightedge->xvalues[0]);
1191 /*
1192 At this point this is the picture:
1193 :xmp atomic.
1194 before left after
1195 R L R L R L R
1196 <---L---> <---R--->
1197 edge
1198 :exmp.
1199 We need to verify that the situation stays like this all the way
1200 down the edge. Again, if the
1201 situation changes somewhere down the edge, we split the edge at that
1202 point and recursively call ourselves (through 'SortSwath') to figure
1203 out the new situation:
1204 */
1205
1206 h -= crosses(h, left->xvalues, rightedge->xvalues);
1207 h -= crosses(h, edge->xvalues, ((before->link)->link)->xvalues);
1208
1209 if (after != NULL && TOP(after) == TOP(edge))
1210
1211 h -= touches(h, rightedge->xvalues, after->xvalues);
1212
1213 IfTrace3((RegionDebug > 1),
1214 "SwathUnion is overlapped until %d: before=%p after=%p\n",
1215 (LONG) TOP(edge) + h, before, after);
1216 /*
1217 OK, if we touched either of our neighbors we need to split at that point
1218 and recursively sort the split edge onto the list. One tricky part
1219 is that when we recursively sort, 'after' will change if it was not
1220 in our current swath:
1221 */
1222 if (h < h0) {
1223 SortSwath(before0->link,
1224 splitedge(edge, edge->ymin + h),
1225 t1_SwathUnion);
1226
1227 if (after == NULL || TOP(after) != TOP(edge))
1228 for (after = before0->link;
1229 TOP(after) == TOP(edge);
1230 after = after->link) { ; }
1231 }
1232 /*
1233 Now we need to augment 'edge' by the left and right of the overlapped
1234 swath, and to discard all edges between before and after, because they
1235 were overlapped and have been combined with the new incoming 'edge':
1236 */
1237 edge->xmin = TYPE1_MIN(edge->xmin, (before->link)->xmin);
1238 edge->xmax = TYPE1_MIN(edge->xmax, (before->link)->xmax);
1239 edgemin(h, edge->xvalues, (before->link)->xvalues);
1240 rightedge->xmin = TYPE1_MAX(rightedge->xmin, (left->link)->xmin);
1241 rightedge->xmax = TYPE1_MAX(rightedge->xmax, (left->link)->xmax);
1242 edgemax(h, rightedge->xvalues, (left->link)->xvalues);
1243 discard(before, after);
1244 }
1245 return(before);
1246 }
1247 /*
1248 :h3.swathrightmost() - Simply Sorts New Edge to Rightmost of Swath
1249
1250 Like all swath functions, this function returns a pointer to the edge
1251 BEFORE the given edge in the sort.
1252 */
1253
swathrightmost(before,edge)1254 struct edgelist *swathrightmost(before, edge)
1255 register struct edgelist *before; /* edge before this swath */
1256 register struct edgelist *edge; /* input edge */
1257 {
1258 register struct edgelist *after;
1259
1260 after = before->link;
1261
1262 while (after != NULL && TOP(after) == TOP(edge)) {
1263 before = after;
1264 after = after->link;
1265 }
1266
1267 return(before);
1268
1269 }
1270 /*
1271 :h3.touches() - Returns the Remaining Height When Two Edges Touch
1272
1273 So, it will return 0 if they never touch. Allows incredibly(?) mnemonic
1274 if (touches(...)) construct.
1275 */
1276
touches(h,left,right)1277 static int touches(h, left, right)
1278 register int h;
1279 register pel *left,*right;
1280 {
1281 for (; h > 0; h--)
1282 if (*left++ >= *right++)
1283 break;
1284 return(h);
1285 }
1286 /*
1287 :h3.crosses() - Returns the Remaining Height When Two Edges Cross
1288
1289 So, it will return 0 if they never cross.
1290 */
1291
crosses(h,left,right)1292 static int crosses(h, left, right)
1293 register int h;
1294 register pel *left,*right;
1295 {
1296 for (; h > 0; h--)
1297 if (*left++ > *right++)
1298 break;
1299 return(h);
1300 }
1301 /*
1302 :h3.cedgemin() - Stores the Mininum of an Edge and an X Value
1303 */
1304
cedgemin(h,e1,x)1305 static int cedgemin(h, e1, x)
1306 register int h;
1307 register pel *e1;
1308 register pel x;
1309 {
1310 for (; --h >= 0; e1++)
1311 if (*e1 > x)
1312 *e1 = x;
1313 return(0);
1314
1315 }
1316 /*
1317 :h3.cedgemax() - Stores the Maximum of an Edge and an X Value
1318 */
1319
cedgemax(h,e1,x)1320 static int cedgemax(h, e1, x)
1321 register int h;
1322 register pel *e1;
1323 register pel x;
1324 {
1325 for (; --h >= 0; e1++)
1326 if (*e1 < x)
1327 *e1 = x;
1328 return(0);
1329
1330 }
1331 /*
1332 :h3.edgemin() - Stores the Mininum of Two Edges in First Edge
1333 */
1334
edgemin(h,e1,e2)1335 static int edgemin(h, e1, e2)
1336 register int h;
1337 register pel *e1,*e2;
1338 {
1339 for (; --h >= 0; e1++,e2++)
1340 if (*e1 > *e2)
1341 *e1 = *e2;
1342 return(0);
1343
1344 }
1345 /*
1346 :h3.edgemax() - Stores the Maximum of Two Edges in First Edge
1347 */
1348
edgemax(h,e1,e2)1349 static int edgemax(h, e1, e2)
1350 register int h;
1351 register pel *e1,*e2;
1352 {
1353 for (; --h >= 0; e1++,e2++)
1354 if (*e1 < *e2)
1355 *e1 = *e2;
1356 return(0);
1357
1358 }
1359 /*
1360 :h3 id=discard.discard() - Discard All Edges Between Two Edges
1361
1362 At first glance it would seem that we could discard an edgelist
1363 structure merely by unlinking it from the list and freeing it. You are
1364 wrong, region-breath! For performance, the X values associated with an
1365 edge are allocated contiguously with it. So, we free the X values when
1366 we free a structure. However, once an edge has been split, we are no
1367 longer sure which control block actually is part of the memory block
1368 that contains the edges. Rather than trying to decide, we play it safe
1369 and never free part of a region.
1370
1371 So, to mark a 'edgelist' structure as discarded, we move it to the end
1372 of the list and set ymin=ymax.
1373 */
1374
discard(left,right)1375 static int discard(left, right)
1376 register struct edgelist *left,*right; /* all edges between here exclusive */
1377 /* should be discarded */
1378 {
1379 register struct edgelist *beg,*end,*p;
1380
1381 IfTrace2((RegionDebug > 0),"discard: l=%p, r=%p\n", left, right);
1382
1383 beg = left->link;
1384 if (beg == right)
1385 return(0);
1386
1387 for (p = beg; p != right; p = p->link) {
1388 if (p->link == NULL && right != NULL)
1389 abort("discard(): ran off end", 38);
1390 IfTrace1((RegionDebug > 0),"discarding %p\n", p);
1391 p->ymin = p->ymax = 32767;
1392 end = p;
1393 }
1394 /*
1395 * now put the chain beg/end at the end of right, if it is not
1396 * already there:
1397 */
1398 if (right != NULL) {
1399 left->link = right;
1400 while (right->link != NULL)
1401 right = right->link;
1402 right->link = beg;
1403 }
1404 end->link = NULL;
1405 return(0);
1406
1407 }
1408
1409 /*
1410 :h2.Changing the Representation of Regions
1411
1412 For convenience and/or performance, we sometimes like to change the way
1413 regions are represented. This does not change the object itself, just
1414 the representation, so these transformations can be made on a permanent
1415 region.
1416
1417 */
1418
MoveEdges(R,dx,dy)1419 void MoveEdges(R, dx, dy)
1420 register struct region *R; /* region to modify */
1421 register fractpel dx,dy; /* delta X and Y to move edge list by */
1422 {
1423 register struct edgelist *edge; /* for looping through edges */
1424
1425 R->origin.x += dx;
1426 R->origin.y += dy;
1427 R->ending.x += dx;
1428 R->ending.y += dy;
1429 if (R->thresholded != NULL) {
1430 R->thresholded->origin.x -= dx;
1431 R->thresholded->origin.y -= dy;
1432 }
1433 /*
1434 From now on we will deal with dx and dy as integer pel values:
1435 */
1436 dx = NEARESTPEL(dx);
1437 dy = NEARESTPEL(dy);
1438 if (dx == 0 && dy == 0)
1439 return;
1440
1441 R->xmin += dx;
1442 R->xmax += dx;
1443 R->ymin += dy;
1444 R->ymax += dy;
1445
1446 for (edge = R->anchor; VALIDEDGE(edge); edge = edge->link) {
1447 edge->ymin += dy;
1448 edge->ymax += dy;
1449 if (dx != 0) {
1450 register int h; /* loop index; height of edge */
1451 register pel *Xp; /* loop pointer to X values */
1452
1453 edge->xmin += dx;
1454 edge->xmax += dx;
1455 for (Xp = edge->xvalues, h = edge->ymax - edge->ymin;
1456 --h >= 0; )
1457 *Xp++ += dx;
1458 }
1459 }
1460 }
1461
1462 /*
1463 :h3.UnJumble() - Sort a Region Top to Bottom
1464
1465 It is an open question whether it pays in general to do this.
1466 */
1467
UnJumble(region)1468 void UnJumble(region)
1469 struct region *region; /* region to sort */
1470 {
1471 register struct edgelist *anchor; /* new lists built here */
1472 register struct edgelist *edge; /* edge pointer for loop */
1473 register struct edgelist *next; /* ditto */
1474
1475 anchor = NULL;
1476
1477 for (edge=region->anchor; VALIDEDGE(edge); edge=next) {
1478 if (edge->link == NULL)
1479 abort("UnJumble: unpaired edge?", 39);
1480 next = edge->link->link;
1481 edge->link->link = NULL;
1482 anchor = SortSwath(anchor, edge, t1_SwathUnion);
1483 }
1484
1485 if (edge != NULL)
1486 vertjoin(anchor, edge);
1487
1488 region->anchor = anchor;
1489 region->flag &= ~ISJUMBLED(ON);
1490 }
1491
1492 /*
1493 */
1494
1495 #undef NEED_OPTIMZEREGION
1496 #ifdef NEED_OPTIMZEREGION
OptimizeRegion(R)1497 static int OptimizeRegion(R)
1498 struct region *R; /* region to optimize */
1499 {
1500 register pel *xP; /* pel pointer for inner loop */
1501 register int x; /* holds X value */
1502 register int xmin,xmax; /* holds X range */
1503 register int h; /* loop counter */
1504 register struct edgelist *e; /* edgelist pointer for loop */
1505
1506 R->flag |= ISRECTANGULAR(ON);
1507
1508 for (e = R->anchor; VALIDEDGE(e); e=e->link) {
1509 xmin = MAXPEL;
1510 xmax = MINPEL;
1511 for (h = e->ymax - e->ymin, xP = e->xvalues; --h >= 0;) {
1512 x = *xP++;
1513 if (x < xmin) xmin = x;
1514 if (x > xmax) xmax = x;
1515 }
1516 if (xmin != xmax || (xmin != R->xmin && xmax != R->xmax))
1517 R->flag &= ~ISRECTANGULAR(ON);
1518 if (xmin < e->xmin || xmax > e->xmax)
1519 abort("Tighten: existing edge bound was bad", 40);
1520 if (xmin < R->xmin || xmax > R->xmax)
1521 abort("Tighten: existing region bound was bad", 41);
1522 e->xmin = xmin;
1523 e->xmax = xmax;
1524 }
1525 R->flag |= ISOPTIMIZED(ON);
1526 return(0);
1527
1528 }
1529
1530 #endif /* This function is not used */
1531
1532 /*
1533 :h2.Miscelaneous Routines
1534
1535 :h3.MoreWorkArea() - Allocate New Space for "edge"
1536
1537 Our strategy is to temporarily allocate an array to hold this
1538 unexpectedly large edge. ChangeDirection frees this array any time
1539 it gets a shorter 'dy'.
1540 */
1541
1542 /*ARGSUSED*/
MoreWorkArea(R,x1,y1,x2,y2)1543 void MoreWorkArea(R, x1, y1, x2, y2)
1544 struct region *R; /* region we are generating */
1545 fractpel x1,y1; /* starting point of line */
1546 fractpel x2,y2; /* ending point of line */
1547 {
1548 register int idy; /* integer dy of line */
1549
1550 idy = NEARESTPEL(y1) - NEARESTPEL(y2);
1551 if (idy < 0) idy = - idy;
1552
1553 /*
1554 * we must add one to the delta for the number of run ends we
1555 * need to store:
1556 */
1557 if (++idy > currentsize) {
1558 IfTrace1((RegionDebug > 0),"Allocating edge of %d pels\n", idy);
1559 if (currentworkarea != workedge)
1560 NonObjectFree(currentworkarea);
1561 currentworkarea = (pel *)Allocate(0, NULL, idy * sizeof(pel));
1562 currentsize = idy;
1563 }
1564 ChangeDirection(CD_CONTINUE, R, x1, y1, y2 - y1, x2, y2);
1565 }
1566
1567 /*
1568 :h3.BoxClip() - Clip a Region to a Rectangle
1569
1570 BoxClip also duplicates the region if it is permanent. Note the
1571 clipping box is specified in REGION coordinates, that is, in
1572 coordinates relative to the region (0,0) point
1573 */
1574
BoxClip(R,xmin,ymin,xmax,ymax)1575 struct region *BoxClip(R, xmin, ymin, xmax, ymax)
1576 register struct region *R; /* region to clip */
1577 register pel xmin,ymin; /* upper left hand corner of rectangle */
1578 register pel xmax,ymax; /* lower right hand corner */
1579 {
1580 struct edgelist anchor; /* pretend edgelist to facilitate discards */
1581 register struct edgelist *e,*laste;
1582
1583 IfTrace1((OffPageDebug),"BoxClip of %p:\n", R);
1584
1585 R = UniqueRegion(R);
1586
1587 if (xmin > R->xmin) {
1588 IfTrace2((OffPageDebug),"BoxClip: left clip old %d new %d\n",
1589 (LONG) R->xmin, (LONG) xmin);
1590 R->xmin = xmin;
1591 }
1592 if (xmax < R->xmax) {
1593 IfTrace2((OffPageDebug),"BoxClip: right clip old %d new %d\n",
1594 (LONG) R->xmax, (LONG) xmax);
1595 R->xmax = xmax;
1596 }
1597
1598 if (ymin > R->ymin) {
1599 IfTrace2((OffPageDebug),"BoxClip: top clip old %d new %d\n",
1600 (LONG) R->ymin, (LONG) ymin);
1601 R->ymin = ymin;
1602 }
1603 if (ymax < R->ymax) {
1604 IfTrace2((OffPageDebug),"BoxClip: bottom clip old %d new %d\n",
1605 (LONG) R->ymax, (LONG) ymax);
1606 R->ymax = ymax;
1607 }
1608
1609
1610 laste = &anchor;
1611 anchor.link = R->anchor;
1612
1613 for (e = R->anchor; VALIDEDGE(e); e = e->link) {
1614 if (TOP(e) < ymin) {
1615 e->xvalues += ymin - e->ymin;
1616 e->ymin = ymin;
1617 }
1618 if (BOTTOM(e) > ymax)
1619 e->ymax = ymax;
1620 if (TOP(e) >= BOTTOM(e)) {
1621 discard(laste, e->link->link);
1622 e = laste;
1623 continue;
1624 }
1625 if (e->xmin < xmin) {
1626 cedgemax(BOTTOM(e) - TOP(e), e->xvalues, xmin);
1627 e->xmin = xmin;
1628 e->xmax = TYPE1_MAX(e->xmax, xmin);
1629 }
1630 if (e->xmax > xmax) {
1631 cedgemin(BOTTOM(e) - TOP(e), e->xvalues, xmax);
1632 e->xmin = TYPE1_MIN(e->xmin, xmax);
1633 e->xmax = xmax;
1634 }
1635 laste = e;
1636 }
1637
1638 R->anchor = anchor.link;
1639
1640 return(R);
1641 }
1642
1643 #ifdef notdef
1644 /*
1645 :h3.CoerceRegion() - Force a TextPath Structure to Become a Region
1646
1647 We also save the newly created region in the textpath structure, if the
1648 structure was permanent. Then we don't have to do this again. Why not
1649 save it all the time? Well, we certainly could, but I suspect it
1650 wouldn't pay. We would have to make this region permanent (because we
1651 couldn't have it be consumed) and this would probably require
1652 unnecessary CopyRegions in most cases.
1653 */
1654
CoerceRegion(tp)1655 struct region *CoerceRegion(tp)
1656 register struct textpath *tp; /* input TEXTTYPE */
1657 {
1658 struct segment *path; /* temporary character path */
1659 struct region *R; /* returned region */
1660
1661
1662 R = Interior(path, EVENODDRULE);
1663 return(R);
1664 }
1665 #endif
1666
1667 /*
1668 :h3.RegionBounds() - Returns Bounding Box of a Region
1669 */
1670
RegionBounds(R)1671 struct segment *RegionBounds(R)
1672 register struct region *R;
1673 {
1674
1675 register struct segment *path; /* returned path */
1676
1677 path = BoxPath(IDENTITY, R->ymax - R->ymin, R->xmax - R->xmin);
1678 path = Join(PathSegment(MOVETYPE, R->origin.x + TOFRACTPEL(R->xmin),
1679 R->origin.y + TOFRACTPEL(R->ymin) ),
1680 path);
1681 return(path);
1682 }
1683
1684 /*
1685 :h2.Formatting/Dump Routines for Debug
1686
1687 :h3.DumpArea() - Display a Region
1688 */
DumpArea(area)1689 void DumpArea(area)
1690 register struct region *area;
1691 {
1692 IfTrace1(TRUE,"Dumping area %p,", area);
1693 IfTrace4(TRUE," X %d:%d Y %d:%d;", (LONG) area->xmin,
1694 (LONG) area->xmax, (LONG) area->ymin,(LONG) area->ymax);
1695 IfTrace4(TRUE," origin=(%d,%d), ending=(%d,%d)\n",
1696 area->origin.x, area->origin.y, area->ending.x, area->ending.y);
1697 DumpEdges(area->anchor);
1698 }
1699
1700 #define INSWATH(p, y0, y1) (p != NULL && p->ymin == y0 && p->ymax == y1)
1701 /*
1702 :h3.DumpEdges() - Display Run End Lists (Edge Lists)
1703 */
1704
1705 static pel RegionDebugYMin = MINPEL;
1706 static pel RegionDebugYMax = MAXPEL;
1707
DumpEdges(edges)1708 void DumpEdges(edges)
1709 register struct edgelist *edges;
1710 {
1711 register struct edgelist *p,*p2;
1712 register pel ymin = MINPEL;
1713 register pel ymax = MINPEL;
1714 register int y;
1715
1716 if (edges == NULL) {
1717 IfTrace0(TRUE," NULL area.\n");
1718 return;
1719 }
1720 if (RegionDebug <= 1) {
1721 for (p=edges; p != NULL; p = p->link) {
1722 edgecheck(p, ymin, ymax);
1723 ymin = p->ymin; ymax = p->ymax;
1724 IfTrace3(TRUE,". at %p type=%d flag=%x",
1725 p, (LONG) p->type,(LONG) p->flag);
1726 IfTrace4(TRUE," bounding box HxW is %dx%d at (%d,%d)\n",
1727 (LONG) ymax - ymin, (LONG) p->xmax - p->xmin,
1728 (LONG) p->xmin, (LONG) ymin);
1729 }
1730 }
1731 else {
1732
1733 for (p2=edges; p2 != NULL; ) {
1734
1735 edgecheck(p2, ymin, ymax);
1736 ymin = p2->ymin;
1737 ymax = p2->ymax;
1738
1739 if (RegionDebug > 3 || (ymax > RegionDebugYMin
1740 && ymin < RegionDebugYMax)) {
1741 IfTrace2 (TRUE,". Swath from %d to %d:\n",
1742 ymin, ymax);
1743 for (p=p2; INSWATH(p,ymin,ymax); p = p->link) {
1744 IfTrace4(TRUE,". . at %p[%x] range %d:%d, ",
1745 p, (LONG) p->flag,
1746 (LONG) p->xmin, (LONG)p->xmax);
1747 IfTrace1(TRUE, "subpath=%p,\n", p->subpath);
1748 }
1749 }
1750 for (y=TYPE1_MAX(ymin,RegionDebugYMin); y < TYPE1_MIN(ymax, RegionDebugYMax); y++) {
1751 IfTrace1(TRUE,". . . Y[%5d] ", (LONG) y);
1752 for (p=p2; INSWATH(p,ymin,ymax); p = p->link)
1753 IfTrace1(TRUE,"%5d ",
1754 (LONG) p->xvalues[y - ymin]);
1755 IfTrace0(TRUE,"\n");
1756 }
1757 while (INSWATH(p2, ymin, ymax))
1758 p2 = p2->link;
1759 }
1760 }
1761 }
1762
1763 /*
1764 :h3.edgecheck() - For Debug, Verify that an Edge Obeys the Rules
1765 */
1766
1767 /*ARGSUSED*/
edgecheck(edge,oldmin,oldmax)1768 static int edgecheck(edge, oldmin, oldmax)
1769 struct edgelist *edge;
1770 int oldmin,oldmax;
1771 {
1772 if (edge->type != EDGETYPE)
1773 abort("EDGE ERROR: non EDGETYPE in list", 42);
1774 /*
1775 The following check is not valid if the region is jumbled so I took it
1776 out:
1777 */
1778 /* if (edge->ymin < oldmax && edge->ymin != oldmin)
1779 abort("EDGE ERROR: overlapping swaths", 43); */
1780 return(0);
1781
1782 }
1783