w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

regions.c
Go to the documentation of this file.
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 "types.h"
44 #include "objects.h"
45 #include "spaces.h"
46 #include "paths.h"
47 #include "regions.h"
48 #include "curves.h"
49 #include "lines.h"
50 #include "pictures.h"
51 #include "fonts.h"
52 #include "hints.h"
53 #include "strokes.h" /* to pick up 'DoStroke' */
54 static void Unwind(struct edgelist *);
55 static void newfilledge(register struct region *, fractpel, fractpel,
56  fractpel, fractpel, int);
57 static void vertjoin(register struct edgelist *, register struct edgelist *);
58 static void discard(register struct edgelist *, register struct edgelist *);
59 static void edgemin(register int, register pel *, register pel *);
60 static void edgemax(register int, register pel *, register pel *);
61 static struct edgelist *splitedge(struct edgelist *, pel);
62 static int touches(int, pel *, pel *);
63 static int crosses(int, pel *, pel *);
64 static struct edgelist *NewEdge(pel, pel, pel, pel, pel *, int);
65 
66 /*
67 :h3.Functions Provided to the TYPE1IMAGER User
68 
69 This module provides the following TYPE1IMAGER entry points:
70 */
71 
72 /*SHARED LINE(S) ORIGINATED HERE*/
73 /*
74 :h3.Functions Provided to Other Modules
75 
76 This module provides the following entry points to other modules:
77 */
78 
79 /*SHARED LINE(S) ORIGINATED HERE*/
80 /*
81 :h3.Macros Provided to Other Modules
82 
83 :h4.GOING_TO() - Macro Predicate Needed for Changing Direction, Etc.
84 
85 The actual generation of run end lists (edge boundaries) is left
86 to the low level rasterizing modules, LINES and CURVES. There
87 are some global region-type
88 questions that occur when doing a low-level
89 rasterization:
90 :ol.
91 :li.Did we just change direction in Y and therefore need to start
92 a new edge?
93 :li.Did we run out of allocated edge space?
94 :li.Do the minimum or maximum X values for the current edge need
95 updating?
96 :eol.
97 In general the REGIONS is not smart enough to answer those questions
98 itself. (For example, determining if and when a curve changes direction
99 may need detailed curve knowledge.) Yet, this must be done efficiently.
100 We provide a macro "GOING_TO" where the invoker tells us where it is
101 heading for (x2,y2), plus where it is now (x1,y1), plus the current
102 region under construction, and the macro answers the questions above.
103 */
104 
105 /*SHARED LINE(S) ORIGINATED HERE*/
106 /*
107 :h2.Data Structures Used to Represent Regions
108 
109 :h3.The "region" Structure
110 
111 The region structure is an anchor for a linked list of "edgelist"
112 structures (see :hdref refid=edgelist..). It also summarizes the
113 information in the edgelist structures (for example, the bounding
114 box of the region). And, it contains scratch areas used during
115 the creation of a region.
116 */
117 
118 /*SHARED LINE(S) ORIGINATED HERE*/
119 /*
120 The ISOPTIMIZED flag tells us if we've put a permanent region in
121 'optimal' form.
122 */
123 #define ISOPTIMIZED(flag) ((flag)&0x10)
124 
125 /*
126 The ISRECTANGULAR flag tells us if a region is a rectangle. We don't
127 always notice rectangles--if this flag is set, the region definitely
128 is a rectangle, but some rectangular regions will not have the flag
129 set. The flag is used to optimize some paths.
130 */
131 
132 /*SHARED LINE(S) ORIGINATED HERE*/
133 /*
134 :h4."T1_INFINITY" - A Constant Region Structure of Infinite Extent
135 
136 Infinity is the complement of a null area:
137 Note - removed the refcount = 1 init, replaced with references = 2 3-26-91 PNM
138 */
139 static struct region t1_infinity = { REGIONTYPE,
141  { 0, 0 }, { 0, 0 },
142  0, 0, 0, 0,
143  NULL, NULL,
144  0, 0, 0, 0, 0, NULL, NULL,
145  NULL, 0, NULL, NULL };
147 
148 /*
149 :h4."EmptyRegion" - A Region Structure with Zero Area
150 
151 This structure is used to initialize the region to be built in
152 Interior():
153 Note - replaced refcount = 1 init with references = 2 3-26-91 PNM
154 */
155 
156 /*SHARED LINE(S) ORIGINATED HERE*/
157 struct region EmptyRegion = { REGIONTYPE,
159  { 0, 0 }, { 0, 0 },
161  NULL, NULL,
162  0, 0, 0, 0, 0, NULL, NULL,
163  NULL, 0, NULL, NULL };
164 
165 /*
166 :h3 id=edgelist.The "edgelist" Structure
167 
168 Regions are represented by a linked list of 'edgelist' structures.
169 When a region is complete, the structures are paired, one for the
170 left and one for the right edge. While a region is being built,
171 this rule may be violated temporarily.
172 
173 An 'edgelist' structure contains the X values for a given span
174 of Y values. The (X,Y) pairs define an edge. We use the crack
175 and edge coordinate system, so that integer values of X and Y
176 go between pels. The edge is defined between the minimum Y and
177 maximum Y.
178 
179 The linked list is kept sorted from top to bottom, that is, in
180 increasing y. Also, if 'e1' is an edgelist structure and 'e2' is the
181 next one in the list, they must have exactly the same ymin,ymax values
182 or be totally disjoint. These two requirements mean that if e2's ymin
183 is less than e1's ymax, it must be exactly equal to e1's ymin. A
184 sublist of structures with identical ymin and ymax values is called a
185 'swath'.
186 
187 In addition, edgelist structures are separately linked together based
188 on what subpath originally created them; each subpath is kept as a
189 separate circular linked list. This information is ignored unless
190 continuity checking is invoked. See :hdref refid=subpath. for a
191 complete description of this.
192 */
193 
194 
195 /*SHARED LINE(S) ORIGINATED HERE*/
196 
197 /*
198 The "edgelist" structure follows the convention of TYPE1IMAGER user
199 objects, having a type field and a flag field as the first two
200 elements. However, the user never sees "edgelist" structures
201 directly; he is given handles to "region" structures only.
202 
203 By having a type field, we can use the "copy" feature of Allocate()
204 to duplicate edge lists quickly.
205 
206 We also define two flag bits for this structure. The ISDOWN bit is set
207 if the edge is going in the direction of increasing Y. The ISAMBIGUOUS
208 bit is set if the edge is identical to its neighbor (edge->link); such
209 edges may be "left" when they should be "right", or vice versa,
210 unnecessarily confusing the continuity checking logic. The FixSubPaths()
211 routine in HINTS will swap ambiguous edges if that avoids crossing edges;
212 see :hdref refid=fixsubp..
213 */
214 
215 /*SHARED LINE(S) ORIGINATED HERE*/
216 
217 /*
218 :h3.KillRegion() - Destroys a Region
219 
220 KillRegion nominally just decrements the reference count to that region.
221 If the reference count becomes 0, all memory associated with it is
222 freed. We just follow the linked list, freeing as we go, then kill any
223 associated (thresholded) picture.
224 Note - added conditional return based on references 3-26-91 PNM
225 */
226 
227 void KillRegion(
228  register struct region *area) /* area to free */
229 {
230  register struct edgelist *p; /* loop variable */
231  register struct edgelist *next; /* loop variable */
232 
233  if (area->references < 0)
234  t1_abort("KillRegion: negative reference count");
235  if ( (--(area->references) > 1) ||
236  ( (area->references == 1) && !ISPERMANENT(area->flag) ) )
237  return;
238 
239  for (p=area->anchor; p != NULL; p=next) {
240  next = p->link;
241  Free(p);
242  }
243  if (area->thresholded != NULL)
244  KillPicture(area->thresholded);
245  Free(area);
246 }
247 /*
248 :h3.CopyRegion() - Makes a Copy of a Region
249 */
250 struct region *CopyRegion(
251  register struct region *area) /* region to duplicate */
252 {
253  register struct region *r; /* output region built here */
254  register struct edgelist *last; /* loop variable */
255  register struct edgelist *p,*newp; /* loop variables */
256 
257  r = (struct region *)Allocate(sizeof(struct region), area, 0);
258  r->anchor = NULL;
259 
260  for (p=area->anchor; VALIDEDGE(p); p=p->link) {
261 
262  newp = NewEdge(p->xmin, p->xmax, p->ymin, p->ymax, p->xvalues, ISDOWN(p->flag));
263  if (r->anchor == NULL)
264  r->anchor = last = newp;
265  else
266  last->link = newp;
267 
268  last = newp;
269  }
270  if (area->thresholded != NULL)
271  /* replaced DupPicture with Dup() 3-26-91 PNM */
272  r->thresholded = (struct picture *)Dup((struct xobject *)area->thresholded);
273  return(r);
274 }
275 /*
276 :h4.NewEdge() - Allocates and Returns a New "edgelist" Structure
277 
278 We allocate space for the X values contiguously with the 'edgelist'
279 structure that locates them. That way, we only have to free the
280 edgelist structure to free all memory associated with it. Damn
281 clever, huh?
282 */
283 
284 static struct edgelist *NewEdge(
285  pel xmin, pel xmax, /* X extent of edge */
286  pel ymin, pel ymax, /* Y extent of edge */
287  pel *xvalues, /* list of X values for entire edge */
288  int isdown) /* flag: TRUE means edge progresses downward */
289 {
290  static struct edgelist template = {
291  EDGETYPE, 0, 1, NULL, NULL,
292  0, 0, 0, 0, NULL };
293 
294  register struct edgelist *r; /* returned structure */
295  register int iy; /* ymin adjusted for 'long' alignment purposes */
296 
297  IfTrace2((RegionDebug),"....new edge: ymin=%d, ymax=%d ",
298  (int32_t)ymin, (int32_t) ymax);
299  if (ymin >= ymax)
300  t1_abort("newedge: height not positive");
301 /*
302 We are going to copy the xvalues into a newly allocated area. It
303 helps performance if the values are all "long" aligned. We can test
304 if the xvalues are long aligned by ANDing the address with the
305 (sizeof(long) - 1)--if non zero, the xvalues are not aligned well. We
306 set 'iy' to the ymin value that would give us good alignment:
307 */
308 #ifdef _WIN64
309  iy = ymin - (((unsigned __int64) xvalues) & (sizeof(int32_t) - 1)) / sizeof(pel);
310 #else
311  iy = ymin - (((unsigned long) xvalues) & (sizeof(int32_t) - 1)) / sizeof(pel);
312 #endif
313 
314  r = (struct edgelist *)Allocate(sizeof(struct edgelist), &template,
315  (ymax - iy) * sizeof(pel));
316 
317  if (isdown) r->flag = ISDOWN(ON);
318  r->xmin = xmin;
319  r->xmax = xmax;
320  r->ymin = ymin;
321  r->ymax = ymax;
322 
323  r->xvalues = (pel *) FOLLOWING(r);
324  if (ymin != iy) {
325  r->xvalues += ymin - iy;
326  xvalues -= ymin - iy;
327  }
328 
329 /*
330 We must round up (ymax - iy) so we get the ceiling of the number of
331 longs. The destination must be able to hold these extra bytes because
332 Allocate() makes everything it allocates be in multiples of longs.
333 */
334  INT32COPY(&r[1], xvalues, (ymax - iy) * sizeof(pel) + sizeof(int32_t) - 1);
335 
336  IfTrace1((RegionDebug),"result=%p\n", r);
337  return(r);
338 }
339 
340 /*
341 :h2.Building Regions
342 
343 :h3.Interior() - Iterate Through a Path, Building a Region
344 
345 This routine is the workhorse driver routine that iterates through a
346 path, calling the appropriate stepping routines to actually produce the
347 run end "edgelist" structures.
348 
349 :ol.
350 :li."Interior" calls StepLine or StepConic or StepBezier as appropriate
351 to produce run ends.
352 :li.Occasionally these routines will notice a change in Y direction
353 and will call ChangeDirection (through the GOING_TO macro); this is
354 a call back to the REGIONS module.
355 :li.ChangeDirection will call whatever function is in the region
356 structure; for Interior, this function is 'newfilledge'.
357 :li.Newfilledge will call NewEdge to create a new edgelist structure,
358 then, call SortSwath to sort it onto the linked list being built at
359 the region "anchor".
360 :eol.
361 
362 By making the function called by ChangeDirection be a parameter of the
363 region, we allow the same ChangeDirection logic to be used by stroking.
364 */
365 
366 static struct edgelist *SortSwath( struct edgelist *, struct edgelist *,
367  struct edgelist *(*)());
368 
369 /*SHARED LINE(S) ORIGINATED HERE*/
370 
371 struct region *Interior(
372  register struct segment *p, /* take interior of this path */
373  register int fillrule) /* rule to follow if path crosses itself */
374 {
375  register fractpel x,y; /* keeps ending point of path segment */
376  fractpel lastx,lasty; /* previous x,y from path segment before */
377  register struct region *R; /* region I will build */
378  register struct segment *nextP; /* next segment of path */
379  struct fractpoint hint; /* accumulated hint value */
380  char tempflag; /* flag; is path temporary? */
381  char Cflag; /* flag; should we apply continuity? */
382 
383  IfTrace2((MustTraceCalls),". INTERIOR(%p, %d)\n", p, (int32_t) fillrule);
384 
385  if (p == NULL)
386  return(NULL);
387 /*
388 Establish the 'Cflag' continuity flag based on user's fill rule and
389 our own 'Continuity' pragmatic (0: never do continuity, 1: do what
390 user asked, >1: do it regardless).
391 */
392  if (fillrule > 0) {
393  Cflag = Continuity > 0;
394  fillrule -= CONTINUITY;
395  }
396  else
397  Cflag = Continuity > 1;
398 
399  ARGCHECK((fillrule != WINDINGRULE && fillrule != EVENODDRULE),
400  "Interior: bad fill rule", NULL, NULL, (1,p), struct region *);
401 
402  if (p->type == TEXTTYPE)
403 /* if (fillrule != EVENODDRULE)
404  else */
405  return((struct region *)UniquePath(p));
406  if (p->type == STROKEPATHTYPE) {
407  if (fillrule == WINDINGRULE)
408  return((struct region *)DoStroke(p));
409  else
410  p = CoercePath(p);
411  }
412 
413  R = (struct region *)Allocate(sizeof(struct region), &EmptyRegion, 0);
414 
415  ARGCHECK(!ISPATHANCHOR(p), "Interior: bad path", p, R, (0), struct region *);
416  ARGCHECK((p->type != MOVETYPE), "Interior: path not closed", p, R, (0), struct region *);
417 
418 
419 /* changed definition from !ISPERMANENT to references <= 1 3-26-91 PNM */
420  tempflag = (p->references <= 1); /* only first segment in path is so marked */
421  if (!ISPERMANENT(p->flag)) p->references -= 1;
422 
423  R->newedgefcn = newfilledge;
424 /*
425 Believe it or not, "R" is now completely initialized. We are counting
426 on the copy of template to get other fields the way we want them,
427 namely
428 :ol.
429 :li.anchor = NULL
430 :li.xmin, ymin, xmax, ymax, to minimum and maximum values respectively.
431 :eol.
432 Anchor = NULL is very
433 important to ChangeDirection.
434 See :hdref refid=CD..
435 
436 To minimize problems of "wrapping" in our pel arithmetic, we keep an
437 origin of the region which is the first move. Hopefully, that keeps
438 numbers within plus or minus 32K pels.
439 */
440  R->origin.x = 0/*TOFRACTPEL(NEARESTPEL(p->dest.x))*/;
441  R->origin.y = 0/*TOFRACTPEL(NEARESTPEL(p->dest.y))*/;
442  lastx = - R->origin.x;
443  lasty = - R->origin.y;
444 /*
445 ChangeDirection initializes other important fields in R, such as
446 lastdy, edge, edgeYstop, edgexmin, and edgexmax. The first segment
447 is a MOVETYPE, so it will be called first.
448 */
449 /*
450 The hints data structure must be initialized once for each path.
451 */
452 
453  if (ProcessHints)
454  InitHints(); /* initialize hint data structure */
455 
456  while (p != NULL) {
457 
458  x = lastx + p->dest.x;
459  y = lasty + p->dest.y;
460 
461  IfTrace2((HintDebug > 0),"Ending point = (%d,%d)\n", x, y);
462 
463  nextP = p->link;
464 
465 /*
466 Here we start the hints processing by initializing the hint value to
467 zero. If ProcessHints is FALSE, the value will remain zero.
468 Otherwise, hint accumulates the computed hint values.
469 */
470 
471  hint.x = hint.y = 0;
472 
473 /*
474 If we are processing hints, and this is a MOVE segment (other than
475 the first on the path), we need to close (reverse) any open hints.
476 */
477 
478  if (ProcessHints)
479  if ((p->type == MOVETYPE) && (p->last == NULL)) {
480  CloseHints(&hint);
481  IfTrace2((HintDebug>0),"Closed point= (%d,%d)\n",
482  x+hint.x, y+hint.y);
483  }
484 
485 /*
486 Next we run through all the hint segments (if any) attached to this
487 segment. If ProcessHints is TRUE, we will accumulate computed hint
488 values. In either case, nextP will be advanced to the first non-HINT
489 segment (or NULL), and each hint segment will be freed if necessary.
490 */
491 
492  while ((nextP != NULL) && (nextP->type == HINTTYPE)) {
493  if (ProcessHints)
494  ProcessHint((struct hintsegment *)nextP, x + hint.x, y + hint.y, &hint);
495 
496  {
497  register struct segment *saveP = nextP;
498 
499  nextP = nextP->link;
500  if (tempflag)
501  Free(saveP);
502  }
503  }
504 
505 /*
506 We now apply the full hint value to the ending point of the path segment.
507 */
508 
509  x += hint.x;
510  y += hint.y;
511 
512  IfTrace2((HintDebug>0),"Hinted ending point = (%d,%d)\n", x, y);
513 
514  switch(p->type) {
515 
516  case LINETYPE:
517  StepLine(R, lastx, lasty, x, y);
518  break;
519 
520  case CONICTYPE:
521  {
522 
523 /*
524 For a conic curve, we apply half the hint value to the conic midpoint.
525 */
526 
527  }
528  break;
529 
530  case BEZIERTYPE:
531  {
532  register struct beziersegment *bp = (struct beziersegment *) p;
533 
534 /*
535 For a Bezier curve, we apply the full hint value to the Bezier C point.
536 */
537 
538  StepBezier(R, lastx, lasty,
539  lastx + bp->B.x, lasty + bp->B.y,
540  lastx + bp->C.x + hint.x,
541  lasty + bp->C.y + hint.y,
542  x, y);
543  }
544  break;
545 
546  case MOVETYPE:
547 /*
548 At this point we have encountered a MOVE segment. This breaks the
549 path, making it disjoint.
550 */
551  if (p->last == NULL) /* i.e., not first in path */
552  ChangeDirection(CD_LAST, R, lastx, lasty, (fractpel) 0);
553 
555 /*
556 We'll just double check for closure here. We forgive an appended
557 MOVETYPE at the end of the path, if it isn't closed:
558 */
559  if (!ISCLOSED(p->flag) && p->link != NULL)
560  return((struct region *)ArgErr("Fill: sub-path not closed", p, NULL));
561  break;
562 
563  default:
564  t1_abort("Interior: path type error");
565  }
566 /*
567 We're done with this segment. Advance to the next path segment in
568 the list, freeing this one if necessary:
569 */
570  lastx = x; lasty = y;
571 
572  if (tempflag)
573  Free(p);
574  p = nextP;
575  }
576  ChangeDirection(CD_LAST, R, lastx, lasty, (fractpel) 0);
577  R->ending.x = lastx;
578  R->ending.y = lasty;
579 /*
580 Finally, clean up the region's based on the user's 'fillrule' request:
581 */
582  if (Cflag)
584  if (fillrule == WINDINGRULE)
585  Unwind(R->anchor);
586  return(R);
587 }
588 /*
589 :h4.Unwind() - Discards Edges That Fail the Winding Rule Test
590 
591 The winding rule says that upward going edges should be paired with
592 downward going edges only, and vice versa. So, if two upward edges
593 or two downward edges are nominally left/right pairs, Unwind() should
594 discard the second one. Everything should balance; we should discard
595 an even number of edges; of course, we abort if we don't.
596 */
597 static void Unwind(
598  register struct edgelist *area) /* input area modified in place */
599 {
600  register struct edgelist *last,*next; /* struct before and after current one */
601  register int y; /* ymin of current swath */
602  register int count,newcount; /* winding count registers */
603 
604  IfTrace1((RegionDebug>0),"...Unwind(%p)\n", area);
605 
606  while (VALIDEDGE(area)) {
607 
608  count = 0;
609  y = area->ymin;
610 
611  do {
612  next = area->link;
613 
614  if (ISDOWN(area->flag))
615  newcount = count + 1;
616  else
617  newcount = count - 1;
618 
619  if (count == 0 || newcount == 0)
620  last = area;
621  else
622  discard(last, next);
623 
624  count = newcount;
625  area = next;
626 
627  } while (area != NULL && area->ymin == y);
628 
629  if (count != 0)
630  t1_abort("Unwind: uneven edges");
631  }
632 }
633 /*
634 :h3."workedge" Array
635 
636 This is a statically allocated array where edges are built
637 before being copied into more permanent storage by NewEdge().
638 */
639 
640 #ifndef MAXEDGE
641 #define MAXEDGE 1000
642 #endif
643 
647 
648 /*
649 :h3 id=cd.ChangeDirection() - Called When Y Direction Changes
650 
651 The rasterizing routines call this entry point when they detect
652 a change in Y. We then build the current edge and sort it into
653 emerging edgelist at 'anchor' by calling whatever "newedgefcn"
654 is appropriate.
655 */
656 
657 void ChangeDirection(
658  int type, /* CD_FIRST, CD_CONTINUE, or CD_LAST */
659  register struct region *R, /* region in which we are changing direction */
660  fractpel x, fractpel y, /* current beginning x,y */
661  fractpel dy) /* direction and magnitude of change in y */
662 {
663  register fractpel ymin,ymax; /* minimum and maximum Y since last call */
664  register pel iy; /* nearest integer pel to 'y' */
665  register pel idy; /* nearest integer pel to 'dy' */
666  register int ydiff; /* allowed Y difference in 'currentworkarea' */
667 
668  IfTrace4((RegionDebug>0),"Change Y direction (%d) from (%d,%d), dy=%d\n",
669  (int32_t) type, x, y, dy);
670 
671  if (type != CD_FIRST) {
672 
673  if (R->lastdy > 0) {
674  ymin = R->firsty;
675  ymax = y;
676  }
677  else {
678  ymin = y;
679  ymax = R->firsty;
680  }
681 
682  if (ymax < ymin)
683  t1_abort("negative sized edge?");
684 
685 
686  /* FIXME: there are not as much parameters as here. */
687  (*R->newedgefcn)(R, R->edgexmin, R->edgexmax, ymin, ymax,
688  R->lastdy > 0 /*, x_at_ymin, x_at_ymax */);
689 
690  }
691 
692  R->firsty = y;
693  R->firstx = x;
694  R->lastdy = dy;
695 
696  iy = NEARESTPEL(y);
697  idy = NEARESTPEL(dy);
698  if (currentworkarea != workedge && idy < MAXEDGE && idy > -MAXEDGE) {
702  }
703  ydiff = currentsize - 1;
704  if (dy > 0) {
705  R->edge = &currentworkarea[-iy];
706  R->edgeYstop = TOFRACTPEL(ydiff + iy) + FPHALF;
707  }
708  else {
709  R->edge = &currentworkarea[ydiff - iy];
710  R->edgeYstop = TOFRACTPEL(iy - ydiff) - FPHALF;
711  }
712  R->edgexmax = R->edgexmin = x;
713 /*
714 If this is the end of a subpath, we complete the subpath circular
715 chain:
716 */
717  if (type == CD_LAST && R->lastedge != NULL) {
718  register struct edgelist *e = R->firstedge;
719 
720  while (e->subpath != NULL)
721  e = e->subpath;
722  e->subpath = R->lastedge;
723  R->lastedge = R->firstedge = NULL;
724  }
725 }
726 /*
727 :h3 id=newfill.newfilledge() - Called When We Have a New Edge While Filling
728 
729 This is the prototypical "newedge" function passed to "Rasterize" and
730 stored in "newedgefcn" in the region being built.
731 
732 If the edge is non-null, we sort it onto the list of edges we are
733 building at "anchor".
734 
735 This function also has to keep the bounding box of the region
736 up to date.
737 */
738 static struct edgelist *swathxsort(struct edgelist *, struct edgelist *);
739 
740 static void newfilledge(register struct region *R,
742 {
743  register pel pelxmin,pelymin,pelxmax,pelymax; /* pel versions of bounds */
744  register struct edgelist *edge; /* newly created edge */
745 
746  pelymin = NEARESTPEL(ymin);
747  pelymax = NEARESTPEL(ymax);
748  if (pelymin == pelymax)
749  return;
750 
751  pelxmin = NEARESTPEL(xmin);
752  pelxmax = NEARESTPEL(xmax);
753 
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;
758 
759  edge = NewEdge(pelxmin, pelxmax, pelymin, pelymax, &R->edge[pelymin], isdown);
760  edge->subpath = R->lastedge;
761  R->lastedge = edge;
762  if (R->firstedge == NULL)
763  R->firstedge = edge;
764 
765  R->anchor = SortSwath(R->anchor, edge, swathxsort);
766 
767 }
768 
769 /*
770 :h2.Sorting Edges
771 
772 :h3.SortSwath() - Vertically Sort an Edge into a Region
773 
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
780 SwathUnion()).
781 
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.
788 */
789 
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 */
792 
793 static struct edgelist *SortSwath(
794  struct edgelist *anchor, /* list being built */
795  register struct edgelist *edge, /* incoming edge or pair of edges */
796  struct edgelist *(*swathfcn)()) /* horizontal sorter */
797 {
798  register struct edgelist *before,*after;
799  struct edgelist base;
800 
801  if (RegionDebug > 0) {
802  IfTrace3(TRUE,"SortSwath(anchor=%p, edge=%p, fcn=%p)\n",
803  anchor, edge, swathfcn);
804  }
805  if (anchor == NULL)
806  return(edge);
807 
808  before = &base;
809  before->ymin = before->ymax = MINPEL;
810  before->link = after = anchor;
811 
812 /*
813 If the incoming edge is above the current list, we connect the current
814 list to the bottom of the incoming edge. One slight complication is
815 if the incoming edge overlaps into the current list. Then, we
816 first split the incoming edge in two at the point of overlap and recursively
817 call ourselves to sort the bottom of the split into the current list:
818 */
819  if (TOP(edge) < TOP(after)) {
820  if (BOTTOM(edge) > TOP(after)) {
821 
822  after = SortSwath(after, splitedge(edge, TOP(after)), swathfcn);
823  }
824  vertjoin(edge, after);
825  return(edge);
826  }
827 /*
828 At this point the top of edge is not higher than the top of the list,
829 which we keep in 'after'. We move the 'after' point down the list,
830 until the top of the edge occurs in the swath beginning with 'after'.
831 
832 If the bottom of 'after' is below the bottom of the edge, we have to
833 split the 'after' swath into two parts, at the bottom of the edge.
834 If the bottom of 'after' is above the bottom of the swath,
835 */
836 
837  while (VALIDEDGE(after)) {
838 
839  if (TOP(after) == TOP(edge)) {
840  if (BOTTOM(after) > BOTTOM(edge))
842  else if (BOTTOM(after) < BOTTOM(edge)) {
844  splitedge(edge, BOTTOM(after)), swathfcn);
845  }
846  break;
847  }
848  else if (TOP(after) > TOP(edge)) {
849  IfTrace0((BOTTOM(edge) < TOP(after) && RegionDebug > 0),
850  "SortSwath: disjoint edges\n");
851  if (BOTTOM(edge) > TOP(after)) {
853  splitedge(edge, TOP(after)), swathfcn);
854  }
855  break;
856  }
857  else if (BOTTOM(after) > TOP(edge))
859 
860  before = after;
861  after = after->link;
862  }
863 
864 /*
865 At this point 'edge' exactly corresponds in height to the current
866 swath pointed to by 'after'.
867 */
868  if (after != NULL && TOP(after) == TOP(edge)) {
869  before = (*swathfcn)(before, edge);
870  after = before->link;
871  }
872 /*
873 At this point 'after' contains all the edges after 'edge', and 'before'
874 contains all the edges before. Whew! A simple matter now of adding
875 'edge' to the linked list in its rightful place:
876 */
877  before->link = edge;
878  if (RegionDebug > 1) {
879  IfTrace3(TRUE,"SortSwath: in between %p and %p are %p",
880  before, after, edge);
881  while (edge->link != NULL) {
882  edge = edge->link;
883  IfTrace1(TRUE," and %p", edge);
884  }
885  IfTrace0(TRUE,"\n");
886  }
887  else
888  for (; edge->link != NULL; edge = edge->link) { ; }
889 
890  edge->link = after;
891  return(base.link);
892 }
893 
894 /*
895 :h3.splitedge() - Split an Edge or Swath in Two at a Given Y Value
896 
897 This function returns the edge or swath beginning at the Y value, and
898 is guaranteed not to change the address of the old swath while splitting
899 it.
900 */
901 
902 static struct edgelist *splitedge(
903  struct edgelist *list, /* area to split */
904  register pel y) /* Y value to split list at */
905 {
906  register struct edgelist *new; /* anchor for newly built list */
907  register struct edgelist *last; /* end of newly built list */
908  register struct edgelist *r; /* temp pointer to new structure */
909  register struct edgelist *lastlist; /* temp pointer to last 'list' value */
910 
911  IfTrace2((RegionDebug > 1),"splitedge of %p at %d ", list, (int32_t) y);
912 
913  lastlist = new = NULL;
914 
915  while (list != NULL) {
916  if (y < list->ymin)
917  break;
918  if (y >= list->ymax)
919  t1_abort("splitedge: above top of list");
920  if (y == list->ymin)
921  t1_abort("splitedge: would be null");
922 
923  r = (struct edgelist *)Allocate(sizeof(struct edgelist), list, 0);
924 /*
925 At this point 'r' points to a copy of the single structure at 'list'.
926 We will make 'r' be the new split 'edgelist'--the lower half.
927 We don't bother to correct 'xmin' and 'xmax', we'll take the
928 the pessimistic answer that results from using the old values.
929 */
930  r->ymin = y;
931  r->xvalues = list->xvalues + (y - list->ymin);
932 /*
933 Note that we do not need to allocate new memory for the X values,
934 they can remain with the old "edgelist" structure. We do have to
935 update that old structure so it is not as high:
936 */
937  list->ymax = y;
938 /*
939 Insert 'r' in the subpath chain:
940 */
941  r->subpath = list->subpath;
942  list->subpath = r;
943 /*
944 Now attach 'r' to the list we are building at 'new', and advance
945 'list' to point to the next element in the old list:
946 */
947  if (new == NULL)
948  new = r;
949  else
950  last->link = r;
951  last = r;
952  lastlist = list;
953  list = list->link;
954  }
955 /*
956 At this point we have a new list built at 'new'. We break the old
957 list at 'lastlist', and add the broken off part to the end of 'new'.
958 Then, we return the caller a pointer to 'new':
959 */
960  if (new == NULL)
961  t1_abort("null splitedge");
962  lastlist->link = NULL;
963  last->link = list;
964  IfTrace1((RegionDebug > 1),"yields %p\n", new);
965  return(new);
966 }
967 
968 /*
969 :h3.vertjoin() - Join Two Disjoint Edge Lists Vertically
970 
971 The two edges must be disjoint vertically.
972 */
973 static void vertjoin(register struct edgelist *top,
974  register struct edgelist *bottom)
975 {
976  if (BOTTOM(top) > TOP(bottom))
977  t1_abort("vertjoin not disjoint");
978 
979  for (; top->link != NULL; top=top->link) { ; }
980 
981  top->link = bottom;
982  return;
983 }
984 
985 /*
986 :h3.swathxsort() - Sorting by X Values
987 
988 We need to sort 'edge' into its rightful
989 place in the swath by X value, taking care that we do not accidentally
990 advance to the next swath while searching for the correct X value. Like
991 all swath functions, this function returns a pointer to the edge
992 BEFORE the given edge in the sort.
993 */
994 
995 static struct edgelist *swathxsort(
996  register struct edgelist *before0, /* edge before this swath */
997  register struct edgelist *edge) /* input edge */
998 {
999  register struct edgelist *before;
1000  register struct edgelist *after;
1001  register pel y = 0;
1002 
1003  before = before0;
1004  after = before->link;
1005 
1006  while (after != NULL && TOP(after) == TOP(edge)) {
1007 
1008  register pel *x1,*x2;
1009 
1010  y = TOP(edge);
1011  x1 = after->xvalues;
1012  x2 = edge->xvalues;
1013 
1014  while (y < BOTTOM(edge) && *x1 == *x2) {
1015  x1++; x2++; y++;
1016  }
1017  if (y >= BOTTOM(edge)) {
1018  edge->flag |= ISAMBIGUOUS(ON);
1019  after->flag |= ISAMBIGUOUS(ON);
1020  break;
1021  }
1022 
1023  if (*x1 >= *x2)
1024  break;
1025 
1026  before = after;
1027  after = after->link;
1028  }
1029 
1030 /*
1031 At this point, 'edge' is between 'before' and 'after'. If 'edge' didn't
1032 cross either of those other edges, we would be done. We check for
1033 crossing. If it does cross, we split the problem up by calling SortSwath
1034 recursively with the part of the edge that is below the crossing point:
1035 */
1036 {
1037  register int h0,h; /* height of edge--number of scans */
1038 
1039  h0 = h = BOTTOM(edge) - y;
1040  y -= TOP(edge);
1041 
1042  if (h0 <= 0) {
1043  IfTrace0((RegionDebug>0),"swathxsort: exactly equal edges\n");
1044  return(before);
1045  }
1046 
1047  if (TOP(before) == TOP(edge))
1048  h -= crosses(h, &before->xvalues[y], &edge->xvalues[y]);
1049  if (after != NULL && TOP(after) == TOP(edge))
1050  h -= crosses(h, &edge->xvalues[y], &after->xvalues[y]);
1051 
1052  if (h < h0) {
1053  SortSwath(before0->link,
1054  splitedge(edge, TOP(edge) + y + h),
1055  swathxsort);
1056 
1057  }
1058 }
1059 
1060  return(before);
1061 }
1062 /*
1063 :h3.SwathUnion() - Union Two Edges by X Value
1064 
1065 We have a left and right edge that must be unioned into a growing
1066 swath. If they are totally disjoint, they are just added in. The
1067 fun comes in they overlap the existing edges. Then some edges
1068 will disappear.
1069 */
1070 
1071 static struct edgelist *SwathUnion(
1072  register struct edgelist *before0, /* edge before the swath */
1073  register struct edgelist *edge) /* list of two edges to be unioned */
1074 {
1075  register int h; /* saves height of edge */
1076  register struct edgelist *rightedge; /* saves right edge of 'edge' */
1077  register struct edgelist *before,*after; /* edge before and after */
1078  int h0; /* saves initial height */
1079 
1080  IfTrace2((RegionDebug > 1),"SwathUnion entered, before=%p, edge=%p\n",
1081  before0, edge);
1082 
1083  h0 = h = edge->ymax - edge->ymin;
1084  if (h <= 0)
1085  t1_abort("SwathUnion: 0 height swath?");
1086 
1087  before = before0;
1088  after = before->link;
1089 
1090  while (after != NULL && TOP(after) == TOP(edge)) {
1091  register struct edgelist *right;
1092 
1093  right = after->link;
1094  if (right->xvalues[0] >= edge->xvalues[0])
1095  break;
1096  before = right;
1097  after = before->link;
1098  }
1099 /*
1100 This is the picture at this point. 'L' indicates a left hand edge,
1101 'R' indicates the right hand edge.
1102 '<--->' indicates the degree of uncertainty as to its placement
1103 relative to other edges:
1104 :xmp atomic.
1105  before after
1106  R <---L----> R L R L R
1107  <---L---> <------R-------------------------->
1108  edge
1109 :exmp.
1110 In case the left of 'edge' touches 'before', we need to reduce
1111 the height by that amount.
1112 */
1113  if (TOP(before) == TOP(edge))
1114  h -= touches(h, before->xvalues, edge->xvalues);
1115 
1116  rightedge = edge->link;
1117 
1118  if (after == NULL || TOP(after) != TOP(edge) ||
1119  after->xvalues[0] > rightedge->xvalues[0]) {
1120  IfTrace2((RegionDebug > 1),
1121  "SwathUnion starts disjoint: before=%p after=%p\n",
1122  before, after);
1123 /*
1124 On this side of the the above 'if', the new edge is disjoint from the
1125 existing edges in the swath. This is the picture:
1126 :xmp atomic.
1127  before after
1128  R L R L R L R
1129  L R
1130  edge
1131 :exmp.
1132 We will verify it remains disjoint for the entire height. If the
1133 situation changes somewhere down the edge, we split the edge at that
1134 point and recursively call ourselves (through 'SortSwath') to figure
1135 out the new situation:
1136 */
1137  if (after != NULL && TOP(after) == TOP(edge))
1138  h -= touches(h, rightedge->xvalues, after->xvalues);
1139  if (h < h0)
1140  SortSwath(before0->link, splitedge(edge, edge->ymin + h), SwathUnion);
1141  /* go to "return" this edge pair; it is totally disjoint */
1142  }
1143  else {
1144 /*
1145 At this point, at the 'else', we know that the
1146 new edge overlaps one or more pairs in the existing swath. Here is
1147 a picture of our knowledge and uncertainties:
1148 :xmp atomic.
1149  before after
1150  R L R L R L R
1151  <---L---> <---R------------------->
1152  edge
1153 :exmp.
1154 We need to move 'after' along until it is to the right of the
1155 right of 'edge'. ('After' should always point to a left edge of a pair:)
1156 */
1157  register struct edgelist *left; /* variable to keep left edge in */
1158 
1159  do {
1160  left = after;
1161  after = (after->link)->link;
1162 
1163  } while (after != NULL && TOP(after) == TOP(edge)
1164  && after->xvalues[0] <= rightedge->xvalues[0]);
1165 /*
1166 At this point this is the picture:
1167 :xmp atomic.
1168  before left after
1169  R L R L R L R
1170  <---L---> <---R--->
1171  edge
1172 :exmp.
1173 We need to verify that the situation stays like this all the way
1174 down the edge. Again, if the
1175 situation changes somewhere down the edge, we split the edge at that
1176 point and recursively call ourselves (through 'SortSwath') to figure
1177 out the new situation:
1178 */
1179 
1180  h -= crosses(h, left->xvalues, rightedge->xvalues);
1181  h -= crosses(h, edge->xvalues, ((before->link)->link)->xvalues);
1182 
1183  if (after != NULL && TOP(after) == TOP(edge))
1184 
1185  h -= touches(h, rightedge->xvalues, after->xvalues);
1186 
1187  IfTrace3((RegionDebug > 1),
1188  "SwathUnion is overlapped until %d: before=%p after=%p\n",
1189  (int32_t) TOP(edge) + h, before, after);
1190 /*
1191 OK, if we touched either of our neighbors we need to split at that point
1192 and recursively sort the split edge onto the list. One tricky part
1193 is that when we recursively sort, 'after' will change if it was not
1194 in our current swath:
1195 */
1196  if (h < h0) {
1197  SortSwath(before0->link,
1198  splitedge(edge, edge->ymin + h),
1199  SwathUnion);
1200 
1201  if (after == NULL || TOP(after) != TOP(edge))
1202  for (after = before0->link;
1203  TOP(after) == TOP(edge);
1204  after = after->link) { ; }
1205  }
1206 /*
1207 Now we need to augment 'edge' by the left and right of the overlapped
1208 swath, and to discard all edges between before and after, because they
1209 were overlapped and have been combined with the new incoming 'edge':
1210 */
1211  edge->xmin = MIN(edge->xmin, (before->link)->xmin);
1212  edge->xmax = MIN(edge->xmax, (before->link)->xmax);
1213  edgemin(h, edge->xvalues, (before->link)->xvalues);
1214  rightedge->xmin = MAX(rightedge->xmin, (left->link)->xmin);
1215  rightedge->xmax = MAX(rightedge->xmax, (left->link)->xmax);
1216  edgemax(h, rightedge->xvalues, (left->link)->xvalues);
1217  discard(before, after);
1218  }
1219  return(before);
1220 }
1221 #if 0
1222 /*
1223 :h3.swathrightmost() - Simply Sorts New Edge to Rightmost of Swath
1224 
1225 Like all swath functions, this function returns a pointer to the edge
1226 BEFORE the given edge in the sort.
1227 */
1228 
1229 struct edgelist *swathrightmost(
1230  register struct edgelist *before, /* edge before this swath */
1231  register struct edgelist *edge) /* input edge */
1232 {
1233  register struct edgelist *after;
1234 
1235  after = before->link;
1236 
1237  while (after != NULL && TOP(after) == TOP(edge)) {
1238  before = after;
1239  after = after->link;
1240  }
1241 
1242  return(before);
1243 
1244 }
1245 #endif
1246 /*
1247 :h3.touches() - Returns the Remaining Height When Two Edges Touch
1248 
1249 So, it will return 0 if they never touch. Allows incredibly(?) mnemonic
1250 if (touches(...)) construct.
1251 */
1252 
1253 static int touches(int h, register pel *left, register pel *right)
1254 {
1255  for (; h > 0; h--)
1256  if (*left++ >= *right++)
1257  break;
1258  return(h);
1259 }
1260 /*
1261 :h3.crosses() - Returns the Remaining Height When Two Edges Cross
1262 
1263 So, it will return 0 if they never cross.
1264 */
1265 
1266 static int crosses(register int h, register pel *left, register pel *right)
1267 {
1268  for (; h > 0; h--)
1269  if (*left++ > *right++)
1270  break;
1271  return(h);
1272 }
1273 #if 0
1274 /*
1275 :h3.cedgemin() - Stores the Mininum of an Edge and an X Value
1276 */
1277 
1278 static void cedgemin(register int h, register pel *e1, register pel x)
1279 {
1280  for (; --h >= 0; e1++)
1281  if (*e1 > x)
1282  *e1 = x;
1283 }
1284 /*
1285 :h3.cedgemax() - Stores the Maximum of an Edge and an X Value
1286 */
1287 
1288 static void cedgemax(register int h, register pel *e1, register pel x)
1289 {
1290  for (; --h >= 0; e1++)
1291  if (*e1 < x)
1292  *e1 = x;
1293 }
1294 #endif
1295 /*
1296 :h3.edgemin() - Stores the Mininum of Two Edges in First Edge
1297 */
1298 
1299 static void edgemin(register int h, register pel *e1, register pel *e2)
1300 {
1301  for (; --h >= 0; e1++,e2++)
1302  if (*e1 > *e2)
1303  *e1 = *e2;
1304 }
1305 /*
1306 :h3.edgemax() - Stores the Maximum of Two Edges in First Edge
1307 */
1308 
1309 static void edgemax(register int h, register pel *e1, register pel *e2)
1310 {
1311  for (; --h >= 0; e1++,e2++)
1312  if (*e1 < *e2)
1313  *e1 = *e2;
1314 }
1315 /*
1316 :h3 id=discard.discard() - Discard All Edges Between Two Edges
1317 
1318 At first glance it would seem that we could discard an edgelist
1319 structure merely by unlinking it from the list and freeing it. You are
1320 wrong, region-breath! For performance, the X values associated with an
1321 edge are allocated contiguously with it. So, we free the X values when
1322 we free a structure. However, once an edge has been split, we are no
1323 longer sure which control block actually is part of the memory block
1324 that contains the edges. Rather than trying to decide, we play it safe
1325 and never free part of a region.
1326 
1327 So, to mark a 'edgelist' structure as discarded, we move it to the end
1328 of the list and set ymin=ymax.
1329 */
1330 
1331 static void discard(register struct edgelist *left, register struct edgelist *right)
1332 {
1333  register struct edgelist *beg,*end,*p;
1334 
1335  IfTrace2((RegionDebug > 0),"discard: l=%p, r=%p\n", left, right);
1336 
1337  beg = left->link;
1338  if (beg == right)
1339  return;
1340 
1341  for (p = beg; p != right; p = p->link) {
1342  if (p->link == NULL && right != NULL)
1343  t1_abort("discard(): ran off end");
1344  IfTrace1((RegionDebug > 0),"discarding %p\n", p);
1345  p->ymin = p->ymax = 32767;
1346  end = p;
1347  }
1348  /*
1349  * now put the chain beg/end at the end of right, if it is not
1350  * already there:
1351  */
1352  if (right != NULL) {
1353  left->link = right;
1354  while (right->link != NULL)
1355  right = right->link;
1356  right->link = beg;
1357  }
1358  end->link = NULL;
1359 }
1360 
1361 /*
1362 :h2.Changing the Representation of Regions
1363 
1364 For convenience and/or performance, we sometimes like to change the way
1365 regions are represented. This does not change the object itself, just
1366 the representation, so these transformations can be made on a permanent
1367 region.
1368 
1369 */
1370 
1371 void MoveEdges(
1372  register struct region *R, /* region to modify */
1373  register fractpel dx, /* delta X ... */
1374  register fractpel dy) /* ... and Y to move edge list by */
1375 {
1376  register struct edgelist *edge; /* for looping through edges */
1377 
1378  R->origin.x += dx;
1379  R->origin.y += dy;
1380  R->ending.x += dx;
1381  R->ending.y += dy;
1382  if (R->thresholded != NULL) {
1383  R->thresholded->origin.x -= dx;
1384  R->thresholded->origin.y -= dy;
1385  }
1386 /*
1387 From now on we will deal with dx and dy as integer pel values:
1388 */
1389  dx = NEARESTPEL(dx);
1390  dy = NEARESTPEL(dy);
1391  if (dx == 0 && dy == 0)
1392  return;
1393 
1394  R->xmin += dx;
1395  R->xmax += dx;
1396  R->ymin += dy;
1397  R->ymax += dy;
1398 
1399  for (edge = R->anchor; VALIDEDGE(edge); edge = edge->link) {
1400  edge->ymin += dy;
1401  edge->ymax += dy;
1402  if (dx != 0) {
1403  register int h; /* loop index; height of edge */
1404  register pel *Xp; /* loop pointer to X values */
1405 
1406  edge->xmin += dx;
1407  edge->xmax += dx;
1408  for (Xp = edge->xvalues, h = edge->ymax - edge->ymin;
1409  --h >= 0; )
1410  *Xp++ += dx;
1411  }
1412  }
1413 }
1414 
1415 /*
1416 :h3.UnJumble() - Sort a Region Top to Bottom
1417 
1418 It is an open question whether it pays in general to do this.
1419 */
1420 
1421 void UnJumble(
1422  struct region *region) /* region to sort */
1423 {
1424  register struct edgelist *anchor; /* new lists built here */
1425  register struct edgelist *edge; /* edge pointer for loop */
1426  register struct edgelist *next; /* ditto */
1427 
1428  anchor = NULL;
1429 
1430  for (edge=region->anchor; VALIDEDGE(edge); edge=next) {
1431  if (edge->link == NULL)
1432  t1_abort("UnJumble: unpaired edge?");
1433  next = edge->link->link;
1434  edge->link->link = NULL;
1435  anchor = SortSwath(anchor, edge, SwathUnion);
1436  }
1437 
1438  if (edge != NULL)
1439  vertjoin(anchor, edge);
1440 
1441  region->anchor = anchor;
1442  region->flag &= ~~ISJUMBLED(ON);
1443 }
1444 
1445 /*
1446 :h2.Miscelaneous Routines
1447 
1448 :h3.MoreWorkArea() - Allocate New Space for "edge"
1449 
1450 Our strategy is to temporarily allocate an array to hold this
1451 unexpectedly large edge. ChangeDirection frees this array any time
1452 it gets a shorter 'dy'.
1453 */
1454 
1455 /*ARGSUSED*/
1456 void MoreWorkArea(
1457  struct region *R, /* region we are generating */
1458  fractpel x1, fractpel y1, /* starting point of line */
1459  fractpel x2, fractpel y2) /* ending point of line */
1460 {
1461  register int idy; /* integer dy of line */
1462 
1463  idy = NEARESTPEL(y1) - NEARESTPEL(y2);
1464  if (idy < 0) idy = - idy;
1465 
1466  /*
1467  * we must add one to the delta for the number of run ends we
1468  * need to store:
1469  */
1470  if (++idy > currentsize) {
1471  IfTrace1((RegionDebug > 0),"Allocating edge of %d pels\n", idy);
1472  if (currentworkarea != workedge)
1474  currentworkarea = (pel *)Allocate(0, NULL, idy * sizeof(pel));
1475  currentsize = idy;
1476  }
1478 }
1479 
1480 /*
1481 :h3.RegionBounds() - Returns Bounding Box of a Region
1482 */
1483 
1484 struct segment *RegionBounds(register struct region *R)
1485 {
1486  register struct segment *path; /* returned path */
1487 
1488  path = BoxPath(IDENTITY, R->ymax - R->ymin, R->xmax - R->xmin);
1489  path = Join(PathSegment(MOVETYPE, R->origin.x + TOFRACTPEL(R->xmin),
1490  R->origin.y + TOFRACTPEL(R->ymin) ),
1491  path);
1492  return(path);
1493 }
1494 
1495 #if 0
1496 /*
1497 :h2.Formatting/Dump Routines for Debug
1498 
1499 :h3.DumpArea() - Display a Region
1500 */
1501 void DumpArea(register struct region *area)
1502 {
1503  IfTrace1(TRUE,"Dumping area %p,", area);
1504  IfTrace4(TRUE," X %d:%d Y %d:%d;", (int32_t) area->xmin,
1505  (int32_t) area->xmax, (int32_t) area->ymin,(int32_t) area->ymax);
1506  IfTrace4(TRUE," origin=(%d,%d), ending=(%d,%d)\n",
1507  area->origin.x, area->origin.y, area->ending.x, area->ending.y);
1508  DumpEdges(area->anchor);
1509 }
1510 
1511 #define INSWATH(p, y0, y1) (p != NULL && p->ymin == y0 && p->ymax == y1)
1512 /*
1513 :h3.DumpEdges() - Display Run End Lists (Edge Lists)
1514 */
1515 
1516 static pel RegionDebugYMin = MINPEL;
1517 static pel RegionDebugYMax = MAXPEL;
1518 
1519 void DumpEdges(register struct edgelist *edges)
1520 {
1521  register struct edgelist *p,*p2;
1522  register pel ymin = MINPEL;
1523  register pel ymax = MINPEL;
1524  register int y;
1525 
1526  if (edges == NULL) {
1527  IfTrace0(TRUE," NULL area.\n");
1528  return;
1529  }
1530  if (RegionDebug <= 1) {
1531  for (p=edges; p != NULL; p = p->link) {
1532  edgecheck(p, ymin, ymax);
1533  ymin = p->ymin; ymax = p->ymax;
1534  IfTrace3(TRUE,". at %p type=%d flag=%x",
1535  p, (int32_t) p->type,(int32_t) p->flag);
1536  IfTrace4(TRUE," bounding box HxW is %dx%d at (%d,%d)\n",
1537  (int32_t) ymax - ymin, (int32_t) p->xmax - p->xmin,
1538  (int32_t) p->xmin, (int32_t) ymin);
1539  }
1540  }
1541  else {
1542 
1543  for (p2=edges; p2 != NULL; ) {
1544 
1545  edgecheck(p2, ymin, ymax);
1546  ymin = p2->ymin;
1547  ymax = p2->ymax;
1548 
1549  if (RegionDebug > 3 || (ymax > RegionDebugYMin
1550  && ymin < RegionDebugYMax)) {
1551  IfTrace2 (TRUE,". Swath from %d to %d:\n",
1552  ymin, ymax);
1553  for (p=p2; INSWATH(p,ymin,ymax); p = p->link) {
1554  IfTrace4(TRUE,". . at %p[%x] range %d:%d, ",
1555  p, (int32_t) p->flag,
1556  (int32_t) p->xmin, (int32_t)p->xmax);
1557  IfTrace1(TRUE, "subpath=%p,\n", p->subpath);
1558  }
1559  }
1560  for (y=MAX(ymin,RegionDebugYMin); y < MIN(ymax, RegionDebugYMax); y++) {
1561  IfTrace1(TRUE,". . . Y[%5d] ", (int32_t) y);
1562  for (p=p2; INSWATH(p,ymin,ymax); p = p->link)
1563  IfTrace1(TRUE,"%5d ",
1564  (int32_t) p->xvalues[y - ymin]);
1565  IfTrace0(TRUE,"\n");
1566  }
1567  while (INSWATH(p2, ymin, ymax))
1568  p2 = p2->link;
1569  }
1570  }
1571 }
1572 
1573 /*
1574 :h3.edgecheck() - For Debug, Verify that an Edge Obeys the Rules
1575 */
1576 
1577 /*ARGSUSED*/
1578 static void edgecheck(struct edgelist *edge, int oldmin, int oldmax)
1579 {
1580  if (edge->type != EDGETYPE)
1581  t1_abort("EDGE ERROR: non EDGETYPE in list");
1582 /*
1583 The following check is not valid if the region is jumbled so I took it
1584 out:
1585 */
1586 /* if (edge->ymin < oldmax && edge->ymin != oldmin)
1587  t1_abort("EDGE ERROR: overlapping swaths"); */
1588 }
1589 #endif
bp
Definition: action.c:1035
#define type(a)
Definition: aptex-macros.h:171
#define count(a)
Definition: aptex-macros.h:781
#define next(a)
Definition: aptex-macros.h:924
#define before
Definition: aptex-macros.h:256
char * p2
Definition: bmpfont.h:62
#define StepBezier(R, xA, yA, xB, yB, xC, yC, xD, yD)
Definition: curves.h:32
@ TRUE
Definition: dd.h:102
#define Free(x)
Definition: dd.h:135
int h
Definition: dviconv.c:9
int base
Definition: gsftopk.c:1502
struct fractpoint hint
Definition: hints.c:78
#define ApplyContinuity(R)
Definition: hints.h:41
#define ProcessHint(hP, currX, currY, hintP)
Definition: hints.h:37
#define InitHints
Definition: hints.h:31
#define CloseHints(hintP)
Definition: hints.h:34
#define MIN(a, b)
Definition: jpegint.h:269
#define MAX(a, b)
Definition: jpegint.h:267
#define NULL
Definition: ftobjs.h:61
small capitals from c petite p
Definition: afcover.h:72
kerning y
Definition: ttdriver.c:212
@ right
Definition: annotate.c:15
int int double double double char double char * top
Definition: gdfx.h:19
int int double double double char double char char * bottom
Definition: gdfx.h:20
signed int int32_t
Definition: stdint.h:77
#define Join(p1, p2)
Definition: paths.h:36
#define PathSegment(t, x, y)
Definition: paths.h:99
#define BoxPath(S, h, w)
Definition: paths.h:102
#define UniquePath(p)
Definition: paths.h:123
#define ISCLOSED(flag)
Definition: paths.h:137
#define ISPATHANCHOR(p)
Definition: paths.h:149
#define StepLine(R, x1, y1, x2, y2)
Definition: lines.h:31
cell * list
Definition: list_routines.h:30
float x
Definition: cordic.py:15
void t1_abort(const char *str)
Definition: objects.c:1088
#define NonObjectFree(a)
Definition: objects.h:61
#define CONICTYPE
Definition: objects.h:150
#define EDGETYPE
Definition: objects.h:144
char MustTraceCalls
#define IfTrace0(condition, model)
Definition: objects.h:233
#define IfTrace2(condition, model, arg0, arg1)
Definition: objects.h:237
#define TEXTTYPE
Definition: objects.h:155
#define IfTrace4(condition, model, arg0, arg1, arg2, arg3)
Definition: objects.h:241
#define LINETYPE
Definition: objects.h:149
#define STROKEPATHTYPE
Definition: objects.h:145
#define Allocate(n, t, s)
Definition: objects.h:59
#define BEZIERTYPE
Definition: objects.h:151
char HintDebug
#define ARGCHECK(test, msg, obj, whenBAD, consumables, rettype)
Definition: objects.h:196
char ProcessHints
char Continuity
#define Dup(obj)
Definition: objects.h:44
char RegionDebug
#define ArgErr(s, o, r)
Definition: objects.h:63
#define ISPERMANENT(flag)
Definition: objects.h:160
#define ISIMMORTAL(flag)
Definition: objects.h:161
#define FOLLOWING(p)
Definition: objects.h:181
#define IfTrace3(condition, model, arg0, arg1, arg2)
Definition: objects.h:239
#define REGIONTYPE
Definition: objects.h:140
#define IfTrace1(condition, model, arg0)
Definition: objects.h:235
#define INT32COPY(dest, source, bytes)
Definition: objects.h:172
#define HINTTYPE
Definition: objects.h:152
#define MOVETYPE
Definition: objects.h:154
#define KillPicture(p)
Definition: pictures.h:34
set set set set set set set macro pixldst1 abits if abits op else op endif endm macro pixldst2 abits if abits op else op endif endm macro pixldst4 abits if abits op else op endif endm macro pixldst0 abits op endm macro pixldst3 mem_operand op endm macro pixldst30 mem_operand op endm macro pixldst abits if abits elseif abits elseif abits elseif abits elseif abits pixldst0 abits else pixldst0 abits pixldst0 abits pixldst0 abits pixldst0 abits endif elseif abits else pixldst0 abits pixldst0 abits endif elseif abits else error unsupported bpp *numpix else pixst endif endm macro pixld1_s mem_operand if asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl elseif asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl else error unsupported endif endm macro pixld2_s mem_operand if mov asr add asl add asl mov asr sub UNIT_X add asl mov asr add asl add asl mov asr add UNIT_X add asl else pixld1_s mem_operand pixld1_s mem_operand endif endm macro pixld0_s mem_operand if asr adds SRC_WIDTH_FIXED bpl add asl elseif asr adds SRC_WIDTH_FIXED bpl add asl endif endm macro pixld_s_internal mem_operand if mem_operand pixld2_s mem_operand pixdeinterleave basereg elseif mem_operand elseif mem_operand elseif mem_operand elseif mem_operand pixld0_s mem_operand else pixld0_s mem_operand pixld0_s mem_operand pixld0_s mem_operand pixld0_s mem_operand endif elseif mem_operand else pixld0_s mem_operand pixld0_s mem_operand endif elseif mem_operand else error unsupported mem_operand if bpp mem_operand endif endm macro vuzp8 reg2 vuzp d d &reg2 endm macro vzip8 reg2 vzip d d &reg2 endm macro pixdeinterleave basereg basereg basereg basereg basereg endif endm macro pixinterleave basereg basereg basereg basereg basereg endif endm macro PF boost_increment endif if endif PF tst PF addne PF subne PF cmp ORIG_W if endif if endif if endif PF subge ORIG_W PF subges if endif if endif if endif endif endm macro cache_preload_simple endif if dst_r_bpp pld[DST_R, #(PREFETCH_DISTANCE_SIMPLE *dst_r_bpp/8)] endif if mask_bpp pld if[MASK, #(PREFETCH_DISTANCE_SIMPLE *mask_bpp/8)] endif endif endm macro fetch_mask_pixblock pixld mask_basereg pixblock_size MASK endm macro ensure_destination_ptr_alignment process_pixblock_tail_head if beq irp skip1(dst_w_bpp<=(lowbit *8)) &&((lowbit *8)<(pixblock_size *dst_w_bpp)) .if lowbit< 16 tst DST_R
static int32_t last
Definition: ppagelist.c:29
int r
Definition: ppmqvga.c:68
static int edgecheck(struct edgelist *edge, int oldmin, int oldmax)
struct edgelist * swathrightmost(struct edgelist *before, struct edgelist *edge)
static void cedgemin(int, pel *, pel)
static void cedgemax(int, pel *, pel)
#define x1
#define y1
#define y2
#define x2
static int Xp
Definition: rate.c:94
static struct region t1_infinity
Definition: regions.c:139
static void Unwind(struct edgelist *)
static struct edgelist * NewEdge(pel, pel, pel, pel, pel *, int)
Definition: regions.c:284
static struct edgelist * SwathUnion(register struct edgelist *before0, register struct edgelist *edge)
Definition: regions.c:1071
static pel * currentworkarea
Definition: regions.c:645
static struct edgelist * SortSwath(struct edgelist *, struct edgelist *, struct edgelist *(*)())
#define MAXEDGE
Definition: regions.c:641
static void edgemin(register int, register pel *, register pel *)
Definition: regions.c:1299
static pel currentsize
Definition: regions.c:646
static int touches(int, pel *, pel *)
static void vertjoin(register struct edgelist *, register struct edgelist *)
Definition: regions.c:973
static void edgemax(register int, register pel *, register pel *)
Definition: regions.c:1309
#define BOTTOM(e)
Definition: regions.c:791
static struct edgelist * swathxsort(struct edgelist *, struct edgelist *)
static int crosses(int, pel *, pel *)
static void discard(register struct edgelist *, register struct edgelist *)
Definition: regions.c:1331
static pel workedge[1000]
Definition: regions.c:644
static void newfilledge(register struct region *, fractpel, fractpel, fractpel, fractpel, int)
Definition: regions.c:740
static struct edgelist * splitedge(struct edgelist *, pel)
#define TOP(e)
Definition: regions.c:790
#define CD_LAST
Definition: regions.h:130
#define CD_CONTINUE
Definition: regions.h:129
#define ChangeDirection(type, R, x, y, dy)
Definition: regions.h:124
#define VALIDEDGE(p)
Definition: regions.h:101
#define MAXPEL
Definition: regions.h:175
#define ISINFINITE(flag)
Definition: regions.h:71
#define MoreWorkArea(R, x1, y1, x2, y2)
Definition: regions.h:132
#define ISDOWN(f)
Definition: regions.h:190
#define CONTINUITY
Definition: regions.h:203
#define EmptyRegion
Definition: regions.h:81
#define UnJumble(R)
Definition: regions.h:138
#define CopyRegion(area)
Definition: regions.h:134
#define MINPEL
Definition: regions.h:174
#define ISAMBIGUOUS(f)
Definition: regions.h:192
#define ISCOMPLEMENT(flag)
Definition: regions.h:62
#define EVENODDRULE
Definition: regions.h:201
#define KillRegion(area)
Definition: regions.h:133
#define WINDINGRULE
Definition: regions.h:200
#define CD_FIRST
Definition: regions.h:128
#define MoveEdges(R, dx, dy)
Definition: regions.h:137
#define Interior(p, rule)
Definition: regions.h:106
#define RegionBounds(r)
Definition: regions.h:135
#define T1_INFINITY
Definition: regions.h:119
lft_cell * left
Definition: routines.h:73
ShellFileEnvironment e
Definition: sh6.c:388
SHORT pel
Definition: spaces.h:36
#define TOFRACTPEL(p)
Definition: spaces.h:44
#define IDENTITY
Definition: spaces.h:34
#define NEARESTPEL(fp)
Definition: spaces.h:46
int32_t fractpel
Definition: spaces.h:37
#define FPHALF
Definition: spaces.h:45
#define int32_t
Definition: stdint.in.h:167
#define DoStroke(sp)
Definition: strokes.h:37
#define CoercePath(sp)
Definition: strokes.h:36
cairo_list_t link
pel ymin
Definition: regions.h:92
pel ymax
Definition: regions.h:92
pel xmin
Definition: regions.h:91
XOBJ_COMMON struct edgelist * link
Definition: regions.h:89
pel * xvalues
Definition: regions.h:93
Edge ** edges
Definition: edgelist.h:61
pel xmax
Definition: regions.h:91
fractpel y
Definition: spaces.h:81
fractpel x
Definition: spaces.h:81
struct segment * link
Definition: paths.h:196
Definition: tpic.c:45
Definition: regions.h:31
XOBJ_COMMON struct fractpoint origin
Definition: regions.h:34
pel ymin
Definition: regions.h:36
pel xmax
Definition: regions.h:37
struct fractpoint ending
Definition: regions.h:35
struct edgelist * anchor
Definition: regions.h:38
pel xmin
Definition: regions.h:36
pel ymax
Definition: regions.h:37
struct picture * thresholded
Definition: regions.h:39
int area
Definition: sh1.c:132
Definition: paths.h:128
pointer path
Definition: t1imager.h:36
@ after
Definition: texnodes.h:374
@ R
Definition: ubidiimp.h:46
@ ON
Definition: ubidiimp.h:55
#define end(cp)
Definition: zic.c:71