236 Project

Painty Paint!

(turned into Multiresolution Paint for DAB)

proposal and progress reports are here

cool pictures at the bottom

Final Report
Multiresolution Paint within the DAB painting system
Vincent Scheib


The desired implementation of a multiresolution image format within the DAB system was not accomplished. The motivation for a multiresolution image format, specific requirements it must meet, and the complications encountered while trying to implement a system into DAB are described. 

Attention is given to the topic of multiresolution images, and specifically wavelet based images, as I was not familiar with the concepts, and they proved more difficult than I had expected. 

Finnaly, an implementation of a multiresolution image was completed, using only the 'over' painting operation (alpha blending).

Multiresolution Painting

A raster image samples a 2D function, usually of color, discretely. A multiresolution image allows for the sampling frequency to vary, possibly arbitrarily and or unboundedly. 

The most commonly desired feature of multiresolution images is the following:

Detail can be added at any place. There is no limit to the detail which can be added. This allows for images to contain dramatic scale differences.

How a Multiresolution Canvas Would Improve DAB

DAB uses a 2D paint blending algorithm to simulate a brush being moved across it’s surface. Between two discrete locations of a brush in time, the footprint of that brush (the part in contact with the surface being painted) must be simulated to be in contact with the canvas. 

Thus, for each discrete position between the current position of the brush and the last position, each portion of the footprint must be blended with a portion of the canvas. 

Because the footprint is 2D, and each pixel in the footprint is unique, an n2 algorithm must be used at each position. The footprint is moved along a line or curve, and is blended m times. Thus the paint blending operation is O(n2m), and because both n and m rely on the resolution of the canvas, it is truly O(r3), where r is the resolution of the canvas.

A Multiresolution implementation of the canvas would allow all paint operations to occur at a fixed resolution, for which the system operates at an interactive rate, regardless of the detail present on the canvas.

Currently, the system [duel GigaHertz  processors, Gig of RAM] is barely able to support a 1024x1024 image, which is not a sufficient resolution when an artist is expected to be creating high quality work.

Further, the basic ability to allow the artist to zoom in to any detail to work would be most useful. A computer monitor is limited in the scale of images it can display. An artist, theoretically, could work on a mural the size of a wall within DAB, if only they could navigate it and maintain interactive rates. 

Working on such large images would require enormous amounts of memory. However, if memory can be used only when required to store high detail work, then this limitation can be drastically reduced. An easy example is a painting signed by an artist. The small signature may require much higher detail than the rest of the image. 


One method used to create multiple resolution images is known as Re-execution. An image at arbitrary resolution can be generated if the artist’s movements are recorded, and then executed again at another resolution. This allows the artist to work interactively at a low resolution, while the high resolution can be computed later at less than interactive speeds. 

However, This method was not feasible to implement with DAB in its current state. The complex 3D footprint of the brush in DAB is highly dependant on the simulation and subdivision systems. Correctly recreating these at higher resolutions is non trivial, and not part of the system which I am familiar with. 

Additionally, this contradicts one of the important features of DAB: Artist’s interaction in a WYSIWYG environment. The artist currently can see exactly what they are producing, where a re-execution strategy would not allow this. Specifically over large scale factors. E.G. an artist can not carefully place detail which is at 32 times the resolution they are working in. 

Separation of Layers

The original method I had intended to work with was a separation of layers approach. New images would be dynamically created at appropriate resolutions to contain the detail work of the artist. In essence, the image would have many high resolution insets. 

There are complicated problems at the borders between resolutions. Applying scale changes to propagate work across these boundaries generates many special cases. EG, a 2x resolution brush stroke crossing over a T boundary between 1x, 4x, and 8x image segments requires a rather complicated software implementation. 

Ken Perlin, and  Luiz Velho offer a better argument against this method in [3] (section 3). Besides boundary issues, they point out issues in updating. Specifically, if an artist draws at high resolution, then over that area in a low resolution, and then again at a high resolution, the system must maintain a record of when each operation was performed. They are focusing on the ‘over’ paint operation, which is a simple alpha blending of paint over old paint. They note that this operation is non-commutative (A over B over C is not equal to B over A over C). 

This approach was taken by Takeo Igarashi and Dennis Cosgrove in [2]. They designed a system for ‘casual painting’ of 3D objects. The object is given a solid base color. Painting a portion of the object causes the generation of an small image for just the portion of the texture map. Multiresolution capability is provided by always using the screen resolution when creating a new image. The user can zoom in and paint very fine detail. It will be captured at the resolution of the screen. These sub images always replace whatever image was previously there. Painting over high resolution with a low resolution causes the high resolution to be destroyed. The authors noted several limitations to this method for anything beyond simple ‘casual’ painting. 

