Full Screen Rotation and Scaling
The Algorithm
This isn't really anything exciting, but it's a very simple approach to full screen image rotation and scaling. Simple and slow.
The algorithm used is just a simple reverse transformation. Basically what I do is run from the upper left hand corner of the DESTINATION buffer, figure out which pixel to pull from the source image, and put it there. Nothing to it. The way I find out where to grab the pixel from is like this:
To scale the image I simply multiply the x' and y' by the scaleRatio.
The Speed -- Lack of?
Ok, so speed isn't really a good word to use here. But if I were to use floating point it would be a heck of a lot slower than it is now. The ways I sped this thing up was by using lookup tables and fixed point math. The tables I made are:
long sinTab[256]; // sin table -- 256 degrees in a circle, not 360 :)
long cosTab[256]; // cosin table
int yTab[200]; // Y offset table. So I don't have to multiply the
// y value by 320. Very minor speed increase.
long scaleTab[128]; // Starting at 0, the largest, and ending at 127
// the smallest. 63 is the original size. This
// table is just something I made to increase the
// speed of scaling. You can adjust it to be as
// big as you want.sinTab, cosTab, and scaleTab are all fixed point numbers. I calculate them by taking the floating point number and multiplying it by 1024. When I put them to use I simply shift them to the right 10 places, which in effect, divides by 1024, but is much faster. I suppose you could use greater precision if you wanted, but for this program it's not necessary.
sinTab/cosTab:
int i;
for (i=0; i<256; i++) {
cosTab[i] = cos((6.28/256)*i)*1024;
sinTab[i] = sin((6.28/256)*i)*1024;
}What we're doing here is looping from 0 to 255 and calculating the (co)sin for each value. We use radians because that's what Borland C++ 3.1's math functions provide us with. By dividing 6.28 by 256 we make it possible to make a complete circle with only 256 "degrees."
We then multiply the (co)sin by 1024 and assign it to a long. This is what makes our fixed point number. When we use these values in the future we will divide our RESULT by 1024. Ie:
These are both correct:
(5*cosTab[14])/1024; or (5*cosTab[14])>>10;This is not:
5*(cosTab[14]/1024) or 5*(cosTab[14]>>10);Here's why:
If you divide cosTab[14] by 1024 before multiplying it then you lose your precision thus making fixed point numbers pretty much useless. But if you multiply the number by 5, then devide by 1024 you will get a precise number.
Now that we've gotten that down we can move on to the next part.
scaleTab:
int i;
float scale;
scale = 1.0/64.0;
for (i=0; i<128; i++) {
scaleTab[i] = scale*1024;
scale += 1.0/64.0;
}Ok, this is something that I made up and is definitely not the only (or the best) way to do this. All this is, is a table of scaling factors with the biggest starting at index 0, the smallest at 127, an the original size at 63.
I'm not really gonna explain this too much because it's really pretty dumb. But it does the trick. If you want to make your own scaling factors it shouldn't be too difficult to figure out. You could easily remove the code for scaling from "fullrot.c" by replacing:
xT = ((((x*c)>>10)-ys)*scaleTab[scale])>>10;
yT = ((((x*s)>>10)+yc)*scaleTab[scale])>>10;with:
xT = ((x*c)>>10)-ys;
yT = ((x*s)>>10)+yc;You'll actually get a small speed increase by doing this too. I personally suggest playing around with it until you understand it. It's very simple.
Compiling
To compile this program you may have to modify the Makefile that I've included to locate your include/lib directories properly. You must have Borland C++ 3.1 or greater and TASM 3.1 or greater. I use the -B option which will allow bcc to compile to an ASM file then call TASM 3.1 to assemble it. The reason I do this is because bcc doesn't understand 386 specific assembly instructions which I use for the screen blit. Beyond that there should be no difficulties. I'm sorry to all you Watcom 9.5, Symantech, or MS C folks out there but there's not a whole lot I can do since I don't own anything other than BC++ 3.1.
Credits
- The palette manipulation code in "gfxpal.c" was originally written by Mark Morley. I've made quite a few alterations to it to fit my needs, but it was originally done by Mark. It was pulled from the VGL library that he created.
You can find VGL20.ZIP at suncad.camosun.bc.ca in /pub/morley.
- The pcx loader was originally written by Christopher Lampton, author of "Flights of Fantasy", published by Waite Group Press.
The ISBN for "Flights of Fantasy" is 1-878739-18-2.
Me, Myself, and I
I am Scott Deming. A starving programmer looking for a career in game dev. So far I haven't had much luck, but I suppose you can't expect things to be given to you on a silver platter now can you? :)
Anyways, I can be reached via any of the following:
Internet: sad@umcc.umich.edu
CIS: 73053,3347
Snail: 14985 Brookview Dr., Apt #201. Riverview, MI 48192
If this documentation (if you can call it that) doesn't explain things very well, then feel free to drop me email. I will try to answer any questions I get. If my response isn't instant then I apologize, but I will respond.
=========
This source code is Copyright 1994, by Scott A. Deming. All Rights Reserved! Permission is granted to anyone who wishes to use it as a learning tool, for profit, or not-for profit. I don't care how you use it, but I would like to know about anyone it helps. Please drop me a line one way or another. It's always nice to hear from people who have actually gotten something out of what I've written.
=========
Last modified: 3-15-94
Enjoy!
P.S.
A little note about "test.pcx"
This is a logo that I created for a company that I am a partner (one of two) of. Currently we have nothing published because we have nothing finished. Someday maybe we will. Someday maybe we won't. If there is anyone out there looking for artwork for their games, or programming please drop me a line. I'm desperatly seeking work. My other partner is a very good artist, and I'm an ok programmer. Thanks for listening.
Scott A. Deming
sad@umcc.umich.edu
FULLROT.C
// Full Screen Rotation
// ====================
// Written using Borland C++ v3.1 and TASM 3.1.
//
// This code demonstrates a number of things.
// - Full screen image rotation/scaling using a reverse transformation
// algorithm.
// - Simple fixed point math.
// - Loading 320X200X256 PCX files.
// - Palette manipulation.
// - How to get into a square aspect ratio, in 320X200X256 CHAINED mode.
//
// I did this as an experiment to see how fast I could make it fly. It's a
// shame that I couldn't get it to go any faster.
//
// How I can be reached:
//
// Internet: sad@umcc.umich.edu
// CIS: 73053,3347
// Snail: 14985 Brookview Dr., Apt. #201
// Riverview, MI 48192
//
// =============================================================================
// This source code is Copyright 1994, by Scott A. Deming. All Rights Reserved!
// Permission is granted to anyone who wishes to use it as a learning tool, for
// profit, or not-for profit. I don't care how you use it, but I would like to
// know about anyone it helps. Please drop me a line one way or another. It's
// always nice to hear from people who have actually gotten something out of
// what I've written.
// =============================================================================
//
// Scott A. Deming
// sad@umcc.umich.edu
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <alloc.h>
#include <memory.h>
#include <dos.h>
#include "gfxpal.h"
#include "gfxpcx.h"
#include "gfxmath.h"
char palette[768];
char *vgaScreen = MK_FP(0xA000, 0x0000);
void gfxSetMode(int mode)
{
// Set screen mode by calling interrupt 0x10
asm {
mov ax, mode
int 0x10
}
}
void gfxExtendMode(void)
{
// Square aspect ratio.
outportb(0x3C2, 0xE3);
}
void gfxRotateFullScreenImage(char *image, char *screen, int angle, int scale)
{
long c, s;
int ys, yc;
int x, y;
int xT, yT;
// Since we're using a "reverse" transformation, we should adjust the angle
// accordingly. So the angle is actually 255-angle.
c = cosTab[255-angle];
s = sinTab[255-angle];
// The main loop will loop from -100(y) to 100(y) and -160(x) to 160(x) so
// we rotate around the center of the screen. This, in effect, places 0,0
// at the center of the screen.
for (y=-100; y<100; y++) {
// We want to calculate sin(y) and cos(y) outside of the X loop. There
// isn't any reason to do it more than once per screen row.
ys = (y*s>>10);
yc = (y*c>>10);
for (x=-160; x<160; x++) {
// x' = cos(x)-sin(y) * scaleRatio;
xT = ((((x*c)>>10)-ys)*scaleTab[scale])>>10;
// y' = sin(x)+cos(y) * scaleRatio;
yT = ((((x*s)>>10)+yc)*scaleTab[scale])>>10;
// Simple clipping goes here. We don't want a bunch of garbage on
// the screen do we?
if (xT>-160 && xT < 160 && yT > -100 && yT < 100) {
screen[(x+160)+yTab[(y+100)]] = image[(xT+160)+yTab[yT+100]];
}
}
}
}
int main()
{
int angle = 0;
int aDir = 1;
int scale = 0;
int sDir = 1;
char *scrImage;
char *screen;
// Allocate/Initialize screen buffer memory.
screen = malloc(64000U);
if (screen == NULL) {
printf("Error allocating screen memory.\n");
return (0);
}
memset(screen, 0, 64000U);
// Initialize fixed point sin/cos/scale/Y tables. -- See gfxmath.c
gfxInitTables();
// Set video mode to graphics mode 320X200X256
gfxSetMode(0x13);
// Set square aspect ratio.
gfxExtendMode();
// Load in our test.pcx image. -- See gfxpcx.c
scrImage = gfxLoadPCX("test.pcx", scrImage, palette);
// Set the palette to that in our test.pcx file. -- See gfxpal.c
gfxSetPalette(0, 256, palette);
// Display the image and wait for a keypress before beginning, clear screen.
memcpy(vgaScreen, scrImage, 64000U);
getch();
memset(vgaScreen, 0, 64000U);
// Loop. Rotate/Scale the image over and over again until a key is pressed.
while (!kbhit()) {
// Rotate/Scale the image into a buffer. Makes for smoother animation.
gfxRotateFullScreenImage(scrImage, screen, angle, scale);
asm {
push ds // Save ds.
cld // Clear direction flag.
// Move the image to the screen quickly using a 32 bit blit.
les di, vgaScreen // Load vgaScreen into [es:di].
lds si, screen // Load screen into [ds:si].
mov ecx, 16000 // 64000/4 bytes [4 byte (32 bit) movs].
rep movsd // 32 bit movs.
// Clear the screen buffer
les di, screen // Load screen into [es:di].
mov ecx, 16000 // 64000/4 bytes [4 byte (32 bit) stos].
xor eax, eax // Set clear color to 0.
rep stosd // 32 bit stos.
pop ds // restore ds.
}
// Adjust rotation.
angle+=aDir;
if (angle>=255) {
aDir = -1;
} else
if (angle<1) {
aDir = 1;
}
// Adjust scaling.
scale+=sDir;
if (scale>=127) {
sDir = -1;
} else
if (scale<1) {
sDir = 1;
}
}
// Pull the keystroke from the keyboard buffer.
getch();
// Return to text mode.
gfxSetMode(0x03);
// Clean up
free(scrImage);
free(screen);
// And finally return to dos.
return (0);
}GFXMATH.C
// Fixed Point Math
// ================
// This code was written 100% by me personally. It's nothing really special
// but it makes things fairly simple. It's very easy to understand and speeds
// things up tremendously compared to floating point.
//
// Scott A. Deming
// sad@umcc.umich.edu
#include <stdio.h>
#include <stdlib.h>
#include <dos.h>
#include <time.h>
#include <math.h>
#include "gfxmath.h"
long cosTab[256];
long sinTab[256];
int yTab[200];
long scaleTab[128];
void gfxInitTables()
{
int i;
float scale;
// Initialize (co)sin table. 256 degrees.
for (i=0; i<256; i++) {
cosTab[i] = cos((6.28/256)*i)*1024;
sinTab[i] = sin((6.28/256)*i)*1024;
}
// Initialize y offset table.
for (i=0; i<200; i++) {
yTab[i] = i*320;
}
scale = 1.0/64.0;
for (i=0; i<128; i++) {
scaleTab[i] = scale*1024;
scale += 1.0/64.0;
}
}GFXMATH.H
#ifndef _gfxtable_h_
#define _gfxtable_h_
#define FIXEDSHIFT 10
#define FIXEDAND 2047
#define ABS(a) ((a < 0) ? -a : a)
#define SGN(a) ((a < 0) ? -1 : 1)
extern long cosTab[256];
extern long sinTab[256];
extern int yTab[200];
extern long scaleTab[128];
void gfxInitTables(void);
#endifGFXPAL.C
// Palette
// =======
// The code here was taken from Mark Morely's VGL library. Thank you Mark for
// placing it in the Public Domain. It's helped me out a lot. :)
//
// I've made some changes to this code for my own personal benefits. If you
// would like to real thing you can obtain it via FTP at suncad.camosun.bc.ca
// in the /pub/morley directory. The file is named VGL20.ZIP.
//
// Scott A. Deming
// sad@umcc.umich.edu
#include <stdio.h>
#include <stdlib.h>
#include <dos.h>
#include <mem.h>
#include "gfxpal.h"
char gfxPalette[768];
void gfxSetPalette(int first, int number, char *palette)
{
int i;
if (number < first) {
return;
}
outp(0x03c8, first);
i = 0;
do {
outp(0x03c9, palette[i++]);
outp(0x03c9, palette[i++]);
outp(0x03c9, palette[i++]);
first++;
} while (first < number);
}
void gfxLoadPalette(char *palFName, char *palette)
{
FILE *pFile;
char palFilename[69];
sprintf(palFilename, "%s", palFName);
pFile = fopen(palFilename, "rb");
if (pFile == 0) {
return;
}
if (fread(palette, 1, 768, pFile) == 768) {
gfxSetPalette(0, 255, palette);
}
fclose(pFile);
}
void gfxSavePalette(char *palFile, char *palette)
{
FILE *pFile;
pFile = fopen(palFile, "wb");
if (pFile == 0) {
return;
}
fwrite(palette, 1, 768, pFile);
fclose(pFile);
}
void gfxBlackPalette(char *palette)
{
memset(palette, 0, 768 );
gfxSetPalette(0, 255, palette);
}
void gfxFadeIn(int first, int number, char *palette)
{
int i, j;
for (i=0; i<32; i++) {
for (j=0; j<number*3; j++) {
gfxPalette[j+first] = (i * (unsigned)palette[j]) >> 5;
}
gfxSetPalette(first, number, gfxPalette);
}
}
void gfxFadeOut(int first, int number, char *palette)
{
int i, j;
for (i=31; i>=0; i--) {
for (j=0; j<number*3; j++) {
gfxPalette[j+first] = (i * (unsigned)palette[j]) >> 5;
}
gfxSetPalette(first, number, gfxPalette);
}
}
void gfxCycleLeft(int first, int number, char far *palette)
{
char tmp[3];
tmp[0] = palette[first*3];
tmp[1] = palette[first*3+1];
tmp[2] = palette[first*3+2];
memmove(palette+(first*3), palette+((first+1)*3), number*3);
palette[(first+number)*3] = tmp[0];
palette[(first+number)*3+1] = tmp[1];
palette[(first+number)*3+2] = tmp[2];
gfxSetPalette(0, 255, palette);
}
void gfxCycleRight(int first, int number, char *palette)
{
char tmp[3];
tmp[0] = palette[(first+number)*3];
tmp[1] = palette[(first+number)*3+1];
tmp[2] = palette[(first+number)*3+2];
memmove(palette+((first+1)*3), palette+(first*3), number*3);
palette[first*3] = tmp[0];
palette[first*3+1] = tmp[1];
palette[first*3+2] = tmp[2];
gfxSetPalette(0, 255, palette);
}GFXPAL.H
#ifndef _gfxpal_h_
#define _gfxpal_h_
extern char gfxPalette[768];
void gfxSetPalette(int first, int number, char *palette);
void gfxLoadPalette(char *palFName, char *palette);
void gfxSavePalette(char *palFile, char *palette);
void gfxBlackPalette(char *palette);
void gfxFadeIn(int first, int number, char *palette);
void gfxFadeOut(int first, int number, char *palette);
void gfxCycleLeft(int first, int number, char far *palette);
void gfxCycleRight(int first, int number, char *palette);
#endifGFXPCX.C
// PCX Image Loading.
// ==================
// This code was taken from Flights Of Fantasy and reworded to fit my style.
// Flights Of Fantasy is a great book written by Christopher Lampton and
// published by Waite Group Press. The ISBN is 1-878739-18-2.
//
// A couple of very minor adjustments have been made to this code. Basically
// to fit my coding style.
//
// Scott A. Deming
// sad@umcc.umich.edu
#include <stdio.h>
#include <stdlib.h>
#include <dos.h>
#include "gfxpcx.h"
#define BYTEMODE 0
#define RUNMODE 1
#define BUFFERSIZE 1024*5
struct pcxHeaderS {
char manufacturer;
char version;
char encoding;
char bitsPerPixel;
int xMin, yMin;
int xMax, yMax;
int hRes, vRes;
char pal16[48];
char reserverd;
char colorPlanes;
int bytesPerLine;
int paletteType;
char filler[58];
};
char *gfxLoadPCX(char *pcxFName, char *image, char *palette)
{
struct pcxHeaderS pcxHeader;
FILE *pcxFile;
int mode = BYTEMODE;
int bRead = 0;
int bufPtr = 0;
long i;
unsigned char *buffer;
unsigned char outByte;
unsigned char byteCount;
char *scr;
char pcxFilename[69];
sprintf(pcxFilename, "%s", pcxFName);
// Open PCX file.
pcxFile = fopen(pcxFilename, "rb");
if (pcxFile == NULL) {
return (NULL);
}
// Read PCX file header.
fseek(pcxFile, 0L, SEEK_SET);
fread(&pcxHeader, sizeof(struct pcxHeaderS), 1, pcxFile);
// Make sure this is a 256 color PCX file.
if (pcxHeader.bitsPerPixel != 8) {
return (NULL);
}
// Is this going to the screen, or a buffer? If a buffer we need to
// allocate some memory.
if (image != MK_FP(0xA000, 0x0000)) {
image = malloc(64000U);
}
scr = image;
buffer = malloc(BUFFERSIZE);
// Load and uncompress image.
for (i=0L; i<64000L; i++) {
if (mode == BYTEMODE) {
if (bufPtr >= bRead) {
bufPtr = 0;
if ((bRead = fread(buffer, 1, BUFFERSIZE, pcxFile)) == 0) {
break;
}
}
outByte = buffer[bufPtr++];
if (outByte > 0xBF) {
byteCount = (int) ((int) outByte & 0x3F);
if (bufPtr >= bRead) {
bufPtr = 0;
if ((bRead = fread(buffer, 1, BUFFERSIZE, pcxFile)) == 0) {
break;
}
}
outByte = buffer[bufPtr++];
if (--byteCount > 0) {
mode = RUNMODE;
}
}
} else
if (--byteCount == 0) {
mode = BYTEMODE;
}
*scr++=outByte;
}
// Load palette
if (palette != NULL) {
fseek(pcxFile, -768L, SEEK_END);
fread(palette, 1, 768, pcxFile);
for (i=0; i<768; i++) {
palette[i]>>=2;
}
}
free(buffer);
return (image);
}GFXPCX.H
#ifndef _gfxpcx_h_
#define _gfxpcx_h_
char *gfxLoadPCX(char *pcxFName, char *image, char *palette);
#endif
