Advanced Lighting Using a Shade Map

The previous demo was cool and all, but making an entire polygon all the same shade isn't very accurate. Different parts of the polygon might have different angles and distances to the light source, as shown in Screenshot. This is especially true if the polygon is large.

To create a more realistic lighting effect, you could just break down all the polygons into smaller 16x16 polygons. Or, instead of breaking down polygons, another idea is to calculate a different light intensity value for every texel on the polygon. As you can imagine, calculating the light intensity for every texel is too expensive to do on the fly, especially if there are lots of lights in the world. Instead, you'll calculate the light intensities before the game starts and store these values in a polygon's shade map. To reduce the memory requirements of the shade map, you could calculate only the correct light intensity every few pixels-for example, on a 16x16 grid. This will keep the shade map relatively small compared to the overall size of the polygon.

Finding the Bounding Rectangle

This shade map will be a rectangular map that covers the entire surface of the polygon. There are a couple ways to find this rectangular shape, and one of these ways is to find the minimum bounding rectangle of a polygon, shown in Screenshot. The minimum bounding rectangle is the smallest rectangle needed to cover a polygon, and one edge of the rectangle shares at least one edge of the polygon.

However, you really need the rectangle to share the same orientation of the polygon's texture bounds so the shade map lines up properly with the texture map. This is the solution you'll use, but keep in mind that this solution has one drawback: It can waste some memory. For example, in Screenshot, the rectangular bounds that are aligned with the texture bounds have a much larger area than the polygon area.

Add a calcBoundingRectangle() method in TexturedPolygon3D to calculate the bounds of a polygon that is aligned with the texture bounds. This method uses dot products to find the desired length of the sides of the rectangle to cover every vertex of the polygon.

/**
 Calculates the bounding rectangle for this polygon that
 is aligned with the texture bounds.
*/
public Rectangle3D calcBoundingRectangle() {
 Vector3D u = new Vector3D(textureBounds.getDirectionU());
 Vector3D v = new Vector3D(textureBounds.getDirectionV());
 Vector3D d = new Vector3D();
 u.normalize();
 v.normalize();
 float uMin = 0;
 float uMax = 0;
 float vMin = 0;
 float vMax = 0;
 for (int i=0; i<getNumVertices(); i++) {
 d.setTo(getVertex(i));
 d.subtract(getVertex(0));
 float uLength = d.getDotProduct(u);
 float vLength = d.getDotProduct(v);
 uMin = Math.min(uLength, uMin);
 uMax = Math.max(uLength, uMax);
 vMin = Math.min(vLength, vMin);
 vMax = Math.max(vLength, vMax);
 }
 Rectangle3D boundingRect = new Rectangle3D();
 Vector3D origin = boundingRect.getOrigin();
 origin.setTo(getVertex(0));
 d.setTo(u);
 d.multiply(uMin);
 origin.add(d);
 d.setTo(v);
 d.multiply(vMin);
 origin.add(d);
 boundingRect.getDirectionU().setTo(u);
 boundingRect.getDirectionV().setTo(v);
 boundingRect.setWidth(uMax - uMin);
 boundingRect.setHeight(vMax - vMin);
 // explicitly set the normal since the texture directions
 // could create a normal negative to the polygon normal
 boundingRect.setNormal(getNormal());
 return boundingRect;
}

Applying the Shade Map

The next step is to determine when to apply the shade map to a polygon. One idea is to combine the shade map with the polygon's texture to create a shaded surface, as shown in Screenshot.

This basic technique creates a shaded surface that looks a little blocky around the shaded edges. To fix this, you can interpolate between shade values to create something that looks like Screenshot.

Instead of first creating a surface, another technique is to perform shading at the same time as texture mapping. This technique is feasible, but it cannot be optimized very well using shade map interpolation because calculating the interpolated shade value can be slow if performed for every pixel on screen. Using surfaces, on the other hand, is just as fast as texture mapping after the surfaces are built. Surfaces can use a large amount of memory, but we cover memory issues later. For now, let's write some code to create shade maps and shaded surfaces. First, to further define the geometry polygon's bounds, shade maps, and surfaces, take a look at Screenshot. In this figure, the surface bounds are slightly larger than the polygon bounds, to make up for any floating-point error during texture mapping. Floating-point error could make the resulting (x,y) surface coordinates incorrect by a texel or so. You don't want the texture mapping to calculate a value outside the bounds of the surface, and making sure the surface is slightly larger than the polygon bounds helps alleviate this issue. Also note that the shade map is aligned with the polygon bounds, not the surface bounds.

