regions.c

source code: Covert TXT to PDF

/* $XConsortium: regions.c,v 1.4 91/10/10 11:18:57 rws Exp $ */
/* Copyright International Business Machines, Corp. 1991
 * All Rights Reserved
 * Copyright Lexmark International, Inc. 1991
 * All Rights Reserved
 *
 * License to use, copy, modify, and distribute this software and its
 * documentation for any purpose and without fee is hereby granted,
 * provided that the above copyright notice appear in all copies and that
 * both that copyright notice and this permission notice appear in
 * supporting documentation, and that the name of IBM or Lexmark not be
 * used in advertising or publicity pertaining to distribution of the
 * software without specific, written prior permission.
 *
 * IBM AND LEXMARK PROVIDE THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES OF
 * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO ANY
 * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
 * AND NONINFRINGEMENT OF THIRD PARTY RIGHTS.  THE ENTIRE RISK AS TO THE
 * QUALITY AND PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT
 * OR MAINTAIN, BELONGS TO THE LICENSEE.  SHOULD ANY PORTION OF THE
 * SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM OR LEXMARK) ASSUMES THE
 * ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION.  IN NO EVENT SHALL
 * IBM OR LEXMARK BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
 * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
 * THIS SOFTWARE.
 */
 /* REGIONS  CWEB         V0023 LOTS                                 */
/*
:h1 id=regions.REGIONS Module - Regions Operator Handler
 
This module is responsible for creating and manipulating regions.
 
&author. Jeffrey B. Lotspiech ([e-mail])
 
 
:h3.Include Files
 
The included files are:
*/

#include <stdio.h>
#include <stdlib.h>

#include  "types.h"
#include  "objects.h"
#include  "spaces.h"
#include  "regions.h"
#include  "paths.h"
#include  "curves.h"
#include  "lines.h"
#include  "pictures.h"
#include  "fonts.h"
#include  "hints.h"
#include  "strokes.h"      /* to pick up 'DoStroke'                        */
static int Unwind();
static int newfilledge();
static struct edgelist *splitedge();
static int vertjoin();
static int touches();
static int crosses();
static int edgemin();
static int edgemax();
static int discard();
static int edgecheck();
static struct edgelist *NewEdge();
struct edgelist *swathxsort();  /* 'SortSwath' function               */
extern struct XYspace *IDENTITY;
 
/*
:h3.Functions Provided to the TYPE1IMAGER User
 
This module provides the following TYPE1IMAGER entry points:
*/
 
/*SHARED LINE(S) ORIGINATED HERE*/
/*
:h3.Functions Provided to Other Modules
 
This module provides the following entry points to other modules:
*/
 
/*SHARED LINE(S) ORIGINATED HERE*/
/*
:h3.Macros Provided to Other Modules
 
:h4.GOING_TO() - Macro Predicate Needed for Changing Direction, Etc.
 
The actual generation of run end lists (edge boundaries) is left
to the low level rasterizing modules, LINES and CURVES.  There
are some global region-type
questions that occur when doing a low-level
rasterization:
:ol.
:li.Did we just change direction in Y and therefore need to start
a new edge?
:li.Did we run out of allocated edge space?
:li.Do the minimum or maximum X values for the current edge need
updating?
:eol.
In general the REGIONS is not smart enough to answer those questions
itself.  (For example, determining if and when a curve changes direction
may need detailed curve knowledge.)  Yet, this must be done efficiently.
We provide a macro "GOING_TO" where the invoker tells us where it is
heading for (x2,y2), plus where it is now (x1,y1), plus the current
region under construction, and the macro answers the questions above.
*/
 
/*SHARED LINE(S) ORIGINATED HERE*/
/*
:h2.Data Structures Used to Represent Regions
 
:h3.The "region" Structure
 
The region structure is an anchor for a linked list of "edgelist"
structures (see :hdref refid=edgelist..).  It also summarizes the
information in the edgelist structures (for example, the bounding
box of the region).  And, it contains scratch areas used during
the creation of a region.
*/
 
/*SHARED LINE(S) ORIGINATED HERE*/
/*
The ISOPTIMIZED flag tells us if we've put a permanent region in
'optimal' form.
*/
#define   ISOPTIMIZED(flag)    ((flag)&0x10)
 
