\input header
\input epsf

\title{Research topics}

While the opportunities for discovering interesting new things about spline surfaces are probably relatively limited, subdivision surfaces are at a stage where new ideas and possible directions of development appear round every corner.

When this is combined with the imminence of wide commercial exploitation, it makes for exciting times.

This note outlines a few of the many many open questions which are open for exploration.
They range from trivial `sort that out in an afternoon' details, to very large new fields in their own right.   I have included just five here, chosen to span that range.  There are many, many more.

 \pop How does the type of a subdivision depend on the arity~?

 \pop Is it possible to define a pure dual interpolating scheme~?

 \pop How can we analyse artifacts, with a view to defining artifact-free schemes~?

 \pop Can we use non-stationarity to improve the behaviour~?

 \pop What about using local refinements instead of global ones~?



 \section {How does the type of a subdivision depend on the arity~?}

When looking at the generation of all possible surface refinement schemes, we saw that it was convenient to take the possible types in pairs,

- quad primal/both

- quad dual/neither

- triangle primal/both

- hexagon dual/both

 \noindent and that the type within a pair was determined by the two numbers constituting the arity.

The question is to find the exact relation between the type and the arity.

I suspect that finding the facts here will take just a few minutes with graph paper for the quad grids, and with triangle graph paper for the other two cases.  Making a precise articulation of the variables and of the relationship might take rather longer.

This is not an issue worthy of documentation, since the reader of any paper reporting the result would probably be able to find the facts more quickly directly than by reading the paper.




 \section {Is it possible to define a pure dual interpolating scheme~?}

This is the question set as an essay question this year.

It is trivial to define primal and both schemes where the limit curve interpolates the original vertices  of the defining polygon.  All that is necessary is to set the coefficient which relates an old vertex to the new one at the `same' position to unity, and then ensure constant precision.

\filbreak

