THREE-DIMENSIONAL GRAPHICS USING THE X WINDOW SYSTEM

X can produce reasonably fast and visually acceptable 3-D graphics

The program in Listing One(page 92) uses three matrices to process coordinates through modeling, viewing, and device scaling transformations. The modeling matrix is made of a concate-nation of rotations about the X and Y axes. The matrix is updated to follow mouse movements. The viewing matrix is precomputed to show a perspective view looking at the origin, from a point at (0, 0, - 15). It maps the world coordinates into virtual device coordinates (VDCs), ranging from (0, 0, 0) to (2, 2, 2). The device matrix maps VDC units to device coordinates -- the window coordinates of Xlib.

The VDC to device coordinate transformation is slightly different for X than for most other devices because the size of the X Window "device" can change. The sox11 driver leaves the device coordinate transformation unchanged when a window is resized. If a window shrinks, the driver shows a "porthole" into an image larger than the window. An application programmer can watch for resize events and update device mapping to match the new window size. This gives a "rubber sheet" effect -- the image stretches to match the size of the window. In the program in Listing One, the device transformation matrix is updated whenever the window size changes so that the image maps to the new window size. There is no clipping code in this example; it relies on the object being within the viewing volume.

Partial Polygons

To improve performance, sox11 uses X server polygon drawing routines to draw polygons. This causes a problem with some polygons. The Starbase graphics library supports polygons with holes in them by defining primitives called partial polygons. (The PHIGS graphics standard calls these groups of polygons "Fill Area Sets.") The program in Listing One shows a cube with a hole in one side. The hole in the face of the cube is a partial polygon. Polygons with holes in them are described as a group of partial polygons, followed by a normal polygon. Each polygon or partial polygon is a loop of vertices. These loops may be the outside edges of separate areas, or the outside and inside edges of a single polygon. Xlib does not explicitly support holes in polygons. To use Xlib polygon routines and produce the desired result, the sox11 driver rearranges the vertices and relies on a detail of the definition of Xlib polygons.

X protocol defines that drawing a polygon only affects the pixels that are within the interior, or on an edge other than the right and bottom edges. This allows adjacent polygons to share common edges without both polygons affecting the pixels on the common edges. A mesh of vertices drawn with an exclusive OR won't leave gaps between polygons. As a result, if a polygon is pinched down so that two edges are on the same coordinates, no pixels are changed along the pinched area. All of the pixels are on a right or bottom edge and are therefore left alone. If such a double edge crosses the interior of a polygon, there is no gap where the edges cross the interior.

When asked to draw a complex polygon, the sox11 driver connects the partial polygons to each other by one of these thin double edges. The result is that one loop of vertices drawn by XFillPolygon appears to be multiple disjointed loops. If the polygon is edged, the edges are later drawn along the edges of the partial polygon loops with an XDrawLines call for each smaller loop. Figure 1 shows an example polygon. This polygon is defined to Starbase as a partial polygon, with the vertices numbered 1, 2, 3, 4, and 5; followed by a polygon with vertices numbered 6, 7, 8, 9, and 10. The X server is sent one XFillPolygon request with all of the vertices from 1 to 11. Then the edges are sent as two XDrawLines calls with the vertices of the Starbase partial polygon and polygon calls.

Color Map Support

X protocol deals with many different types of hardware, each of which has a variety of methods for representing and controlling colors. X protocol categorizes the representation of colors into six different visual classes: StaticGray, GrayScale, StaticColor, PseudoColor, TrueColor, and DirectColor. These classes indicate whether a display interprets pixel values as levels of brightness or as indices into tables of colors. They also indicate whether any color tables have writable entries, and whether the bits in a pixel are grouped into particular bits that determine the red, green, and blue brightness of a color. Some displays, such as the HP Turbo SRX, support multiple visual classes at the same time. The sox11 driver supports all six classes of visuals, but I will only discuss the PseudoColor class, because it raises the most interesting issues. A PseudoColor class visual indicates that pixel values are indices into a writable table of colors, called a "color map."

