Solid Objects and Back-Face Removal
The first demo, Simple3DTest1, draws every polygon in the order in which they appear in the polygon list. In this example, this technique doesn't have any negative impact because you are drawing a flat tree with no polygons that overlap. If you were drawing a solid shape-that is, a group of polygons with a front, a back, and sides-you would need a better algorithm for determining which polygons to draw and in what order. Otherwise, polygons in the back could appear over polygons in the front, or polygons that are far away could appear on top of polygons that are close up. Needless to say, this would lead to a confusing 3D experience. We get to ordering visible polygons in later chapters, but first let's talk about hidden surface-removal algorithms. This idea is to not draw polygons or parts of polygons that are either behind other polygons or otherwise aren't seen by the camera. The first hidden surface-removal technique you'll use is called back-face removal, sometimes called back-face culling. Screenshot shows the basic idea of back-face removal: Draw only polygons that are facing the camera.
Removing back faces is a great trick and, on average, reduces by half the number of polygons that need to be drawn. Also, back-face removal draws convex polyhedrons perfectly with no extra effort. A convex polyhedron is a polyhedron, or 3D polygonal solid, with no inward bulges. Back-face removal isn't a perfect solution for drawing all polygons, however. For convex polyhedrons or for several solid objects, you need another algorithm, such as z-buffering, which we get into in , "3D Objects." To determine whether a polygon is a back face, let's first introduce the concept of a polygon normal. A polygon normal is the vector that is perpendicular, or orthogonal, to the polygon. Luckily, the normal also points in the direction the polygon is facing. You can tell whether the polygon is facing the camera if the normal is less than 90° from the direction to the camera, as shown in Screenshot.
Now you just need to calculate two things: the polygon normal and the angle between two vectors. Let's start with the angle between two vectors.
The Dot Product
To calculate the angle between two vectors, you can take advantage of the law of cosines, as shown in Screenshot.
To make the law of cosines work with vectors, instead of the lengths a, b, and c, we'll use the vectors U, V, and (U-V). Thus, the law of cosines equation becomes this:
|U-V|2 = |U|2+|V|2-2|U||V|cos q
In this case, the exact angle isn't important. You need to know only whether the angle is less than 90°. If the angle is less than 90° (or "acute"), then the cosine of the angle will be greater than 0. In other words, cos q > 0. Likewise, 2|U||V| cos q > 0. Let's solve the law of cosines with this in mind.
2|U||V| cos q = |U|2 + |V|2 - |U-V|2 = |U|2+|V|2-(Ux-Vx)2-( Uy-Vy)2-(Uz-Vz)2 = |U|2+|V|2-Ux2-Vx2-Uy2-Vy2-Uz2-Vz2 + 2UxVx + 2UyVy + 2UzVz = 2UxVx + 2UyVy + 2UzVz |U||V| cos q = UxVx + UyVy + UzVz
That certainly simplified a lot, didn't it? Just three multiplications and two additions are all it takes to determine whether an angle between two vectors is acute. It turns out (surprise, surprise) that this isn't the first time this has been done before. This equation is called the dot product and is one of the basics of vector math. It's often denoted as a dot, as in this example:
U•V = UxVx + UyVy + UzVz = |U||V| cos q
Therefore, with the dot product, you can easily tell whether the angle between two vectors is acute, obtuse, or a right angle:
If (U•V<0), then (q>90°) If (U•V=0), then (q=90°) If (U•V>0), then (q<90°)
You'll use the dot product a lot in 3D graphics, so add a getDotProduct() method to the Vector3D class to calculate the dot product between two vectors:
/**
Returns the dot product of this vector and the specified
vector.
*/
public float getDotProduct(Vector3D v) {
return x*v.x + y*v.y + z*v.z;
}
Looking back at the big picture of back-face removal, you can now tell whether the angle between a polygon normal and the vector to the camera is acute. Next, you need to find the polygon normal.
The Cross Product
Using the dot product, you can tell whether two vectors are orthogonal, or at right angles to each other, if their dot product is 0. This helps you find the normal of a polygon. Okay, so now you want to find the normal of a specific polygon. Take any two vectors in this polygon (we'll call them U and V). The dot product between these vectors and the polygon's normal, N, will be 0:
U•N = 0 V•N = 0
Therefore:
UxNx + UyNy + UzNz = 0 VxNx + VyNy + VzNz = 0
This system of equations has infinite solutions, but one solution can be found by using determinants (determinants are one of those things you'll find in a linear algebra textbook):
Nx = UyVz - UzVy Ny = UzVx - UxVz Nz = UxVy - UyVx
That's it-you now have the normal. This solution is called the cross product and is donated by a cross:
UxV = (UyVz - UzVy, UzVx - UxVz, UxVy - UyVx)
Just as with the dot product, you'll use the cross product often, so add a cross product to the Vector3D class:
/**
Sets this vector to the cross product of the two
specified vectors. Either of the specified vectors can
be this vector.
*/
public void setToCrossProduct(Vector3D u, Vector3D v) {
// assign to local vars first in case u or v is 'this'
float x = u.y * v.z - u.z * v.y;
float y = u.z * v.x - u.x * v.z;
float z = u.x * v.y - u.y * v.x;
this.x = x;
this.y = y;
this.z = z;
}
There's one catch, and maybe you thought of it. The normal is just a vector orthogonal to the polygon. How can you tell which way the normal is pointing? It could be pointing in the direction the polygon is facing, or it could be pointing in the opposite direction because both vectors are orthogonal to the polygon. And which side of the polygon is the "front" and which is the "back," anyway? The answer is: It all depends on how the vertices in the polygon are defined. In the right-handed coordinate system, the front of the polygon is the side where the vertices of the polygon appear in counterclockwise order, as in Screenshot. If you looked at that polygon on the other side, the vertices would be in clockwise order.
So, be sure to define your polygons so that viewing them from the front makes the vertices appear in counterclockwise order. Next, add some methods to the Polygon3D class to calculate the normal. The normal will be a member variable, so it doesn't have to be recalculated every time. Because each vertex in the polygon is a point, you use the vectors temp1 and temp2 to calculate two vectors in the polygon.
/**
Calculates the unit-vector normal of this polygon.
This method uses the first, second, and third vertices
to calculate the normal, so if these vertices are
collinear, this method will not work.
Use setNormal() to explicitly set the normal.
This method uses static objects in the Polygon3D class
for calculations, so this method is not thread-safe across
all instances of Polygon3D.
*/
public Vector3D calcNormal() {
if (normal == null) {
normal = new Vector3D();
}
temp1.setTo(v[2]);
temp1.subtract(v[1]);
temp2.setTo(v[0]);
temp2.subtract(v[1]);
normal.setToCrossProduct(temp1, temp2);
normal.normalize();
return normal;
}
/**
Gets the normal of this polygon. Use calcNormal() if
any vertices have changed.
*/
public Vector3D getNormal() {
return normal;
}
/**
Sets the normal of this polygon.
*/
public void setNormal(Vector3D n) {
if (normal == null) {
normal = new Vector3D(n);
}
else {
normal.setTo(n);
}
}
The calcNormal() method uses the first, second, and third vertices of the polygon to determine the normal. Of course, this won't work if these three vertices all fall on the same line (that is, if they are collinear). In the next chapter, we talk about bounding rectangles of polygons; you can use a bounding rectangle's normal in cases like this. Finally, you can determine whether a polygon is facing the camera. Add another method to Polygon3D, called isFacing(), which checks whether the polygon is facing a specific point:
/**
Tests if this polygon is facing the specified location.
This method uses static objects in the Polygon3D class
for calculations, so this method is not thread-safe across
all instances of Polygon3D.
*/
public boolean isFacing(Vector3D u) {
temp1.setTo(u);
temp1.subtract(v[0]);
return (normal.getDotProduct(temp1) >= 0);
}
calcNormal() and isFacing() use temporary static Vector3D objects, which pretty much makes Polygon3D not thread-safe. That's okay in this situation because you're calling these methods only in the main thread in the game.
More About the Dot and Cross Products
For reference, here are a few properties of the dot product and the cross product. You'll use a few of these in the next chapter. Here, A, B, and C are vectors and s is a real number. Dot product:
A•B = B•A (sA)•B = s(A•B) A•B+A•C = A•(B+C)
Cross product:
AxB = -BxA Ax(B+C) = AxB+AxC
Scalar triple product:
(AxB)•C = (CxA)•B = (BxC)•A
Vector triple product:
Ax(BxC) = B(A•C)-C(A•B)