CS 679 W01 Project - Multiresolution Curves

For my final project, I implemented a multiresolution curve editor, based on the SIGGRAPH '94 paper by Adam Finkelstein and David Salesin. The framework, acting on an arbitrary endpoint-interpolating cubic B-spline curve, provides a variety of resolution levels via wavelet analysis. Supported operations include smoothing the curve, editing the overall sweep of the curve while preserving its details, continuous levels of smoothing and editing, direct manipulation, colour and size dimensions, and adaptive curve sampling.

User Interface

The most commonly used controls are on the main screen.

Free-form Design Surface (center). Draw your curve here. Left mouse button adds a point (can only be done in highest resolution), middle mouse button modifies geometry, and right mouse button modifies colour and width.
Resolution Slider (middle right). Controls resolution level, to tenths of a unit.
Status Panel (upper right). Displays current and max level, current and max control points.
Colour Palette (bottom left). Loads your cursor with the selected colour.
Width Control (bottom right). Left slider is the primary width. If "Alternate?" checkbox is checked, right slider is the secondary width and the two widths rotate as new points are added.

More control is provided through menus.

File. "Clear" (hotkey L) clears the current curve, "Load..." loads a curve specification from a file you select, "Save..." writes the current curve specification to a file you select, and "Quit" terminates the program.
Draw Mode. Radio buttons "Control Polygon" (hotkey C) shows the control polygon, and "Curve Only" (hotkey O) hides it.
Curve Params (accessible through Draw Mode menu). Text fields allow you to enter the number of curve evaluations per control point, and subdivision threshold in pixels.
Manipulation. Radio buttons "Control Pt" (hotkey E) enables curve manipulation via control points, and "Direct" (hotkey D) allows direct manipulation of the curve.

Filter Bank

The core of this project is implementing the filter bank that takes a high level representation of the cubic B-spline, and breaks it down into successively smaller sets of control points and successively larger sets of detail functions. The filter bank works on an arbitrary number of input control points, but behaviour is most intuitive when there are exactly 2^n + 3 for some non-negative n. Here is an example of smoothing and editing using the filter bank.

	Original input curve (34 control points, level 5).
	Same curve sent through filter bank (4 control points, level 0).
	Modified curve (4 control points, level 0).
	Same curve with detail re-added (34 control points, level 5).

First I specify a bunch of matrices that represent the scaling functions (B-spline basis functions - from Cox-de Boor-Mansfield recursion formula) and the orthogonal wavelets. For decomposition, the problem distills down into successively solving Ax = b linear equations. For this, I used LU decomposition since I have multiple right-hand-sides (6, for x, y, r, g, b, and width). Reconstruction can be done with simpler matrix additions and multiplications.

More Features

Adaptive Curve Sampling

If a cubic B-spline is sampled uniformly in t, the resulting line segments will not typically be of equal length. I implemented adaptive recursive line sampling to remedy this. Essentially I guarantee that no line segment is longer than a certain threshold specified in pixels. This, paired with the ability to tweak the number of samples per control point, provides a gradient between smooth and blocky curves.

Additional Dimensions

Finkelstein and Salesin's original multiresolution framework only supported x and y dimensions. I added colour (r, g, b) and line width (as suggested in their Extensions and future work section). All of the machinery extended readily to these additional dimensions. My goal was to provide the ability to specify calligraphy-like curves.

My "non-artist" attempt at a calligraphy capital J.

Fractions

The original filter bank only allows for integer-level smoothing and editing, and the change in curve can sometimes be quite dramatic between levels. Clearly "smooth" transitions would be better. I do a variation of (1 - t)*c + t*d interpolation to ascribe meaning to curves at fractional levels. Implementing editing is more difficult, first having to figure out which control points at the integer level are maximally influenced by a change in control point at the fractional level, and doing a more complicated (e.g. non-linear) interpolation.

	Curve at top level 6.
	Same image at level 4.5.
	Same image at level 3.5.

Direct Manipulation

Direct manipulation by tugging on the curve (at any level of resolution, even fractional) is an alternative to control point manipulation. I simulate scan conversion by finding the closest sampled point (Euclidean distance) to the location the user clicked. The Cox-de Boor-Mansfield recurrence tells which control points influence that particular location, and by how much. I take the pseudoinverse and multiply by the specified delta change (up to 6 dimensions) to get the final change in control points. Since the result of the recurrence typically yields a singular matrix, I couldn't reuse LU decomposition; I had to implement singular value decomposition to calculate the pseudoinverse.

Future Work

Implement more features of the paper, such as editing a constant portion of the curve, curve character libraries, orientation of detail, and scan conversion and curve compression.
Harder stuff like non-uniform B-splines, scanning curves, handling discontinuities, extensions to 2D surfaces, etc.
Make the editor a bit more usable, such as undo (I wished more than once I had this!), distinguishing among control points on top of one another, showing size component of control points, colour editor instead of using just the 12 canned colours, delete control points, multiple curves on the free-form design surface, etc.
Efficiency and error checking. I don't think anything drastically crashes, but who knows. Although the editor currently runs at reasonable interactive speeds, speed and memory usage could be better. I should be taking advantage of the fact that most of the matrices are banded, to reduce storage. I did implement a banded matrix multiplication routine, but more could be done. There exists an order n LU decomposition algorithm for banded matrices, which would help.

References

A. Finkelstein and D. Salesin. Multiresolution Curves. Proceedings of SIGGRAPH '94, p. 261.
E. Stollnitz, T. DeRose, and D. Salesin. Wavelets for Computer Graphics, Morgan Kaufmann Publishers, Inc., San Francisco, 1996.
W. Press, S. Teukolsky, W. Vetterling, B. Flannery. Numerical Recipes in C, Cambridge University Press, Cambridge, 1992.
CS 679 Course Notes