Abstracts of Recent Publications

Environment Matting and Compositing
Abstract:

 
This paper introduces a new process, environment matting, which captures not just a foreground object and its traditional opacity matte from a real-world scene, but also a description of how that object refracts and reflects light, which we call an environment matte. The foreground object can then be placed in a new environment, using environment compositing, where it will refract and reflect light from that scene. Objects captured in this way exhibit not only specular but glossy and translucent effects, as well as selective attenuation and scattering of light according to wavelength. Moreover, the environment compositing process, which can be performed largely with texture mapping operations, is fast enough to run at interactive speeds on a desktop PC. We compare our results to photos of the same objects in real scenes. Applications of this work include the relighting of objects for virtual and augmented reality, more realistic 3D clip art, and interactive lighting design.

 
Citation:
Douglas E. Zongker, Dawn M. Werner, Brian Curless, and David H. Salesin. Proceedings of SIGGRAPH 99, in Computer Graphics Proceedings, Annual Conference Series, 1999.

 
On-line documents:
Complete article [Acrobat pdf file, 1,703 Kb (hi-res figures)]
Complete article [Acrobat pdf file, 484 Kb (lo-res figures)]
Project web page

Interactive Arrangement of Botanical L-System Models
Abstract:

 
In this paper, we explore the problem of interactively manipulating plant models without sacrificing their botanical accuracy. The primary technical contribution of the paper is a method for interactively manipulating plant structures using a inverse-kinematics optimization technique. The branches of the plant are endowed with flexural and torsional stiffnesses, and these are used in the IK optimization. We demonstrate our approach with several examples of plant models arranged in this fashion.

 
Citation:
Joanna L. Power, A. J. Bernheim Brush, David H. Salesin, and Przemyslaw Prusinkiewicz. 1999 ACM Symposium on Interactive 3D Graphics.

 
On-line documents:
Complete article [Acrobat pdf file, 120 Kb]
Color Plate [Acrobat pdf file, 44 Kb]

Computer-Generated Floral Ornament
Abstract:

 
This paper describes some of the priniciples of traditional floral ornamental design, and explores ways in which these designs can be created algorithmically. It introduces the idea of "adaptive clip art," which encapsulates the rules for creating a specific ornamental pattern. Adaptive clip art can be used to generate patterns that are tailored to fit a particularly shaped region of the plane. If the region is resized or reshaped, the ornament can be automatically regenerated to fill this new area in an appropriate way. Our ornamental patterns are created in two steps: first, the geometry of the pattern is generated as a set of two-dimensional curves and filled boundaries: second, this geometry is rendered in any number of styles. We demonstrate our approach with a variety of floral ornamental designs.

 
Citation:
Michael T. Wong, Douglas E. Zongker, and David Salesin. Proceedings of SIGGRAPH 98, in Computer Graphics Proceedings, Annual Conference Series, 1998.

 
On-line documents:
Complete article [Acrobat pdf file, 9.7 Mb]

Reproducing Color Images Using Custom Inks
Abstract:

 
We investigate the general problem of reproducing color images on an offset press using custom inks in any combination and number. While this problem has been explored previously for the case of two inks, there are a number of new mathematical and algorithmic challenges that arise as the number of inks increases. These challenges include more complex gamut mapping strategies, more efficient ink selection strategies, and fast and numerically accurate methods for computing ink separations in situations that may be either over-or under-constrained. In addition, the demands of high-quality color printing require an accurate physical model of the colors that result from overprinting multiple inks using halftoning, including the effects of trapping, dot gain, and the interreflection of light between ink layers. In this paper, we explore these issues related to printing with multiple custom inks, and address them with new algorithms and physcial models. Finally, we present some printed examples demonstrating the promise of our methods.

 
Citation:
Eric J. Stollnitz, Victor Ostromoukhov, and David Salesin. Proceedings of SIGGRAPH 98, in Computer Graphics Proceedings, Annual Conference Series, 1998.

 
On-line documents:
Article without appendices [Acrobat pdf file, 221 Kb]
Project web page

