The Postage Stamp Rasteriser
============================
by John Walker -- kelvin@fourmilab.ch
WWW home page: http://www.fourmilab.ch/
Ever needed a little rasteriser? A little one--small, simple,
suitable, for example, for creating preview bitmaps that allow users
to select images graphically rather than typing in stoopid little file
names that mean nothing to nobody.
PSTAMPR.C is a software component that performs vector and polygon
scan conversion into monochrome bitmaps of user-defined resolution.
It handles binary (light and dark) bitmaps of any addressable
resolution and scan converts both vectors and polygons (concave or
convex). Its handling of concave polygons uses the latest, most
accurate algorithm known to the author (patiently evolved within the
belly of AutoCAD for over eight years).
This component is intended to be clean, self-sufficient, and
independent. It isn't particularly efficient, but neither is it
profligate in its use of your CPU resources. It's called the "Postage
Stamp Rasteriser" because it's intended for making small, simple,
monochrome images, however, there are no inherent limitations that
prevent your using it in more ambitious applications. If performance
is critical, however, you'll want to optimise some of the algorithms:
AutoCAD's implementation of these functions is far more CPU efficient,
but at the cost of enormously increased complexity of the code.
PSTAMPR should, in all cases, produce the same bitmaps as AutoCAD's
rasteriser would if presented with the same vectors and polygons.
Built-in code allows exporting the bitmaps created with PSTAMPR as
uncompressed TIFF files.
You access PSTAMPR through the following functions. For clarity of
documentation, the functions are described in prototyped declaration
form. For compatibility with vintage C compilers, however, the actual
declarations use the old-fashioned form.
INITIALISATION
==============
To use PSTAMPR to scan convert a vector image, first initialise it by
calling:
char *psrinit(unsigned int xsize, unsigned int ysize,
unsigned int background)
where xsize and ysize give, respectively, the width and height of the
bitmap in pixels and background specifies the background colour (zero
or nonzero) to which the bitmap will be initialised. psrinit()
returns a character pointer to the bitmap, dynamically allocated with
malloc(), or NULL if the bitmap could not be allocated. The bitmap is
stored as 8 bits per char. Your program can set and read the bits
without knowing the precise format of the bitmap by calling the
psrsetpixel() and psrgetpixel() functions (see below). If, for
efficiency's sake, you want to directly access the bitmap, refer to
the code in those functions for an example of how the bitmap is
addressed. The bitmap can be internally organised with pixel 0,0 at
the bottom left or the top left. If the compile-time variable FlipY
is defined, 0,0 is at the bottom left; if it isn't defined, then pixel
0,0 is at the top left. Lines in the bitmap are padded to the next
byte boundary; you can determine the number of bytes in each line of
the bitmap by calling psrlinelen().
The pointer returned by psrinit() is a "handle" you pass to all the
other functions of PSTAMPR. The fact that all state is kept in the
bitmap itself permits your program to use PSTAMPR to create any number
of bitmaps simultaneously, even in parallel threads of a multitasking
program. IMPORTANT--to dispose of the bitmap you *must* call
psrterm() with the handle of the bitmap rather than attempting to free
the handle directly with free(). psrinit() allocates some local
storage at the start of the bitmap and hence the handle it returns
doesn't point to the start of the allocated buffer. Consequently,
passing that pointer to free() will lead to disaster.
PIXEL SCAN CONVERSION
=====================
To set an individual pixel in the bitmap, call:
void psrsetpixel(char *bhandle, unsigned int x, unsigned int y,
unsigned int colour)
where bhandle is the handle to the bitmap returned by psrinit(), x and
y specify the co-ordinates of the pixel to be set, and colour
specifies whether the pixel is to be set to zero (colour == 0) or one
(colour != 0).
VECTOR SCAN CONVERSION
======================
To draw a vector into a bitmap, call:
void psrvector(char *bhandle, unsigned int fx, unsigned int fy,
unsigned int tx, unsigned int ty,
unsigned int colour)
bhandle is the handle to the bitmap, fx and fy specify one endpoint of
the vector while tx and ty give the other. The colour of the vector
(whether it is drawn in zero or one bits) is determined by whether
colour is zero or nonzero.
POLYGON SCAN CONVERSION
=======================
To draw a solid-filled polygon (which may be concave or convex) into
the bitmap, call:
void psrpoly(char *bhandle, struct spolygon *poly,
unsigned int colour)
Once again, bhandle is the handle to the bitmap. The vertices of the
polygon are given in the spolygon structure poly, which is declared as
follows:
struct spoint {
unsigned int x, y;
};
struct spolygon {
int npoints; Number of points in polygon
struct spoint pt[MAXVERT + 1]; Actual points
};
The compile-time variable MAXVERT specifies the maximum vertices a
polygon may contain. This number must be known when PSTAMPR is
compiled in order to correctly allocate stack space used for tables of
edges and intersections within psrpoly(). Finally, the colour of the
polygon (whether it is scan converted to zero or one bits) is
specified by whether the argument colour is zero or nonzero.
RETRIEVING INDIVIDUAL PIXELS
============================
You may read the value of an individual pixel from the bitmap with:
int psrgetpixel(char *bhandle, unsigned int x, unsigned int y)
where bhandle is the handle to the bitmap, and x and y specify the
column and row address of the pixel to be read. The value of the
pixel is returned by psrgetpixel(): 0 or 1. Reading out the entire
bitmap with psrgetpixel() is staggeringly inefficient; it's far better
to write code that accesses the bitmap directly.
DIRECT BITMAP ACCESS
====================
To access a row of pixels in the bitmap, you need only know the row
address and the number of bytes each row of pixels occupies in memory.
You can obtain the memory length of pixel rows with:
int psrlinelen(char *bhandle)
where bhandle is the handle to the bitmap. The function returns the
row length in bytes. For example, the pixels in row 12 of the image
myImage are stored at the address:
char *row12, *myImage;
row12 = myImage + (12 * psrlinelen(myImage));
Pixels are stored 8 per byte, with the leftmost pixel in the high
order (0x80) bit. Thus, the pixel in column X of row12 may be
extracted with the expression:
((*(row12 + (X >> 3)) & (0x80 >> (X & 7))) ? 1 : 0)
Obviously, for efficiency you should call psrlinelen() only a single
time after creating the bitmap with psrinit(), then store its value in
a local variable for subsequent accesses to the bitmap.
EXPORTING THE IMAGE IN TIFF FORMAT
==================================
You can write your bitmap as an uncompressed monochrome TIFF image
file by calling:
void psrtiff(char *bhandle, FILE *fd)
where bhandle is the handle to the bitmap and fd is the handle of a
binary file already opened for writing. The TIFF image is written
starting at the current file position of the file fd, and after the
image has been written, the current file position of fd will be left
at the first byte following the TIFF image. Since no seeks are
performed on fd, it may be any type of file, even a device file or
pipe which cannot be positioned.
RELEASING A BITMAP
==================
To release the storage allocated for a bitmap, call:
void psrterm(char *bhandle)
where bhandle is the image handle. The storage allocated for the
bitmap in psrinit() will be freed. No references may be made to the
bitmap using the handle after its storage is relinquished with
psrterm().
BUILT-IN TEST PROGRAM
=====================
If you compile PSTAMPR.C with TestProgram defined, a main() function
is included that performs a fairly demanding regression test on the
PSTAMPR functions. It creates a bitmap using a mix of vectors,
polygons, and pixels, then exports the bitmap as a TIFF file. The
TIFF file is then read back and compared byte-for-byte against a
known-correct canned TIFF file. Extraneous garbage at the end of the
TIFF file is also reported. If you compile with PosRast defined, the
test program will write the bitmap to standard output in the PBM
format used by Jef Poskanzer raster toolkit (normally ASCII mode, but
binary if you also define Binary at compile time). This can be handy
if you run into problems and want to use the PBMPLUS tools to analyse
the generated bitmap (for example, subtracting what you got from a
known correct bitmap to see which pixels differ).
CONFIGURING FOR PERFORMANCE
===========================
PSTAMPR uses the package extensively to verify arguments to
functions and to make internal consistency checks. Once you're happy
that PSTAMPR is working properly, you may compile it with the symbol
NDEBUG defined at compile time, which will remove the assertions and
the substantial compute overhead they create.