Lazy Evaluation

Deborah F. Berman, Jason T. Bartell, and David H. Salesin offer a very attractive approach to the problem in [1]. I worked to extend this method, and will explain their approach.

The lazy evaluation is well suited to a Bandpass pyramid. Perlin and Velho describe the Lowpass and Bandpass pyramids well in section 2 of [4]. Simply, the lowpass pyramid contains the image at many resolutions, where the bandpass pyramid contains the difference of the image at one higher resolution. Thus, the bandpass pyramid starts with one pixel, and each additional image can be added to the previous image to gain further detail.

The bandpass pyramid therefore has the advantage that information is not stored redundantly. Specific frequencies are stored at only one level. Roughly put, modifying the image at a specific resolution requires only an update at that specific resolution, the enormous amount of pixels at higher resolutions need not be modified directly. 

Berman et al make use of the Haar wavelet, the simplest wavelet basis. This provides a form of a bandpass pyramid, however the wavelet representation is not essential to their multiresolution algorithm. Detailed information on the Haar wavelet, and how it can be used in computer graphics, can be found in [5] and [6]. I found this informative, however not critical to the problems I am trying to address. The Haar wavelet is so simple, it need not even be used. In [3] a B-Spline wavelet is used, for increased image quality when decomposing and extrapolating data. However, the problems encountered deal with principles common to all bandpass pyramids, regardless of which wavelet is used. 

They key to the lazy evaluation is to not be forced to modify data until it is displayed. The paper presents an order O(m+j) algorithm for display. Painting operations occur in a fixed resolution image cache. When the user navigates to other portions or scales of the image, the data structure is updated to reflect the changes made. 

The paint operations of ‘over’, ‘under’, ‘in’, and ‘erase’ are supported. These are very basic painting operations, which rely basically on an alpha blending operation. It is worthwhile to consider the ‘over’ operation in detail.

Over is defined as: 
NewColor = AppliedColor * alpha + PreviousColor * (1 - alpha)

In the bandpass pyramid, the current color is available at a node, and the difference from that color to the next higher resolution is stored. Modifying the current color is a trivial task up updating the difference from the previous node. Updating the higher resolution data is where this representation excels. In a lowpass pyramid all higher resolution pixels would require updating. However, in the bandpass pyramid, these are stored as a difference from the current node. The ‘over’ operation obscures these pixels partially. Therefore, the differences of the higher resolution pixels need only be scaled down! This can be accomplished by storing a single scaling factor in each node. Only a node at the current resolution must be updated. During display, scaling factors are accumulated together as the tree is traversed. 

This is very significant because it avoids modifying such large volumes of data. I attempted to find similar methods for use with DAB.

DAB and the Lazy Evaluation Method: parts that work

Currently DAB makes use of 9 channels of information (3 Color for wet paint, 3 Color for dry paint, 3 Volume representations (1 wet, 2 dry)), compared to the RGBA of most paint programs. 

The difficulty is in finding an extrapolation scheme. When a user paints over an area of higher resolution the high resolution data must be updated. Berman et al found that the ‘over’ and ‘erase’ operations can be handled most efficiently by storing the scalar of occlusion. The blending operations in DAB are more complex than this, however. 

The dry volume information in DAB poses a difficulty only in the drying process. The user can not dry paint selectively in DAB, and therefore we need not concern ourselves with it’s extrapolation. The only problem with drying in a multiresolution image is that the entire canvas must be dried at once. This operation is almost non-interactive already for a 1024x1024 image. Amortizing this cost was considered by drying only a portion of the image at a time. However, this would cause artifacts to show up if the user paints over a ‘just dried’ region and a ‘soon to be dried’ region. The paint deposited in the two regions will differ, and the bump map rendering of the height field will show this boundary artifact. 

The drying operation also suffers from requiring a decomposition of the entire image. All the highest resolution pixel values must have their volume adjusted, but their color values must be adjusted as well. The drying operation modifies the color of the ‘dry layer’ such that after the drying operation, the color of the blended wet layer over dry layer is the same. Performing this color blending will require an full decomposition of the highest resolution – touching every node in the tree. 

The wet volume information could be handled in the following way. As the user paints, record the difference in paint volume from when the user started painting. If the paint volume has decreased, multiply all higher resolution volume units by NewPaintVolume / OldPaintVolume. This will remove the correct volume of paint from the high resolution pixels. It will also maintain the high frequency detail. 

