jxh@cup.portal.com (Jim - Hickstein) (10/13/89)
Does anyone out there sell gray-scale fonts in small-cell sizes (i.e. around 9x16), or software that implements the various filtering algorithms in the literature? I ought to ask before I go ahead and do it all myself. I especially want proportionally-spaced fonts. -Jim Hickstein jxh@cup.portal.com ...!sun!portal!cup.portal.com!jxh
turk@Apple.COM (Ken "Turk" Turkowski) (10/17/89)
In article <23018@cup.portal.com> jxh@cup.portal.com (Jim - Hickstein) writes: >Does anyone out there sell gray-scale fonts in small-cell sizes (i.e. >around 9x16), or software that implements the various filtering algorithms >in the literature? I ought to ask before I go ahead and do it all myself. >I especially want proportionally-spaced fonts. Note that ther is a difference between gray-scale fonts and anti-aliased fonts. The latter assumes some kind of linear filtering to avoid aliasing in the frequency domain, and the former assumes no such thing, and may use nonlinear filters which do result in aliasing, but may produce better quality results. -- Ken Turkowski @ Apple Computer, Inc., Cupertino, CA Internet: turk@apple.com Applelink: TURKOWSKI1 UUCP: sun!apple!turk
nagle@well.UUCP (John Nagle) (10/19/89)
It should be straightforward to turn a character outline into a grey-scale bitmapped character. The obvious approach is to generate the font in a large size, impose the grid of the desired smaller bitmap over the large one, and tally the number of pixels on in each square of the smaller bitmap to get a density value. One might be able to do better than this, but it's worth a try as a first cut. John Nagle
td@alice.UUCP (Tom Duff) (10/21/89)
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.
jxh@cup.portal.com (Jim - Hickstein) (10/25/89)
Thanks for the pointers to algorithms, although I already have plenty. I need implementations: source code. I don't have time to write it myself. Or fonts, themselves. Helvetica Condensed would do nicely (9x12 cells). And yes, I did mean anti-aliased, not simply grey-scale. Keep those cards and letters coming! -Jim Hickstein jxh@cup.portal.com ...!sun!portal!cup.portal.com!jxh