Elvis lives. Or so some people have been saying in the 25 years since the reported death of the King. This momentous anniversary would have escaped my notice, had it not been brought to my attention by my spouse. And she probably wouldn't have mentioned it had she not seen some television show that provided the inspiration for this month's Challenge.

It seems some Elvis devotee had discovered a collection of rarely seen images of the Hound Dog, and constructed a portrait of the King using tiny versions of those images. I recall once having put together a jigsaw puzzle of the space shuttle similarly constructed. Viewed from a distance, the mosaic of smaller images took on the appearance of the shuttle on the launch pad, or, in the case of the television show, the swiveling hips of Mr. Love Me Tender. Having recently completed scoring our Jigsaw Puzzle challenge, the two ideas came together in my mind to form this month's Challenge.

The prototype for the code you should write is:

 

void InitMosaic(

  short numElements,  

         /* number of pixmaps from which the mosaic should be created */

  const PixMapHandle element[]

         /* element[i] is a PixMapHandle to the i-th image used to construct the mosaic */

);

 

typedef struct MosaicPiece {

  short elementIndex;

         /* index into element[] of the image used to construct this piece of the mosaic */

  Rect elementRect;

         /* which portion of element[elementIndex] was used to construct this piece */

  Rect mosaicRect;

         /* which portion of desiredImage this piece is used to construct */

         /* elementRect and mosaicRect must be the same size */

} MosaicPiece;

 

void Mosaic(

  const PixMapHandle desiredImage,

         /* PixMapHandle populated with the desired image to be constructed */

  const Rect minPieceSize,

         /* mosaic pieces must be of this size or larger */

  PixMapHandle mosaic,

         /* PixMapHandle to preallocated image in which the mosaic is to be placed */

         /* initialized to black */

  MosaicPiece *piece,

         /* pointer to array of mosaic pieces */

         /* populated by your code */

  long *numMosaicPieces

         /* number of mosaic pieces created by your code */

);

 

void TermMosaic(void);

     /* deallocate any memory allocated by InitMosaic or multiple Mosaic calls */

 

Your InitMosaic routine will be given an array of numElements images (elements) from which you will be asked to construct a sequence of mosaics. The image elements are in the form of PixMaps. InitMosaic should perform any analysis on these images that you decide would be useful in the subsequent mosaic construction.

Next, your Mosaic routine will be called multiple times. In each call, you will be given another PixMap, the image (desiredImage) you are being asked to approximate with your mosaic, along with a Rect that defines the minimum size of the pieces of the mosaic you will construct. Your task is to create an array of MosaicPieces that, when combined, form a mosaic that looks something like the desiredImage. Each MosaicPiece identifies the image element being used to create the mosaic piece, the portion (elementRect) of the image being used, and the portion (mosaicRect) of the mosaic being constructed with this piece. The mosaicRect of one piece must not overlap that of another piece. You should return the number of MosaicPieces you create in numMosaicPieces, and you should also create your mosaic image in the mosaic PixMap. Memory for the mosaic PixMap, its constituent members, and for the MosaicPieces will be preallocated.

Your TermMosaic routine will be called once for each call to InitMosaic so that you can return any dynamically allocated memory.

Scoring will be based on execution time and on how close your mosaic image resembles the desired image. For each pixel in the mosaic, I�ll calculate the root mean square distance in RGB space between the corresponding values of the mosaic and the desired image. Your raw score will be the sum of those distances over all image pixels. For each second of execution time, I�ll add a penalty of 10% to the raw score.  Execution time will include the time taken by the Mosaic routine, plus a share of the InitMosaic and TermMosaic time, divided equally among the Mosaic calls. The winner will be the correct solution with the lowest score.

This will be a native PowerPC Carbon C++ Challenge, using the Metrowerks CodeWarrior Pro 7.0 development environment. Please be certain that your code is carbonized, as I may evaluate this Challenge using Mac OS X.