MIPS and floating point for drawing 3D geometry Solution

Submission instructions




All work must be your own, and must be submitted by MyCourses. Include your name and student number at the top of your source file. Submit only one file, drawGeometry.asm. Do not use a zip archive. Check your submission by downloading your submission from the server and checking that it was correctly submitted. You will not receive marks for work that is incorrectly submitted.




Overview



In this assignment, you will use the memory mapped display tool in MARS to animate 3D geometry loaded from a file. The assignment is broken into three parts: basic utilities, line drawing, and then matrix multiplication.




Bitmap display and provided code




We will use the default settings of the bitmap display. That is, when you select Bitmap Display from the Tools menu, it will have a base address set to the start of static data (0x10010000), and will be 512 pixels wide and 256 pixels high. Do not forget to press the Connect to MIPS button so that the display to works with your program.




The top left corder of the memory mapped bitmap display corresponds to the first memory address (0x10010000) with one word (four bytes) encoding the pixel colour. The top byte of the word is unused, while the lower three bytes provide the red, greed, and blue components of the pixel’s colour (e.g., red is 0x00ff0000, green is 0x0000ff00, blue is 0x000000ff, black is 0x00000000, and white is 0x00ffffff).




The memory in the display is in row-major order. That is, the pixel just to the right of the top left pixel will be at 0x10010004. The pixel just below the top left pixel will be at 0x10010800, which is the memory address that comes after all the pixels in the first row. This is an offset of 0x800 because the display is 512 pixels wide, or 0x200, and each pixel takes up 4 bytes. Suppose we would like to set a pixel to a given colour. Let x be an integer specifying the column (valid values going from 0 to 511 inclusive), and let y be an integer specifying the row (valid values going from 0 to 255 inclusive). To set pixel (x; y) to white, we would store 0x00ffffff at memory location b + 4(x + wy), where b is the base address of the memory mapped display, and w = 512 is the width.




With a total of 256 rows, or 0x100, the amount of memory needed for the display is 0x80000 bytes (i.e., 512 time 256 times 4). In this assignment, we will reserve this memory in the static data segment. We will also reserve an equal amount of memory to allow us to draw first into an off-screen buffer, and then once finished drawing, copy that off-screen memory buffer into the bitmap display’s memory. To reserve the space, for both the memory mapped display and the off-screen buffer, the following labels and directives are provided at the top of your assembly file. It is OK to assume that the size of the bitmap display will never be set to a different size (that is, your solution can be hard coded assuming these dimensions).




.data # start data segment with
bitmapDisplay
so that it
is at 0x10010000
.globl bitmapDisplay # force it to show at the
top
of the
symbol
table
bitmapDisplay: .space 0x80000 #
Reserve space
for
memory
mapped
bitmap display



bitmapBuffer:
.space
0x80000 # Reserve space for an "offscreen" buffer
width:
.word
512
#
Screen Width in Pixels
height:
.word
256
#
Screen Height in Pixels
Note that later in the assignment, you will use line data loaded from a separate provided file, teapotLine-Data.bin. Assembly code to load from file is provided in the void loadLineData( char* filename, float* data, int* count ) function. The static data segment has the following labels and direc-tives to help with this task, specifically, the name of the file to load, a pointer to memory to store the number of lines, and pointer to memory to store the line data. We also declare memory with an error message that the loadLineData function will print to the Run I/O console should there be problems load-ing the file. The provided code includes an example of how to call loadLineData.




lineDataFileName:
.asciiz "teapotLineData.bin"


errorMessage:
.asciiz "Error: File must be in directory where MARS is started."
lineCount
:
.space
4
#
int containing number
of lines
lineData:


.space
0x4800
#
space for teapot line
data



Each line in the line data consists of 8 words, the start and end point of each line in 3D space, stored as single precision floats using 4 coordinates for each point, x0, y0, z0, w0, x1, y1, z1, w1. Here, we use 4 components because these 3D points are stored in homogeneous representation, and the w coordinate will always be 1.




Utility functions (5 marks)



Several simple utility functions will be needed for drawing with an off-screen buffer and a bitmap display. Implement the following functions. Note that these functions are small and simple. They do not call any other functions and will not need to use the stack.