Synthesizing Realistic Facial Expressions from Photographs
Abstract:

 
We present new techniques for creating photorealistic textured 3D facial models from photographs of a human subject, and for creating smooth transitions between different facial expressions by morphing between these different models. Starting from several uncalibrated views of a human subject, we employ a user-assisted technique to recover the camera poses corresponding to the views as well as the 3D coordinates of a sparse set of chosen locations on the subject's face. A scattered data interpolation techniques is then used to deform a generic face mesh to fit the particular geometry of the subject's face. Having recovered the camera poses and the facial geometry, we extract from the input images one or more texture maps for the model. This process is reapeated for several facial expressions of a particular subject. To generate transitions between these facial expressions we use 3D shape morphing between the corresponding face modes, while at the same time blending the corresponding textures. Using our technique, we have been able to generate highly realistic face models and natural looking animations.

 
Citation:
Frederic Pighin, Jamie Hecker, Dani Lischinski, Richard Szeliski, and David Salesin. To appear in Proceedings of SIGGRAPH 98, in Computer Graphics Proceedings, Annual Conference Series, 1998.

 
On-line documents:
Complete article [Acrobat pdf file, 272 Kb]

 
Also available as Department of Computer Science and Engineering Technical Report TR 97-01-03.
Text only [compressed PostScript file, 80 Kb]
Color plates [compressed PostScript file, 80 Kb]
Project web page

Computer-Generated Watercolor
Abstract:
This paper describes the various artistic effects of watercolor and shows how they can be simulated automatically. Our watercolor model is based on an ordered set of translucent glazes, which are created independently using a shallow-water fluid simulation. We use a Kubelka-Munk compositing model for simulating the optical effect of the superimposed glazes. We demonstrate how computer-generated watercolor can be used in three different applications: as part of an interactive watercolor paint system, as a method for automatic image "watercolorization", and as a mechanism for non-photorealistic rendering of three-dimensional scenes.

 
Citation:
Cassidy Curtis, Sean Anderson, Josh Seims, Kurt Fleischer, and David H. Salesin. Proceedings of SIGGRAPH 97, in Computer Graphics Proceedings, Annual Conference Series, 1997.

 
On-line documents:
The paper (gzipped PostScript, 8.1 Mb)
The paper (.pdf, 1.83 Mb)
The paper (.pdf, 517 Kb, images compressed beyond recognition)

Multiperspective Panoramas for Cel Animation
Abstract:
Traditional 2D cel-animation uses background panoramas over which foreground characters, and the camera, move. Because characters move through complex worlds, the panorama often contains multiple views of the world taken from different perspectives, but nonetheless seamlessly integrated into a 2D painting that is locally coherent, but may be globally nonsensical. This is a difficult task in which computer graphics can be of service. The panorama-creation process is currently performed by specialists, and the complexity of camera paths through the world is limited by their ability to assemble multiple views into a coherent whole. Futhermore, once an artist has created the panorama it is often difficult to incorporate computer-generated imagery elements into the animation because it is hard to abstract a meaningful 3D geometry for the world. This paper presents a system that creates a layout-guide from a crude 3D model and a camera path through that model; this layout-guide is then used in the production of a panorama, but one in which complex paths are possible, and in which the incorporation of CG elements is simple.

 
Citation:
Daniel N. Wood, Adam Finkelstein, John F. Hughes, Craig E. Thayer, and David H. Salesin. Proceedings of SIGGRAPH 97, in Computer Graphics Proceedings, Annual Conference Series, 1997.

 
On-line documents:
Complete article [Acrobat pdf file, 2 Mb]

Orientable Textures for Image-Based Pen-and-Ink Illustration
Abstract:
We present an interactive system for creating pen-and-ink-style line drawings from greyscale images in which the strokes of the rendered illustation follow the features of the original image. The user, via new interaction techniques for editing a direction field, specifies an orientation for each region of the image; the computer draws oriented strokes, based on a user-specified set of example strokes, that achieve the same tone as the image via a new algorithm that compares an adaptively-blurred version of the current illustration to the target tone image. By aligning the direction field with surface orientation of the objects in the image the user can create textures that appear attached to those objects instead of merely converying their darkness. The result is a more compelling pen-and-ink illustration than was previously possible from 2D reference imagery.

 
Citation:
Michael P. Salisbury, Michael T. Wong, John F. Hughes, and David H. Salesin. Proceedings of SIGGRAPH 97, in Computer Graphics Proceedings, Annual Conference Series, 401-406, August 1997.

 
On-line documents:
Complete article [compressed PostScript file, 2.3 Mb]

