/-------------------------------------\
|         MapToSpr / SprToMap         |
| Mosaic compression of bitmap images |
|       (C) Chris Bazley, 2006        |
|      Release 1 (14 Dec 2006)        |
\-------------------------------------/
N.B. This text is best viewed at a display width of 77 columns.

-----------------------------------------------------------------------------
1   Introduction
    ============

  Star Fighter 3000 is a three dimensional flying shoot-em-up game (I won't
call it a flight simulator, because it doesn't have much in the way of
physics). It was published in 1994 for 32-bit Acorn computers. In this game,
the ground is represented as an infinitely repeating flat texture map which
is 4096 by 4096 texels in size, and has a colour depth of 8 bits per texel.
You don't have to be a genius to calculate that an ordinary bitmap image of
this size would require 134,217,728 bits of memory (which happens to be
exactly 16 megabytes).

  Given that this game was designed for machines with only 2 megabytes of
memory, how was this achieved? The answer is a clever trick that was used in
many games of that era, although more commonly in those that featured a two
dimensional world. Instead of storing a single huge texture, Star Fighter
3000 uses a much smaller map that has only 256 by 256 elements. Each element
is a reference to one of up to 256 tiles. The tile graphics are stored
separately, and each one is only 16 by 16 texels in size.

  Each map location is represented by a single byte, so the memory required
for a ground map is only 524,288 bits (64 kilobytes). The game only allocates
space for up to 192 tiles rather than the theoretical maximum of 256. This
adds a modest 393,216 bits (48 kilobytes) to the total. Thus the total
memory usage has been reduced from 16,384 KB to 112 KB; a compression ratio
of almost 1:146!

  Naturally there are drawbacks to this approach: Specialised tools are
required to edit the game maps, and each set of tile graphics must be
painstakingly designed. As a compression method, it only works with images
that contain many areas of similarity (ideal for an aerial view of a
landscape, but not for complex images). On the plus side, the same map can
easily be given a new appearance by rendering it with a different set of
graphics.

  Several years ago, I became interested in the possibility of generating
Star Fighter 3000 maps automatically. I don't mean random maps, such as those
generated by Sim City 2000. I mean taking a photographic image, identifying
areas of similarity, and generating a map and associated set of tile
graphics from it. Naively, I even thought that this might even be viable
method of (lossy) image compression.

  The programs described herein allow you to do just that; decompose an image
into a mosaic of smaller tiles, from which an approximation of the original
image can then be reconstructed. The results are not as good as I had hoped;
my method certainly isn't going to supplant JPEG image compression. A
reconstructed image tends to resemble a collage of little bits of paper (did
you ever do one at school?) except at very low compression ratios.

  However you can have a bit of fun if you also have a copy of Star Fighter
