Progress Thread -- Pleiades (Working Title)

Progress Thread -- Pleiades (Working Title)
by on (#176869)
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:

    [ A B C ]
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.
Re: Progress Thread -- Pleiades (Working Title)
by on (#176971)
Turns out, using this seriously fast multiplication routine, I can actually perform all the multiplications per point without sacrificing speed. This lets me have all the point coordinates in RAM and move them arbitrarily. It also lets me rotate about any point instead of just the origin.
Re: Progress Thread -- Pleiades (Working Title)
by on (#176987)
Well, you still can do something with the BG. Maybe a hazy dim band, angled appropriately to represent when you're looking into the galactic plane(Milky Way)?