The Starbase library, like most graphics standards, is based on a model of controlling a virtual device. One result is that the library presents color maps as being completely available to application programs. The Xlib concept of color maps is different. Xlib knows that many programs will be executing on one display, and usually must share a single hardware color map. Reconciling these two approaches to color maps can be done in two different ways. Either the library's color indices can be mapped to a different set of allocated Xlib indices, or a new software color map can be allocated by Xlib for the exclusive use of the sox11 driver.

The allocation of individual indices is unsatisfactory if an application uses Boolean pixel changing functions to combine colors on the display. A program may expect to OR together a red color in index 1 and a green color in index 2 to produce a yellow color that it set in index 3. Rearranged color indices will not necessarily produce the expected result.

Allocating a complete color map also has drawbacks. Because most displays only support one color map at a time, the server switches the hardware color map to correctly display the current window. All other windows are then displayed with essentially random colors. This can be visually jarring, making the rest of the windows more eye catching than the supposed center of interest.

The sox11 driver uses some of each color method to avoid most of the weaknesses of each method. The driver starts by using the default X color map. It then allocates a new color map if a program changes any of the color map entries. This means a Starbase program can share the common default color map, as long as it doesn't care about the index values for each color. When a program needs to control the color of particular indices, a full color map is used, which gives the program complete control.

When a color map is allocated, sox11 uses some color map tricks to replace missing Xlib features. The Starbase library defines a control called "display enable." This selects the bits in a pixel that are used to index into a color map. When looking up a color, those bits that are not display enabled are read as zero. Several HP displays provide this control in hardware, but the X protocol does not have this feature. The sox11 driver simulates hardware display enable by rewriting the color map. Thus all indices that differ only by bits in display disabled planes have the same color.

The display enable feature can be used for double buffering. In double buffering, bits in a pixel are divided into two sets. Half of the bits hold the image that is being displayed, while the other half are cleared and redrawn to create a new image. With double buffering, the transition from displaying one image to displaying the next is extremely fast. When the undisplayed image is ready, the color map is rewritten and the new image is displayed in completed form. There is no flicker while the image is changing. This is important for animation, where images are being constantly updated.

Listings Two (page 98) and Three (page 98) show the header declarations and code for an Xlib double buffering utility. This allocates colors from a shared color map, then maps the program's pixel indices to the values returned from Xlib. The utility will only work with PseudoColor class visuals, and will only succeed if there are sufficient free pixels to allocate from the color map.

Hidden Surface Removal

When drawing 3-D objects as wireframe outlines, removal of hidden lines is helpful, but not vital, to the perception of the objects' structures. Perspective projection and the motion of vertices during rotations give clues about the distance of points. When drawing objects with solid faces, removal of surfaces appearing behind other surfaces is very important. The image only makes sense to our eyes if "hidden surfaces" remain hidden.

The sox11 driver does not perform hidden surface removal. An application program using either Xlib or the sox11 driver can do some hidden surface removal before drawing polygons. A program can detect and remove the faces of objects that are directed away from the viewer. A vector pointing perpendicularly out from the face (a "normal"), is either entered as part of the object data, or computed from the vertices of each face. Perspective transformation is applied to this normal vector. If the resulting vector has a negative Z component, then the face is on the back of the object as seen from this viewing position. The back faces can be removed, because they should never be visible. Back face removal detects all hidden surfaces of a single convex object, but won't always be sufficient for multiple or more complicated objects.

Another hidden surface removal method that can be applied by an application program using the sox11 driver is called the "painter's algorithm." This consists of sorting the polygons in an object so that the most distant are drawn first. When two polygons overlap each other on the display, the closer polygon will be drawn last and will cover up the more distant one. The faces of the object drawn by the example program in Listing One have been sorted so that the painter's algorithm applies to those faces that are not back faces. For more general objects, an actual sorting of the faces is required.

The painter's algorithm fails if faces pierce through each other or if a group of faces are arranged to form a cycle of overlapping polygons. If face A hides part of face B, face B hides part of face C, and face C hides part of face A, the polygons cannot be sorted. Another technique must be used. Two possible methods are scan line hidden surface removal or Z buffering. To use either of these techniques with Xlib requires that the conversion from vectors and polygons to scan lines or pixels be done by the client program, instead of the X server. If an application must handle graphics of such complexity, an approach different than layering on Xlib may have to be used. Peer-level interface Starbase drivers perform these hidden surface removal operations quickly, using hardware scan conversion and Z buffering.