3000 (and my RISC OS applications FednetCmp and SFToSpr), because you can
replace the game maps with your own pictures!

  Although I have tried to write portable code (you should be able to
compile it on any system that supports ISO 'C' 1999, the programs only
understand new-style RISC OS sprite files. This is a bitmap image format
defined in volume 5a of the RISC OS 3 programmers reference manual. I
suspect that it would not be too difficult to adapt the code to use a less
esoteric bitmap graphics format.

-----------------------------------------------------------------------------
2   SprToMap program
    ================

  This program generates a map and associated set of tile graphics from an
image file that has 8, 16 or 32 bits per pixel.

First, the image is sub-divided into a regular grid of equal-sized tiles.
The dimensions of the grid and tile size are configurable. By default, the
grid will be large enough to cover most of the image without overlapping its
edges. A narrow strip at the righthand or bottom edge may be lost if the
dimensions of the image are not an exact multiple of the tile size.

  Next, each grid location is compared with every other grid location in the
input image. Each pair of pixels in turn is compared using a weighted least-
squares function. The respective weights used for red, green and blue colour
components are 2:4:1. The pixel differences are totalled to produce a single
value that corresponds to the overall difference between the two grid
locations. The bottom 5% of the maximum possible total difference is scaled
down to the range 0 - 255 (where 255 means a difference of 5% or greater).

  Generating the table of differences is usually the slowest part of the
whole process, and can use large amounts of memory if the tile size is too
small relative to the size of the input image. To optimise access to the
difference table, a second table of indexes into the first is also created.
The total amount of memory required (in bytes) can be calculated using the
following formula, where 'w' is the width of the grid (in tiles), and 'h' is
its height:

  ((w * h) * (w * h - 1)) / 2 + w * h * 4

  It can be seen that with a tile size of 16, an image of 1024 by 768 pixels
would require 4,729,344 bytes (4.51 MB) for the difference table and table
of indexes into it. This is significantly more than is required for the
input image itself (only 3 MB, assuming it has 32 bpp).

  The next stage of the process is to reduce the number of output tiles by
identifying groups of similar grid locations. Initially, each group consists
of only one grid location. Pairs are then merged, starting with the most
similar groups (0% error). Every time a pair is merged, the difference table
is updated to reflect the changed relationship between the new super-group
and any other groups remaining. The new difference values are calculated by
weighting the old values according to how many members each sub-group had
before being incorporated in the super-group.

 The threshold at which two groups will be merged is gradually increased
until it reaches some minimum acceptable quality (less than 0.1% error,
unless otherwise specified). If no quality was specified then the merge
threshold will continue to increase until there are fewer than the maximum
allowed no. of output tiles; otherwise an error will be reported if the
requested quality results in too many output tiles.

  Next, a map with the same dimensions as the grid is created, on which to
mark the position of every member of the surviving groups. Each group is
assigned a new reference number (henceforth, the 'tile number') which is
stored in the map wherever members of that group are to be found. There are
two types of map; 'wide' maps have 2 bytes per grid location, whereas 'byte'
maps have only 1 byte per grid location. The former are more common because
they are automatically generated when there are more than 256 output tiles.

  The output tile images are produced either by copying the portion of the
input image at the 'first' grid location in each group, or by averaging the
red, green and blue colour components from every grid location in a group.
The first method is somewhat arbitrary but can produce better results if the
input image is dithered. The second method may produce a somewhat flat and
textureless tile image if differences between the members of its group
cancel each other out; such monochromaticity also tends to accentuate the
boundaries between tiles.

  Finally, the map is saved to file. Several options are provided to
facilitate generation of Star Fighter 3000 maps: The map may be flipped
vertically, so that the first row of data corresponds to the bottom of the
image rather than the top. It will also be repeated vertically and
horizontally as many times as required to cover the width and height
specified by the user (if those dimensions are larger than the grid covering
the input image).

Syntax:

*SprToMap [-verbose] [-merge] [-quality 0..100] [-tilesout <outfile>]
          [-tilesize 1..97] [-maxtiles 1..63336] [-bpp 8|16|32]
          [-mapout <outfile>] [-vflip] [-width 1..N] [-height 1..N] <infile>

Options:

-verbose            Enables display of informational messages whilst
                    processing (including percentage done).
-blend              Produce tile images by averaging similar areas of the
                    input image (default is to pick one grid location)
-quality 0..100     Controls the difference threshold below which all grid
                    locations will be merged (between 0% and 5% error;
                    default is 0.1%).
-tilesout <outfile> Specifies a file name or path to which the generated
                    tile images should be saved.
-tilesize 1..97     Sets the size of the tile images (default is 8), which
                    is the square root of the no. of pixels per map location.
-maxtiles 1..63336  Limits the maximum no. of tiles to be generated. Smaller
                    values may reduce the quality of the reconstructed image.
-bpp 8|16|32        Specifies the no. of bits per pixel in the tile images;
                    '8' gives 256 colours, '16' gives 32,768 colours and '32'
                    gives 16,777,216 colours. (Default is to use the same
                    colour depth as the input image.)
-mapout <outfile>   Specifies a file name or path to which the generated map
                    should be saved.
-vflip              Flip the generated map vertically when saving it.
-width 1..N         Forces the map to a specified width (default is the
                    width of the input image divided by the tile size).
-height 1..N        Forces the map to a specified height (default is the
                    height of the input image divided by the tile size).

-----------------------------------------------------------------------------
3   MapToSpr program
    ================

  This program reconstructs an image from a map file and associated set of
tile graphics. As might be expected, it is much simpler than the 'SprToMap'
program.

  First, the tile images file is loaded. Whether or not to treat the map as
a 'wide' or 'byte' map is decided automatically by finding the highest-named
sprite, or the number of sprites in the file (if '-order' was specified). If
there are more than 256 tile images then the map is assumed to be 'wide' (two
bytes per map location).

  Because the width of a map is not stored in a map file (which just consists
of raw tile references), it is usually advisable to specify the width in the
command line options. An error will be reported if the size of the map is
not exactly divisible by the specified width. If no width is specified then
the program will attempt to guess the width. Its first guess is the square
root of the map size; it then tries progressively smaller heights until it
finds one by which the area is exactly divisible (this assumes the map is
probably wider than it is tall).

  During the process of loading the map file, it may be flipped vertically
if requested by the user. This option is provided to facilitate decoding of
Star Fighter 3000 maps.

  The output image is generated by simply arranging the tile images in the
order specified by the map. Each row of tiles is arranged and output
separately to reduce the amount of memory required (which can be enormous,
for large maps). The number of bits per pixel and dots per inch in the
output image will be the same as for the tile images. An error will be
reported unless all the tile images have the same dimensions and format.

Syntax:

*MapToSpr [-verbose] [-order] [-vflip] [-width 1..N] [-output <outfile>]
          <mapfile> <tilesfile>
Options:

-verbose            Enables display of informational messages whilst
                    processing (including percentage done).
-order              Find tile images from reference numbers by their order
                    in the sprite file (default is to search by sprite name).
-vflip              Flip the input map vertically before using it to
                    construct the output image.
-width 1..N         Specifies the width of the input map, in tiles. The map
                    size must be a multiple of this value. Will attempt to
                    guess the width from the map size, unless specified.
-output <outfile>   Specifies a file name or path to which the reconstructed
                    image should be saved.

-----------------------------------------------------------------------------
4   Program history
    ===============

Release 1 (14 Dec 2006)

  First public release.

-----------------------------------------------------------------------------
5   Compiling the programs
    ======================

  Full source code is supplied with these programs. To compile and link the
code without modification you will also require an ISO 9899:1999 standard 'C'
library (as supplied with recent versions of the Acorn C/C++ Development
Suite).

  The supplied 'Make' files were automatically generated by Acorn's Make
application, and will attempt to invoke the Norcroft RISC OS ARM C compiler
and ARM linker supplied with the Acorn C/C++ Development Suite. To reduce
external dependencies, they are set up to compile code compatible with
floating point emulator 2 and link against RISCOS Ltd's generic stubs
library ('StubsG'). The symbol 'RISC_OS' is pre-defined, which enables some
code that is reliant on RISC OS system calls (e.g. to set file types and
verify sprite areas).

  It is possible to re-compile the programs for RISC OS using the
combination of the GNU C compiler and UnixLib. When I attempted it, some
tweaking was required because of omissions in UnixLib; the <stdint.h> header
doesn't define all the symbols and types that it should, and the "kernel.h"
header doesn't define _kernel_ERROR (which should be -2). Of course you must
also specify -std=iso9899:1999 in the command line options. Once these
problems have been overcome, the resultant code is slightly faster than that
generated by the Norcroft compiler.

-----------------------------------------------------------------------------
6   Licence and Disclaimer
    ======================

  These programs are free software; you can redistribute and/or modify them
under the terms of the GNU General Public Licence as published by the Free
Software Foundation; either version 2 of the Licence, or (at your option)
any later version.

  These programs are distributed in the hope that they will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public Licence for
more details.

  You should have received a copy of the GNU General Public Licence along
with these programs; if not, write to the Free Software Foundation, Inc.,
675 Mass Ave, Cambridge, MA 02139, USA.

-----------------------------------------------------------------------------
7   Credits
    =======

  These image manipulation tools were designed (if you can call it that!)
and programmed by Chris Bazley.

  A single header file from CBLibrary is included with the source code. This
library and its use are covered by the GNU Lesser General Public Licence.
You can obtain the rest of CBLibrary from http://www.bigfoot.com/~chrisbazley

  My thanks to Guttorm Vik and the current maintainers of StrongED, the
excellent text editor I used for writing these programs. It is available
from http://stronged.iconbar.com

  The game Star Fighter 3000 is  FEDNET Software 1994, 1995.

-----------------------------------------------------------------------------
8  Contact details
   ===============

  Feel free to contact me with any bug reports, suggestions or anything else.
Even if you think that my programs are crap, I'll be interested to know!

  Mail:  Mr C.J. Bazley
         43 Wilton Grove
         Wimbledon
         London
         SW19 3QU

  Email: mailto:chrisbazley@bigfoot.com (preferred)

  WWW:   http://starfighter.acornarcade.com
         http://www.bigfoot.com/~chrisbazley
