Assignment 2: Raster Graphics

Upon completion of this assignment you will have a working Haskell program that converts shapes (including points, rectangles, polygons, and circles) into raster graphics that can be rendered directly onto a bitmapped display screen at arbitrary pixel size.

Introduction

This assignment continues on from your previous assignment, but considers the situation where there might not be an API like CodeWorld for drawing shapes on the screen. In particular, when drawing pictures on a modern bitmapped computer display we need to be aware of the fact that they are composed of discrete picture elements, called pixels, arranged in a grid or raster. This word is derived from the Latin word for “rake”, rastrum. Rasterisation means rendering an abstract (or mathematical) description of an image into a raster representation of that image. In your previous assignment you drew shapes using the shape drawing functions of CodeWorld. In this assignment you will convert shapes directly to raster images, which can be rendered directly to the display.

Learning Objectives

Successful completion of this assignment will:

• Consolidate your understanding of lists and their manipulation.
• Expand your ability to implement classical iterative algorithms in Haskell.
• Deepen your understanding of abstraction and separation of concerns.
• Understand the model-view-controller software pattern for building graphical user interfaces.
• Broaden your experience in managing input from users via event handling.

Marks

This assignment is worth 12% of your total marks for the course. A mark breakdown is provided below alongside each of your assignment tasks. Your program code will be marked for both functionality and style. Your report will be marked for coverage of and insight on the work you have done, what you have learned, and where you might have done better.

---

Setting things up

1. Go to the assignment’s gitlab repository: https://gitlab.cecs.anu.edu.au/comp1100/comp1100-assignment2. You will need to log in if you are not already.

2. Click on the Fork button to create your own private version of the assignment, so you can work on it independently from everyone else.

3. Click on your name and wait a little while.

4. Your web page should automatically refresh, and if everything went well, display your repository containing the assignment files. You can check this by looking above the banner “The project was successfully forked.”, it should display your name instead of comp1100.

5. Click on “Overview” in the menu on the left.

6. Next to the “Fork” button in your repository, there is a button which says “SSH”. Click on it and switch it to “HTTPS”.

7. Copy this URL.

8. Open IntelliJ. If some other project opens up then close the window: click on the menu File at the top of the IntelliJ window and select Close Project.

9. In the IntelliJ IDEA window, click on Check out from Version Control and select Git.

10. Paste the URL that you copied above into the Clone Repository dialogue box as the Git Repository URL. Set Parent directory where you want your working directory to be created (say ~/comp1100), and leave the directory name as comp1100-assignment2.

11. Click Clone and follow the same IntelliJ steps as Lab 2 starting from the clone step. Make sure you add the upstream remote:

    git remote add upstream https://gitlab.cecs.anu.edu.au/comp1100/comp1100-assignment2.git

Using multiple machines

You may want to work on your own personal computer for this assignment, as well as working in the lab. You can set up an IntelliJ project, cloning your project from GitLab to your personal computer in much the same way, by following the steps starting from the step “Copy this URL” set in bold typeface above.

However, when you switch from computer A (say the labs) to computer B (say your personal computer) you should make sure to commit and push all of your changes back to GitLab from computer A, so you can pull them to computer B before resuming work. Every work session should thus proceed as follows:

1. git pull
2. Do some work…
3. git commit -a -m ""
4. git push

When you switch to a different machine, use that same sequence. In short, always pull before you start, and always commit and push when you finish.

---

Framework

This assignment has a framework that is similar to that of Assignment 1, though the user interactions are slightly more sophisticated, though hopefully self explanatory.

Model.hs

The file src/Model.hs contains familiar looking definitions of types that represent the problem domain (similar to those of the previous assignment), independently of any specific user interface. These type definitions allow us to capture the user’s intent to create shapes using shape-drawing tools that can be selected by the user, and to draw those shapes as bitmaps on screen, at a pixel resolution selected by the user. Take a look at these types now, and make sure you understand them. The initial model has no shapes defined, with resolution set to 1.

Controller.hs

The file src/Controller.hs implements the GUI-based mouse and keyboard input functionality of the application, allowing users to:

1. revert to the initial model having no shapes by typing Esc
2. display the current model on the console by typing D
3. delete the last shape added by typing Backspace or Delete
4. set the pixel resolution to 1/10 $1/10$ by typing 0
5. set the pixel resolution to 1/k $1/k$ by typing one of the digits 1 through 9
6. halve the pixel resolution by typing -or ,
7. double the pixel resolution by typing = or .
8. switch the current shape drawing tool by typing t
9. switch the colour to use in drawing by typing c
10. complete a polygon by typing ` ` (space bar)
11. set a control point for the current shape by clicking the mouse
12. complete a shape by releasing the left mouse button (except for polygons, which are added by typing ` `, as above)

Take a close look at the code and reflect on your work in the last assignment.

View.hs