/*
The ISRECTANGULAR flag tells us if a region is a rectangle.  We don't
always notice rectangles--if this flag is set, the region definitely
is a rectangle, but some rectangular regions will not have the flag
set.  The flag is used to optimize some paths.
*/
 
/*SHARED LINE(S) ORIGINATED HERE*/
/*
:h4."INFINITY" - A Constant Region Structure of Infinite Extent
 
Infinity is the complement of a null area:
Note - removed the refcount = 1 init, replaced with references = 2 3-26-91 PNM
*/
static struct region infinity = { REGIONTYPE,
                           ISCOMPLEMENT(ON)+ISINFINITE(ON)+ISPERMANENT(ON)+ISIMMORTAL(ON), 2,
                           {0, 0}, {0, 0},
                           0, 0, 0, 0,
                           NULL, NULL,
                           0, 0, 0, 0, 0, NULL, NULL,
                           NULL, 0, NULL, NULL };
/* we rename INFINITY to T1_INFINITY. Anyhow it is currently not used */
struct region *T1_INFINITY = &infinity;
 
/*
:h4."EmptyRegion" - A Region Structure with Zero Area
 
This structure is used to initialize the region to be built in
Interior():
Note - replaced refcount = 1 init with references = 2 3-26-91 PNM
*/
 
/*SHARED LINE(S) ORIGINATED HERE*/
struct region EmptyRegion = { REGIONTYPE,
                           ISPERMANENT(ON)+ISIMMORTAL(ON), 2,
                           {0, 0}, {0, 0},
                           MAXPEL, MAXPEL, MINPEL, MINPEL,
                           NULL, NULL,
                           0, 0, 0, 0, 0, NULL, NULL,
                           NULL, 0, NULL, NULL };
 
/*
:h3 id=edgelist.The "edgelist" Structure
 
Regions are represented by a linked list of 'edgelist' structures.
When a region is complete, the structures are paired, one for the
left and one for the right edge.  While a region is being built,
this rule may be violated temporarily.
 
An 'edgelist' structure contains the X values for a given span
of Y values.  The (X,Y) pairs define an edge.  We use the crack
and edge coordinate system, so that integer values of X and Y
go between pels.  The edge is defined between the minimum Y and
maximum Y.
 
The linked list is kept sorted from top to bottom, that is, in
increasing y.  Also, if 'e1' is an edgelist structure and 'e2' is the
next one in the list, they must have exactly the same ymin,ymax values
or be totally disjoint.  These two requirements mean that if e2's ymin
is less than e1's ymax, it must be exactly equal to e1's ymin.  A
sublist of structures with identical ymin and ymax values is called a
'swath'.
 
In addition, edgelist structures are separately linked together based
on what subpath originally created them; each subpath is kept as a
separate circular linked list.  This information is ignored unless
continuity checking is invoked.  See :hdref refid=subpath. for a
complete description of this.
*/
 
 
/*SHARED LINE(S) ORIGINATED HERE*/
 
/*
The "edgelist" structure follows the convention of TYPE1IMAGER user
objects, having a type field and a flag field as the first two
elements.  However, the user never sees "edgelist" structures
directly; he is given handles to "region" structures only.
 
By having a type field, we can use the "copy" feature of Allocate()
to duplicate edge lists quickly.
 
We also define two flag bits for this structure.  The ISDOWN bit is set
if the edge is going in the direction of increasing Y. The ISAMBIGUOUS
bit is set if the edge is identical to its neighbor (edge->link); such
edges may be "left" when they should be "right", or vice versa,
unnecessarily confusing the continuity checking logic.  The FixSubPaths()
routine in HINTS will swap ambiguous edges if that avoids crossing edges;
see :hdref refid=fixsubp..
*/
 
/*SHARED LINE(S) ORIGINATED HERE*/
 
/*
:h3.KillRegion() - Destroys a Region
 
KillRegion nominally just decrements the reference count to that region.
If the reference count becomes 0, all memory associated with it is
freed.  We just follow the linked list, freeing as we go, then kill any
associated (thresholded) picture.
Note - added conditional return based on references 3-26-91 PNM
*/
 
