Reconstruction Filters in Computer GraphicsDon P. MitchellArun N. NetravaliAT&T Bell LaboratoriesMurray Hill, New Jersey 07974Many conversions between continuous and discrete representations mayoccur in the course of generating an image. For example when ray trac-ing a texture-mapped surface, a photograph may be sampled by a digi-tizer to define the texture, then the texture samples are interpolated andresampled when a ray strikes the textured surface, the ray samples areinterpolated and resampled to generate pixel values, and the pixels areinterpolated by a display and finally resampled by retinal cells when theimage is viewed. Resampling may be more explicit, as in enlarging orreducing a digital image or warping an image (e.g., with Catmull andSmith's algorithm [CAT80]). Each of these conversions can introduceconspicuous errors into an image.Errors introduced by sampling (e.g., aliasing) have received considerableattention in the graphics community since Crow identified this as thecause of certain unwanted artifacts in synthetic images [CRO77]. Alias-ing in images was discussed in the classic 1934 paper by Mertz and Gray[MER34]. Their discussion contains a description of artifacts well-known to graphics researchers today and shows that the condition forpreventing aliasing was known, as a rule of thumb, long beforeShannon's proof of the sampling theorem:The interference usually manifests itself in the form of serra-tions on diagonal lines and occasional moire effects in thereceived picture. Confusion in the signal may be practicallyeliminated by using an aperture of such a nature that it cutsoff all [Fourier] components with n numbers greater thanN/2 [half the scanning rate] ....By comparison, the problems introduced by reconstruction have beensomewhat neglected in the graphics literature. Reconstruction can beresponsible for aliasing and other types of distortion that mar the subjec-tive quality of an image. This paper will focus on the effects of recon-struction and how to design filters for graphics applications.2. Aliasing Caused by ReconstructionAliasing in synthetic images is a serious problem and still not completelysolved. In other digital-signal-processing applications, aliasing is elim-inated by prefiltering signals before sampling, as illustrated in Figure 1.Note that it is the prefiltered signal that is reconstructed in this case.While prefiltering is the classic solution to aliasing problems, there is aspecial problem encountered in computer graphics. Many syntheticimages originate from what we will call procedural signals, in which the221ABSTRACTProblems of signal processing arise in imagesynthesis because of transformations betweencontinuous and discrete representations of 2Dimages. Aliasing introduced by sampling hasreceived much attention in graphics, but recon-struction of samples into a continuousrepresentation can also cause aliasing as wellas other defects in image quality. The prob-lem of designing a filter for use on images isdiscussed, and a new family of piecewisecubic filters are investigated as a practicaldemonstration. Two interesting cubic filtersare found, one having good antialiasing pro-perties and the other having good image-quality properties. It is also shown that recon-struction using derivative as well as amplitudevalues can greatly reduce aliasing.CR Categories and Subject Descriptions: 1.3.3 [ Computer Graphics ]:Picture/Image Generation; 1.4.1 [ Image Processing ]: DigitizationGeneral Terms: AlgorithmsAdditional Keywords and Phrases: Antialiasing, Cubic Filters, Filters,Derivative Reconstruction, Reconstruction, Sampling1. IntroductionThe issues of signal processing arise in image synthesis because oftransformation between continuous and discrete representations ofimages. A continuous signal is converted to a discrete one by sampling,and according to the sampling theorem [SHA49], all the information inthe continuous signal is preserved in the samples if they are evenlyspaced and the frequency of sampling is twice that of the highest fre-quency contained in the signal. A discrete signal can be converted to acontinuous one by interpolating between samples, a process referred to inthe signal-processing literature as reconstruction.signal is only implicitly defined by an algorithm for computing pointsamples. Operations that require an explicit representation of the signalcannot be performed, and in particular, prefiltering is impractical. Thisdifficulty is unique to computer graphics, and ray tracing is the clearestexample of it [WHI80].To explain the role that reconstruction plays in aliasing, it will be helpfulto review briefly the theory of sampling and define the operations ofsampling and reconstruction more precisely. In one dimension, a signalcan be represented by a continuous function f(x). Producing a discretesignal by sampling is equivalent to multiplying by an infinite train ofimpulses known as a comb function:centered at the location of an impulse in the comb. Equation (4) statesthat, in the frequency domain, reconstruction can be interpreted as themultiplication by K(v) which is intended to eliminate all the extraneousreplicas of the signal's spectrum and keep the original base-band cen-tered at the origin. K(v) is indicated by the dashed curve in Figure 2.However, Figure 2 also demonstrates a problem. The replicas of the sig-nal spectrum overlap, and the reconstruction filter can not isolate a pureversion of the base-band signal. When part of the energy in a replica ofthe spectrum leaks into the reconstructed signal, aliasing results. If thebandwidth of the signal were narrower or the sampling rate higher, thecopies would not overlap, and exact reconstruction would be possible.Even if the replicated spectra do not overlap, aliasing can result frompoor reconstruction, as illustrated in Figure 3. When aliasing is a conse-quence of undersampling (or lack of prefiltering), it is referred to asprealiasing, and when it results from poor reconsttuction, it is calledpostaliasing.Figure 4 shows an extreme example of aliasing in an image. In this fig-ure, the two-dimensional signal, f(x,y) = sin(x2+y2), was sampled on a128 x 128 pixel grid. Then, these samples were reconstructed with acubic filter (to be described later in the paper) and resampled to 512 x512 pixels.The rings on the left side of the image are part of the actual signal, butthe rings on the right side are Moire' patterns due to prealiasing. In thecenter of the image is a