text: /* $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.                                                         */
  /*
  :h1.CURVES Module - Stepping Beziers
   
  This module is responsible for "rasterizing"
  third order curves.  That is, it changes the high level curve
  specification into a list of pels that that curve travels
  through.
   
  :h3.Include Files
   
  Include files needed:
  */
   
  #include "types.h"
  #include "objects.h"
  #include "spaces.h"
  #include "paths.h"
  #include "regions.h"
  #include "curves.h"
  #include "lines.h"
  #include "arith.h"
   
   
  /*
  :h3.Functions Provided to Other Modules
   
  External entry points:
  */
  /*SHARED LINE(S) ORIGINATED HERE*/
   
  /*
  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.
  */
  /*
  :h2.Bezier Third Order Curves
  */
  /*
  :h3.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.
  */
   
  int BezierTerminationTest(xa,ya,xb,yb,xc,yc,xd,yd)
  fractpel xa,ya,xb,yb,xc,yc,xd,yd;
  {
    fractpel dmax;
    dmax =          TYPE1_ABS(xa - xb);
    dmax = TYPE1_MAX(dmax,TYPE1_ABS(ya - yb));
    dmax = TYPE1_MAX(dmax,TYPE1_ABS(xd - xc));
    dmax = TYPE1_MAX(dmax,TYPE1_ABS(yd - yc));
    if(dmax > FPHALF)
      return(0); /* not done yet */
    else
      return(1); /* done */
  }
   
  /*
  :h3.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.
  */
  static struct segment *StepBezierRecurse(I,xA,yA,xB,yB,xC,yC,xD,yD)
         struct bezierinfo *I; /* Region under construction or NULL            */
         fractpel xA,yA;       /* A control point                              */
         fractpel xB,yB;       /* B control point                              */
         fractpel xC,yC;       /* C control point                              */
         fractpel xD,yD;       /* D control point                              */
   
  {
   if (BezierTerminationTest(xA,yA,xB,yB,xC,yC,xD,yD))
   {
    if (I->region == NULL)
     return(PathSegment(LINETYPE, xD - xA, yD - yA));
    else
     StepLine(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;   yBC >>= 1;
    xCD >>= 1;   yCD >>= 1;
    xABC >>= 2;   yABC >>= 2;
    xBCD >>= 2;   yBCD >>= 2;
    xABCD >>= 3;   yABCD >>= 3;
   
    if (I->region == NULL)
    {
     return( Join(
      StepBezierRecurse(I, xA, yA, xAB, yAB, xABC, yABC, xABCD, yABCD),
      StepBezierRecurse(I, xABCD, yABCD, xBCD, yBCD, xCD, yCD, xD, yD)
                  )
           );
    }
    else
    {
     StepBezierRecurse(I, xA, yA, xAB, yAB, xABC, yABC, xABCD, yABCD);
     StepBezierRecurse(I, xABCD, yABCD, xBCD, yBCD, xCD, yCD, xD, yD);
    }
   }
   /*NOTREACHED*/
   /* To make ANSI-C-comnpiler happy (RMz): */
   return(0);
  }
   
  /*
  :h3.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))
   
  /*
  :h3.StepBezier() - Produce Run Ends for a Bezier Curve
   
  This is the entry point called from outside the module.
  */
   
  struct segment *StepBezier(R, xA, yA, xB, yB, xC, yC, xD, yD)
         struct region *R;     /* Region under construction or NULL            */
         fractpel xA,yA;       /* A control point                              */
         fractpel xB,yB;       /* B control point                              */
         fractpel xC,yC;       /* C control point                              */
         fractpel xD,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) )
                 abort("Beziers this big not yet supported", 3);
   
         return(StepBezierRecurse(&Info,
                                  (fractpel) 0, (fractpel) 0, xB, yB, xC, yC, xD, yD));
  }
   
  