Specifications

To improve the visual quality of the game, you must optimize the remaining 192 colors for the photo being displayed

and adjust these colors whenever the player moves to a new room. Color optimization requires that you implement an

algorithm based on octrees, which will be explained later.

Final CP: Tux Controller Serial Port Device This portion of the MP is due on the ﬁnal due date. A

subsequent document will be released with the tux controller requirements. Your requirements in the game are:

• Display the elapsed time (minutes.seconds) on the 7-segment displays.

• Up/down/left/right on the tux controller have the same affect as the keyboard’s keys.

• A/B/C on the tux controller should have the same affect as Ins/Home/PgUp.

Final CP: Color Clustering using Octrees The Task: The graphics mode used in MP2 provides a 320× 200

display in which each pixel color is speciﬁed using one byte. The 8-bit value for a given pixel is used as an index into

a palette of 256 colors, each of which is selected from one of 2

possible colors. These palette colors, as you should

know from the pre-lab, are stored in VGA memory by writing three bytes corresponding to the red, green, and blue

components of a color. The two most signiﬁcant bits in each byte are ignored, leaving six bits (0 to 63) for red (R), six

bits for green (G), and six bits for blue (B).

In contrast, many image formats provide 24-bit RGB color for each pixel. The .photo ﬁles in the distribution have

been transformed into a smaller format in which each pixel is represented with a 16-bit value in which the ﬁve most

signiﬁcant bits form a red component, the middle six bits form a green component, and the ﬁve least signiﬁcant bits

form a blue component. Visually, you have bits as shown here: RRRRRGGGGGGBBBBB.

The code that we distributed to you maps these 16-bit values into the ﬁrst 64 VGA palette colors, which have been set

up for you (in modex.c) to provide 6-bit RGB colors (two bits each). These colors are also used for objects in the

game, and you must not change them. The other 192 colors are free for your use in selecting colors that best represent

the content of an individual room photo.

Your task, then, is to implement an algorithm that examines the 16-bit pixels for a single room photo, selects 192

colors that enhance the visual quality of the photo, transform the image data stored in the ﬁle into a C array containing

appropriate bytes (one-byte VGA colors), and set the VGA palette registers to the colors that you have selected when-

ever that particular photo is displayed by the game.

Octrees:

The most common algorithms for mapping the multitude of colors that comprise a typical image into a smaller number

for display on a computer screen make use of octrees, or degree eight trees. Each level of such a tree categorizes pixels

based on one bit of red, one bit of green, and one bit of blue. The eight possible children for a node correspond to the

eight possible values of these bits.

An example using two colors (one level of a quadtree) is shown to the right. Here,

pixels corresponding to colors with the most signiﬁcant bit of both their red and blue

components equal to 0 are added into the lower left quadrant of the tree. Those with

blue MSB equal to 1 and red MSB equal to 0 are added to the upper left quadrant. And

so forth. Each quadrant can then be subdivided into four parts based on the second

MSB of red and the second MSB of blue. And the process can continue as long as we

have bits of colors left.

In the ﬁrst level of an octree, we also make use of the green component’s MSB, result-

ing in eight octants. Each of these octants can then be subdivided into eight octants

based on the second MSB, and so forth. With 5:6:5 RGB, we could in theory build a

tree six levels deep, but our algorithm will make use of only four levels.

An octree need not be built as a pointer-based data structure. In fact, we strongly recommend that you not try to follow

such an approach. Since each level contains exactly eight children for each node, each level ﬁts easily into an array.

For example, the ﬁrst level is an array of eight elements indexed by a concatenation of the RGB MSBs. The second