Texturing, Bumpmapping of Spheres in Realtime

@DrWatson

Published in 

atari

 · 1 year ago

Subject: Texturing, Bumpmapping of Spheres in Realtime
Date: 23 Apr 1995 20:27:07 GMT

FAST TEXTURING OF SPHERES

Two weeks ago 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 even though. 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 this coordinates always into that spherical coordinate system (SCS), in which the thing that you want to to is particularly easy.

The conversion between different SCS can be done fast using a lookup-table.

SPHERICAL COORDINATES (SC)

Spherical 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 regard 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 were 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:

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 SCS's: 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:

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 straightforward way:

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 sufficient for storing a SC.

The lookuptable for the converting between the two SCS's in then a array of short int's 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 a 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 horizontal span that is covered by the sphere.

I will use a kartesian koordinate 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 particularly 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 lookup tables.

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 x = -r to r 
 for y = -sqrt(r*r-y*y) to sqrt(r*r-y*y) 
   beta1 = ARCSIN_TABLE[x*S/(r*2)+S/2] 
   alpha1 = ARCCOS_TABLE[y*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.

Here's a pseudocode to compute a intensity-texture:

for alpha = 0 to S 
 for beta = 0 to S 
  (x,y,z) = convertSCtokartesian(alpha,beta) 
  INTENSITY_TEXTURE[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 similar 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 int's of the size S*S to store the bump-map.

Once I got the surface-normal I have to compute the intensity.

If the incident light is parallel, this can be done using intensity-textures, too. Note, that a intensity-texture then can be seen as a mapping from surface-normals to intensities.

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,INTENSITY_TEXTURE[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 intensity-texture, 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,INTENSITY_TEXURE[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 regarded while initializing the 2d-lookuptable.

To compute the intensity-texture 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 texture spheres that are lit by more than one lightsource.

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 should be a efficient way to do a appropriate test.

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 intensity-texture (a one-dimensional texture is then sufficient).

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 optimized highly. I achieved 17 fps at texturing a sphere of 100 pixel diameter on a 286/12Mhz.

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)

I will post a source for Watcom/Turbo C++ that does the things above to comp.sys.ibm.pc.demos.

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, 4.22.1995