Solution Manual for Interactive Computer Graphics, 8th Edition

Preview (13 of 41 Pages)

100%

Purchase to unlock

Loading page image...

Angel and Shreiner: Interactive Computer Graphics, EighthEditionChapter 1 Solutions1.1 The main advantage of the pipeline is that each primitive can beprocessed independently. Not only does this architecture lead to fastperformance, it reduces memory requirements because we need not keep allobjects available. The main disadvantage is that we cannot handle mostglobal effects such as shadows, reflections, and blending in a physicallycorrect manner.1.2 If we use lines of constant longitude and lines of constant latitude, theirintersections define a set of quadrilaterals. If we draw diagonals for eachquadrilateral, we get a set of triangles. However, at the poles all the curvesof constant longitude meet and we get triangles rather than quadrilaterals.1.3 We derive this algorithm later in Chapter 6. First, we can form thetetrahedron by finding four equally spaced points on a unit sphere centeredat the origin. One approach is to start with one point on thezaxis(0,0,1). We then can place the other three points in a plane of constantz.One of these three points can be placed on theyaxis. To satisfy therequirement 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 equilateraltriangles by bisecting the sides and connecting the bisectors. However, thebisectors of the sides are not on the unit circle so we must push thesepoints out to the unit circle by scaling the values. We can continue thisprocess recursively on each of the triangles created by the bisection process.1.4 Suppose that the line segment is between the points (x1, y1) and(x2, y2) We can use the endpoints of the line segment to determine theslope and y intercept of a line of which the segment is part, i.e.y=mx+h=y2−y1x2−x1x+y1−y2−y1x2−x1x1.Note that we can deal with horizontal and vertical line segments as specialcases. We can find the intersections with the sides of the window bysubstitutingy=ymax,y=ymin,x=xmax, andx=xmin(the equationsfor the sides of the window) into the above equation. We can check the1

Loading page image...

locations of the points of intersection to determine if they are on the linesegment 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 theline segment is part independently against each of the sides of the window.We could do this process iteratively, each time shortening the line segmentif it intersects one side of the window.1.6 Here we have to intersect the line segment against the polygons thatdetermine the sides of the window. Each of these polygons is part of aplane. The equation of each plane is of the formax+by+cz+d= 0,where the coefficientsa,b,c, anddcan be determined from the vertices ofthe parallelepiped. The line segment is either parallel to a particular planeor intersects it in exactly one place that can be determined from theequation of the line. For a line passing through the two three–dimensionalpoints (x1, y1, z1) and (x2, y2, z2), we can write its equation in parametricform asx(t) = (1−t)x1+tx2,y(t) = (1−t)y1+ty2,z(t) = (1−t)z1+tz2.We can substitute this equation in the equation for a plane and determinetfor the point of intersection.1.7 In a one–point perspective, two faces of the cube is parallel to theprojection plane, while in a two–point perspective only the edges of thecube in one direction are parallel to the projection. In the general case of athree–point perspective there are three vanishing points and none of theedges 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 eachsuccessively, there is only about 10 nanoseconds to process each. For a 480x 640 interlaced display operating at 60 Hz we must process only 480 x 640x 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 about300k pixels whereas the 2000 x 3000 pixel movie frame has 6M pixels, orabout 18 times as many as the video display. Thus, it can take 18 times asmuch time to render each frame if there is a lot of pixel-level calculations.2

Loading page image...

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

Loading page image...

Angel and Shreiner: Interactive Computer Graphics, EighthEditionChapter 2 Solutions2.2 Each iteration removes the central triangle of the four created bysubdivision. If we start with an equilateral triangle, the area is reduced by3/4 by each iteration. Hence, in the limit we have no area left. If weconsider the perimeter, again starting with an equilateral triangle, we findthat if the original triangle had a side length of one unit and a perimeter ofthree units, the three remaining triangles created by the subdivision have acombined perimeter of 4 1/2 units. Thus the perimeter increases at eachiteration and in the limit we have an object with no area and an infiniteperimeter.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 acolor C in RGB space, we specify its complement in CMY space. Forexample, 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 thexandydirections. Thetransformation is linear, that isxs=ax+b, ys=cy+d.We mustmaintain proportions, so thatxsin the same relative position in theviewport asxis in the window, hencex−xminxmax−xmin=xs−uw,xs=u+wx−xminxmax−xmin.Likewiseys=v+hx−xminymax−ymin.2.10 The biggest advantage of relative positioning is that it corresponds tothe way we think. We use terms such as “in front of,” “next to,”, “to theright,” “forward,” and “back” in speech to describe the location of objects.For structures that we will consider in Chapter 10, we shall see that whenobjects have parts such as a model of the human figure, we can describe1

