Chapter 7 – Issues in Rendering Graphic Images

 

In this section of the notes, we discuss a number of issues from Chapter 7 in the second edition of the textbook or chapter 8 in the third edition.

 

Line Clipping

This discussion is based on Section 7.3 of the second edition or Section 8.4 of the third.  The problem addressed by line clipping is that a graphic view typically displays only part of a scene.  We must decide what part of the scene will be visible in the graphic window and what part of the scene will not be visible and thus should not be computed.

 

The basis of clipping is the fact that most images to be displayed comprise a number of polygons, each of which comprise at least three lines.  Line clipping is the process of computing what part, if any, of a line segment specified by its end points, will appear in the display window.  Although the term “window” may have a precise meaning in the world of graphic displays, we use it here with its intuitive meaning and find that sufficient.

 

Consider a triangle that is too large to be displayed in a graphic window.  In our example below, each of the three lines forming the triangle must be clipped for the display.

 

 

For each line to be displayed, there are a number of possibilities.

      1.   Both end-points are inside the clipping region

      2.   One end-point is inside the clipping region and one is not.
      3.   Neither end-point is inside the clipping region.

 

One of the basic requirements for simple line clipping is that the clipping region be a convex polygon.  The reason for that requirement is the handling of lines for which both end points are within the clipping region.  We would like to say that in this case the entire line will be within the clipping region and will be visible in the viewing window.  But any polygon satisfying this requirement is convex, by definition.  There are more complex algorithms that will clip against non-convex polygons, but we will not discuss them.

 

If a line is not entirely contained within a convex clipping region, it must intersect the boundary of the region in at least one point.  There are a number of unusual situations, such as the line actually forming a boundary (in which case it intersects in an infinite number of points), but we focus on the case of one intersection or two intersections.  All clipping algorithms depend on computing the point of intersection of the line with the boundary.  For the situations of interest to us, we count the number of intersections as follows.

 

      1.   Both end-points are inside the clipping region                0 intersections

      2.   One end-point inside and one outside                                        1 intersection
      3.   Neither end-point is inside the clipping region.               0 or 2 intersections.

 

As an aside, it is possible to demonstrate situations in which a line with neither point inside the clipping region intersects the boundary of the clipping region at exactly one point.  One example of such a case would be a line tangent to a circle, where the circle defines the convex clipping region.  In such a case, no part of the line is within the clipping region, so no part of the line is displayed.  We treat this case as the line having no intersection.

 

One of the convex figures most commonly used for line clipping is the rectangle.  There are two reasons for this choice.  Consider a rectangle defined by

                                                      Xmin £ X £ Xmax, and
                                                      Ymin £ Y £ Ymax.

 

      1.   Determining whether or not a point is within the region is simply the process
            of checking its coordinates against the boundaries of the region.
      2.   Computing the point of intersection of the line and the boundary is extremely simple.

            Consider a line given by the equation Y = M·X + B.

                        If it intersects the line X = X0, it intersects at Y0 = M·X0 + B

                        If it intersects the line Y = Y0, it intersects at X0 = (Y0 – B) / M.

 

We need to be a bit more specific here to differentiate between intersecting the boundary of the rectangle from intersecting a line with the proper coordinates.  Suppose a line given by
Y = M·X + B intersecting the line X = X0, where X0 is either Xmin or Xmax.  We compute the value Y0 = M·X0 + B.  If Ymin £ Y0 £ Ymax, then the line Y = M·X + B intersects the boundary of the rectangle.  If either Y0 > Ymax or Y0 < Ymin, then the line Y = M·X + B intersects the line X = X0, but not the boundary of the rectangle defined by the line  X = X0.  A similar statement applies to the line Y = M·X + B intersecting the line Y = Y0, where Y0 is either Ymin or Ymax.

 

Given the difficulty of forming a precise formulation of the above statement, it would be wise to present an example.

 

Example:  Consider a line with end-points (2, 3) and (8, 6) being clipped by the rectangle defined by the inequalities

                                                      3 £ X £ 7, and
                                                      2 £ Y £ 4.

 

The slope of the line from (2, 3) to (8, 6) is easily seen to be  = 0.5.  Consider the point (2, 3).  If it is on the line, then 3 = ·2 + B, so B = 2, and Y = ·X + 2.
We now consider the points of intersection of this line with the lines X = 3 and X = 7.

 

For X = 3, Y = Y = ·3 + 2 = 1.5 + 2.0 = 3.5.  We note that Ymin £ 3.5 £ Ymax and conclude that the line from (2, 3) to (8, 6) intersects the clipping region at (3, 3.5).

 

For X = 7, Y = Y = ·7 + 2 =  > Ymax, so the line does not intersect the clipping region at its boundary defined by Xmax = 7.

 

For computing the X-values for given Y, we represent the line as X = (Y – B) / M, in our case this is X = 2·(Y – 2).  For Y = 2, X = 2·0 = 0 < Xmin, so the line does not intersect the clipping region at the boundary defined by Ymin = 2.

 