Building the Shade Map

Now we move on to building the shade map. Remember, you need to build the shade map only once for each polygon, unless the lights change or a polygon moves. In the renderer, you'll keep the shade map static, so you don't ever have to recalculate it. The code for building a shade map is in Listing 8.9, in the ShadedSurface class. The ShadedSurface class is a subclass of Texture that contains a source texture, the surface data, and a shade map.

Listing 8.9 Building the Shade Map in ShadedSurface.java

public static final int SURFACE_BORDER_SIZE = 1;
public static final int SHADE_RES_BITS = 4;
public static final int SHADE_RES = 1 << SHADE_RES_BITS;
public static final int SHADE_RES_MASK = SHADE_RES - 1;
public static final int SHADE_RES_SQ = SHADE_RES*SHADE_RES;
public static final int SHADE_RES_SQ_BITS = SHADE_RES_BITS*2;
...
/**
 Builds the shade map for this surface from the specified
 list of point lights and the ambient light intensity.
*/
public void buildShadeMap(List pointLights,
 float ambientLightIntensity)
{
 Vector3D surfaceNormal = surfaceBounds.getNormal();
 int polyWidth = (int)surfaceBounds.getWidth() -
 SURFACE_BORDER_SIZE*2;
 int polyHeight = (int)surfaceBounds.getHeight() -
 SURFACE_BORDER_SIZE*2;
 // assume SURFACE_BORDER_SIZE is <= SHADE_RES
 shadeMapWidth = polyWidth / SHADE_RES + 4;
 shadeMapHeight = polyHeight / SHADE_RES + 4;
 shadeMap = new byte[shadeMapWidth * shadeMapHeight];
 // calculate the shade map origin
 Vector3D origin = new Vector3D(surfaceBounds.getOrigin());
 Vector3D du = new Vector3D(surfaceBounds.getDirectionU());
 Vector3D dv = new Vector3D(surfaceBounds.getDirectionV());
 du.multiply(SHADE_RES - SURFACE_BORDER_SIZE);
 dv.multiply(SHADE_RES - SURFACE_BORDER_SIZE);
 origin.subtract(du);
 origin.subtract(dv);
 // calculate the shade for each sample point.
 Vector3D point = new Vector3D();
 du.setTo(surfaceBounds.getDirectionU());
 dv.setTo(surfaceBounds.getDirectionV());
 du.multiply(SHADE_RES);
 dv.multiply(SHADE_RES);
 for (int v=0; v<shadeMapHeight; v++) {
 point.setTo(origin);
 for (int u=0; u<shadeMapWidth; u++) {
 shadeMap[u + v * shadeMapWidth] =
 calcShade(surfaceNormal, point,
 pointLights, ambientLightIntensity);
 point.add(du);
 }
 origin.add(dv);
 }
}
/**
 Determine the shade of a point on the polygon.
 This computes the Lambertian reflection for a point on
 the plane. Each point light has an intensity and a
 distance falloff value, but no specular reflection or
 shadows from other polygons are computed. The value
 returned is from 0 to ShadedTexture.MAX_LEVEL.
*/
protected byte calcShade(Vector3D normal, Vector3D point,
 List pointLights, float ambientLightIntensity)
{
 float intensity = 0;
 Vector3D directionToLight = new Vector3D();
 for (int i=0; i<pointLights.size(); i++) {
 PointLight3D light = (PointLight3D)pointLights.get(i);
 directionToLight.setTo(light);
 directionToLight.subtract(point);
 float distance = directionToLight.length();
 directionToLight.normalize();
 float lightIntensity = light.getIntensity(distance)
 * directionToLight.getDotProduct(normal);
 lightIntensity = Math.min(lightIntensity, 1);
 lightIntensity = Math.max(lightIntensity, 0);
 intensity += lightIntensity;
 }
 intensity = Math.min(intensity, 1);
 intensity = Math.max(intensity, 0);
 intensity+=ambientLightIntensity;
 intensity = Math.min(intensity, 1);
 intensity = Math.max(intensity, 0);
 int level = Math.round(intensity*ShadedTexture.MAX_LEVEL);
 return (byte)level;
}

