MIPS and floating point for drawing 3D geometry COMP 273 Assignment 3


Category: You will Instantly receive a download link for .zip solution file upon Payment


5/5 - (2 votes)

1 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, teapotLineData.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 directives 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 loading 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.
2 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 modify 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!
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 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 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). 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 order, 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. 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 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 floating 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 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, 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); } } }