Suggestions for Projects

We are collecting a number of possible projects here for students to pick from. While you are encouraged to dream up your own you can also pick one off of this list. For lack of a better systemization we have grouped the projects into those which are primarily implementation, i.e., write code for a small interactive application, and those which are primarily theory oriented, e.g., study the smoothness of a class of subdivision schemes. The latter may at times involve small amounts of implementation along the lines of writing a Maple program to manipulate various Fourier transform expressions of subdivision matrices, for example.

Note that his list is incomplete and we are adding to it as we go along.

Implementation Projects

Loop's scheme

Loop's scheme is a subdivision method for surfaces which will work for arbitrary triangular meshes and which generalizes quartic triangular splines. The main references on this are Loop's thesis from Utah, which we have in hardcopy only and a recent Siggraph paper, ``Piecewise Smooth Surface Reconstruction,'' by Hugues Hoppe et al., Siggraph 1994, pages 295-305.

Peters' C¹ surface scheme

Jörg Peters has recently described a scheme for arbitrary topology meshes which results in a globally C¹ by generating a number of Bezier patches. The scheme is not as simple as Loop's scheme for example, but it results in a finite set of patches, while other generatlization such as Loop's scheme only produce a surface in the subdivision limit around extraordinary points. In fact surprisingly little is known about the smoothness around such extraordinary points. An intriguing possibility of Peters' scheme is the fact that it allows for the incorporation of interpolation constraints. This can possibly be turned into an interpolating subdivision scheme for arbitrary topology meshes. The relevant papers are online. The C¹ algorithm is described in ``C¹ Surfaces Splines'' and a somewhat restricted but much simpler version is described in ``Smoothing Polyhedra Made Easy''.

Catmull-Clark and Doo-Sabin schemes

These schemes generalize quadratic and cubic splines over arbitary topology meshes by modifying the schemes around extraordinary points. The schemes were the first introduced and are classic. The are simple to implement and result in surfaces which are C¹ and C² everywhere except at extraordinary points. We have hardcopy of the relevant articles availalbe.

Butterfly scheme

This is the only scheme which is interpolating by design. It is based on work by Dyn/Gregory/Levin and we have hardcopy of the article. It works for triangular meshes. If these are regular the limiting surface will be C¹. For irregular vertices this is not true and there are a number of possible modifications that would be interesting to explore.

Kobbelt's scheme

This scheme is very similar to the Butterfly scheme except it works for meshes which have quadrilateral faces rather than triangular ones. The behaviour at extraordinary points appears nice, but no proof is yet given for this. The relevant paper is ``Interpolatory Subdivision on Open Quadrilateral Nets with Arbitrary Topology''.

Some general remarks

Any of the above could be oriented more towards theory by focusing on such aspects as smoothness of the limit surfaces near extraodinary points. This typically involves computing various Fourier transforms of subdivision matrices and examining the eigen values of these. In some cases this can lead to suggested modifications. Often there are degrees of freedom left and an interesting exploration would be to see how the resulting functions change as these degrees of freedom get manipulated. Such an exploration could easily be done in Maple or Matlab for those how prefer to stick with such tools.

Theory Projects

Deslauriers Dubuc interpolating subdivision

This is a classic scheme for the real line which is interpolating. The paper describes how to compute the exact Hölder smoothness of the resulting limit functions. Build a Maple (or Mathematica) toolbox to compute this smoothness for various order schemes. We have hardcopy of the relevant paper.

Variational design of interpolating subdivisions

Leif Kobbelt describes and interesting idea: instead of using polynomials to do interpolating subdivision compute new points by solving a discrete variational problem. This could easily be implemented in Matlab or Maple and it would be interesting to see just what kinds of curves one can build with this.

Differentiating a subdivision curve

There are a number of observations relating differecing of control points and applying a somewhat modified scheme to the difference coefficients, to the derivative of a given scheme. For example, differentiating the interpolating schemes of Deslauriers-Dubuc leads to the average interpolating functions of Donoho. This observation generalizes. A nice project would be to pick one family of curves, e.g., B-spline curves and work out the various derivatives in the irrgularly spaced knot setting. Again this is mostly pencil and paper and some Maple/Mathematica work.