This code is fairly straightforward. The buildShadeMap() method builds a shade map for a surface, and the calcShade() method calculates the light intensity value for a point on the shade map. In the renderer, you create all the shade maps before the game starts, but another idea is to store the shade maps in a file and load the shade maps from this file. This way, the shade maps don't have to be recalculated at startup.

Building the Surface

Next, we move on to building the surface, shown in Listing 8.10. This involves two separate methods: one to interpolate between values in the shade map, and another to actually draw the texture with the correct shade onto the surface.

Listing 8.10 Building the Surface in ShadedSurface.java

/**
 Builds the surface. First, this method calls
 retrieveSurface() to see if the surface needs to be
 rebuilt. If not, the surface is built by tiling the
 source texture and apply the shade map.
*/
public void buildSurface() {
 if (retrieveSurface()) {
 return;
 }
 int width = (int)surfaceBounds.getWidth();
 int height = (int)surfaceBounds.getHeight();
 // create a new surface (buffer)
 newSurface(width, height);
 // builds the surface.
 // assume surface bounds and texture bounds are aligned
 // (possibly with different origins)
 Vector3D origin = sourceTextureBounds.getOrigin();
 Vector3D directionU = sourceTextureBounds.getDirectionU();
 Vector3D directionV = sourceTextureBounds.getDirectionV();
 Vector3D d = new Vector3D(surfaceBounds.getOrigin());
 d.subtract(origin);
 int startU = (int)((d.getDotProduct(directionU) -
 SURFACE_BORDER_SIZE));
 int startV = (int)((d.getDotProduct(directionV) -
 SURFACE_BORDER_SIZE));
 int offset = 0;
 int shadeMapOffsetU = SHADE_RES - SURFACE_BORDER_SIZE -
 startU;
 int shadeMapOffsetV = SHADE_RES - SURFACE_BORDER_SIZE -
 startV;
 for (int v=startV; v<startV + height; v++) {
 sourceTexture.setCurrRow(v);
 int u = startU;
 int amount = SURFACE_BORDER_SIZE;
 while (u < startU + width) {
 getInterpolatedShade(u + shadeMapOffsetU,
 v + shadeMapOffsetV);
 // keep drawing until we need to recalculate
 // the interpolated shade. (every SHADE_RES pixels)
 int endU = Math.min(startU + width, u + amount);
 while (u < endU) {
 buffer[offset++] =
 sourceTexture.getColorCurrRow(u,
 shadeValue >> SHADE_RES_SQ_BITS);
 shadeValue+=shadeValueInc;
 u++;
 }
 amount = SHADE_RES;
 }
 }
}
/**
 Gets the shade (from the shade map) for the specified
 (u,v) location. The u and v values should be
 left-shifted by SHADE_RES_BITS, and the extra bits are
 used to interpolate between values. For an interpolation
 example, a location halfway between shade values 1 and 3
 would return 2.
*/
public int getInterpolatedShade(int u, int v) {
 int fracU = u & SHADE_RES_MASK;
 int fracV = v & SHADE_RES_MASK;
 int offset = (u >> SHADE_RES_BITS) +
 ((v >> SHADE_RES_BITS) * shadeMapWidth);
 int shade00 = (SHADE_RES-fracV) * shadeMap[offset];
 int shade01 = fracV * shadeMap[offset + shadeMapWidth];
 int shade10 = (SHADE_RES-fracV) * shadeMap[offset + 1];
 int shade11 = fracV * shadeMap[offset + shadeMapWidth + 1];
 shadeValue = SHADE_RES_SQ/2 +
 (SHADE_RES-fracU) * shade00 +
 (SHADE_RES-fracU) * shade01 +
 fracU * shade10 +
 fracU * shade11;
 // the value to increment as u increments
 shadeValueInc = -shade00 - shade01 + shade10 + shade11;
 return shadeValue >> SHADE_RES_SQ_BITS;
}
/**
 Gets the shade (from the built shade map) for the
 specified (u,v) location.
*/
public int getShade(int u, int v) {
 return shadeMap[u + v * shadeMapWidth];
}

