mirror of https://github.com/lianthony/NT4.0
You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
606 lines
23 KiB
606 lines
23 KiB
/*********************************************************************
|
|
|
|
scspline.c -- New Scan Converter Spline Module
|
|
|
|
(c) Copyright 1992 Microsoft Corp. All rights reserved.
|
|
|
|
6/10/93 deanb assert.h and stdio.h removed
|
|
3/19/93 deanb size_t replaced with int32
|
|
10/28/92 deanb memory requirements reworked
|
|
10/09/92 deanb reentrant
|
|
9/28/92 deanb quick out for nearly vert/horiz splines
|
|
9/25/92 deanb branch on scan kind
|
|
9/22/92 deanb subpix calculation using subdivision
|
|
9/14/92 deanb reflection correction with iX/YOffset
|
|
9/10/92 deanb first dropout code
|
|
9/02/92 deanb Precision reduction by shifting control points
|
|
7/24/92 deanb Initial Q set for perfect symmetry
|
|
7/23/92 deanb EvaluateSpline split out and moved to NewScan
|
|
7/20/92 deanb removed unreachable case
|
|
7/16/92 deanb faster power of 2
|
|
7/06/92 deanb Cleanups
|
|
7/01/92 deanb Reinstate a single spline routine
|
|
6/30/92 deanb Implicit spline rendering
|
|
3/23/92 deanb First cut
|
|
|
|
**********************************************************************/
|
|
|
|
/*********************************************************************/
|
|
|
|
/* Imports */
|
|
|
|
/*********************************************************************/
|
|
|
|
#include "fscdefs.h" /* shared data types */
|
|
#include "fserror.h" /* error codes */
|
|
#include "fontmath.h" /* for power of 2 calc */
|
|
|
|
#include "scglobal.h" /* structures & constants */
|
|
#include "scanlist.h" /* for direct horizscan add call */
|
|
#include "scspline.h" /* for own function prototypes */
|
|
|
|
/*********************************************************************/
|
|
|
|
/* Constants */
|
|
|
|
/*********************************************************************/
|
|
|
|
#define QMAXSHIFT 7 /* shift limit q precision */
|
|
|
|
/*********************************************************************/
|
|
|
|
/* Local Prototypes */
|
|
|
|
/*********************************************************************/
|
|
|
|
FS_PRIVATE F26Dot6 CalcHorizSpSubpix(int32, F26Dot6*, F26Dot6*);
|
|
FS_PRIVATE F26Dot6 CalcVertSpSubpix(int32, F26Dot6*, F26Dot6*);
|
|
|
|
|
|
/*********************************************************************/
|
|
|
|
/* Export Functions */
|
|
|
|
/*********************************************************************/
|
|
|
|
/* pass callback routine pointers to scanlist for smart dropout control */
|
|
|
|
FS_PUBLIC void fsc_SetupSpline (PSTATE0)
|
|
{
|
|
fsc_SetupCallBacks(ASTATE SC_SPLINECODE, CalcHorizSpSubpix, CalcVertSpSubpix);
|
|
}
|
|
|
|
|
|
/*********************************************************************/
|
|
|
|
FS_PUBLIC int32 fsc_CalcSpline(
|
|
PSTATE /* pointer to state variables */
|
|
F26Dot6 fxX1, /* start point x coordinate */
|
|
F26Dot6 fxY1, /* start point y coordinate */
|
|
F26Dot6 fxX2, /* control point x coordinate */
|
|
F26Dot6 fxY2, /* control point y coordinate */
|
|
F26Dot6 fxX3, /* ending x coordinate */
|
|
F26Dot6 fxY3, /* ending y coordinate */
|
|
uint16 usScanKind ) /* dropout control type */
|
|
{
|
|
F26Dot6 fxXInit, fxYInit; /* initial step values */
|
|
F26Dot6 fxXScan, fxYScan; /* set to first crossings */
|
|
F26Dot6 fxXX2, fxYY2; /* translated reflected control point */
|
|
F26Dot6 fxXX3, fxYY3; /* translated reflected end point */
|
|
|
|
F26Dot6 afxXControl[2]; /* params for BeginElement call */
|
|
F26Dot6 afxYControl[2];
|
|
|
|
void (*pfnAddHorizScan)(PSTATE int32, int32);
|
|
void (*pfnAddVertScan)(PSTATE int32, int32);
|
|
|
|
int32 lABits; /* 1+int(log2(alpha)) */
|
|
int32 lXYBits; /* 1+int(log2(max(x3,y3))) */
|
|
int32 lZBits; /* 6, 5, 4 log2(subpixels per pix) */
|
|
int32 lZShift; /* 0, 1, 2 shift to minipixel */
|
|
F26Dot6 fxZRound; /* rounding factor for minipix shift */
|
|
F26Dot6 fxZSubpix; /* 64, 32, 16 subpixels per pix */
|
|
int32 lQuadrant; /* 1, 2, 3, or 4 */
|
|
|
|
F26Dot6 fxAx, fxAy; /* parametric 2nd order terms */
|
|
F26Dot6 lAlpha; /* cross product measures curvature */
|
|
|
|
int32 lR, lT; /* quadratic coefficients for xx, yy */
|
|
int32 lS2, lU2, lV2; /* half coefficients for xy, x, y */
|
|
int32 lRz, lSz, lTz; /* coeff's times subpix size */
|
|
|
|
int32 lQ; /* cross product value */
|
|
int32 lDQx, lDQy; /* first order derivative */
|
|
int32 lDDQx, lDDQy; /* second order derivative */
|
|
|
|
int32 lYScan; /* scan line counter */
|
|
int32 lYStop; /* scan line end */
|
|
int32 lYIncr; /* scan line direction */
|
|
int32 lYOffset; /* reflection correction */
|
|
int32 lXScan; /* horiz pix position */
|
|
int32 lXStop; /* pix end */
|
|
int32 lXIncr; /* pix increment direction */
|
|
int32 lXOffset; /* reflection correction */
|
|
|
|
static const int32 lZShiftTable[] = { /* for precision adjustment */
|
|
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 0 - 9 */
|
|
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 10 - 19 */
|
|
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 20 - 29 */
|
|
1, 1, 1, 2, 2, 2, 3, 3 /* 30 - 34 */
|
|
};
|
|
|
|
|
|
/* printf("(%li, %li) - (%li, %li) -(%li, %li)\n", fxX1, fxY1, fxX2, fxY2, fxX3, fxY3 ); */
|
|
|
|
|
|
/* Translate spline point 1 to (0,0) and reflect into the first quadrant */
|
|
|
|
if (fxY3 > fxY1) /* if going up */
|
|
{
|
|
lQ = 0L;
|
|
lQuadrant = 1;
|
|
|
|
fxYScan = SCANABOVE(fxY1); /* first scanline to cross */
|
|
fxYInit = fxYScan - fxY1; /* first y step */
|
|
lYScan = (int32)(fxYScan >> SUBSHFT);
|
|
lYStop = (int32)((SCANBELOW(fxY3)) >> SUBSHFT) + 1;
|
|
lYIncr = 1;
|
|
lYOffset = 0; /* no reflection */
|
|
fxYY2 = fxY2 - fxY1; /* translate */
|
|
fxYY3 = fxY3 - fxY1;
|
|
}
|
|
else /* if going down */
|
|
{
|
|
lQ = 1L; /* to include pixel centers */
|
|
lQuadrant = 4;
|
|
|
|
fxYScan = SCANBELOW(fxY1); /* first scanline to cross */
|
|
fxYInit = fxY1 - fxYScan; /* first y step */
|
|
lYScan = (int32)(fxYScan >> SUBSHFT);
|
|
lYStop = (int32)((SCANABOVE(fxY3)) >> SUBSHFT) - 1;
|
|
lYIncr = -1;
|
|
lYOffset = 1; /* reflection correction */
|
|
fxYY2 = fxY1 - fxY2; /* translate and reflect */
|
|
fxYY3 = fxY1 - fxY3;
|
|
}
|
|
|
|
if (fxX3 > fxX1) /* if going right */
|
|
{
|
|
fxXScan = SCANABOVE(fxX1); /* first scanline to cross */
|
|
fxXInit = fxXScan - fxX1; /* first x step */
|
|
lXScan = (int32)(fxXScan >> SUBSHFT);
|
|
lXStop = (int32)((SCANBELOW(fxX3)) >> SUBSHFT) + 1;
|
|
lXIncr = 1;
|
|
lXOffset = 0; /* no reflection */
|
|
fxXX2 = fxX2 - fxX1; /* translate */
|
|
fxXX3 = fxX3 - fxX1;
|
|
}
|
|
else /* if going left or straight */
|
|
{
|
|
lQ = 1L - lQ; /* to include pixel centers */
|
|
lQuadrant = (lQuadrant == 1) ? 2 : 3; /* negative x choices */
|
|
|
|
fxXScan = SCANBELOW(fxX1); /* first scanline to cross */
|
|
fxXInit = fxX1 - fxXScan; /* first x step */
|
|
lXScan = (int32)(fxXScan >> SUBSHFT);
|
|
lXStop = (int32)((SCANABOVE(fxX3)) >> SUBSHFT) - 1;
|
|
lXIncr = -1;
|
|
lXOffset = 1; /* reflection correction */
|
|
fxXX2 = fxX1 - fxX2; /* translate and reflect */
|
|
fxXX3 = fxX1 - fxX3;
|
|
}
|
|
|
|
/*-------------------------------------------------------------------*/
|
|
|
|
afxXControl[0] = fxX2;
|
|
afxYControl[0] = fxY2;
|
|
afxXControl[1] = fxX3;
|
|
afxYControl[1] = fxY3;
|
|
|
|
fsc_BeginElement( ASTATE usScanKind, lQuadrant, SC_SPLINECODE, /* where and what */
|
|
2, afxXControl, afxYControl, /* number of pts */
|
|
&pfnAddHorizScan, &pfnAddVertScan ); /* what to call */
|
|
|
|
/*-------------------------------------------------------------------*/
|
|
|
|
if (usScanKind & SK_NODROPOUT) /* if no dropout control */
|
|
{
|
|
if (lYScan == lYStop) /* and if no scan crossings */
|
|
{
|
|
return NO_ERR; /* then quick exit */
|
|
}
|
|
|
|
if (lXScan == lXStop) /* if nearly vertical */
|
|
{
|
|
lXScan += lXOffset;
|
|
while (lYScan != lYStop)
|
|
{
|
|
pfnAddHorizScan(ASTATE lXScan, lYScan);
|
|
lYScan += lYIncr; /* advance y scan + or - */
|
|
}
|
|
return NO_ERR; /* quick out */
|
|
}
|
|
}
|
|
|
|
/*-------------------------------------------------------------------*/
|
|
|
|
else /* if smart dropout control on */
|
|
{
|
|
if (lXScan == lXStop) /* if nearly vertical */
|
|
{
|
|
lXScan += lXOffset;
|
|
while (lYScan != lYStop)
|
|
{
|
|
pfnAddHorizScan(ASTATE lXScan, lYScan);
|
|
lYScan += lYIncr; /* advance y scan + or - */
|
|
}
|
|
return NO_ERR; /* quick out */
|
|
}
|
|
|
|
if (lYScan == lYStop) /* if nearly horizontal */
|
|
{
|
|
lYScan += lYOffset;
|
|
while (lXScan != lXStop)
|
|
{
|
|
pfnAddVertScan(ASTATE lXScan, lYScan);
|
|
lXScan += lXIncr; /* advance x scan + or - */
|
|
}
|
|
return NO_ERR; /* quick out */
|
|
}
|
|
}
|
|
|
|
/*-------------------------------------------------------------------*/
|
|
|
|
/* Now calculate parametric term precision */
|
|
|
|
Assert(fxXX3 <= MAXSPLINELENGTH);
|
|
Assert(fxYY3 <= MAXSPLINELENGTH);
|
|
|
|
lAlpha = (fxXX2 * fxYY3 - fxYY2 * fxXX3) << 1; /* curvature term */
|
|
|
|
lABits = PowerOf2(lAlpha);
|
|
lXYBits = fxXX3 > fxYY3 ? PowerOf2((int32)fxXX3) : PowerOf2((int32)fxYY3);
|
|
|
|
Assert(lXYBits <= 12); /* max allowed spline bits */
|
|
Assert(lABits <= 25);
|
|
|
|
lZShift = lZShiftTable[lABits + lXYBits]; /* look up precision fix */
|
|
lZBits = SUBSHFT - lZShift;
|
|
|
|
if (lZShift > 0) /* if precision fix is needed */
|
|
{
|
|
fxZRound = 1L << (lZShift - 1);
|
|
|
|
fxXX2 = (fxXX2 + fxZRound) >> lZShift; /* shift to 32 or 16 subpix grid */
|
|
fxXX3 = (fxXX3 + fxZRound) >> lZShift;
|
|
fxYY2 = (fxYY2 + fxZRound) >> lZShift;
|
|
fxYY3 = (fxYY3 + fxZRound) >> lZShift;
|
|
|
|
fxXInit = (fxXInit + fxZRound) >> lZShift;
|
|
fxYInit = (fxYInit + fxZRound) >> lZShift;
|
|
|
|
lAlpha = (fxXX2 * fxYY3 - fxYY2 * fxXX3) << 1; /* recompute curvature */
|
|
}
|
|
|
|
Assert (FXABS(lAlpha * fxXX3) < (1L << 29) + (3L << 24));
|
|
Assert (FXABS(lAlpha * fxYY3) < (1L << 29) + (3L << 24));
|
|
|
|
/* Calculate terms for Q = Rxx + Sxy + Tyy + Ux + Vy */
|
|
|
|
fxAx = fxXX3 - (fxXX2 << 1);
|
|
fxAy = fxYY3 - (fxYY2 << 1);
|
|
|
|
lR = fxAy * fxAy;
|
|
lS2 = -fxAx * fxAy;
|
|
lT = fxAx * fxAx;
|
|
lU2 = fxYY2 * lAlpha;
|
|
lV2 = -fxXX2 * lAlpha;
|
|
|
|
/*
|
|
Calculate starting forward difference terms:
|
|
|
|
lQ = Q(x,y) = Rxx + Sxy + Tyy + Ux + Vy
|
|
lDQx = Q(x+z, y) - Q(x, y) = R(2xz + zz) + Syz + Uz
|
|
lDQy = Q(x, y+z) - Q(x, y) = T(2yz + zz) + Sxz + Vz
|
|
|
|
*/
|
|
fxZSubpix = 1L << lZBits; /* adjusted subpix per pix */
|
|
|
|
if (lXYBits <= QMAXSHIFT) /* if small enough use full Q */
|
|
{
|
|
lQ += (lR * fxXInit + (lS2 << 1) * fxYInit + (lU2 << 1)) * fxXInit +
|
|
(lT * fxYInit + (lV2 << 1)) * fxYInit;
|
|
lDQx = (lR * ((fxXInit << 1) + fxZSubpix) + (lS2 << 1) * fxYInit + (lU2 << 1)) << lZBits;
|
|
lDQy = (lT * ((fxYInit << 1) + fxZSubpix) + (lS2 << 1) * fxXInit + (lV2 << 1)) << lZBits;
|
|
|
|
lRz = lR << (lZBits << 1); /* needed in the loop */
|
|
lSz = (lS2 << 1) << (lZBits << 1);
|
|
lTz = lT << (lZBits << 1);
|
|
}
|
|
else /* if too big take out a 2 * Z */
|
|
{
|
|
lQ += (((lR >> 1) * fxXInit + lS2 * fxYInit + lU2) >> lZBits) * fxXInit +
|
|
(((lT >> 1) * fxYInit + lV2) >> lZBits) * fxYInit;
|
|
|
|
lDQx = lR * (fxXInit + (fxZSubpix >> 1)) + lS2 * fxYInit + lU2;
|
|
lDQy = lT * (fxYInit + (fxZSubpix >> 1)) + lS2 * fxXInit + lV2;
|
|
|
|
lRz = lR << (lZBits - 1); /* needed in the loop */
|
|
lSz = lS2 << lZBits;
|
|
lTz = lT << (lZBits - 1);
|
|
}
|
|
lDDQx = lRz << 1; /* 2nd derivative terms */
|
|
lDDQy = lTz << 1;
|
|
|
|
/*-------------------------------------------------------------------*/
|
|
|
|
if (usScanKind & SK_NODROPOUT) /* if no dropout control */
|
|
{
|
|
lXScan += lXOffset; /* pre increment */
|
|
lXStop += lXOffset; /* limit too */
|
|
|
|
/* Branch to appropriate inner loop */
|
|
|
|
if (lAlpha > 0L) /* if curvature up */
|
|
{
|
|
while ((lXScan != lXStop) && (lYScan != lYStop))
|
|
{
|
|
if ((lQ < 0L) || (lDQy > lTz)) /* check against dy */
|
|
{
|
|
lXScan += lXIncr; /* advance x scan + or - */
|
|
lQ += lDQx; /* adjust cross product */
|
|
lDQx += lDDQx; /* adjust derivative */
|
|
lDQy += lSz; /* adjust cross term */
|
|
}
|
|
else
|
|
{
|
|
pfnAddHorizScan(ASTATE lXScan, lYScan);
|
|
lYScan += lYIncr; /* advance y scan + or - */
|
|
lQ += lDQy; /* adjust cross product */
|
|
lDQy += lDDQy; /* adjust derivative */
|
|
lDQx += lSz; /* adjust cross term */
|
|
}
|
|
}
|
|
}
|
|
else /* if curvature down */
|
|
{
|
|
while ((lXScan != lXStop) && (lYScan != lYStop))
|
|
{
|
|
if ((lQ < 0L) || (lDQx > lRz)) /* check against dx */
|
|
{
|
|
pfnAddHorizScan(ASTATE lXScan, lYScan);
|
|
lYScan += lYIncr; /* advance y scan + or - */
|
|
lQ += lDQy; /* adjust cross product */
|
|
lDQy += lDDQy; /* adjust derivative */
|
|
lDQx += lSz; /* adjust cross term */
|
|
}
|
|
else
|
|
{
|
|
lXScan += lXIncr; /* advance x scan + or - */
|
|
lQ += lDQx; /* adjust cross product */
|
|
lDQx += lDDQx; /* adjust derivative */
|
|
lDQy += lSz; /* adjust cross term */
|
|
}
|
|
}
|
|
}
|
|
|
|
/* if past bounding box, finish up */
|
|
|
|
while (lYScan != lYStop)
|
|
{
|
|
pfnAddHorizScan(ASTATE lXScan, lYScan);
|
|
lYScan += lYIncr; /* advance y scan + or - */
|
|
}
|
|
}
|
|
|
|
/*-------------------------------------------------------------------*/
|
|
|
|
else /* if dropout control on */
|
|
{
|
|
if (lAlpha > 0L) /* if curvature up */
|
|
{
|
|
while ((lXScan != lXStop) && (lYScan != lYStop))
|
|
{
|
|
if ((lQ < 0L) || (lDQy > lTz)) /* check against dy */
|
|
{
|
|
pfnAddVertScan(ASTATE lXScan, lYScan + lYOffset);
|
|
lXScan += lXIncr; /* advance x scan + or - */
|
|
lQ += lDQx; /* adjust cross product */
|
|
lDQx += lDDQx; /* adjust derivative */
|
|
lDQy += lSz; /* adjust cross term */
|
|
}
|
|
else
|
|
{
|
|
pfnAddHorizScan(ASTATE lXScan + lXOffset, lYScan);
|
|
lYScan += lYIncr; /* advance y scan + or - */
|
|
lQ += lDQy; /* adjust cross product */
|
|
lDQy += lDDQy; /* adjust derivative */
|
|
lDQx += lSz; /* adjust cross term */
|
|
}
|
|
}
|
|
}
|
|
else /* if curvature down */
|
|
{
|
|
while ((lXScan != lXStop) && (lYScan != lYStop))
|
|
{
|
|
if ((lQ < 0L) || (lDQx > lRz)) /* check against dx */
|
|
{
|
|
pfnAddHorizScan(ASTATE lXScan + lXOffset, lYScan);
|
|
lYScan += lYIncr; /* advance y scan + or - */
|
|
lQ += lDQy; /* adjust cross product */
|
|
lDQy += lDDQy; /* adjust derivative */
|
|
lDQx += lSz; /* adjust cross term */
|
|
}
|
|
else
|
|
{
|
|
pfnAddVertScan(ASTATE lXScan, lYScan + lYOffset);
|
|
lXScan += lXIncr; /* advance x scan + or - */
|
|
lQ += lDQx; /* adjust cross product */
|
|
lDQx += lDDQx; /* adjust derivative */
|
|
lDQy += lSz; /* adjust cross term */
|
|
}
|
|
}
|
|
}
|
|
|
|
/* if outside the bounding box, finish up */
|
|
|
|
while (lXScan != lXStop)
|
|
{
|
|
pfnAddVertScan(ASTATE lXScan, lYScan + lYOffset);
|
|
lXScan += lXIncr; /* advance x scan + or - */
|
|
}
|
|
|
|
while (lYScan != lYStop)
|
|
{
|
|
pfnAddHorizScan(ASTATE lXScan + lXOffset, lYScan);
|
|
lYScan += lYIncr; /* advance y scan + or - */
|
|
}
|
|
}
|
|
|
|
/*-------------------------------------------------------------------*/
|
|
|
|
return NO_ERR;
|
|
}
|
|
|
|
|
|
/*********************************************************************/
|
|
|
|
/* Private Callback Functions */
|
|
|
|
/*********************************************************************/
|
|
|
|
FS_PRIVATE F26Dot6 CalcHorizSpSubpix(
|
|
int32 lYScan,
|
|
F26Dot6 *pfxX,
|
|
F26Dot6 *pfxY )
|
|
{
|
|
F26Dot6 fxYDrop; /* dropout scan line */
|
|
F26Dot6 fxX1, fxY1; /* local control points */
|
|
F26Dot6 fxX2, fxY2;
|
|
F26Dot6 fxX3, fxY3;
|
|
F26Dot6 fxXMid, fxYMid; /* spline center point */
|
|
|
|
/* printf("Spline (%li, %li) - (%li, %li) - (%li, %li)", *pfxX, *pfxY,
|
|
*(pfxX+1), *(pfxY+1), *(pfxX+2), *(pfxY+2));
|
|
*/
|
|
|
|
fxYDrop = ((F26Dot6)lYScan << SUBSHFT) + SUBHALF;
|
|
|
|
Assert(((fxYDrop > *pfxY) && (fxYDrop < *(pfxY+2))) ||
|
|
((fxYDrop < *pfxY) && (fxYDrop > *(pfxY+2))));
|
|
|
|
fxX2 = *(pfxX+1);
|
|
fxY2 = *(pfxY+1);
|
|
|
|
if (*pfxY < *(pfxY+2)) /* if spline goes up */
|
|
{
|
|
fxX1 = *pfxX; /* just copy it */
|
|
fxY1 = *pfxY;
|
|
fxX3 = *(pfxX+2);
|
|
fxY3 = *(pfxY+2);
|
|
}
|
|
else /* if spline goes down */
|
|
{
|
|
fxX1 = *(pfxX+2); /* flip it upside down */
|
|
fxY1 = *(pfxY+2);
|
|
fxX3 = *pfxX;
|
|
fxY3 = *pfxY;
|
|
}
|
|
|
|
do /* midpoint subdivision */
|
|
{
|
|
fxXMid = (fxX1 + fxX2 + fxX2 + fxX3 + 1) >> 2;
|
|
fxYMid = (fxY1 + fxY2 + fxY2 + fxY3 + 1) >> 2;
|
|
|
|
if (fxYMid > fxYDrop)
|
|
{
|
|
fxX2 = (fxX1 + fxX2) >> 1; /* subdivide down */
|
|
fxY2 = (fxY1 + fxY2) >> 1;
|
|
fxX3 = fxXMid;
|
|
fxY3 = fxYMid;
|
|
}
|
|
else if (fxYMid < fxYDrop)
|
|
{
|
|
fxX2 = (fxX2 + fxX3) >> 1; /* subdivide up */
|
|
fxY2 = (fxY2 + fxY3) >> 1;
|
|
fxX1 = fxXMid;
|
|
fxY1 = fxYMid;
|
|
}
|
|
}
|
|
while (fxYMid != fxYDrop);
|
|
|
|
/* printf(" (%li, %li)\n", fxXMid, fxYMid); */
|
|
|
|
return fxXMid;
|
|
}
|
|
|
|
|
|
/*********************************************************************/
|
|
|
|
FS_PRIVATE F26Dot6 CalcVertSpSubpix(
|
|
int32 lXScan,
|
|
F26Dot6 *pfxX,
|
|
F26Dot6 *pfxY )
|
|
{
|
|
F26Dot6 fxXDrop; /* dropout scan line */
|
|
F26Dot6 fxX1, fxY1; /* local control points */
|
|
F26Dot6 fxX2, fxY2;
|
|
F26Dot6 fxX3, fxY3;
|
|
F26Dot6 fxXMid, fxYMid; /* spline center point */
|
|
|
|
/* printf("Spline (%li, %li) - (%li, %li) - (%li, %li)", *pfxX, *pfxY,
|
|
*(pfxX+1), *(pfxY+1), *(pfxX+2), *(pfxY+2));
|
|
*/
|
|
|
|
fxXDrop = ((F26Dot6)lXScan << SUBSHFT) + SUBHALF;
|
|
|
|
Assert(((fxXDrop > *pfxX) && (fxXDrop < *(pfxX+2))) ||
|
|
((fxXDrop < *pfxX) && (fxXDrop > *(pfxX+2))));
|
|
|
|
fxX2 = *(pfxX+1);
|
|
fxY2 = *(pfxY+1);
|
|
|
|
if (*pfxX < *(pfxX+2)) /* if spline goes right */
|
|
{
|
|
fxX1 = *pfxX; /* just copy it */
|
|
fxY1 = *pfxY;
|
|
fxX3 = *(pfxX+2);
|
|
fxY3 = *(pfxY+2);
|
|
}
|
|
else /* if spline goes left */
|
|
{
|
|
fxX1 = *(pfxX+2); /* flip it around */
|
|
fxY1 = *(pfxY+2);
|
|
fxX3 = *pfxX;
|
|
fxY3 = *pfxY;
|
|
}
|
|
|
|
do
|
|
{
|
|
fxXMid = (fxX1 + fxX2 + fxX2 + fxX3 + 1) >> 2;
|
|
fxYMid = (fxY1 + fxY2 + fxY2 + fxY3 + 1) >> 2;
|
|
|
|
if (fxXMid > fxXDrop)
|
|
{
|
|
fxX2 = (fxX1 + fxX2) >> 1; /* subdivide left */
|
|
fxY2 = (fxY1 + fxY2) >> 1;
|
|
fxX3 = fxXMid;
|
|
fxY3 = fxYMid;
|
|
}
|
|
else if (fxXMid < fxXDrop)
|
|
{
|
|
fxX2 = (fxX2 + fxX3) >> 1; /* subdivide right */
|
|
fxY2 = (fxY2 + fxY3) >> 1;
|
|
fxX1 = fxXMid;
|
|
fxY1 = fxYMid;
|
|
}
|
|
}
|
|
while (fxXMid != fxXDrop);
|
|
|
|
/* printf(" (%li, %li)\n", fxXMid, fxYMid); */
|
|
|
|
return fxYMid;
|
|
}
|
|
|
|
|
|
/*********************************************************************/
|