Find out how to create surfaces and add illumination to make your models more realistic
Raise your hand if you haven’t seen Toy Story — the computer-animated extravaganza from Walt Disney Pictures and Pixar. For those of you who missed out, Toy Story, was the first fully computer-animated feature film in the history of motion pictures. I mention this in order to illustrate the role 3D computer graphics are beginning to play in our society. As I noted back in my first column on this topic, 3D computer graphics have made the leap from the benches of government and university laboratories into the heart of corporate America.
Now, it may surprise you to know that the techniques I’ve demonstrated in this column and the techniques used by the folks at Pixar in Toy Story have a lot in common. We certainly won’t be covering everything the guys at Pixar know in this series of columns, but the material presented here will provide you with the foundation that all 3D computer graphic concepts rest upon. After all, 3D computer graphics, whether used in a movie like Toy Story or in an applet in one of my columns, begins with a model of the world (Toy Story required over 400) and ends with a picture on a computer screen.
With this in mind, let’s begin.
Looking beneath the surface
Last month I presented a portal that rendered a scene (or model) as a wire frame. To see that applet in action, take a quick look back at “
3D computer graphics: Slide it, spin it, make it move — transforming your virtual world
.”
While wire-frame drawings are a fit vehicle to introduce the topic of 3D computer graphics, they suffer from several shortcomings. In particular, they display only the edges of a model. Of course, that limitation is also one of their advantages. Edge information is faster to process and to display. Consequently, large wire-frame drawings often can be manipulated in real time, while more realistic drawings cannot.
None the less, the illusion of reality suffers. Real objects have surfaces, or faces, not just edges (you can’t see through them as you can with a wire-frame object). The modeling environment we’ve been working with in previous months contained information about edges only. Remember, the basic unit of construction is the triangle. To add surfaces to our model, we simply need to draw solid triangles instead of just their edges.
No problem, right? Wrong. Unfortunately, the order in which we draw these triangles is very important. In fact, it is the most challenging part of creating the applet in this article.
The painter’s algorithm provides us with one way to properly draw surfaces. Let’s take a look at this technique.
The painter’s algorithm
The painter’s algorithm is based on a very simple observation: surfaces that are farther away from us are blocked by surfaces that are closer to us.
Take a look at the following series of illustrations, which show a cube in the process of being drawn — first the back face (A), then the two sides (B), and finally the front (C). The faces drawn last (those toward the front) obscure the appropriate parts of the surfaces drawn earliest (those toward the rear), creating a very natural effect. This is the essence of the painter’s algorithm — draw the farthest faces first and the nearest faces last.
One caveat: Although the painter’s algorithm is computationally and conceptually much easier than most alternatives, it does suffer from several flaws.
Its major weakness stems from the difficulty in defining what “farther away” really means in a quantifiable sense — there are several possibilities, and none of them work in every case. Thus, it’s possible to create worlds that the painter’s algorithm will not draw correctly.
Perhaps the most obvious example of where the painter’s algorithm falls short is with intersecting surfaces. Take a look at the figure Intersecting triangles. The left side of the figure shows how intersecting surfaces should appear — each triangle partially overlaps the other. The right side of the figure shows how the painter’s algorithm would draw the same set of triangles. Because the painter’s algorithm draws each surface in its entirety, the triangles will not appear to intersect; one triangle will always be drawn on top of the other.
If you have control of the model, however, you can often modify it to fix problem areas. Simply moving one of the objects or adjusting the size or location of some of the surfaces, for example, can take care of any glitches. As you interact with the solid model of the beach scene shown later in the article, you will notice occasional flaws. I have deliberately left these flaws in order to expose you to the weaknesses of the painter’s algorithm. I’ll leave it as an exercise for you to solve the problems. (Hint: Try modifying the placement of the beach chair.)
Ordering the surfaces
As I mentioned earlier, the most challenging part of the solid model applet is implementing the ordering of the surfaces.
To begin, we need some method for calculating a surface’s relative distance from the portal. There are several ways of doing this. I’ve selected the simplest method I know of — calculating the distance from the portal to the geometric center of the surface, also known as its center of gravity (point c). This technique is detailed in the following diagram.
We want to find the distance of the center of gravity (point c) to the portal; that is, we want to calculate the value of its z coordinate (its depth). We do this by taking the average of the z coordinates of the other three points:
Next, we need some method for sorting the surfaces efficiently. I stress efficiency at this point because inefficiencies in a sorting algorithm can totally blow the performance of a program.
The most efficient, general-purpose sort is one based on C.A.R. Hoare’s quicksort algorithm. My implementation of this algorithm, QuickSort.java, is general enough for use in your own projects. Our application calls for a specialized subclass of QuickSort called TriangleShapeQuickSort.java. The following code segment shows how the surfaces are sorted:
// this is the instance that will be doing
// the sorting...
private TriangleShapeQuickSort _tsqs = new TriangleShapeQuickSort();
// this is called when it's time to paint
// a scene...
public void paintScene(Graphics gr)
{
Vector vec = new Vector();
Object o = null;
Enumeration enum = getScene().elements();
// loop through all of the elements that make
// up a scene, store the triangles...
while (enum.hasMoreElements())
{
o = enum.nextElement();
if (o instanceof TriangleShape)
{
vec.addElement(o);
}
}
// copy the vector into an array
// for sorting...
Object [] rgo = new Object [ vec.size() ];
vec.copyInto(rgo);
_tsqs.sort(rgo); // sort!!
// loop through all of the triangles and
// paint each one...
for (int i = 0; i < rgo.length; i++)
{
o = rgo[i];
TriangleShape ts = (TriangleShape)o;
paintScene(gr, ts);
}
}
Let’s take a closer look at what’s going on in this code. When it’s time to draw the scene, we get every surface from the scene and put it in a Vector. Once the Vector is filled, we copy it into an array and sort it using the sort() method of the TriangleShapeQuickSort instance. After sorting, the instances in the array are ordered according to their distance from the portal. At this point, all that remains is to step through the array and paint each surface in turn. The result is the applet shown here.
Pretty neat, but we’re still lacking the one thing that can make our scene truly realistic — light and shading.
Let there be light: Illumination basics
Shading is an artistic technique used to represent gradations of light. Correctly done, the use of shading can really bring a scene to life. We’re going to work though a simple technique for surface shading.
Take a look at the figure Illuminating a surface. Assume that each face has the same amount of surface area. Each ray of light in the figure represents a fixed amount of illumination. The more rays that strike a surface, the better illuminated that surface is. In the illustration, surface B is illuminated twice as brightly as surface A.
Now consider the illustration in the figure Light distribution on surfaces of varying angles. The object in this figure has three similar surfaces, each at a different angle with respect to the light source. Assuming the density of the light is uniformly distributed, surfaces that are perpendicular to the light rays (in this case, surface C) receive more illumination than surfaces that are at more oblique angles (in this case, surfaces A and B).
Let’s look at how we can put this to use.
In order to calculate the amount of illumination a surface receives from a light source, we essentially need to calculate the angle between the light source and the surface — or more correctly, between a light source and a line perpendicular to the surface.
The following figure depicts a surface receiving illumination. Line n, called the normal, is perpendicular to the surface. The angle between the normal and the light rays is called R.
Our next step is to translate R into a shade of gray, which will allow us to add shading to our application. I’m going to throw a bit of math your way, so if math’s not your thing, just hang tight; the applet is coming up next.
If we calculate the cosine of R, we’ll obtain a number between 0 and 1. We can use this number to assign a level of gray to the surface: 0 being black and 1 being white. The result is a more realistic beach scene applet, shown here.
Let’s take a quick look at the code before we finish.
private void paintScene(Graphics gr, TriangleShape ts)
{
.
.
.
Coordinates n0 = Algorithms.getCentroid(ts);
Coordinates n1 = Algorithms.getNormal(ts);
Coordinates n2 = Algorithms.getLine(n0, coordsLight);
float dot1 = (float)Algorithms.dot(n1, n2);
float dot = (float)(dot1 / 2.0 + 0.5);
Color clr = new Color(dot, dot, dot);
gr.setColor(clr);
gr.fillPolygon(rgx, rgy, 4);
.
.
.
The Algorithms.getCentroid() method returns the coordinates of the center of gravity of the triangular surface. The Algorithms.getNormal() method returns the surface’s normal. And the Algorithms.getLine() method uses the location of the center of gravity and the location of the light source to find a ray of light stiking the surface.
The cosine of the angle between the two (the location of the center of gravity and the location of the light source) is calculated by the Algorithms.dot() method and returns a value between -1.0 and 1.0. This number is divided by two and added to 0.5 to make a number between 0.0 and 1.0. A new color — a shade of gray — is created using this calculated value as its red, blue, and green components. The color is used to draw a filled polygon representing the triangle.
You can find the complete source code for the work we did this month in the Resources section at the end of this article.
Conclusion
Well, we’re almost done with our 3D graphics series. Next month I’ll wrap things up with a discussion of VRML (Virtual Reality Modeling Language). I’ll explain what VRML is, how to read it, and how to translate it into something one of our portals can understand — and display! I’ll see you then.