void KillRegion(area)
        register struct region *area;  /* area to free                       */
{
        register struct edgelist *p;  /* loop variable                       */
        register struct edgelist *next;  /* loop variable                    */
 
        if (area->references < 0)
               abort("KillRegion:  negative reference count", 28);
        if ( (--(area->references) > 1) ||
           ( (area->references == 1) && !ISPERMANENT(area->flag) ) )
            return;
 
        for (p=area->anchor; p != NULL; p=next) {
               next = p->link;
               Free(p);
        }
	/* KillPicture-macro removed from sources (RMz, 2001-04-01)
        if (area->thresholded != NULL)
                 KillPicture(area->thresholded);
	*/
        Free(area);
}
/*
:h3.CopyRegion() - Makes a Copy of a Region
*/
struct region *CopyRegion(area)
        register struct region *area;  /* region to duplicate                */
{
        register struct region *r;  /* output region built here              */
        register struct edgelist *last=NULL;  /* loop variable                    */
        register struct edgelist *p,*newp;  /* loop variables                */
 
        r = (struct region *)Allocate(sizeof(struct region), area, 0);
        r->anchor = NULL;
 
        for (p=area->anchor; VALIDEDGE(p); p=p->link) {
 
               newp = NewEdge(p->xmin, p->xmax, p->ymin, p->ymax, p->xvalues, ISDOWN(p->flag));
               if (r->anchor == NULL)
                       r->anchor = last = newp;
               else
                       last->link = newp;
 
               last = newp;
        }
        if (area->thresholded != NULL)
    /* replaced DupPicture with Dup() 3-26-91 PNM */
               r->thresholded = (struct picture *)Dup(area->thresholded);
        return(r);
}
/*
:h4.NewEdge() - Allocates and Returns a New "edgelist" Structure
 
We allocate space for the X values contiguously with the 'edgelist'
structure that locates them.  That way, we only have to free the
edgelist structure to free all memory associated with it.  Damn
clever, huh?
*/
 
static struct edgelist *NewEdge(xmin, xmax, ymin, ymax, xvalues, isdown)
       pel xmin,xmax;        /* X extent of edge                             */
       pel ymin,ymax;        /* Y extent of edge                             */
       pel *xvalues;         /* list of X values for entire edge             */
       int isdown;           /* flag:  TRUE means edge progresses downward   */
{
       static struct edgelist template = {
                 EDGETYPE, 0, 1, NULL, NULL,
                 0, 0, 0, 0, NULL };
 
       register struct edgelist *r;  /* returned structure                   */
       register int iy;      /* ymin adjusted for 'long' alignment purposes  */
 
       IfTrace2((RegionDebug),"....new edge: ymin=%d, ymax=%d ",
                                              (LONG)ymin, (LONG) ymax);
       if (ymin >= ymax)
               abort("newedge: height not positive", 29);
/*
We are going to copy the xvalues into a newly allocated area.  It
helps performance if the values are all "long" aligned.  We can test
if the xvalues are long aligned by ANDing the address with the
(sizeof(long) - 1)--if non zero, the xvalues are not aligned well.  We
set 'iy' to the ymin value that would give us good alignment:
*/
       iy = ymin - (((unsigned long) xvalues) & (sizeof(LONG) - 1)) / sizeof(pel);
 
       r = (struct edgelist *)Allocate(sizeof(struct edgelist), &template,
                             (ymax - iy) * sizeof(pel));
 
       if (isdown) r->flag = ISDOWN(ON);
       r->xmin = xmin;
       r->xmax = xmax;
       r->ymin = ymin;
       r->ymax = ymax;
 
       r->xvalues = (pel *) FOLLOWING(r);
       if (ymin != iy) {
               r->xvalues += ymin - iy;
               xvalues -= ymin - iy;
       }
 
/*
We must round up (ymax - iy) so we get the ceiling of the number of
longs.  The destination must be able to hold these extra bytes because
Allocate() makes everything it allocates be in multiples of longs.
*/
       LONGCOPY(&r[1], xvalues, (ymax - iy) * sizeof(pel) + sizeof(LONG) - 1);
 
       IfTrace1((RegionDebug),"result=%p\n", r);
       return(r);
}
 
/*
:h2.Building Regions
 
:h3.Interior() - Iterate Through a Path, Building a Region
 
This routine is the workhorse driver routine that iterates through a
path, calling the appropriate stepping routines to actually produce the
run end "edgelist" structures.
 
:ol.
:li."Interior" calls StepLine or StepConic or StepBezier as appropriate
to produce run ends.
:li.Occasionally these routines will notice a change in Y direction
and will call ChangeDirection (through the GOING_TO macro); this is