3D
PROGRAMMING
part 1  Camera movements
Background

Over years we have seen numerous demos with 3D objects spinning and rotating
and one of the most common effects in atari demos must be the spinning cube,
either with filled polygons, wireframe or dots and later on, gouraud shaded
and texturemapped polygons.
If we take a step back and look at those screens again we notice most of them
have one thing in common, they all spin infront of the screen and there
usually isnt anything else on spinning with it. This gives the impression
there is only one object and its not a part of a bigger scene, this sure
can be entertaining but when you see the same thing over and over again in
demos you get a bit bored of it and wish the programmer could have spent a
bit more time trying to get a decent scene in there.
So how can we get a more complex scene running? One with multiple objects
and a moveable camera? And more important, how can we get a flying camera
in there so we dont have to have all objects rotating infront of the camera?
First we have to know how objects are stored in memory and how they make
their way to the screen.
Vertices and indices

Objects have vertices (x, y, z and sometimes w describing a position in a
world) and some sort of index to the same vertices to describe each face.
The indices are there simply to index into the vertex table because faces
share vertices and we dont want to do more work than needed with those
vertices since there might be hundreds or even thousands of them.
A face made up of two triangles might look like this:
vertices

10,10,0 (x, y, z)
10,10,0
10,10,0
10,10,0
Each of the vertics can also be thought of as a matrix, more about that
later.
indices

0, 1, 3 (face 0)
1, 2, 3 (face 1)
From now on I will only use the vertices since we're thats all we need for
this article.
To go from a bunch of vertices to a spinning object on screen (the points of
a square in this case) we need to transform them somehow, the most obvious
way for many programmers would be to the classic rotation formula and then
perspective project the vertices to go from 3D to 2D. This is ok for a
spinning object but if we want to implement a camera system there is a
better way, using matrices.
Introduction to matrices

Matrices in this case are basically 2D arrays containing numbers, like this.
[1 0 0]
[0 1 0]
[0 0 1]
This happens to be a so called 3x3 identity matrix.
Matrices are very useful for 3D maths since one single 3x3 matrix can
describe scale and rotation around all three axis and its quicker (less
calculations) than the old rotation formula.
After you have your matrix you have to apply it to all vertices in the
object, in our case the four vertices making up the square.
Applying a matrix to a vertex means simply means multiplying, in our case
we multiply a 3x3 matrix with a 1x3 vertex, something like this.
x' = x*m[0][0] + y*m[1][0] + z*m[2][0];
y' = x*m[0][1] + y*m[1][1] + z*m[2][1];
z' = x*m[0][2] + y*m[1][2] + z*m[2][2];
Where x, y and z are vertex components and m[][] is a matrix element.
x', y' and z' is the resulting vertex after the transformation.
If we apply this matrix to all our vertices on the world we end up with a
camera system where we can pan the camera and look up and down etc but what
about moving around? To accomplish that we need to get the camera position
into the equation somehow, normally this is done using a 4x4 matrix instead
which can hold all the rotation and translation (moving). This is a bit
overkill for our simple system since it would add a few multiplication and
adds for each vertex. Instead we translate each vertex before we apply the
matrix to it, this does exactly the same as having the translation in the
matrix.
So before the above piece of code we do:
x = x + camera_pos_x
y = y + camera_pos_y
z = z + camera_pos_z
This will offset the vertex and then rotate it around the camera, just what
we want.
One question still remains, how do we generate this matrix? Easy, using
trigonometri.
Something like this:
sx = sin(xa)
sy = sin(ya)
sz = sin(za)
cx = cos(xa)
cy = cos(ya)
cz = cos(za)
m[0][0] = cy*cz
m[0][1] = cy*sz
m[0][2] = sy
m[1][0] = sx*sy*cz  cx*sz
m[1][1] = sx*sy*sz + cx*cz
m[1][2] = sx*cy
m[2][0] = cx*sy*cz + sx*sz
m[2][1] = cx*sy*sz  sx*cz
m[2][2] = cx*cy
xa, ya and za are angles for x, y and z axis respectivly.
The above code will generate a matrix based on euler angles so its really
easy to pan the camera say 5 degrees to the left but this also means you
have no idea what the camera is actually looking at, what if you want to
follow a spaceship flying across the screen? You could calculate the angles
for rotation based on a camera position and a target position using sine and
cosine and that usually works fine but there is another, better way.
A camera matrix and how to use it

