The first (real) assignment will be in two parts. In the first part, you will learn how to write a simple parser in order to establish an easy and flexible way read input into your programs. In the second part of the assignment, you will use simple parsers to a) read in the description of a transformation and produce the resulting matrix, and b) draw 2D lines defined in an input file and output the resulting image.
Also due this week: the matrix library assigned last week
Homework 1 is due on Tuesday Oct. 14 at 11:59 pm
For this and future assignments, you will need a matrix library. You are encouraged to write one yourself, but using one downloaded from the Internet is also acceptable. Here is an example library written for C++ by a student from last year's class.
Note: If you do download a matrix library, you cannot use any graphics capabilities it might have. In other words, you still must implement all of your own transformations (rotation, translation, scaling, projections, etc.).
Your library should support the following operations:
It is important to have an inverse function that is efficient and numerically robust. For this reason, please don't invert your matrices using determinants! Here is Peter's inversion code to get you started.
Please see the HW1 parser page.
Write a program called transform4x4 that uses a simple parser (as described in part 1) to read a description of a transformation, compute the corresponding matrix, and print the result to stdout. The datafiles look like this:
translation tx ty tz rotation axisX axisY axisZ angle scaleFactor sx sy sz
where tx, ty, etc. are all real numbers. Your code should be able to handle an arbitrary number of commands (translation, rotation, or scaleFactor) listed in any order. Think of the input file as representing a series of transformation matrices in which the top-down order of the input file corresponds to a left-to-right sequence of matrices leading up to a vector to be transformed. Therefore, if you had an input file reading:
translation 0 0 1 rotation 1 1 1 .5 scaleFactor 1 2 3
You would think of this as representing: (T)(R)(S)(some vector) = result
where (T), (R), (S) are the corresponding transformation matrices. So, in this example, (S) is applied first, (R) second, and so forth.
Example input files can be found in the homework 1 data.
See Homogeneous
Coordinates and Transformation
Matrices
for more detailed
information on how you are to do this. This site doesn't give the
general rotation matrix explicitly. You can work it out yourself, or
just use our derivation:
. . . 0 . . . 0 . = elements of 3x3 matrix . . . 0 0 0 0 1
Your 2D line drawing program should be called draw2d and take the following arguments:
draw2d [xmin] [xmax] [ymin] [ymax] [xRes] [yRes]
xmin, xmax, ymin, ymax are real numbers that give the range of x and y values in the image. Note that the lines can go off the screen, outside the image space.
The two integers xRes and yRes indicate the size of the image to be made.
Input should be read using a simple parser. The input format looks like this:
polyline 0.0 0.0 1.0 0.0 1.0 1.0 0.0 1.0 0.0 0.0 polyline 3.0 -3.0 6.0 5.0 9.0 -4.0
Each polyline keyword starts a new line and each pair of real numbers indicates an (x,y) position. The program should "move" to the first location and then draw lines connecting the dots through the rest. The program should not return to the first point -- if a closed curve is desired, the first point will be repeated at the end.
The line-drawing routine must use Bresenham's algorithm. You can use whatever colors you like, although the sample results are white on black.
The output image should be written to stdout in the PPM file format.
PPM images are text files containing
Example:
P3 2 2 255 255 255 255 0 0 0 0 0 0 255 255 255
This indicates that the image is 2x2 with a maximum intensity of 255. The upper-left and lower-right pixels are white, while the upper-right and lower-left pixels are black.
To view an image, you can pipe the output of your program to display:
./draw2d -1.5 1.5 -1.5 1.5 400 400 < starbox.2d | display -
You can also save to a file using convert:
./draw2d -1.5 1.5 -1.5 1.5 400 400 < starbox.2d | convert - starbox.png
Once you've implemented the functions as discussed above, please write some simple test code to demonstrate them. Copy the output of your test code into your README file for the following cases:
Plus two or three of the other operations (addition, normalization, scalar multiplication, etc. etc.) of your choice.
For part 1, you need to write lexers and parsers for both the polyline language and the transform4x4 language. See the HW1 parser page for an explanation of parsers and links to tutorials on using lexer/parser generators. Check out Bill's example lexer/parser if you'd like an example.
For part A, please test your transform4x4 on an example transformation file (such as one of those supplied in this week's test code). Then, include the output in your README file.
For part B, you'll probably want to divide the code into the following sections (in order to make future reuse easier.)
Make sure to clearly comment your code and include instructions in your README for the execution of your program.
You should develop your own test cases for Part 0 (be sure to include any necessary information in your README.) We have provided a few test cases for part 2 in the homework 1 data.
If you work on a Windows box, you could download Irfanview to display your ppm files.