/***********************************************************
Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts,
and the Massachusetts Institute of Technology, Cambridge, Massachusetts.

                        All Rights Reserved

Permission 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 names of Digital or MIT not be
used in advertising or publicity pertaining to distribution of the
software without specific, written prior permission.  

DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
DIGITAL 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.

******************************************************************/
/* $Header: mipolyclip.c,v 1.9 87/06/15 00:57:41 sue Exp $ */
/*
 *     clippoly.c   (Sutherland and Hodgeman clipper)
 *
 *     Written by Brian Kelleher; Jan. 1986.
 *
 *     This is an implementation of Sutherland and Hodgeman's
 *     polygon clipping algorithm.
 *     The result of this routine is to fill in the array
 *     clippedpts with a new polygon which is the intersection
 *     of the original polygon with the clip rect.  The number of
 *     vertices in the new polygon is returned.
 *     The routine will also clip properties associated with
 *     vertices (examples: r, g, b, i, z).  These properties must be
 *     unsigned shorts and are linearly interpolated along an edge.
 *
 *     I think this algorithm works fine for general (concave)
 *     polygons as well as convex.  It leaves extraneous edges along
 *     the clip boundary; however, these shouldn't be a problem
 *     since they are sent directly to the scan-converter, which
 *     will do the right thing.
 *     One possible problem, however, is that when a vertex is
 *     outside the clip boundary, this algorithm just
 *     throws it away.  This may cause problems when scan-converting,
 *     since we have potentially lost information along a scanline
 *     where edges existed outside of the clip boundary.  If this turns
 *     out to be a problem, then all points outside the clip boundary
 *     can simply be truncated to the boundary (e.g. the point (10, 500)
 *     is truncated to (500, 500) at the clip boundary x=500).  I can't think
 *     of any case where this causes trouble (I think all is OK), but
 *     just wanted to record my concerns here.
 *
 */
#include "X.h"
#include "Xmd.h"
#include "misc.h"
#include "miscstruct.h"
#include "mistruct.h"
#include "gc.h"
#include "os.h"
#include "opaque.h"


/*
 *     Used to describe a clipping boundary.
 *     The edge field tells which side of the clip rect we are
 *     dealing with (ie. TOP), and the value field tells the value
 *     of that edge (ie. y = 100).
 */
typedef struct _boundary {
    int edge;
    int value;
} boundary;

#define TOP    0
#define BOTTOM 1
#define LEFT   2
#define RIGHT  3



/*
 *  Call the clipper once for each boundary of the
 *  clipping rectangle.
 *  Return the points in the resulting polygon.
 *  The ptsOut buffer is a temporary buffer allocated by the
 *  client of this routine which we can use to put the new
 *  points into.
 */
int miClipPoly(nIn,ptsIn,nOut,ptsOut,clipRect)
    int nIn;			/* number of points               */
    DDXPointPtr ptsIn;		/* first point in vertex list     */
    int *nOut;			/* number of points out		  */
    DDXPointPtr ptsOut;		/* temporary buffer of points	  */
    RectangleRec clipRect;	/* clipping rectangle             */
{
    DDXPointPtr localPts;
    boundary bound;
    RectangleRec bbox;         	/* polygon's bounding box         */

    if(!(localPts=(DDXPointPtr)ALLOCATE_LOCAL(sizeof(DDXPointRec)*(2*nIn+4))))
	return(1);

    getPgonBbox(nIn, ptsIn, &bbox);

    /*
     *  Check trivial accept
     */
    if ((bbox.x >= clipRect.x) &&
	(bbox.y >= clipRect.y) &&
	(bbox.x + bbox.width <= clipRect.x + clipRect.width) &&
	(bbox.y + bbox.height <= clipRect.y + clipRect.height)) 
    {

	*nOut = nIn;
	DEALLOCATE_LOCAL(localPts);
	return(0);
    }

    /*
     *  Check trivial reject
     */
    if ((bbox.x > clipRect.x + clipRect.width) ||
	(bbox.y > clipRect.y + clipRect.height) ||
	(bbox.x + bbox.width < clipRect.x) ||
	(bbox.y + bbox.height < clipRect.y)) 
    {

	*nOut = 0;
	DEALLOCATE_LOCAL(localPts);
	return(1);
    }

    /*
     *  clip to the top, then bottom, left, right
     */
    bound.edge = TOP;  bound.value = clipRect.y;
    nIn = SHclip(ptsIn,localPts,nIn,bound);

    bound.edge = BOTTOM;  bound.value = clipRect.y + clipRect.height;
    nIn = SHclip(localPts,ptsOut,nIn,bound);

    bound.edge = LEFT;  bound.value = clipRect.x;
    nIn = SHclip(ptsOut,localPts,nIn,bound);

    bound.edge = RIGHT;  bound.value = clipRect.x + clipRect.width;
    nIn = SHclip(localPts,ptsOut,nIn,bound);

    *nOut = nIn;
    DEALLOCATE_LOCAL(localPts);
    return(1);
}