Progressive Previewing of Ray-Traced Images Using Image Plane Discontinuity Meshing
Abstract:
This paper presents a new method for progressively previewing a ray-traced image while it is being computed. Our method constructs and incrementally updates a constrained Delaunay triangulation for the image plane containing various important discontinuity edges in the image along with all of the image samples that have been computed by the ray tracer. The triangulation is rendered using hardware Gourand shading, yielding a piecewise linear approximation to the final image. Texture mapped surfaces as well as other regions in the image that are not well approximated by linear interpolation, are handled threough the use of hardware texture mapping.

 
Citation:
F.P. Pighin, D. Lishinski, and D.H. Salesin. Eight Eurographics Workshop on Rendering, 115-125, Saint-Etienne, France, June 1997.

 
On-line documents:
Complete article [Acrobat pdf file, 400 Kb]

Clustering for Glossy Global Illumination
Abstract:
We present a new clustering algorithm for global illumination in complex environments. The new algorithm extends previous work on clustering for radiosity to allow for non-diffuse (glossy) reflectors. We represent clusters as points with directional distributions of outgoing and incoming radiance and importance, and we derive an error bound for transfers between these clusters. The algorithm groups input surfaces into a hierarchy of clusters, and then permits clusters to interact only if the error bound is below an acceptable tolerance. We show that the algorithm is asymptotically more efficient than previous clustering algorithms even when restricted to ideally diffuse environments. Finally, we demonstrate the performance of our method on two complex glossy environments.

 
Citation:
Per H. Christensen, Dani Lischinski, Eric J. Stollnitz, and David H. Salesin. Clustering for glossy global illumination. ACM Transactions on Graphics 16, January 1997.

 
On-line documents:
Complete article [Acrobat file, 843 Kb]
Complete article [compressed PostScript file, 9.1 Mb]
Article without color images [compressed PostScript file, 92 Kb]

Comic Chat
Abstract:
Comics have a rich visual vocabulary, and people find them appealing. They are also an effective form of communication. We have built a system, called Comic Chat, that represents on-line communications in the form of comics. Comic Chat automates numerous aspects of comics generation, including balloon construction and layout, the placement and orientation of comic characters, the default selection of character gestures and expressions, the incorporation of semantic panel elements, and the choice of zoom factor for the virtual camera. This paper describes the mechanisms that Comic Chat uses to perform this automation, as well as novel aspects of the program's user interface. Comic Chat is a working program, allowing groups of people to communicate over the Internet. It has several advantages over other graphical chat programs, including the availability of a graphical history, and a dynamic graphical presentation.
Citation:
D. Kurlander, David H. Salesin, T. Skelly. Comic chat. Proceedings of SIGGRAPH 96, in Computer Graphics Proceedings, Annual Conference Series, 225-236, August 1996.

 
On-line documents:
Complete article [Acrobat file, 2.3 Mb]

Declarative Camera Control for Automatic Cinematography
Abstract:
Animations generated by interactive 3D computer graphics applications are typically portrayed either from a particular character's point of view or from a small set of strategically-placed viewpoints. By ignoring camera placement, such applications fail to realize important storytelling capabilities that have been explored by cinematographers for many years.
 In this paper, we describe several of the principles of cinematography and show how they can be formalized into a declarative language, called the Declarative Camera Control Language ( dccl ). We describe the application of dccl within the context of a simple interactive video game and argue that dccl represents cinematic knowledge at the same level of abstraction as expert directors by encoding 16 idioms from a film textbook. These idioms produce compelling animations, as demonstrated on the accompanying videotape.
Citation:
David B. Christianson, Sean. E. Anderson, Li-Wei He, Daniel S. Weld, Michael F. Cohen, David H. Salesin. Declarative camera control for automatic cinematography. Proceedings of AAAI '96 (Portland, OR), 148-155, 1996. An earlier version appeared as Department of Computer Science and Engineering Technical Report TR 95-01-03, University of Washington, 1995.

 
On-line documents:
Complete article [Acrobat file, 240 KB]

Fast Rendering of Complex Environments
Using a Spatial Hierarchy
Abstract:
We present a new method for accelerating the rendering of complex static scenes. The technique is applicable to unstructured scenes containing arbitrary geometric primitives and has sublinear asymptotic complexity. Our approach is to construct a spatial hierarchy of cells over the scene and to associate with each cell a simplified representation of its contents. The scene is then rendered using a traversal of the hierarchy in which a cell's approximation is drawn instead of its contents if the approximation is sufficiently accurate. We apply the method to several different scenes and demonstrate significant speedups with little image degradation. We also exhibit and discuss some of the artifacts that our approximation may cause.
Citation:
Brad Chamberlain, Tony DeRose, Dani Lischinski, David H. Salesin, and John Snyder. Fast rendering of complex environments using a spatial hierarchy. Proceedings of Graphics Interface '96 (Toronto), 132-141, 1996.
On-line documents:
Text of article [compressed PostScript file, 38 Kb]
Color plates 1 and 2 [compressed PostScript file, 225 Kb]
Color plates 3 to 5 [compressed PostScript file, 1 Mb]