Ideally, building surfaces needs to be fast because you're going to be building surfaces on the fly within the game. So, there's no optimizations applied to the buildSurface() method. For example, we've added a couple methods to the ShadedTexture class called setCurrRow() and getColorCurrRow(). Because you are building the surface one row at a time, you can use these methods instead of the getColor() method so the row offset doesn't have to be recalculated for every texel. The getInterpolatedShade() method gets the shade value at the specified location. You don't need to call this method for every texel, either, because you're building each row in the surface horizontally. You can use the shadeValueInc value to increment shadeValue for every texel. This way, you need to get the correct interpolated shade value only every 16 texels, similarly to how you optimized texture mapping. Finally, Listing 8.11 shows the code for actually creating a ShadedSurface.

Listing 8.11 Creating a ShadedSurface Instance in ShadedSurface.java

/**
 Creates a ShadedSurface for the specified polygon. The
 shade map is created from the specified list of point
 lights and ambient light intensity.
*/
public static void createShadedSurface(
 TexturedPolygon3D poly, ShadedTexture texture,
 Rectangle3D textureBounds,
 List lights, float ambientLightIntensity)
{
 // create the surface bounds
 poly.setTexture(texture, textureBounds);
 Rectangle3D surfaceBounds = poly.calcBoundingRectangle();
 // give the surfaceBounds a border to correct for
 // slight errors when texture mapping
 Vector3D du = new Vector3D(surfaceBounds.getDirectionU());
 Vector3D dv = new Vector3D(surfaceBounds.getDirectionV());
 du.multiply(SURFACE_BORDER_SIZE);
 dv.multiply(SURFACE_BORDER_SIZE);
 surfaceBounds.getOrigin().subtract(du);
 surfaceBounds.getOrigin().subtract(dv);
 int width = (int)Math.ceil(surfaceBounds.getWidth() +
 SURFACE_BORDER_SIZE*2);
 int height = (int)Math.ceil(surfaceBounds.getHeight() +
 SURFACE_BORDER_SIZE*2);
 surfaceBounds.setWidth(width);
 surfaceBounds.setHeight(height);
 // create the shaded surface texture
 ShadedSurface surface = new ShadedSurface(width, height);
 surface.setTexture(texture, textureBounds);
 surface.setSurfaceBounds(surfaceBounds);
 // create the surface's shade map
 surface.buildShadeMap(lights, ambientLightIntensity);
 // set the polygon's surface
 poly.setTexture(surface, surfaceBounds);
}

Caching Surfaces

Keep in mind that surfaces take up a lot of memory, so precreating a surface for every polygon in a game might not be feasible. Instead, you have to create a surface on the fly, and only for the polygons that are visible. Because building a surface is expensive, it's not a great idea to create every surface for every frame. Instead, the polygon renderer caches surfaces in a "visible" list. Only those surfaces that appear in the current frame are kept in the list, and the others are removed from memory to make room for more surfaces. This works for a lot of conditions, but you're probably thinking of cases in which a polygon appears often but is not necessarily in every frame. For example, if the player is turning quickly left and right, getting a look at everything around, a surface could appear and reappear, being re-created every time it appears. In situations like these, the garbage collector probably never even got a chance to throw away the surface memory in the first place. Wouldn't it be great if, instead of rebuilding a surface, you just asked the garbage collector to give it back to you if it wasn't already garbage-collected? Well, you can. This is accomplished using soft references. A SoftReference object enables you to reference an object softly, as opposed to referencing it using a normal, strong reference. If only a soft reference to an object exists (that is, an object is softly reachable), the garbage collector has the option to clean it up. Usually, the garbage collector cleans up other objects before it cleans up softly reachable ones. Also, all softly reachable objects are cleaned before the VM throws an OutOfMemoryException. In the ShadedSurface class, you create a new SoftReference to the surface's buffer like this:

/**
 Creates a new surface and add a SoftReference to it.
*/
protected void newSurface(int width, int height) {
 buffer = new short[width*height]
 bufferReference = new SoftReference(buffer);
}

Later, if the polygon renderer determines that the surface is no longer visible, the strong reference is removed:

/**
 Clears this surface, allowing the garbage collector to
 remove it from memory if needed.
*/
public void clearSurface() {
 buffer = null;
}

At this point, the buffer array is softly reachable, so the garbage collector has the option of removing it permanently from memory. Later, if you want the surface back, first you can test whether it's retrievable from the garbage collector. If so, SoftReference's get() method returns the object, which you then assign back to a strong reference.

/**
 If the buffer has been previously built and cleared but
 not yet removed from memory by the garbage collector,
 then this method attempts to retrieve it. Returns true if
 successful.
*/
public boolean retrieveSurface() {
 if (buffer == null) {
 buffer = (short[])bufferReference.get();
 }
 return !(buffer == null);
}

If the object was already garbage-collected, the get() method returns null and you need to rebuild the surface. So basically, you've implemented the equivalent of digging a surface out of the trashcan. Sun recommends that garbage collectors don't throw away recently used or recently created softly reachable objects, but it's not a requirement of the garbage collectors. You might need to implement another level of caching yourself, but using soft references is a good idea nonetheless. That's it for shaded surfaces. For good measure, the rest of the ShadedSurface class is in Listing 8.12.

Listing 8.12 Remaining Methods of ShadedSurface.java

package com.brackeen.javagamebook.graphics3D.texture;
import java.lang.ref.SoftReference;
import java.util.List;
import com.brackeen.javagamebook.math3D.*;
/**
 A ShadedSurface is a preshaded Texture that maps onto a
 polygon.
*/
public final class ShadedSurface extends Texture {
 public static final int SURFACE_BORDER_SIZE = 1;
 public static final int SHADE_RES_BITS = 4;
 public static final int SHADE_RES = 1 << SHADE_RES_BITS;
 public static final int SHADE_RES_MASK = SHADE_RES - 1;
 public static final int SHADE_RES_SQ = SHADE_RES*SHADE_RES;
 public static final int SHADE_RES_SQ_BITS = SHADE_RES_BITS*2;
 private short[] buffer;
 private SoftReference bufferReference;
 private boolean dirty;
 private ShadedTexture sourceTexture;
 private Rectangle3D sourceTextureBounds;
 private Rectangle3D surfaceBounds;
 private byte[] shadeMap;
 private int shadeMapWidth;
 private int shadeMapHeight;
 // for incrementally calculating shade values
 private int shadeValue;
 private int shadeValueInc;
 /**
 Creates a ShadedSurface with the specified width and
 height.
 */
 public ShadedSurface(int width, int height) {
 this(null, width, height);
 }
 /**
 Creates a ShadedSurface with the specified buffer,
 width, and height.
 */
 public ShadedSurface(short[] buffer, int width, int height) {
 super(width, height);
 this.buffer = buffer;
 bufferReference = new SoftReference(buffer);
 sourceTextureBounds = new Rectangle3D();
 dirty = true;
 }
 /**
 Gets the 16-bit color of the pixel at location (x,y) in
 the bitmap. The x and y values are assumed to be within
 the bounds of the surface; otherwise an
 ArrayIndexOutOfBoundsException occurs.
 */
 public short getColor(int x, int y) {
 return buffer[x + y * width];
 }
 /**
 Gets the 16-bit color of the pixel at location (x,y) in
 the bitmap. The x and y values are checked to be within
 the bounds of the surface, and if not, the pixel on the
 edge of the texture is returned.
 */
 public short getColorChecked(int x, int y) {
 if (x < 0) {
 x = 0;
 }
 else if (x >= width) {
 x = width-1;
 }
 if (y < 0) {
 y = 0;
 }
 else if (y >= height) {
 y = height-1;
 }
 return getColor(x,y);
 }
 /**
 Marks whether this surface is dirty. Surfaces marked as
 dirty may be cleared externally.
 */
 public void setDirty(boolean dirty) {
 this.dirty = dirty;
 }
 /**
 Checks whether this surface is dirty. Surfaces marked as
 dirty may be cleared externally.
 */
 public boolean isDirty() {
 return dirty;
 }
 /**
 Sets the source texture for this ShadedSurface.
 */
 public void setTexture(ShadedTexture texture) {
 this.sourceTexture = texture;
 sourceTextureBounds.setWidth(texture.getWidth());
 sourceTextureBounds.setHeight(texture.getHeight());
 }
 /**
 Sets the source texture and source bounds for this
 ShadedSurface.
 */
 public void setTexture(ShadedTexture texture,
 Rectangle3D bounds)
 {
 setTexture(texture);
 sourceTextureBounds.setTo(bounds);
 }
 /**
 Sets the surface bounds for this ShadedSurface.
 */
 public void setSurfaceBounds(Rectangle3D surfaceBounds) {
 this.surfaceBounds = surfaceBounds;
 }
 /**
 Gets the surface bounds for this ShadedSurface.
 */
 public Rectangle3D getSurfaceBounds() {
 return surfaceBounds;
 }
}