Loading page image...

their motion much easier in terms of the relative positioning of thecomponents. In implementation, there are additional advantages to relativepositioning. For example, if we store the positions of the vertices thatdetermine an object in terms of their relative positions from a particularvertex, 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 cursorwhich contains the position we measure from.2.11 Most practical tests work on a line by line basis. Usually we usescanlines, 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 linepassing through it, these intersections can be ordered. The firstintersection begins a set of points inside the polygon. The secondintersection leaves the polygon, the third reenters and so on.2.12 A simple but inefficient test would be to compute the intersections ofall pairs of lines that are determined by the edges of the polygons. Wecould then test if any of these intersections lie on the edges as opposed tothe 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 isrepresented as a list of interior polygons (those polygons with no otherpolygons inside them). Each interior polygon is represented as an array ofpointers into the vertex array. To draw the mesh, we traverse the list ofinterior polygons, drawing each polygon.One disadvantage of the vertex list is that if we wish to draw the edges inthe mesh, by rendering each polygon shared edges are drawn twice. Wecan avoid this problem by forming an edge list or edge array, each elementis a pair of pointers to vertices in the vertex array. Thus, we can draw eachedge once by simply traversing the edge list. However, the simple edge listhas no information on polygons and thus if we want to render the mesh insome other way such as by filling interior polygons we must add somethingto this data structure that gives information as to which edges form eachpolygon.A flexible mesh representation would consist of an edge list, a vertex listand a polygon list with pointers so we could know which edges belong towhich polygons and which polygons share a given vertex.2

Loading page image...

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 renderedby their edges rather than filled. However, a simple edge list does notcontain any polygon by polygon information such as to which polygons agiven edge belongs.2.15 The Maxwell triangle corresponds to the triangle that connects thered, green, and blue vertices in the color cube.2.18 If can display four colors, there are 2 bits per pixel in the framebuffer. Because 64 = 23∗2, we can display only 4 reds, 4 greens and 4 blueswhich probably indicates a low quality CRT.2.19 Consider the lines defined by the sides of the polygon. We can assigna direction for each of these lines by traversing the vertices in acounter-clockwise order. One very simple test is obtained by noting thatany point inside the object is on the left of each of these lines. Thus, if wesubstitute the point into the equation for each of the lines (ax+by+c), weshould always get the same sign.2.21 Each of the four tetrahedrons that are created has 1/8 of the volumeof the original tetrahedron. Hence, by keeping only these four andremoving the middle volume, the resulting volume is half the originalvolume. Each of the triangles that we create when we subdivide has 1/4the area of the original face. Thus each subtetrahedron has the same areaas one of the original faces and in total the surface area of the foursubtetrahedrons is the same as the surface area of the original tetrahedron,even though the central section has been removed. If we repeat thecalculation for the length of all edges, we find the length of all edges keptafter a subdivision is greater the the length of the edges of the originaltetrahedron.3

Loading page image...

Angel: Interactive Computer Graphics, Eighth EditionChapter 3 Solutions3.7 There are a couple of potential problems. One is that the applicationprogram can map different points in object coordinates to the same pointin screen coordinates. Second, a given position on the screen whentransformed back into object coordinates may lie outside the user’swindow.3.8 In picking we have the additional problem that the point in screencoordinates may not correspond to a point on any object or may transformback to points on multiple objects. In the later case we may needadditional information such as depth to decide which object to select.3.11 Consider a three position switch. The three positions can correspondto velocities of 0, +1 and -1. We can integrate to get positions from thesevelocities. Thus, we have no change (0), a constantly increasing position(+1), and a constantly decreasing position (-1).3.13 Let (x1, y1) be the end of the arm of lengthl1. Assuming that thelower-left corner is the originx1=l1cosθy1=l−1 sinθIf (x2, y2) is the position of the end of the second arm, we can use a similarformula measured from (x1, y1)x2=x1+l2sinφy2=y1+l2sinφ3.14 Each scan is allocated 1/60 second. For a given scan we have to take10% of the time for the vertical retrace which means that we start to drawscan 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 mon this line at time .81nm/(60*1024).3.20 When the display is changing, primitives that move or are removedfrom the display will leave a trace or motion blur on the display as thephosphors persist. Long persistence phosphors have been used in text onlydisplays where motion blur is less of a problem and the long persistencegives a very stable flicker-free image.1

