Spherical projections, part deux
SLJ 12/4/97
The first writeup described how to project the x-y plane onto a sphere
centered at the origin and project it through the origin. It would be
pretty nifty though to project onto a sphere which is centered at
someplace other than the origin -- imagine a picture reflected in
a ball which is some distance away from the picture.
The strategy is the same as before: start on the computer screen,
trace backwards through the origin, and figure out the corresponding
point in the image. Consider a sphere which is up on the z-axis
somewhere:
x^2 + y^2 + (z-z0)^2 = r^2
As before, we start at the point (x0,y0,d), where d=magnification factor,
and backtrack through the origin:
x=x0*t, y=y0*t, z=d*t
(x0^2 + y0^2 + d^2)*t^2 - 2*d*z0*t + (z0^2 - r^2) = 0
This is a quadratic polynomial in t, so the solution is given by the
quadratic formula:
t = (2*d*z0 +/- sqrt(4*d^2*z0^2 - 4*(z0^2-r^2)*(x0^2+y0^2+d^2)))
/ 2*(x0^2 + y0^2 + d^2)
where d, z0, and r are all constants. The only quantity which needs to
be computed is x0^2 + y0^2; let
a=x0^2 + y0^2,
f(a) = (c1 +/- sqrt(c2 - c3*(a+d^2))) / (2*(a+d^2))
t = f(a)
x = t*x0, y=t*y0
If z0 (the center of the sphere) is greater than r (the radius of the
sphere), then the sphere sits completely above the x-y plane. This
has several important ramifications:
1) There are two intersection points with the sphere; these are
the +/- roots of f(a). One (the negative root) corresponds to
the bottom hemisphere, and the other (the positive root) corresponds
to the upper hemisphere.
2) There are only a finite number of points which will appear in
the projection through the origin! That is, if you take this
sphere and project through the origin, it will be a circle in
the projection plane at z=d. Only the points inside of this
circle can be traced back to hit the sphere. Points outside
of the circle will generate a negative number in the sqrt()
part of f(a).
The equation of this circle in the projection plane is
x0^2 + y0^2 = d^2*r^2 / (z0^2 - r^2)
Thus only points inside this circle should be considered.
Implementation
--------------
To calculate x0^2 + y0^2 and then use it as a table lookup can
be a bit tricky, since the result will generally be greater than 8 bits.
One option is to use several sets of tables, and use the high byte of
the x0^2 + y0^2 value as an index into the specific table to use. That
is, let
f0(a) = f(a)
f1(a) = f(a+256)
f2(a) = f(a+2*256)
f3(a) = f(a+3*256)
...
Then, let s = x0^2 + y0^2. The high byte of s tells which table to use.
If it is zero, then use f0; if it is one, then use f1; and so on. If
the tables are page-aligned, then this just amounts to adding #>s to #>f0
to get the proper table index. Obviously this won't work for large pictures,
but reasonably sized pictures should work just fine. For example, if
x0=0..64 then x0^2 +y0^2 = 0..2^12 = 4 bits in the high byte = 16 tables.
(I skipped 2^12; think of it as 2^12-1).
Symmetries
----------
The calculation can be improved considerably by taking symmetry
into account. The quantity x0^2 + y0^2 is the same for the four points
(x0,y0) (-x0,y0) (-x0,-y0) (x0,-y0)
and the corresponding point on the sphere differs by the negative signs
in exactly the same way (i.e. if (x0,y0) -> (x,y) then (-x0,y0) -> (-x,y)
etc.). This means that the point calculation needs to be done only
once for every four points.
Moreover, it gives a way of doubling the picture size for a given
number of tables. That is, we can use a 128x128 screen area with only
sixteen f(a) tables -- the tables given above, for x0=0..64, since -64..0
is given by symmetry.
Scrolling
---------
Sometimes it might be neat to scroll the picture across the
sphere. This is easily done by simply scrolling the picture in the
plane -- i.e. instead of x=t*x0, use x=t*x0+const to scroll in the
x-direction. The reflection of the picture in the sphere will appear
to move across the sphere.
Well, that hopefully wraps up these waking-up thoughts -- on to new
stuff!