We've talked about nearly everything in the ShadedSurface class except the dirty flag. The dirty flag is irrelevant to the ShadedSurface itself-ShadedSurface doesn't care whether the flag is dirty. The dirty flag can be used externally to mark whether the surface data should be cleared. This idea is shown in the ShadedSurfacePolygonRenderer in Listing 8.13. It's not much different from any other renderer, except that it keeps a list of every surface that has been built. As discussed earlier, you build only the visible surfaces. If a surface is not visible (it is marked as dirty), the surface data is cleared and the surface is removed from the list.

Listing 8.13 ShadedSurfacePolygonRenderer.java

package com.brackeen.javagamebook.graphics3D;
import java.awt.*;
import java.awt.image.*;
import java.util.List;
import java.util.LinkedList;
import java.util.Iterator;
import com.brackeen.javagamebook.math3D.*;
import com.brackeen.javagamebook.graphics3D.texture.*;
/**
 The ShadedSurfacePolygonRenderer is a PolygonRenderer that
 renders polygons with ShadedSurfaces. It keeps track of
 built surfaces and clears any surfaces that weren't used
 in the last rendered frame, to save memory.
*/
public class ShadedSurfacePolygonRenderer
 extends FastTexturedPolygonRenderer
{
 private List builtSurfaces = new LinkedList();
 public ShadedSurfacePolygonRenderer(Transform3D camera,
 ViewWindow viewWindow)
 {
 this(camera, viewWindow, true);
 }
 public ShadedSurfacePolygonRenderer(Transform3D camera,
 ViewWindow viewWindow, boolean eraseView)
 {
 super(camera, viewWindow, eraseView);
 }
 public void endFrame(Graphics2D g) {
 super.endFrame(g);
 // clear all built surfaces that weren't used this frame.
 Iterator i = builtSurfaces.iterator();
 while (i.hasNext()) {
 ShadedSurface surface = (ShadedSurface)i.next();
 if (surface.isDirty()) {
 surface.clearSurface();
 i.remove();
 }
 else {
 surface.setDirty(true);
 }
 }
 }
 protected void drawCurrentPolygon(Graphics2D g) {
 buildSurface();
 super.drawCurrentPolygon(g);
 }
 /**
 Builds the surface of the polygon if it has a
 ShadedSurface that is cleared.
 */
 protected void buildSurface() {
 // build surface, if needed
 if (sourcePolygon instanceof TexturedPolygon3D) {
 Texture texture =
 ((TexturedPolygon3D)sourcePolygon).getTexture();
 if (texture instanceof ShadedSurface) {
 ShadedSurface surface =
 (ShadedSurface)texture;
 if (surface.isCleared()) {
 surface.buildSurface();
 builtSurfaces.add(surface);
 }
 surface.setDirty(false);
 }
 }
 }
}

The ShadedSurfacePolygonRenderer calls the buildSurface() method for every polygon. If the surface is cleared, it is built (or retrieved from the garbage collector) and added to the list of built surfaces.

Shaded Surface Demo

Now you'll create a demo using the shaded surfaces. The ShadingTest2 class is the same as the TextureMapTest2, except it creates a few PointLight3Ds and uses the ShadedSurfacePolygonRenderer. A screenshot from ShadingTest2 is shown in Screenshot.

Screenshot ShadingTest2 demonstrates shaded surfaces.

As usual, you can walk around the house and see it from all sides. The house has low ambient light intensity and a couple of strong point lights to show off some of the realistic, dramatic lighting you can create.