Global Illumination of Glossy Environments
Using Wavelets and Importance
Abstract:
We show how importance-driven refinement and a wavelet basis can be combined to provide an efficient solution to the global illumination problem with glossy and diffuse reflections. Importance is used to focus the computation on the interactions having the greatest impact on the visible solution. Wavelets are used to provide an efficient representation of radiance, importance, and the transport operator. We discuss a number of choices that must be made when constructing a finite element algorithm for glossy global illumination. Our algorithm is based on the standard wavelet decomposition of the transport operator and makes use of a four-dimensional wavelet representation for spatially- and angularly-varying radiance distributions. We use a final gathering step to improve the visual quality of the solution. Features of our implementation include support for curved surfaces as well as texture-mapped anisotropic emission and reflection functions.

 
Citation:
Per H. Christensen, Eric J. Stollnitz, David H. Salesin, and Tony D. DeRose. Global illumination of glossy environments using wavelets and importance. ACM Transactions on Graphics, 15(1):37-71, January 1996.

 
On-line documents:
Complete article [Acrobat file, 611 Kb]
Complete article [compressed PostScript file, 2.8 Mb]

Hierarchical Image Caching for Accelerated Walkthroughs of Complex Environments
Abstract:
We present a new method for accelerating walkthroughs of geometrically complex static scenes. As a preprocessing step, our method constructs a BSP-tree that hierarchically partitions the geometric primitives in the scene. In the course of a walkthrough, images of nodes at various levels of the hierarchy are cached for reuse in subsequent frames. A cached image is applied as a texture map to a single quadrilateral that is drawn instead of the geometry contained in the corresponding node. Visual artifacts are kept under control by using an error metric that quantifies the descrepancy between the appearance of geometry contained in a node and the cached image. The new method is shown to achieve significant speedups for a walkthrough of a complex outdoor scene, with little or no loss in rendering quality.

 
Citation:
Jonathan Shade, Dani Lischinski, Tony D. DeRose, and John Snyder, David H. Salesin. Hierarchical image caching for accelerated walkthroughs of complex environments. Proceedings of SIGGRAPH 96, in Computer Graphics Proceedings, Annual Conference Series, 75-82, August 1996.

 
On-line documents:
Complete article [Acrobat pdf file, 180 Kb]

 
Also available as Department of Computer Science and Engineering Technical Report TR 96-01-06.
TR 96-01-06 [compressed postscript file, 40 Kb]
Plate1 [compressed Postscript file, 824 Kb]
Plate2 [compressed Postscript file, 704 Kb]
Project web page

Interactive Multiresolution Surface Viewing
Abstract:
Multiresolution analysis has been proposed as a basic tool supporting compression, progressive transmission, and level-of-detail control of complex meshes in a unified and theoretically sound way.
We extend previous work on multiresolution analysis of meshes in two ways. First, we show how to perform multiresolution analysis of colored meshes by separately analyzing shape and color. Second, we describe efficient algorithms and data structures that allow us to incrementally construct lower resolution approximations to colored meshes from the geometry and color wavelet coefficients at interactive rates. We have integrated these algorithms in a prototype mesh viewer that supports progressive transmission, dynamic display at a constant frame rate independent of machine characteristics and load, and interactive choice of tradeoff between the amount of detail in geometry and color. The viewer operates as a helper application to Netscape, and can therefore be used to rapidly browse and display complex geometric models stored on the World Wide Web.
Citation:
Andrew Certain, Jovan Popovic, Tony DeRose, Tom Duchamp, David H. Salesin, Werner Stuetzle. Interactive multiresolution surface viewing. Proceedings of SIGGRAPH 96, in Computer Graphics Proceedings, Annual Conference Series, 91-98, August 1996.

 
 Available as Department of Computer Science and Engineering Technical Report TR 96-01-07, University of Washington, 1996.

 
On-line documents:
Compelete article [Acrobat file, 435 Kb]

