CS 417 Homework 3 Solutions
------------------------------------------------------------------------
Problem 1
Limiting geometry rate for separate triangles:
12 layers * 70K tris/layer * 3 verts/triangle = 2520K verts.
136M verts/second / 2520K verts = 53.97 frames/second.
Limiting geometry rate for tstrips:
12 layers * 70K tris/layer * 10 verts / 8 tris = 1050K verts.
136M verts/second / 1050K verts = 129.52 frames/second.
Limiting fill rates:
800x600: 12 layers * 800 * 600 frags/layer = 5760K frags.
1200M frags/second / 5760K frags = 208.33 frames/second.
1024x768: 12 layers * 1024 * 768 frags/layer = 9437184 frags.
1200M frags/second / 9437184 frags = 127.16 frames/second.
1280x1024: 12 layers * 1280 * 1024 frags/layer = 15728640 frags.
1200M frags/second / 15728640 frags = 76.29 frames/second.
1600x1200: 12 layers * 1600 * 1200 frags/layer = 23040K frags.
1200M frags/second / 23040K frags = 52.08 frames/second.
1.1
Total rate is min(geom rate, fill rate):
800x600: min(53.97, 208.33) = 53.97 frames/second.
1024x768: min(53.97, 127.16) = 53.97 frames/second.
1280x1024: min(53.97, 76.29) = 53.97 frames/second.
1600x1200: min(53.97, 52.08) = 52.08 frames/second.
1.2.
Total rate is min(geom rate, fill rate):
800x600: min(129.52, 208.33) = 129.52 frames/second.
1024x768: min(129.52, 127.16) = 127.16 frames/second.
1280x1024: min(129.52, 76.29) = 76.29 frames/second.
1600x1200: min(129.52, 52.08) = 52.08 frames/second.
------------------------------------------------------------------------
Problem 2
2.1.
Fourth degree.
2.2.
p(t) = at^4 + bt^3 + ct^2 + dt + e
p'(t) = 4at^3 + 3bt^2 + 2ct + d
p(0) = e = p0
p'(0) = d = v0
p(0.5) = a/16 + b/8 + c/4 + d/2 + e = p0.5
p(1) = a + b + c + d + e = p1
p'(1) = 4a + 3b + 2c + d = v1
Let A = [ 0 0 0 0 1 ]
[ 0 0 0 1 0 ]
[ 1 2 4 8 16 ]
[ 1 1 1 1 1 ]
[ 4 3 2 1 0 ]
x = [a]
[b]
[c]
[d]
[e]
b = [ p0 ]
[ v0 ]
[16p0.5]
[ p1 ]
[ v1 ]
Solving Ax = b will yield:
a = -8p0 + -2v0 + 16p0.5 + -8p1 + 2v1
b = 18p0 + 5v0 + -32p0.5 + 14p1 + -3v1
c = -11p0 + -4v0 + 16p0.5 + -5p1 + v1
d = v0
e = p0
Matrix equation
p(t) = [t^4 t^3 t^2 t 1] [ -8 -2 16 -8 2][ p0 ]
[ 18 5 -32 14 -3][ v0 ]
[-11 -4 16 -5 1][p0.5]
[ 0 1 0 0 0][ p1 ]
[ 1 0 0 0 0][ v1 ]
2.3.
It moves the opposite way.
2.4.
p(t) = at^5 + bt^4 + ct^3 + dt^2 + et + f
p'(t) = 5at^4 + 4bt^3 + 3ct^2 + 2dt + e
p(0) = f = p0
p'(0) = e = v0
p(0.5) = a/32 + b/16 + c/8 + d/4 + e/2 + f = p0.5
p'(0.5) = 5a/16 + 4b/8 + 3c/4 + d + e = v0.5
p(1) = a + b + c + d + e + f = p1
p'(1) = 5a + 4b + 3c + 2d + e = v1
Let A = [ 0 0 0 0 0 1 ]
[ 0 0 0 0 1 0 ]
[ 1 2 4 8 16 32 ]
[ 5 8 12 16 16 0 ]
[ 1 1 1 1 1 1 ]
[ 5 4 3 2 1 0 ]
x = [a]
[b]
[c]
[d]
[e]
b = [ p0 ]
[ v0 ]
[32p0.5]
[16v0.5]
[ p1 ]
[ v1 ]
Solving Ax = b will yield:
a = 24p0 + 4v0 + 16v0.5 + + -24p1 + 4v1
b = -103/2p0 + -35/4v0 + 8p0.5 + -32v0.5 + 87/2p1 + -27/4v1
c = 33p0 + 13/2v0 + -16p0.5 + 16v0.5 + -17p1 + 5/2v1
d = -13/2p0 + -11/4v0 + 8p0.5 + + -3/2p1 + 1/4v1
e = v0
f = p0
Matrix equation
p(t) = [t^5 t^4 t^3 t^2 t 1] [ 24 4 16 0 -24 4 ][ p0 ]
[ -68 -12 16 -40 52 -8 ][ v0 ]
[ 66 13 -32 32 -34 5 ][p0.5]
[ -23 -6 16 -8 7 -1 ][v0.5]
[ 0 1 0 0 0 0 ][ p1 ]
[ 1 0 0 0 0 0 ][ v1 ]
2.5.
It moves in the same direction, a bit less than in part 2.3.
2.6.
a. In Hermite spline, the first endpoint doesn't affect the second
segment, so it has greater locality of control.
b. The Hermite spline is only guaranteed to have C^1 continuity at the join
point. The new spline has C^inf continuity because it is a single
polynomial across the whole interval.
[C^inf (the "inf" is supposed to stand for an infinity symbol) means that
all the derivatives (i.e., f, f', f'', f''', f'''', ...) exist and are
continuous. All polynomials are C^inf -- the first few derivatives are
other polynomials, and the rest are zero.]
------------------------------------------------------------------------
Problem 3
3.1
First, a symmetry argument: There is nothing asymmetrical about the problem
statement (continuity of derivatives and identical zero boundary conditions at
both ends), so the solution must be symmetrical about the center. This means
that p0(t) = p3(1-t) and p1(t) = p2(1-t).
By C^2 condition at t = 0, p0(0) = p0'(0) = p0''(0) = 0
Therefore d0 = c0 = b0 = 0 and p0(x) = a0x^3
Therefore p1(0) = p0(1) = a0 = d1
p1'(0) = p0'(1) = 3*a0 = c1
p1''(0) = p0''(1) = 6*a0 = 2*b1 => b1 = 3*a0
Therefore p1(x) = a1 x^3 + 3*a0 x^2 + 3*a0 x + a0
By symmetry, p1'(1) = 0 = 3*a1 + 9*a0 => a1 = -3*a0
so p1(x) = -3*a0 x^3 + 3*a0 x^2 + 3*a0 x + a0
by summing-to-one property, p1(1) + 2*p0(1) = 1
4*a0 + 2*a0 = 1 => a0 = 1/6
This gives us the last two columns of the matrix as
(1/6) [-3 3 3 1; 1 0 0 0]'.
The other two can be had by expanding p3(t) = p0(1-t) and
p2(t) = p1(1-t):
p3(t) = (1/6)(1-t)^3 = (1/6)(-t^3 + 3t^2 - 3t + 1)
p2(t) = (1/6)(-3(1-t)^3 + 3(1-t)^2 + 3(1-t) + 1)
= (1/6)(3t^3 - 9t^2 + 9t - 3
+ 3t^2 - 6t + 3
- 3t + 3
+ 1)
= (1/6)(3t^3 - 6t^2 + 4)
This gives the first two columns as (1/6) [-1 3 -3 1; 3 -6 0 4]'.
Note that the columns are in the order p3, p2, p1, p0 because when we look at
the four control points that affect a given segment, we find that for the
first (lowest numbered) control point it's the rightmost edge (p3) of the
basis function that touches the segment whereas for the last (highest
numbered) control point it's the leftmost edge (p0) of the basis function that
touches the segment.
3.2
Since we just derived it from a fully constrained set of equations, the cubic
B-spline is the unique cubic basis spline that has support 4 and continuity
C^2.
3.3
An order-d B-spline has d segments and is of degree d-1 -- hence d^2
coefficients define it. C^(d-2) continuity at d+1 places is (d-1)(d+1) = d^2
- 1 constraints. The last constraint comes from summing to one.
------------------------------------------------------------------------
Problem 4
4.1. Always
4.2. Not always
4.3. Always
4.4. Always
4.5. Always
4.6. Not Always
4.7. Always
4.8. Always
4.9. Not Always
4.10. Always
4.11. Always
4.12. Not Always
There was some confusion in class about the last two. According to H&B a
"z-axis shear" is one that is proportional to the z coordinate, changing only
x and y but preserving z. It's not a shear parallel to the z axis as you
might think from the name. So translation along z does not preserve the
behavior of the shear, but translation perpendicular to z commutes with it
just fine (because it does not change the z coordinate).