Last three topics - Will be on Final Exam

CSU540 Computer Graphics - Fall 2005 - Prof. Futrelle

Updated 5 December 2005

Version with Phong shading, posted Sat Dec 3 20:30h EST 2005

Version with BSP tree, posted Sat Dec 3 21:55h EST 2005

Version with antialising, posted Sun Dec 4 16:35h EST 2005

Addtional material on BSP trees posted Mon Dec 5 05:15h EST 2005

As I said in class, we will go over three simple topics (or at least, simple versions of them). They are

Each of these is treated in turn below.

Phong vertex-based shading for highlights

As the book explains in Sec. 9.2 (through 9.2.2), there are two approaches to Phong shading, both dealing with highlights related to the relation of the eyepoint direction e and the reflected ray direction r.

The basic Phong term that is added to the diffuse and ambient terms of pg. 193, is the one in eq. 9.5: c = cl (er)p, where I've omitted the max function, which is not critical to understanding the basic idea. The equation can also be viewed as stating that the Phong contribution to the illumination is proportional to (cosφ)p, where φ is the angle between the eye direction and the reflected ray.

The first technique, which is the simplest Phong shading, interpolates the illumination across each triangle, just as Gouraud shading does, but it takes into account the (partial) specular behavior of the surface. This technique can be described as follows:

The second technique, Phong normal interpolation, described in Sec. 9.2.2, first interpolates the normals across the triangles, and then computes the illumination for each interpolated normal. In detail:

What you'll need to be able to do for Phong shading on the Final

BSP trees (binary space partitioning trees)

Here's the cool BSP applet site that's important for your Final Exam:

The BSP tree is an important strategy in real-time graphics, because it involves one up-front computation for (unchanging) scene elements which can then be rapidly rendered from any viewpoint. The essence of the technique depends on using the painter's algorithm (Fig. 8.1), which consists of painting items farthest from the viewpoint first, then closer ones, with the closer ones possibly occluding the ones rendered earlier in the sequence. This automatically eliminates hidden surfaces. The scene is divided by planes. A tree is built. When a ray from the viewpoint strikes the plane at the root of the tree, it strikes it from one side or another. Items on the farther side are rendered first. While working on that half of the tree, each node is again examined, and whichever children of that node that are on the farther side are also rendered first, and so forth. The cool applet site I discovered shows this clearly, after some study.

The question you'll be asked on the Final about BSP trees will depend entirely on your already having experimented with the applet so you have a good understanding of the relation between the positions of planes in space, the corresponding tree structure, and what it implies for rendering order. Also, some objects may be bisected, even more than once by another plane, creating additional partial planes and corresponding nodes. Here are some of the types of experiments you can do with the applet to help your understanding, always starting with the simplest possible experiments.

It's important to realize that in the simple demo as in our textbook that planes are being placed with respect to other planes. So the objects themselves are used as the partitioning surfaces. In some treatments of BSP trees, the planes and objects are quite distinct; not in our case.

Walking the tree: This be seen in the example figure below, where the tree walk is explained in addition. The traversal algorithm is presented in pseudocode on page 180 of the text. But in the figure below, the strategy becomes clear. The recursive traversal algorithm, in its simplest possible form is the following:

draw(tree, eyepoint){
  If tree empty: return;
  Choose the appropriate subtree and draw(subtree, eyepoint);
  Draw the root triangle;
  Choose the otherSubtree and draw(otherSubtree, eyepoint);

The example screenshot and its intuitive trace/explanation

  • First, note carefully how the tree is constructed. The first plane drawn is 0. The next is 1, drawn on the backside of 0, as related to 0's normal, so it is in a right subtree. Note that in the subtree under 1, node 5 is on 1's backside, so it is in the right subtree of 1. 6 is on the frontside of 1, the side that 1's normal projects to, so it is placed in 1's left subtree.
  • Exactly the same rules apply to the left subtree of 0, the subtree on 0's frontside. Once node 2 is created, 3 is in its right subtree, because it is on 2's backside, just as 5 is on the backside of 1. Node 4 is on the frontside of 2 so it forms the left subtree of 2.
  • Now for the traversal of the tree. The eyepoint is on the positive side of the root node 0, so we examine the subtree that is further away, the tree on 0's backside, the tree with 1, 5, and 6. These will be the ones drawn first. We draw the tree rooted at 1. Since the eyepoint is on the backside of 1, we follow the tree away from the eyepoint, the tree on the 1's frontside, which is 6. Since 6 has no subtrees, we return and draw 6. When we return to node 1, we know that the remaining subtree is closer to the eyepoint, so we draw node 1 and traverse subtree 5.
  • We then return to node 0 and draw that, since its left tree contains objects closer to the eyepoint. We then examine the 2 subtree. 2 faces the eyepoint, so we pursue the tree on the opposite face which is 3. After drawing that, 2 is drawn and the other subtree, 4, is entered and 4 is drawn.
  • Collecting all drawing operations above together, we see that the sequence of drawing is 6, 1, 5, 0, 3, 2, and 4, as it must be to render the scene correctly.
  • NB: If you open the image on the left in a separate window, you'll see it in more detail..


Two simple screenshots that show how the position with respect to the frontside and backside of a surface determine which subtree an object will be placed in.

The key to understanding the placement of objects in the tree is to pay attention to the orientation of the partitioning surfaces. In the example above, the initial plane, 0, is drawn with its positive normal to the left. Then plane 1 is positioned on the positive side of 0 so it is placed in the left, positive, subtree of 0. In the above example, plane 0 is oriented to the right. When plane 1 is drawn in the same location as before it is now on the backside of 0, so it is in the right subtree. Plane 2, on the positive or frontside of 0, is in the left, positive subtree of 0.


In each case, the viewpoint (not shown) was placed at the lower left corner, oriented up and to the right. This accounts for the pink circles in the trees, corresponding to the viewpoint. In either case, when viewing is done, the key to tree traversal is to see which side of each subtree root node the vector from the viewpoint/eyepoint strikes the plane corresponding to that node. Once that's determined, the subtree farthest from the viewpoint is drawn first.

What you'll need to be able to do for BSP trees on the Final


Antialiasing is the simplest of the three topics. You'll need to know the basics of oversampling and also "jittering". The simple basics are covered in your textbook in Sec. 3.7. Jittering, usually called stratified sampling, is covered in Sec. 10.11.1. Both sections are short. What's not shown clearly is what I've illustrated in the figure below.

In the figure, the value in a single pixel can be estimated by rendering an area in a high-resolution array and then downsampling by averaging values. The figure below shows the computations done to render four pixels. Each pixel is represented by a 4x4 portion of a large array. The red region is rendered in the large array with its "pixels" marked as red or background (white in this case). By counting the small pixels, an estimate can be made about the proportion of red that should be rendered in each of the four actual pixels that will appear in the final image. For example, the lower left pixel is 5/16 red and 11/16 background. Since red can be represented as 255,0,0, and white as 255,255,255, this would yield a light red color of 255,175,175 (because 11/16 of 255 is about 175). Another way to think of this light red color is to realize that it is composed of 175,175,175 (a light, colorless gray) plus 80,0,0, a modest but pure red component.

What you'll need to be able to do for antialiasing on the Final

You'll need to be able to do two things: (1) Create a sketch such as in the figure above and compute (estimate) RGB values for it. (2) Draw diagrams such as in Figs. 10.27, 10.28, and 10.29 and explain why they illustrate different strategies for sampling. In the 4x4 strategy in the figure above, you should imagine that the sampling was done by regular or jittered samples. If it had been done by random samples, some of the pixels might have been missed entirely and some weighted more than once.

Go to CSU540 home page. or RPF's Teaching Gateway or homepage