Summary

The X Window System produces reasonably fast and visually acceptable 3-D graphics. Depending on application requirements, the existing Xlib graphics interface, extensions to the X protocol, or coexisting peer-level 3-D graphics libraries can be used to provide a variety of capabilities, performance ranges, and portability levels. Xlib calls, which provide the best portability among the currently available X implementations, can be used to implement most features of existing 3-D graphics libraries.

Bibliography

Foley, J.D., and Van Dam, A. Fundamentals of Interactive Computer Graphics, Reading, Mass.: Addison-Wesley, 1982.

Jones, O. Introduction to the X Window System, Englewood Cliffs, N.J.: Prentice-Hall, 1989.

Newman, W.M., and Sproull, R.F. Principles of Interactive Computer Graphics, New York, N.Y.: McGraw-Hill, 1973~

Nye, A. Xlib Programming Manual for Version 11, Newton, Mass.: O'Reilly and Associates, 1988.

Rogers, D.F., and Adams, J. A. Mathematical Elements For Computer Graphics New York, N.Y.: McGraw-Hill, 1976~

_THREE-DIMENSIONAL GRAPHICS USING THE X-WINDOW SYSTEM_ by Michael Stroyan [LISTING ONE]



/* example.c - An example of three dimensional graphics using Xlib. */

#include <X11/Xlib.h>
#include <X11/Xutil.h>
#include <math.h>
#include <stdio.h>
#include "double_buffer.h"

typedef double Transform[4][4];
typedef double Point[3];

Display *display;           /* display connection */
Window window;              /* window identifier */
GC gc;                      /* graphics context */
XColor colors[4];           /* colors to draw with */
double_buffer_state *dbuf_state; /* state record for double buffer utilities */
double_buffer = 1;          /* Whether to use double buffering */
unsigned int width, height; /* last known window size */
Transform model;            /* transform from world to modelling coordinates */
Transform view;             /* transform from modelling to VDC coordinates */
Transform device;           /* transform from VDC to device coordinates */
Transform composite;        /* transform from world to device coordinates */
Transform motion;           /* transform for modelling motion */

identity(transform)
/* Set a Transform matrix to an identity matrix. */
Transform transform; /* transform to operate on */
{
   register int i, j;

   for (i = 0; i < 4; i++)
      for (j = 0; j < 4; j++)
         transform[i][j] = (i == j);
}

rotate_X(transform, angle)
/* Set a Transform matrix to a rotation around the X axis. */
Transform transform; /* transform to operate on */
double angle;        /* angle in radians to rotate by */
{
   identity(transform);
   transform[1][1] = transform[2][2] = cos(angle);
   transform[2][1] = -(transform[1][2] = sin(angle));
}

rotate_Y(transform, angle)
/* Set a Transform matrix to a rotation around the Y axis. */
Transform transform; /* transform to operate on */
double angle;        /* angle in radians to rotate by */
{
   identity(transform);
   transform[0][0] = transform[2][2] = cos(angle);
   transform[0][2] = -(transform[2][0] = sin(angle));
}

transform_point(transform, p, tp)
/* Apply a Transform matrix to a point. */
Transform transform; /* transform to apply to the point */
Point p;             /* the point to transform */
Point tp;            /* the returned point after transformation */
{
   int i, j;
   double homogeneous[4];
   double sum;

   for (i = 0; i < 4; i++) {
      sum = 0.0;
      for (j = 0; j < 3; j++)
         sum += p[j] * transform[j][i];
      homogeneous[i] = sum + transform[3][i];
   }

   for (i = 0; i < 3; i++)
      tp[i] = homogeneous[i] / homogeneous[3];
}

cross_product(v1, v2, c)
/* Compute the cross product of two vectors. */
Point v1, v2; /* the vectors to take the cross product of */
Point c;      /* the result */
{
   c[0] = v1[1] * v2[2] - v1[2] * v2[1];
   c[1] = v1[2] * v2[0] - v1[0] * v2[2];
   c[2] = v1[0] * v2[1] - v1[1] * v2[0];
}