Multiresolution Video
Abstract:
We present a new representation for time-varying image data, called multiresolution video. The representation allows for varying -- and arbitrarily high -- spatial and temporal resolutions in different parts of a video sequence. The representation is based on a sparse, hierarchical encoding of the video data. We show how multiresolution video supports a number of primitive operations: drawing frames at a particular spatial and temporal resolution; and translating, scaling, and compositing multiresolution sequences. These primitives are then used as the building blocks to support a variety of applications: video compression; multiresolution playback, including motion-blurred "fast-forward" and "reverse"; constant speed display; enhanced video scrubbing; and "video clip art" editing and compositing. The multiresolution representation requires little storage overhead, and the algorithms using the representation are both simple and efficient.

 
Citation:
Adam Finkelstein, Charles E. Jacobs, David H. Salesin. Multiresolution Video. Proceedings of SIGGRAPH 96, in Computer Graphics Proceedings, Annual Conference Series, 281-290, August 1996.
On-line documents:
Complete article [Acrobat file, 651 Kb]
Complete article [compressed Postscript file, 3.5 Mb]
Article without color images [compressed Postscript file, 54Kb]

Rendering Parametric Surfaces in Pen and Ink
Abstract:
This paper presents new algorithms and techniques for rendering parametric free-form surfaces in pen and ink. In particular, we introduce the idea of "controlled-density hatching" for conveying tone, texture, and shape. The fine control over tone this method provides allows the use of traditional texture mapping techniques for specifying the tone of pen-and-ink illustrations. We also show how a planar map, a data structure central to our rendering algorithm, can be constructed from parametric surfaces, and used for clipping strokes and generating outlines. Finally, we show how curved shadows can be cast onto curved objects for this style of illustration.

 
Citation:
George Winkenbach, David H. Salesin. Rendering parametric surfaces in pen and ink. Proceedings of SIGGRAPH 96, in Computer Graphics Proceedings, Annual Conference Series, 469-476, August 1996.
On-line documents:
Available as Technical Report:
96-01-05 [compressed Postscript file, 801 Kb]

Reproducing Color Images as Duotones
Abstract:
We investigate a new approach for reproducing color images. Rather than mapping the colors in an image onto the gamut of colors that can be printed with cyan, magenta, yellow, and black inks, we choose the set of printing inks for the particular image being reproduced. In this paper, we look at the special case of selecting inks for duotone printing, a relatively inexpensive process in which just two inks are used. Specifically, the system we describe takes an image as input, and allows a user to select 0, 1, or 2 inks. It then chooses the remaining ink or inks so as to reproduce the image as accurately as possible and produces the appropriate color separations automatically.
Citation:
Joanna L. Power, Brad S. West, Eric J. Stollnitz, and David H. Salesin. Reproducing color images as duotones. Proceedings of SIGGRAPH 96, in Computer Graphics Proceedings, Annual Conference Series, 237-248, August 1996.
On-line documents:
Article without duotones [Acrobat file, 2.8 Mb]
Article without duotones [compressed PostScript file, 3.0 Mb]

Scale-dependent Reproduction of Pen-and-ink Illustrations 
Abstract:
This paper describes a compact resolution- and scale-independent representation for pen-and-ink illustrations. The proposed representation consists of a low-resolution grey-scale image, augmented by a set of discontinuity segments. We also present a new reconstruction algorithm that magnifies the low-resolution image while keeping the image sharp along the discontinuities. By storing pen-and-ink illustrations in this representation, we can produce high-fidelity illustrations at any scale and resolution by generating an image of the desired size and filling that image with pen-and-ink strokes.

 
Citation:
Mike Salisbury, Corey Anderson, Dani Lischinski, and David H. Salesin. Scale-dependent Reproduction of Pen-and-ink Illustration. Proceedings of SIGGRAPH 96, in Computer Graphics Proceedings, Annual Conference Series, 461-468, August 1996.
On-line documents:
Available as Technical Report:
TR 96-01-02 [compressed PostScript file, 11.5 Mb]

