Path: utzoo!utgpu!watmath!att!dptg!ulysses!andante!alice!td
From: td@alice.UUCP (Tom Duff)
Newsgroups: comp.graphics
Subject: Re: Gray scale fonts, question of availability
Summary: simple, extremely effective algorithm
Message-ID: <10038@alice.UUCP>
Date: 20 Oct 89 17:19:47 GMT
References: <23018@cup.portal.com> <4782@internal.Apple.COM> <14160@well.UUCP>
Organization: AT&T Bell Laboratories, Murray Hill NJ
Lines: 57

If you have character outlines and want grey-scale fonts, the best
algorithm known is described in the paper
	Polygon Scan Conversion by Exact Convolution
	by Tom Duff, AT&T Bell Laboratories, Murray Hill, NJ 07974
	in Proceedings of RIDT '89 (International Workshop
	on Raster Imaging and Digital Typography)
	Cambridge University Press, 1989

By `best algorithm known' I mean that the algorithm produces
results that are indistinguishable from perfection, and runs
pretty quickly as well.

(I hesitate to mention that I am the Tom Duff named above,
since that might be construed as blowing my own horn.)

The short summary is as follows:
To area-sample a polygon, we can just clip it to each pixel
and compute the areas of the clipped polygons, using the
trapezoid decomposition (called `Newell's algorithm' by
some, although it's older than Newell's grandmother.)

But, all that clipping can be pretty expensive.  You
can get rid of most of it by noticing pixels that
have simple structure (e.g. those crossed by zero or
one edge.)
But, we can do better than that.  The algorithm in the
paper above does no polygon clipping at all.

Notice that all the edges of the clipped polygons
are pieces of edges of the original polygon, or of the
pixel edges.  The contributions of the original polygon's
edges can be computed by dicing the edges by the pixel
boundaries using the symmetric DDA.  The contributions
of the pixel edges are even easier.  The vertical edges
contribute zero, since the trapezoids are of zero width.
The bottom edges likewise contribute zero, since the
trapezoids are of zero height.  This leaves just the
top edges.  Their contributions can be computed using
a regular old non-antialised scan-conversion algorithm,
but computing the pixel-spans on each scan line to
floating-point (or scaled-integer) precision.

Essentially the same algorithm can be used to sample
with a higher-order kernel, because the trapezoid
decomposition doesn't work only to calculate area,
but for any integral at all, including the convolution
integral.  (This is a simple consequence of Green's
theorem.)

What kernel should you use?  I recommend the
separable 2d version of the Catmull-Rom cubic
spline.  Mitchell and Netravali (in a Siggraph 88
paper) recommend a kernel that's 2/3 of the
Catmull-Rom kernel plus 1/3 of the uniform
cubic B-spline kernel (again, the 2d separable
version.)  Mitchell & Netravali know better than
I, having done some experimental evaluation.