Build Vector and Matrix Operations Yourself

Goal

Build 3D vector operations and 4x4 matrix multiplication yourself, and use them to move, rotate and shrink shapes. When this lab is done, you can read and write transformation matrices, and you have confirmed by hand why the multiplication order matters.

Why it matters

The reason the matrix is 4x4 for a 3D computation is that translation is not a multiplication. If you write coordinates with one more, as (x, y, z, 1), the last column is multiplied by that 1 and added to the result, and that is how translation enters the multiplication. This is called homogeneous coordinates, and the distinction that w of 1 means a point and 0 means a direction comes from here.

And once transformations are expressed as matrices, you can multiply several of them in advance into one. This is why the GPU multiplies just one MVP matrix per vertex. However, matrix multiplication is not commutative, so if you swap the order the object orbits instead of spinning in place. Once you have seen this difference in numbers, you will not forget it.

Steps

1. Put the /root/linalg/gfxlib.py toolbox in place.
2. Make seven vector operations in /root/linalg/vec.py.
3. Make 4x4 matrix multiplication in /root/linalg/mat.py.
4. Make translation, scale and rotation matrices in /root/linalg/xform.py.
5. Write the result of swapping the multiplication order to /root/linalg/out/05-order.txt.
6. Draw three transformed squares to /root/linalg/out/square.png.
7. Find the normal and area with the cross product and write them to /root/linalg/out/07-normal.txt.

Notes

• Keep all files inside /root/linalg. The grader puts that folder on the import path and calls your functions directly.
• To see the picture, start a server with nohup python3 -m http.server 8080 -d /root/linalg/out & and then open http://localhost:8080/square.png in the Web preview.
• Common mistake 1: mixing up the indexes of mul and building a transposed matrix. Testing with the identity matrix will not catch it, so test with a translation matrix.
• Common mistake 2: making the sign of rotate_y the same as the other axes. Because of the cyclic order of the axes, only the y axis is opposite.

Put the drawing toolbox in place

Save /root/linalg/gfxlib.py exactly as in the example, and use /root/linalg/check.py to draw a test pattern and make /root/linalg/out/00-check.png. The pattern is a 64x64 black background with a white (255,255,255) diagonal line from (0,0) to (63,63), and over it a red (255,0,0) horizontal line from (0,32) to (63,32).

From this lab on, you do not rebuild the PNG encoder. We hand you the same code you built by hand in the first lab as a tool — because file formats are not what you learn here.

The lab Pod has no volume, so the files you made in the previous lab are not kept. That is why each lab starts by putting the toolbox in place again.

Create Canvas(w, h, bg), draw the two lines with line(x0, y0, x1, y1, rgb), and then save with write_png(path). Draw the horizontal line later, so that the intersection (32,32) becomes red.

3D vector operations

In /root/linalg/vec.py, make seven functions: add(a,b), sub(a,b), scale(a,s), dot(a,b), cross(a,b), length(a) and normalize(a). Vectors are tuples of length 3, and only dot and length return a real number.

You must write the definition of the cross product exactly, down to the signs.

cross(a, b) = (a1*b2 - a2*b1, a2*b0 - a0*b2, a0*b1 - a1*b0)

If cross((1,0,0), (0,1,0)) gives (0,0,1), the sign is right. If it comes out the other way, the right-handed coordinate system has been flipped, and later the lighting will look as if it shines from behind the object.

normalize may receive a vector of length 0. In that case, return the original vector as it is so that you do not divide by zero.

4x4 matrix multiplication

In /root/linalg/mat.py, make three functions: identity(), mul(a,b) and apply(m,v). Matrices are row-major (a list holding 4 lists of length 4), and apply treats the point (x,y,z) as the column vector (x,y,z,1), multiplies, and returns the four components (x,y,z,w).

The definition of the multiplication is out[r][c] = sum(a[r][k] * b[k][c] for k in range(4)). If you mix up the index order even once, you get a transposed matrix, and testing with the identity matrix will not catch it — because the identity matrix is its own transpose.

So test with an asymmetric matrix. One with values only in the last column, like a translation matrix, is good.

apply computes m[r][0]*x + m[r][1]*y + m[r][2]*z + m[r][3]*1 for r=0..3.

Translation, scale and rotation matrices

In /root/linalg/xform.py, make five functions: translate(tx,ty,tz), scale(sx,sy,sz), rotate_x(deg), rotate_y(deg) and rotate_z(deg). Angles are taken in degrees, and the convention is a right-handed coordinate system.

The upper-left 2x2 of rotate_z is [[cos, -sin], [sin, cos]]. With this, rotate_z(90) sends the x axis (1,0,0) to the y axis (0,1,0).

By the same rule, rotate_x sends y to z, and rotate_y sends z to x. Only rotate_y has its sign put in the opposite way — m[0][2] = sin and m[2][0] = -sin. This is because the cyclic order of the axes is x→y→z→x, and if you make the sign uniform here, only the y axis rotation turns the wrong way.

Use math.radians to convert degrees to radians.

The multiplication order changes the result

Let T = translate(2,0,0) and R = rotate_z(90), apply mul(T,R) and mul(R,T) to the point (1,0,0), and write the results to /root/linalg/out/05-order.txt as two lines, TR=x,y,z and RT=x,y,z. Write to six decimal places.

In the convention where a column vector is multiplied on the right, the matrix on the right is applied first. mul(T, R) means rotating first and translating afterwards.

Follow it by hand. First find where R sends (1,0,0), and add T to that. The opposite order applies T first and then applies R.

In one case the object spins in place and is then moved, and in the other it moves away from the origin and then orbits around the origin. The results differ greatly.

Draw the transformed squares

Use /root/linalg/plot.py to write a 256x256 PNG to /root/linalg/out/square.png. The square in model coordinates is (-1,-1,0), (1,-1,0), (1,1,0), (-1,1,0), and you map it to screen coordinates with sx = 128 + 60*x and sy = 128 - 60*y. Draw three squares on a black background — the one with no transformation in white (255,255,255), the one with rotate_z(30) applied in red (255,60,60), and the one with mul(translate(1.2,-0.8,0), scale(0.5,0.5,1)) applied in green (60,255,60).

Each square is four line segments that join the four vertices in order and return from the last to the first point. Use line(x0, y0, x1, y1, rgb) of gfxlib.Canvas.

Note that a subtraction goes into y when you map to screen coordinates. The y of math grows upward, and the y of an image grows downward. If you leave this out, the green square is drawn at the top.

The green square's transformation shrinks first and translates afterwards — the right side of mul(translate, scale) goes first.

Find the normal and area with the cross product

Use /root/linalg/normal.py to find the unit normal and area of two triangles and write them to /root/linalg/out/07-normal.txt as four lines, t1_normal=, t1_area=, t2_normal= and t2_area=. Triangle 1 is A(0,0,0) B(2,0,0) C(0,3,0), and triangle 2 is A(1,1,1) B(2,1,1) C(1,1,3), and the normal is cross(B-A, C-A) normalized.

The length of the cross product is the area of the parallelogram the two edges make, so the triangle's area is half of that. That is, area = length(cross(B-A, C-A)) / 2.

The sign of the normal is decided by the order in which you go around the vertices. cross(B-A, C-A) and cross(C-A, B-A) point in exactly opposite directions. This order later becomes the criterion that separates front faces from back faces, so keep to the order you are given.

Write values with %.6f and join vector components with commas. Example: t1_normal=0.000000,0.000000,1.000000