Wavelets for Computer Graphics: Theory and Applications
Preview:
This distinctly accessible introduction to wavelets provides computer graphics professionals and researchers with the mathematical foundations for understanding and applying this new and powerful tool.
Wavelets are rapidly becoming a core technique in computer graphics, with applications to:
image editing and compression;
automatic level-of-detail control for editing and rendering curves and surfaces;
surface reconstruction from contours; and
physical simulation for global illumination and animation.
Stressing intuition and clarity, this book offers a solid understanding of the theory of wavelets and their proven applications in computer graphics.
Although previous introductions to wavelets have presented an elegant mathematical framework, that framework is too restrictive to apply to many problems in graphics. In contrast, this book focuses on a generalized theory that naturally accommodates the kinds of objects that commonly arise in computer graphics, including images, open curves, and surfaces of arbitrary topology.
The book also contains a foreword by Ingrid Daubechies and an appendix covering the necessary background material in linear algebra.

 
Contents: See the table of contents.

 
Citation:
Eric J. Stollnitz, Tony D. DeRose, and David H. Salesin. Wavelets for Computer Graphics: Theory and Applications. Morgan Kaufmann, San Francisco, 1996.

 
ISBN: 1-55860-375-1

 
Ordering information: See Morgan Kaufmann's web site.

 
On-line material:
Matlab code from Appendix C [compressed tar file, 17 Kb]

The Virtual Cinematographer: a Paradigm for Automatic Real-Time Camera Control and Directing
Abstract:
This paper presents a paradigm for automatically generating complete camera specifications for capturing events in virtual 3D environments in real-time. We describe a fully implemented system, called the Virtual Cinematographer, and demonstrate its application in a virtual "party" setting. Cinematographic expertise, in the form of film idioms, is encoded as a set of small hierarchically organized finite state machines. Each idiom is responsible for capturing a particular type of scene, such as three virtual actors conversing or one actor moving across the environment. The idiom selects shot types and the timing of transitions between shots to best communicate events as they unfold. A set of camera modules, shared by the idioms, is responsible for the low-level geometric placement of specific cameras for each shot. The camera modules are also responsible for making subtle changes in the virtual actors' positions to best frame each shot. In this paper, we discuss some basic heuristics of filmmaking and show how these ideas are encoded in the Virtual Cinematographer.
Citation:
Li-Wei He, Michael F. Cohen, David H. Salesin. The virtual cinematographer: a paradigm for automatic real-time camera control and directing. Proceedings of SIGGRAPH 96, in Computer Graphics Proceedings, Annual Conference Series, 217-224, August 1996.

 
On-line documents:
Complete article [Acrobat file, 158 Kb]

Fast Multiresolution Image Querying
Abstract:
We present a method for searching in an image database using a query image that is similar to the intended target. The query image may be a hand-drawn sketch or a (potentially low-quality) scan of the image to be retrieved. Our searching algorithm makes use of multiresolution wavelet deompositions of the query and database images. The coefficients of these decompositions are distilled into small "signatures" for each image. We introduce an "image querying metric" that operates on these signatures. This metric essentially compares how many significant wavelet coefficients the query has in common with potential targets. The metric includes parameters that can be tuned, using a statistical analysis, to accommodate the kinds of image distortions found in different types of image queries. The resulting algoritm is simple, requires very little storage overhead for the database signatures, and is fast enough to be performed on a database of 20,000 images at interactive rates (on standard desktop machines) as a query is sketched. Our experiments with hundreds of queries in databases of 1000 and 20,000 images show dramatic improvement, in both speed and success rate, over using a conventional L1, L2, or color histogram norm.
Citation:
Charles E. Jacobs, Adam Finkelstein, David H. Salesin. Fast Multiresolution Image Querying. Proceedings of SIGGAPH 95, in Computer Graphics Proceedings, Annual Conference Series, pages 277-286, August 1995.

 
On-line documents:
Available as Technical Report TR 95-01-06:
Complete report [compressed PostScript file, 474 Kb]
Report without color plates [compressed PostScript file, 63 Kb]

Wavelets for Computer Graphics: A Primer
Abstract:
Wavelets are a mathematical tool for hierarchically decomposing functions. Using wavelets, a function can be described in terms of a coarse overall shape, plus details that range from broad to narrow. Regardless of whether the function of interest is an image, a curve, or a surface, wavelets provide an elegant technique for representing the levels of detail present. This primer is intended to provide those working in computer graphics with some intuition for what wavelets are, as well as to present the mathematical foundations necessary for studying and using them. In Part 1, we discuss the simple case of Haar wavelets in one and two dimensions, and show how they can be used for image compression. Part 2 presents the mathematical theory of multiresolution analysis, develops bounded-interval spline wavelets, and describes their use in multiresolution curve and surface editing.

 
Citations:
Eric J. Stollnitz, Tony D. DeRose, and David H. Salesin. Wavelets for computer graphics: A primer, part 1. IEEE Computer Graphics and Applications, 15(3):76-84, May 1995.
Eric J. Stollnitz, Tony D. DeRose, and David H. Salesin. Wavelets for computer graphics: A primer, part 2. IEEE Computer Graphics and Applications, 15(4):75-85, July 1995.

 
On-line documents:
Part 1 [Acrobat file, 264 Kb]
Part 1 [compressed PostScript file, 473 Kb]
Part 2 [Acrobat file, 865 Kb]
Part 2 [compressed PostScript file, 417 Kb]
Matlab code [compressed tar file, 17 Kb]

