Lab 4: Practice

In this lab you will write a small number of slightly longer, more complex functions. The algorithms required are not difficult, but you will need to think carefully about the requirements, and test your code thoroughly to meet them. These exerises are chosen because it is easy to get them nearly right, but they may require some thought to get exactly right.

Purpose and Outcomes

  1. Experience setting up the working directory with required headers, Makefile, etc.
  2. More practice with following detailed requirements.
  3. More practice with loops, functions and arrays.
  4. Testing and debugging practice.

Setup

  1. In your CMPT 127 working directory, create the directory "4", add it to the repo, and make it the current directory: 
    $ mkdir 4
$ svn add 4
$ cd 4

Requirements for all tasks

  1. These rules apply to all tasks. Substitude the task number for "X" in the following rules.
  2. You may use any function from Lab 3's "imgops.c" to help you.
  3. The test server will use only your source file named "tX.c" file for each task X, e.g. "t1.c", and link it's own main() and a reference implementation of "imgops.c".
  4. You should copy and modify any helpful Makefile, headers, and/or source from Lab 3 to help you write a test program. You should probably use the visualization code in "draw.c" to help debug.
  5. Your source file can contain other functions as long as they do not have the same names as any function in Lab 3's "imgops.c". If you want to call functions from "imgops.c", compile that file into your program: do not paste those functions into "tX.c".
  6. Do not define a main() function in "tX.c": this will prevent it building on the test server. Your main() shoud be in another file, which will not be graded.
  7. Do not use any functions from "draw.h" in "tX.c": these can be used in your test program but not in the submitted file itself.

Task 1: draw_circle()

You must write a function that draws a filled circle into an image array of the same type as in Lab 3.

Requirements

  1. Create and add a single C source file called "t1.c".
  2. "t1.c" should contain the function draw_circle() and agree exactly with this function declaration: 
    void draw_circle( uint8_t img[], 
                  unsigned int cols,
                  unsigned int rows,
		  int x,
		  int y,
		  int r,
		  uint8_t color );
  3. The image array img, and its sizes (cols,rows) should be interpreted in the same way as for Lab 3.
  4. The function draws a filled circle in the image array in the specified color.
  5. The center of the circle is at the center of the pixel at the coordinate {x,y} and it has the specified radius in pixels.
  6. Note that x and y may fall outside the image.
  7. On return, every pixel that contains a point inside the defined circle i.e. (distance to {x,y} < radius (NOT <= radius) ) must be set to color. Do not set the color of any other pixel.
  8. For a radius of zero, do not set any pixels.
  9. When rounding floating point calculations, round to the nearest integer, with 0.5 rounded up to 1.

Example

You might find these examples helpful for interpreting the specs. In every case the image array img has been zeroed in advance. 

draw_circle( img, 16 16, 8, 8, 1, 255);

Note: this is 9 white pixels in the center of the image. Why does a radius of 1 cause 9 pixels to be filled? We are considering all the points in the pixel and not just the point at the centre of the pixel. This diagram shows all the pixels that contain points less than R=1 from the center of the pixel at (x,y): 

 for( int i=10; i>0; i-- )
    draw_circle( img, 64, 32, 32, 16, 2*i, 200/i+55);

Task 2: draw_rectangle()

Draw the outline of a rectangle in the specified color.

Requirements

  1. Create and add a single C source file called "t2.c".
  2. "t2.c" should contain the function draw_rectangle() and agree exactly with this function declaration: 
    void draw_rectangle( uint8_t array[], 
		          unsigned int cols, 
		          unsigned int rows, 
		          int x,
		          int y,
		          int rect_width,
		          int rect_height,
		          uint8_t color );
  3. The rectangle edges are aligned with the x,y axes.
  4. A corner of the rectangle is at the pixel at coordinate {x,y}, and the rectangle is rect_width pixels wide by rect_height pixels tall.
  5. Each rectangle size may be negative, extending the rectangle to the left and/or up, or positive, extending right and/or down.
  6. A rectangle wih zero in either dimension should not be drawn.
  7. The rectangle outline is one pixel thick.

Example

draw_rectangle( img, w, h, w/2, h/2, -5, -5, 128 ); 
draw_rectangle( img, w, h, w/2, h/2, 5, 5, 255 );

Task 3: life()

Compute one step of Conway's Game of Life. The rules and history of the Game of Life can be found here.

Summary

The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

  1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
  2. Any live cell with two or three live neighbours lives on to the next generation.
  3. Any live cell with more than three live neighbours dies, as if by overcrowding.
  4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed - births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the preceding one). The rules continue to be applied repeatedly to create further generations.

Requirements

  1. Create and add a single C source file called "t3.c".
  2. "t3.c" should contain the function life() and agree exactly with this function declaration: 
      void life( uint8_t array[], 
	     unsigned int cols, 
	     unsigned int rows );
  3. Edge pixels wrap around left-right and top-bottom, creating a torus topology rather than the infinite grid of Conway's original.
  4. 'Off' pixels have the value 0.
  5. All non-zero values are considered 'On' pixels.
  6. New 'on' pixels are set to 255.
  7. New 'off' pixels are set to 0.

Examples

Your function must correctly compute a single step of Life, so that it can be used in a loop to create a Life simulation as shown here. 

  int glider[][2] = { {1,0}, {2,1}, {0,2}, {1,2}, {2,2} };   

  for( int i=0; i<5; i++ )
    set_pixel( img, w, h, glider[i][0], glider[i][1], 255 );
  
  for( int i=0; i<32; i++ )
    { 
      draw_image_grey( img, w, h );
      life( img, w, h );
    } 
  draw_image_grey( img, w, h );
(back where we started!)

End of lab.