/*
 *  return the bounding box of the polygon
 */
static getPgonBbox(n, pts, bbox)
    register int n;
    register DDXPointPtr pts;
    RectanglePtr bbox;
{
    register int l, r, t, b;

    l = r = pts->x;
    b = t = pts++->y;

    while (--n) 
    {
	if (pts->x < l)
	    l = pts->x;
	if (pts->x > r)
	    r = pts->x;
	if (pts->y < b)
	    b = pts->y;
	if (pts->y > t)
	    t = pts->y;

	pts++;
    }

    bbox->x = l;
    bbox->y = b;
    bbox->width = r - l;
    bbox->height = t - b;
}


/*
 *  This is where the real work is done.
 *  Sutherland and Hodgeman are a couple of crazy guys.
 */
static int
SHclip(ptsIn,ptsOut,nIn,bound)
    register DDXPointPtr ptsIn;  /* first point in vertex list     */
    register DDXPointPtr ptsOut; /* resulting polygon              */
    register int nIn;            /* number of points               */
    boundary bound;              /* which edge of cliprect         */
{
    DDXPointRec s, p;             /* start and end points of an edge  */
    register int nOut = 0;       /* number of pts output by clipper  */
    register int pIn, sIn;       /* boolean flags                    */
    DDXPointRec ClipIntersect();

    /*
     *  start at the top of the polygon and work around the poly
     */
    s = ptsIn[nIn-1];
    while (nIn--) 
    {
        p = *ptsIn++;

        /*
         *  determine the insideness of the points
         */
        switch (bound.edge) 
        {
          case TOP:
            pIn = (p.y >= bound.value) ? TRUE : FALSE;
            sIn = (s.y >= bound.value) ? TRUE : FALSE;
            break;
          case BOTTOM:
            pIn = (p.y <= bound.value) ? TRUE : FALSE;
            sIn = (s.y <= bound.value) ? TRUE : FALSE;
            break;
          case LEFT:
            pIn = (p.x >= bound.value) ? TRUE : FALSE;
            sIn = (s.x >= bound.value) ? TRUE : FALSE;
            break;
          case RIGHT:
            pIn = (p.x <= bound.value) ? TRUE : FALSE;
            sIn = (s.x <= bound.value) ? TRUE : FALSE;
            break;
        }

        /*
         *  if p is inside
         */
        if (pIn) 
        {
            /*
             *  if s is inside
             */
            if (sIn) 
            {
                *(ptsOut++) = p;
                nOut++;
            }
            else 
            {
                *(ptsOut++) = ClipIntersect(s,p,bound);
                *(ptsOut++) = p;
                nOut += 2;
            }
        }
        else 
        {
            /*
             *  if s is inside
             */
            if (sIn) 
            {
                *(ptsOut++) = ClipIntersect(s,p,bound);
                nOut++;
            }
        }

        s = p;
    }

    return(nOut);
}



/*
 *  Calculate intersections with simple boundaries.
 *  The algorithm is simple -- we just use similar
 *  triangles.
 *  We also have to clip the pixel data to the boundary.
 *  This is done very similar to the coordinate data, except
 *  that we have to worry about different pixel types.
 *
 *  In calculating intersections, we must make certain that
 *  the direction of the first point to the second point is
 *  always consistent.  This will ensure that polygons sharing
 *  an edge will remain coincident.  We will not worry about this
 *  for pixel data because the problem is not noticable.
 */
static DDXPointRec
ClipIntersect(s,p,bound)
    DDXPointRec s, p;		/* describe a line                */
    boundary bound;
{
    DDXPointRec i;
    register int dpts, dbound;

    /*
     *  Note that we don't have to worry about divide by 0
     *  because this routine will never get called in such
     *  a case.
     *  Also, make sure we are always going in a consistent direction
     *  so we don't get hurt by numerical errors.
     */
    if ((bound.edge == TOP) || (bound.edge == BOTTOM)) 
    {
        dbound = bound.value - p.y;
        dpts = s.y - p.y;
	if (dpts > 0) 
        {
	    i.x = p.x + ((s.x - p.x) * dbound) / dpts;
	    i.y = bound.value;
	}
	else 
        {
	    i.x = s.x + ((p.x - s.x) * (bound.value-s.y)) / -dpts;
	    i.y = bound.value;
	}
    }
    else 
    {
        dbound = bound.value - p.x;
        dpts = s.x - p.x;
	if (dpts > 0) 
        {
	    i.y = p.y + ((s.y - p.y) * dbound) / dpts;
	    i.x = bound.value;
	}
	else 
        {
	    i.y = s.y + ((p.y - s.y) * (bound.value-s.x)) / -dpts;
	    i.x = bound.value;
	}
    }

    return(i);
}