11 RRLL: Math

Racket Rogue-Like Library: Math Functions

Common mathematical routines used for many RRLL modules.

11.1 Basic Math Utilities

Additional math functions for fixnums and flonums.

11.2 Coordinate Systems

The main coordinate systems used in the project are:

• Screen coordinates (x y)

• Map coordinates (x y z 1)

• Camera coordinates (x y z w) and (x y w)

These coordinates and their transformations are used in the rendering pipeline.

A set of functions for working with vectors in affine and projective spaces is implemented throghout the following modules.

11.2.1 Screen Coordinates

The screen – represented by canvas – is a two-dimensional plane with origin in the upper-left corner and the X coordinate growing from left to right and the Y coordinate growing from top to bottom.

The screen coordinates are represented as fixnum? values.

11.2.2 Map Coordinates

The world map is represented from the top view with origin – as the screen – with the origin at the top-left corner and the X coordinate growing from left to riht and the Y coordinate growing from top to bottom.

The respective compass directions North, East, South and West are shown in the picture as well.

For all practical purposes their respective azimut angles are clockwise from 0 pointing north:

• north \varphi=0

• east \varphi=\frac{\pi}{2}

• south \varphi=\pi

• west \varphi=\frac{3\pi}{2}

The Z coordinate representing the height on the map grows from below the map up.

The inclination starts at \theta=0 for looking north (towards negative Y). Positive inclination goes up to \theta=\frac{\pi}{2} looking straight up in positive Z direction or down to \theta=-\frac{\pi}{2} looking straight down in negative Z direction.

11.2.3 Transformations in Map Coordinates

The simplest transformation is translation by given vector \vec{t} can be represented by the following matrix:

\vec{t}=(x_y,y_t,z_t)

T=\begin{bmatrix} 1 & 0 & 0 & x_t \\ 0 & 1 & 0 & y_t \\ 0 & 0 & 1 & z_t \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}

Rotation around the Z axis counter-clockwise by the angle \theta is:

Z=\begin{bmatrix} \cos\theta & \sin\theta & 0 & 0 \\ -\sin\theta & \cos\theta & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}

Rotation around the X axis counter-clockwise by the angle \theta is:

X=\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & \cos\theta & \sin\theta & 0 \\ 0 & -\sin\theta & \cos\theta & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}

Rotation around the Y axis counter-clockwise by the angle \theta is:

Y=\begin{bmatrix} \cos\theta & 0 & -\sin\theta & 0 \\ 0 & 1 & 0 & 0 \\ \sin\theta & 0 & \cos\theta & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}

11.2.4 Camera Coordinates

The 3D coordinates used for populating the world with polygons from the map and the camera coordinates share a similar same coordinate system.

The X coordinate grows from left to right, the Y coordinate grows from top to bottom and the Z coordinate grows into the screen.

After applying camera translation and all rotations, the axis are flipped to represent the point in camera coordinate axes using the following matrix:

M=\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}

It switches the axes as follows:

x_w=x_m y_w=-z_m z_w=-y_m w_w=w_m

With camera axes in place the projective transformation to camera projective coordinates is performed using the projection matrix. The following parameters are used:

• r - pixel aspect ratio: pixel width over pixel height

• w - camera canvas width in pixels

• h - camera canvas height in pixels

• n - near plane Z distance

• f - far plane Z distance

Because of limitations of the 24-bit fixed-point w-buffer (TODO), the near-plane distance has to be fixed:

n=0.1

The far-plane distance can be almost anything but for all practical purposes the following is used:

n=100

The projection assumes 90^\circ viewing angle in the smaller canvas dimension and slightly bigger viewing angle in the other dimension that gets calculated from the camera canvas width and height.

First, primary lens size is calculated:

w<=h\Rightarrow l=w w>h\Rightarrow l=h

Then width and height aspect ratio is computed:

r_w=\frac{w}{l} r_h=\frac{h}{l}

The projection matrix is then as follows:

P=\begin{bmatrix} \frac{2\cdot n\cdot r}{r_w} & 0 & 0 & 0 \\ 0 & \frac{2\cdot n}{r_h} & 0 & 0 \\ 0 & 0 & \frac{f+n}{f-n} & 1 \\ 0 & 0 & \frac{2\cdot f\cdot n}{f-n} & 0 \\ \end{bmatrix}

After applying the projection matrix the vertices are in camera projective coordinates. Clipping against frustum is performed in these coordinates.

11.2.5 Vector Projection

Any point in camera projective coordinates can be represented as:

P=(x_p,y_p,z_p,w_p)

A screen vector then is:

S=(x_s,y_s,w_s)

The projection is as follows:

x_s=w\cdot\frac{x_p+1}{2\cdot w_p} y_s=w\cdot\frac{y_p+1}{2\cdot w_p} w_s=w_p

The screen coordinates must be rounded to the nearest integer.

11.3 Generic Linear Algebra

11.3.1 Generic 2D Vectors

These procedures help with basic map vector handling.

C=A+v\cdot(B-A)

11.3.2 Generic 3D Vectors