void clearBuffer( int colour )




This function takes the clear colour, and sets every pixel in the off-screen bitmapBuffer to be this colour. You may find that partial loop unrolling (i.e., setting more than just one pixel inside the loop) will make your function faster by reducing the total number of instructions necessary to get the job done.




For testing, you can examen different locations in memory before and after your call to make sure they are set appropriately. Alternatively you could temporarily make your function mod-ify the on-screen buffer so you can view it in the bitmap display, but be sure to set it back to off-screen buffer.




void copyBuffer()




This function performs a memory copy. It should copy all pixels from the off-screen buffer to the on-screen buffer. Again, partial loop unrolling may improve performance. Test by clearing the off-screen buffer to different colours and copying to the on-screen buffer.




void drawPoint( int x, int y )




This function takes x and y coordinates of a pixel as signed integers, and sets the given pixel in the off-screen buffer to green. The colour is thus 0x0000ff00. The drawPoint function must do bounds checking on the input parameters. Use sltu to simultaneously check lower and upper bounds of the x coordinate. Do the same to check that the y coordinate is valid. If either is out of bounds, your function should do nothing so as not to overwrite memory that is not part of the display!




Line drawing (5 marks)



With the basic utility functions of screen clearing, off-screen to on-screen buffer copying, and drawing points, we now want to be able to draw lines. You will use an algorithm similar to Bresenham’s line
drawing algorithm, which is an efficient integer based solution using only addition and subtraction for determining which pixels need to be set to draw a line between two points. The basic algorithm assumes that the line has a slope less than one, and that the starting x position (column) x0 is less than or equal to the end column x1. With these assumptions, the problem is reduced to a simple loop where the x position is stepped one pixel at a time from x0 to x1, while the y position is periodically increased depending on how far the current pixel is from the line. The trick is to keep track of a measure of the distance, or the error. After drawing pixel (x; y), the question is if pixel (x + 1; y) is closest to the line, or if it is farther from the line than (x + 1; y + 1).




void drawLine( int x0, int y0, int x1, int y1 )




See the end of this assignment for the code which will step x and y in either positive or neg-ative pixel increments depending on the input. This is a more useful line drawing algorithm than what is described above as it will work for all lines, of any slope, and does make the assumption that x0 < x1. Implement this function and have it call your drawPoint call. You should not use any multiplication or division in your implementation. Test your code by drawing some different lines, and note that you can even draw lines that have an endpoint that is off-screen thanks to the bounds checking in drawPoint. Note that you will need to use the stack because drawLine calls another function.




Matrix multiplication (5 marks)



To draw points and lines that represent 3D geometry on our 2D bitmap display, we will need a matrix vector multiplication (more details on using the result of the multiply to compute screen coordinates are in the next section). Specifically, the matrix multiply will use a 4-by-4 matrix of floating point numbers, and the 4 component vector will be the homogeneous representation of a 3D point (x; y; z), which is simply the vector (x; y; z; 1).

void mulMatrixVec( float* matrix, float* vec, float* out )




This function takes 3 pointers as parameters, the first being a 4-by-4 matrix is row-major or-der, and the second and third being 4 component vectors. Given that the size of the matrix and vectors is fixed, you might consider implementing this function without using loops! As this function does not call any other functions, you can probably accomplish the computation without the need of the stack.




As you will want to test your code, consider making sample matrices and vectors to multiply, such as the following.




testMatrix: .float




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16



testVec1: .float 1
0
0 0
testVec2: .float 0
1
0 0
testVec3: .float
0
0
1 0
testVec4: .float
0
0
0 1
testResult: .space
16





Multiplying textMatrix by testVec1 produces a vector equal to the first column of the matrix, that is, (1; 5; 9; 13). Note the use of a .space directive to reserve memory for storing the answer in testResult, specifically 4 floats, each being 4 bytes, or a total of 16 bytes of space reserved. Remember that you can use the code presented in class for printing a 4 component float vector to check your results.

Geometry drawing and animation (5 marks)