backface(p1, p2, p3)
/* Determine if a polygon is a back face of an object */
Point p1, p2, p3; /* the first three vertices of a polygon */
{
   Point v1, v2, c;

   /* This relies on the first three vertices of each face being clockwise
    * around a convex angle or counter-clockwise around a concave
    * angle as viewed from the front of the face. */
   v1[0] = p2[0] - p1[0];
   v1[1] = p2[1] - p1[1];
   v1[2] = p2[2] - p1[2];
   v2[0] = p2[0] - p3[0];
   v2[1] = p2[1] - p3[1];
   v2[2] = p2[2] - p3[2];
   cross_product(v1, v2, c);
   return(c[2] > 0);
}

concatenate_transforms(transform1, transform2, result)
/* Use matrix multiplication to combine two transforms into one. */
Transform transform1, transform2; /* the transforms to combine */
Transform result;                 /* the new combined transform */
{
   register int i, j, k; /* index variables */
   Transform temporary;  /* a temporary result */
   /* Using a temporary result allows a single transform to be passed in
    * as both one of the original transforms and as the new result. */

   for (i = 0; i < 4; i++) {
      for (j = 0; j < 4; j++) {
         temporary[i][j] = 0.0;
         for (k = 0; k < 4; k++) {
            temporary[i][j] += transform1[i][k] * transform2[k][j];
         }
      }
   }

   for (i = 0; i < 4; i++)
      for (j = 0; j < 4; j++)
         result[i][j] = temporary[i][j];
}

init_X(argc, argv)
/* Initialize the X window system */
int argc;  /* the number of program arguments */
char *argv[]; /* an array of pointers to program arguments */
{
   XEvent event;                /* holds X server events */
   static XSizeHints xsh = {           /* Size hints for window manager */
      (PPosition | PSize | PMinSize), /* flags */
      300,                            /* height */
      300,                            /* width */
      200,                            /* minimum height */
      200,                            /* minimum width */
      5,                              /* x coordinate */
      5                               /* y coordinate */
   };
   static XWMHints xwmh = {      /* More hints for window manager */
      (InputHint | StateHint),  /* flags */
      False,                    /* input */
      NormalState,              /* initial_state */
      0,                        /* icon pixmap */
      0,                        /* icon window */
      0, 0,                     /* icon location */
      0,                        /* icon mask */
      0,                        /* Window group */
   };
   static XClassHint xch = {     /* Class hints for window manager */
      "example",                /* name */
      "EXample"                 /* class */
   };
   XGCValues gcvalues;

   if ((display = XOpenDisplay(NULL)) == NULL) {
      fprintf(stderr, "Can't open %s\n", XDisplayName(NULL));
      exit(1);
   }

   window = XCreateSimpleWindow(display,
       DefaultRootWindow(display),
       xsh.x, xsh.y,   xsh.width, xsh.height,   2,
       WhitePixel(display, DefaultScreen(display)),
       BlackPixel(display, DefaultScreen(display)));

   XSetStandardProperties(display, window, "Example", "Example",
       None, argv, argc, &xsh);
   XSetWMHints(display, window, &xwmh);
   XSetClassHint(display, window, &xch);

   XSelectInput(display, window,
       StructureNotifyMask |
       ExposureMask |
       ButtonPressMask |
       Button1MotionMask |
       PointerMotionHintMask);

   XMapWindow(display, window);
   XFlush(display);

   do {
      XNextEvent(display, &event);
   } while (event.type != MapNotify || event.xmap.window != window);

   gc = XCreateGC(display, window, 0, &gcvalues);
   XSetState(display, gc,
       WhitePixel(display, DefaultScreen(display)),
       BlackPixel(display, DefaultScreen(display)),
       GXcopy, AllPlanes);

   /* black */
   colors[0].red = 0;
   colors[0].green = 0;
   colors[0].blue = 0;

   /* white */
   colors[1].red = 65535;
   colors[1].green = 65535;
   colors[1].blue = 65535;

   /* green */
   colors[2].red = 0;
   colors[2].green = 40000;
   colors[2].blue = 0;

   /* yellow */
   colors[3].red = 65535;
   colors[3].green = 65535;
   colors[3].blue = 0;

   dbuf_state = start_double_buffer(display,
       DefaultColormap(display, DefaultScreen(display)), 2, colors);
   if (dbuf_state == NULL) {
         fprintf(stderr, "Couldn't allocate resources for double buffering\n");
    exit(1);
   }
   XSetPlaneMask(display, gc, dbuf_state->drawing_planes);
}