For Y = 4, X = 2·(4 – 2) = 2·2 = 4.  We note that Xmin £ 4 £ Xmax and conclude that the line from (2, 3) to (8, 6) intersects the clipping region at (4.0, 4.0).

 

The part of the line segment displayed in the clipping region is the ling segment defined by the end points (3.0, 3.5) to (4.0, 4.0).

 

The Cohen-Sutherland clipping model is one of the more commonly used algorithms for line clipping.  One of the reasons for its popularity is its use of Boolean operations to replace some of the more time-costly floating point operations.

 

The Cohen-Sutherland algorithm processes a line segment for clipping by comparing the
(X,Y)-coordinates of each of the end points to the values specifying the boundaries of the clipping rectangle.  Each of the two endpoints is characterized by a four-bit code called the outcode.  The textbook uses the notation b0b1b2b3 for the outcode.  The notation Y0Y1X0X1 seems to be a bit more descriptive of the structure of the outcode.  The outcode for a point has a two-bit value describing its X-coordinate and a two-bit value describing the Y.

 

We examine the method for computing the X-outcodes; the method for the Y-outcodes is similar.  For each outcode group, we compare the coordinate to the bounds of the rectangle.

For the X coordinate of the point, there are three possible comparisons to the values Xmin and Xmax used to specify the boundaries of the clipping rectangle.

 

            X < Xmin                      Outcode = 01
            Xmin £ X £ Xmax           Outcode = 00
            X > Xmax                      Outcode = 10

 

There is no 11 outcode assigned.  The structure of the outcode has been selected under two constraints.  For the full four-bit outcode.

      1.   If the outcode of a point is zero, then it is inside the clipping rectangle.

      2.   If the bit-wise AND of the outcodes of two points is not zero, then both
            points are outside the clipping rectangle and on the same side.

 

Before moving to a general description of the outcode, let’s consider a special case – a line with endpoints (XA, YA) and (XB, YB) being clipped against a rectangle characterized by points (Xmin, Ymin) and (Xmax, Ymax) under the two constraints

            XA < XB, and

            Ymin £ YA £ YB £ Ymax.

 

There are a number of situations possible, even under these constraints.

 

In this option, we have XA < XB £ Xmin
No part of the line is within the clipping rectangle and the line is not to be displayed.

 

 

 

In this option, we have XA < Xmin < XB.

Here part of the line lies within the viewing rectangle

and thus only part is displayed.  The line is clipped at

the border of the viewing rectangle.

 

Here we have Xmin £ XA < XB £ Xmax.

The entire line is displayed within the clipping

rectangle.

 

 

Here we have XA < Xmin < Xmax < XB.

Both ends of the line are outside the viewing rectangle, but the line intersects the clipping region.  The line is clipped at both ends and only the segment of the line within the clipping region is displayed.

 

Here we have XA < Xmax < XB.

In this case, the line is again clipped at the boundary of the clipping region and only the part inside is displayed.

 

In this last option, we have Xmax £ XA < XB.

No part of the line is within the clipping rectangle and thus no part of the line is displayed.

 

We now focus on the complete four-bit outcode for a point.  As indicated above, it is formed from two fields, each relating a coordinate to the corresponding bounds of the rectangle.  We represent the code by Y0Y1X0X1 where

      X0X1= 01 if X < Xmin                                 Y0Y1= 01 if Y < Ymin

      X0X1= 00 if Xmin £ X £ Xmax                      Y0Y1= 00 if Ymin £ Y £ Ymax

      X0X1= 10 if X > Xmax                                 Y0Y1= 10 if Y > Ymax

 

The structure of the four-bit outcodes is shown in the figures at left.  This breaks the plane into nine regions based on the relationship of the point to the boundaries of the rectangle.

 

Note that all outcodes to the left of the rectangle have outcodes of the form xx01, all to the right have outcodes of the form xx10 and those in the center have outcodes of the form xx00.

 

 

Now that we have the outcodes of the endpoints of the line calculated, we characterize them in order to use them in the line clipping.

 

Let points A, with coordinates (XA, YA), and B, with coordinates (XB, YB), be the endpoints of a line segment that is to be clipped.  Suppose that we have computed the outcodes of points A and B, called OA and OB respectively, by comparison with the boundaries of the clipping rectangle.  Depending on the values of OA and OB, there are a number of cases.

 

OA = 0 and OB = 0                                     The line is entirely contained in the clipping
                                                                  region.  Display the entire line.

 

OA ¹ 0 and OB = 0, or                               One endpoint of the line is inside the clipping

OA = 0 and OB ¹ 0                                     region and one endpoint is outside the region.

                                                                  Compute (XC, YC), the point at which the line

                                                                  intersects the boundary of the region, and draw

                                                                  the line from the interior point to (XC, YC).

 

