Understandably, my Super Smash Bros. for NES doesn't qualify for the competition, so I decided to work on a space-themed game that can also go on the competition cartridge. I'm thinking something like Elite -- you can travel between the systems in the Pleiades cluster, trading, exploring, and fighting.
So far, I have this tech demo -- a 3D star rendering. Press Up, Down, Left, Right, A, and B to rotate the points on an axis. The grey section of the screen is the amount of time I have used up in rendering all 18 points. The bright stars are the 9 main stars in the Pleiades cluster, along with the relatively minor HIP 17572, which serves as a stop-over between the two "lobes" of the group. These stars are close by, so we have accurate measurements of their distance from the Sun and their locations in the sky. I used this to find their positions in 3D coordinates. I also render a fainter cube in the middle for testing.
My technique is based on this article, which derives a way calculate a 3D rotation matrix without any multiplication. In short, a 3D rotation is a combination of rotations in all 3 axes. Each rotation can be represented as a simple matrix, with sines, cosines, zeros, and ones. To calculate the new coordinates of a point, simply multiply their coordinates by each matrix. To save time, we can multiply the 3 axis rotation matrices together first. The article cleverly uses trig identities to eliminate all multiplication from this calculation. Sine and cosine are stored in a table for quick lookup. See the article for details on the derivation.
Once I have the 9 element matrix M, rotating a point P to P' with it would look like this:
You might expect that I would need 9 multiplications to calculate each point. I was able to make it work with only a few additions instead. To do this, I precompute shifts for all 9 matrix elements. Essentially, I have a table with A*1, A*2, A*4, A*8, A*16, A*32, and A*64, and the same for B, C, D, E, F, G, H, and I.
To calculate Ax without a full multiplication, I constrain the coordinates as well, saving them using two powers. If x is 14, then I save it as something like 4 and -1. That means that x is equal to 2^4 - 2^1. Some numbers are not representable this way. 13, for example, is not, but we can approximate it with 2^3+2^2=12, or 2^4-2^1=14. I wrote a program to find the best approximation for all of the stars' coordinates. There is very little error.
Right now, I am using an orthographic projection. I might switch to using a perspective projection -- this means that closer objects actually look closer. The key calculation is to calculate a scaling factor fov/(fov+z). Fov is a constant, so I can use a table of precomputed fov factors to eliminate the division. Both x and y are multiplied by this factor. This will require performing 2 actual multiplications per point.
Using my current technique, I could probably render 64 points if I drop the frame rate to 30. That could be used to render background stars in a celestial sphere. I also want to be able to render a few points at arbitrary locations, to show the location of the player's ship, for example. These will need to perform all 9 multiplications. Luckily, there are algorithms for quickly calculating the 8x8->16 bit multiplication using a table of squares.
So far, I have this tech demo -- a 3D star rendering. Press Up, Down, Left, Right, A, and B to rotate the points on an axis. The grey section of the screen is the amount of time I have used up in rendering all 18 points. The bright stars are the 9 main stars in the Pleiades cluster, along with the relatively minor HIP 17572, which serves as a stop-over between the two "lobes" of the group. These stars are close by, so we have accurate measurements of their distance from the Sun and their locations in the sky. I used this to find their positions in 3D coordinates. I also render a fainter cube in the middle for testing.
My technique is based on this article, which derives a way calculate a 3D rotation matrix without any multiplication. In short, a 3D rotation is a combination of rotations in all 3 axes. Each rotation can be represented as a simple matrix, with sines, cosines, zeros, and ones. To calculate the new coordinates of a point, simply multiply their coordinates by each matrix. To save time, we can multiply the 3 axis rotation matrices together first. The article cleverly uses trig identities to eliminate all multiplication from this calculation. Sine and cosine are stored in a table for quick lookup. See the article for details on the derivation.
Once I have the 9 element matrix M, rotating a point P to P' with it would look like this:
Code:
[ A B C ]
M = [ D E F ]
[ G H I ]
[ Ax + By + Cz ]
P' = MP = [ Dx + Ey + Fz ]
[ Gx + Hy + Iz ]
M = [ D E F ]
[ G H I ]
[ Ax + By + Cz ]
P' = MP = [ Dx + Ey + Fz ]
[ Gx + Hy + Iz ]
You might expect that I would need 9 multiplications to calculate each point. I was able to make it work with only a few additions instead. To do this, I precompute shifts for all 9 matrix elements. Essentially, I have a table with A*1, A*2, A*4, A*8, A*16, A*32, and A*64, and the same for B, C, D, E, F, G, H, and I.
To calculate Ax without a full multiplication, I constrain the coordinates as well, saving them using two powers. If x is 14, then I save it as something like 4 and -1. That means that x is equal to 2^4 - 2^1. Some numbers are not representable this way. 13, for example, is not, but we can approximate it with 2^3+2^2=12, or 2^4-2^1=14. I wrote a program to find the best approximation for all of the stars' coordinates. There is very little error.
Right now, I am using an orthographic projection. I might switch to using a perspective projection -- this means that closer objects actually look closer. The key calculation is to calculate a scaling factor fov/(fov+z). Fov is a constant, so I can use a table of precomputed fov factors to eliminate the division. Both x and y are multiplied by this factor. This will require performing 2 actual multiplications per point.
Using my current technique, I could probably render 64 points if I drop the frame rate to 30. That could be used to render background stars in a celestial sphere. I also want to be able to render a few points at arbitrary locations, to show the location of the player's ship, for example. These will need to perform all 9 multiplications. Luckily, there are algorithms for quickly calculating the 8x8->16 bit multiplication using a table of squares.