Introduction to 2D Linux Game Programming/Algorithms/Simple Software Transformations/Optimized Integer Scaling

Optimized Image Scaling


This takes the previous, non-optimzed version of the integer scaling program and changes a few things to make it much quicker.

The Source:

// IntegerScale.cpp

#include <iostream>
#include "include/S.h"

using namespace std;

 * This is the speed optimized version of our IntegerScale()
 * function.  Readability is a distant second to speed.
 * We pre-calculate everything we can rather than calculating
 * over and over in the inner for loops.  Where we can't
 * pre-calculate, we move the calculation as "high" up in the
 * for loop chain as we can.  We move definitions of variables
 * out of the loops so they're defined once rather than every 
 * iteration.  Instead of rebuilding a row scale times we
 * calculate it once, then copy it scale-1 times.  It is a
 * much quicker algorithm, but it's also much more difficult
 * to read or explain.  After seeing the original, unoptomized
 * scale function, it should be easier to see what this one
 * is doing.

int main()
	// All the variables that can be pre-calculated
	// and do not change in the for loops
	const int width = S::sw();         // The original Array's width
	const int height = S::sh(width);   // The original Array's height
	const int scale = S::ss(width);    // How many times to scale the image
	const int s_size = width*height;   // Size of source image
	const int widthscale = width*scale;
	const int scalewidthscale = scale*widthscale;
	const int heightscale = height*scale;

	// Our source and destination arrays
	int source[s_size];     // Original Array
	int dest[scalewidthscale * height]; // Scaled Array

	// Pointers for the line we're going to copy
	int *repeat; // Address of first element of row we're copying
	int *traverserepeat; // Address of the element we're copying
	int *traversedest; // Address we're copying to in dest array

	// Setup our source "image"
	for(int x = 0; x < s_size; ++x)

	cout << "\n\n";
	S::print_rect(width, height, &source[0]);
	cout << "\n\n";

	// The following for loop iterators 
	// defined out of the for loop to 
	// avoid recreating them every time 
	// we drop out of the inner loops
	int hrepeat = 0; // height repeat
	int w = 0;       // width counter
	int wrepeat = 0; // width repeat

	// Integers we calculate as high up in the for loops
	// as possible
	int hscalewidthscale; // h * scale * width * scale
	int wscale;           // w * scale
	int hwidth;           // h * width

	for(int h = 0; h < height; ++h) // Source Height Position
		hscalewidthscale = h*scalewidthscale;

		// Set the address of the first element of the array
		// We're going to copy

		for(; hrepeat < scale; ++hrepeat) // Repeat a full row scale times
			if(hrepeat==0) // This is a new line in the source image
				for(; w < width; ++w) // Source width Offset
					wscale = w*scale;
					hwidth = h*width;
					// Repeat individual pixel scale times
					for(; wrepeat < scale; ++wrepeat)
						dest[hscalewidthscale + wscale + wrepeat] = source[ hwidth + w];

					wrepeat = 0;
				w = 0;
				// The initial element we're going to copy

				// The initial element to copy to dest[]
				for(; w < width; ++w)
					wscale = w*scale;
					for(; wrepeat < scale; ++wrepeat)
						// Copy a value into dest[]

						// Traverse the array we're
						// copying from and into
				w = 0;
		hrepeat = 0;

	cout << "\n" << endl;