From: krisr@cue.bc.ca (Kristof Roomp)
Subject: Bitmap rotation & scaling solution
Summary: How to use a linear xfrom to rotate & scale bitmaps
Keywords: graphics bitmap
Organization: Softwords Research International Ltd., Victoria, B.C., Canada
Date: 19 Nov 92 19:07:01 GMT


hey guys!
while dreaming my way through linear algebra, I suddenly realized that
linear transformations could be quite handy in rotating, scaling, etc. of
bitmaps. here's a quicky version of my idea.... it should be possible to
make it use integer arithmetic with little trouble (ie. a LOT faster). I
just wanted to make clear what the program was doing...
 
here ya go...
 
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. resu 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,
get->xsize/2,target->ysize/2,&m);
        // transform source to target (origin is at the center of both
        //      bitmaps
 
     // continue program...
     }

thats it... see if you can come up with some clever integer arithmetic to
speed up the process...