Bitmap Rotation and Scaling

Intro

I first saw this type of display with the Unreal demo by Future Crew. I was awe struck by how they could display hundreds of little copies of the same bitmap and do it so fast! Since then I’ve learned a thing or two, and it really wasn’t THAT much of an accomplishment. I decided to break my vow of silence and share with you how it was done. I had theorized how I would do it, and amazingly it was very similiar to the method layed out in More Tricks of the Game programming Gurus, so I’ll just cover their routine instead.

The Code

This version is the easier to read because it doesn’t use fixed point math, and no lookup tables. Basically, when we go to display a picture, we progress from left to right and top to bottom. What if we modified this behavior so that we were progressing at a tilted angle? When it comes down to it, that is all we are doing! Look at the picture on the right. Notice that when we rotate the bitmap by angle Theta, we get two equal triangles. The dU and dV for each triangle correspond to the opposite dU and dV for the other triangle. We will modify our normal vectors by du and dv to attain bitmap rotation. Without further delay, here’s the code!

void Bitmap::RotateAndScale(float angle,float scale)
{
	long u,v,rowU,rowV,startingU,startingV;
	long duCol,dvCol,duRow,dvRow;
	long x,y;
	char* dest=vid->video_screen;

	startingU=32<<16;
	startingV=32<<16;

	duCol=(long)(math->SinRaw(angle+90)*scale*0x10000);
	dvCol=(long)(math->SinRaw(angle)*scale*0x10000);

	duRow=-dvCol;
	dvRow= duCol;

	startingU-=vid->XCenter*duCol+vid->YCenter*duRow;
	startingV-=vid->XCenter*dvCol+vid->YCenter*dvRow;
	rowU=startingU;
	rowV=startingV;
	for(long y=0;yScreen_Height;y++)
	{
		u=rowU;
		v=rowV;
		for(long x=0;xScreen_Width;x++)
		{
			*dest++ = Bmp[(u>>16&63)+(v>>16&63)*f.Width];
		 	u+=duCol;
		 	v+=dvCol;
		}
		rowU+=duRow;
		rowV+=dvRow;
	}
}

We first declare a whole crapload of long variables that we will be needing. Notice that we don’t declare ANY float types. That is because we will be using the usual 16:16 fixed point math. We first set our dest pointer to the location of video ram. We then set startingU and startingV to the middle of the bitmap, assuming that it is 64×64. In order for our bitmap to tile, it must be a factor of 2 (32,64,128,256,512,1024) you’ll see why later on. Also notice to make our startingU and startingV variables fixed point we can either multiply by 0×10000 or shift them left 16 bits. We calculate our duCol and dvCol variables by using the sin(theta) and sin(theta+90). We multiply them by our scale factor to get our scaling. Since we are dealing with a double or float type in the multiplication, we multiply by 0×10000 to get duCol and dvCol into fixed point form. Remember how the dV and dU of both of the triangles were equal. We use this to our advantage and set duRow equal to -dvCol and dvRow equal to duCol. The next two assignments are optional, but usually desired. We subtract startingU and startingV by an equation involving the screen’s X and Y centers. What we are acutally doing is translating the entire picture to be centered around the middle of the screen, otherwise all the rotation will be around 0,0 which looks pretty tacky!

We then dive into our routine! We initialize rowU and rowV with startingU and startingV then we proceed into a framework very similar to normal bitmap blitting. We have two for loops that proceede from top to bottom and left to right. With every y itteration we set u and v to rowU and rowV. Those are incremented by duRow and dVRow after the x loop. Inside that is where a bulk of the work is being done. We proceede left to right on the screen, we use the expression *dest++ to assign the location dest is pointing to, and it will post increment the variable with one statement. That’s a lot easier than the expression dest[y*vid->Screen_Height+x]=?. We index our the array holding our bitmap (Bmp) with u and v. Both need to be turned back into non-fixed point to be of any use, so we shift then to the right 16 bits. We also do a logical AND with 63 to make the values wrap around, this gives us our tiling. The value 63 is simply the the width-1, this will work with any bitmap with dimensions that are a multiple of 2. We then multiply that by the bitmap width to get the correct place in the bitmap. Afterwards, we increment u and v accordingly. That’s IT!

NOTES: You will notice, especially with older computers, that the display will slow with cetain bitmap sizes, and at certain angles. Firstly, since we are moving through the bitmap in a non-linear fassion, if our bitmap doesn’t fit into the onboard cache it has to flip flop it around and this slows our routine down. Also, when the bitmap is at 0 or 180 everything goes quickly, but the frame rate will drop at 90-270 degrees, because of the way the bitmap is layed out in memory. Normally, horizontal pixels are in neighboring addresses, but this isn’t the case when we start spinning it around! With newer machines, this probably won’t even be noticed!