NetNews Usenet Archive 1992 #30/NN_1992_30.iso/spool/comp/graphics/13058

Text File | 1992-12-21 | 5.4 KB | 184 lines

Xref: sparky comp.graphics:13058 rec.games.programmer:5104
Newsgroups: comp.graphics,rec.games.programmer
Path: sparky!uunet!usc!howland.reston.ans.net!sol.ctr.columbia.edu!destroyer!cs.ubc.ca!news.UVic.CA!softwords!cue!krisr
From: [e-mail] (Kristof Roomp)
Subject: Algorithm for Bitmap rotation & scaling
Message-ID: <krisr.724726801@cue>
Summary: An algorithm to scale and rotate bitmaps
Sender: [e-mail] (CNews)
Nntp-Posting-Host: cue.bc.ca
Organization: Softwords Research International Ltd., Victoria, B.C., Canada
Date: 19 Dec 92 01:00:01 GMT
Lines: 170


while dreaming my way through linear algebra, I suddenly realized that
linear transformations could be quite handy in rotating, scaling, etc. of
aps. I do have an assembler version of this if anyone is interested.
(A lot faster, as only uses integer adds between pixels).

First here's a bunch of matrix operation, just in case you don't know how
to construct you own favorate matrices. What you basically do is create
a matrix with initmatrix. If you pass this matrix to LinearTransform, it
will faithfully draw bitmap onto the screen as if no manipulatios were made.
(ie BitBlt, but a bit slower).
Now, suppose you want to rotate the bitmap. Easy... just all the rotate
procedure on the matrix you created with initmatrix. Pass it the angle
(in rads) and it will modify the matrix accordingly. You do not have the
hange the source bitmap in any way. Now just call LinearTransform with
the new matrix, and tada! the bitmap has been rotated about its center.
ou can apply as many operations on tp of each ther witno loss of acuracy
in the bitmap. When assembler is used to speed things up, you can get
Wing Commander performance (i think this is how wing commander does it
anyhow). The only problem i'm having is with the boundry points. How to quickly
skip over the pixels that are not contained in the source bitmap.
Anyhow, enough talk... here it is:

// a matrix that looks something like
// [ a b ]
/ [ c d ]

typedef struct
        {
        double a,b,c,d;
        } MATRIX22;

// initializes a transform matrix.

void initmatrix(MATRIX *m)
     {
     m->a=1; m->b=0; m->c=0; m->d=1;
     }

// multiplies two matrices. result is stored in m1.
void matrixmul(MATRIX22 *m1,MATRIX22 *m2)
     {
     MATRIX22 m3;

     m3.a=m1->a*m2->a + m1->b*m2->c;
     m3.b=m1->a*m2->b + m1->b*m2->d;
     m3.c=m1->c*m2->a + m1->d*m2->c;
     m3.d=m1->c*m2->b + m1->d*m2->d;

     *m1=m3;
     }

// scales x axis by factor
void ScaleX(MATRIX22 *m,double factor)
     {
     MATRIX22 m2;

     m2.a=factor; m2.b=0;
     m2.c=0; m2.d=1;

     matrixmul(m,&m2);
     }

// scales y axis by factor
void ScaleY(MATRIX22 *m,double factor)
     {
     MATRIX22 m2;

     m2.a=1; m2.b=0;
     m2.c=0; m2.d=factor;

     matrixmul(m,&m2);
     }

// rotates counterclockwise by angle
void Rotate(MATRIX22 *m,double angle)
     {
     MATRIX22 m2;

     m2.a=cos(angle); m2.b=-sin(angle);
     m2.c=sin(angle); m2.d=cos(angle);

     matrixmul(m,&m2);
     }

// reflects about a line through the origin of angle angle
void Reflect(MATRIX22 *m,double angle)
     {
     MATRIX22 m2;

     m2.a=cos(2*angle); m2.b=sin(2*angle);
     m2.c=sin(2*angle); m2.d=-cos(2*angle);

     matrixmul(m,&m2);
    }

// notice you can perform as many of the above transformation as you want
/ on the matrix before passing it to LinearTransform. you might rotate,
// scale, and rotate again... all done in one swoop.

// very inefficient linear transform from one bitmap to another
// lots of optimization possible, though.

#define min(a,b) ( (a<b) ? a : b )
#define max(a,b) ( (a>b) ? a : b )

void LinearTransform(HBITMAP source,HBITMAP target,int xorg,int yorg,
                int xtarg,int ytarg,MATRIX22 *m)
    {
    double a,b,c,d,ai,bi,ci,di,det;
    int x1,y1,x2,y2,x3,y3,x4,y4,minx,miny,maxx,maxy,x,y,xp,yp;

    a=m->a; b=m->b; c=m->c; d=m->d;

    det=a*d-b*c;
    if (det==0)
        Error("LinearTransform: a non-invertible transform matrix");

    ai=d/det; bi=-b/det; ci=-c/det; di=a/det;

    x1=-xorg*a + -yorg*b;
    y1=-xorg*c + -yorg*d;

    x2=(source->xsize-xorg)*a + -yorg*b;
    y2=(source->xsize-xorg)*c + -yorg*d;

    x3=-xorg*a + (source->ysize-yorg)*b;
    y3=-xorg*c + (source->ysize-yorg)*d;

    x4=(source->xsize-xorg)*a + (source->ysize-yorg)*b;
    y4=(source->xsize-xorg)*c + (source->ysize-yorg)*d;

    minx=min(x1,min(x2,min(x3,x4) ) );
    maxx=max(x1,max(x2,max(x3,x4) ) );

    miny=min(y1,min(y2,min(y3,y4) ) );
    maxy=max(y1,max(y2,max(y3,y4) ) );

    for (y=miny;y<=maxy;y++)
        {
        for(x=minx;x<=maxx;x++)
            {
            xp=x*ai + y*bi;
            yp=x*ci + y*di;
            DrawPixel(target,x+xtarg,y+ytarg,
                GetPixel(source,xp+xorg,yp+yorg));
            }
        }
    }


void main(void)
     {
     MATRIX22 m;

     // set up graphics et al.

     initmatrix(&m);
     ScaleX(&m,2);              // make x twice as big
     Rotate&m,1.04719);        // rotate bitmap by pi/3 (60 degrees)
     ScaleY(&m,2);              // make y twice as big
     Reflect(&m,0.7853);        // reflect about a line with an angle of pi/4
                                   (45 degrees)
     LinearTransform(source,target,source->xsize/2,source->ysize/2,
        target->xsize/2,target->ysize/2,&m);
        // transform source to target (origin is at the center of both
        //      bitmaps

     // continue program...
     }