CS 248: Midterm Solutions

Question 3

Grader: Greg Humphreys


This question asked about the treatment of RGB and color index representation in a system that allows multiple windows.

The problem with this system is that the system needs to know how to interpret the contents of the framebuffer at each pixel. Each pixel may be a true RGB value, or it may be an index into a colormap. Additionally, the system may support multiple colormaps.

The best way to solve this problem is to store a bit along with the pixel that says whether the pixel is to be interpreted as RGB or color index. This can be implemented efficiently by simply having a separate buffer that has one bit per pixel. Note that this system would only allow one global colormap. Some window systems that only have one colormap switch the colormap whenever the "focus" window changes (this is why X-windows colors sometimes flash when you move your cursor into, say, Netscape). This limitation could be overcome by storing more than one bit with each pixel, which would give you 2^N-1 colormaps (where N is the number of bits), and an RGB representation.

Many people misinterpreted the question to be asking about simply how to handle multiple colormaps, and didn't say anything about RGB.

Another common mistake was to simply say that we could pick one representation or the other, and force all windows to exist in that represenation. It is not possible to do the color index lookup BEFORE the framebuffer (storing RGB in the framebuffer always), since another application may need to change the colormap (we showed an example of this in class). Similarly, storing RGB in color-index mode would require an enormous colormap, which would be very inefficient.

2.5 points were given for correctly identifying the problem.
2.5 points were given for saying how to distinguish between RGB and color index modes
2.5 points were given for saying something about different colormaps (either more bits or changing the global colormap were fine).


This question basically boiled down to, "How do you render into a window that's partially obscured without destroying the contents of the windows on top?"

There are a few ways to do this, some of which are more efficient than others. The efficiency of each scheme changes depending on what you're rendering, and how obscured the window is.

The simplest thing to do is to keep a "window-id" buffer, where each pixel has a value associated with it that uniquely identifies the window that "owns" that pixel. Then, each pixel generated by any rendering library would simply carry with it the window ID of the window being rendered to, and the pixel fragment would be rejected if it does not match the ID in the framebuffer.

Another approach is to dynamically compute the rectangular extents of all windows that obscure the window in question, and manually clip all primitives to the window boundaries before rendering them. This can potentially be very expensive, and is typically not what is done in practice. Some students made the clever suggestion of manually setting the alpha of any pixel fragment that fell outside the visible region of the window to zero, and setting the blending mode to OVER.

One approach that was suggested by a number of students was to render each window into an off-screen buffer, and manually composite the images by simply drawing them back-to-front. While this approach will work in theory, it has astronomical memory requirements, and is not a practical solution to the problem.

5 points were given for saying that you needed to reject pixel fragments
2.5 points were given for correctly using the window-id buffer
7.5 points were given for describing the clipping algorithm.

1 point was lost for using the process-ID instead of the window-ID; this doesn't work because one process could have two windows that overlap.
5 points were lost for the off-screen rendering approach.