Angel and Shreiner: Interactive Computer Graphics, Seventh
Edition
Chapter 8 Solutions
8.1 First, 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 by
8.2 We can form the equation of the plane of the first polygon using any
three of its vertices. We can next put each of the vertices of the second
polygon into this equation. If we get the same sign for all, then the second
polygon cannot intersect the first. If two successive vertices have different
8.3 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,
8.4 The object–oriented approach has an outer loop that goes over
objects.We can try to parallelize the rendering of objects. However, we
would need some method of combining the objects at the end and
1
8.5 See Problem 5.22. Nonuniform scaling will not preserve the angle
8.6 First we want to move the window to the center with the translation
T(−(xmax +xmin)/2,−(ymax +ymin)/2,0). Next we want to scale the
8.7 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.
8.8 We can use our ability to render filled polygons by forming
quadrilaterals. Consider the back (furthest from the viewer) two sets of
data {f(xi, zN)}and {f(xi, zN−1)}. We form quadrilaterals from the
values {f(xi, zN)},{f(xi+1, zN)},{f(xi, zN−1)}, and {f(xi−1, zN−1)}for
i= 0,1,2, …. Once these are rendered, we go on to form quadrilaterals
2
that part of the calculation involves intersecting the curve with the visible
top and bottom. This calculation must be carried out to the resolution of
the display to avoid dangling line segments. This algorithm does not
require fill and was used before raster displays became available.
8.9 The O(k) was based upon computing the intersection of rays with the
planes containing the kpolygons. We did not consider the cost of filling the
polygons, which can be a large part of the rendering time. If we consider a
scene which is viewed from a given point there will be some percentage of
8.10 Each convex polyhedra can be culled because none of its back faces
8.11 There are a number of ways we can attempt to get O(klog k)
performance. One is to use a better sorting algorithm for the depth sort.
8.12 We can find the equation of the plane of one the polygons from any
three of its vertices. We can then successively test the values of all the
vertices of the other in the this equation. If we get the same sign for each
vertex, then the second polygon does not intersect the first. Note that we
must also test if the first polygon intersects the second by forming the
8.13 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
3
8.15 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.
8.16 If we look at all the paths generated by flood fill they visit each
square once. Thus if we were to draw lines between these paths we would
have a maze. Alternately, we can start with cells in which all walls are
8.17 Flood fill should work with arbitrary closed areas. In practice, we can
8.18 Suppose that the equation of the edge is y=mx +hwhere mand h
are determined from (x1, y1) and (x2, y2). For any change ∆yin y, the
corresponding change in xmust be ∆x=1
m∆y. Thus if (xi, yi) is the
8.19 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
4
8.20 Consider scan line algorithms. Each vertex has a priority, so we can
think of all the intersections of edges of all the polygons with scan lines
generating a set of (x, y, p) triplets where pis the priority of a polygon. We
8.21 Although each pixel uses five rays, the total number of rays has only
8.22 As long as the radius is less than 0.5, the circle is entirely within the
8.23 A mathematical answer can be investigated using the notion of
reconstruction of a function from its samples (see Chapter 7). However, a
8.24 The jaggedness we see in rasterized lines is caused by having to choose
a single pixel for each x (or y). A line of one pixel width actually covers
more than one pixel for each x (or y), something that an antialiasing
algorithm takes care of. In a CRT, if the beam is not well focussed, the
8.25 We want klevels between Imin and Imax that are distributed
Imin )1
5
8.26 We can use a simple threshold test where the threshold changes each
time based on the random number generator. Thus, for each pixel we
compare it to a random number between 0 and 1. If the pixel exceeds the
8.27 If there are very few levels, we cannot display a gradual change in
brightness. Instead the viewer will see steps of intensity. A simple rule of
thumb 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
8.28 Consider the trapezoid formed by the an edge and the xaxis or the
four points (xi, yi),(xi+1),(xi,0),and (xi+1,0).The area of this trapezoid
is 1
2
yi+1+yi
xi+1−xi. Suppose that all the yiare positive (an assumption which is
6