The Postage Stamp Rasteriser ============================ by John Walker 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.