/* $XConsortium: curves.c,v 1.3 91/10/10 11:17:56 rws Exp $ */
/* Copyright International Business Machines,Corp. 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 licensee provides a license to      */
/* IBM, Corp. to use, copy, modify, and distribute derivative        */
/* works and their documentation for any purpose and without         */
/* fee, 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 not be used in advertising or publicity pertaining to      */
/* distribution of the software without specific, written prior      */
/* permission.                                                       */

/* IBM PROVIDES 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) ASSUMES      */
/* THE ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION.  IN      */
/* NO EVENT SHALL IBM 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.                                                         */
/*

/*
 * CURVES Module - Stepping Beziers
 *
 * This module is responsible for "rasterizing"
 * Bezier third order curves.  That is, it changes the high level curve
 * specification into a list of pels that that curve travels through.
 */


/**
 * Includes
 **/
#ifndef T1GST		// TetiSoft
#include "global.h"	// TetiSoft
#endif		// TetiSoft
//include "types.h"	// TetiSoft
//include "objects.h"
//include "spaces.h"
//include "paths.h"
//include "regions.h"
//include "curves.h"
//include "lines.h"
//include "arith.h"
//include "protos.h"	// TetiSoft 
//include "aliases.h"	// TetiSoft 


/**
 * Local prototypes
 **/
static int BezierTerminationTest(fractpel xa, fractpel ya, fractpel xb, fractpel yb, fractpel xc, fractpel yc, fractpel xd, fractpel yd);
static struct segment *StepBezierRecurse(struct T1GlyphEngine *engine, struct bezierinfo *I, fractpel xA, fractpel yA, fractpel xB, fractpel yB, fractpel xC, fractpel yC, fractpel xD, fractpel yD);


/**
 * The "bezierinfo" Structure
 *
 * This structure is used to store information used when we subdivide
 * Bezier curves.
 **/
struct bezierinfo
{
	struct region *region;	/* the region being built or NULL             */
	struct fractpoint last;	/* not used yet; maybe could save some work  */
	struct fractpoint origin;	/* the origin of the bezier                */
};


/*
 * Checking for termination of the subdivision process:
 * This is the stupidest test in the world, just check if the coordinatewise
 * distance from an end control point to the next control point is less than
 * one half pel.   If so, we must be done.
 * This returns 1 if the subdivision is terminated and 0 if you still need
 * to subdivide.
 */
//
//NOTE: 4/26/93 AMISH
//I'm marking this function static, since it is.
//
//static int BezierTerminationTest(fractpel xa, fractpel ya, fractpel xb, fractpel yb,
//							fractpel xc, fractpel yc, fractpel xd, fractpel yd)
//{
//	fractpel dmax;
//
//	dmax = ABS(xa - xb);
//	dmax = MAX(dmax, ABS(ya - yb));
//	dmax = MAX(dmax, ABS(xd - xc));
//	dmax = MAX(dmax, ABS(yd - yc));
//	if (dmax > FPHALF)
//		return (0);	/* not done yet */
//	else
//		return (1);	/* done */
//}

/**
 * REWRITTEN BY AMISH:
 * The original routine is rather silly.  It does many more comparisons
 * than we care about.  Profiling revealed that this routine is called
 * very frequently, and it was very inefficient
 * 20-April-93
 **/
static int BezierTerminationTest(fractpel xa, fractpel ya, fractpel xb, fractpel yb,
							fractpel xc, fractpel yc, fractpel xd, fractpel yd)
{
	if (ABS(xa-xb) > FPHALF)
		return 0;

	if (ABS(ya-yb) > FPHALF)
		return 0;

	if (ABS(xd-xc) > FPHALF)
		return 0;

	if (ABS(yd-yc) > FPHALF)
		return 0;

	return 1;	/* Done */
}


/*
 * StepBezierRecurse() - The Recursive Logic in StepBezier()
 *
 * The recursion involves dividing the control polygon into two smaller
 * control polygons by finding the midpoints of the lines.  This idea is
 * described in any graphics text book and its simplicity is what caused
 * Bezier to define his curves as he did.  If the input region 'R' is NULL,
 * the result is a path that is the 'flattened' curve; otherwise StepBezier
 * returns nothing special.
 */