OA ¹ 0 and OB ¹ 0, and                             Both endpoints are outside the clipping region

OA & OB ¹ 0                                             and on the same side of one of the boundaries

                                                                  of the clipping region.  Discard the line.

 

OA ¹ 0 and OB ¹ 0, and                             Both endpoints are outside the clipping region,

OA & OB = 0                                             but on different sides of two of the boundaries.

                                                                  The line may or may not intersect the clipping
                                                                  rectangle, so further analysis is needed to

                                                                  determine whether to clip the line or discard it.

 

 

Our first example of clipping was of this last case.  As we saw in that example, it is necessary to examine all four possible points of intersection of the line with the boundary of the clipping region in order to see if the line crosses the boundary in two points and thus should b clipped and partially drawn.

 

 

Hidden Surface Removal

The next topic for discussion is hidden surface removal.  Our goal here is to determine what parts of the graphic scene need not be rendered because they will be invisible.  In the interest of efficiency, we want to do this with as few computational resources as possible.  There are two topics that we shall discuss:

      1)   Back Face Removal
      2)   The Z-Buffer Algorithm.

 

Back Face Removal

Imagine viewing a cube, which is a solid figure with six faces.  Some of us might think of looking at a child’s block with letters on it; some others might think of a die in a game of chance.  Of the six faces of the cube, a maximum of three are visible at any given time.

Were we to compute a graphic representation of the cube, we would not want to waste computational resources on the faces that would be invisible.  These are called the back faces of the object.

 

Suppose a face of a solid with an outward facing normal vector N at a point P on the surface.  We consider also the vector V – the vector in the direction of the viewer, as used in the reflection model.  Let q be the angle between the two vectors.  It should be obvious that the surface is visible to the viewer if and only if
 – 90° < q < 90°.  This is equivalent to cos(q) > 0.

 

Consider the dot product N·V = |N|·|V|·cos(q), where |N| > 0 and |V| > 0 as each of the vectors has a direction.  From this observation, we see that N·V > 0 if and only if cos(q) > 0, and the surface is visible only if N·V > 0.  Hence we have the back face removal rule:

 

Remove the surface as hidden if N·V £ 0.

 

The situation becomes simpler if we recall that much of the visualization is done along the
Z-axis, so that V =  in homogeneous coordinates.  Recalling that N =  was shown to be the normal vector for a surface described by the equation a·x + b·y + c·z + d = 0, and noting that, in this case, N·V = c, we have the very simple rule:

 

Remove the surface described by a·x + b·y + c·z + d = 0 if c £ 0.

 

The Z-Buffer Algorithm

Suppose that we are creating a graphic display of a set of objects at differing distances from the camera.  We realize that objects closer to the camera may obscure objects that are farther away.  We want to compute the scene without devoting resources to objects that will not be visible.  There are a number of algorithms for this, we consider the Z-buffer algorithm as it is the most common and, given the right hardware, fairly easy to implement.

 

The Z-buffer algorithm depends on the fact that any computer display can be viewed as an array of pixels.  For example, a high resolution display with 32-bit color can be modeled as an array [1024][1280] of long integer.  Under the constraint of the screen resolution, a point will be visible in the display only if the ray from the point to the COP (center of projection) intersects the image plane on one the large, but finite, number of pixels.

 

The Z-buffer for a display is an array of depth information (single precision floating point numbers) sized identically to the display.  For the display mentioned above, the size of the
Z-buffer would be 1024 · 1280 · 4 bytes = 210 · 5·28 · 22 = 5·220 bytes = 5 megabytes.  Current top-of-the-line graphics cards contain 128 MB of memory, so allocating 5 MB of memory to the Z-buffer is quite reasonable.  It should be obvious that this algorithm would not have been feasible in the days when memory was more expensive and graphics cards rarely had more than 1 MB of memory.

 

In implementing the algorithm, we consider the objects to be displayed as being in front of a background of uniform color set at a distance from the camera greater than any of the objects to be displayed.  The algorithm begins by setting each pixel in the display buffer to the color of this background and setting each real number in the Z-buffer to the distance of this background.  Note that we do not need a real distance, just any number larger than the distance to the most remote object that is to be in the graphics scene.

 

As we render each object in the graphics scene, we are setting the color of the pixel in the display to correspond to that on the corresponding point on the object.  We compute the distance of each point on the object and compare it to the distance stored in the Z-buffer for that ray from the COP through the pixel.  The rules are simple.

 

      If the distance is greater than that stored in the Z-buffer, there is an point on another
            object that is obscuring the point on this object, so it is not visible.  Do nothing.

 

      If the distance is less than that stored in the Z-buffer, the point on this object might
            be visible in the display.  Update the display buffer and the Z-buffer to the color
            of the point and the distance to this point.

 

Given this algorithm, it would appear more efficient to sort the objects by distance from the COP (camera) and render them by non-decreasing order of distance.