Loading page image...

Angel and Shreiner: Interactive Computer Graphics, EighthEditionChapter 4 Solutions4.1 If the scaling matrix is uniform thenRS=RS(α, α, α) =αR=SRConsiderRx(θ), if we multiply and use the standard trigonometricidentities for the sine and cosine of the sum of two angles, we findRx(θ)Rx(φ) =Rx(θ+φ)By simply multiplying the matrices we findT(x1, y1, z1)T(x2, y2, z2) =T(x1+x2, y1+y2, z1+z2)4.4 TranslationT=10x01y001RotationR=cosθ−sinθ0sinθcosθ0001ScalingS=sx000sy0001ShearH=1cotφ00100011

Loading page image...

The general form of a homogeneous coordinate transformation matrix forworking with two dimensional graphics isM=abcdef001and has six degrees of freedom.4.5 There are 12 degrees of freedom in the three–dimensional affinetransformation. Consider a pointp= [x, y, z,1]Tthat is transformed top′= [x′y′, z′,1]Tby the matrixM. Hence we have the relationshipp′=MpwhereMhas 12 unknown coefficients butpandp′are known.Thus we have 3 equations in 12 unknowns (the fourth equation is simplythe identity 1=1). If we have 4 such pairs of points we will have 12equations in 12 unknowns which could be solved for the elements ofM.Thus if we know how a quadrilateral is transformed we can determine theaffine transformation.In two dimensions, there are 6 degrees of freedom inMbutpandp′haveonlyxandycomponents. Hence if we know 3 points both before and aftertransformation, we will have 6 equations in 6 unknowns and thus in twodimensions if we know how a triangle is transformed we can determine theaffine transformation.4.6 The signs on the sine terms in the rotation matrices must all bechanged. You can check this result by noting that a positive 90 degreerotation about z in a right–handed system brings the positive x axis to thepositive z axis, while in a left–handed system a positive 90 degree rotationabout the z axis brings the positive y axis to the positive x axis. Similarresults hold for rotations about the x and y axes.4.7 It is easy to show by simply multiplying the matrices that theconcatenation of two rotations yields a rotation and that the concatenationof two translations yields a translation. If we look at the product of arotation and a translation, we find that the left three columns ofRTarethe left three columns ofRand the right column ofRTis the rightcolumn of the translation matrix. If we now considerRTR′whereR′is arotation matrix, the left three columns are exactly the same as the leftthree columns ofRR′and the and right column still has 1 as its bottomelement. Thus, the form is the same asRTwith an altered rotation (whichis the concatenation of the two rotations) and an altered translation.2

Loading page image...

Inductively, we can see that any further concatenations with rotations andtranslations do not alter this form.4.8 If we do a translation by -h we convert the problem to reflection abouta line passing through the origin. From m we can find an angle by whichwe can rotate so the line is aligned with either the x or y axis. Now reflectabout the x or y axis. Finally we undo the rotation and translation so thesequence is of the formT−1R−1SRT.4.9 We can start with a rotation about any of the axes. The next rotationcan be about either of the other two axes and the third can be eitherabout the third axis or the first. Hence there are 3*2*2 = 12 possibleorders: 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 instancetransformation becomesI=TRHS. We can see that this order makessense if we consider a cube centered at the origin whose sides are alignedwith the axes. The scale gives us the desired size and proportions. Theshear then converts the right parallelepiped to a general parallelepiped.Finally we can orient this parallelepiped with a rotation and place it wheredesired with a translation. Note that the orderI=TRSHwill work too.4.12 A plane can be described by the equationax+by+cz+d= 0.If wedefine the two homogeneous coordinate column matricesp=[xyz1]Tandn=[abcd]Tthen the equation of theplane becomesp·n= 0.4.13 A vertex in a three-dimensional system is a location. It has no otherproperties but its location.4.14R=Rz(θz)Ry(θy)Rx(θx) =cosθycosθzcosθzsinθxsinθy−cosθxsinθzcosθxcosθzsinθy+ sinθxsinθz0cosθysinθzcosθxcosθz+ sinθxsinθysinθz−cosθzsinθx+ cosθxsinθysinθz0−sinθycosθysinθxcosθxcosθy000014.16 It would seem that the matrixR=Rx(45)Ry(45) would be correctbut it is not. After the first rotation by 45 degrees, the resulting side viewis not symmetric and the required angle of rotation has a cosine of√63.The angle is approximately 35.36 degrees. We consider this problem inSection 5.3.3

