MIPS and ﬂoating point for drawing 3D geometry

Assignment 3

All work must be your own, and must be submitted by MyCourses. Include your name and student number at the top of your source ﬁle. Submit only one ﬁle, 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.

1 Overview

In this assignment, you will use the memory mapped display tool in MARS to animate 3D geometry loaded from a ﬁle. 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 ﬁrst 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 ﬁrst 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., 512time256times4). Inthisassignment,wewillreservethismemoryinthestaticdatasegment. Wewill also reserve an equal amount of memory to allow us to draw ﬁrst into an off-screen buffer, and then once ﬁnished 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 ﬁle. It is OK to assume that the size of the bitmap display will neverbesettoadifferentsize(thatis,yoursolutioncanbehardcodedassumingthesedimensions).

.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 ﬁle, teapotLineData.bin. Assemblycodetoloadfromﬁleisprovidedinthevoid loadLineData( char* filename, float* data, int* count ) function. The static data segment has the following labels and directives to help with this task, speciﬁcally, the name of the ﬁle 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 messagethattheloadLineDatafunctionwillprinttotheRunI/Oconsoleshouldtherebeproblemsloading the ﬁle. 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 ﬂoats 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.

2 Utility functions (5 marks)

Severalsimpleutilityfunctionswillbeneededfordrawingwithanoff-screenbufferandabitmapdisplay. 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 ﬁnd 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 suretheyaresetappropriately. Alternativelyyoucouldtemporarilymakeyourfunctionmodify 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 theon-screenbuffer. Again,partialloopunrollingmayimproveperformance. Testbyclearing 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 upperboundsofthe x coordinate. Dothesametocheckthatthe y coordinateisvalid. Ifeither is out of bounds, your function should do nothing so as not to overwrite memory that is not part of the display!

3 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 efﬁcient 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 theendcolumn x1. Withtheseassumptions,theproblemisreducedtoasimpleloopwherethe 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 negative 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.

4 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). Speciﬁcally, the matrix multiply will use a 4-by-4 matrix of ﬂoating point numbers, andthe4componentvectorwillbethehomogeneousrepresentationofa3Dpoint (x,y,z),whichissimply the vector (x,y,z,1). void mulMatrixVec( float* matrix, float* vec, float* out ) This function takes 3 pointers as parameters, the ﬁrst being a 4-by-4 matrix is row-major order, and the second and third being 4 component vectors. Given that the size of the matrix and vectors is ﬁxed, 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. Asyouwillwanttotestyourcode,considermakingsamplematricesandvectorstomultiply,suchasthe 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 producesavectorequaltotheﬁrstcolumnofthematrix,thatis, (1,5,9,13). Notetheuseofa.spacedirectivetoreservememoryforstoringtheanswerintestResult, speciﬁcally 4 ﬂoats, 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 ﬂoat vector to check your results.

5 Geometry drawing and animation (5 marks)

Given that you have completed the other parts of the assignment, you are now ready to draw and animate a rotating teapot. Recall that the 3D line data for the teapot is loaded from ﬁle. There is a line countwiththethenumberoflinestodraw,andabufferwiththelinedata. Foreachlinethereare8ﬂoating point numbers, speciﬁcally, 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 Mp into a 2D screen location. This is done by taking the ﬁrst two components divided by the last. That is, if (x,y,z,w) = Mp, 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, anditisthisw componentthatwillcontainthedistanceofthepointaftermultiplicationbythe matrix. While the matrix M was prepared specially for this assignment, it is actually the product 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, andreturntwointegervaluesforthe x and y locationofthepointinthebitmapdisplay. Note thatyouwillnaturallyusediv.sforﬂoatingpointdivision,butyouwillalsoneedtoconvert the ﬂoating point values to integers with cvt.w.s, and move from the coprocessor into the regular registers with mfc1. Consult the MIPS instruction speciﬁcations 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, andthedrawsthelineswith drawLine. Asthisfunctionwilldoloopingandcallyourmatrix multiplication and line drawing functions, you will need to use the stack! You will want to declarememoryinthestaticdatasegmentforavectortostoretheresultofyourmatrixvector multiplies (for instance, see the testResult declaration example in the previous section).

Animation Toanimatetheteapot,youcanrepeatedlydrawtheteapot,withatransformationappliedtoallthepoints 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. Youshouldnowﬁnishyourmainfunctiontoproduceananimation. Inaloop,repeatedlycallclearBuffer, 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 ﬁxed 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); } } }

Sale!