d=\vec{v_1}\cdot\vec{v_2} d=x_{v_1}\cdot x_{v_2}+y_{v_1}\cdot y_{v_2}+z_{v_1}\cdot z_{v_2}

l=\sqrt{\vec{v}\cdot \vec{v}} l=\sqrt{x_v^2+y_v^2+z_v^2}

l^2=x_v^2+y_v^2+z_v^2

d=\sqrt{(x_A-x_B)^2+(y_A-y_B)^2+(z_A-z_B)^2}

d^2=(x_A-x_B)^2+(y_A-y_B)^2+(z_A-z_B)^2

\vec{v{}’}=n\cdot \vec{v} \vec{v}=(x_v,y_v,z_v) \vec{v{}’}=(x_v{}’,y_v{}’,z_v{}’) \vec{v{}’}=(n\cdot x_v,n\cdot y_v,n\cdot z_v)

\vec{v{}’}=\frac{v}{n} \vec{v{}’}=\frac{1}{n}\cdot \vec{v}

C=A+v\cdot(B-A)

C=A\times B A=(x_A,y_A,z_A) B=(x_B,y_B,z_B) C=(x_C,y_C,z_C) x_C=y_A\cdot z_B-z_A\cdot y_B y_C=z_A\cdot x_B-x_A\cdot z_B z_C=x_A\cdot y_B-y_A\cdot x_B

11.4 Normalized Projective 3D Linear Algebra

This module handles the basic vector transformation in 4D affine vector space representing 3D projective vector space.

11.4.1 Normalized Projective 3D Vectors

The first part of this module implements the basic affine 4D vector operations.

\vec{v}=(x_v,y_v,z_v,w_v) \vec{v}{}’=(x_v{}’,y_v{}’,z_v{}’,w_v{}’) x_v{}’=\frac{x_v}{w_v} y_v{}’=\frac{y_v}{w_v} z_v{}’=\frac{z_v}{w_v} w_v{}’=w_v

\vec{v}=(x_v,y_v,z_v,w_v) \vec{v}{}’=(x_v{}’,y_v{}’,z_v{}’,w_v{}’) x_v{}’=x_v\cdot w_v y_v{}’=y_v\cdot w_v z_v{}’=z_v\cdot w_v w_v{}’=w_v

11.4.2 Normalized 3D Transformation Matrices

These functions implement construction and application of 4\times 4 matrices.

M=\begin{bmatrix} r0c0 & r0c1 & r0c2 & r0c3 \\ r1c0 & r1c1 & r1c2 & r1c3 \\ r2c0 & r2c1 & r2c2 & r2c3 \\ r3c0 & r3c1 & r3c2 & r3c3 \\ \end{bmatrix}

M=\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}

M=\begin{bmatrix} M_{0,0} & M_{0,1} & M_{0,2} & M_{0,3} \\ M_{1,0} & M_{1,1} & M_{1,2} & M_{1,3} \\ M_{2,0} & M_{2,1} & M_{2,2} & M_{2,3} \\ M_{3,0} & M_{3,1} & M_{3,2} & M_{3,3} \\ \end{bmatrix}

\vec{v}=(x_v,y_v,z_v,w_v) \vec{v}{}’=(x_v{}’,y_v{}’,z_v{}’,w_v{}’) x_v{}’=M_{0,0}\cdot x_v+M_{0,1}\cdot y_v+M_{0,2}\cdot z_v+M_{0,3}\cdot w_v y_v{}’=M_{1,0}\cdot x_v+M_{1,1}\cdot y_v+M_{1,2}\cdot z_v+M_{1,3}\cdot w_v z_v{}’=M_{2,0}\cdot x_v+M_{2,1}\cdot y_v+M_{2,2}\cdot z_v+M_{2,3}\cdot w_v w_v{}’=M_{3,0}\cdot x_v+M_{3,1}\cdot y_v+M_{3,2}\cdot z_v+M_{3,3}\cdot w_v

\begin{bmatrix}x_v{}’\\y_v{}’\\z_v{}’\\w_v{}’\end{bmatrix}= \begin{bmatrix} M_{0,0} & M_{0,1} & M_{0,2} & M_{0,3} \\ M_{1,0} & M_{1,1} & M_{1,2} & M_{1,3} \\ M_{2,0} & M_{2,1} & M_{2,2} & M_{2,3} \\ M_{3,0} & M_{3,1} & M_{3,2} & M_{3,3} \\ \end{bmatrix}\cdot \begin{bmatrix}x_v\\y_v\\z_v\\w_v\end{bmatrix}

11.5 Transformations in World/Camera Coordinates

This module contains useful matrices for working in world/camera coordinates.

11.6 Angle Manipulation Helpers

This module contains simple functions for working with angles in the range \langle 0;2\pi\rangle.

Angles in this module and other related modules represented in 2D map coordinates point in the north direction for zero angle rotating clockwise as the angle increases.

11.7 2D Integer Vectors

A convenience structure for representing 2D coordinates in the grid. The x and y values can only be fixnum?s.