Loading page image...

4.17 One test is to use the first three vertices to find the equation of theplaneax+by+cz+d= 0. Although there are four coefficients in theequation only three are independent so we can select one arbitrarily ornormalize so thata2+b2+c2= 1. Then we can successively evaluateax+bc+cz+dfor the other vertices. A vertex will be on the plane if weevaluate to zero. An equivalent test is to form the matrix1111x1x2x3x4y1y2y3y4z1z2z3z4for eachi= 4, ...If the determinant of this matrix is zero the ith vertex isin the plane determined by the first three.4.18 If they are collinear, one vertex is a linear combination of the othertwo and the determinant of the matrixx1x2x3y1y2y3z1z2z3will be zero.4.19 Although we will have the same number of degrees of freedom in theobjects we produce, the class of objects will be very different. For exampleif we rotate a square before we apply a nonuniform scale, we will shear thesquare, something we cannot do if we scale then rotate.4.21 The vectora=u×vis orthogonal touandv. The vectorb=u×aisorthogonal touanda. Hence,u,aandbform an orthogonal coordinatesystem.4.22 The determinant of the matrix is 1 +θ2. Repeated multiplications bythis matrix increase the determinant so the resulting operation becomesfurther and further from a rotation matrix causing the point to becomefurther and further from the origin. One remedy is to use the matrixR=1−θ00θ1−θ20000100001,4

Loading page image...

which has a determinant of 1.4.23 Usingr= cosθ2+ sinθ2v,withθ= 90 andv= (1,0,0),we find forrotation about thex-axisr=√22 (1,1,0,0).Likewise, for rotation about theyaxisr=√22 (1,0,1,0).4.24 Using the notation sinθx=sx, cosθx=cx,and likewise forθyandθz,we findRx(θx)Ry(θy)Rz(θz) =cycz−cyszsy0−czsxsy+cxsz−sxsysz+czcz−sxcy0−cxsycz+sxszcxsysz+sxczcxcy00001.Using quaternions, we form the three unit quaternionsrx= cosθx2 + sinθx2 (1,0,0),rx= cosθy2 + sinθy2 (0,1,0),rx= cosθz2 + sinθz2 (0,0,1).We can now computerxryrzusing quaternion multiplication and obtain aresulting 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-levelobjects and do not need the flexibility offered by a coordinate-freeapproach, (3) even a system that provides scalars, vectors, and pointswould have to have an underlying frame to use for the implementation.4.28 (a) ¿1 (b) ¿0 and ¡14.29 Expanding repeatedly as in the hintP=α1P1+α2P2+. . .=α1P1+ (α2+α1−α1)P2+. . .5

Preview Mode

This document has 41 pages. Sign in to access the full document!

Report

Study Now!

Document Details

Related Documents

DevOps and Its Importance Study Notes

Veeam Certified Engineer VMCE-V12

Modules 1 - 3 Basic Network Connectivity and Commu

Notes CCNA

CCNA 200-301 Portable Command Guide 5th Edition 20

CCNA 200-301 Portable Command Guide 5th Edition 22

CCNA 200-301 Portable Command Guide 5th Edition 36

Foundations of Novell Networking Section 26

Modulo 7 DHCPv4

Build and troubleshooting Integration Challenge

Company

Explore

Study Tools