Skip to content
Textbook Guides

Solution Manual for Interactive Computer Graphics, 8th Edition

Need help with textbook exercises? Solution Manual for Interactive Computer Graphics, 8th Edition offers comprehensive solutions that make studying easier.

Preview 13 of 41 pages

See the first 13 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    Angel and Shreiner: Interactive Computer Graphics, Eighth Edition Chapter 1 Solutions 1.1 The main advantage of the pipeline is that each primitive can be processed independently. Not only does this architecture lead to fast performance, it reduces memory requirements because we need not keep all objects available. The main disadvantage is that we cannot handle most global effects such as shadows, reflections, and blending in a physically correct manner. 1.2 If we use lines of constant longitude and lines of constant latitude, their intersections define a set of quadrilaterals. If we draw diagonals for each quadrilateral, we get a set of triangles. However, at the poles all the curves of constant longitude meet and we get triangles rather than quadrilaterals. 1.3 We derive this algorithm later in Chapter 6. First, we can form the tetrahedron by finding four equally spaced points on a unit sphere centered at the origin. One approach is to start with one point on the z axis (0 , 0 , 1). We then can place the other three points in a plane of constant z . One of these three points can be placed on the y axis. To satisfy the requirement that the points be equidistant, the point must be at (0 , 2 √ 2 / 3 , − 1 / 3). The other two can be found by symmetry to be at ( − √ 6 / 3 , − √ 2 / 3 , − 1 / 3) and ( √ 6 / 3 , − √ 2 / 3 , − 1 / 3). We can subdivide each face of the tetrahedron into four equilateral triangles by bisecting the sides and connecting the bisectors. However, the bisectors of the sides are not on the unit circle so we must push these points out to the unit circle by scaling the values. We can continue this process recursively on each of the triangles created by the bisection process. 1.4 Suppose that the line segment is between the points ( x 1 , y 1 ) and ( x 2 , y 2 ) We can use the endpoints of the line segment to determine the slope and y intercept of a line of which the segment is part, i.e. y = mx + h = y 2 − y 1 x 2 − x 1 x + y 1 − y 2 − y 1 x 2 − x 1 x 1 . Note that we can deal with horizontal and vertical line segments as special cases. We can find the intersections with the sides of the window by substituting y = y max , y = y min , x = x max , and x = x min (the equations for the sides of the window) into the above equation. We can check the 1

  2. Page 2
  3. Page 3
    Read page 3 as text

    locations of the points of intersection to determine if they are on the line segment or only on the line of which it is part. 1.5 In Exercise 1.4, we saw that we could intersect the line of which the line segment is part independently against each of the sides of the window. We could do this process iteratively, each time shortening the line segment if it intersects one side of the window. 1.6 Here we have to intersect the line segment against the polygons that determine the sides of the window. Each of these polygons is part of a plane. The equation of each plane is of the form ax + by + cz + d = 0 , where the coefficients a , b , c , and d can be determined from the vertices of the parallelepiped. The line segment is either parallel to a particular plane or intersects it in exactly one place that can be determined from the equation of the line. For a line passing through the two three–dimensional points ( x 1 , y 1 , z 1 ) and ( x 2 , y 2 , z 2 ), we can write its equation in parametric form as x ( t ) = (1 − t ) x 1 + tx 2 , y ( t ) = (1 − t ) y 1 + ty 2 , z ( t ) = (1 − t ) z 1 + tz 2 . We can substitute this equation in the equation for a plane and determine t for the point of intersection. 1.7 In a one–point perspective, two faces of the cube is parallel to the projection plane, while in a two–point perspective only the edges of the cube in one direction are parallel to the projection. In the general case of a three–point perspective there are three vanishing points and none of the edges of the cube are parallel to the projection plane. 1.8 We have to process 1280 x 1024 x 72 pixels/sec. If we process each successively, there is only about 10 nanoseconds to process each. For a 480 x 640 interlaced display operating at 60 Hz we must process only 480 x 640 x 30 pixels/sec which gives us about 109 nanoseconds to process each pixel. 1.9 Each frame for a 480 x 640 pixel video display contains only about 300k pixels whereas the 2000 x 3000 pixel movie frame has 6M pixels, or about 18 times as many as the video display. Thus, it can take 18 times as much time to render each frame if there is a lot of pixel-level calculations. 2

  4. Page 4
    Read page 4 as text

    1.10 Good examples for this problem are architecture, mechanical parts design, electrical circuit design and a paint program. 1.11 A 1024 x 1280 display has a 4 to 5 aspect ratio. Hence, if the diagonal is 50 cm and we want square pixels, the screen must be approximately 31 cm x 39 mm. Each pixel is then about 0.3 mm on each side. A smooth display will require about 3 triads for each pixel, and thus the triads are about 0.1 mm apart. Finally if the shadow mask is halfway between the screen and electron guns, the shadow mask spacing is half the triad spacing. 3

  5. Page 5
    Read page 5 as text

    Angel and Shreiner: Interactive Computer Graphics, Eighth Edition Chapter 2 Solutions 2.2 Each iteration removes the central triangle of the four created by subdivision. If we start with an equilateral triangle, the area is reduced by 3/4 by each iteration. Hence, in the limit we have no area left. If we consider the perimeter, again starting with an equilateral triangle, we find that if the original triangle had a side length of one unit and a perimeter of three units, the three remaining triangles created by the subdivision have a combined perimeter of 4 1/2 units. Thus the perimeter increases at each iteration and in the limit we have an object with no area and an infinite perimeter. 2.8 The subtractive colors are often called the complementary colors. Suppose each color in the RGB system can be written as the triplet (r,g,b) where each value is between 0 and 1. Then, the complement of the color (r,g,b) is the color in CMY space (c,m,y) = (1-r, 1-g, 1-b). If we want a color C in RGB space, we specify its complement in CMY space. For example, if we want a full red, in RGB it is (1,0,0) and its complement is (0,1,1). In CMY, (0,1,1) is magenta and yellow, which have red in common. 2.9 We can solve this problem separately in the x and y directions. The transformation is linear, that is x s = ax + b, y s = cy + d. We must maintain proportions, so that x s in the same relative position in the viewport as x is in the window, hence x − x min x max − x min = x s − u w , x s = u + w x − x min x max − x min . Likewise y s = v + h x − x min y max − y min . 2.10 The biggest advantage of relative positioning is that it corresponds to the way we think. We use terms such as “in front of,” “next to,”, “to the right,” “forward,” and “back” in speech to describe the location of objects. For structures that we will consider in Chapter 10, we shall see that when objects have parts such as a model of the human figure, we can describe 1

  6. Page 6
    Read page 6 as text

    their motion much easier in terms of the relative positioning of the components. In implementation, there are additional advantages to relative positioning. For example, if we store the positions of the vertices that determine an object in terms of their relative positions from a particular vertex, we can move the whole object by simply moving the base vertex. The major disadvantage of relative positioning is that if an error is made, all further positions are incorrect. To support relative positioning we must add some sort of graphics cursor which contains the position we measure from. 2.11 Most practical tests work on a line by line basis. Usually we use scanlines, each of which corresponds to a row of pixels in the frame buffer. If we compute the intersections of the edges of the polygon with a line passing through it, these intersections can be ordered. The first intersection begins a set of points inside the polygon. The second intersection leaves the polygon, the third reenters and so on. 2.12 A simple but inefficient test would be to compute the intersections of all pairs of lines that are determined by the edges of the polygons. We could then test if any of these intersections lie on the edges as opposed to the lines. 2.13 There are two fundamental approaches: vertex lists and edge lists. With vertex lists we store the vertex locations in an array. The mesh is represented as a list of interior polygons (those polygons with no other polygons inside them). Each interior polygon is represented as an array of pointers into the vertex array. To draw the mesh, we traverse the list of interior polygons, drawing each polygon. One disadvantage of the vertex list is that if we wish to draw the edges in the mesh, by rendering each polygon shared edges are drawn twice. We can avoid this problem by forming an edge list or edge array, each element is a pair of pointers to vertices in the vertex array. Thus, we can draw each edge once by simply traversing the edge list. However, the simple edge list has no information on polygons and thus if we want to render the mesh in some other way such as by filling interior polygons we must add something to this data structure that gives information as to which edges form each polygon. A flexible mesh representation would consist of an edge list, a vertex list and a polygon list with pointers so we could know which edges belong to which polygons and which polygons share a given vertex. 2

  7. Page 7
    Read page 7 as text

    2.14 The advantage of an edge list is that when we traverse the edge list, each edge is drawn exactly once which is efficient if polygons are rendered by their edges rather than filled. However, a simple edge list does not contain any polygon by polygon information such as to which polygons a given edge belongs. 2.15 The Maxwell triangle corresponds to the triangle that connects the red, green, and blue vertices in the color cube. 2.18 If can display four colors, there are 2 bits per pixel in the frame buffer. Because 64 = 2 3 ∗ 2 , we can display only 4 reds, 4 greens and 4 blues which probably indicates a low quality CRT. 2.19 Consider the lines defined by the sides of the polygon. We can assign a direction for each of these lines by traversing the vertices in a counter-clockwise order. One very simple test is obtained by noting that any point inside the object is on the left of each of these lines. Thus, if we substitute the point into the equation for each of the lines (ax+by+c), we should always get the same sign. 2.21 Each of the four tetrahedrons that are created has 1/8 of the volume of the original tetrahedron. Hence, by keeping only these four and removing the middle volume, the resulting volume is half the original volume. Each of the triangles that we create when we subdivide has 1/4 the area of the original face. Thus each subtetrahedron has the same area as one of the original faces and in total the surface area of the four subtetrahedrons is the same as the surface area of the original tetrahedron, even though the central section has been removed. If we repeat the calculation for the length of all edges, we find the length of all edges kept after a subdivision is greater the the length of the edges of the original tetrahedron. 3

  8. Page 8
    Read page 8 as text

    Angel: Interactive Computer Graphics, Eighth Edition Chapter 3 Solutions 3.7 There are a couple of potential problems. One is that the application program can map different points in object coordinates to the same point in screen coordinates. Second, a given position on the screen when transformed back into object coordinates may lie outside the user’s window. 3.8 In picking we have the additional problem that the point in screen coordinates may not correspond to a point on any object or may transform back to points on multiple objects. In the later case we may need additional information such as depth to decide which object to select. 3.11 Consider a three position switch. The three positions can correspond to velocities of 0, +1 and -1. We can integrate to get positions from these velocities. Thus, we have no change (0), a constantly increasing position (+1), and a constantly decreasing position (-1). 3.13 Let ( x 1 , y 1 ) be the end of the arm of length l 1 . Assuming that the lower-left corner is the origin x 1 = l 1 cos θ y 1 = l − 1 sin θ If ( x 2 , y 2 ) is the position of the end of the second arm, we can use a similar formula measured from ( x 1 , y 1 ) x 2 = x 1 + l 2 sin φ y 2 = y 1 + l 2 sin φ 3.14 Each scan is allocated 1/60 second. For a given scan we have to take 10% of the time for the vertical retrace which means that we start to draw scan line n at .9n/(60*1024) seconds from the beginning of the refresh. But allocating 10% of this time for the horizontal retrace we are at pixel m on this line at time .81nm/(60*1024). 3.20 When the display is changing, primitives that move or are removed from the display will leave a trace or motion blur on the display as the phosphors persist. Long persistence phosphors have been used in text only displays where motion blur is less of a problem and the long persistence gives a very stable flicker-free image. 1

  9. Page 9
    Read page 9 as text

    Angel and Shreiner: Interactive Computer Graphics, Eighth Edition Chapter 4 Solutions 4.1 If the scaling matrix is uniform then RS = RS ( α, α, α ) = α R = SR Consider R x ( θ ), if we multiply and use the standard trigonometric identities for the sine and cosine of the sum of two angles, we find R x ( θ ) R x ( φ ) = R x ( θ + φ ) By simply multiplying the matrices we find T ( x 1 , y 1 , z 1 ) T ( x 2 , y 2 , z 2 ) = T ( x 1 + x 2 , y 1 + y 2 , z 1 + z 2 ) 4.4 Translation T =    1 0 x 0 1 y 0 0 1    Rotation R =    cos θ − sin θ 0 sin θ cos θ 0 0 0 1    Scaling S =    s x 0 0 0 s y 0 0 0 1    Shear H =    1 cot φ 0 0 1 0 0 0 1    1

  10. Page 10
    Read page 10 as text

    The general form of a homogeneous coordinate transformation matrix for working with two dimensional graphics is M =    a b c d e f 0 0 1    and has six degrees of freedom. 4.5 There are 12 degrees of freedom in the three–dimensional affine transformation. Consider a point p = [ x, y, z, 1] T that is transformed to p ′ = [ x ′ y ′ , z ′ , 1] T by the matrix M . Hence we have the relationship p ′ = Mp where M has 12 unknown coefficients but p and p ′ are known. Thus we have 3 equations in 12 unknowns (the fourth equation is simply the identity 1=1). If we have 4 such pairs of points we will have 12 equations in 12 unknowns which could be solved for the elements of M . Thus if we know how a quadrilateral is transformed we can determine the affine transformation. In two dimensions, there are 6 degrees of freedom in M but p and p ′ have only x and y components. Hence if we know 3 points both before and after transformation, we will have 6 equations in 6 unknowns and thus in two dimensions if we know how a triangle is transformed we can determine the affine transformation. 4.6 The signs on the sine terms in the rotation matrices must all be changed. You can check this result by noting that a positive 90 degree rotation about z in a right–handed system brings the positive x axis to the positive z axis, while in a left–handed system a positive 90 degree rotation about the z axis brings the positive y axis to the positive x axis. Similar results hold for rotations about the x and y axes. 4.7 It is easy to show by simply multiplying the matrices that the concatenation of two rotations yields a rotation and that the concatenation of two translations yields a translation. If we look at the product of a rotation and a translation, we find that the left three columns of RT are the left three columns of R and the right column of RT is the right column of the translation matrix. If we now consider RTR ′ where R ′ is a rotation matrix, the left three columns are exactly the same as the left three columns of RR ′ and the and right column still has 1 as its bottom element. Thus, the form is the same as RT with an altered rotation (which is the concatenation of the two rotations) and an altered translation. 2

  11. Page 11
    Read page 11 as text

    Inductively, we can see that any further concatenations with rotations and translations do not alter this form. 4.8 If we do a translation by -h we convert the problem to reflection about a line passing through the origin. From m we can find an angle by which we can rotate so the line is aligned with either the x or y axis. Now reflect about the x or y axis. Finally we undo the rotation and translation so the sequence is of the form T − 1 R − 1 SRT . 4.9 We can start with a rotation about any of the axes. The next rotation can be about either of the other two axes and the third can be either about the third axis or the first. Hence there are 3*2*2 = 12 possible orders: xyz, xyx, xzy, xzx, yxz, yxy, yzx, yzy, zyx, zyz, zxy, zxz. 4.11 The most sensible place to put the shear is second so that the instance transformation becomes I = TRHS . We can see that this order makes sense if we consider a cube centered at the origin whose sides are aligned with the axes. The scale gives us the desired size and proportions. The shear then converts the right parallelepiped to a general parallelepiped. Finally we can orient this parallelepiped with a rotation and place it where desired with a translation. Note that the order I = TRSH will work too. 4.12 A plane can be described by the equation ax + by + cz + d = 0 . If we define the two homogeneous coordinate column matrices p = [ x y z 1 ] T and n = [ a b c d ] T then the equation of the plane becomes p · n = 0 . 4.13 A vertex in a three-dimensional system is a location. It has no other properties but its location. 4.14 R = R z ( θ z ) R y ( θ y ) R x ( θ x ) =      cos θ y cos θ z cos θ z sin θ x sin θ y − cos θ x sin θ z cos θ x cos θ z sin θ y + sin θ x sin θ z 0 cos θ y sin θ z cos θ x cos θ z + sin θ x sin θ y sin θ z − cos θ z sin θ x + cos θ x sin θ y sin θ z 0 − sin θ y cos θ y sin θ x cos θ x cos θ y 0 0 0 0 1      4.16 It would seem that the matrix R = R x (45) R y (45) would be correct but it is not. After the first rotation by 45 degrees, the resulting side view is not symmetric and the required angle of rotation has a cosine of √ 6 3 . The angle is approximately 35.36 degrees. We consider this problem in Section 5.3. 3

  12. Page 12
    Read page 12 as text

    4.17 One test is to use the first three vertices to find the equation of the plane ax + by + cz + d = 0. Although there are four coefficients in the equation only three are independent so we can select one arbitrarily or normalize so that a 2 + b 2 + c 2 = 1. Then we can successively evaluate ax + bc + cz + d for the other vertices. A vertex will be on the plane if we evaluate to zero. An equivalent test is to form the matrix      1 1 1 1 x 1 x 2 x 3 x 4 y 1 y 2 y 3 y 4 z 1 z 2 z 3 z 4      for each i = 4 , ... If the determinant of this matrix is zero the ith vertex is in the plane determined by the first three. 4.18 If they are collinear, one vertex is a linear combination of the other two and the determinant of the matrix      x 1 x 2 x 3 y 1 y 2 y 3 z 1 z 2 z 3      will be zero. 4.19 Although we will have the same number of degrees of freedom in the objects we produce, the class of objects will be very different. For example if we rotate a square before we apply a nonuniform scale, we will shear the square, something we cannot do if we scale then rotate. 4.21 The vector a = u × v is orthogonal to u and v . The vector b = u × a is orthogonal to u and a . Hence, u , a and b form an orthogonal coordinate system. 4.22 The determinant of the matrix is 1 + θ 2 . Repeated multiplications by this matrix increase the determinant so the resulting operation becomes further and further from a rotation matrix causing the point to become further and further from the origin. One remedy is to use the matrix R =      1 − θ 0 0 θ 1 − θ 2 0 0 0 0 1 0 0 0 0 1      , 4

  13. Page 13
    Read page 13 as text

    which has a determinant of 1. 4.23 Using r = cos θ 2 + sin θ 2 v , with θ = 90 and v = (1 , 0 , 0) , we find for rotation about the x -axis r = √ 2 2 (1 , 1 , 0 , 0) . Likewise, for rotation about the y axis r = √ 2 2 (1 , 0 , 1 , 0) . 4.24 Using the notation sin θ x = s x , cos θ x = c x , and likewise for θ y and θ z , we find R x ( θ x ) R y ( θ y ) R z ( θ z ) =      c y c z − c y s z s y 0 − c z s x s y + c x s z − s x s y s z + c z c z − s x c y 0 − c x s y c z + s x s z c x s y s z + s x c z c x c y 0 0 0 0 1      . Using quaternions, we form the three unit quaternions r x = cos θ x 2 + sin θ x 2 (1 , 0 , 0) , r x = cos θ y 2 + sin θ y 2 (0 , 1 , 0) , r x = cos θ z 2 + sin θ z 2 (0 , 0 , 1) . We can now compute r x r y r z using quaternion multiplication and obtain a resulting quaternion whose elements correspond to those of the matrix. 4.27 Possible reasons include (1) object-oriented systems are slower, (2) users are often comfortable working in world coordinates with higher-level objects and do not need the flexibility offered by a coordinate-free approach, (3) even a system that provides scalars, vectors, and points would have to have an underlying frame to use for the implementation. 4.28 (a) ¿1 (b) ¿0 and ¡1 4.29 Expanding repeatedly as in the hint P = α 1 P 1 + α 2 P 2 + . . . = α 1 P 1 + ( α 2 + α 1 − α 1 ) P 2 + . . . 5

28 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Information Technology study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.