Fast Texture Mapping Of Spheres.
(Hans Kopp)
Changes to the original article in comp.graphics.algorithms:
- I added a short description of specular bumpmapping to this article.
- I removed some misspellings (thanks to Kathryn Linafelter),
and some incorrect technical terms.
In april 95 I posted an article that outlined a method for the
fast texture mapping of parallel projected spheres. In this article
I asked if this method is something new. I got two letters from
people who had developed their own algorithms for the fast texturing
of spheres, though both didn't publish them. There was no letter that
said that this algorithm has been published somewhere.
In this article I will try to give a better explanation of the
method I used, and I will describe some extensions, like
diffuse shading, bump mapping and specular shading of spheres in
realtime.
If you think that drawing spheres is a stupid thing to do,
read this article any way. Some of the techniques described can
be used in other algorithms as well.
All algorithms are scanline-orientated and require only
table-lookups, additions and some logical operations in the
interior loops. I implemented the algorithms in this article.
The basic idea of all algorithms is to store both points on the
sphere's surface and vectors in spherical coordinates, and to
convert these coordinates always into that spherical coordinate
system (SCS), in which the thing that you want to do is
particularly easy.
The conversion between different SCS can be done fast using
a lookup-table.
SPHERICAL COORDINATES (SC)
Sperical coordinates appear in a lot of math textbooks,
though I will give a short description, since SC are essential
for the algorithms below.
To describe a point in space using SC, you need two angles,
alpha e [0..2Pi[ and beta e [-Pi/2..Pi/2[, and the distance r
of the point to the origin. Since I use only points on spheres
and normalized vectors, r is always constant, and I don't have
to consider it any further.
A exemplary SCS is that of the earth, with the longitude as the
first angle alpha, and the latitude as the second angle beta.
Every SCS has a special axis, the polar axis. The polar axis is
the line where beta = -Pi/2 or beta = Pi/2, e.g. the polar axis
of the earth's SCS just connects the two poles of the earth.
To convert SC given in a SCS with the y-axis as polar-axis into
kartesian coordinates, take the following formula:
x = r*cos(alpha)*cos(beta)
y = r*sin(beta)
z = r*sin(alpha)*cos(beta)
For my purposes, the most important property of SCSs is that
it is very easy to rotate a point given in SC around the polar
axis of the SCS. You just have to add the desired angle to the
alpha-coordinate of the point. Nevertheless, it is very difficult
to rotate a point in SC around any other axis.
But, if you want to move a texture or anything else into an arbitrary
position, you have to rotate it at least around 3 axis. Why this is so
is discussed in many physic textbooks (any rigid body with a single,
fixed point has three degrees of freedom).
To solve this problem, I convert the SC from the first SCS into a
second SCS with a polar axis identical to the second axis of rotation.
In physics the second axis of rotation is chosen perpendicular to the
first. I will do the same.
Our problem at the moment is the conversion between the two SCSs:
We have a fixed point in a first SCS, and want to compute the SC of
that point in a second SCS.
I will derive the formula that does this for a first SCS with the
y-axis as polar axis and a second SCS with the z-axis as polar axis:
First, I convert the point from the first SCS into kartesian
coordinates:
x = cos(alpha1)*cos(beta1)
y = sin(beta1)
z = sin(alpha1)*cos(beta1)
Then, I convert the point from kartesian coordinates into the
second SCS:
beta2 = arcsin(z)
w = x/cos(beta2)
alpha2 = arccos(w)
if (y/cos(beta2) < 0) alpha2 = Pi*2 - alpha2
This is just the inverse of the mapping above, with y and z exchanged.
To compute this formula during rendering, I store the mapping in
a large 2D-lookuptable. How this is done is described below.
Now I can rotate the point in this second SCS. But I still have
to rotate the point around a third axis. To do this, I go in
a third SCS, that's polar axis is perpendicular to the second axis.
I can use the same mapping for the conversion from the second
SCS to the third SCS as I used for the conversion from the first to
the second SCS. Note, that the third SCS is different from the first!
For illustrations, what happens to a 3D-object when it is rotated
in this way, see a physics textbook that deals with 'rigid bodies' or
'euler angles'.
DOING IT FAST
To do this stuff fast during rendering, you first have to convert the
spherical coordinates into unsigned integers.
I do this in a straighforward way:
alpha_int = alpha/(2*pi)*S
beta_int = (beta+Pi/2)/Pi*S
where 0..S is the range of the integer-SC
(0 <= alpha_int < S, 0 <= beta_int < S)
I will store the two SC in a single integer, using the first
n bits for alpha_int, and the second n bits for beta_int (n = log2(S)):
alpha_beta_int = alpha + beta*S.
If you choose S=256, 16 bit are sufficent for storing a SC.
The lookuptable for the converting between the two SCSs in then a
array of short ints of the size S*S.
Here's pseudo-code, how to compute it:
for alpha_int1 = 0 to S-1
for beta_int1 = 0 to S-1
(alpha1,beta1) = convert_to_double(alpha_int1,beta_int1)
(x,y,z) = convert_to_kartesian(alpha1,beta1) (1)
(alpha2,beta2) = convert_to_spherical(x,y,z) (2)
(alpha_int2,beta_int2) = convert_to_int(alpha2,beta2)
LOOKUPTABLE[alpha_int1 + beta_int1*S] = alpha_int2 + beta_int2*S
next
next
The function in line (1) uses an SCS with the x-axis as polar axis,
while the function in line (2) uses a SCS with z-axis as polar axis.
TEXTURING
The parallel-projected textured sphere is drawn scanline by scanline
and pixel by pixel.
In every scanline I first have to compute the width of the sphere
in that scanline (scanconvert the contour of the projected sphere).
Then, compute the color of every pixel in this horizonal span that
is covered by the sphere.
I will use a kartesian coordinate system with the z-axis
perpendicular to the screen, and that has a origin that lies in the
center of the sphere.
At first, I have to map each pixel (x,y) onto the sphere, and
convert this point on the sphere into the SC (alpha,beta).
For this purpose, I use a initial SCS, so that this mapping is
particulary easy and I can do both, the mapping onto the sphere and
the conversion into SC, in a single step.
The SCS that fulfills this requirements has a polar axis that is
identical to the y-axis. (again, if you take the SCS of the earth,
you would look towards the equator).
The formula to do the mapping with a sphere of radius r is :
beta1 = asin(y/r)
alpha1 = acos(x/sqrt(r^2-y^2))
(2*sqrt(r^2-y^2) is the width of the sphere in scanline y)
This formula is computed during rendering using lookuptables.
Now I can rotate this point around the three axis, as described above.
The texture is stored also in SC so that the only thing remaining
is to look up the color. (the texture is an array of color-values
of the size S*S).
Here's the algorithm in pseudo-code:
for y = -r to r
for x = -sqrt(r*r-y*y) to sqrt(r*r-y*y)
beta1 = ARCSIN_TABLE[y*S/(r*2)+S/2]
alpha1 = ARCCOS_TABLE[x*S/(2*sqrt(r*r-y*y))+S/2] + phi
alpha_beta_2 = LOOKUPTABLE[alpha1 + beta1*S] + theta
alpha_beta_3 = LOOKUPTABLE[alpha_beta_2] + psi
putpixel(x,y,TEXTURE[alpha_beta_3])
next
next
where
ARCSIN_TABLE[i] = arcsin(i*2/S-1)*S/PI+S/2 , (i=0..S)
ARCCOS_TABLE[i] = arccos(i*2/S-1)*S/(PI*2) , (i=0..S)
phi, theta and psi are the angles used in the three rotations
In this pseudo-code I ignored the problem that e.g. alpha_beta_2
may become greater than S*S, but the 2D-lookuptable has only the
size S*S.
To solve this problem, you can either use masking-operations, or
use a 2D-lookuptable and a texture of the size S*S+S.
(LOOKUPTABLE[S*S+i] = LOOKUPTABLE[i] , i = 0..S)
You may have noticed, that the program contains still squareroots
and multiplications/divisions. It isn't too hard to remove these
using another lookuptable and fixed-point forward-differencing.
DIFFUSE SHADING
The intensity-distribution on a sphere that is lit by a lightsource
is also a texture. So, you can use the techniques in the chapter
above for diffuse shading of spheres. The only thing you have to
adapt is the preprocessing.
This technique is called 'environment-mapping' in graphics literature
(see e.g. Foley/vanDam). The 'intensity-texture" is actually
a mapping from surface normals to intensities or colors and
is called environment-map.
Here's a pseudocode to compute it:
for alpha = 0 to S
for beta = 0 to S
(x,y,z) = convertSCtokartesian(alpha,beta)
ENV_MAP[alpha+beta*S] = shade_sphere(x,y,z)
next
next
This method can be used to draw spheres that are lit by more than
one lightsource.
BUMP-MAPPING
A bump-map is similiar to a texture, with the difference that it does
not map color-values to points on the sphere, but surface-normals.
If you use bump-maps, you use the normal you found in the bump-map to
shade a given point on the sphere, and not the true normal of the
sphere at this point.
I store surface-normals in SC, too. So, I use a array of short ints
of the size S*S to store the bump-map.
Once I have the surface-normal I have to compute the intensity.
If the incident light is parallel, this can be done using
a environment-map, too.
You can rotate surface-normals in the same way as you rotated points
on the sphere.
a pseudo-code for bump-mapping follows :
for each pixel (x,y)
(alpha1,beta1) = converttoSC(x,y)
alpha1 = alpha1 + phi1
alpha_beta2 = LOOKUPTABLE[alpha1+beta1*S]+theta1
alpha_beta3 = LOOKUPTABLE[alpha_beta2]+psi1
normal1 = BUMPMAP[alpha_beta3]+phi2
normal2 = LOOKUPTABLE[normal1]+theta2
normal3 = LOOKUPTABLE[noraml2]+psi2
putpixel(x,y,ENV_MAP[normal3])
next
Note, that this algorithm involves 6 rotations:
first, I rotate the bump-map, using 3 rotations, then
I rotate the light-vector/surface-normal, using again 3 rotations.
The first few lines in this pseudo-code would be identical to
the code for the texture-mapping, so I abbreviated them.
SPECULAR SHADING
Specular shading is harder to do than diffuse shading.
For specular shading, I have to compute the direction of the ray
coming from the eye of the viewer, after it has been reflected on the
spheres surface. To do this, I go into that SCS, where the computing
of the reflected ray is particularly easy. This is the
SCS with the polar axis parallel to the direction of view.
In this SCS, the direction of the reflected ray can be computed by
multiplying the (integer-) beta-coordinate of a given
point by 2 (draw it!!!).
Again, all incident light should be parallel, so that the intensity
of the point depends only on the direction of the reflected ray.
The actual computation of the intensity is done using a
environment-map, that contains a intensity-value for every direction
of the ray.
here's the pseudo-code for specular shading:
for each pixel (x,y)
(alpha1,beta1) = converttoSC(x,y)
alpha_beta2 = LOOKUPTABLE[alpha1+beta1*S] (1)
alpha2 = alpha_beta2 and (S-1) (2)
beta2 = alpha_beta2/S
beta2 = beta2*2
alpha2 = alpha2 + phi
alpha_beta3 = LOOKUPTABLE[alpha2+beta2*S] + theta
alpha_beta4 = LOOKUPTABLE[alpha_beta3] + psi
putpixel(x,y,ENV_MAP[alpha_beta4]
next
The 'and' in line (2) is a bitwise and, that is used
to extract alpha2 out of alpha_beta2.
In line (1), LOOKUPTABLE[] is used to convert SC from
a SCS with the y-axis as polar axis to a SCS with the z-axis as
polar axis.
This has to be considered while initializing the 2d-lookuptable.
To compute the environment-map during preprocessing, use
the formula for specular shading that can be found e.g. in
Foley/VanDam:
I = I0*cos(delta)^e
'delta' is the angle between the reflected ray and the incident light.
'e' is a constant (e.g. 12).
Again, you can use this method to shade spheres that are lit by
more than one light source.
Note, that this algorithm does not test if the light does really
reach a point on the sphere. This is a serious flaw of this
algorithm, which has the effect that a lightsource behind
the sphere causes a lit circle at the margin of the sphere.
At least if you use only one lightsource, there is
an efficent way to do a appropriate test.
SPECULAR BUMPMAPPING
It is important to know that the mapping I used to switch between
SCS (LOOKUPTABLE) is the inverse of itself. This is necessary if
you want to do e.g. specular bumpmapping.
The pseudocode to do this follows:
for each pixel(x,y)
(alpha1,beta1) = converttoSC(x,y) (1)
alpha_beta2 = LOOKUPTABLE[alpha1+beta1*S] (2)
alpha_beta3 = LOOKUPTABLE[alpha_beta2+phi1]+theta1 (3)
alpha_beta4 = LOOKUPTABLE[alpha_beta3]+psi1
normal1 = BUMPMAP[alpha_beta4] (4)
normal2 = LOOKUPTABLE[normal1-psi1] (5)
normal3 = LOOKUPTABLE[normal2-theta1]-phi1
normal3_alpha = normal3 and (S-1) (6)
normal3_beta = normal3 / S
dir1_beta = normal3_beta*2
dir2 = LOOKUPTABLE[normal3_alpha+dir1_beta+phi2]+theta2 (7)
dir3 = LOOKUPTABLE[dir2]+psi2
putpixel(x,y,ENV_MAP[dir3] (8)
next
There are eight operations to do for every pixel:
1. Convert screen-coordinates to spherical coordinates
2. Go into a SCS (*) with the polar axis parallel to the direction
of view
3. Rotate the point using transformation 1, which describes the
orientation of the bumpmap
4. Get the normal from the bumpmap
5. Apply the inverse of transformation 1 to the normal, in order to
convert it into the initial (*) SCS
6. Multiply the beta-coordinate by 2 to get the direction of the
reflected ray.
7. Rotate this directional vector using transformation 2, which describes
the orientation of the lightsources.
8. Get the intensity for this pixel
THINGS I DIDN'T DO
The things in this chapter were neither tested nor implemented.
If a sphere is illuminated by a single lightsource, you can
use the symmetry of the intensity-distribution to
reduce either the number of table-lookups or the size of the
env-map (a one-dimensional map is then sufficent).
The use of spherical coordinates can be fruitful for other realtime-
graphic-algorithms as well. In the chapter 'Specular Shading'
I computed the direction of a reflected ray without multiplications.
It should be possible to do other calculations with normalized vectors
in spherical coordinates and without multiplications as well,
e.g. the computing of normalized vector-products or dot-products.
Remember the basic idea of the algorithms in this article:
To do something, go into that SCS, in which the thing you want to
do is particularly easy.
The method I used to bump-map spheres can be used to bump-map
polygons as well.
If you want to texture planets in a flight-simulator, the
rotation that has to be applied to the planets before drawing is given
in the form of an orthogonal matrix. But the texturing-algorithm
uses 3 angles to describe such a rotation. So, you have to
convert the orthogonal matrix into the three angles.
MISCELLANEOUS
Using assembler language the programs above can be highly optimized.
I achieved 17 fps at texturing a sphere of 100 pixel diameter
on a 286/12Mhz, and 250 fps for the same sphere on a 486/66Mhz.
Of course, the algorithms described can be used free of royalities.
This article may be redistributed.
Here's a short summary of some of the mail I got about the first
article:
Joe Lee and Mike Currington have developed their own algorithms for
the fast texture mapping of spheres with diffuse shading.
Diana Gruber send me some suggestions for improving the
C++-source. My code wasn't really well optimized.
Steve Metke suggested the extension of this algorithm to
ellipsoids. I agree, that this should be possible, though it
will not be easy.
Here's a list of books that might help you to implement or
understand the algorithms:
* Foley/vanDam (shading, introduction to 3D-graphics)
* PCGPE, Mark Feldmann et al.
(fixed-point math, assembler coding, shading,
introduction to 3D-graphics, planar texture mapping)
(the PCGPE can be found on a lot of ftp-servers)
* Classical Mechanics, H.Goldstein, (euler angles)
Please, don't ask for executables. Maybe I make a demo about
spheres in the next few months and upload it to a ftp-server.
I am a student of computer science at the university in
Erlangen/Germany.
Thanks for reading this,
Hans Kopp, 5.15.1995