Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!caip!rutgers!sri-spam!nike!ucbcad!ucbvax!ucsfcgl!pixar!ph
From: ph@pixar.UUCP (Paul Heckbert)
Newsgroups: net.graphics
Subject: Re: Possible way of anti-aliasing.
Message-ID: <109@pixar.UUCP>
Date: Thu, 2-Oct-86 21:28:45 EDT
Article-I.D.: pixar.109
Posted: Thu Oct  2 21:28:45 1986
Date-Received: Sat, 4-Oct-86 11:09:02 EDT
References: <280@joevax.UUCP> <265@hoqam.UUCP> <7706@sun.uucp>
Distribution: net
Organization: Pixar -- Marin County, California
Lines: 65
Summary: cause of aliasing, some approaches and references


    [This is a repeat of my posting of 21 Sept, which apparently died
     before it reached most of you; too bad the net's so flaky!]

In article <323@axiom.UUCP>, gts@axiom.UUCP (Guy Schafer) writes:
> How is anti-aliasing done?
> Just averaging the (color, intensity, brightness?) of the two cells adjacent
> to any object boundary sounds good but there are a few problems ...

First a nutshell explanation of the cause of aliasing.
It results because a continuous image (either natural or synthetic) is being
sampled on a discrete grid of pixel locations.  Signal theory tells us that
when a continuous image is sampled, frequencies higher than half the
sampling rate will look like ("alias") as lower frequencies.  A simple
example of temporal (rather than spatial) aliasing is the "wagon wheel effect"
seen on film and TV.

To eliminate aliasing, one can either

    a) increase the sampling rate to twice the highest frequency in
       the image (go to higher resolution)
or  b) low pass filter (blur) the image BEFORE SAMPLING to eliminate
       unreproducible high frequencies

The method you suggested, filtering after sampling, is a third possibility,
but this approach gets very clumsy because of the difficulty
of inferring the true edge locations after sampling has been done.
It's the method used at NYIT [Jules Bloomenthal, `Edge Inference with
Applications to Antialiasing', SIGGRAPH '83].  This method is conceptually
flawed so I wouldn't recommend it (I used to work there, so I know!).

Using approach (a) above you either point sample at high resolution
(say 2000 or 4000 line) and output at that high resolution, which is pretty
much what Digital Productions does, or sample at high resolution and average
the image down to medium resolution (say 500 line), which is what most folks
in the TV graphics business do, if they do antialiasing at all.

The theoretically "correct" approach is (b), however: analytic antialiasing.
Algorithms have been developed for simple objects such as lines and
polygons, but analytic antialiasing of curved surfaces is an open problem.

Of course, the ultimate place to learn about computer graphics is not USENET,
but your local library.  I recommend:

    Frank Crow, `The Aliasing Problem in Computer-Generated Shaded Images',
    Communications of the ACM, Nov. 1977

    Eliot Feibush, Marc Levoy, Robert Cook,
    `Synthetic Texturing Using Digital Filters', SIGGRAPH '80

    any recent ACM SIGGRAPH proceedings

    David F. Rogers, `Procedural Elements for Computer Graphics',
    McGraw-Hill, 1985  ( contains pseudocode for antialiasing lines )

The latter is the only book on image synthesis I know of; I highly recommend it.
With any antialiasing method it is essential that you properly compensate for
intensity nonlinearities in your CRT or film recorder or your attempts
at antialiasing will be disappointing.  Rogers' book discusses this
`gamma correction' problem.

Paul Heckbert
Pixar				415-499-3600
P.O. Box 13719			UUCP: {sun,ucbvax}!pixar!ph
San Rafael, CA 94913		ARPA: ph%pixar.uucp@ucbvax.berkeley.edu