Back to index

tetex-bin  3.0
spaces.c
Go to the documentation of this file.
00001 /* $XConsortium: spaces.c,v 1.4 91/10/10 11:19:16 rws Exp $ */
00002 /* Copyright International Business Machines, Corp. 1991
00003  * All Rights Reserved
00004  * Copyright Lexmark International, Inc. 1991
00005  * All Rights Reserved
00006  *
00007  * License to use, copy, modify, and distribute this software and its
00008  * documentation for any purpose and without fee is hereby granted,
00009  * provided that the above copyright notice appear in all copies and that
00010  * both that copyright notice and this permission notice appear in
00011  * supporting documentation, and that the name of IBM or Lexmark not be
00012  * used in advertising or publicity pertaining to distribution of the
00013  * software without specific, written prior permission.
00014  *
00015  * IBM AND LEXMARK PROVIDE THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES OF
00016  * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO ANY
00017  * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
00018  * AND NONINFRINGEMENT OF THIRD PARTY RIGHTS.  THE ENTIRE RISK AS TO THE
00019  * QUALITY AND PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT
00020  * OR MAINTAIN, BELONGS TO THE LICENSEE.  SHOULD ANY PORTION OF THE
00021  * SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM OR LEXMARK) ASSUMES THE
00022  * ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION.  IN NO EVENT SHALL
00023  * IBM OR LEXMARK BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
00024  * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
00025  * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
00026  * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
00027  * THIS SOFTWARE.
00028  */
00029  /* SPACES   CWEB         V0021 ********                             */
00030 /*
00031 :h1 id=spaces.SPACES Module - Handles Coordinate Spaces
00032  
00033 This module is responsible for handling the TYPE1IMAGER "XYspace" object.
00034  
00035 &author. Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com)
00036  
00037  
00038 :h3.Include Files
00039 */
00040 
00041 #include <stdio.h>
00042 #include <stdlib.h>
00043 #include <string.h>
00044 
00045 #include "types.h"
00046 #include "objects.h"
00047 #include "spaces.h"
00048 #include "paths.h"
00049 #include "pictures.h"
00050 #include "fonts.h"
00051 #include "arith.h"
00052 #include "trig.h"
00053 
00054 static int FindFfcn();
00055 static int FindIfcn();
00056 /*
00057 :h3.Entry Points Provided to the TYPE1IMAGER User
00058 */
00059  
00060 /*SHARED LINE(S) ORIGINATED HERE*/
00061  
00062 /*
00063 :h3.Entry Points Provided to Other Modules
00064 */
00065  
00066 /*
00067 In addition, other modules call the SPACES module through function
00068 vectors in the "XYspace" structure.  The entry points accessed that
00069 way are "FConvert()", "IConvert()", and "ForceFloat()".
00070 */
00071  
00072 /*SHARED LINE(S) ORIGINATED HERE*/
00073 /*
00074 :h3.Macros and Typedefs Provided to Other Modules
00075  
00076 :h4.Duplicating and Killing Spaces
00077  
00078 Destroying XYspaces is so simple we can do it with a
00079 macro:
00080 */
00081  
00082 /*SHARED LINE(S) ORIGINATED HERE*/
00083 /*
00084 On the other hand, duplicating XYspaces is slightly more difficult
00085 because of the need to keep a unique ID in the space, see
00086 :hdref refid=dupspace..
00087  
00088 :h4.Fixed Point Pel Representation
00089  
00090 We represent pel positions with fixed point numbers.  This does NOT
00091 mean integer, but truly means fixed point, with a certain number
00092 of binary digits (FRACTBITS) representing the fractional part of the
00093 pel.
00094 */
00095  
00096 /*SHARED LINE(S) ORIGINATED HERE*/
00097 /*
00098 :h2.Data Structures for Coordinate Spaces and Points
00099 */
00100 /*
00101 :h3 id=matrix.Matrices
00102  
00103 TYPE1IMAGER uses 2x2 transformation matrices.  We'll use C notation for
00104 such a matrix (M[2][2]), the first index being rows, the second columns.
00105 */
00106  
00107 /*
00108 :h3.The "doublematrix" Structure
00109  
00110 We frequently find it desirable to store both a matrix and its
00111 inverse.  We store these in a "doublematrix" structure.
00112 */
00113  
00114 /*SHARED LINE(S) ORIGINATED HERE*/
00115  
00116 /*
00117 :h3.The "XYspace" Structure
00118  
00119 The XYspace structure represents the XYspace object.
00120 */
00121  
00122 /*SHARED LINE(S) ORIGINATED HERE*/
00123 #define    RESERVED  10      /* 'n' IDs are reserved for invalid & immortal spaces */
00124 /*
00125 */
00126 #define    NEXTID    ((SpaceID < RESERVED) ? (SpaceID = RESERVED) : ++SpaceID)
00127  
00128 static unsigned int SpaceID = 1;
00129  
00130 struct XYspace *CopySpace(S)
00131        register struct XYspace *S;
00132 {
00133        S = (struct XYspace *)Allocate(sizeof(struct XYspace), S, 0);
00134        S->ID = NEXTID;
00135        return(S);
00136 }
00137 /*
00138 :h3.The "fractpoint" Structure
00139  
00140 A fractional point is just a "fractpel" x and y:
00141 */
00142  
00143 /*SHARED LINE(S) ORIGINATED HERE*/
00144  
00145 /*
00146 :h3.Lazy Evaluation of Matrix Inverses
00147  
00148 Calculating the inverse of a matrix is somewhat involved, and we usually
00149 do not need them.  So, we flag whether or not the space has the inverse
00150 already calculated:
00151 */
00152  
00153 #define    HASINVERSE(flag)   ((flag)&0x80)
00154  
00155 /*
00156 The following macro forces a space to have an inverse:
00157 */
00158  
00159 #define    CoerceInverse(S)   if (!HASINVERSE((S)->flag)) { \
00160     MatrixInvert((S)->tofract.normal, (S)->tofract.inverse); (S)->flag |= HASINVERSE(ON); }
00161 /*
00162 :h3.IDENTITY Space
00163  
00164 IDENTITY space is (logically) the space corresponding to the identity
00165 transformation matrix.  However, since all our transformation matrices
00166 have a common FRACTFLOAT scale factor to convert to 'fractpel's, that
00167 is actually what we store in 'tofract' matrix of IDENTITY:
00168 */
00169  
00170 static struct XYspace identity = { SPACETYPE, ISPERMANENT(ON) + ISIMMORTAL(ON)
00171                         + HASINVERSE(ON), 2, /* added 3-26-91 PNM */
00172                         NULL, NULL,
00173                         NULL, NULL, NULL, NULL,
00174                      INVALIDID + 1, 0,
00175                       {{{FRACTFLOAT, 0.0}, {0.0, FRACTFLOAT}},
00176                         {{1.0/FRACTFLOAT, 0.0}, {0.0, 1.0/FRACTFLOAT}}},
00177                         {{0, 0}, {0, 0}} };
00178 struct XYspace *IDENTITY = &identity;
00179  
00180 /*
00181 */
00182 #define  MAXCONTEXTS   16
00183  
00184 static struct doublematrix contexts[MAXCONTEXTS];
00185  
00186 #ifdef notdef
00187 
00188 static int nextcontext = 1;
00189  
00190 /*SHARED LINE(S) ORIGINATED HERE*/
00191 
00192 #if __STDC__
00193 #define   pointer          void *
00194 #else
00195 #define   pointer          char *
00196 #endif
00197  
00198 /*
00199 :h3.FindDeviceContext() - Find the Context Given a Device
00200  
00201 This routine, given a device, returns the index of the device's
00202 transformation matrix in the context array.  If it cannot find it,
00203 it will allocate a new array entry and fill it out.
00204 */
00205  
00206 static int FindDeviceContext(device)
00207        pointer device;       /* device token                                 */
00208 {
00209        DOUBLE M[2][2];       /* temporary matrix                             */
00210        float Xres,Yres;      /* device  resolution                           */
00211        int orient = -1;      /* device orientation                           */
00212        int rc = -1;          /* return code for QueryDeviceState             */
00213  
00214        if (rc != 0)          /* we only bother with this check once          */
00215                abort("Context:  QueryDeviceState didn't work", 44);
00216  
00217        M[0][0] = M[1][0] = M[0][1] = M[1][1] = 0.0;
00218  
00219        switch (orient) {
00220            case 0:
00221                M[0][0] = Xres;  M[1][1] = -Yres;
00222                break;
00223            case 1:
00224                M[1][0] = Yres;  M[0][1] = Xres;
00225                break;
00226            case 2:
00227                M[0][0] = -Xres;  M[1][1] = Yres;
00228                break;
00229            case 3:
00230                M[1][0] = -Yres;  M[0][1] = -Xres;
00231                break;
00232            default:
00233                abort("QueryDeviceState returned invalid orientation", 45);
00234        }
00235        return(FindContext(M));
00236 }
00237  
00238 /*
00239 :h3.FindContext() - Find the Context Given a Matrix
00240  
00241 This routine, given a matrix, returns the index of that matrix matrix in
00242 the context array.  If it cannot find it, it will allocate a new array
00243 entry and fill it out.
00244 */
00245  
00246 int FindContext(M)
00247        DOUBLE M[2][2];       /* array to search for                          */
00248 {
00249        register int i;       /* loop variable for search                     */
00250        for (i=0; i < nextcontext; i++)
00251                if (M[0][0] == contexts[i].normal[0][0] && M[1][0] == contexts[i].normal[1][0]
00252                    && M[0][1] == contexts[i].normal[0][1] && M[1][1] == contexts[i].normal[1][1])
00253                        break;
00254  
00255        if (i >= nextcontext) {
00256                if (i >= MAXCONTEXTS)
00257                        abort("Context:  out of them", 46);
00258                LONGCOPY(contexts[i].normal, M, sizeof(contexts[i].normal));
00259                MatrixInvert(M, contexts[i].inverse);
00260                nextcontext++;
00261        }
00262  
00263        return(i);
00264 }
00265  
00266 /*
00267 :h3.Context() - Create a Coordinate Space for a Device
00268  
00269 This user operator is implemented by first finding the device context
00270 array index, then transforming IDENTITY space to create an appropriate
00271 cooridnate space.
00272 */
00273  
00274 struct XYspace *Context(device, units)
00275        pointer device;       /* device token                                 */
00276        DOUBLE units;         /* multiples of one inch                        */
00277 {
00278        DOUBLE M[2][2];       /* device transformation matrix                 */
00279        register int n;       /* will hold device context number              */
00280        register struct XYspace *S;  /* XYspace constructed                   */
00281  
00282        IfTrace2((MustTraceCalls),"Context(%x, %f)\n", device, &units);
00283  
00284        ARGCHECK((device == NULL), "Context of NULLDEVICE not allowed",
00285                     NULL, IDENTITY, (0), struct XYspace *);
00286        ARGCHECK((units == 0.0), "Context: bad units", NULL, IDENTITY, (0), struct XYspace *);
00287  
00288        n = FindDeviceContext(device);
00289  
00290        LONGCOPY(M, contexts[n].normal, sizeof(M));
00291  
00292        M[0][0] *= units;
00293        M[0][1] *= units;
00294        M[1][0] *= units;
00295        M[1][1] *= units;
00296  
00297        S = (struct XYspace *)Xform(IDENTITY, M);
00298  
00299        S->context = n;
00300        return(S);
00301 }
00302 #endif
00303  
00304 /*
00305 :h3.ConsiderContext() - Adjust a Matrix to Take Out Device Transform
00306  
00307 Remember, we have :f/x times U times D/ and :f/M/ and and we want :f/x
00308 times U times M times D/.  An easy way to do this is to calculate
00309 :f/D sup <-1> times M times D/, because:
00310 :formula.
00311 x times U times D times D sup <-1> times M times D = x times U times M times D
00312 :formula.
00313 So this subroutine, given an :f/M/and an object, finds the :f/D/ for that
00314 object and modifies :f/M/ so it is :f/D sup <-1> times M times D/.
00315 */
00316  
00317 static void ConsiderContext(obj, M)
00318        register struct xobject *obj;  /* object to be transformed            */
00319        register DOUBLE M[2][2];    /* matrix (may be changed)                */
00320 {
00321        register int context=0; /* index in contexts array                      */
00322  
00323        if (obj == NULL) return;
00324  
00325        if (ISPATHTYPE(obj->type)) {
00326                struct segment *path = (struct segment *) obj;
00327  
00328                context = path->context;
00329        }
00330        else if (obj->type == SPACETYPE) {
00331                struct XYspace *S = (struct XYspace *) obj;
00332  
00333                context = S->context;
00334        }
00335        else if (obj->type == PICTURETYPE) {
00336 
00337        }
00338        else
00339                context = NULLCONTEXT;
00340  
00341        if (context != NULLCONTEXT) {
00342                MatrixMultiply(contexts[context].inverse, M, M);
00343                MatrixMultiply(M, contexts[context].normal, M);
00344        }
00345 }
00346  
00347 /*
00348 :h2.Conversion from User's X,Y to "fractpel" X,Y
00349  
00350 When the user is building paths (lines, moves, curves, etc.) he passes
00351 the control points (x,y) for the paths together with an XYspace.  We
00352 must convert from the user's (x,y) to our internal representation
00353 which is in pels (fractpels, actually).  This involves transforming
00354 the user's (x,y) under the coordinate space transformation.  It is
00355 important that we do this quickly.  So, we store pointers to different
00356 conversion functions right in the XYspace structure.  This allows us
00357 to have simpler special case functions for the more commonly
00358 encountered types of transformations.
00359  
00360 :h3.Convert(), IConvert(), and ForceFloat() - Called Through "XYspace" Structure
00361  
00362 These are functions that fit in the "convert" and "iconvert" function
00363 pointers in the XYspace structure.  They call the "xconvert", "yconvert",
00364 "ixconvert", and "iyconvert" as appropriate to actually do the work.
00365 These secondary routines come in many flavors to handle different
00366 special cases as quickly as possible.
00367 */
00368  
00369 int FXYConvert(pt, S, x, y)
00370        register struct fractpoint *pt;  /* point to set                      */
00371        register struct XYspace *S;  /* relevant coordinate space             */
00372        register DOUBLE x,y;  /* user's coordinates of point                  */
00373 {
00374        pt->x = (*S->xconvert)(S->tofract.normal[0][0], S->tofract.normal[1][0], x, y);
00375        pt->y = (*S->yconvert)(S->tofract.normal[0][1], S->tofract.normal[1][1], x, y);
00376        return(0);
00377        
00378 }
00379  
00380 int IXYConvert(pt, S, x, y)
00381        register struct fractpoint *pt;  /* point to set                      */
00382        register struct XYspace *S;  /* relevant coordinate space             */
00383        register LONG x,y;    /* user's coordinates of point                  */
00384 {
00385        pt->x = (*S->ixconvert)(S->itofract[0][0], S->itofract[1][0], x, y);
00386        pt->y = (*S->iyconvert)(S->itofract[0][1], S->itofract[1][1], x, y);
00387        return(0);
00388        
00389 }
00390  
00391 /*
00392 ForceFloat is a substitute for IConvert(), when we just do not have
00393 enough significant digits in the coefficients to get high enough
00394 precision in the answer with fixed point arithmetic.  So, we force the
00395 integers to floats, and do the arithmetic all with floats:
00396 */
00397  
00398 int ForceFloat(pt, S, x, y)
00399        register struct fractpoint *pt;  /* point to set                      */
00400        register struct XYspace *S;  /* relevant coordinate space             */
00401        register LONG x,y;    /* user's coordinates of point                  */
00402 {
00403        (*S->convert)(pt, S, (DOUBLE) x, (DOUBLE) y);
00404        return(0);
00405        
00406 }
00407  
00408 /*
00409 :h3.FXYboth(), FXonly(), FYonly() - Floating Point Conversion
00410  
00411 These are the routines we use when the user has given us floating
00412 point numbers for x and y. FXYboth() is the general purpose routine;
00413 FXonly() and FYonly() are special cases when one of the coefficients
00414 is 0.0.
00415 */
00416  
00417 fractpel FXYboth(cx, cy, x, y)
00418        register DOUBLE cx,cy;  /* x and y coefficients                       */
00419        register DOUBLE x,y;  /* user x,y                                     */
00420 {
00421        register DOUBLE r;    /* temporary float                              */
00422  
00423        r = x * cx + y * cy;
00424        return((fractpel) r);
00425 }
00426  
00427 /*ARGSUSED*/
00428 fractpel FXonly(cx, cy, x, y)
00429        register DOUBLE cx,cy;  /* x and y coefficients                       */
00430        register DOUBLE x,y;  /* user x,y                                     */
00431 {
00432        register DOUBLE r;    /* temporary float                              */
00433  
00434        r = x * cx;
00435        return((fractpel) r);
00436 }
00437  
00438 /*ARGSUSED*/
00439 fractpel FYonly(cx, cy, x, y)
00440        register DOUBLE cx,cy;  /* x and y coefficients                       */
00441        register DOUBLE x,y;  /* user x,y                                     */
00442 {
00443        register DOUBLE r;    /* temporary float                              */
00444  
00445        r = y * cy;
00446        return((fractpel) r);
00447 }
00448  
00449 /*
00450 :h3.IXYboth(), IXonly(), IYonly() - Simple Integer Conversion
00451  
00452 These are the routines we use when the user has given us integers for
00453 x and y, and the coefficients have enough significant digits to
00454 provide precise answers with only "long" (32 bit?) multiplication.
00455 IXYboth() is the general purpose routine; IXonly() and IYonly() are
00456 special cases when one of the coefficients is 0.
00457 */
00458  
00459 fractpel IXYboth(cx, cy, x, y)
00460        register fractpel cx,cy;  /* x and y coefficients                     */
00461        register LONG x,y;    /* user x,y                                     */
00462 {
00463        return(x * cx + y * cy);
00464 }
00465  
00466 /*ARGSUSED*/
00467 fractpel IXonly(cx, cy, x, y)
00468        register fractpel cx,cy;  /* x and y coefficients                     */
00469        register LONG x,y;    /* user x,y                                     */
00470 {
00471        return(x * cx);
00472 }
00473  
00474 /*ARGSUSED*/
00475 fractpel IYonly(cx, cy, x, y)
00476        register fractpel cx,cy;  /* x and y coefficients                     */
00477        register LONG x,y;    /* user x,y                                     */
00478 {
00479        return(y * cy);
00480 }
00481  
00482  
00483 /*
00484 :h3.FPXYboth(), FPXonly(), FPYonly() - More Involved Integer Conversion
00485  
00486 These are the routines we use when the user has given us integers for
00487 x and y, but the coefficients do not have enough significant digits to
00488 provide precise answers with only "long" (32 bit?)  multiplication.
00489 We have increased the number of significant bits in the coefficients
00490 by FRACTBITS; therefore we must use "double long" (64 bit?)
00491 multiplication by calling FPmult().  FPXYboth() is the general purpose
00492 routine; FPXonly() and FPYonly() are special cases when one of the
00493 coefficients is 0.
00494  
00495 Note that it is perfectly possible for us to calculate X with the
00496 "FP" method and Y with the "I" method, or vice versa.  It all depends
00497 on how the functions in the XYspace structure are filled out.
00498 */
00499  
00500 fractpel FPXYboth(cx, cy, x, y)
00501        register fractpel cx,cy;  /* x and y coefficients                     */
00502        register LONG x,y;    /* user x,y                                     */
00503 {
00504        return( FPmult(x, cx) + FPmult(y, cy) );
00505 }
00506  
00507 /*ARGSUSED*/
00508 fractpel FPXonly(cx, cy, x, y)
00509        register fractpel cx,cy;  /* x and y coefficients                     */
00510        register LONG x,y;    /* user x,y                                     */
00511 {
00512        return( FPmult(x, cx) );
00513 }
00514  
00515 /*ARGSUSED*/
00516 fractpel FPYonly(cx, cy, x, y)
00517        register fractpel cx,cy;  /* x and y coefficients                     */
00518        register LONG x,y;    /* user x,y                                     */
00519 {
00520        return( FPmult(y, cy) );
00521 }
00522  
00523  
00524  
00525 /*
00526 :h3.FillOutFcns() - Determine the Appropriate Functions to Use for Conversion
00527  
00528 This function fills out the "convert" and "iconvert" function pointers
00529 in an XYspace structure, and also fills the "helper"
00530 functions that actually do the work.
00531 */
00532  
00533 static void FillOutFcns(S)
00534        register struct XYspace *S;  /* functions will be set in this structure */
00535 {
00536        S->convert = FXYConvert;
00537        S->iconvert = IXYConvert;
00538  
00539        FindFfcn(S->tofract.normal[0][0], S->tofract.normal[1][0], &S->xconvert);
00540        FindFfcn(S->tofract.normal[0][1], S->tofract.normal[1][1], &S->yconvert);
00541        FindIfcn(S->tofract.normal[0][0], S->tofract.normal[1][0],
00542                 &S->itofract[0][0], &S->itofract[1][0], &S->ixconvert);
00543        FindIfcn(S->tofract.normal[0][1], S->tofract.normal[1][1],
00544                 &S->itofract[0][1], &S->itofract[1][1], &S->iyconvert);
00545  
00546        if (S->ixconvert == NULL || S->iyconvert == NULL)
00547                 S->iconvert = ForceFloat;
00548 }
00549  
00550 /*
00551 :h4.FindFfcn() - Subroutine of FillOutFcns() to Fill Out Floating Functions
00552  
00553 This function tests for the special case of one of the coefficients
00554 being zero:
00555 */
00556  
00557 static int FindFfcn(cx, cy, fcnP)
00558        register DOUBLE cx,cy;  /* x and y coefficients                       */
00559        register fractpel (**fcnP)();  /* pointer to function to set          */
00560 {
00561        if (cx == 0.0)
00562                *fcnP = FYonly;
00563        else if (cy == 0.0)
00564                *fcnP = FXonly;
00565        else
00566                *fcnP = FXYboth;
00567        return(0);
00568        
00569 }
00570  
00571 /*
00572 :h4.FindIfcn() - Subroutine of FillOutFcns() to Fill Out Integer Functions
00573  
00574 There are two types of integer functions, the 'I' type and the 'FP' type.
00575 We use the I type functions when we are satisfied with simple integer
00576 arithmetic.  We used the FP functions when we feel we need higher
00577 precision (but still fixed point) arithmetic.  If all else fails,
00578 we store a NULL indicating that this we should do the conversion in
00579 floating point.
00580 */
00581  
00582 static int FindIfcn(cx, cy, icxP, icyP, fcnP)
00583        register DOUBLE cx,cy;  /* x and y coefficients                       */
00584        register fractpel *icxP,*icyP;  /* fixed point coefficients to set    */
00585        register fractpel (**fcnP)();  /* pointer to function to set          */
00586 {
00587        register fractpel imax;  /* maximum of cx and cy                      */
00588  
00589        *icxP = cx;
00590        *icyP = cy;
00591  
00592        if (cx != (float) (*icxP) || cy != (float) (*icyP)) {
00593 /*
00594 At this point we know our integer approximations of the coefficients
00595 are not exact.  However, we will still use them if the maximum
00596 coefficient will not fit in a 'fractpel'.   Of course, we have little
00597 choice at that point, but we haven't lost that much precision by
00598 staying with integer arithmetic.  We have enough significant digits
00599 so that
00600 any error we introduce is less than one part in 2:sup/16/.
00601 */
00602  
00603                imax = TYPE1_MAX(TYPE1_ABS(*icxP), TYPE1_ABS(*icyP));
00604                if (imax < (fractpel) (1<<(FRACTBITS-1)) ) {
00605 /*
00606 At this point we know our integer approximations just do not have
00607 enough significant digits for accuracy.  We will add FRACTBITS
00608 significant digits to the coefficients (by multiplying them by
00609 1<<FRACTBITS) and go to the "FP" form of the functions.  First, we
00610 check to see if we have ANY significant digits at all (that is, if
00611 imax == 0).  If we don't, we suspect that adding FRACTBITS digits
00612 won't help, so we punt the whole thing.
00613 */
00614                        if (imax == 0) {
00615                                *fcnP = NULL;
00616                                return(0);
00617                        }
00618                        cx *= FRACTFLOAT;
00619                        cy *= FRACTFLOAT;
00620                        *icxP = cx;
00621                        *icyP = cy;
00622                        *fcnP = FPXYboth;
00623                }
00624                else
00625                        *fcnP = IXYboth;
00626        }
00627        else
00628                *fcnP = IXYboth;
00629 /*
00630 Now we check for special cases where one coefficient is zero (after
00631 integer conversion):
00632 */
00633        if (*icxP == 0)
00634                *fcnP = (*fcnP == FPXYboth) ? FPYonly : IYonly;
00635        else if (*icyP == 0)
00636                *fcnP = (*fcnP == FPXYboth) ? FPXonly : IXonly;
00637        return(0);
00638        
00639 }
00640 /*
00641 :h3.UnConvert() - Find User Coordinates From FractPoints
00642  
00643 The interesting thing with this routine is that we avoid calculating
00644 the matrix inverse of the device transformation until we really need
00645 it, which is to say, until this routine is called for the first time
00646 with a given coordinate space.
00647  
00648 We also only calculate it only once.  If the inverted matrix is valid,
00649 we don't calculate it; if not, we do.  We never expect matrices with
00650 zero determinants, so by convention, we mark the matrix is invalid by
00651 marking both X terms zero.
00652 */
00653  
00654 void UnConvert(S, pt, xp, yp)
00655        register struct XYspace *S;  /* relevant coordinate space             */
00656        register struct fractpoint *pt;  /* device coordinates                */
00657        DOUBLE *xp,*yp;       /* where to store resulting x,y                 */
00658 {
00659        DOUBLE x,y;
00660  
00661        CoerceInverse(S);
00662        x = pt->x;
00663        y = pt->y;
00664        *xp = S->tofract.inverse[0][0] * x + S->tofract.inverse[1][0] * y;
00665        *yp = S->tofract.inverse[0][1] * x + S->tofract.inverse[1][1] * y;
00666 }
00667  
00668 /*
00669 :h2.Transformations
00670 */
00671 /*
00672 :h3 id=xform.Xform() - Transform Object in X and Y
00673  
00674 TYPE1IMAGER wants transformations of objects like paths to be identical
00675 to transformations of spaces.  For example, if you scale a line(1,1)
00676 by 10 it should yield the same result as generating the line(1,1) in
00677 a coordinate space that has been scaled by 10.
00678  
00679 We handle fonts by storing the accumulated transform, for example, SR
00680 (accumulating on the right).  Then when we map the font through space TD,
00681 for example, we multiply the accumulated font transform on the left by
00682 the space transform on the right, yielding SRTD in this case.  We will
00683 get the same result if we did S, then R, then T on the space and mapping
00684 an unmodified font through that space.
00685 */
00686  
00687 struct xobject *t1_Xform(obj, M)
00688        register struct xobject *obj;  /* object to transform                 */
00689        register DOUBLE M[2][2];    /* transformation matrix                  */
00690 {
00691        if (obj == NULL)
00692                return(NULL);
00693  
00694        if (obj->type == FONTTYPE) {
00695                register struct font *F = (struct font *) obj;
00696  
00697                F = UniqueFont(F);
00698                return((struct xobject*)F);
00699        }
00700        if (obj->type == PICTURETYPE) {
00701 /*
00702 In the case of a picture, we choose both to update the picture's
00703 transformation matrix and keep the handles up to date.
00704 */
00705                register struct picture *P = (struct picture *) obj;
00706                register struct segment *handles;  /* temporary path to transform handles */
00707  
00708                P = UniquePicture(P);
00709                handles = PathSegment(LINETYPE, P->origin.x, P->origin.y);
00710                handles = Join(handles,
00711                               PathSegment(LINETYPE, P->ending.x, P->ending.y) );
00712                handles = (struct segment *)Xform((struct xobject *) handles, M);
00713                P->origin = handles->dest;
00714                P->ending = handles->link->dest;
00715                KillPath(handles);
00716                return((struct xobject *)P);
00717        }
00718  
00719        if (ISPATHTYPE(obj->type)) {
00720                struct XYspace pseudo;  /* local temporary space              */
00721                PseudoSpace(&pseudo, M);
00722                return((struct xobject *) PathTransform(obj, &pseudo));
00723        }
00724  
00725  
00726        if (obj->type == SPACETYPE) {
00727                register struct XYspace *S = (struct XYspace *) obj;
00728  
00729 /* replaced ISPERMANENT(S->flag) with S->references > 1 3-26-91 PNM */
00730                if (S->references > 1)
00731                        S = CopySpace(S);
00732                else
00733                        S->ID = NEXTID;
00734  
00735                MatrixMultiply(S->tofract.normal, M, S->tofract.normal);
00736                /*
00737                * mark inverted matrix invalid:
00738                */
00739                S->flag &= ~HASINVERSE(ON);
00740  
00741                FillOutFcns(S);
00742                return((struct xobject *) S);
00743        }
00744  
00745        return(ArgErr("Untransformable object", obj, obj));
00746 }
00747  
00748 /*
00749 :h3.Transform() - Transform an Object
00750  
00751 This is the external user's entry point.
00752 */
00753 struct xobject *t1_Transform(obj, cxx, cyx, cxy, cyy)
00754        struct xobject *obj;
00755        DOUBLE cxx,cyx,cxy,cyy;  /* 2x2 transform matrix elements in row order */
00756 {
00757        DOUBLE M[2][2];
00758  
00759        IfTrace1((MustTraceCalls),"Transform(%p,", obj);
00760        IfTrace4((MustTraceCalls)," %f %f %f %f)\n", cxx, cyx, cxy, cyy);
00761  
00762        M[0][0] = cxx;
00763        M[0][1] = cyx;
00764        M[1][0] = cxy;
00765        M[1][1] = cyy;
00766        ConsiderContext(obj, M);
00767        return(Xform(obj, M));
00768 }
00769 /*
00770 :h3.Scale() - Special Case of Transform()
00771  
00772 This is a user operator.
00773 */
00774  
00775 struct xobject *t1_Scale(obj, sx, sy)
00776        struct xobject *obj;  /* object to scale                              */
00777        DOUBLE sx,sy;         /* scale factors in x and y                     */
00778 {
00779        DOUBLE M[2][2];
00780        IfTrace3((MustTraceCalls),"Scale(%p, %f, %f)\n", obj, sx, sy);
00781        M[0][0] = sx;
00782        M[1][1] = sy;
00783        M[1][0] = M[0][1] = 0.0;
00784        ConsiderContext(obj, M);
00785        return(Xform(obj, M));
00786 }
00787  
00788 /*
00789 :h3 id=rotate.Rotate() - Special Case of Transform()
00790  
00791 We special-case different settings of 'degrees' for performance
00792 and accuracy within the DegreeSin() and DegreeCos() routines themselves.
00793 */
00794  
00795 #ifdef notdef
00796 struct xobject *xiRotate(obj, degrees)
00797        struct xobject *obj;  /* object to be transformed                     */
00798        DOUBLE degrees;       /* degrees of COUNTER-clockwise rotation        */
00799 {
00800        DOUBLE M[2][2];
00801  
00802  
00803        IfTrace2((MustTraceCalls),"Rotate(%z, %f)\n", obj, &degrees);
00804  
00805        M[0][0] = M[1][1] = DegreeCos(degrees);
00806        M[1][0] = - (M[0][1] = DegreeSin(degrees));
00807        ConsiderContext(obj, M);
00808        return(Xform(obj, M));
00809 }
00810 #endif
00811  
00812 /*
00813 :h3.PseudoSpace() - Build a Coordinate Space from a Matrix
00814  
00815 Since we have built all this optimized code that, given an (x,y) and
00816 a coordinate space, yield transformed (x,y), it seems a shame not to
00817 use the same logic when we need to multiply an (x,y) by an arbitrary
00818 matrix that is not (initially) part of a coordinate space.  This
00819 subroutine takes the arbitrary matrix and builds a coordinate
00820 space, with all its nifty function pointers.
00821 */
00822  
00823 void PseudoSpace(S, M)
00824        struct XYspace *S;    /* coordinate space structure to fill out       */
00825        DOUBLE M[2][2];       /* matrix that will become 'tofract.normal'     */
00826 {
00827        S->type = SPACETYPE;
00828        S->flag = ISPERMANENT(ON) + ISIMMORTAL(ON);
00829        S->references = 2;   /* 3-26-91 added PNM  */
00830        S->tofract.normal[0][0] = M[0][0];
00831        S->tofract.normal[1][0] = M[1][0];
00832        S->tofract.normal[0][1] = M[0][1];
00833        S->tofract.normal[1][1] = M[1][1];
00834  
00835        FillOutFcns(S);
00836 }
00837  
00838 /*
00839 :h2 id=matrixa.Matrix Arithmetic
00840  
00841 Following the convention in Newman and Sproull, :hp1/Interactive
00842 Computer Graphics/,
00843 matrices are organized:
00844 :xmp.
00845        | cxx   cyx |
00846        | cxy   cyy |
00847 :exmp.
00848 A point is horizontal, for example:
00849 :xmp.
00850        [ x y ]
00851 :exmp.
00852 This means that:
00853 :formula/x prime = cxx times x + cxy times y/
00854 :formula/y prime = cyx times x + cyy times y/
00855 I've seen the other convention, where transform matrices are
00856 transposed, equally often in the literature.
00857 */
00858  
00859 /*
00860 :h3.MatrixMultiply() - Implements Multiplication of Two Matrices
00861  
00862 Implements matrix multiplication, A * B = C.
00863  
00864 To remind myself, matrix multiplication goes rows of A times columns
00865 of B.
00866 The output matrix may be the same as one of the input matrices.
00867 */
00868 void MatrixMultiply(A, B, C)
00869        register DOUBLE A[2][2],B[2][2];  /* input matrices                   */
00870        register DOUBLE C[2][2];    /* output matrix                          */
00871 {
00872        register DOUBLE txx,txy,tyx,tyy;
00873  
00874        txx = A[0][0] * B[0][0] + A[0][1] * B[1][0];
00875        txy = A[1][0] * B[0][0] + A[1][1] * B[1][0];
00876        tyx = A[0][0] * B[0][1] + A[0][1] * B[1][1];
00877        tyy = A[1][0] * B[0][1] + A[1][1] * B[1][1];
00878  
00879        C[0][0] = txx;
00880        C[1][0] = txy;
00881        C[0][1] = tyx;
00882        C[1][1] = tyy;
00883 }
00884 /*
00885 :h3.MatrixInvert() - Invert a Matrix
00886  
00887 My reference for matrix inversion was :hp1/Elementary Linear Algebra/
00888 by Paul C. Shields, Worth Publishers, Inc., 1968.
00889 */
00890 void MatrixInvert(M, Mprime)
00891        DOUBLE M[2][2];       /* input matrix                                 */
00892        DOUBLE Mprime[2][2];    /* output inverted matrix                     */
00893 {
00894        register DOUBLE D;    /* determinant of matrix M                      */
00895        register DOUBLE txx,txy,tyx,tyy;
00896  
00897        txx = M[0][0];
00898        txy = M[1][0];
00899        tyx = M[0][1];
00900        tyy = M[1][1];
00901  
00902        D = M[1][1] * M[0][0] - M[1][0] * M[0][1];
00903        if (D == 0.0)
00904                abort("MatrixInvert:  can't", 47);
00905  
00906        Mprime[0][0] = tyy / D;
00907        Mprime[1][0] = -txy / D;
00908        Mprime[0][1] = -tyx / D;
00909        Mprime[1][1] = txx / D;
00910 }
00911 /*
00912 :h2.Initialization, Queries, and Debug
00913 */
00914 /*
00915 :h3.InitSpaces() - Initialize Constant Spaces
00916  
00917 For compatibility, we initialize a coordinate space called USER which
00918 maps 72nds of an inch to pels on the default device.
00919 */
00920  
00921 struct XYspace *USER = &identity;
00922  
00923 void InitSpaces()
00924 {
00925   /* extern char *DEFAULTDEVICE; */
00926  
00927        IDENTITY->type = SPACETYPE;
00928        FillOutFcns(IDENTITY);
00929  
00930        contexts[NULLCONTEXT].normal[1][0]
00931              = contexts[NULLCONTEXT].normal[0][1]
00932              = contexts[NULLCONTEXT].inverse[1][0]
00933              = contexts[NULLCONTEXT].inverse[0][1] = 0.0;
00934        contexts[NULLCONTEXT].normal[0][0]
00935              = contexts[NULLCONTEXT].normal[1][1]
00936              = contexts[NULLCONTEXT].inverse[0][0]
00937              = contexts[NULLCONTEXT].inverse[1][1] = 1.0;
00938  
00939        USER->flag |= ISIMMORTAL(ON);
00940        CoerceInverse(USER);
00941 }
00942 /*
00943 :h3.QuerySpace() - Returns the Transformation Matrix of a Space
00944  
00945 Since the tofract matrix of an XYspace includes the scale factor
00946 necessary to produce fractpel results (i.e., FRACTFLOAT), this
00947 must be taken out before we return the matrix to the user.  Fortunately,
00948 this is simple:  just multiply by the inverse of IDENTITY!
00949 */
00950  
00951 void QuerySpace(S, cxxP, cyxP, cxyP, cyyP)
00952        register struct XYspace *S;  /* space asked about                     */
00953        register DOUBLE *cxxP,*cyxP,*cxyP,*cyyP;  /* where to put answer      */
00954 {
00955        DOUBLE M[2][2];       /* temp matrix to build user's answer           */
00956  
00957        if (S->type != SPACETYPE) {
00958                ArgErr("QuerySpace: not a space", S, NULL);
00959                return;
00960        }
00961        MatrixMultiply(S->tofract.normal, IDENTITY->tofract.inverse, M);
00962        *cxxP = M[0][0];
00963        *cxyP = M[1][0];
00964        *cyxP = M[0][1];
00965        *cyyP = M[1][1];
00966 }
00967  
00968 /*
00969 :h3.FormatFP() - Format a Fixed Point Pel
00970  
00971 We format the pel as "dddd.XXXX", where XX's are hexidecimal digits,
00972 and the dd's are decimal digits.  This might be a little confusing
00973 mixing hexidecimal and decimal like that, but it is convenient
00974 to use for debug.
00975  
00976 We make sure we have N (FRACTBITS/4) digits past the decimal point.
00977 */
00978 #define  FRACTMASK   ((1<<FRACTBITS)-1)  /* mask for fractional part         */
00979  
00980 void FormatFP(string, fpel)
00981        register char *string;  /* output string                              */
00982        register fractpel fpel; /* fractional pel input                       */
00983 {
00984        char temp[8];
00985        register char *s;
00986        register char *sign;
00987  
00988        if (fpel < 0) {
00989                sign = "-";
00990                fpel = -fpel;
00991        }
00992        else
00993                sign = "";
00994  
00995        sprintf(temp, "000%x", fpel & FRACTMASK);
00996        s = temp + strlen(temp) - (FRACTBITS/4);
00997  
00998        sprintf(string, "%s%d.%sx", sign, fpel >> FRACTBITS, s);
00999 }
01000  
01001 /*
01002 :h3.DumpSpace() - Display a Coordinate Space
01003 */
01004 /*ARGSUSED*/
01005 void DumpSpace(S)
01006        register struct XYspace *S;
01007 {
01008        IfTrace4(TRUE,"--Coordinate space at %p,ID=%d,convert=%p,iconvert=%p\n",
01009                    S, S->ID, S->convert, S->iconvert);
01010        IfTrace2(TRUE,"             |  %12.3f  %12.3f  |",
01011                    S->tofract.normal[0][0], S->tofract.normal[0][1]);
01012        IfTrace2(TRUE,"   [  %d  %d ]\n", S->itofract[0][0], S->itofract[0][1]);
01013        IfTrace2(TRUE,"             |  %12.3f  %12.3f  |",
01014                    S->tofract.normal[1][0], S->tofract.normal[1][1]);
01015        IfTrace2(TRUE,"   [  %d  %d ]\n", S->itofract[1][0], S->itofract[1][1]);
01016 }