MIPS and floating point for drawing 3D geometry

COMP 273 Assignment 3

Submission instructions

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.

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);

}

}

}

Sale!