If volume has been added, it can be added to the high resolution pixels in a constant manner. 

DAB and the Lazy Evaluation Method: parts that do not work

The above considerations affect only the efficiency of the algorithm. The true problem is with color blending as the user paints. DAB differs from most painting programs in that it uses a bi-directional blend operation. 

Berman et al used only simple paint operations which effectively cover higher resolution data. In effect, they can store all the user’s work in a ‘foreground image’, and then apply those changes to the image below. In the multiresolution case, this simply requires applying the changes to possibly many pixels for each foreground image. However, lazy evaluation works here because all the changes can be gathered in one layer, and then applied with one operation.

DAB can not use lazy evaluation. The bi-directional blending operations use both the foreground and background images at each simulation step. A separation can not be made between the current user’s work, and the canvas below. 

Thus, the user actually changes all paint on any pixels that they touch. This can not be applied in a partial manner to the high resolution pixels in that area. Therefore, the high resolution data is simply lost. But the actual changes made by the user should not destroy the high resolution information. 

An example:

· The user zooms to very high resolution, and paints. Varying color and volume information is deposited on the canvas. 
· The user then zooms out to a lower resolution. A glazing brush stroke is applied over a large portion of the high detail work. The glazing stroke is not completely opaque – the color of the paint below shows through, as does its volume. 
· Additionally, (and this is where DAB differs from others) the high detail paint has been blended into the brush, and back down to the canvas. Paint is not simply added to the canvas, it is taken away, modified, and replaced many times. It is clear from current work with DAB that this operation will not obliterate the previous paint, but only modify it. 

I have failed to find a method to lazily modify the paint model in this situation. 

The brute force approach would be to store each simulation step taken, the paint removed and added in each step, for each pixel, and to re-execute all those simulation steps for all higher resolution pixels. This would not be accurate, because the operations performed on the lower resolution image may differ from the high resolution due to clamping of volume to the 0 – 1 range. Additionally, this would require very large amounts of dynamic storage. 

Ignoring the multiple blending operations, and attempting to blend from the final result has not lead to a solution either. 


A solution for multiresolution painting within the DAB system was not found to be feasible. The available literature on multiresolution painting deals only with the simplest of paint blending operations, and does not extend to the paint model used in DAB. The interactive constraint, including the artist’s ability to see exactly the detail that they are painting, further limit the options available. 

Aditional Work

Everything in this report is the result of reading papers and working things out on paper. For project day, it is nice to have a demo. Thus, I put together a very quick implementation of the system described in [1]. I did not use wavelets, and the system still works, I am still not sure why they used wavelts in that system. 

Screen Shots and Breif Description:

multiresolution painting
Zooming in by 223, or 838,608 times!
Painting at the lowest resolution will 
update even the finest detail at the highest resolution.

This single multiresolution image contains all of the slides I used to give my presentation (they're just inside the 'c' in "Scheib"). The slide focused on here is sketching out the general idea of having a large image with just portions at high detail. The entire multires image loaded from disk in about 10 seconds. 

The multiresolution painting program allows the user to zoom in and add detail anywhere. Zooming out and painting over the highest resolution areas is still fast and efficient. The smallest text in the image, saying “Paint Over Me” can be covered with a thin layer of paint while not destroying it. This can be done even when zoomed out all the way. A 'regular' image could not allow this, because far too many pixels would be modified at once. 

If the entire image had been stored at the resolution of the finest details, it would be 223 X 223 = 70,000,000,000,000 pixels in size!

During the presentation, the text “Paint Over Me” was displayed 3 feet tall. If the entire image could have been shown at that resolution, it would be 595 miles tall!

A bug in an early implementation:
oddly coupled Sierpinski Triangles.

A bandpass quadtree is used to store the image. The tree must be traversed ouside of the active image area in order to reach some of the final pixel values. However, traversing the entire tree would be far too costly. The tree must be pruned carefully, allowing steps outside the active area, but once outside only moving back towards the active area. 


Deborah F. Berman, Jason T. Bartell, and David H. Salesin
Multiresolution Painting and Compositing (1994) 

Takeo Igarashi and Dennis Cosgrove
Chameleon : 3D Paint for Teddy 2001

Ken Perlin Luiz Velho 
B-spline Wavelet Paint   (1994?) 

Ken Perlin, Luiz Velho
Live Paint: Painting with Procedural Multiscale Textures (1995) 

Eric J. Stollnitz Tony D. DeRose David H. Salesin
Wavelets For Computer Graphics, A Primer: Part 1&2  (1995)