!!html_class cgfs !!html_title Hidden Surface Removal - Computer Graphics from Scratch
Hidden Surface Removal {#ch:hidden_surface_removal}
We can now render any scene from any point of view, but the resulting image is visually simple: we're rendering objects in wireframe, giving the impression that we're looking at the blueprint of a set of objects, not at the objects themselves.
The remaining chapters of this book focus on improving the visual quality of the rendered scene. By the end of this chapter, we'll be able to render objects that look solid (as opposed to wireframe). We already developed an algorithm to draw filled triangles, but as we will see, using that algorithm correctly in a 3D scene is not as simple as it might seem!
The first idea that comes to mind when we want to make solid objects look solid is to use the function DrawFilledTriangle
that we developed in Chapter 7 (Filled Triangles) to draw each triangle of the objects using a random color (Figure 12-1).
The shapes in Figure 12-1 don't quite look like cubes, do they? If you look closely, you'll see what the problem is: parts of the back faces of the cube are drawn on top of the front faces! This is because we're blindly drawing 2D triangles on the canvas in a "random order" or, more precisely, in the order they happen to be defined in the Triangles
list of the model, without taking into account the spatial relationships between them.
You might be tempted to go back to the model definition and change the order of the triangles to fix this problem. However, if our scene includes another instance of the cube that is rotated
A first solution to this problem is known as the painter's algorithm. Real-life painters draw backgrounds first, and then cover parts of them with foreground objects. We could achieve the same effect by drawing all the triangles in the scene back to front. To do so, we'd apply the model and camera transforms and sort the triangles according to their distance to the camera.
This works around the "no single correct order" problem explained above, because now we're looking for a correct ordering for a specific relative position of the objects and the camera.
Although this would indeed draw the triangles in the correct order, it has some drawbacks that make it impractical.
First, it doesn't scale well. The most efficient sorting algorithm known to humans is
Second, it requires us to know the whole list of triangles at once. This requires a lot of memory and stops us from using a stream-like approach to rendering. We want our renderer to be like a pipeline, where model triangles enter on one end and pixels come out the other end, but this algorithm doesn't start drawing pixels until every triangle has been transformed and sorted.
Third, even if we'd be willing to live with these limitations, there are cases where a correct ordering of triangles just doesn't exist at all. Consider the case in Figure 12-2. We will never be able to sort these triangles in a way that produces the correct results.
We can't solve the ordering problem at the triangle level, so let's try to solve it at the pixel level.
For each pixel on the canvas, we want to paint it with the "correct" color, where the "correct" color is the color of the object that is closest to the camera. In Figure 12-3, that's
At any time during rendering, each pixel on the canvas represents one point in the scene (before we draw anything, it represents a point infinitely far away). Suppose that for each pixel on the canvas, we kept the
Let's go back to Figure 12-3. Suppose that because of the order of the triangles in a model, we want to paint
In this particular case, we'd have gotten the correct result regardless of the values of
In terms of implementation, we need a buffer to store the
But where do the
Here is yet another application of the attribute-mapping algorithm we developed in Chapter 8 (Shaded Triangles). Why not use z0
, z1
, and z2
; compute z01
, z02
, and z012
; combine them to get z_left
and z_right
; then, for each horizontal segment, compute z_segment
. Finally, instead of blindly calling PutPixel(x, y, color)
, we do this:
z = z_segment[x - xl]
if (z < depth_buffer[x][y]) {
canvas.PutPixel(x, y, color)
depth_buffer[x][y] = z
}
For this to work correctly, every entry in depth_buffer
should be initialized to
The results we get now are much better---check out Figure 12-4.
The results look much better, but what we're doing is subtly wrong. The values of
To see how the values are wrong, consider the simple case of a line segment from
Let's compute the projection of these points with
The slope of the function is constant, so we can write
We can manipulate that expression to solve for
If we plug in the values we know and do some arithmetic, we get
This says that the value of
Where did we go wrong? We're using linear interpolation, which we know works well, and we're feeding it the correct values, which come from data, so why is the result wrong?
Our mistake is hidden in the implicit assumption we make when we use linear interpolation: that the function we are interpolating is linear to begin with! In this case, it turns out it isn't.
If
That is, for a given difference in screen coordinates, the difference in
More formally, the equation of the plane that contains the line segment we're studying is
On the other hand we have the perspective projection equations:
We can get
If we replace
Multiplying by
This is clearly not a linear function of
However, if we compute
This clearly is a linear function of
In order to verify that this works, let's calculate the interpolated value for
$${ M_{1 \over z} - A_{1 \over z} \over M'x - A'x } = { B{1 \over z} - A{1 \over z} \over B'_x - A'_x }$$
$$M_{1 \over z} = A_{1 \over z} + (M'x - A'x) ({B{1 \over z} - A{1 \over z} \over B'_x - A'_x})$$
And therefore
This value is correct, in the sense that it matches our original calculation of
All of this means we need to use values of
Depth buffering produces the desired results. But can we make things even faster?
Going back to the cube, even if each pixel ends up having the right color, many of them are painted over several times. For example, if a back face of the cube is rendered before a front face, many pixels will be painted twice. This can be costly. So far we've been computing
Can we discard pixels earlier, before we go into all of this computation? It turns out we can discard entire triangles before we even start rendering!
So far we've been talking informally about front faces and back faces. Imagine every triangle has two distinct sides; it's impossible to see both sides of a triangle at the same time. In order to distinguish between the two sides, we'll stick an imaginary arrow on each triangle, perpendicular to its surface. Then we'll take the cube and make sure every arrow is pointing out. Figure 12-8 shows this idea.
These arrows let us classify each triangle as "front" or "back," depending on whether they point toward the camera or away from the camera. More formally, if the view vector and this arrow (which is actually a normal vector of the triangle) form an angle of less than
At this point, we need to impose a restriction on our 3D models: that they are closed. The exact definition of closed is pretty involved, but fortunately an intuitive understanding is enough. The cube we've been working with is closed; we can only see its exterior. If we removed one of its faces, it wouldn't be closed because we could see inside it. This doesn't mean we can't have objects with holes or concavities; we would just model these with thin "walls." See Figure 12-10 for some examples.
Why impose this restriction? Closed objects have the interesting property that the set of front faces completely covers the set of back faces, no matter the orientation of the model or the camera. This means we don't need to draw the back faces at all, saving valuable computation time.
Since we can discard (cull) all the back faces, this algorithm is called back face culling. Its pseudocode is remarkably simple for an algorithm that can cut our rendering time by half!
CullBackFaces(object, camera) {
for T in object.triangles {
if T is back-facing {
remove T from object.triangles
}
}
}
Let's take a more detailed look at how to determine whether a triangle is front-facing or back-facing.
Suppose we have the normal vector
We can again use the properties of the dot product to make this simpler. Remember that if
Because
The classification criterion is simply this:
::: center
:::
The edge case
Where do we get the normal vector from? It turns out there's a vector operation, the cross product
Note that "the direction of the normal vector" is not the same as "the normal vector." There are two reasons for this. The first one is that
The second reason is that if
Moreover, the cross product of two vectors is not commutative: $\vec{V_1}\times\vec{V_2} = -({\vec{V_2} \times \vec{V_1}}$). In other words, the order of the vectors in this operation matters. And since we defined
Fortunately, none of this is random. Given the definition of the cross product operation, the way we defined
We just need to keep this rule in mind when designing 3D models manually and list the vertices of each triangle in clockwise order when looking at its front face, so that their normals point "out" when we compute them this way. Of course, the example cube model we've been using so far follows this rule.
In this chapter, we made our renderer, which could previously only render wireframe objects, capable of rendering solid-looking objects. This is more involved than just using DrawFilledTriangle
instead of DrawWireframeTriangle
, because we need triangles close to the camera to obscure triangles further away from the camera.
The first idea we explored was to draw the triangles from back to front, but this had a few drawbacks that we discussed. A better idea is to work at the pixel level; this idea led us to a technique called depth buffering, which produces correct results regardless of the order in which we draw the triangles.
We finally explored an optional but valuable technique that doesn't change the correctness of the results, but can save us from rendering approximately half of the triangles of the scene: back face culling. Since all the back-facing triangles of a closed object are covered by all its front-facing triangles, there's no need to draw the back-facing triangles at all. We presented a simple algebraic way to determine whether a triangle is front- or back-facing.
Now that we can render solid-looking objects, we'll devote the rest of this book to making these objects look more realistic.