Research Interests

Last Updated: November 26, 1997
An up-to-date Research Statement
The following is a slightly older, more detailed description of my research.

Problem statement

The primary thrust of my research is investigating triangular surface interpolation techniques. That is, given a triangulated set of points in 3 space, find a smooth surface that interpolates these points. In this problem, we are interested in parametric surfaces (ie, F(u) = (x(u), y(u), z(u)). This problem is more difficult than the related functional problem where we are searching for surfaces of the form z=F(x,y).

At issue is the question of smoothness. Previously, tangent plane continuity was used as the smoothness criteria. Piecewise polynomial (or rational polynomial) surface patches were fit to the data so that adjacent patches were tangent plane continous along their common boundary. Unfortunately, surfaces constructed in this fashion have poor visual shape despite meeting the mathematical smoothness constraints. Curvature plots show that curvature in unequally distributed across these patches, resulting in surfaces that look like smooth polyhedra (at best).

One class of techniques that have been used to construct better looking surfaces are global optimization techniques. These techniques are global in the sense that all the data is considered when constructing each patch (this is in constrast to the more common definition of global optimization meaning finding global minimums instead of local minimums).

While global optimization techniques provide far better surfaces, this improvement comes at a high computational price. Even for small numbers of surface patches, these techniques require hours of CPU time to compute the surface. I am currently looking at local techniques that create surfaces with better shape. There are several thrusts to my research, but all seem to indicate that lower degree surface patches (having fewer degrees of freedom) more naturally give high quality surfaces.

The Cubic Interpolant

One technique I developed that has resulted in higher quality surfaces is the cubic interpolant. This is a cubic surface element that matches second order data prescribed at the data points (second order == position, first derivatives, second derivatives). In order to use this patch, I relaxed the continuity conditions from tangent plane continuity to approximate continuity (ie, where the surface normals of two patches along their common boundaries are nearly equal). Despite having lower order continuity, the resulting surfaces cubic interpolant appear far smoother than the corresponding surfaces contructed by the C1 schemes.

To construct cubic interpolant surfaces we need second order data at the vertices. When approximating known functions, this data is reasonable to obtain. However, when fitting surfaces to scattered data, we are normally lacking both the first and second derivatives at the data points. Thus, one of the topics I am researching are methods for estimating this derivative information from data points containing only positional information.

Approximate Continuity

A second research topic to come from my cubic interpolant research is that of approximate continuity. More formally, two patches are said to join with approximate continous with tolerance e if the angle between the surface normals of the two patches at any point along the common boundary is less than e.

In my work the the cubic interpolant, I worked backwards to produce approximately continuous surfaces: I would

  1. sample a known function,
  2. fit cubic interpolant patches to the data,
  3. test the boundaries to see if the continuity condition was met.
    If not met, refine the sampling and repeat.
I verified the condition numerically by sampling the boundary at multiple locations and seeing if the condition was met at these sample points.

Part of my research involves developing a better test for approximate continuity. For cubic patches, we can determine the maximum discontinuity by finding the roots of a degree 18 polynomial. What I would like is to find a less expensive technique that is accurate to a prescribed tolerance.

With a slightly different thrust, I am trying to develop a construction of approximately continuous surace patches. That is, given that we want our patches to interpolate certain data and meet with approximate continuity, how do we build patches that meet these constraints?

Surface Quality

All of the above ties into an idea of surface quality. Essentially, as humans we can recognize surfaces having good shape when we see them. Unfortunately, this idea of "good shape" is hard to define mathematically. What is clear is that it is a metric of the entire surface patch (and probably the entire surface). This is why tangent plane continuous techniques fail to produce surfaces of good shape: they are only a metric applied to a differential area along the boundaries between adjacent patches.

Global optimization techniques try to minimize energy functions over an entire surface patch (or patches). These techniques are slow because it is expensive to evaluate these functionals (and since you have to vary parameters to minimize this value, you have to evaluate your functional many times).

In addition to the ideas mentioned in the earlier sections, my interest in shape also deals with how to test the quality of surface patches. Commonly used techniques include shaded images, curvature plots, reflections lines, and isophotes. But it is unclear what metrics should be used, and indeed, different applications probably require different metrics.