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: Select all
[ A B C ]
M = [ D E F ]
[ G H I ]
[ Ax + By + Cz ]
P' = MP = [ Dx + Ey + Fz ]
[ Gx + Hy + Iz ]
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.