Your work for the required portion of this assignment will be done in the file src/View.hs. This file is responsible for rendering the model as graphics on the display. Unlike the previous assignment, here we will not be using the built-in Codeworld API functions for drawing shapes. Instead, your task is to implement displaying of shapes as raster graphics. The function shapeToRaster chooses for a given shape which raster generation function to use. We have already provided you with the implementation of the function that draws a point on the screen at a given coordinate. Your task in this assignment is to complete each of rectangle, line, circle, ellipse, and polygon, as described below.

---

Building, running, interacting

Once again, we are using cabal: a build tool for Haskell that avoids the need to build all of the pieces of your project separately by hand.

There are several useful commands for cabal:

• cabal build

  This will compile all of the necessary Haskell files needed for the programs.

• cabal run

  These will run the program, compiling your Haskell files as necessary.

• cabal repl

  This is probably where you will be spending most of your time trying out your code. REPL stands for Read-Eval-Print Loop. This will launch a GHCi interactive environment and load the program files.

• cabal clean

  This will delete any build files and can be useful if the files become corrupted or you just want to build everything afresh. This will not delete any important files such as your source code programs.

• cabal reconfigure

  This will reconfigure the project for the operating system of your computer. Sometimes you will need to do this after upgrading the OS or Haskell itself. Otherwise there are not many reasons to do this.

You must execute these cabal commands in the top-level directory of your project (the default directory for the IntelliJ Terminal tool for your project): ~/comp1100/comp1100-assignment2 if you set the parent directory to be ~/comp1100 as suggested above.

Try running the program now using cabal run. Open the indicated URL in a browser. The point tool will be active by default. Click on the coordinate grid with the left mouse button and you will see a pixel appear at resolution 1.0. Change the resolution to 110  $\frac{1}{10}$ by typing 0 0 . You will see the size of the pixel shrink to one tenth of its original size, and at a position that is closer to where you clicked the mouse. Increase the pixel size by typing = a few times. You will be able to test the implementations of your shape drawing functions similarly, making sure that they function properly over a range of pixel resolutions.

---

Tasks [total 70 marks]

Your goal is to enable the user to draw rectangles, lines, polygons, circles, and ellipses, by completing the corresponding function definitions in src/View.hs.

Recall that a circle with centre at coordinate (0,0) $(0,0)$ is defined by the equation x 2 +y 2 =r 2  $x^2+y^2=r^2$ , where x x and y y are the points on the circumference of the circle with radius r r .

Similarly, an ellipse with centre at coordinate (0,0) $(0,0)$ is defined by the equation x 2 a 2  +y 2 b 2  =1 $\frac{x^2}{a^2}+\frac{y^2}{b^2}=1$ , where x x and y y are the points on the circumference of the ellipse with semi-major axis a a , and semi-minor axis b b .

Note that a circle is simply a degenerate ellipse where r=a=b $r=a=b$ so that we have x 2 r 2  +y 2 r 2  =x 2 +y 2 r 2  =1 $\frac{x^2}{r^2}+\frac{y^2}{r^2}=\frac{x^2+y^2}{r^2}=1$ , which yields the circle equation by multiplying both sides by r 2  $r^2$ .

1. Rectangles (rectangle) [5 marks]

Given two coordinates that specify the opposing corners of a rectangle, function rectangle must generate a list of pixels with coordinates that lie on the boundary of the rectangle, and having shade 1.0 (opaque). Note that the input coordinates can be given in any order.

Hint: using list comprehensions you can enumerate the pixels over the range of the x x and y y coordinates of the sides of the rectangle. Be careful for rectangles that have zero width/height, or width/height of only one pixel, making sure that all pixels on the resulting raster have unique coordinates.

This property applies to all shapes: no two pixels in a shape raster can have the same coordinates.

The following Haskell code entered into GHCi produces the resulting picture (remember to use cabal repl to load your assignment code into GHCi):

drawingOf $ updateView $ Model [(Black, Rectangle (0,0) 4 2)] (RectangleTool Nothing) Black 1 

Adjust the pixel resolution to see a finer-grained raster:

drawingOf $ updateView $ Model [(Black, Rectangle (0,0) 4 2)] (RectangleTool Nothing) Black 0.1 

2. Lines (line) [15 marks]

Bresenham’s line algorithm (see references ¹) is lauded as a seminal work that shaped the field of computer graphics. It is an efficient algorithm for drawing lines on a raster display. Your task is to implement this algorithm or its variant.

There are various descriptions of Bresenham’s algorithm online. If you use them to understand the algorithm, remember to cite them in your report!

It is even possible to find implementations of the algorithm in Haskell, such as implementations on Rosetta stone website and in Haskell wiki, among others. Although you can read and analyse code available online, it is imperative that you do not copy any part of it.

Use online resources for your learning (again, remember to cite them!), but do not look at any implementation in Haskell while writing your own code!

The following Haskell code entered into GHCi produces the resulting picture:

drawingOf $ updateView $ Model [(Black, Line (-10,0) (10,5))] (LineTool Nothing) Black 1 

