CPSC 645/VIZA 675 – Geometric Modeling
Homework
1
due 2/24/09
You may write or use a simple computer program to help you
with the computational parts of this problem or use a computer algebra package
for simple operations (e.g.
to multiply polynomials or solve a matrix).
However, you should show the setup and all your work for each problem. Many of these questions attempt to come to
the same conclusion using different methods. Therefore, without showing your work, little
or no credit may be given for a given question.
1. [20 points] We have seen
that if a point x is represented as a
convex combination of another set of points (i.e.;
where and ) that x lies in
the convex hull of the points pi. Prove that this statement is true. (Hint, use the recursive definition of the convex
hull as a union of lines.)
2. [30 points] Assume that
you would like to control the position of a camera for an animation. You know the starting and ending positions of
the camera as well as two intermediate positions of the camera and the time
that the camera should be at each of those two points.
a) [3 points] What degree polynomial curve would you need to
interpolate the data?
b) [6 points] Use Lagrange polynomials to build the general
form of the interpolated curve.
c) [6 points] Assume for the remainder of these questions
that the time interval of the camera from
beginning to end is in the range [0,1] and that the two intermediate positions
are equally spaced in terms of time. Use Vandermonde matrices to derive the
interpolating polynomial (be sure to show your work!!!).
d) [6 points] Use Neville’s algorithm to evaluate the
interpolating polynomial at t=.5 in general
form (you should obtain a weighted combination of unknown points).
e) [3 points] Furthermore, assume for the remainder of these
questions that we also know the velocity of the camera at the two end-points. What degree polynomial would you use to
interpolate these parameters?
f) [6 points] Write the interpolating polynomial in general
form (in terms of the unknown points and velocities) for this curve.
3. [40 points] Assume we
have a 2D parametric curve with control points:
Time Points
0
(0,0)
.3 (1,4)
.7 (2,0)
.9 (1,2)
1 (3,-1)
a) [6 points] Use the Vandermonde matrix to construct the
interpolating polynomial for this data.
b) [6 points] Build a change of basis matrix to convert this
polynomial to a Bezier curve and give the control points for this Bezier curve.
c) [5 points] Compute the direction of the derivative of
this curve at its two end-points using the Bezier control points derived above.
d) [6 points] Compute the direction of the derivative at t=.5
using the Bezier control points.
e) [5 points] Compute the integral of the x and y coordinates of the curve using the Bezier basis from t=0 to t=1.
f) [6 points] Raise the degree of the Bezier curve by 1 and
give the control points for this curve.
g) [6 points] Subdivide the curve at t=0.25
and provide the control points for the two subdivided Bezier curves.
4. [10 points].
Bezier curves are formed by taking a linear interpolation between pairs of
points, i.e.
weighting them by 1-t and t.
Consider if a different function, f(t), were used, where f(0)=0,
f(1)=1, and weighting was by 1-f(t) and f(t).
[That is, the standard interpolation used in Bezier curves is f(t)=t]
For the following properties of Bezier curves, briefly state whether you would
expect the property would be maintained, and (very briefly) why.
If it would be maintained for some f(t), give a brief description of
what characteristics of f would make it hold:
- Affine invariance
- Convex Hull property
- Interpolates endpoints
- Variation diminishing property
- Starting/ending derivatives can be found by difference of
endpoints