Quasi-Interpolated Surface Pasting

What is surface pasting?

Surface pasting is a surface composition technique that is used to construct surfaces with varying levels of detail. A feature is placed on top of an existing surface to provide a region of increased detail. The base surface can be a simple tensor product surface or can be a composite surface produced by previous surface pasting operations. After pasting, the base surface remains unchanged and the feature surface combines characteristics of its unpasted shape and the underlying surface. See the Surface Pasting page for more details on how surface pasting works, or see Section 2.5 of my thesis.

What's wrong with surface pasting?

Surface pasting is an approximation technique, and so does not have guaranteed continuity between the base surface and the pasted feature. It is quite common to construct composite surfaces that have pronounced C¹ discontinuities, or even unsightly gaps, between the feature and base. These discontinuities and gaps can be reduced to any desired tolerance by refining the feature surface, but at a cost. When a feature surface is refined, the number of control points is raised, dramatically increasing the cost of the pasting operation. If the feature surface is refined too much, the performance of the pasting editor suffers greatly.

Discontinuities in a pasted surface.

How do we fix it?

The poor continuity between the base and the feature could (in theory, at least) be reduced by changing the position of the control points in only a few of the outermost rings of the feature's control points. The interior control points contribute to the overall shape of the pasted feature, but do nothing to influence the position and cross boundary derivatives around the boundary. I adapted a curve approximation technique called quasi-interpolation and used it to set the boundary control points. (Quasi-interpolation was originally developed by de Boor and Fix, but I based my work on an extended method due to Lyche and Schumaker. In fact, Lyche suggested using quasi-interpolation for this task.)

How did it work?

It worked pretty well, actually. I implemented two techniques: Q⁰-pasting to reduce only the C⁰ discontinuities between the feature and the base, and Q¹-pasting to reduce both the C⁰ and C¹ discontinuities. Both methods gave good results and, due to careful optimization of the quasi-interpolation operators used, did not significantly increase the cost of the pasting operation.

Theoretical stuff

I was able to show that the error between the feature boundary had the best possible order. For example, if a bicubic tensor-product surface is pasted on a bicubic base, we achieve O(h³) error convergence in the position of a Q⁰-pasted surface when the control point density of the pasted surface is increased. This has been confirmed by empirical test. In contrast, the error in a standard pasted surface decreases as O(h²), according to empirical tests.

Empirical error values

The theoretical results are nice, but it's all for naught if the surfaces don't actually look good. The examples below are of the same surfaces pasted using standard pasting, Q⁰-pasting, and Q¹-pasting, as noted. You can see that the quasi-pasted surfaces looked much better, even though they used the same number of control points.

standard pasted surface

Q0-pasted surface

Q1-pasted surface

A Caveat

I mentioned that both the methods that I used produced good results, but there was one small problem. The Q⁰-pasting method reduced the C⁰ discontinuity, it produced composite surfaces with high C¹ discontinuities, as shown below:

standard pasted surface

Q0-pasted surface

Q1-pasted surface

A note on speed

Quasi-pasting produces higher-quality composite surfaces, but that's not such a big deal... it's easy to get higher quality surfaces if you sacrifice speed of evaluation. However, quasi-interpolated surface pasting is not much slower than standard surface pasting when applied to models with the same number of control points. On the samples tested, Q⁰-pasting used about 10% more affine combinations to place the feature control points than did standard pasting, and Q¹-pasting actually used fewer affine combinations than standard pasting, with the advantage increasing with the size of the feature.

The main issue, however, is not how much work is required to paste surfaces with the same number of control points, but how much work is required to construct surfaces that have a particular quality. The features in the examples shown on this page have 81 control points, arranged in a 9x9 square. As a test, I refined the feature surface in the standard pasting case until its boundary error values came close to those obtained with the quasi-interpolated surface pasting. Here's what I found:

As you can see, the standard pasted surface has to have the number of its control points increased by a factor of 9 before its C⁰-discontinuities surpassed those of the Q¹-pasted surface, and the C¹ discontinuities were still much worse. Combining this with the cost savings per boundary control point placed with Q¹-pasting, and we get about a tenfold speedup when using Q¹-pasting compared to standard surface pasting.

Additional Resources

Additional information on Quasi-Interpolated Surface Pasting can be found here:

• Better Pasting via Quasi-Interpolation, Blair Conrad and Stephen Mann, in Curve and Surface Design: Saint-Malo 1999, Vanderbilt University Press, pages 27-36.
• Better Pasting Through Quasi-Interpolation, Blair Conrad, Masters Thesis, University of Waterloo
• A Power Point poster that was presented at Eurographics 1999.