3. Polygons (polygon) [10 marks]

Once you have your line drawing algorithm working, you can use it to draw polygons. A closed polygon, defined by a sequence of vertices, is simply the line segments formed between each successive pair of vertices in the sequence, plus a line segment between the first and last vertices in the sequence.

Here is an example:

drawingOf $ updateView $ Model [(Black, Polygon [(-3,0),(0,2),(3,0),(0,-2)])] (PolygonTool []) Black 0.1 

4. Circles (circle) [20 marks]

Bresenham’s algorithm for lines can be extended to draw circles, see for example the midpoint circle algorithm.

Your task is to implement function circle in View.hs. Again, there are many sources of information and Haskell code online. You can analyse, for example, the version available in RosettaStone.

Close any Haskell implementation you find online before coding! Do not copy any part of it. You must produce your code yourself.

Note that due to the circle’s symmetry, it is enough to calculate points in one octant only (for example, in the first 45° of the circle) and for each such point to determine the symmetry points in other seven octants.

If the centre (a,b) of a circle with radius r is not at coordinate (0,0), you can translate a circle with radius r centred at (0,0) to a circle centred at (a,b).

Here is an example of a circle:

drawingOf $ updateView $ Model [(Black, Circle (0,0) 9)] (CircleTool Nothing) Black 1 

And the same circle with a different resolution:

drawingOf $ updateView $ Model [(Black, Circle (0,0) 9)] (CircleTool Nothing) Black 0.1 

Do not panic if your circle is slightly different from the circle above. But do justify in your report that it is a circle and explain what may cause the discrepancy.

5. Ellipses (ellipse) [20 marks]

The midpoint algorithm for circles generalises to ellipses (see references ²).

Ellipses are symmetrical between the four quadrants. This means that the ellipses’ symmetry allows only 4 simultaneous points to be plotted at a time (while it was 8 for circles). This means that you need to calculate points in a full 90°.

Instead of mirroring octants, mirror quadrants formed from pairs of iterations over the x x and y y axes for the octants. That is, the x x iterations go from 0 0 to q x =a 2 a 2 +b 2   √   $q_x=\frac{a^2}{\sqrt{a^2+b^2}}$ , computing the y y coordinate at each step. Similarly, the y y iterations go from 0 0 to q y =b 2 a 2 +b 2   √   $q_y=\frac{b^2}{\sqrt{a^2+b^2}}$ , computing the x x coordinate at each step.

Here is an example of an ellipse:

drawingOf $ updateView $ Model [(Black, Ellipse (4,2) 10 6)] (EllipseTool Nothing) Black 1 

And the same ellipse with a different resolution:

drawingOf $ updateView $ Model [(Black, Ellipse (4,2) 10 6)] (EllipseTool Nothing) Black 0.1 

---

Report [30 marks]

You are required to write a concise technical report explaining your design choices in completing your program, its implementation, a self-critique of your work, and potential improvements you could make. The requirement, content, format and word limit for the report is the same as the first assignment.

This is not a mandatory word count. It is simply the maximum number of words that your tutor will read in marking your assignment. If you can document your work in fewer words without compromising the presentation, please do so.

In addition to the content given in the assignment 1 specification, you should discuss the performance and efficiency of your program.

Your report must be in PDF format, located at the root of your assignment repository on GitLab and named Report.pdf. Otherwise it may not be marked. Use git add Report.pdf and then commit and push your work to GitLab. You should check your project on https://gitlab.cecs.anu.edu.au to see that everything, including your report, is there by the deadline.

The report must have a title page with the following items:

• Your name
• Your laboratory time and tutor
• Your university ID
• Collaborators, if any

---

Communicating

Do not post your code publicly, either on Piazza or via other forums. If by mistake you post your code publicly on Piazza, an email containing your post with your code will be sent to all students. This means that others will have access to your code and you may be held responsible for plagiarism.

Once again, and we cannot stress this enough: do not post your code publicly. If you need help with your code, post it privately to the instructors.

When brainstorming with your friends, do not show your code to them. There might be some pressure from your friends and even some judgements that you are not sharing the code, but it is for both your and their benefit.

Anything that smells of plagiarism will be dealt with seriously and there may be serious consequences.

Sharing ideas is perfectly fine, but sharing should stop at ideas.

Course staff will not look at assignment code unless it is posted privately in piazza.

Course staff will typically give assistance by directing you to relevant exercises from the labs, or definitions and examples from the lectures.

Before the assignment is due, course staff will not give individual tips on writing functions for the assignment or how your code can be improved. You will receive their feedback when the mark is released.

---

Submission Checklist

Preferably 24 hours prior to the assignment deadline, you should make sure that:

• You have fully read and understand the entire assignment specification.
• Your work so far is pushed to GitLab.
• Your program works on the lab machines—if the program does not work on the lab machines, it might fail tests used by the instructors.
• The report is in PDF format, located at the root of your project on GitLab and named Report.pdf. Otherwise, it may not be marked.

---

References