Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!cbatt!ihnp4!qantel!lll-lcc!pyramid!decwrl!sun!falk
From: falk@sun.uucp (Ed Falk)
Newsgroups: net.graphics
Subject: Re: Possible way of anti-aliasing.
Message-ID: <7706@sun.uucp>
Date: Sat, 27-Sep-86 18:53:25 EDT
Article-I.D.: sun.7706
Posted: Sat Sep 27 18:53:25 1986
Date-Received: Tue, 30-Sep-86 07:22:44 EDT
References: <280@joevax.UUCP> <265@hoqam.UUCP>
Distribution: net
Organization: Sun Microsystems, Inc.
Lines: 77

> Why is this technique called "anti-aliasing"?
> 
Mini-lecture:



It comes from data analysis.  Suppose I am sampling an electrical signal
digitally.  I can't make a continuous sample, so I settle for taking sample
points at certain intervals, say 100hz.  Now, suppose there's a 101 hz sine
wave coming in.  My sample points look like this:

  **        **        *         *         *         *         *         *      
 *  *      *  *      * *       * *       * *       * *       * *       * *     
 *  *      *  *      * *      *   *     *   *     *   *     *   *     *   *    
*   *     *   *     *   *     *   *     *   *     X   *     X   *     X   *    
*    *    *    *    X   *     X   *     X   *     *   *     *   *     *   *    
X----*----X----*----*---*-----*----*----*----*----*---*-----*---*-----*---*----
     *    *    *    *    *   *     *   *     *   *    *    *     *   *     *   
      *  *      *  *     *   *     *   *     *   *     *   *     *   *     *   
      *  *      *  *     *   *     *   *     *   *     *   *     *   *     *   
      *  *      *  *      * *       * *       * *       * *       * *       * *
       **        **        *         *         *         *         *         * 

where the "X"s represent the actual samples I take.

If I only look at the points I sampled, I see


                                                                               
                                                                               
                                                                               
                                                  X         X         X        
                    X         X         X                                      
X---------X--------------------------------------------------------------------






As you can see, this masquerades ("aliases") as a much lower frequency
(1 hz to be precise).  In order to avoid this effect, you have to sample
at at least twice the highest frequency you will be recording, or put
a low-pass filter in front of your recorder.
You get almost identical results sampling a 99hz input.

It turns out that this happens not just for signals over time, but for
signals over space.  An image is nothing more than signals over space in
two dimensions.  An extreme case of this effect is the "picket fence"
problem:  Suppose you render an image of a picket fence in the distance.  The
fence has pickets whose spatial frequency (pickets/inch) is very close to
the image pixel resolution (pixels/inch).  For example, if your pixel
resolution is 100 pixels/inch, and I have an image with 101 pickets per inch,
I'll get the effect of one picket per inch on the screen.

These are extreme examples, but you get the idea.  More typical examples are
polygons or lines with sharp edges.  The visual effect is of "jaggies" along
the sharp edge.  In image rendering, a sharp edges is just like the leading
(or trailing) edges of a square wave or pulse in a signal over time -- it's
just loaded with high frequencies.

The solution for these 2-d spatial aliasing artifacts is exactly the same
as for 1-d temporal aliases:  take more samples or filter the input.

Taking more samples is conceptually easy, just get a higher resolution
display and compute more pixels.  But this is expensive.

Since the image never had an analog stage, you can't actually filter the
input, but you can fake it in various ways.  The typical "anti-aliasing"
technique is to take higher-resoution samples in the neighborhood of
a high-frequency edge and average them together to do a sort of digital
filtering on the affective pixels.  Whole books have been written
(or at least ought to be) on how to do the digital filtering.
-- 
		-ed falk, sun microsystems
			falk@sun.com
			sun!falk