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!