git.sesse.net Git - rdpsrv/blob - Xserver/lib/font/Type1/curves.c

   1 /* $XConsortium: curves.c,v 1.4 92/07/07 17:14:55 gildea Exp $ */
   2 /* Copyright International Business Machines,Corp. 1991              */
   3 /* All Rights Reserved                                               */
   4
   5 /* License to use, copy, modify, and distribute this software        */
   6 /* and its documentation for any purpose and without fee is          */
   7 /* hereby granted, provided that licensee provides a license to      */
   8 /* IBM, Corp. to use, copy, modify, and distribute derivative        */
   9 /* works and their documentation for any purpose and without         */
  10 /* fee, that the above copyright notice appear in all copies         */
  11 /* and that both that copyright notice and this permission           */
  12 /* notice appear in supporting documentation, and that the name      */
  13 /* of IBM not be used in advertising or publicity pertaining to      */
  14 /* distribution of the software without specific, written prior      */
  15 /* permission.                                                       */
  16
  17 /* IBM PROVIDES THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES        */
  18 /* OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT        */
  19 /* LIMITED TO ANY IMPLIED WARRANTIES OF MERCHANTABILITY,             */
  20 /* FITNESS FOR A PARTICULAR PURPOSE, AND NONINFRINGEMENT OF          */
  21 /* THIRD PARTY RIGHTS.  THE ENTIRE RISK AS TO THE QUALITY AND        */
  22 /* PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT        */
  23 /* OR MAINTAIN, BELONGS TO THE LICENSEE.  SHOULD ANY PORTION OF      */
  24 /* THE SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM) ASSUMES      */
  25 /* THE ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION.  IN      */
  26 /* NO EVENT SHALL IBM BE LIABLE FOR ANY SPECIAL, INDIRECT OR         */
  27 /* CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING         */
  28 /* FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF        */
  29 /* CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT        */
  30 /* OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS           */
  31 /* SOFTWARE.                                                         */
  32 /*
  33 :h1.CURVES Module - Stepping Beziers
  34
  35 This module is responsible for "rasterizing"
  36 third order curves.  That is, it changes the high level curve
  37 specification into a list of pels that that curve travels
  38 through.
  39
  40 :h3.Include Files
  41
  42 Include files needed:
  43 */
  44
  45 #include "objects.h"
  46 #include "spaces.h"
  47 #include "paths.h"
  48 #include "regions.h"
  49 #include "curves.h"
  50 #include "lines.h"
  51 #include "arith.h"
  52
  53
  54 /*
  55 :h3.Functions Provided to Other Modules
  56
  57 External entry points:
  58 */
  59 /*SHARED LINE(S) ORIGINATED HERE*/
  60
  61 /*
  62 Note that "stepping" and "flattening" are so similiar that they use the
  63 same routine.  When the "region" parameter is NULL, that is a flag that
  64 we are flattening instead of stepping.
  65 */
  66 /*
  67 :h2.Bezier Third Order Curves
  68 */
  69 /*
  70 :h3.The "bezierinfo" Structure
  71
  72 This structure is used to store information used when we subdivide
  73 Bezier curves.
  74 */
  75
  76 struct bezierinfo {
  77        struct region *region;  /* the region being built or NULL             */
  78        struct fractpoint last;  /* not used yet; maybe could save some work  */
  79        struct fractpoint origin;  /* the origin of the bezier                */
  80 } ;
  81
  82 /*
  83    Checking for termination of the subdivision process:
  84    This is the stupidest test in the world, just check if the coordinatewise
  85    distance from an end control point to the next control point is less than
  86    one half pel.   If so, we must be done.
  87    This returns 1 if the subdivision is terminated and 0 if you still need
  88    to subdivide.
  89 */
  90
  91 static int BezierTerminationTest(xa,ya,xb,yb,xc,yc,xd,yd)
  92 fractpel xa,ya,xb,yb,xc,yc,xd,yd;
  93 {
  94   fractpel dmax;
  95   dmax =          ABS(xa - xb);
  96   dmax = MAX(dmax,ABS(ya - yb));
  97   dmax = MAX(dmax,ABS(xd - xc));
  98   dmax = MAX(dmax,ABS(yd - yc));
  99   if(dmax > FPHALF)
 100     return(0); /* not done yet */
 101   else
 102     return(1); /* done */
 103 }
 104
 105 /*
 106 :h3.StepBezierRecurse() - The Recursive Logic in StepBezier()
 107
 108 The recursion involves dividing the control polygon into two smaller
 109 control polygons by finding the midpoints of the lines.  This idea is
 110 described in any graphics text book and its simplicity is what caused
 111 Bezier to define his curves as he did.  If the input region 'R' is NULL,
 112 the result is a path that is the 'flattened' curve; otherwise StepBezier
 113 returns nothing special.
 114 */
 115 static struct segment *StepBezierRecurse(I,xA,yA,xB,yB,xC,yC,xD,yD)
 116        struct bezierinfo *I; /* Region under construction or NULL            */
 117        fractpel xA,yA;       /* A control point                              */
 118        fractpel xB,yB;       /* B control point                              */
 119        fractpel xC,yC;       /* C control point                              */
 120        fractpel xD,yD;       /* D control point                              */
 121
 122 {
 123  if (BezierTerminationTest(xA,yA,xB,yB,xC,yC,xD,yD))
 124  {
 125   if (I->region == NULL)
 126    return(PathSegment(LINETYPE, xD - xA, yD - yA));
 127   else
 128    StepLine(I->region, I->origin.x + xA, I->origin.y + yA,
 129                        I->origin.x + xD, I->origin.y + yD);
 130  }
 131  else
 132  {
 133   fractpel xAB,yAB;
 134   fractpel xBC,yBC;
 135   fractpel xCD,yCD;
 136   fractpel xABC,yABC;
 137   fractpel xBCD,yBCD;
 138   fractpel xABCD,yABCD;
 139
 140   xAB = xA + xB;  yAB = yA + yB;
 141   xBC = xB + xC;  yBC = yB + yC;
 142   xCD = xC + xD;  yCD = yC + yD;
 143
 144   xABC = xAB + xBC;  yABC = yAB + yBC;
 145   xBCD = xBC + xCD;  yBCD = yBC + yCD;
 146
 147   xABCD = xABC + xBCD;  yABCD = yABC + yBCD;
 148
 149   xAB >>= 1;   yAB >>= 1;
 150   xBC >>= 1;   yBC >>= 1;
 151   xCD >>= 1;   yCD >>= 1;
 152   xABC >>= 2;   yABC >>= 2;
 153   xBCD >>= 2;   yBCD >>= 2;
 154   xABCD >>= 3;   yABCD >>= 3;
 155
 156   if (I->region == NULL)
 157   {
 158    return( Join(
 159     StepBezierRecurse(I, xA, yA, xAB, yAB, xABC, yABC, xABCD, yABCD),
 160     StepBezierRecurse(I, xABCD, yABCD, xBCD, yBCD, xCD, yCD, xD, yD)
 161                 )
 162          );
 163   }
 164   else
 165   {
 166    StepBezierRecurse(I, xA, yA, xAB, yAB, xABC, yABC, xABCD, yABCD);
 167    StepBezierRecurse(I, xABCD, yABCD, xBCD, yBCD, xCD, yCD, xD, yD);
 168   }
 169  }
 170  /*NOTREACHED*/
 171 }
 172
 173 /*
 174 :h3.TOOBIG() - Macro to Test if a Coordinate is Too Big to Bezier SubDivide Normally
 175
 176 Intermediate values in the Bezier subdivision are 8 times bigger than
 177 the starting values.  If this overflows, a 'long', we are in trouble:
 178 */
 179
 180 #define  BITS         (sizeof(long)*8)
 181 #define  HIGHTEST(p)  (((p)>>(BITS-4)) != 0)  /* includes sign bit */
 182 #define  TOOBIG(xy)   ((xy < 0) ? HIGHTEST(-xy) : HIGHTEST(xy))
 183
 184 /*
 185 :h3.StepBezier() - Produce Run Ends for a Bezier Curve
 186
 187 This is the entry point called from outside the module.
 188 */
 189
 190 struct segment *StepBezier(R, xA, yA, xB, yB, xC, yC, xD, yD)
 191        struct region *R;     /* Region under construction or NULL            */
 192        fractpel xA,yA;       /* A control point                              */
 193        fractpel xB,yB;       /* B control point                              */
 194        fractpel xC,yC;       /* C control point                              */
 195        fractpel xD,yD;       /* D control point                              */
 196 {
 197        struct bezierinfo Info;
 198
 199        Info.region = R;
 200        Info.origin.x = xA;
 201        Info.origin.y = yA;
 202
 203        xB -= xA;
 204        xC -= xA;
 205        xD -= xA;
 206        yB -= yA;
 207        yC -= yA;
 208        yD -= yA;
 209
 210        if ( TOOBIG(xB) || TOOBIG(yB) || TOOBIG(xC) || TOOBIG(yC)
 211             || TOOBIG(xD) || TOOBIG(yD) )
 212                abort("Beziers this big not yet supported");
 213
 214        return(StepBezierRecurse(&Info,
 215                                 (fractpel) 0, (fractpel) 0, xB, yB, xC, yC, xD, yD));
 216 }
 217