Angel: Interactive Computer Graphics, Fifth Edition Chapter 1 SolutionsThe 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.We derive this algorithm later in Chapter 6. First, we can form the tetrahedron by finding four equally spaced points on a unit sphere centeredat 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, 2p2/3,−1/3). The other two can be found by symmetry to be at(−p6/3,−p2/3,−1/3) and (p6/3,−p2/3,−1/3).We can subdivide each face of the tetrahedron into four equilateral triangles by bisecting the sides and connecting the bisectors. However, thebisectors 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.In Exercise , 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 segmentif it intersects one side of the window.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 athree–point perspective there are three vanishing points and none of the edges of the cube are parallel to the projection plane.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 asmuch time to render each frame if there is a lot of pixel-level calculations.There are single beam CRTs. One scheme is to arrange the phosphorsin vertical stripes (red, green, blue, red, green, ....). The major difficulty isthat the beam must change very rapidly, approximately three times as fast a each beam in a three beam system. The electronics in such a system the electronic components must also be much faster (and more expensive).Chapter 2 SolutionsWe can solve this problem separately in the x and y directions. The transformation is linear, that is xs = ax + b, ys = cy + d. We must maintain proportions, so that xs in the same relative position in the viewport as x is in the window, hencex − xminxmax − xmin=xs − uw,xs = u + wx − xminxmax − xmin.Likewiseys = v + hx − xminymax − ymin.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 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.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 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. 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 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 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 listand a polygon list with pointers so we could know which edges belong to which polygons and which polygons share a given vertex.The Maxwell triangle corresponds to the triangle that connects the red, green, and blue vertices in the color cube.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 wesubstitute the point into the equation for each of the lines (ax+by+c), weshould always get the same sign.There are eight vertices and thus 256 = 28 possible black/white colorings. If we remove symmetries (black/white and rotational) there are 14 unique cases. See Angel, Interactive Computer Graphics (Third Edition) or the paper by Lorensen and Kline in the references.Chapter 3 SolutionsThe general problem is how to describe a set of characters that might have thickness, curvature, and holes (such as in the letters a and q). Suppose that we consider a simple example where each character can be approximated by a sequence of line segments. One possibility is to use amove/line system where 0 is a move and 1 a line. Then a character can be described by a sequence of the form (x0, y0, b0), (x1, y1, b1), (x2, y2, b2), .....where bi is a 0 or 1. This approach is used in the example in the OpenGL Programming Guide. A more elaborate font can be developed by using polygons instead of line segments.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.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 mon this line at time .81nm/(60*1024).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.Chapter 4 SolutionsIf the scaling matrix is uniform thenRS = RS(α, α, α) = αR = SRConsider R x(θ), if we multiply and use the standard trigonometric identities for the sine and cosine of the sum of two angles, we findR x(θ)R x(φ) = R x(θ + φ)By simply multiplying the matrices we findT(x1, y1, z1)T(x2, y2, z2) = T(x1 + x2, y1 + y2, z1 + z2)There are 12 degrees of freedom in the three–dimensional affine transformation. Consider a point p = [x, y, z, 1]T that is transformed top_ = [x_y_, z_, 1]T by the matrix M. Hence we have the relationshipp_ = 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.It is easy to show by simply multiplying the matrices that the concatenation 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 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. Inductively, we can see that any further concatenations with rotations andtranslations do not alter this form.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 thesequence is of the form T−1R−1SRT.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 wheredesired with a translation. Note that the order I = TRSH will work too. 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 0cos θ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 00 0 0 1⎡⎡⎡⎡⎡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 a2 + b2 + c2 = 1. Then we can successively evaluate ax + bc + cz + d for the other vertices. A vertex will be on the plane if weevaluate to zero. An equivalent test is to form the matrix⎡⎡⎡⎡⎡1 1 1 1x1 x2 x3 x4y1 y2 y3 y4z1 z2 z3 z4⎡⎡⎡⎡⎡for each i = 4, ... If the determinant of this matrix is zero the ith vertex isin the plane determined by the first three.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 exampleif we rotate a square before we apply a nonuniform scale, we will shear thesquare, something we cannot do if we scale then rotate.The vector a = u × v is orthogonal to u and v. The vector b = u × a isorthogonal to u and a. Hence, u, a and b form an orthogonal coordinate system.Using r = cos θ2+ sin θ2v, with θ = 90 and v = (1, 0, 0), we find forrotation about the x-axisr =√22(1, 1, 0, 0).Likewise, for rotation about the y axisr =√22(1, 0, 1, 0).Possible reasons include (1) object-oriented systems are slower, (2) users are often comfortable working in world coordinates withhigher-levelobjects 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.Chapter 5 SolutionsEclipses (both solar and lunar) are good examples of the projection ofan object (the moon or the earth) onto a nonplanar surface. Any time a shadow is created on curved surface, there is a nonplanar projection. All the maps in an atlas are examples of the use of curved projectors. If the projectors were not curved we could not project the entire surface of a spherical object (the Earth) onto a rectangle.Suppose that we want the view of the Earth rotating about the sun. Before we draw the earth, we must rotate the Earth which is a rotation about the y axis. Next we translate the Earth away from the origin. Finally we do another rotation about the y axis to position the Earth in itsdesired location along its orbit. There are a number of interesting variantsof this problem such as the view from the Earth of the rest of the solar system.Yes. Any sequence of rotations is equivalent to a single rotation about a suitably chosen axis. One way to compute this rotation matrix is to form the matrix by sequence of simple rotations, such asR = RxRyRz.The desired axis is an eigenvector of this matrix.The result follows from the transformation being affine. We can also take a direct approach. Consider the line determined by the points(x1, y1, z1) and (x2, y2, z2). Any point along can be written parametricallyas (_x1 + (1 −_)x2, _y1 + (1 −_)y2, _z1 + (1 −_)z2). Consider the simple projection of this point 1d(_z1+(1−_)z2) (_x1 + (1 − _)x2, _y1 + (1 − _)y2)which is of the form f(_)(_x1 + (1 − _)x2, _y1 + (1 − _)y2). This form describes a line because the slope is constant. Note that the function f(_)implies that we trace out the line at a nonlinear rate as _ increases from 0to 1.The specification used in many graphics text is of the angles the projector makes with x,z and y, z planes, the angles defined by the projection of a projector by a top view and a side view.Another approach is to specify the foreshortening of one or two sides of acube aligned with the axes.The CORE system used this approach. Retained objects were kept indistorted form. Any transformation to any object that was defined with other than an orthographic view transformed the distorted object and the orthographic projection of the transformed distorted object was incorrect.If we use _ = _ = 45, we obtain the projection matrixP =266641 0 −1 00 1 −1 00 0 0 00 0 0 137775All the points on the projection of the point , z) in the direction dx, dy, dz) are of the form (x + _dx, y + _dy, z + _dz). Thus the shadow ofthe point (x, y, z) is found by determining the _ for which the line intersects the plane, that isaxs + bys + czs = dSubstituting and solving, we find_ =d − ax − by − czadx + bdy + cdz.However, what we want is a projection matrix, Using this value of _ we findxs = z + _dx =x(bdy + cdx) − dx(d − by − cz)adx + bdy + cdzwith similar equations for ys and zs. These results can be computed by multiplying the homogeneous coordinate point (x, y, z, 1) by the projectionmatrixM =26664bdy + cdz −bdx −cdx −ddx−ady adx + cdz −cdy −ddy−adz −bdz adx + bdy −ddz0 0 0 adx + bdy + cdz37775.Suppose that the average of the two eye positions is at (x, y, z) and the viewer is looking at the origin. We could form the images using the LookAt function twice, that isgluLookAt(x-dx/2, y, z, 0, 0, 0, 0, 1, 0);/* draw scene here *//* swap buffers and clear */gluLookAt(x+dx/2, y, z, 0, 0, 0, 0, 1, 0);/* draw scene again *//* swap buffers and clear */Chapter 6 SolutionsPoint sources produce a very harsh lighting. Such images are characterized by abrupt transitions between light and dark. The ambient light in a real scene is dependent on both the lights on the scene and thereflectivity properties of the objects in the scene, something that cannot becomputed correctly with OpenGL. The Phong reflection term is not physically correct; the reflection term in the modified Phong model is evenfurther from being physically correct.If we were to take into account a light source being obscured by an object, we would have to have all polygons available so as to test for thiscondition. Such a global calculation is incompatible with the pipeline model that assumes we can shade each polygon independently of all other polygons as it flows through the pipeline.Materials absorb light from sources. Thus, a surface that appears red under white light appears so because the surface absorbs all wavelengths oflight except in the red range—a subtractive process. To be compatible withsuch a model, we should use surface absorbtion constants that define the materials for cyan, magenta and yellow, rather than red, green and blue.Let ψ be the angle between the normal and the halfway vector, φ be the angle between the viewer and the reflection angle, and θ be the anglebetween the normal and the light source. If all the vectors lie in the sameplane, the angle between the light source and the viewer can be computer either as φ + 2θ or as 2(θ + ψ). Setting the two equal, we find φ = 2ψ. Ifthe vectors are not coplanar then φ < 2ψ.Without loss of generality, we can consider the problem in two dimensions. Suppose that the first material has a velocity of light of v1 andthe second material has a light velocity of v2. Furthermore, assume that the axis y = 0 separates the two materials.Place a point light source at (0, h) where h > 0 and a viewer at (x, y) where y < 0. Light will travel in a straight line from the source to a point(t, 0) where it will leave the first material and enter the second. It willthen travel from this point in a straight line to (x, y). We must find the tthat minimizes the time travelled.Using some simple trigonometry, we find the line from the source to (t, 0)has length l1 = √h2 + t2 and the line from there to the viewer has length 1l2 = _y2 + (x − t)2. The total time light travels is thus l1v1 + l2v2 .Minimizing over t gives desired result when we note the two desired sines are sin θ1 = h√h2+t2 and sin θ2 = −y √(y2+(x−t)2 .Shading requires that when we transform normals and points, we maintain the angle between them or equivalently have the dot productp ·v = p_ ·v_ when p_ = Mp and n_ = Mp. If M T M is an identity matrix angles are preserved. Such a matrix (M−1 = M T ) is called orthogonal. Rotations and translations are orthogonal but scaling and shear are not.Probably the easiest approach to this problem is to rotate the given plane to plane z = 0 and rotate the light source and objects in the same way. Now we have the same problem we have solved and can rotate everything back at the end.A global rendering approach would generate all shadows correctly. Ina global renderer, as each point is shaded, a calculation is done to see which light sources shine on it. The projection approach assumes that we can project each polygon onto all other polygons. If the shadow of a given polygon projects onto multiple polygons, we could not compute these shadow polygons very easily. In addition, we have not accounted for the different shades we might see if there were intersecting shadows from multiple light sources.Chapter 7 SolutionsFirst, consider the problem in two dimensions. We are looking for an _ and _ such that both parametric equations yield the same point, that is x(_) = (1 − _)x1 + _x2 = (1 − _)x3 + _x4,y(_) = (1 − _)y1 + _y2 = (1 − _)y3 + _y4.These are two equations in the two unknowns _ and _ and, as long as the line segments are not parallel (a condition that will lead to a division byzero), we can solve for _ _. If both these values are between 0 and 1, thesegments intersect.If the equations are in 3D, we can solve two of them for the _ and _ where x and y meet. If when we use these values of the parameters in the two equations for z, the segments intersect if we get the same z from both equations.If we clip a convex region against a convex region, we produce the intersection of the two regions, that is the set of all points in both regions,which is a convex set and describes a convex region. To see this, consider any two points in the intersection. The line segment connecting them must be in both sets and therefore the intersection is convex.See Problem . Nonuniform scaling will not preserve the anglebetween the normal and other vectors.Note that we could use OpenGL to, produce a hidden line removed image by using the z buffer and drawing polygons with edges and interiors the same color as the background. But of course, this method was not used in pre–raster systems.Hidden–line removal algorithms work in object space, usually with either polygons or polyhedra. Back–facing polygons can be eliminated. In general, edges are intersected with polygons to determine any visible parts.Good algorithms (see Foley or Rogers) use various coherence strategies tominimize the number of intersections.The O(k) was based upon computing the intersection of rays with the planes containing the k polygons. We did not consider the cost of filling thepolygons, which can be a large part of the rendering time. If we consider ascene which is viewed from a given point there will be some percentage of1the area of the screen that is filled with polygons. As we move the viewer closer to the objects, fewer polygons will appear on the screen but each will occupy a larger area on the screen, thus leaving the area of the screen that is filled approximately the same. Thus the rendering time will be about the same even though there are fewer polygons displayed.There are a number of ways we can attempt to get O(k log k) performance. One is to use a better sorting algorithm for the depth sort. Other strategies are based on divide and conquer such a binary spatial partitioning.If we consider a ray tracer that only casts rays to the first intersection and does not compute shadow rays, reflected or transmitted rays, then the image produced using a Phong model at the point of intersection will be the same image as produced by our pipeline renderer. This approach is sometimes called ray casting and is used in volume rendering and CSG. However, the data are processed in a different order from the pipeline renderer. The ray tracer works ray by ray while the pipeline renderer works object by object.Consider a circle centered at the origin: x2 + y2 = r2. If we know that a point (x, y) is on the curve than, we also know (−x, y), (x,−y), (−x,−y), (y, x), (−y, x), (y,−x), and (−y,−x) are also on the curve. This observation is known as the eight–fold symmetry of the circle. Consequently, we need only generate 1/8 of the circle, a 45 degree wedge, and can obtain the rest by copying this part using the symmetries. If we consider the 45 degree wedge starting at the bottom, the slope of thiscurve starts at 0 and goes to 1, precisely the conditions used for Bresenham’s line algorithm. The tests are a bit more complex and we have to account for the possibility the slope will be one but the approach is thesame as for line generation.Flood fill should work with arbitrary closed areas. In practice, we can get into trouble at corners if the edges are not clearly defined. Such can bethe case with scanned images.Note that if we fill by scan lines vertical edges are not a problem. Probably the best way to handle the problem is to avoid it completely by never allowing vertices to be on scan lines. OpenGL does this by having vertices placed halfway between scan lines. Other systems jitter the y value of any vertex where it is an integer.Although each pixel uses five rays, the total number of rays has only doubled, . consider a second grid that is offset one half pixel in both thex and y directions.A mathematical answer can be investigated using the notion of reconstruction of a function from its samples (see Chapter 8). However, avery easy to see by simply drawing bitmap characters that small pixels lead to very unreadable characters. A readable character should have some overlap of the pixels.We want k levels between Imin and Imax that are distributed exponentially. Then I0 = Imin, I1 = Iminr,I2 = Iminr2, ..., Ik−1 = Imax = Iminrk−1. We can solve the last equation forthe desired r = ( ImaxImin)1k−1If there are very few levels, we cannot display a gradual change in brightness. Instead the viewer will see steps of intensity. A simple rule ofthumb is that we need enough gray levels so that a change of one step is not visible. We can mitigate the problem by adding one bit of random noise to the least significant bit of a pixel. Thus if we have 3 bits (8 levels),the third bit will be noise. The effect of the noise will be to break up regions of almost constant intensity so the user will not be able to see astep because it will be masked by the noise. In a statistical sense the jittered image is a noisy (degraded) version of the original but in a visualsense it appears better.。
