SUGGESTIONS FOR LOW-LEVEL INTERFACES TO CEDAR-
GRAPHICS BITMAPS

Jorge Stolfi, August 10, 1982

1. Bitmaps

I propose the following extension of BitmapRep:

BitmapRef: TYPE = REF BitmapDescr;

BitmapDescr: TYPE = RECORD
[height, width: NAT, -- in pixels
bitsPerPixel: (0..16],
deltaX, deltaY, -- in bits
offset: Environment.BitAddress,
baseRef: REF CoreBlock,
basePtr: LONG POINTER TO CoreBlock];

CoreBlock: TYPE = RECORD
[words: SEQUENCE COMPUTED length: CARDINAL OF CARDINAL];

A BitmapDescr is intended to represent a single in-core bitmap (not necessarily a color plane) of some raster device. For example, in full 24 bits-per-pixel color mode, with interleaved red and green, we would have two bitmaps, one of 16bpp and one of 8bpp.

The first word of the bitmap proper (in the form of a CoreBlock) is pointed to by basePtr; if the bitmap is in counted storage, baseRef is used instead of (or in addition to) basePtr.

The height and width are given in pixels. The parameters deltaX, deltaY, and offset give the conversion between pixel coordinates and memory addresses: the address of pixel [X, Y] is offset + deltaX*X + deltaY*Y.

All color and B/W display modes available here at PARC that I know of can be accomodated in this scheme; in fact, that would be the case even if we restrict deltaX to be equal to bitsPerPixel, and deltaY to be positive. However, this simplification requires all bitmaps to be compact (i.e., consecutive pixels in the same row should be adjacent in core) and ties the device coordinate system to the bitmap layout.

The latter may not be much of a problem (users that want to fiddle with raw bitmaps should pay the price), but the former may be incompatible with some exotic device of the future, or may lead to memory waste in some applications; therefore, I advocate keeping the general addressing scheme as defined before.

Note that with the above declarations the maximum raster length is 2↑15-1 bits, which, in the extreme case of 16 bits per pixel, would be only 2↑11-1 = 2047 pixels. Therefore, forward compatibility considerations may require deltaX and deltaY to be long INTs. Also, bitsPerPixel should probably be (0..32], just in case someone comes up with a full-color mode with interleaved red and green and blue, or something of the sort.

2. The BitmapOps interface

The lowest level of CedarGraphics would be a set of facilities for dealing with such bitmaps; in a sense, it would be an extension of the BitBlt interface. First, it would provide some useful routines, like

GetPixel: PROC [b: BitmapRef, ix: PixelIndices] RETURNS [p: PixelValue];

PutPixel: PROC [b: BitmapRef, ix: PixelIndices, p: PixelValue];

PixelValue: CARDINAL; -- or maybe LONG CARDINAL

PixelIndices: TYPE = [x, y: Coordinate];
Coordinate: TYPE = INTEGER;

NewBitmap: PROC
[height, width: NAT, bitsPerPixel: (0..16],
deltaX: INTEGER ← 0, -- default is bitsPerPixel
positiveDeltaY, roundDeltaYToNearestWord: BOOL ← TRUE,
baseRef: REF CoreBlock ← NIL,
basePtr: LONG POINTER TO CoreBlock ← NIL]
RETURNS [b: BitmapRef];
-- (if both baseRef and basePtr are omited, allocates a new
-- CoreBlock of sufficient size).

ClipBitmap: PROC [b: BitmapRef, box: BitmapBox]
RETURNS [bClipped: BitmapRef];

BitmapBox: [low, lim: PixelIndices];

A BitmapBox bx defines the set of pixels with indices satisfying
bx.low.x LEQ pix.x < bx.lim.x AND bx.low.y LEQ pix.y < bx.lim.y. ClipBitmap returns a new BitmapRep that points to the same CoreBlock but has offset, height, and width modified in such a way that only the pixels inside the given box are accesible, and bClipped[x, y] = b[x+bx.low.x, y+bx.low.y].

The main procedure in this interface would be a generalized BITBLT operation:

DoBitmapOp: PROC
[sink: BitmapRef,
sinkOp: BitBlt.SrcFunc ← null,
binOp: BitBlt.DstFunc ← null,
source: BitmapRef ← NIL,
pat: RepeatingPattern,
sourceOp: BitBlt.srcFunc ← null,
bx: BitmapBox ← [[0, 0], [LAST[Coordinate], LAST[Coordinate]]],
pos: PixelIndices ← [0, 0]];

This procedure performs sink ← (sinkOp sink) binOp (sourceOp source), within the intersection of the bounding box bx and the sink’s own bounding box.

