Character generation under grid constraints

ABSTRACT

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.

REFERENCES

• 1: Coueignoux, P.,"Character Generation by Computer," Computer Graphics and Image Processing, Vot 16, pp 240-269, 1981
• 2: CORPORATE Adobe Systems Inc., PostScript language reference manual (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 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: R. D. Hersch, Real scan-conversion of shape contours, CG International '87 on Computer graphics 1987, p.207-220, June 1987, Karuizawa, Japan
• 7: Bresenham, J.E.,"Algorithm for computer control of a digital plotter," IBM Systems Journal, Vol 4, No 1, 1965, pp 25-30
• 8: Jack Bresenham, A linear algorithm for incremental digital display of circular arcs, Communications of the ACM, v.20 n.2, p.100-106, Feb. 1977 [doi>10.1145/359423.359432]
• 9: M. D. McIlroy, Best approximate circles on integer grids, ACM Transactions on Graphics (TOG), v.2 n.4, p.237-263, October 1983 [doi>10.1145/245.246]
• 10: James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 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: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• 13: Vaughan Pratt, Techniques for conic splines, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.151-160, Jul. 1985
• 14: Pitteway, M., "Algorithm for Drawing Ellipses or Hyperbolae with digital plotters," Computer Journal, Vol 10, No 3, pp 282-289, Nov. 1967
• 15: David F. Rogers, Procedural elements for computer graphics, McGraw-Hill, Inc., New York, NY, 1984
• 16: Hourdequin, M., Coueignoux, P., "Specifying arbitrary planar smooth curves for fast drawing", Proceedings Eurographics Conference, Bologna 1979, pp 193-211

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Digitizing and scanning

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

  J. Computer Applications

General Terms:
Algorithms, Design