Previous    Next

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.

##### Screenshot Lighting a polygon with just one shade isn't accurate because different parts of the polygon might have different angles and distances to the light source.

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.

##### Screenshot The minimum bounding rectangle of a polygon always 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.

##### Screenshot The bounding rectangle of a polygon that is aligned with the texture coordinates can waste memory.

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);
d.setTo(v);
d.multiply(vMin);
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;
}
```

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.

##### Screenshot The shade map covers the entire surface of the polygon and is merged with the texture to create a shaded surface.

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.

##### Screenshot Interpolating the shade map gives the final surface a smoother look.

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.

##### Screenshot The shade map is given a small border around the edges to make up for any floating-point imprecision when texture mapping. The shade map is aligned with the polygon bounds, not the surface bounds.

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.

```public static final int SURFACE_BORDER_SIZE = 1;
public static final int SHADE_RES_BITS = 4;
...
/**
Builds the shade map for this surface from the specified
list of point lights and the ambient light intensity.
*/
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
// calculate the shade map origin
Vector3D origin = new Vector3D(surfaceBounds.getOrigin());
Vector3D du = new Vector3D(surfaceBounds.getDirectionU());
Vector3D dv = new Vector3D(surfaceBounds.getDirectionV());
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());
for (int v=0; v<shadeMapHeight; v++) {
point.setTo(origin);
for (int u=0; u<shadeMapWidth; u++) {
pointLights, ambientLightIntensity);
}
}
}
/**
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);
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;
startU;
startV;
for (int v=startV; v<startV + height; v++) {
sourceTexture.setCurrRow(v);
int u = startU;
int amount = SURFACE_BORDER_SIZE;
while (u < startU + width) {
// keep drawing until we need to recalculate
int endU = Math.min(startU + width, u + amount);
while (u < endU) {
buffer[offset++] =
sourceTexture.getColorCurrRow(u,
u++;
}
}
}
}
/**
(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 offset = (u >> SHADE_RES_BITS) +
// the value to increment as u increments
}
/**
specified (u,v) location.
*/
public int getShade(int u, int v) {
}
```

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.

```/**
Creates a ShadedSurface for the specified polygon. The
shade map is created from the specified list of point
lights and ambient light intensity.
*/
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
surface.setTexture(texture, textureBounds);
surface.setSurfaceBounds(surfaceBounds);
// create the surface's shade map
// 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.*;
/**
polygon.
*/
public final class ShadedSurface extends Texture {
public static final int SURFACE_BORDER_SIZE = 1;
public static final int SHADE_RES_BITS = 4;
private short[] buffer;
private SoftReference bufferReference;
private boolean dirty;
private Rectangle3D sourceTextureBounds;
private Rectangle3D surfaceBounds;
// for incrementally calculating shade values
/**
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.
*/
this.sourceTexture = texture;
sourceTextureBounds.setWidth(texture.getWidth());
sourceTextureBounds.setHeight(texture.getHeight());
}
/**
Sets the source texture and source bounds for this
*/
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.

```package com.brackeen.javagamebook.graphics3D;
import java.awt.*;
import java.awt.image.*;
import java.util.List;
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.
*/
extends FastTexturedPolygonRenderer
{
private List builtSurfaces = new LinkedList();
ViewWindow viewWindow)
{
this(camera, viewWindow, true);
}
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()) {
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
*/
protected void buildSurface() {
// build surface, if needed
if (sourcePolygon instanceof TexturedPolygon3D) {
Texture texture =
((TexturedPolygon3D)sourcePolygon).getTexture();
if (surface.isCleared()) {
surface.buildSurface();
}
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.