Figure 3 Changing a curves overall sweep without affecting its character. Given the original curve(a), the system extracts the over- all sweep(b). If the user modifies the sweep(c), the system can I pply the detail (d) Figure 5 Changing the character of a curve without affecting its sweep through synthesis +AC C+pp-1. P+I AC Note that editing the sweep of the curve at lower levels of The middle of the dark curve is pulled, using editing at var- els of smoothing. A change in a control point incl ing affects larger portions of the high-resolution curve(o lowest level, when j=0, the entire curve is affected. At the d effect, while a change in a control point row effect level, when j=J, only the narrow portion influenced by one control point is affected. The kind of flexibility that this multireso- solved in linear time using LU decomposition [12]. Thus we can lution editing allows is suggested in Figures 3 and 4 compute the entire filter bank operation without ever forming and using A or B explicitly 4. 2 Editing the character of the curve Multiresolution curves also naturally support changes in the char 4 Application II: Multiresolution curves and surfaces acter of a curve. without affecting its overall Let c be control points of a curve, and letC, Do,..., D-I denote its wavelet transform. Editing the character of the curve is simply a matter of re- We presented two applications of wavelets in Part I: compression of placing the existing set of detail coefficients,.,D-Iwithsome ages. Our third application of wavelets in computer graphics is new set and reconstructing. To avoid coo curve design and editing, as described in detail by Finkelstein and system artifacts. all detail coefficients are expressed in terms of the Salesin (8J. Their multiresolution curves are built from a wavelet curve s local tangent and normal, rather than thex and y directions cussed in the previous section s cubic B-splines, which we dis- Figure 5 demonstrates how the character of curves in an illustration can be modified with various detail styles. ( The interactive illus- Multiresolution curves conveniently support a variety of opera- tration system used to create this figure was described by Salisbury eta.[l4].) changing a curve's overall"sweep"while maintaining its fine de 4.3 Multiresolution surfaces tails, or"character"(Figures 3 and 4); changing a curve's"character without affecting its overall Multiresolution editing can be extended to surfaces by using ten- sor products of B-spline scaling functions and wavelets. Either the standard construction or the nonstandard construction described g a curve at any continuous level of detail, allowing an ar- in Part 1 for Haar basis functions can be used to form a two- ary portion of the curve to be affected through direct manipu- dimensional basis from a one-dimensional B-spline basis. We can then edit surfaces using the same operations described for curves. For example, Figure 6 shows a bicubic tensor-product B-spline sur- smoothing at continuous levels to remove undesirable features face after altering its at different levels of detail from a curve approximating or"fitting"a curve within a guaranteed maximum We can further generalize multiresolution analysis to surfaces of error tolerance, for scan conversion and other applications arbitrary topology by defining wavelets based on subdivision sur- faces, as described by Lounsbery et al. [10]. Their nonorthogonal Here we'll describe briefly just the first two of these operations, wavelet basis, in combination with the work of Eck et al. 6], al which fall out quite naturally from the multiresolution representa lows any polyhedral object to be decomposed into scaling function and wavelet coefficients. Then a compression scheme similar to the one presented for images in Section 3. 3 of Part 1 can be used to dis- play the object at various levels of detail simply by leaving out sma 4.1 Editing the sweep of the curve wavelet coefficients during reconstruction. An example of this tech- nique is shown in Figure 7. Editing the sweep of a curve at an level of the wavelet transform is simple. Let C be the points of the original curve o, let C be a low-resolution version of C, and let c be 5 Conclusion an edited version of C, given by C-C+ AC. The edited ver- Our primer has only touched on a few of the many uses for wavelets sion of the highest resolution curve C in computer graphics. We hope this introduction to the topic has ex-(a) (b) (c) (d) Figure 3 Changing a curve’s overall sweep without affecting its character. Given the original curve (a), the system extracts the overall sweep (b). If the user modifies the sweep (c), the system can reapply the detail (d). 1 2 3 4 Figure 4 The middle of the dark curve is pulled, using editing at various levels of smoothing j. A change in a control point inC1 has a very broad effect, while a change in a control point inC4 has a narrow effect. solved in linear time using LU decomposition [12]. Thus we can compute the entire filter bank operation without ever forming and using Aj or Bj explicitly. 4 Application III: Multiresolution curves and surfaces We presented two applications of wavelets in Part 1: compression of one-dimensional signals and compression of two-dimensional images. Our third application of wavelets in computer graphics is curve design and editing, as described in detail by Finkelstein and Salesin [8]. Their multiresolution curves are built from a wavelet basis for endpoint-interpolating cubic B-splines, which we discussed in the previous section. Multiresolution curves conveniently support a variety of operations: changing a curve’s overall “sweep” while maintaining its fine details, or “character” (Figures 3 and 4); changing a curve’s “character” without affecting its overall “sweep” (Figure 5); editing a curve at any continuous level of detail, allowing an arbitrary portion of the curve to be affected through direct manipulation; smoothing at continuous levels to remove undesirable features from a curve; approximating or “fitting” a curve within a guaranteed maximum error tolerance, for scan conversion and other applications. Here we’ll describe briefly just the first two of these operations, which fall out quite naturally from the multiresolution representation. 4.1 Editing the sweep of the curve Editing the sweep of a curve at an integer level of the wavelet transform is simple. Let CJ be the control points of the original curve f J (t), let Cj be a low-resolution version of CJ , and let Cˆj be an edited version of Cj , given by Cˆj = Cj + Cj . The edited version of the highest resolution curveCˆ J = CJ +CJ can be computed Figure 5 Changing the character of a curve without affecting its sweep. through synthesis: Cˆ J = CJ + CJ = CJ + PJ PJ1 Pj+1 Cj . Note that editing the sweep of the curve at lower levels of smoothing j affects larger portions of the high-resolution curvef J (t). At the lowest level, when j = 0, the entire curve is affected. At the highest level, when j = J, only the narrow portion influenced by one original control point is affected. The kind of flexibility that this multiresolution editing allows is suggested in Figures 3 and 4. 4.2 Editing the character of the curve Multiresolution curves also naturally support changes in the character of a curve, without affecting its overall sweep. Let CJ be the control points of a curve, and letC0 , D0 , : : :, DJ1 denote its wavelet transform. Editing the character of the curve is simply a matter of replacing the existing set of detail coefficientsDj , : : : , DJ1 with some new set Dˆj , : : : , Dˆ J1 , and reconstructing. To avoid coordinatesystem artifacts, all detail coefficients are expressed in terms of the curve’s local tangent and normal, rather than the x and y directions. Figure 5 demonstrates how the character of curves in an illustration can be modified with various detail styles. (The interactive illustration system used to create this figure was described by Salisbury et al. [14].) 4.3 Multiresolution surfaces Multiresolution editing can be extended to surfaces by using tensor products of B-spline scaling functions and wavelets. Either the standard construction or the nonstandard construction described in Part 1 for Haar basis functions can be used to form a twodimensional basis from a one-dimensional B-spline basis. We can then edit surfaces using the same operations described for curves. For example, Figure 6 shows a bicubic tensor-product B-spline surface after altering its sweep at different levels of detail. We can further generalize multiresolution analysis to surfaces of arbitrary topology by defining wavelets based on subdivision surfaces, as described by Lounsbery et al. [10]. Their nonorthogonal wavelet basis, in combination with the work of Eck et al. [6], allows any polyhedral object to be decomposed into scaling function and wavelet coefficients. Then a compression scheme similar to the one presented for images in Section 3.3 of Part 1 can be used to display the object at various levels of detail simply by leaving out small wavelet coefficients during reconstruction. An example of this technique is shown in Figure 7. 5 Conclusion Our primer has only touched on a few of the many uses for wavelets in computer graphics. We hope this introduction to the topic has ex- 5