Back to index

tetex-bin  3.0
curves.c
Go to the documentation of this file.
00001 /* $XConsortium: curves.c,v 1.3 91/10/10 11:17:56 rws Exp $ */
00002 /* Copyright International Business Machines,Corp. 1991              */
00003 /* All Rights Reserved                                               */
00004  
00005 /* License to use, copy, modify, and distribute this software        */
00006 /* and its documentation for any purpose and without fee is          */
00007 /* hereby granted, provided that licensee provides a license to      */
00008 /* IBM, Corp. to use, copy, modify, and distribute derivative        */
00009 /* works and their documentation for any purpose and without         */
00010 /* fee, that the above copyright notice appear in all copies         */
00011 /* and that both that copyright notice and this permission           */
00012 /* notice appear in supporting documentation, and that the name      */
00013 /* of IBM not be used in advertising or publicity pertaining to      */
00014 /* distribution of the software without specific, written prior      */
00015 /* permission.                                                       */
00016  
00017 /* IBM PROVIDES THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES        */
00018 /* OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT        */
00019 /* LIMITED TO ANY IMPLIED WARRANTIES OF MERCHANTABILITY,             */
00020 /* FITNESS FOR A PARTICULAR PURPOSE, AND NONINFRINGEMENT OF          */
00021 /* THIRD PARTY RIGHTS.  THE ENTIRE RISK AS TO THE QUALITY AND        */
00022 /* PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT        */
00023 /* OR MAINTAIN, BELONGS TO THE LICENSEE.  SHOULD ANY PORTION OF      */
00024 /* THE SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM) ASSUMES      */
00025 /* THE ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION.  IN      */
00026 /* NO EVENT SHALL IBM BE LIABLE FOR ANY SPECIAL, INDIRECT OR         */
00027 /* CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING         */
00028 /* FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF        */
00029 /* CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT        */
00030 /* OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS           */
00031 /* SOFTWARE.                                                         */
00032 /*
00033 :h1.CURVES Module - Stepping Beziers
00034  
00035 This module is responsible for "rasterizing"
00036 third order curves.  That is, it changes the high level curve
00037 specification into a list of pels that that curve travels
00038 through.
00039  
00040 :h3.Include Files
00041  
00042 Include files needed:
00043 */
00044  
00045 #include "types.h"
00046 #include "objects.h"
00047 #include "spaces.h"
00048 #include "paths.h"
00049 #include "regions.h"
00050 #include "curves.h"
00051 #include "lines.h"
00052 #include "arith.h"
00053  
00054  
00055 /*
00056 :h3.Functions Provided to Other Modules
00057  
00058 External entry points:
00059 */
00060 /*SHARED LINE(S) ORIGINATED HERE*/
00061  
00062 /*
00063 Note that "stepping" and "flattening" are so similiar that they use the
00064 same routine.  When the "region" parameter is NULL, that is a flag that
00065 we are flattening instead of stepping.
00066 */
00067 /*
00068 :h2.Bezier Third Order Curves
00069 */
00070 /*
00071 :h3.The "bezierinfo" Structure
00072  
00073 This structure is used to store information used when we subdivide
00074 Bezier curves.
00075 */
00076  
00077 struct bezierinfo {
00078        struct region *region;  /* the region being built or NULL             */
00079        struct fractpoint last;  /* not used yet; maybe could save some work  */
00080        struct fractpoint origin;  /* the origin of the bezier                */
00081 } ;
00082  
00083 /*
00084    Checking for termination of the subdivision process:
00085    This is the stupidest test in the world, just check if the coordinatewise
00086    distance from an end control point to the next control point is less than
00087    one half pel.   If so, we must be done.
00088    This returns 1 if the subdivision is terminated and 0 if you still need
00089    to subdivide.
00090 */
00091  
00092 int BezierTerminationTest(xa,ya,xb,yb,xc,yc,xd,yd)
00093 fractpel xa,ya,xb,yb,xc,yc,xd,yd;
00094 {
00095   fractpel dmax;
00096   dmax =          ABS(xa - xb);
00097   dmax = MAX(dmax,ABS(ya - yb));
00098   dmax = MAX(dmax,ABS(xd - xc));
00099   dmax = MAX(dmax,ABS(yd - yc));
00100   if(dmax > FPHALF)
00101     return(0); /* not done yet */
00102   else
00103     return(1); /* done */
00104 }
00105  
00106 /*
00107 :h3.StepBezierRecurse() - The Recursive Logic in StepBezier()
00108  
00109 The recursion involves dividing the control polygon into two smaller
00110 control polygons by finding the midpoints of the lines.  This idea is
00111 described in any graphics text book and its simplicity is what caused
00112 Bezier to define his curves as he did.  If the input region 'R' is NULL,
00113 the result is a path that is the 'flattened' curve; otherwise StepBezier
00114 returns nothing special.
00115 */
00116 static struct segment *StepBezierRecurse(I,xA,yA,xB,yB,xC,yC,xD,yD)
00117        struct bezierinfo *I; /* Region under construction or NULL            */
00118        fractpel xA,yA;       /* A control point                              */
00119        fractpel xB,yB;       /* B control point                              */
00120        fractpel xC,yC;       /* C control point                              */
00121        fractpel xD,yD;       /* D control point                              */
00122  
00123 {
00124  if (BezierTerminationTest(xA,yA,xB,yB,xC,yC,xD,yD))
00125  {
00126   if (I->region == NULL)
00127    return(PathSegment(LINETYPE, xD - xA, yD - yA));
00128   else
00129    StepLine(I->region, I->origin.x + xA, I->origin.y + yA,
00130                        I->origin.x + xD, I->origin.y + yD);
00131  }
00132  else
00133  {
00134   fractpel xAB,yAB;
00135   fractpel xBC,yBC;
00136   fractpel xCD,yCD;
00137   fractpel xABC,yABC;
00138   fractpel xBCD,yBCD;
00139   fractpel xABCD,yABCD;
00140  
00141   xAB = xA + xB;  yAB = yA + yB;
00142   xBC = xB + xC;  yBC = yB + yC;
00143   xCD = xC + xD;  yCD = yC + yD;
00144  
00145   xABC = xAB + xBC;  yABC = yAB + yBC;
00146   xBCD = xBC + xCD;  yBCD = yBC + yCD;
00147  
00148   xABCD = xABC + xBCD;  yABCD = yABC + yBCD;
00149  
00150   xAB >>= 1;   yAB >>= 1;
00151   xBC >>= 1;   yBC >>= 1;
00152   xCD >>= 1;   yCD >>= 1;
00153   xABC >>= 2;   yABC >>= 2;
00154   xBCD >>= 2;   yBCD >>= 2;
00155   xABCD >>= 3;   yABCD >>= 3;
00156  
00157   if (I->region == NULL)
00158   {
00159    return( Join(
00160     StepBezierRecurse(I, xA, yA, xAB, yAB, xABC, yABC, xABCD, yABCD),
00161     StepBezierRecurse(I, xABCD, yABCD, xBCD, yBCD, xCD, yCD, xD, yD)
00162                 )
00163          );
00164   }
00165   else
00166   {
00167    StepBezierRecurse(I, xA, yA, xAB, yAB, xABC, yABC, xABCD, yABCD);
00168    StepBezierRecurse(I, xABCD, yABCD, xBCD, yBCD, xCD, yCD, xD, yD);
00169   }
00170  }
00171  /*NOTREACHED*/
00172  return NULL;
00173 }
00174  
00175 /*
00176 :h3.TOOBIG() - Macro to Test if a Coordinate is Too Big to Bezier SubDivide Normally
00177  
00178 Intermediate values in the Bezier subdivision are 8 times bigger than
00179 the starting values.  If this overflows, a 'long', we are in trouble:
00180 */
00181  
00182 #if defined(BITS)
00183 #undef BITS
00184 #endif
00185 #define  BITS         (sizeof(LONG)*8)
00186 #define  HIGHTEST(p)  (((p)>>(BITS-4)) != 0)  /* includes sign bit */
00187 #define  TOOBIG(xy)   ((xy < 0) ? HIGHTEST(-xy) : HIGHTEST(xy))
00188  
00189 /*
00190 :h3.StepBezier() - Produce Run Ends for a Bezier Curve
00191  
00192 This is the entry point called from outside the module.
00193 */
00194  
00195 struct segment *StepBezier(R, xA, yA, xB, yB, xC, yC, xD, yD)
00196        struct region *R;     /* Region under construction or NULL            */
00197        fractpel xA,yA;       /* A control point                              */
00198        fractpel xB,yB;       /* B control point                              */
00199        fractpel xC,yC;       /* C control point                              */
00200        fractpel xD,yD;       /* D control point                              */
00201 {
00202        struct bezierinfo Info;
00203  
00204        Info.region = R;
00205        Info.origin.x = xA;
00206        Info.origin.y = yA;
00207  
00208        xB -= xA;
00209        xC -= xA;
00210        xD -= xA;
00211        yB -= yA;
00212        yC -= yA;
00213        yD -= yA;
00214  
00215        if ( TOOBIG(xB) || TOOBIG(yB) || TOOBIG(xC) || TOOBIG(yC)
00216             || TOOBIG(xD) || TOOBIG(yD) )
00217                t1_abort("Beziers this big not yet supported");
00218  
00219        return(StepBezierRecurse(&Info,
00220                                 (fractpel) 0, (fractpel) 0, xB, yB, xC, yC, xD, yD));
00221 }
00222