init_transforms()
/* Initialize transformations for modelling, viewing, and device mapping. */
{
   Window root;
   int x, y;
   unsigned int b, d;

   identity(model);

   identity(view);
   view[2][2] = 2.0;
   view[2][3] = 1.0;
   view[3][2] = 29.0;
   view[3][3] = 15.0;

   XGetGeometry(display, window, &root, &x, &y, &width, &height, &b, &d);
   identity(device);
   device[0][0] = device[3][0] = width / 2.0;
   device[1][1] = device[3][1] = height / 2.0;

   concatenate_transforms(model, view, composite);
   concatenate_transforms(composite, device, composite);
}

#define POINTS 16     /* The total number of unique points */
#define POLYPOINTS 12 /* The maximum number of vertices in a polygon */
#define PARTIALS 6    /* The maximum number of partial polygons in a polygon */

#define END_POLYGON -2         /* designates the end of one polygon */
#define END_POLYGONS -3        /* designates the end of all polygons */
#define END_PARTIAL_POLYGON -1 /* designates the end of a partial polygon */

redraw()
/* Draw the 3d object using the current composite transform. */
{
   static Point points[POINTS] = {
      -4.0, -4.0, -4.0,
       4.0, -4.0, -4.0,
      -4.0,  4.0, -4.0,
       4.0,  4.0, -4.0,
      -4.0, -4.0,  4.0,
       4.0, -4.0,  4.0,
      -4.0,  4.0,  4.0,
       4.0,  4.0,  4.0,
      -2.0, -4.0, -2.0,
       2.0, -4.0, -2.0,
      -2.0,  0.0, -2.0,
       2.0,  0.0, -2.0,
      -2.0, -4.0,  2.0,
       2.0, -4.0,  2.0,
      -2.0,  0.0,  2.0,
       2.0,  0.0,  2.0,
   };
   Point transformed_points[POINTS];
   static int polygons[] = {

      10, 11,  9,  8, 10, END_POLYGON,
      12, 13, 15, 14, 12, END_POLYGON,
      9, 11, 15, 13,  9, END_POLYGON,
      11, 10, 14, 15, 11, END_POLYGON,
      10,  8, 12, 14, 10, END_POLYGON,

      0,  4,  5,  1,  0, END_PARTIAL_POLYGON,
      8, 12, 13,  9,  8, END_POLYGON,

      0,  1,  3,  2,  0, END_POLYGON,
      6,  7,  5,  4,  6, END_POLYGON,
      5,  7,  3,  1,  5, END_POLYGON,
      7,  6,  2,  3,  7, END_POLYGON,
      6,  4,  0,  2,  6, END_POLYGON,

      END_POLYGONS,
   };
   XPoint buffer[POLYPOINTS]; /* a set of Xlib coordinate vertices */
   int partials[PARTIALS];    /* starting points of partial polygons */
   int num_partials;          /* number of partial polygons in a polygon*/
   int src;                   /* an index into buffer[] */
   int dest;                  /* an index into polygons[] */
   int i;                     /* an index into partials[] */
   int at_start_of_polygon;   /* flags the start of each polygon */
   int skip_polygon;          /* flags a backface polygon */

   XSetForeground(display, gc, colors[0].pixel);
   XFillRectangle(display, window, gc, 0, 0, width, height);

   for (i = POINTS - 1; i >= 0; i--)
      transform_point(composite, points[i], transformed_points[i]);

   dest = 0;
   at_start_of_polygon = True;
   partials[0] = 0;
   num_partials = 1;
   for (src = 0; polygons[src] != END_POLYGONS; src++) {
      if (at_start_of_polygon) {
         skip_polygon = backface(
            transformed_points[polygons[src]],
            transformed_points[polygons[src+1]],
            transformed_points[polygons[src+2]]);
         at_start_of_polygon = False;
      }
      switch (polygons[src]) {
      case END_POLYGON:
        if (!skip_polygon) {
           XSetForeground(display, gc, colors[2].pixel);
           XFillPolygon(display, window, gc, &buffer[0], dest,
          Complex, CoordModeOrigin);
           XSetForeground(display, gc, colors[1].pixel);
           partials[num_partials] = dest;
           for (i=0; i<num_partials; i++)
           XDrawLines(display, window, gc, &buffer[partials[i]],
               partials[i+1] - partials[i], CoordModeOrigin);
      }
      dest = 0;
      at_start_of_polygon = True;
      break;
      case END_PARTIAL_POLYGON:
      partials[num_partials++] = dest;
      break;
      default:
      buffer[dest].x = transformed_points[polygons[src]][0];
      buffer[dest++].y = transformed_points[polygons[src]][1];
      break;
      }
   }
   if (double_buffer) {
      double_buffer_switch(dbuf_state);
      XSetPlaneMask(display, gc, dbuf_state->drawing_planes);
   } else {
      XSetPlaneMask(display, gc, AllPlanes);
   }
   XFlush(display);
}