/*
 * Note that "stepping" and "flattening" are so similiar that they use the
 * same routine.  When the "region" parameter is NULL, that is a flag that
 * we are flattening instead of stepping.
 */
static struct segment *StepBezierRecurse(
		struct T1GlyphEngine *engine,
		struct bezierinfo *I,		/* Region under construction, or NULL */
		fractpel xA, fractpel yA,	/* A control point */
		fractpel xB, fractpel yB,	/* B control point */
		fractpel xC, fractpel yC,	/* C control point */
		fractpel xD, fractpel yD)	/* D control point */
{
	if (BezierTerminationTest(xA, yA, xB, yB, xC, yC, xD, yD))
	{
		if (I->region == NULL)
			return (t1_PathSegment(engine, LINETYPE, xD - xA, yD - yA));
		else
			t1_StepLine(engine, I->region, I->origin.x + xA, I->origin.y + yA,
				 I->origin.x + xD, I->origin.y + yD);
	}
	else
	{
		fractpel xAB, yAB;
		fractpel xBC, yBC;
		fractpel xCD, yCD;
		fractpel xABC, yABC;
		fractpel xBCD, yBCD;
		fractpel xABCD, yABCD;

		xAB = xA + xB;
		yAB = yA + yB;
		xBC = xB + xC;
		yBC = yB + yC;
		xCD = xC + xD;
		yCD = yC + yD;

		xABC = xAB + xBC;
		yABC = yAB + yBC;
		xBCD = xBC + xCD;
		yBCD = yBC + yCD;

		xABCD = xABC + xBCD;
		yABCD = yABC + yBCD;

		xAB >>= 1;
		yAB >>= 1;
//		xBC >>= 1;	// TetiSoft
//		yBC >>= 1;	// TetiSoft
		xCD >>= 1;
		yCD >>= 1;
		xABC >>= 2;
		yABC >>= 2;
		xBCD >>= 2;
		yBCD >>= 2;
		xABCD >>= 3;
		yABCD >>= 3;

		if (I->region == NULL)
		{
			return (t1_Join(    engine,
					    StepBezierRecurse(engine, I, xA, yA, xAB, yAB, xABC, yABC, xABCD, yABCD),
					    StepBezierRecurse(engine, I, xABCD, yABCD, xBCD, yBCD, xCD, yCD, xD, yD)
				)
			    );
		}
		else
		{
			StepBezierRecurse(engine, I, xA, yA, xAB, yAB, xABC, yABC, xABCD, yABCD);
			StepBezierRecurse(engine, I, xABCD, yABCD, xBCD, yBCD, xCD, yCD, xD, yD);
		}
	}
	/*NOTREACHED*/
}


/*
 * TOOBIG() - Macro to Test if a Coordinate is Too Big to Bezier SubDivide Normally
 *
 * Intermediate values in the Bezier subdivision are 8 times bigger than
 * the starting values.  If this overflows, a 'long', we are in trouble:
 */
#define  BITS         (sizeof(long)*8)
#define  HIGHTEST(p)  (((p)>>(BITS-4)) != 0)	/* includes sign bit */
#define  TOOBIG(xy)   ((xy < 0) ? HIGHTEST(-xy) : HIGHTEST(xy))


/*
 * StepBezier() - Produce Run Ends for a Bezier Curve
 *
 * This is the entry point called from outside the module.
 */
struct segment *StepBezier(
		struct T1GlyphEngine *engine,
		struct region *R,		/* Region under construction or NULL */
		fractpel xA, fractpel yA,	/* A control point */
		fractpel xB, fractpel yB,	/* B control point */
		fractpel xC, fractpel yC,	/* C control point */
		fractpel xD, fractpel yD)	/* D control point */
{
	struct bezierinfo Info;

	Info.region = R;
	Info.origin.x = xA;
	Info.origin.y = yA;

	xB -= xA;
	xC -= xA;
	xD -= xA;
	yB -= yA;
	yC -= yA;
	yD -= yA;

	if (TOOBIG(xB) || TOOBIG(yB) || TOOBIG(xC) || TOOBIG(yC)
	    || TOOBIG(xD) || TOOBIG(yD))
	{
		FatalError("Beziers this big not yet supported");
		return NULL;
	}

	return (StepBezierRecurse(engine, &Info,
		       (fractpel) 0, (fractpel) 0, xB, yB, xC, yC, xD, yD));
}