Exercises Computer Graphics

Session 2 - Bitoperations



Useful Links:


Decades ago, graphics acceleration cards were not as good as today. These were the days of CGA, 16-color EGA and 256-color VGA. In this lesson, we will study these video-modes, both to show how these modes operated, and to get acquainted with low-level bit-manipulation.

Because Processing does not really support these modes, you have to code against a small Screen data type included in the exercises file, rather than calling the Processing drawing API explicitly. The Screen object supports a more low-level addressing mode. The figure below demonstrates the structure of the screen for a 16x8 screen supporting 256 colors.


Each pixel on the screen is represented as a byte (8 bits). This byte is a number between 0 and 255 and is used as an index into a datastructure called the "palette". A palette maps the 256 different indices to 256 different colours. The colours are represented as 32-bit integers, formatted as an RGB-value 0xAARRGGBB, where AA is the colour's "alpha" value, representing its transparency.

32-bit microprocessors cannot address individual bytes. Instead, you can only address 32-bit "words" (usually represented using the int type). Our Screen abstraction supports two primitive operations: one can read 4 pixels simultaneously using a call to screen.get(int index), and one can write 4 pixels to the screen simultaneously by calling screen.put(int index, int pixels). Note that, by representing 4 pixels using one int that we represent a screen of width pixels using only width/4 integers. The height of the screen remains unchanged. Physically, our 2D screen is represented in memory as a 1D array, so our 16x8 screen is actually an array of 32 ints (= 16/4 * 8), indexed from 0 to 31. This is shown in the figure below:

Physical Screen

To manipulate pixels within words (ints) you will need to use bitoperations. The usual bitoperations include AND (x&y), OR (x|y), XOR (x^y), NOT (~x), left shift (x<<y), right shift (x>>y) and unsigned right shift (x>>>y), where x and y are integers. You can experiment with them by printing out their result in hexadecimal form using hex or in binary form using binary. Here is an example of how to extract the green colour value of an RGB colour:

    color c = color(0,177,255);
    println(c); // -16731649
    println(hex(c)); // 0xFF00B1FF
    int g = (c >> 8) & 255;
    println(g); // 177
    println(hex(g)); // 0x000000B1

To extract the green colour part, we first shifted the colour 8 bits to the left, such that the 8 bits representing green become the least significant bits. Then, we set all other bits to 0 by performing a binary AND operation with the number 0x000000FF (which is the hexadecimal representation of 255). This works, because x&0 is always 0, and x&1 is always x.

When setting individual pixels, you will need to be careful not to override the surrounding pixels in the same word. Say you want to change the second pixel in word 0x01020304 to 05. You should be careful not to override this word with 0x00050000, which is the word encoding the value of the second pixel. Rather, you need to combine the word (which we will call the "background") with the value of the pixel (which we will call the "foreground"). This combining is usually done with bitmasks. A bitmask is used to indicate which pixels should be left unchanged by an operation, and which should not. Here is one way to combine background and foreground using bitmasks:

    int foreground = 0x00050000;
    int background = 0x01020304;
    int mask = 0xFF00FFFF;
    println(hex(background & mask)); // 0x01000304
    println(hex((background & mask) | foreground)); // 0x01050304

Note the combination of background with foreground using |. This works because 0|x is always x, so the other pixels will remain intact.


Exercise 1: Vertical Lines

Write a procedure that draws a vertical line in 320x200x8 mode. Start from the following example code.

Vertical Line

Exercise 2: Horizontal Lines

Write a procedure that draws a horizontal line as fast as possible. Make sure horizontal and vertical lines can cross correctly.

Horizontal Line

Valid HTML 4.01 Transitional ©2008-2009 Tom Van Cutsem