If we think about what we want for a minute, we need a system where we can
specify a camera position and what to look at, we also want to be able to
roll the camera around its own axis, it is still possible to accomplish all
this using trigonometri but there is always the Gimbal lock to look out for
where rotation around one axis cancel out rotation around another axis.
We can build a matrix without using trigonometri, its quite easy if you know
some basic 3D maths, lets have a look how to do it without going into
too much detail how matrices work (there are plenty of online tutorials).
; Get the look at vector from the position and target
look.x = camera_pos_x  camera_target_x
look.y = camera_pos_y  camera_target_y
look.z = camera_pos_z  camera_target_z
; Normalise the lookat vector
len = 1.0 / sqrt (look_x*look_x + look_y*look_y + look_z*look_z)
look_x = look_x*len
look_y = look_y*len
look_z = look_z*len
; We have to decide what is up in our world, up is usually (0,1,0)
; or something like that depending on what your world looks like.
; If we change this we can roll the camera.
; Using a cross product here we get the vector pointing right (or left
; depending on how you want it)
; right = up x look (cross product)
right_x = up_y*look_z  up_z*look_y
right_y = up_z*look_x  up_x*look_z
right_z = up_x*look_y  up_y*look_x
; Normalise(right)
len = 1.0f / sqrt (right_x*right_x + right_y*right_y + right_z*right_z)
right_x = right_x*len
right_y = right_y*len
right_z = right_z*len
/* Up = Look x Right */
; Even if we said up is pointing right up we dont actually know what
; up is until we have done another cross product
up_x = look_y*right_z  look_z*right_y
up_y = look_z*right_x  look_x*right_z
up_z = look_x*right_y  look_y*right_x
; Make sure up is normalised
len = 1.0 / sqrtf (up_x*up_x + up_y*up_y + up_z*up_z);
up_x = up_x*len
up_y = up_y*len
up_z = up_z*len
; Store the finished vectors
m[0][0] = right_x
m[1][0] = right_y
m[2][0] = right_z
m[0][1] = up_x
m[1][1] = up_y
m[2][1] = up_z
m[0][2] = look_x
m[1][2] = look_y
m[2][2] = look_z
If we apply this matrix to our vertices they will be transformed into camera
space ready for screen projection.
One thing to keep in mind is that this matrix might be wrong depending on
what our world looks like, ie if we have negative Z going into the screen
or something like that, if you use this code straight off you might have
to adjust a few things.
The way to control the camera roll is to give an up vector since working with
vectors like this can be rather tricky we calculate it with a bit of sine
and cosine.
x = sin(roll angle)
y = cos(roll angle)
z = 0
use this as up vector and specify the angle and you're sorted.
Here is an example of how this could be implemented in 68k, I'm using the
FPU for all calculations for best accuracy, this is quite important since
we normalise the vectors and by doing so we lose accuracy, especially if we
used fixed point.
The bit where the matrix is applied to the vertices can be written using
fxied point since its executed many times.
create_world_to_camera_matrix
; up vector
fmove.s #0,fp0
fmove.s #1,fp1
fmove.s #0,fp2
lea.l.upvec,a1
fmove.s fp0,0(a1)
fmove.s fp1,4(a1)
fmove.s fp2,8(a1)
; Camera position
fmove.s view_point_x,fp0
fmove.s view_point_y,fp1
fmove.s view_point_z,fp2
; Where to look at
fmove.s target_point_x,fp3
fmove.s target_point_y,fp4
fmove.s target_point_z,fp5
fsub.x fp3,fp0
fsub.x fp4,fp1
fsub.x fp5,fp2
fmove.x fp0,fp3
fmove.x fp1,fp4
fmove.x fp2,fp5
fmul.x fp3,fp3
fmul.x fp4,fp4
fmul.x fp5,fp5
fadd.x fp3,fp4
fadd.x fp4,fp5
fsqrt.x fp5
fdiv.x fp5,fp0
fdiv.x fp5,fp1
fdiv.x fp5,fp2
; store look
fmove.s fp0,rslt_02
fmove.s fp1,rslt_12
fmove.s fp2,rslt_22
lea.l.temp,a1
fmove.s fp0,0(a1)
fmove.s fp1,4(a1)
fmove.s fp2,8(a1)
lea.l .upvec,a0
bsr.crossnorm
; store right
fmove.s 0(a2),fp0
fmove.s 4(a2),fp1
fmove.s 8(a2),fp2
fmove.s fp0,rslt_00
fmove.s fp1,rslt_10
fmove.s fp2,rslt_20
move.l a1,a0
move.l a2,a1
bsr.s .crossnorm
fmove.s 0(a2),fp0
fmove.s 4(a2),fp1
fmove.s 8(a2),fp2
; store up
fmove.s fp0,rslt_01
fmove.s fp1,rslt_11
fmove.s fp2,rslt_21
rts
.upvec dc.s 0,1,0
.temp dc.s 0,0,0
.crossnorm
fmove.s 0(a0),fp0
fmove.s 4(a0),fp1
fmove.s 8(a0),fp2
fmove.s 0(a1),fp3
fmove.s 4(a1),fp4
fmove.s 8(a1),fp5
fmul.x fp5,fp1
fmul.x fp3,fp2
fmul.x fp4,fp0
fmul.x 8(a0),fp4
fmul.x 0(a0),fp5
fmul.x 4(a0),fp3
fsub.x fp4,fp1
fsub.x fp5,fp2
fsub.x fp3,fp0
fmove.x fp1,fp3
fmove.x fp2,fp4
fmove.x fp0,fp5
fmul.x fp3,fp3
fmul.x fp4,fp4
fmul.x fp5,fp5
fadd.x fp3,fp4
fadd.x fp4,fp5
fsqrt.x fp5
fdiv.x fp5,fp1
fdiv.x fp5,fp2
fdiv.x fp5,fp0
lea.l .vec,a2
fmove.s fp1,0(a2)
fmove.s fp2,4(a2)
fmove.s fp0,8(a2)
rts
.vec dc.s 0,0,0
world2cameramatrix
rslt_00 dc.s 0
rslt_10 dc.s 0
rslt_20 dc.s 0
rslt_01 dc.s 0
rslt_11 dc.s 0
rslt_21 dc.s 0
rslt_02 dc.s 0
rslt_12 dc.s 0
rslt_22 dc.s 0
; Camera position
view_point_x dc.s 100
view_point_y dc.s 0
view_point_z dc.s 0
; Target position
target_point_x dc.s 0
target_point_y dc.s 0
target_point_z dc.s 0
The following routine will apply the matrix to a vertex in x, y, z format
stored in a buffer called vertices, after transformation the vertices are
saved to camera_coords. Please note that both the matrix and all vertices
are in 32bit floating point format but they can easily be converted to
fixed point for increased speed.
This code can be optimised quite a lot with various tricks but I think for
educational purposes its best kept like this.
apply_matrix
lea.l vertices,a1
lea.l camera_coords,a2
fmove.s view_point_x,fp5
fmove.s view_point_y,fp6
fmove.s view_point_z,fp7
lea.l world2cameramatrix,a5
.loop
move.l a5,a6
fmove.s (a1)+,fp0
fmove.s (a1)+,fp1
fmove.s (a1)+,fp2
fmove.s view_point_x,fp5
fmove.s view_point_y,fp6
fmove.s view_point_z,fp7
fadd.x fp5,fp0
fadd.x fp6,fp1
fadd.x fp7,fp2
fmove.s (a6)+,fp3
fmove.s (a6)+,fp4
fmove.s (a6)+,fp5
fmul.x fp0,fp3
fmul.x fp1,fp4
fmul.x fp2,fp5
fadd.x fp3,fp4
fadd.x fp4,fp5
fmove.s fp5,(a2)+
fmove.s (a6)+,fp3
fmove.s (a6)+,fp4
fmove.s (a6)+,fp5
fmul.x fp0,fp3
fmul.x fp1,fp4
fmul.x fp2,fp5
fadd.x fp3,fp4
fadd.x fp4,fp5
fmove.s fp5,(a2)+
fmove.s (a6)+,fp3
fmove.s (a6)+,fp4
fmove.s (a6)+,fp5
fmul.x fp0,fp3
fmul.x fp1,fp4
fmul.x fp2,fp5
fadd.x fp3,fp4
fadd.x fp4,fp5
fmove.s fp5,(a2)+
Summary

I know I have left some things out in this article like the use of 4x4
matrices and things like screen projection but I wanted show an easy
way to generate a camera matrix and the use of 4x4 matrices isnt really
needed for most games/demos.
Hopefully this artciel will be enough to get you started writing your own
3D engines with proper camera movements.
If you have any questions feel free to ask me on irc or email me.
Fredrik Egeberg (deez  deez@algonet.se)