Given that you have completed the other parts of the assignment, you are now ready to draw and an-imate a rotating teapot. Recall that the 3D line data for the teapot is loaded from file. There is a line count with the the number of lines to draw, and a buffer with the line data. For each line there are 8 float-ing point numbers, specifically, the two endpoints of the line, where each point is represented as a four component vector (i.e., in homogeneous coordinates). To draw the lines on the bitmap display, you will transform the 4D end point vectors into (x,y) display coordinates, and then send these 2D endpoints to your line drawing function. The following matrix provides a perspective projective suitable for drawing the teapot.




M: .float




331.3682, 156.83034, -163.18181, 1700.7253 -39.86386, -48.649902, -328.51334, 1119.5535




0.13962941, 1.028447, -0.64546686, 0.48553467




0.11424224, 0.84145665, -0.52810925, 6.3950152




Implement the following functions:

( int x, int y ) = point2Display( float* vec )




To compute the 2D display point from 4D line end-point p, you must convert the product M p into a 2D screen location. This is done by taking the first two components divided by the last. That is, if (x; y; z; w) = M p, then our display coordinates are (x=w; y=w). The reason for this division is that we would like points which are far to appear smaller on the display window, and it is this w component that will contain the distance of the point after multiplication by the matrix. While the matrix M was prepared specially for this assignment, it is actually the prod-uct of a number of very simple matrices (the details are covered in COMP 557, Fundamentals of Computer Graphics). Thus, this function should take a pointer to a 4 component vector, and return two integer values for the x and y location of the point in the bitmap display. Note that you will naturally use div.s for floating point division, but you will also need to convert the floating point values to integers with cvt.w.s, and move from the coprocessor into the regular registers with mfc1. Consult the MIPS instruction specifications to be sure you are using the instructions correctly!

void draw3DLines( float* lineData, int lineCount )




Write a function that loops over all the line data, uses mulMatrixVec with the matrix M to transform the end-points, converts the results to display coordinates with point2Display, and the draws the lines with drawLine. As this function will do looping and call your matrix multiplication and line drawing functions, you will need to use the stack! You will want to declare memory in the static data segment for a vector to store the result of your matrix vector multiplies (for instance, see the testResult declaration example in the previous section).




Animation




To animate the teapot, you can repeatedly draw the teapot, with a transformation applied to all the points between each drawTeapot call. The following 4-by-4 homogeneous matrix represents a small rotation about the z axis.




R: .float




0.9994
0.0349 0
0
-0.0349
0.9994 0
0
0
0
1
0
0
0
0
1
Implement the following function:

rotate3DLines( float* lineData, int lineCount )




This function loops through all the line data transforming each end-point of each line by the matrix R. Note that multiple calls to this function will have a cumulative effect, that is, we can call this function to increase the total rotation of the geometry by a small amount on each drawing pass.




You should now finish your main function to produce an animation. In a loop, repeatedly call clearBuffer, draw3DLines, copyBuffer, and rotate3Dlines. Use black (that is 0x00000000) as the clear colour. You may make an endless loop and let the program run forever, or instead run the loop a fixed number of times (e.g., 30) before doing a syscall to terminate the program.




Finally, note that MARS after running for some time can end up in a state where it runs quite slowly. The solution is to simply close and restart.

drawLine source code




void drawLine( int x0, int y0, int x1, int y1 ) { int offsetX = 1;




int offsetY = 1;




int x = x0;




int y = y0;




int dX = x1 - x0;




int dY = y1 - y0;




if ( dX < 0 ) {




dX = -dX;




offsetX = -1;




}




if ( dY < 0 ) {




dY = -dY;




offsetY = -1;




}




drawPoint( x, y );




if (dX dY) {




int error = dX;




while (x != x1) {

error = error - 2*dY;

if (error < 0) {




y = y + offsetY;

error = error + 2*dX;

}




x = x + offsetX;




drawPoint(x,y);




}




} else {




int error = dY;




while (y != y1) {

error = error - 2*dX;

if (error < 0) {




x = x + offsetX;

error = error + 2*dY;

}




y = y + offsetY;




drawPoint(x,y);




}




}




}