CS 779 Final Project

Variational Interpolation

Eugene Greene

Topics

1. Variational Interpolation

   Given a set of points (potentially with associated normals), we want a surface that interpolates the points and normals. In particular, we want a surface defined by an implicit function defined by F(X) = 0. Variational interpolation is a method to derive such a surface. This technique seeks to minimize a sum of partial derivatives of F, and in the process reduces the bending of the implicitly defined surface.

   In addition to providing points on the surface (for which the height of F is 0), we can provide points off the surface, along with their corresponding non-zero height values.

2. Modelling techniques using variational interpolation

   I implemented a modelling tool including various techniques relying on the variational interpolation method. This is based on Turk and O'Brien's work.

3. Shape transformation using d-dimensional variational interpolation

   I also implemented a tool that can transform a shape between any of a given set of shapes.

Implementation

1. D-dimensional variational interpolation

   The variational interpolation code that underlies all of the functionality is general-purpose. Any (non-degenerate) set of d-dimensional control points and corresponding function height values can be input. Any implementation of a basis function can be provided to be used by the interpolation. I implemented the thin plate spline basis function Φ (r) = r² ln r, and the cubic basis function Φ (r) = r³.

2. Modelling tools
   1. Function height adjustment

      Making a control point's height positive or negative will push the surface out or in respectively.

      Height = 0	Height = 1	Height = -1

   2. Control point translation

      The user can move control points anywhere. If the control point's height is zero, this is "direct manipulation".

   3. Normal rotation

      A surface "normal" can be specified for a control point. It is just a copy of the control point, perturbed slightly in the direction of the normal, with a small non-zero height value. This will not actually be the surface normal. It just helps gives some direction to the surface.

      Original normal	Bottom normal rotated

   4. Control point insertion and deletion

      Control points for a surface can be added on that surface or on any surface in the scene. If the height value of the new point is zero, and it is placed on the surface, then the surface will not change. Control points can also be removed. This will almost certainly change the surface.

   5. Surface blending

      Given the control points for two or more surfaces, they can be merged so that one new surface is formed. Any control points inside any of the other surfaces will be removed. The new surface will be a blending of the previous surfaces (the surfaces will intersect with smooth joins).

      Original surfaces	Blended surfaces

Extras

1. Shape transformation

   Given (the control points for) n different shapes, we can place each shape on a vertex of a (n-1)-simplex. Travelling through this simplex, we can transform one shape to another, going through intermediate forms that are combinations of the shapes. We can evaluate the surface at any point in the simplex; the following are seven snapshots showing intermediate forms between three shapes.

   Shape 1	Between 1, 2	Shape 2
   Between 1, 3	Between 1, 2, 3	Between 2, 3
   	Shape 3

2. Influence radius with falloff

   In order to help prevent the surface from "exploding", I allow the user to choose a radius of influence for point translation and height manipulation. The effect of the operation is full at the selected control point, and affects nearby control points as well, with the effect falling off to zero at the specified radius.

   Original surface	Translated points

3. Experimentation

   I ran the variational interpolation method along with the Nielson patch scheme. I used three sets of points and normals. Both schemes output a set of surface points and corresponding normals. The following table shows the resulting surfaces and construction times. The construction time is the average time in seconds required to calculate each vertex and normal pair.

   Set	Tetrahedron	Torus	Head
   Size	4 points, 4 normals	32 points, 32 normals	506 points, 506 normals
   Variational interpolation surface
   Nielson surface
   Nielson construction time	0.0000811450	0.0000942133	0.0000684967
   Variational interpolation construction time	0.0000782731	0.0005136806	0.0325281879

   It appears as if the Nielson scheme surfaces result in some flat areas and some large curvature areas, while the variational interpolation scheme has less variation in its curvature.

   For variational interpolation, the amortized time per output point becomes worse as the number of input points increases.

Observations

Although variational interpolation can provide surfaces with small curvature, there are a couple of drawbacks besides the potential construction time.

• There is no way to provide desired connectivity information. If we do not provide enough points, the topology of the generated surface may be undesirable.

  Too few points	Enough points

• The tool automatically provides a "boundary". This is just a set of control points outside the surface with relatively large (negative) height values. The boundary serves to push the surface inwards. If there was no boundary, the surface could relatively easily "explode" beyond the existing control points. This results from the minimization process, which minimizes derivatives, but says nothing about surface size.

References

1. Baerentzen, Andreas. Public Domain Polygonizer. 2003. http://www.unchainedgeometry.com/jbloom/papers.html.
2. Duchon, Jean. 1977. Splines Minimizing Rotation-Invariant Semi-Norms in Sobolev Spaces. Constructive Theory of Functions of Several Variables, Lecture Notes in Mathematics. Springer-Verlag. 1977, 85-100.
3. Savchenko, V. V., Pasko, A. A., Okunev, O. G., and Kunni, T. L. 1995. Function representation of solids reconstructed from scattered surface points and contours. Computer Graphics Forum 14, 4 (Oct. 1995), 181-188.
4. Turk, G. and O'Brien, J. F. 2002. Modelling with implicit surfaces that interpolate. ACM Trans. Graph. 21, 4 (Oct. 2002), 855-873.
5. Turk, G. and O'Brien, J. F. 2005. Shape transformation using variational implicit functions. In ACM SIGGRAPH 2005 Courses (Los Angeles, California, July 31 - August 04, 2005). J. Fujii, Ed. SIGGRAPH '05. ACM, New York, NY, 13.