Computer-Generated Pen-and-Ink Illustration
Abstract:
This paper describes the principles of traditional pen-and-ink illustration, and shows how a great number of them can be implemented as part of an automated rendering system. It introduces "stroke textures," which can be used for achieving both texture and tone with line drawing. Stroke textures also allow resolution-dependent rendering, in which the choice of strokes used in an illustration is appropriately tied to the resolution of the target medium. We demonstrate these techniques using complex architectural models, including Frank Lloyd Wright's "Robie House."

 
Citation:
Georges Winkenbach and David H. Salesin. Computer-Generated Pen-and-Ink Illustration. Proceedings of SIGGRAPH 94 (Orlando, Florida, July 24-29, 1994). in Computer Graphics, Annual Conference Series, 1994.

 
On-line documents:
Available as Technical Report:
TR 94-01-08b [compressed Postscript file, 2.2 Mb]

Interactive Pen-and-Ink Illustration
Abstract:
We present an interactive system for creating pen-and-ink illustrations. The system uses stroke textures--collections of strokes arranged in different patterns--to generate texture and tone. The user"paints" with a desired stroke texture to achieve a desired tone, and the computer draws all of the individual strokes.
The system includes support for using scanned or rendered images for reference to provide the user with guides for outline and tone. By following these guides closely, the illustration system can be used for interactive digital halftoning, in which stroke textures are applied to convey details that would otherwise be lost in this black-and white medium.
By removing the burden of placing individual strokes from the user, the illustration system makes it possible to create fine stroke work with a purely mouse-based interface. Thus, this approach holds promise for bringing high-quality balck-and white illustration to the world of personal computing and desktop publishing.

 
Citation:
Michael P. Salisbury, Sean E. Anderson, Ronen Barzel, and David H. Salesin. Interactive Pen-and-Ink Illustration. Proceedings of SIGGRAPH 94, in Computer Graphics Proceedings, Annual Conference Series, pages 101-108, July 1994.

 
On-line documents:
Available as Technical Report:
TR 94-01-07b [compressed PostScript file, 10.3M]

Multiresolution Curves
Abstract:
We describe a multiresolution curve representation, based on wavelets, that conveniently supports a variety of operations: smoothing a curve; editing the overall form of a curve while preserving its details; and approximating a curve within any given error tolerance for scan conversion. We present methods to support continuous levels of smoothing as well as direct manipulation of an arbitrary portion of the curve; the control points, as well as the discrete nature of the underlying hierarchical representation, can be hidden from the user. The multiresolution representation requires no extra storage beyond that of the original control points, and the algorithms using the representation are both simple and fast.

 
Citation:
Adam Finkelstein, David H. Salesin. Multiresolution Curves. In Proceedings of SIGGRAPH '94, pages 261-268. ACM, New York, 1994.

 
On-line documents:
Available as Technical Report:
TR 94-01-06b [compressed PostScript file, 352Kb]

Multiresolution Painting and Compositing
Abstract:
We describe a representation for "multiresolution images"--images that have different resolutions in different places--and methods for creating such images using painting and compositing operations. These methods are very easy to implement, and they are efficient in both memory and speed. At a particular resolution, the representation requires space proportional only to the amount of detail actually present, and the most common painting operations, "over" and "erase," require time proportional only to the number of pixels displayed. Finally, we show how "fractional-level zooming" can be implemented in order to allow a user to display and edit portions of a multiresolution image at any arbitrary size.
Citation:
Deborah F. Berman, Jason T. Bartell, David H. Salesin. Multiresolution Painting and Compositing. Proceedings of SIGGRAPH 94, in Computer Graphics Proceedings, Annual Conference Series, 85-90, July 1994.
On-line documents:
Available as Technical Report:
TR 94-01-09b [compressed PostScript file, 8.8 Mb]