The pattern pat specifies the value that is to be subtituted for source pixels that fall outside the source’s bounding box (or for all source pixels, if source = NIL). Pixel [0, 0] of the source is aligned with pixel pos of the sink.

This procedure uses BitBlt in the easy cases (hopefully, the majority of them). In addition to the capabilities of BitBlt, I found it convenient to add the option of complementing the sink as well as the source, and the "filling in" of missing source pixels described above. These two extensions may require extra BITBLTS, but they are not too hard to code (as you certainly know from implementing CedarGraphics) and they help a lot in the writing of client programs.

I don’t have any bright ideas about the proper representation of RepeatingPatterns. For the BOP application I had in mind, I found that providing a single pixel value (i.e., a 1 by 1 brick) was enough. This can be translated into the BITBLT gray pattern representation provided the pixel size is a power of two, or in case the pixel value given is either all zeros or all ones (two very common cases). I guess this will not be enough for some CedarGraphics uses (e.g., halftoning), so I will leave this problem to you.

The bx parameter is logically superfluous, given the ClipBitmap procedure above; it is provided mainly for efficiency reasons (it prevents the allocation of a new BitmapDescr).

An important point is what happens when the bitsPerPixel of sink and source are different. Since the color interpretation of pixel values is defined only at a higher level in the CedarGraphics hierarchy, the effect of such BitmapOp may be left undefined. For some applications other than CedarGraphics it might be useful to define it in some arbitrary manner, e.g. by zero filling/truncating the most significant bits of each pixel, but that may not be worthwhile.

3. The Multple Bitmaps interface

Since a device may use more than one bitmap, the following "interface sugar" should be useful:

Bitmaps: TYPE = ARRAY BitmapName OF BitmapRef;

BitmapName: TYPE = {A, B, C};

Again, the concept of "color" is not defined at this level, so there there is no implicit correspondence between the bitmap names A, B and C and the red, green and blue color planes. Some of the bitmaps may be missing. The bitmaps may have different pixel lengths, different deltas and different offsets. They may have even different bounding boxes (although it is hard to conceive of an application that needs this feature).

The procedures of the BitmapOps interface are extended here to work on such triplets of bitmaps: we define

PixelValues: TYPE = ARRAY BitmapName OF PixelValue;

RepeatingPatterns: TYPE=ARRAY BitmapName OF RepeatingPattern;

so we can define GetPixels, PutPixels, ClipBitmaps, DoBitmapsOp in the obvious way. As before, the effect of DoBitmapsOp need not be defined unless corresponding bitmaps of sink and source have the same bitsPerPixel.

4. Color representation

Depending on the device and the mode in which it is set up, the correspondence between colors and pixel values may be established by an algebraic formula, a procedure, a table, or a combination of the above. The following representation is intended to cover all of these possibilities:

ColorEncoding: TYPE = RECORD
[parms: EncodingParameters,
PixelsToColor: PixelsToColorProc,
ColorToPixels: ColorToPixelsProc,
SetColor: SetColorProc];

EncodingParameters TYPE = REF;

PixelsToColorProc: TYPE = PROC [parms: EncodingParameters, pixs: PixelValues] RETURNS [c: Color];

