“Character generation under grid constraints” by Hersch

An original and fast filling algorithm based on vertical scan line sweep and contour tracking of a presorted shape description allows filling of character shapes with real subpixel resolution. Identical parts of a character lying at a different phase in respect to the grid will have a dissimilar discrete look. Grid constraints are applied in order to force given parts of a character (stems, serifs) to attain identical phasing. So that several contraints may be applied, degrees of freedom are provided in the form of stretchable null-segments inserted at particular locations in the character outline description. Grid constraints are also applied to avoid discrete arcs with an isolated pixel or a long horizontal or vertical run. The type of constraints applied to parts of a character consists only of horizontal or vertical subpixel translations. The resulting character description therefore remains nearly identical to the original description. The processing time used to apply grid constraints is negligible, compared with the time needed for character scan-conversion and filling. Hence, this method is very well adapted for direct character generation on non-impact printers. It is also suitable for character rasterization in typographic computer-aided design systems.

1. Coueignoux, P.,”Character Generation by Computer,” Computer Graphics and Image Processing, Vot 16, pp 240-269, 1981
2. Adobe Systems Inc, Postscript Language Reference Manual, Addison-Wesley, 1985
3. Karow, P., “Elektronische Modifikation grafischer und verbalgrafischer Zeichen,” Deutscher Drucker, Nr. 25, pp.4-8, August 1979
4. Knuth, D., Tex and Metafont, American Mathematical Society, Digital Press, 1979
5. Hersch, R.D., “Descriptive Contour Fill of Partly Degenerated Shapes,” IEEE Computer Graphics and Applications, Vol 6, No 7, July 1986.
6. Hersch, R.D., “Real Scan-Conversion of Shape Contours, ” Proceedings Computer Graphics International 87, Karuizawa, Japan, Ed. T.L Kunii, Springer Verlag, 1987
7. Bresenham, J.E.,”Algorithm for computer control of a digital plotter,” IBM Systems Journal, Vol 4, No 1, 1965, pp 25-30
8. Bresenham, J.E., “A Linear Algorithm for Incremental Digital Display of Circular Arcs,” Communications of the ACM, Vol 20, No 2, Febrary 1977
9. Mcllroy, M.D., “Best Approximate CirOes on Integer Grids,” ACM Transactions on Graphics, Vol. 2, No 4, pp 237-263, Oct 83.
10. Foley, J.D., Van Dam, A., Fundamentals of Interactive Computer Graphics, Addison-Wesley, 1982
11. Ackland, B.D., Weste, NH., “The Edge Flag Algorithm – A Fill Method for Raster Scan Displays,” IEEE Trans. on Computers, Vol 30, No 1, January 1981, pp. 41-48
12. Newman, W.M., Sproull, R.F., Principles of Interactive Computer Graphics, McGraw-Hill, 1979
13. Pratt, v., “Techniques for Conic Splines,” Proceedings of SIGGRAPH’85, (San Francisco, July 22-26,1985). In ACM Computer Graphics, Vol 19, No 3, (July 1985), pp t51-159
14. Pitteway, M., “Algorithm for Drawing Ellipses or Hyperbolae with digital plotters,” Computer Journal, Vol 10, No 3, pp 282-289, Nov. 1967
15. Rogers, D.F., Mathematical Elements for Computer Graphics, McGraw-Hill, New-York, 1976
16. Hourdequin, M., Coueignoux, P., “Specifying arbitrary planar smooth curves for fast drawing”, Proceedings Eurographics Conference, Bologna 1979, pp 193-211