main(argc, argv)
char *argv[];
{
   XEvent event;             /* holds X server events */
   int x, y;                 /* the last X pointer position */
   int new_x, new_y;         /* a new X pointer position */
   unsigned int mask;        /* mask of button and modifier key state */
   unsigned int dummy;       /* placeholder for unwanted return values */

   init_X(argc, argv);
   init_transforms();

   printf("Drag button 1 to rotate the object.\n");
   printf("Press button 2 to toggle double buffering on and off.\n");
   printf("Press button 3 to stop the program.\n");

   for (; ; ) {
      XNextEvent(display, &event);
      switch (event.type) {
      case DestroyNotify:
         XCloseDisplay(display);
         exit(0);
         break;
      case Expose:
         if (event.xexpose.count == 0) {
            redraw();
         }
         break;
      case ConfigureNotify:
         if ((event.xconfigure.width != width) ||
         (event.xconfigure.height != height)) {
         width = event.xconfigure.width;
         height = event.xconfigure.height;

         device[0][0] = device[3][0] = width / 2.0;
         device[1][1] = device[3][1] = height / 2.0;

         concatenate_transforms(model, view, composite);
         concatenate_transforms(composite, device, composite);
         redraw();
        }
        break;
      case MotionNotify:
         XQueryPointer(display, window,
             &dummy, &dummy,
             &dummy, &dummy,
             &new_x, &new_y,
             &mask);
         if (!(mask & Button1Mask))
            break;
         rotate_X(motion, M_PI / 360.0 * (new_y - y));
         concatenate_transforms(model, motion, model);
         rotate_Y(motion, -M_PI / 360.0 * (new_x - x));
         concatenate_transforms(model, motion, model);
         x = new_x;
         y = new_y;
         concatenate_transforms(model, view, composite);
         concatenate_transforms(composite, device, composite);
         redraw();
         break;
      case ButtonPress:
         x = event.xbutton.x;
         y = event.xbutton.y;
         if (event.xbutton.button == 2)
            double_buffer ^= 1;
         if (event.xbutton.button == 3)
            exit(0);
         break;
      default:
         break;
      }
   }
}

[LISTING TWO]



/* double_buffer.h - declarations for an Xlib double buffering utility. */

/* double buffering state record */
typedef struct {
   Display *display;
   Colormap cmap;
   long drawing_planes;     /* planes currently drawn to */
   int buffer;              /* which buffer to show, even or odd */
   XColor *colormaps[2];    /* color maps for even and odd buffers */
   int map_size;            /* number of entries in color maps */
   long masks[2];           /* write_enable masks for odd and even */
   long *planes;            /* individual planes */
   long pixel;              /* pixel base value of double buffering */
} double_buffer_state;

/* double buffering procedures */
extern double_buffer_state *start_double_buffer();
extern void double_buffer_switch();
extern void end_double_buffer();

[LISTING THREE]



/* double_buffer.c - an Xlib double buffering utility. */

#include <X11/Xlib.h>
#include <malloc.h>
#include <stdio.h>
#include "double_buffer.h"