ColorToPixelsProc: TYPE = PROC [parms: EncodingParameters, c: Color RETURNS [pixs: PixelValues];

SetColorProc: TYPE = PROC [parms: EncodingParameters, pixs: PixelValues, c: Color];

where

Color: TYPE = [red, green, blue: REAL -- in the range [0.0...1,0] -- ];

The three components of a Color argument give the amounts of red, green and blue, or any equivalent set of color parameters: intensity/hue/saturation, CIE X/Y/Z, etc. Color values should be device-independent.

The parms and the PixelsToColor procedure together define the mapping between pixel values and Color values characteristic of the device in question. For absolute color modes (e.g. full 24bpp) the parms field may be NIL, or point to a small record containing just the number of bits per color plane and their position in the bitmaps (like "the first eight bits of bitmap A are red, the next eight bits of bitmap A are green, and bitmap B is blue"). For mapped color modes (e.g. mapped 8bpp) the parms will point to (among other things) the current color map, whose entries are set by SetColor.

If the device’s response is significantly nonlinear, ColorToPixels and SetColor should compensate for it; the parms record may contain parameters (e.g., gamma) that determine some part of this correction.

The inverse mapping (REAL color values to pixels) is given by the ColorToPixels procedure, and is by necessity only approximate. This is not necessarily the color encoding used by CedarGraphics, which may want to use some halftoning process when converting colors to pixels. Ideally, inverse mappings should enter the scene only higher up in the CedraGraphics hierarchy; however, inverting a "black box" function is rather inefficient process, so it is best that the inverse function be provided by the same module that implements the direct one.

5. Device interfaces

The lowest-level interfaces to the various raster devices would be defined in terms of the above. For example, an interface ColorScreen would provide essentially the same objects as the existing ColorDisplay, except that we would have a single declaration

bitmaps: READONLY Bitmaps;

replacing bitsPerPixelA, bitsPerPixelB, ... wplA, ..., baseC. The interface would also export the variable

encoding: READONLY ColorEncoding;

these two variables would be set by SetMode, that would remain more or less as it is (with perhaps a more general definition of Mode). The mixedRG flag would become private, and the procedures GetColorMap, SetColormap, GetPixel, SetPixel, ... etc, would be replaced by encoding.PixelsToColor, encoding.SetColor, encoding.ColorToPixels, and GetPixels/SetPixels from the multiple bitmaps interface. In full 24bpp mode, encoding.SetColor would be NIL, and encoding.ColorToPixels would be one of two procedures depending on the mixedRG submode.

With the current color devices, this interface allows not only the full 24bpp mode and the various mapped modes with client-defined color map, but also several other "emulated" modes. For example, one could have a Mode like "gray-scale, 8 bits per pixel, gamma=2.5"; SetMode would set up an 8bpp mapped mode, with an appropriate color map so that pixel values from 000C to 377C would show up as the appropriate gray levels. In this case, encoding.SetColor would be NIL, and encoding.PixelsToColor may be defined analytically.

Another example in the same vein would be a mode like "3 bits of red, 3 bits of green, 2 bits of blue". As above, the implementation module would emulate this by an appropriate color map, but to the client it would look like a hardware mode, and the color map setup would be automatic.

With reference to the latter example, note that the client can build, with a trivial modification to the offset and bitsPerPixel fields, one separate BitmapDescr for each color plane, and use PutPixel and DoBitmapOp on each plane without affecting the others, even though they are all combined in a single bitmap. Admittedly, this will be rather inefficient, but it may be wothwhile. (This feature may seem rather silly, but I had to implement it for BOP, so there is at least one application for it...). BITBLT may still be applicable in such single-plane BitmapOps, but it would require some smart coding.

The black-and-white display would have a similar interface, except that it would support only two modes, (OFF or ON). When ON, bitmaps[A] would be the screen bitmap, bitmaps[B] = bitmaps[C] = NIL, encoding.SetColor would be NIL, and so forth.

6. Color cursors.

Any software cursor(s) would be implemented, for each device that needs them, on top of the above interfaces, using DoBitmapOp for drawing and erasing the arrow on the screen bitmap(s).

7. CedarGraphics

I would like CedarGraphics to have a single kind of BitmapDevice, containing

BitMapDeviceRep: TYPE = RECORD
[bitmaps: Bitmaps,
encoding: ColorEncoding,
.. other info];

The procedure GraphicsOps.NewContextFromBitmap should be generalized to accept a Bitmaps triplet and a ColorEncoding. The BitmapDeviceRep may specify a more elaborate color-to-pixels encoding, e.g. halftoning, to be used instead (or in combination with) the basic single-pixel ColorEncoding.

Conversely, there should be a procedure GraphicsOps.GetBitmaps that returns the Bitmaps into which a given Graphics.context is drawing, with the bounding boxes restricted to the context’s clipping box (what about non-rectangular clipping regions? good question!).

The ultimate generalization of DrawBitmap is of course provided by the CedarGraphics facilities for copying a context (treated as a sampled image) into another, under general coordinate transformations and with automatic color decoding and re-encoding.

8. Viewers

The window manager would continue to use CedarGraphics to communicate with client programs, but will have the choice of carrying its internal bookkeeping at the level of the BitmapOps and MultipleBitmaps interfaces. The advantages of doing so would be (perhaps) increased efficiency, and a the more explicit accounting of pixels (coordinates are INTEGERs, not REALs, at that level). A possible disadvantage would be the inability to handle some future devices (say, a display with 300 pixels per inch, or rotated by 45 degrees, or...)

9. Conclusion

I am aware that much of this is already in CedarGraphics. The main points of this proposal are (1) to make low-level access to the bitmaps of CedarGraphics available in public interfaces, (2) extend such access to color devices in an uniform way, (3) use such interfaces as a common foundation for CedarGraphics and raster device interfaces, and (4) provide some bitmap operations at a level intermediate between BitBlt and CedarGraphics.

I believe this would benfit many applications (like BOP) where the images to be given to CedarGraphics come in the form of bitmaps, and perhaps make the lower levels of CedarGraphics more device-independent.