[Index]
These techniques require alpha blending, where pixels from both the source and destination of drawing are blended using a mathematical function. Full alpha blending using 24 bits per pixel is a handy technique, but we do not always have the luxury of assuming we have access to an efficient alpha blending mechanism. For example, the X-Windows system currently only allows this feature via an extension known as the Render extension, which is not yet present on all installations of X.
There are cases where full transparency or full opaqueness of source pixels suffices. Fonts, for example, can be rendered adequately by copying glyphs from a bitmap having only these two levels of transparency. The fully opaque pixels are painted using the desired colour, and the fully transparent pixels are skipped. Images which are see-through in places can be implemented using a similar technique.
This is a sufficiently common special case that implementing it efficiently should be possible, and exposing a portable interface to this feature is clearly worthwhile.
This paper describes an implementation of bi-level transparency in bitmaps, for the X-Windows system.
A clipmask pixmap can be used to paint an irregularly shaped area with a certain colour, or it can be used to choose which pixels are affected when copying a pixmap.
Because a clipmask only contains 1 bit per pixel, it can only be used to store two levels of transparency: fully opaque or fully transparent.
The drawing model used by MS-Windows does not directly allow such a stencilling operation, so the effects of a clipmask must be simulated on that platform. Fortunately this is simple to achieve.
MS-Windows does not yet allow this technique, but may do so in the future.
What use is an 8 bit alpha channel? This allows 256 levels of transparency, which can be used in combination with an appropriate alpha blending function to produce high quality optical effects. The alpha channel is commonly used to provide a translucent glass effect, so that pixels can change the colour or brightness of an affected pixel.
Translucency of this kind can be used to produce three dimensional lighting effects, good anti-aliased lines and fonts, smooth animation, and so on. Because each final pixel drawn on the screen is a combination of source and destination, many options are available, from overwriting the destination with a completely new value, to blending it subtley with the source.
The introduction of these features into windowing systems is far from settled. Many questions are still open, such as the use of alpha channels in combination with windows. Should windows be able to be partially or fully transparent? How does obscuring a window with another affect backing store?
Even if these interactions were settled, the same choices may not have been made on all platforms, such as MS-Windows or Macintosh. In attempting to provide a portable approach we should steer clear of the leading edge of technology where best practice is yet to be determined, and instead design using the core operations which are stable and implemented similarly on all platforms.
For this reason, multi-level translucency is not considered in this document. Bi-level transparency is, however, a quite portable bitmap operation.
The following discussion refers to this second approach. A pixmap of arbitrary pixel depth is joined with a clipmask (a pixmap of depth one) in a single object, which we shall refer to as a Bitmap. A Bitmap can be thought of as a rectangular array of pixels, some parts of which can be fully transparent.
This notion of a Bitmap having pixels with one bit of transparency fits well with the more general concept of an alpha channel being associated with each pixel, not as a separate array of data. This model of alpha channels is popular in the literature and in practice.
Bitmaps of this kind are useful for many reasons. A drawing package which includes Bitmaps but avoids mention of clipmasks can do many of the same things which would otherwise require a clipmask, but without introducing a new concept. Because the clipmask and the pixmap component of the Bitmap are on the server side, they can be drawn efficiently. If the system uses gamma correction to improve the display of colours, the Bitmap can be prepared from data which is already gamma corrected, so that ordinary fast bitmap copying operations suffice to draw correct pixels to a window.
Why should clipmasks be joined with pixmaps, and not with windows? Windows do not yet support a consistent transparency model on all platforms, so for the sake of portability we ignore the possibility that windows may be partially transparent. If a window is assumed to be fully opaque, it is only the preparation of an image for display on the screen which requires the use of this transparency information. Bitmaps are the primary method used in such preparation.
A Bitmap is thus a useful, simple concept which joins the features of fully opaque pixmaps with a clipmask, to allow transparency.
A Bitmap conceptually is a pair of pixmaps, together with a rectangle specifying the dimensions of the pixmaps, in pixels.
struct Rect {
int x, y, width, height;
};
struct Bitmap {
Rect area;
Pixmap image;
Pixmap clipmask;
};
The top-left point of a Bitmap is always (0,0), so only the width and height fields of the area are non-negative. We could thus omit the x and y componenets of the rectangle, but for simplicity we shall retain these fields.
If a Bitmap is fully opaque (as many will be) the clipmask field can be left empty to signal that fact. Ideally, when we draw into the Bitmap, the drawing operations should update the clipmask, and even remove it if the entire Bitmap becomes fully opaque.
Let's consider three important drawing operations, fill_rect, copy_rect and draw_text.
Let us assume that we have an object which stores necessary graphics information, such as an X-Windows GC graphics context. This object is called a Graphics object, and is contains fields such as:
struct Graphics {
Bitmap * bmap;
Colour colour;
Display * disp;
GC gc;
};
We assume, for efficiency, that the Graphics object already has the correct drawing colour set in its GC. Keeping this operation outside the fill_rect function is sensible since it may be common to draw many filled rectangles using the same colour. Selecting the colour first, then drawing the rectangles assuming the correct colour has been selected avoids duplication of effort.
The following is a small implementation of the fill_rect operation, for the X-Windows system.
void fill_rect(Graphics *dst, Rect r)
{
Display *disp;
XID dst_id;
GC dst_gc;
Pixmap dst_mask;
GC dst_mask_gc;
if (dst->colour.alpha > 127)
return; /* nothing to draw if colour is transparent */
/* destination is a bitmap */
disp = dst->disp;
dst_gc = dst->gc;
dst_id = dst->bmap->image;
dst_mask = dst->bmap->clipmask;
/* draw the rectangle */
if (dst_mask == None)
{
/* destination is fully opaque: simple case */
/* fill pixels with colour */
XFillRectangle(disp, dst_id, dst_gc,
r.x, r.y, r.width, r.height);
}
else {
/* destination is partially transparent */
dst_mask_gc = XCreateGC(disp, dst_mask, 0, NULL);
if (! dst_mask_gc)
return 0;
/* opaque -> 1 (opaque) */
XSetFunction(disp, dst_mask_gc, GXset);
/* fill pixels with colour */
XFillRectangle(disp, dst_id, dst_gc,
r.x, r.y, r.width, r.height);
/* update transparency information */
XFillRectangle(disp, dst_mask, dst_mask_gc,
r.x, r.y, r.width, r.height);
XFreeGC(disp, dst_mask_gc);
if ((r.x == 0) && (r.y == 0) &&
(r.width == dst->bmap->area.width) &&
(r.height == dst->bmap->area.height)) /* all opaque */
{
XFreePixmap(disp, dst_mask);
dst->bmap->clipmask = None;
}
}
}
The first test in the function checks if the drawing colour is more transparent than opaque. Assuming we have an alpha field within the Colour object, which measures transparency as a number from 0 (opaque) to 255 (transparent), we can check if it is beyond half-way, and if so, draw nothing:
if (dst->colour.alpha > 127) return; /* nothing to draw if colour is transparent */
In essence this examines the top-most bit of the transparency information in the Colour structure, and if it signals transparency, we avoid drawing any pixels. This provides two levels of transparency within the drawing colour, which is similar to the two levels of transparency within the Bitmap. We could avoid this test if we wanted drawing colours to be fully opaque, but extending the notion of bi-level transparency into the drawing colour itself has some rewards when drawing to windows, which, as mentioned before, should not use clipmasks to implement transparency, for reasons of portability.
After this test, some values are copied into local variables. This step is not necessary, but avoids some dereferencing of pointers in the latter parts of the function. The function as it stands does not require this step, but as we shall see later when discussing client-side clipping, the inner part of this function can be re-cast as a loop, in which case avoiding dereferences can save a little time.
The core functionality of the fill_rect operation follows, and is essentially a conditional statement, asking if the destination Bitmap has an associated clipmask:
if (dst_mask == None) ... else ...
If it does not have a clipmask, we just perform one XFillRectangle operation. If it does has a clipmask, we perform two XFillRectangle operations, one to change the opaque pixels within the Bitmap's image field, and one to set opaqueness information within the clipmask. The first of these operations is that same as in the first branch of the conditional.
It would have been possible to combine this common drawing operation and move the conditional statement to just guard the second XFillRectangle call, which draws into the clipmask, but re-casting the function as a loop for client-side clipping makes it more efficient to completely separate the two cases. This will be explained in a little more detail later.
The second XFillRectangle call draws into a newly constructed GC which affects the Bitmap's clipmask. Using the GXset drawing mode causes pixels to be set to a value of 1 wherever drawing occurs. In X-Windows, 1 is used within a clipmask to signify that the corresponding pixel in the image is opaque, and 0 is used for transparency. Keeping the construction of the new GC inside the conditional avoids creating one if there is no clipmask.
The final check in the function removes the clipmask from the Bitmap if we've filled the entire area with colour:
if ((r.x == 0) && (r.y == 0) &&
(r.width == dst->bmap->area.width) &&
(r.height == dst->bmap->area.height)) /* all opaque */
{
XFreePixmap(disp, dst_mask);
dst->bmap->clipmask = None;
}
In that case, any clipmask associated with the Bitmap is now redundant, since it will be filled with 1's. We can thus improve efficiency by deleting the clipmask and avoid the second call to XFillRectangle on each subsequent call to fill_rect. As mentioned earlier, the ideal would be to somehow detect that a clipmask is now signalling total opaqueness, and delete it in that case, but that is very inefficient to implement since we would need to read all the bits back from the server to check each time. Instead, this simple test just handles one common case, that the whole bitmap has been filled with colour, and is therefore completely opaque. It is worthwhile handling this one case, because it has the potential to save time by halving the number of messages sent to the graphics server, and thus also halve the amount of work the server must do for each fill_rect call.
Client-side clipping, by contrast, is a series of mathematical calculations which occurs within a client program to clip drawing before sending each drawing request to the server. This has the potential to reduce the work-load of the graphics server and avoid message traffic, but may have a cost in terms of increasing the number of drawing requests sent to the server.
Let us assume we have a structure called a Region, which defines an arbitrary set of points:
struct Region {
int num_rects;
Rect * rects;
};
A Region is here implemented as an array of distinct rectangles. There are many possible implementions of Regions, but this one is general and simple.
Suppose that we have a Region defined as part of the Graphics object:
struct Graphics {
Bitmap * bmap;
Colour colour;
Display * disp;
GC gc;
Region * clip;
};
Suppose also that this Region is always within the destination Bitmap's boundaries, so that by clipping to this Region we automatically clip drawing to be within the Bitmap. Thus, we can avoid server-side clipping for Bitmaps. This is quite a realistic assumption, since we can force the programmer to obtain a Graphics object through a defined interface in order to perform any drawing, and part of that interface can initialise the clip region to contain the Bitmap's drawable area. Subsequently the programmer may modify the clipping Region, but again, we can restrict this operation so that the resulting Region is always clipped to the boundary of the Bitmap. Thus we can assume the clip Region only refers to points within the Bitmap.
To clip the fill_rect operation we simply walk through the clip Region's rectangle list, obtain the intersection of each rectangle with the target rectangle, and fill that intersection. The intersection of two rectangles is guaranteed to be another (possibly empty) rectangle, so the mathematics is quite simple, and the operation to fill each intersection is just a call to XFillRectangle. We assume we have a function, clip_rect which clips two rectangles, returning the result:
Rect clip_rect(Rect r1, Rect r2)
{
if ((r1.x >= r2.x+r2.width) ||
(r2.x >= r1.x+r1.width) ||
(r1.y >= r2.y+r2.height) ||
(r2.y >= r1.y+r1.height))
{
/* no overlap */
r1.x = r1.y = 0;
r1.width = r1.height = 0;
return r1;
}
if (r1.x < r2.x) {
r1.width -= (r2.x - r1.x);
r1.x = r2.x;
}
if (r1.y < r2.y) {
r1.height -= (r2.y - r1.y);
r1.y = r2.y;
}
if (r1.x + r1.width > r2.x + r2.width)
r1.width = r2.x + r2.width - r1.x;
if (r1.y + r1.height > r2.y + r2.height)
r1.height = r2.y + r2.height - r1.y;
return r1; /* overlap */
}
The central part of the fill_rect operation is thus now a loop in each branch:
Rect clipped;
...
if (dst_mask != None)
{
/* destination is fully opaque: simple case */
for (i=0; i < dst->clip->num_rects; i++) {
clipped = clip_rect(r, dst->clip->rects[i]);
if (clipped.width == 0)
continue; /* nothing visible here */
if (clipped.height == 0)
continue; /* nothing visible here */
/* fill pixels with colour */
XFillRectangle(disp, dst_id, dst_gc,
clipped.x, clipped.y,
clipped.width, clipped.height);
}
}
else {
/* destination is partially transparent */
dst_mask_gc = XCreateGC(disp, dst_mask, 0, NULL);
if (! dst_mask_gc)
return 0;
/* opaque -> 1 (opaque) */
XSetFunction(disp, dst_mask_gc, GXset);
for (i=0; i < dst->clip->num_rects; i++) {
clipped = clip_rect(r, dst->clip->rects[i]);
if (clipped.width == 0)
continue; /* nothing visible here */
if (clipped.height == 0)
continue; /* nothing visible here */
/* fill pixels with colour */
XFillRectangle(disp, dst_id, dst_gc,
clipped.x, clipped.y,
clipped.width, clipped.height);
/* update transparency information */
XFillRectangle(disp, dst_mask, dst_mask_gc,
clipped.x, clipped.y,
clipped.width, clipped.height);
}
XFreeGC(disp, dst_mask_gc);
...
}
The simpler first case shows the operation most clearly. We walk through the clipping Region's rectangle list, calling clip_rect to clip the target rectangle r against the clipping rectangle. This new clipped rectangle is used when drawing, instead of r. For efficiency, we avoid drawing clipped rectangles which have zero width or height since drawing such rectangles will cause traffic to the server to no effect.
It should now be clear why separating the two cases using one conditional is important. The second case is more complex, and involves creating a GC. This clearly should occur outside the loop, otherwise an additional expensive round-trip to the server would occur each time through the loop. Grouping the two XFillRectangle calls within the loop avoids performing the calculations twice, once for the Bitmap's image and again for its clipmask. Thus, separating the two cases is simpler and more efficient than trying to merge the first call to XFillRectangle into a common block of code.
In theory it can also reduce the amount of work the graphics server must do to implement server-side clipping, but unless there is a way to tell the server to avoid this cost, it will still need to perform those checks. They will be trivial since the clipping will have been achieved already by the client, but the checks will still be performed. Currently defined interfaces for X-Windows and MS-Windows do not allow a programmer to avoid server-side clipping, so the only performance benefit we can claim from client-side clipping is the reduction in traffic.
As stated earlier, client-side clipping may actually result in an increase of traffic to the server, because each fill_rect operation, for instance, may cause up to N XFillRectangle calls, where N is the number of rectangles in the clipping Region. Each call fills a small part of the destination.
This cost is ameliorated slightly by the fact that implementations of Xlib, the X-Windows client-side protocol library, usually buffer XFillRectangle requests and send a more efficient burst of traffic for that case. Nevertheless, the traffic cost exists, and we must justify this cost.
The first observation to make is that there is not always an increase in traffic. In many cases, no clipping occurs, particularly in drawing to Bitmaps. Clipping is mostly used to implement overlapping windows in a window manager, or overlapping sub-windows within a window. Thus, only drawing to windows is of concern; drawing to Bitmaps usually results in the same traffic as normal.
The second observation to make is that there are cases where the traffic to the server is actually reduced. If sub-windows, for instance, are implemented using server-side objects, the only way to clip a drawn figure is to do so on the server's side. Even if that figure is completely obscured, or off the edge of the window, traffic to the server will still be needed, unless client-side clipping is used. If sub-windows are implemented completely on the client's side, client-side clipping really shines, because only the required drawing operations are transmitted to the server.
Consider an artificial situation to prove this point. Suppose we had a program which draws a thousand small rectangles to a window using fill_rect. Suppose that, through client-side clipping, we were able to determine that only one hundred of those rectangles needed to be drawn, but that half of them were clipped, requiring two operations for each to be drawn fully. This still only results in one hundred and fifty messages to the server, a considerable reduction in traffic than the original one thousand.
This situation is less artificial than it may seem. Most existing office programs which use push-buttons and drop-down menus rely heavily on drawing lots of small shapes, many of those being filled rectangles, and many others being text characters. The way existing window managers work, a window may often be temporarily partially obscured by another window. Revealing the obscured part of a window usually causes the program to refresh that portion by issuing drawing operations. This is exactly the situation described in the previous paragraph; many of the parts of the display do not need to be drawn, and client-side clipping can be used to silently remove redundant drawing operations to actually improve efficiency. Even if the window manager stores the entire window in backing store memory we are no worse off, because in that case we avoid trivial window updates entirely. Although in the future window managers may use backing store for all windows, for now the use of window updates is still common-place, and worth considering.
This is such a common occurrence that on its own is a good reason to implement client-side clipping. There are other reasons. Implementing sub-windows in the client rather than on the server gives a degree of portability not achieved otherwise, since sub-windows can then be guaranteed to behave the same way on all platforms. Clipping can be extended identically to other client-side objects, such as Images, which are similar to Bitmaps except they are drawn into using direct memory accesses. Custom font rendering is also made simpler, a fact which will be discussed in a later section.
We will only consider copying one Bitmap to another Bitmap. This is the most complex situation, because it involves four cases; each Bitmap may or may not have an associated clipmask. Copying pixels to a window is a special, simpler case since we have determined that windows do not have clipmasks, and thus we can rule out two of the cases. Because copying to windows is a subset of copying to Bitmaps, we shall ignore it in favour of the more general case.
What are the desired properties of a copy_rect operation from a Bitmap to another Bitmap? Firstly, the opaque pixels should be the only pixels copied. Secondly, if those opaque pixels replace a previously transparent area, we must change the destination Bitmap's clipmask to be opaque in those places. Thirdly, it would be desirable to delete the destination's clipmask if it is now fully opaque.
There are four cases:
In cases 2 and 4, the destination clipmask is modified. In those cases we wish to delete that clipmask if it is now fully opaque. For efficiency, the simplest way to achieve this is to remove it if and only if we've modified the entire destination and if the source is fully opaque (restricting the situation to case 2).
The source rectangle sr is copied to the destination point dp, which is where the pixel from the point (sr.x,sr.y) will be drawn. The rest of the pixels will be drawn to the right and below that point. There is no scaling in this function; the source rectangle is copied to the destination without changing its size. Scaling requires server-side support, which does not exist on X-Windows although it does on MS-Windows. For portability and consistency we assume no scaling.
A point is defined as:
struct Point {
int x;
int y;
};
The following code is an implementation of copy_rect for X-Windows, omitting client-side clipping.
void copy_rect(Graphics *dst, Point dp, Graphics *src, Rect sr)
{
Display *disp;
XID dst_id;
GC dst_gc;
XID src_id;
Pixmap src_mask;
Pixmap dst_mask;
GC dst_mask_gc;
/* assume destination is a bitmap */
disp = dst->disp;
dst_gc = dst->gc;
dst_id = dst->bmap->image;
dst_mask = dst->bmap->clipmask;
/* assume source is a bitmap */
src_id = src->bmap->image;
src_mask = src->bmap->clipmask;
if ((dst_mask == None) && (src_mask == None))
{
/* case 1: src and dst are both opaque */
XCopyArea(disp, src_id, dst_id, dst_gc,
sr.x, sr.y, sr.width, sr.height,
dp.x, dp.y);
}
else if ((src_mask == None) && (dst_mask != None))
{
/* case 2: src is opaque, but dst is not */
dst_mask_gc = XCreateGC(disp, dst_mask, 0, NULL);
if (! dst_mask_gc)
return 0;
/* dst -> 1 (opaque) */
XSetFunction(disp, dst_mask_gc, GXset);
/* copy the pixels */
XCopyArea(disp, src_id, dst_id, dst_gc,
sr.x, sr.y, sr.width, sr.height,
dp.x, dp.y);
/* update dst's opaqueness information */
XFillRectangle(disp, dst_mask, dst_mask_gc,
dp.x, dp.y, sr.width, sr.height);
XFreeGC(disp, dst_mask_gc);
/* remove opaque clipmask */
if ((dp.x == 0) && (dp.y == 0) &&
(sr.width == dst->bmap->area.width) &&
(sr.height == dst->bmap->area.height))
{
XFreePixmap(disp, dst_mask);
dst->bmap->clipmask = None;
}
}
else if ((src_mask != None) && (dst_mask == None))
{
/* case 3: src has a clipmask, dst is opaque */
XSetClipMask(disp, dst_gc, src_mask);
XSetClipOrigin(disp, dst_gc, dp.x, dp.y);
XCopyArea(disp, src_id, dst_id, dst_gc,
sr.x, sr.y, sr.width, sr.height,
dp.x, dp.y);
XSetClipMask(disp, dst_gc, None);
XSetClipOrigin(disp, dst_gc, 0, 0);
}
else {
/* case 4: both src and dst each have a clipmask */
dst_mask_gc = XCreateGC(disp, dst_mask, 0, NULL);
if (! dst_mask_gc)
return 0;
/* either clipmask has a 1 -> 1 (opaque) */
XSetFunction(disp, dst_mask_gc, GXor);
/* copy the pixels through a clipmask */
XSetClipMask(disp, dst_gc, src_mask);
XSetClipOrigin(disp, dst_gc, dp.x, dp.y);
XCopyArea(disp, src_id, dst_id, dst_gc,
sr.x, sr.y, sr.width, sr.height,
dp.x, dp.y);
/* merge opaqueness information */
XCopyArea(disp, src_mask, dst_mask, dst_mask_gc,
sr.x, sr.y, sr.width, sr.height,
dp.x, dp.y);
XSetClipMask(disp, dst_gc, None);
XSetClipOrigin(disp, dst_gc, 0, 0);
XFreeGC(disp, dst_mask_gc);
}
}
The above omits client-side clipping, which in principle can be achieved in much the same way as in fill_rect, except that we must first also clip the source rectangle to the source Bitmap's boundary, to prevent copying pixels from non-existent locations outside the source Bitmap:
Rect clipped; ... /* clip source rectangle to destination's boundary */ clipped = clip_rect(src->bmap->area, sr); dp.x = dp.x + clipped.x - sr.x; dp.y = dp.y + clipped.y - sr.y; sr = clipped;
Inside the clipping loop, the general form of the XCopyArea operation becomes:
XCopyArea(disp, src_id, dst_id, dst_gc, sr.x + clipped.x - dp.x, sr.y + clipped.y - dp.y, clipped.width, clipped.height, clipped.x, clipped.y);
Because clipping may reduce the area to be copied from the source, the second and third lines above replace sr.x and sr.y as the top-left source point.
Note that cases 2 and 4 modify the clipmask, and that case 2 handles the special situation of deleting a fully opaque destination clipmask.
The simplest way to draw text is to rely on the server's algorithms. This is usually very efficient, but can only be guaranteed to work for characters from the ASCII set or possibly from the ISO Latin 1 set (code page 8859-1).
To provide internationalisation in a portable way, a client-side font rendering technique is preferable, because then the glyphs are drawn using a known algorithm from a known font which can be moved to any platform.
The X-Windows Render extension is designed to update the aging X-Windows interface. It acknowledges that modern X clients often render font glyphs themselves and by-pass the existing server-side font rendering techniques because they are dated, and do not scale well for rendering Unicode fonts.
This discussion of a draw_text operation assumes we have a simple client-side font technique, which assumes a font is broken into several Subfonts, each of which stores a part of the font which can be individually loaded for efficiency. We also assume that a Subfont is described by a bitmap, represented as a clipmask.
This is a special form of a Bitmap, in which the image component is empty, but the clipmask is not. Wherever the clipmask is opaque, we draw the current drawing colour; wherever it is transparent we avoid changing any pixels.
Thus, if drawing to a Bitmap using the colour red, we draw red pixels only where the Subfont's clipmask is opaque. If the destination Bitmap has a clipmask of its own, we also make the appropriate pixels opaque within it. Since Bitmaps are a super-set of windows we consider this more general case in this section.
We will assume that we are drawing UTF-8 encoded Unicode text, without paying attention to true internationalisation concerns such as direction of text flow, composing glyphs from multiple characters, or other such difficulties. Assume we have the following defintions:
struct Subfont {
Pixmap clipmask;
};
struct Font {
int height;
int maximum_width;
Subfont * list;
};
struct Graphics {
Bitmap * bmap;
Colour colour;
Display * disp;
GC gc;
Region * clip;
Font * font;
};
char *utf8_to_unicode(char *s, int *nbytes, unsigned long *ch);
Subfont *font_char_info(Font *f, unsigned long ch, int *w);
A Subfont essentially just stores a clipmask, which is a pixmap of depth 1 bit per pixel. A Font is a way of caching Subfonts. We do not need to know the details of how a Font is obtained, except that it stores Subfonts for later use, and knows the height and maximum width of any character in any Subfont. We'll assume that the programmer has already obtained a Font and stored a pointer to it into the destination Graphics object.
Each call of the function utf8_to_unicode decodes the stream of bytes producing one Unicode character, and returning the character in the ch field.
The font_char_info function does two things: it loads the Subfont which is needed to draw the character ch, and returns its width in the w parameter, unless a glyph for that character could not be found, in which case -1 is returned in w. In the following code, if a glyph cannot be found for a character, a hollow rectangle of width 5 pixels is drawn instead.
We will assume that each Subfont is an image containing 256 glyphs in a grid 32 wide by 8 high. The width between each grid line is equal to the Font's maximum_width field. The height between each grid line is given by the Font's height field. Thus, the following lines reveal the top left point (x,y) of any glyph:
h = f->height; ... x = (ch%32) * f->maximum_width; y = ((ch/32)%8) * h;
The following is a simple implementation of draw_text for the X-Windows system, which performs no clipping:
void draw_text(Graphics *dst, Point dp, char *s, int nbytes)
{
int i, x, y, w, h;
unsigned long ch;
Subfont *sub;
Font * f;
Display *disp;
Drawable dst_id;
GC dst_gc;
Drawable sub_clip = None;
Drawable dst_mask = None;
GC dst_mask_gc = NULL;
if (dst->colour.alpha > 0x7F)
return; /* nothing to draw if colour is transparent */
/* destination is a bitmap */
disp = dst->disp;
dst_gc = dst->gc;
dst_id = dst->bmap->image;
if (dst->bmap->clipmask != None) {
dst_mask = dst->bmap->clipmask;
dst_mask_gc = XCreateGC(disp, dst_mask, 0, NULL);
if (dst_mask_gc) {
/* opaque -> 1 */
XSetFunction(disp, dst_mask_gc, GXset);
}
}
/* obtain font to use when drawing */
f = dst->font;
/* draw glyphs */
h = f->height;
while (nbytes > 0) {
cp = &ch;
if ((s = utf8_to_unicode(s, &nbytes, &ch)) == NULL)
break;
sub = font_char_info(f, ch, &w);
if (w < 0) {
/* character glyph not found, draw a box */
XSetClipMask(disp, dst_gc, None);
fill_rect(dst, rect(dp.x,dp.y,1,h));
fill_rect(dst, rect(dp.x,dp.y+h-1,4,1));
fill_rect(dst, rect(dp.x,dp.y,4,1));
fill_rect(dst, rect(dp.x+3,dp.y,1,h));
dp.x += 5;
continue; /* go to next character */
}
/* else, character glyph exists */
x = (ch%32) * f->maximum_width;
y = ((ch/32)%8) * h;
/* set up stencil drawing from the clipmask */
if (sub_clip != sub->clipmask) {
sub_clip = sub->clipmask;
XSetClipMask(disp, dst_gc, sub_clip);
if (dst_mask_gc)
XSetClipMask(disp, dst_mask_gc, sub_clip);
}
XSetClipOrigin(disp, dst_gc, dp.x-x, dp.y-y);
if (dst_mask_gc)
XSetClipOrigin(disp, dst_mask_gc, dp.x-x, dp.y-y);
/* clip to the clipping region */
XFillRectangle(disp, dst_id, dst_gc,
dp.x, dp.y, w, h);
if (dst_mask_gc) {
/* update transparency information */
XFillRectangle(disp, dst_mask, dst_mask_gc,
dp.x, dp.y, w, h);
}
dp.x += w;
/* go to next character */
}
XSetClipOrigin(disp, dst_gc, 0, 0);
XSetClipMask(disp, dst_gc, None);
if (dst_mask_gc)
XFreeGC(disp, dst_mask_gc);
}
Essentially this is just a loop which fetches the next Unicode character to draw, and then draws it using the X-Window's XSetClipOrigin and XSetClipMask features to use the Subfont's clipmask as a stencil, then using XFillRectangle to paint in the currently selected colour where the glyph is opaque. If the destination has a clipmask, we also update it using a second call to XFillRectangle.
Some things are factored outside the loop for efficiency. Because this function draws glyphs one at a time, efficiency is very important. Avoiding spurious calls to XSetClipMask, by only sending a message to the server when the Subfont changes, wins a surprising amount of speed. Traffic to the server is clearly the bottleneck with this implementation.
Drawing text from right to left is not currently handled, but it simply a matter or organising to move the destination point dp to right left by subtracting the glyph's width, rather than adding it. Other internationalisation improvements are clearly needed, but it functions fairly well for many languages. No client-side clipping is performed in the above function, but it is easy to imagine how to add it.
Interestingly, client-side clipping is the only way to clip such glyphs within an arbitrary region on X-Windows, since the function XSetClipMask overrides the server-side clipping function XSetClipRectangles. Because these two functions are mutually exclusive, if we wished to draw half a glyph, in general we cannot do that on the server side. With client-side clipping, however, it is simple: just reduce the size of the rectangle passed to XFillRectangle. We could, of course, clip server-drawn text, but that loses the utility of portable international client-rendered text.
The advantages of such a simple bitmapped implementation of Fonts are that international text can be handled consistently within a program, and across different platforms; that clipping can be achieved correctly; that programs can rely on a font being rendered at a certain size and with particular pixel placements; that the same logic for drawing text can be used even with client-side objects such as Images.
The main disadvantage of this approach is that speed is slower than server-side drawing of text. If fonts are kept as bitmaps on disk, this lowers the quality of text also, since scalable fonts produce better glyphs at large sizes, but there is nothing in the above implementation which assumes the font information requires bitmaps; as long as the font_char_info function can obtain a Subfont clipmask, we do not care whether it comes from a bitmap or a scalable font algorithm.
Efficiency is discussed last since portability has been the motivating factor in the above designs. Earlier the efficiency of client-side clipping concluded that there are cases where a program clearly benefits from that feature, but that an increase in message traffic to the graphics server was also a possible, and undesirable, side-effect.
Let us now consider the efficiency of the entire Bitmap construct. Is joining the concept of a clipmask with a pixmap an efficient plan, or does it necessarily introduce inefficiencies into a program?
The main inefficiency in the Bitmap concept arises from the need to duplicate drawing. Every time the pixmap is updated, the clipmask must be updated correspondingly. This has the potential to double the traffic to the server, and double its work load. This traffic is necessary, however, and would occur even if a more general-purpose clipmasking operation were implemented rather than a single multi-purpose Bitmap concept.
You will have noticed in the above discussions that a special case was repeatedly considered: if we ever know for certain that the clipmask is now totally opaque, we can delete it and remove it from the Bitmap. A Bitmap which has no clipmask is handled as efficiently as an ordinary pixmap, so clearly this is an important special case to consider.
This one special case is likely to improve efficiency quite a lot. It is a common case to create a new Bitmap and fill it with pixels from a window or another Bitmap. In this case, the clipmask can often be discarded, and the efficiency of drawing to and from that Bitmap increases. The most common situations in which pixmaps are used are to store the pixels underneath a temporary window such as a pull-down menu, or to render a prepared image to the screen. In both those cases the Bitmap will usually be fully opaque.
In that case the only inefficiencies lie in creating a clipmask in the first place, and subsquently destroying it (both one-time events), and the cost in conditional statements to test whether clipmasking operations are needed.
The first set of inefficiencies is easy to avoid by having two ways to create a Bitmap: new_transparent_bitmap and new_opaque_bitmap. The first function is needed because the drawing operations we've discussed only ever move clipmasks towards a fully opaque state, never in the other direction, so we need some way to create an initially fully transparent Bitmap. The second function is needed to avoid the one-time creation and destruction of the clipmask.
To avoid the second, less signifcant inefficiency which results from having to test a Bitmap for the existence of a clipmask each time it is drawn into, program profiling is needed. The likelihood is that these if-statement occupy vastly less time than would the message traffic for a drawing operation, and so optimising them would produce no measureable increase in speed.
Nevertheless, one scheme should be mentioned which would probably improve efficiency slightly. It should be noticed that once a Bitmap achieves a fully-opaque state, its clipmask can be deleted, and its efficiency improves. Prior to that it has a clipmask. We could thus entirely avoid the if-statements used to determine if a Bitmap has a clipmask by separating each drawing operation into separate functions, and calling the appropriate function through a pointer.
The Graphics object can be modified to include pointers to the appropriate functions:
struct Graphics {
Bitmap * bmap;
Colour colour;
Display * disp;
GC gc;
Region * clip;
Font * font;
void (*fill_rect)(Graphics *g, Rect r);
void (*copy_rect)(Graphics *g, Point p, Graphics *src, Rect r);
void (*draw_text)(Graphics *g, Point p, char *utf8, int bytes);
};
A Graphics object is obtained through a known, fixed interface. Let's say it's a function called get_graphics. This function can examine the Bitmap passed to it and determine if it has a clipmask, and if so initialise the Graphics object's function pointers to use functions which assume the clipmask is there. Conversely, if it has no clipmask, faster functions can be used. Indeed, whenever the clipmask is deleted from the Bitmap, the functions can be swapped to use faster functions than before.
As stated previously, such a scheme is probably redundant because the inefficiency of a few if-statements is much smaller than the cost of actual drawing requests sent to the server.
In summary, a fully opaque Bitmap can be implemented as efficiently as an ordinary server-side pixmap, if we consider that message traffic to the graphics server, and the server-side implementation, make up the main costs. This is likely to be the case, as if-statements and client-side clipping calculations should occupy little time.
When implementing partially-transparent Bitmaps, we send twice as many messages to the graphics server, to correctly use and update the Bitmap's clipmask, but this would be needed in any use of clipmasks. Joining the idea of clipmasks with pixmaps into a single Bitmap structure simplifies the programmer interface while sacrificing little.
The one situation where efficiency is a concern, is where a clipmask has become fully opaque through several drawing operations, but the drawing operations have been unable to notice this fact. In this case redundant messages to the graphics server will be issued whenever the Bitmap is used, but in general this is a difficult situation to spot using an algorithm, without resorting to an inefficient brute-force technique of reading the clipmask bits back from the server periodically.
In conclusion, this one inefficient case is probably unlikely to be an issue in practice. Most real-world cases will either need the transparency mask each time, to implement partially transparent icons for example, or else will remove the clipmask using the special case of drawing over the entire Bitmap. Both these cases are efficient with the developed code examples, and are likely to be the most common cases.
Are Bitmaps enough? One could argue that keeping the clipmask separate from a Bitmap, and adding the ability to use it as a modifier to drawing operations, would be a scheme equally worthy of consideration. Only having Bitmaps forces all clipmasking activity to go through a Bitmap.
While this is true, it should be said that Bitmaps are all that is needed for most common applications. Adding clipmasking to the drawing model would complicate things slightly, but may be worthwhile in future work. In the mean time, Bitmaps suffice for many cases.