static void release(state)
register double_buffer_state *state;
/* Release a possibly partially allocated double buffer state record. */
{
   if (state != NULL) {
      if (state->colormaps[0] != NULL) free(state->colormaps[0]);
      if (state->colormaps[1] != NULL) free(state->colormaps[1]);
      if (state->planes != NULL) free(state->planes);
      free(state);
   }
}

static long color(state, simple_color)
register double_buffer_state *state;
register long simple_color;
/* Map the supplied color into the equivalent color
 * using the double buffered planes. */
{
   register long i, plane, computed_color;

   computed_color = state->pixel;
   for (plane = 1, i = 0; simple_color != 0; plane <<= 1, i++) {
      if (plane & simple_color) {
         computed_color |= state->planes[i];
         simple_color &= ~plane;
      }
   }
   return(computed_color);
}

double_buffer_state *start_double_buffer(display, cmap, planes, colors)
Display *display;
Colormap cmap;
long planes;    /* how many planes for each buffer */
XColor *colors; /* color settings for buffers */
/* Start double buffering in given number of planes per buffer.
 * If resources can be allocated, then set color pixels in colors parameter
 * and return the address of a double_buffer_state record.
 * Otherwise, return NULL.  */
{
   register double_buffer_state *state;
   register long i, high_mask, low_mask;

   /* Allocate memory. */
   state = (double_buffer_state *) malloc(sizeof(double_buffer_state));
   if (state == NULL)
      return (NULL);

     state->map_size = 1 << (2 * planes);
     state->colormaps[0] = (XColor *) malloc(state->map_size * sizeof(XColor));
     state->colormaps[1] = (XColor *) malloc(state->map_size * sizeof(XColor));
     state->planes = (long *) malloc((2 * planes) * sizeof(long));
     if (state->colormaps[1] == NULL || state->colormaps[0] == NULL
      || state->planes == NULL) {
      release(state);
      return(NULL);
     }
     state->display = display;
     state->cmap = cmap;

   /* Get colors to double buffer with. */
   if (XAllocColorCells(state->display, state->cmap, False,
      state->planes, 2*planes, &state->pixel, 1) == 0) {
      release(state);
      return(NULL);
   }

   /* Prepare the write enable masks. */
   state->masks[0] = AllPlanes;
   state->masks[1] = AllPlanes;
   /* Mask 0 won't write in the "low" planes. */
   /* Mask 1 won't write in the "high" planes. */
   for (i = 0; i < planes; i++) {
      state->masks[0] &= ~state->planes[i];
      state->masks[1] &= ~state->planes[planes + i];
   }

   /* Prepare the flags and pixel values for each color. */
   for (i = 0; i < (1 << planes); i++) {
      colors[i].pixel = color(state, i | (i << planes));
      colors[i].flags = DoRed | DoGreen | DoBlue;
   }

   /* Prepare the two color map settings. */
   /* Colormap 0 displays the "low" planes. */
   /* Colormap 1 displays the "high" planes. */
   low_mask = (1 << planes) - 1;
   high_mask = low_mask << planes;
   for (i = state->map_size - 1; i >= 0; i--) {
      state->colormaps[0][i] = colors[i & low_mask];
      state->colormaps[0][i].pixel = color(state, i);

      state->colormaps[1][i] = colors[(i & high_mask) >> planes];
      state->colormaps[1][i].pixel = color(state, i);
   }

   /* Set up initial color map and write_enable. */
   state->buffer = 0;
   state->drawing_planes = state->masks[state->buffer];
   XStoreColors(state->display, state->cmap,
      state->colormaps[state->buffer], state->map_size);

   return(state);
}

void double_buffer_switch(state)
register double_buffer_state *state;
/* Change double buffering buffer.
 * Return the new planes mask for double buffering. */
{
   /* Toggle the buffers. */
   state->buffer ^= 1;

   /* Adjust the color map and write enable mask. */
   XStoreColors(state->display, state->cmap,
      state->colormaps[state->buffer], state->map_size);

   state->drawing_planes = state->masks[state->buffer];
}

void end_double_buffer(state)
register double_buffer_state *state;
{
   XFreeColors(state->display, state->cmap,
      &state->pixel, 1, ~(state->masks[0] & state->masks[1]));
   release(state);
}