It is not quite so easy to define interpolating schemes which are neither primal nor dual, but the property that, if two steps of such a scheme are combined into one, a `both' scheme results, leads to a set of quadratic equations between the coefficients which can be used to construct such schemes.

\filbreak

The remaining class of schemes contains those which are dual, so that both vetices and edges of the original polygon map into edges of the refined polygon.  Can we make an interpolating one~?

\filbreak

The constructive approach here needs to take one step of the scheme, and then determine the limit point of the middle of the edge corresponding to an initial vertex, using the eigenvectors of the unit eigenvalue component.

\filbreak

I believe I have a proof of impossibility for the arity=2 case, based on support arguments which do not involve any detailed solution of equations, but these do not obviously generalise to higher arities.

\filbreak

So the situation is unknown.  Maybe dual interpolating schemes are impossible for all arities; maybe they are impossible for binary schemes but examples can be constructed for higher arities; maybe my conjecture is wrong and a counterexample can be found.  Maybe it proves to be very difficult indeed to determine the possibility or not: no proofs, but no counterexamples either.

Whichever way the facts turn out, there is a result of interest here, which would be well worthy of publication as a 4-page short note.

I think that finding the facts is a matter of a week or less of concentrated work - just right for an essay question.


 \section {How can we analyse artifacts, with a view to defining artifact-free schemes~?}

There are two openings here.

 \firstsubsection{Applying bivariate Fourier analysis to longitudinal and lateral artifacts}

This requires an activity which is clearly visible.  The task is one of applying a well-understood standard technique to some examples and then inducing conclusions and generalisations from those examples.  Finally, maybe, checking against a few more complex examples.

\filbreak

It may also be that generating function analysis can give some clues as to the longitudinal artifacts, as it did (unexpectedly) to the lateral ones.

\filbreak

I would regard this exploration as a good first-term project for a PhD student, by which to learn the nuts and bolts of subdivision, but also to produce some new learning on the way.

 \subsection{Finding some way of understanding and predicting rotational artifacts}

Again the immediate task is an obvious one, of applying fourier analysis to the known bad configurations and seeing what predictions it makes.   There is, however, more creativity required in the finding of a range of bad configurations, and in the invention of new rules for interacting extraordinary points which help to minimise the effects.

\filbreak

This will lead to ad hoc knowledge, and a deeper understanding can only start to be sought once that basis is established.  I do not know where this question might lead, nor whether it is a one-term project or a three-year one.  I don't think it is longer than that.  I do know that even the ad hoc results would be valued by the people building subdivision software systems.


 \section {Can we use non-stationarity to improve the behaviour~?}

In the univariate case the answer is definitely yes.  As an example, we can take one of the definitions of the 4-pt scheme, which is that each new point is chosen so that the 3-pt estimate of 2nd derivative at the new point is the mean of the 3-pt estimates of 2nd derivative at the neighbouring old vertices.  This can be slightly modified so that the new vetex goes at the place where the 3-pt estimate of curvature (the reciprocal of the radius of the circle through three points) is the mean of the estimates at the neighbouring old vertices.

\filbreak

This scheme has two obvious properties.  The first is that if it is given points lying on a circle that property will be invariant under subdivision, so that the limit curve will be the circle itself, giving good artifact properties.

\filbreak

The second is that if the points are equally distributed round the circle the scheme itself will tend towards the 4-pt scheme as the curvature and 2nd derivative get to be more nearly the same thing.

In fact it is also possible to choose the new point so that any unevenness of distribution also dies away as refinement proceeds, so that the limit of the scheme is always the 4-pt one.

\filbreak

There is a plausible analogue of this in the bivariate case, which deserves exploration.

Take any of the interpolating schemes (Butterfly, Guskov, ...) which has just one kind of new point, and articulate the stencil for that point in terms of a mean of some 2nd derivatives.  This effectively means taking the laplacian of some scalar measure.

There is a generalisation to intrinsic derivatives (already explored in the smoothing context by Leif Kobbelt's team) which uses the Laplace-Beltrami operator on the mean curvature, $H$.
$$\Delta_B(H) = 0$$

\filbreak

If the analogy with the univariate case is reliable, which is not guaranteed, the resulting scheme should converge towards the original scheme as refinement proceeds, thus saving us the job of analysing its convergence and continuity properties.   It should also generate cylinders and spheres exactly if the original vertices lay on one of those surfaces.  Note that this is a local property because of the local support properties, and so the only artifacts arising would be at places where the original vertices were sampled from surfaces with transitions between such surfaces (tangency lines).

There may well be other approaches, and so a project checking this construction might well be just the first opening up of a complete new technology.


 \section {What about using local refinements instead of global ones~?}

We have approached the subject in terms of refinements which apply everywhere to the same level.  Interrogations may go down to different levels in different regions, but the approximated answers need to be sewn together in a way which heals the glitches.

In fact the $\sqrt2$ and $\sqrt3$ schemes do lend themselves to graded meshing, even they need fix-ups.

The graphics community writing games in which the player flies through a very large complicated terrain have developed techniques whereby nearby regions are rendered at the fiull resolution of the model, while in regions further away a much coarser version is sent to the graphics card.  There is sound mathematics for this, called {\bf Progressive Meshing}.  This is a well developed technology which ensures complete compatibility between the parts of the mesh being rendered at different resolutions.  In fact there is also careful smoothing in time, as well, so that the changes in resolution as you fly towards a previously coarse region are made smoothly and invisibly.

Current refinement techniques do not give compatible approximations at different levels, and there is not any clearly defined procedure for inserting individual new vertices.

There is, however, a theory called {\sl Quasi-crystals}, which can define grids with rotational instead of translational symmetries.  This theory has a very natural way of defining a sequential refinement, in which the unit operation is the adding of just one extra vertex.

Although the grids thus defined look pretty random, they have well-distributed densities, and they have a sufficiently rigid structure underneath to support a lot of mathematical analysis.  I have seen them applied with good effect to the progressive transmission of images across the Web.

There is a clear opening to combine these ideas to give local refinement where it is necessary while retaining coherence between the approximations.

BUT the existing theory is essentially of functions.  It needs to be extended to cover manifolds.  We also need some idea as to what the equivalent of an extraordinary point is in a grid which looks random but isn't.

This is a question which could open up a whole new direction for subdivision, and provide research careers for whole groups of academics.




\end