Wavelet Radiance
Abstract:
In this paper, we show how wavelet analysis can be used to provide an efficient solution method for global illumination with glossy and diffuse reflections. Wavelets are used to sparsely represent radiance distribution functions and the transport operator. In contrast to previous wavelet methods (for radiosity), our algorithm transports light directly among wavelets, and eliminates the pushing and pulling procedures.

 
The framework we describe supports curved surfaces and spatially-varying anisotropic BRDFs. We use importance to make the global illumination problem tractable for complex scenes, and we use a final gathering step to improve the visual quality of the solution.

 
Citation:
Per H. Christensen, Eric J. Stollnitz, David H. Salesin, and Tony D. DeRose. Wavelet radiance. In G. Sakas, P. Shirley, and S. Müller, editors, Photorealistic Rendering Techniques, pages 295-309. Springer-Verlag, Berlin, 1995.

 
Reprinted from Proceedings of the Fifth Eurographics Workshop on Rendering (Darmstadt, Germany, June 1994), pages 287-302.

 
On-line documents:
Complete article [Acrobat file, 263 Kb]
Complete article [compressed PostScript file, 1.4 Mb]

Electronic ``How Things Work'' Articles: Two Early Prototypes
Abstract:
The Electronic Encyclopedia Exploratorium (E3) is a vision of a future computer system--a kind of electronic ``How Things Work'' book. Typical articles in E3 will describe such mechanisms as compression refrigerators, engines, telescopes, and mechanical linkages. Each article will provide simulations, 3-dimensional animated graphics that the user can manipulate, laboratory areas that allow a user to modify the device or experiment with related artifacts, and a facility for asking questions and receiving customized, computer-generated English language explanations. In this paper, we discuss some of the foundational technology--especially focusing on topics in articial intelligence, graphics, and user interfaces--needed to achieve this long-term vision. We describe our two initial prototypes and the technical lessons we've learned from them.

 
Citation:
F. Amador, Deborah Berman, Alan Borning, Tony D. DeRose, Adam Finkelstein, D. Neville, David Notkin, David H. Salesin, Michael Salisbury, J. Sherman, Y. Sun, D. Weld, G. Winkenbach. Electronic ``How Things Work'' articles: Two early prototypes. IEEE Transactions on Knowledge and Data Engineering 5(4): 611-618, August 1993.

 
On-line documents:
Earlier version of article [Postscript file, 306 Kb]

A Continuous Adjoint Formulation for Radiance Transport 
Abstract:
We describe a continuous adjoint formulation for radiance transport that allows a global illumination algorithm to focus on the directional interactions that contribute most to the visible scene. We show how the adjoint quantity for radiance can be described by an angular distribution that is only piecewise-continuous. This observation motivates the formulation of a related adjoint quantity, called exitant directional importance, whose angular distribution is continuous. We prove that exitant directional importance is equivalent to radiance in the sense that the two quantities satisfy the same transport equation and can be propagated through the environment in the same fashion.

 
An adjoint formulation can dramatically reduce the time to compute radiosities when much of the scene is invisible. We present some preliminary results that demonstrate how the adjoint formulation for radiance can provide significant speed-ups even when all surfaces are visible.

 
Citation:
Per H. Christensen, David H. Salesin, Tony D. DeRose. Proceedings of the Fourth Eurographics Workshop on Rendering (Paris, France), 95-104, 1992.

 
On-line documents:
Article without figures [Acrobat file, 107 Kb]

Reconstructing Illumination Functions with Selected Discontinuities 
Abstract:
Typical illumination functions contain boundaries that are discontinuous in intensity or derivative. These discontinuities arise from contact between surfaces, and from the penumbra and umbra boundaries of shadows cast by area light sources. In this paper, we present an algorithm that allows for smooth (C1) reconstruction of intensity everywhere across a surface except along selected edges of intensity or derivative discontinuity. The reconstruction algorithm is based on a piecewise-cubic scattered data interpolation method originally proposed by Clough and Tocher. Our results show marked improvement over piecewise linear or C1 quadratic reconstructions of some simple illumination functions.

 
Citation:
Dani Lischinski, Tony D. DeRose, David H. Salesin. Proceedings of the Third Eurographics Workshop on Rendering (Bristol, England), 99-112, 1992.

 
On-line documents:
Article without figures [Acrobat file, 155 Kb]