Home
Patent Search
IMT Blog
REGISTER
|
SIGN IN
United States Patent
5781714
Collins , ; et al.
July 14, 1998
Title
Apparatus and methods for creating and using portable fonts
Abstract
A computer system includes a requesting computer which asks a responding computer, such as an Internet server, for one or more portions of text. The responding computer reacts by sending the requested text. The requesting computer can either render the requested text without the text's font shapes, or it can ask the responding computer to send descriptions of such shapes, and then render the text using them. Preferably the font descriptions sent are grouped into sets, or portable font resources ("PFR"); each text sent identifies the one or more PFRs needed to define its font shapes; and the requesting computer asks for PFRs identified in texts it receives. The fonts and characters within fonts represented by each PFR vary as a function of its associated text. For each character to be rendered, the requesting computer finds which PFR associated with the character's text describes its shape, and uses that font description to render that shape. The responding computer can install such new font descriptions into its operating system, so character shapes can be rapidly rendered by standard operating system calls. The responding computer can translate a text's pre-defined font description into new font descriptions which depend only on character-font shapes. The responding computer can receive a changed body of text and a corresponding old set of PFRs, and derive a new set of one or more PFRs as a function of which character-font shapes occur in the changed text.
Inventors:
Collins; John S.
(Boston,
MA
)
, Goldwater; Mark H.
(Norfolk,
MA
)
Assignee:
Bitstream Inc.
(Cambridge,
MA
)
Appl. No.:
527518
Filed:
September 12, 1995
Current U.S. Class:
345/471
Field of Search:
395/167-172,141-143 382/177-180,190-194
U.S. Patent Documents
4785391
November 1988
Apley et al.
5099435
March 1992
Collins et al.
5167016
November 1992
Bagley et al.
5309554
May 1994
Ito
5355449
October 1994
Lung et al.
5473709
December 1995
Aoki
5473743
December 1995
Watanabe
Foreign Patent Documents
0-480-399-A2
Apr., 1992
EP
0-534-622-A2
Mar., 1993
EP
0-583-548-A1
Feb., 1994
EP
Other References
Electronic Documents: A White Paper, .COPYRGT. 1993, by No Hands Software, 1301 Shoreway Road, Suite 220 Belmont, CA 94002. .
The Dawn of Easy Electronic Documents?, .COPYRGT. 1993 by Info World Publishing Company, vol. 9, Issue 14, pp. 4-8. .
Fonts and Output Issues, The Seybold Report of Desktop Publishing, Apr. 8, 1991, pp. 27-30. .
Tools Review on Common Ground, Adobe Acrobat Exchange and Adobe Acrobat Starter Kit,Publish magazine, Feb. 1994. .
Portable Documents, InfoWorld, Jan. 17, 1994, pp. 66-67 and 71-77. .
AdobeAcrobatProducts & Technology, An Overview, by Adobe Systems Incorporated, 1585 Chareston Road, Mountain View, CA 94039, Nov. 1992. .
Fontographer product brochure, from Altsys Corporation, 269 Renner Road, Richardson, TX 75080. .
Product review of Fontographer, MacUser magazine, Oct. 1992, p. 56. .
Product review of FontStudio, MacUser magazine, May 1992, starting at p. 56. .
Product review of FontStudio, MacUser magazine, Sep. 1990, pp. 76 and 80. .
Adobe Type I Font Format, published by Adobe Systems Incorporated, 1990. .
Affidavit of John Collins concerning Fontographer and FontStudio programs, dated May 24, 1995. .
Affidavit of John Collins Concerning Prior Art Programs For De-Compressing And Installing Fonts, dated Dec. 6, 1995. .
Ditital Formats for Typefaces, by Peter Karow, Published by URW Verlag, Hamburg, Germany, 1987, Title page, Copyright Notice Page, Table of Contents, and pp. 116-117 and pp. 376 and 377. .
Character Generation Under Grid Constraints, by Roger Hersch, Computer Graphics, vol. 21, No. 4, Jul. 1987, pp. 243-252. .
Microsoft Windows Device Driver Adaptation Guide, .COPYRGT. 1987-1992 by Microsoft Corporation, front cover, title page, copyright page, and pp. 122 and 123. .
Microsoft Windows Printers and Font Kit, .COPYRGT. 1987-1992 by Microsoft Corporation, front cover, title page, copyright page, table of contents, and pp. 86 and 87. .
PostScript Language, by Adobe Systemes, Incorp. Seventh Printing, Aug. 1987. .
TrueType Font Embedding DLL Specification, Mar. 29, 1995, Version 0.912, published by Microsoft Corporation. .
Teach Yourself Web Publishing With HTML In A Week, 1995, by Sams Publishing, Indianapolis, Indiana, pp. 3-21, 137-152, 369-377, and 387-389. .
LaserJet Unlimited, Edition II, by Nace and Gardner, published by Peachpit Press 1988, pp. 263-268 and 445. .
"Adobe Acrobat In Use" by Brailsford from Desktop Publishing Commentary, Aug. 1993, UK. vol. 9, No. 4, ISSN 0957-3178, pp. 9-13. .
"Elseware technology promise more efficient font portability" by Mark Moore, PC Week, vol. 10, No. 17, May 3 1993..~
Primary Examiner:
Jankus; Almis R.
Attorney, Agent or Firm:
Porter; Edward W.
Parent Case Text
REFERENCE TO PRIOR APPLICATION
The present application is a continuation-in-part application of U.S. patent application Ser. No. 08/250,372, filed by the inventors of this application, John S. Collins and Mark H. Goldwater, on May 27, 1994 now U.S. Pat. No. 5,583,978.
Claims
What we claim is:
1. A computerized method comprising the steps of:
receiving a plurality of characters and an identification for each such character of an associated pre-defined font;
accessing, for each combination of a character and pre-defined font so received, a pre-defined font description which describes a sequence of outline segments which define each of the one or more outlines of the shape of the character in its associated pre-defined font using a given font description language;
generating a new font description from the pre-defined font description of the shape for each received character-font combination, which new font description describes the shape of the combination as a sequence of outline segments according to a new font description language, wherein said step of generating new font descriptions for a given character-font combination includes the steps of:
modeling the given character-font shape defined by the given pre-defined font description associated with that shape, said modeling including the steps of:
identifying description-independent segmentation points in the one or more outlines represented by the outline segments of the given pre-defined font description, the location of which description-independent points is a function of each such outline's shape, independently of the sequence or segmentation of the outline segments included in the pre-defined font description;
approximating the shape of the outline defined by the pre-defined font description between adjacent description-independent points with new segments bounded at those adjacent description-independent points; and
generating a given one of said new font descriptions in which the
sequence of outline segments includes said new segments; and
installing said new font descriptions created by said generating step into the operating system of a computer;
calling said operating system to have said computer use said installed new font descriptions to render the character-font shapes the new font descriptions represent.
2. A computerized method as in claim 1 wherein:
said step of generating new font descriptions is performed on a first computer system; and
said steps of installing said new font descriptions into the operating system and calling the operating system to render character-font shapes represented by the new font descriptions are performed on a second computer system.
3. A computerized method as in claim 1 wherein:
said step of receiving a plurality of characters and identifications of associated predefined fonts receives a body of text containing said characters and identifications;
said step of generating new font descriptions generates a text-specific set of font descriptions associated with said text in which the particular character-font shapes represented is a function of the fonts and the particular characters in each font identified in said text; and
said step of calling the operating system to render character-font shapes is used to render an image of a portion of said body of text.
4. A computerized method as in claim 3:
further including the step of transferring said text and said text-specific set of font descriptions from a first computer system to a second computer system; and
wherein said steps of installing said new font descriptions into the operating system and calling the operating system to render character-font shapes is performed by said second computer systems.
5. A computerized method as in claim 4:
further including the step, performed on said second computer system, of converting said new font description transferred to it from said first computer system, into a font description language used by the operating system of said second computer system; and
wherein said step of installing said new font descriptions installs said converted versions of said new font descriptions into the operating system of said second computer system.
6. A computer system comprising:
a screen upon which said computer system can render images;
an operating system to which calls can be made to render the image of a character-font shape defined by a font description which is written in a language compatible with, and which has been installed in, said operating system;
means for receiving a text including a sequence of characters and an identification for each such character of an associated font;
means for receiving a set of outline font descriptions associated with said text, which describe the shape of character-font combinations identified in said text as a sequence of outline segments;
means for converting said received font descriptions into a font description language compatible with said operating system;
means for installing said converted font descriptions into said operating system; and
means for generating an image of said text on said screen by calling said operating system to render images of character-font shapes defined by said converted font descriptions which have been installed in said operating system.
7. A computer system as in claim 6:
further including means for opening and closing a file on which said text and said outline font descriptions have been recorded;
wherein said means for receiving a text and said means for receiving a set of outline font descriptions, respectively, include means for receiving said text and said font descriptions from said file after said file has been opened by said file opening means;
wherein said means for converting said received font descriptions and said means for installing them include, respectively, means for converting and installing said font descriptions after said file has been opened by said file opening means; and
further including means for un-installing said converted font descriptions associated with said text from said operating system after said file has been closed by said means for closing.
8. A computer system as in claim 6 further including means for generating an image of said text on said screen by rendering images of character-font shapes defined by said received font descriptions before they have been converted and installed in said operating system, so said text can be viewed before said conversion and installation is complete.
9. A computer system as in claim 6 wherein:
said means for receiving a set of font descriptions includes means for receiving a plurality of font resources associated with said text, each of which includes a description of one or more physical fonts and font descriptions of one or more character-font shapes associated with such described physical fonts;
said means for converting said received font descriptions includes means for creating, for a physical font described in a plurality of said font resources, an installable outline font which includes:
a converted description of the physical font derived from a physical font description contained in one of the received font resources; and
converted font descriptions derived from font descriptions associated with the physical font in different ones of the received font resources; and
said means for installing installs said installable fonts in said operating system.
10. A computer system comprising:
means for rendering images of fonted documents whose font descriptions are in a given font description language;
means for receiving a text including a sequence of characters and an identification for each such character of an associated font;
means for receiving a set of outline font descriptions associated with said text in which:
the character-font shapes represented in the set is a function of the fonts and the particular characters in each font identified in said text; and
each font description describes the shape of a character-font combination as a sequence of outline segments;
means for converting said received set of font descriptions into a corresponding set of font descriptions for the same character-font shapes written in the font description language compatible with the means for rendering images; and
means for causing said means for rendering images to render an image of said received text.
11. A computerized method comprising the steps of:
responding to the receipt over a computer network of a first message indicating that a given text is to be sent to a recipient network address associated with the first message by sending the given text over the network addressed to the first message's associated recipient address; and
responding to the receipt over a computer network of a second message indicating that a given set of font descriptions is to be sent to a recipient network address associated with the second message by sending the given set of font descriptions over the network addressed to the second message's associated recipient address; and
wherein:
the given text includes a plurality of characters and an identification for each such character of an associated font
the font descriptions of the given set of font descriptions each define the shape of a given character in a given font; and
the set of character-font shapes represented by the given set of font descriptions is a function of both the fonts identified in the given text and the particular characters for which each such font is identified in said text.
12. A computerized method as in claim 11 further including the steps of:
receiving said text;
accessing, for each individual combination of a character and font identified in said text, a pre-defined font description which describes a sequence of outline segments defining each outline of the corresponding character-font shape;
generating from each accessed pre-defined font description a new font description which describes a character-font shape as a sequence of outline segments, said generating including:
modeling the character-font shape defined by the accessed pre-defined font description, said modeling including the steps of:
identifying description-independent segmentation points in the one or more outlines represented by the outline segments of the pre-defined font description, the location of which description-independent points is a function of each such outline's shape, independently of the sequence and segmentation of the outline segments included in the pre-defined font description;
approximating the shape of the outline defined by the pre-defined font description between adjacent description-independent points with new segments bounded at those adjacent description-independent points; and
making said new segments part of said new font description's sequence of outline segments; and including said new font description in the given set of font descriptions sent over the network.
13. A computerized method as in claim 11 wherein:
said step of responding to the receipt of a first message includes responding to each of a plurality of such first messages, each indicating that a different text is to be sent to a recipient network address associated with the individual first message, by sending the first message's indicated text over the network addressed to the first message's associated recipient address; and
said step of responding to the receipt of a second message includes responding to each of a plurality of such second messages, each indicating that a set of font descriptions associated with a different text is to be sent to a recipient network address associated with the individual second message, by sending the second message's indicated sets of font descriptions over the network addressed to the second message's associated recipient address.
14. A computerized method as in claim 13 wherein:
the individual texts which are sent over said network in response to said first messages each include the name of a set of font descriptions; and
the individual second messages each include the name of a set of font descriptions.
15. A computerized method as in claim 14 wherein:
the sets of font descriptions associated with texts are font resources, where each font resource is a group of one or more font descriptions;
some texts have multiple font resources associated with them; and
some font resources are associated with multiple texts; and
each text includes the name of each of the text's associated font resources.
16. A computerized method as in claim 13 wherein the texts are HTML text files.
17. A computerized method as in claim 16 wherein said HTML texts each contain one or more tags containing URL specifications identifying the name of files containing the set of font descriptions associated with the HTML text.
18. A computerized method to be performed on a computer system comprising the steps of:
sending a text-request message over a computer network requesting that a given text be sent to said computer system over the network, wherein the requested text includes a plurality of characters and an identification for each such character of an associated predefined font
receiving said requested text over the network;
sending a font-request message over the network requesting that a font resource containing a set of font descriptions be sent to said computer system over the network, wherein:
the requested font resource includes one or more font descriptions;
the font descriptions each define the shape of a given character in a given font; and
the set of character-font shapes represented by the requested font resource is a function of the fonts and the particular characters in each font identified in said requested text; and
receiving said requested font resource over the network;
using said received font resource to render an image of a portion of said received text.
19. A computerized method as in claim 18 further including the step of rendering an image of the received text without character-font shapes derived from the requested font resource, before receiving the requested font resource.
20. A computerized method as in claim 18 further including the steps of
determining whether or not to send said font-request message as a function of the state of a variable; and
rendering an image of said received text without character-font shapes derived from the requested font resource, when said determining step determines not to send said font-request message.
21. A computerized method as in claim 20 further including the step of setting said variable in response to input from a user of said computer system.
22. A computerized method as in claim 18 wherein:
the requested text includes the name of a font resource; and
said step of sending a font-request message includes reading the font resource name from the received text and using the name in the font-request message to identify the font resource requested.
23. A computerized method as in claim 18 wherein:
the step of sending a font-request message sends one or more font-request messages to request that a plurality of font resources associated with the requested text be sent to the computer system over the network;
each of the requested font resources includes a description of one or more physical fonts and one or more font descriptions of character-font shapes associated with each such described physical font;
the step of receiving the requested font resource receives said plurality of requested font resources; and
the step of using the received font resource to render an image uses the plurality of requested font resources to render the image by finding, for each given character-font shape to be rendered as part of the image, a font description of the given shape from one of the received font resources and using the font description found to render the characterfont shape as part of said image.
24. A computerized method as in claim 23 wherein:
the set of character-font shapes represented by a first of said requested font resources is a function of the fonts and the particular characters in each font identified in a body of text which is not identical with the requested text; and
the set of character-font shapes represented by a second of said requested font resources is a function of the fonts and the particular characters in each font which are identified in the requested text but not contained in said first requested font resource.
25. A computerized method as in claim 23 wherein said step of sending a font-request message sends a separate font-request message over the network for each of said plurality of font resources associated with said given text.
26. A computerized method as in claim 23:
wherein the steps of the method are repeated for different texts;
further including the step of storing on said computer system requested font resources which have been requested and received in conjunction with a first text after a second text has been requested by a text-request message; and
wherein said step of sending a font-request message for font resources associated with said second text includes determining whether or not to send a font-request message for a font resource associated with the second text as a function of whether or not said font resource is currently already stored on said computer system.
27. A computerized method as in claim 23 wherein said given text includes the names of associated font resources.
28. A computerized method as in claim 18:
further including the step of installing the character font descriptions contained in the requested font resources into the operating system of the computer system so the shapes described by such font descriptions can be rendered by making calls to said operating system; and
wherein the step of using the requested font resources to render an image of a portion of the received text includes making such calls to said operating system.
29. A computerized method as in claim 28 further including the step of converting font descriptions contained in said requested font resources into a font description language which is compatible with said operating system before installing those font descriptions in the operating system.
30. A computerized method as in claim 18 wherein:
the text-request and font-request messages conform to the HTTP protocol;
the requested text is an HTML text containing a URL specification of one or more font resources and a specification of one or more fonts are to be used when rendering an image of one or more portions of said HTML text; and
the step of sending a font-request message includes including a URL corresponding to one of said URL specifications contained in the requested HTML text in the HTTP font-request message sent over the network.
31. A computerized method as in claim 30 wherein the requested HTML text contains a tag which contain the the URL specification.
32. A computerized method as in claim 30 wherein:
the requested HTML text contains a tag which specifies that a given HTML text type is to have an associated font; and
the step of using the requested font resource to render an image includes causing portions of the HTML text having the given text type to be rendered in the font specified in said tag.
33. A computerized method as in claim 30 wherein:
the requested HTML text contains a tag which specifies that adjacent HTML text is to have a given associated font; and
the step of using the requested font resources to render an image includes causing HTML text adjacent to said tag to be rendered in the font specified in said tag.
34. A computer system comprising:
means for receiving a body of text containing a plurality of characters and an identification for each such character of an associated font;
means for receiving an old set of one or more font resources each of which contains font descriptions of less than all characters in one or more fonts; and
means for creating a new set of one or more font resources for the body of text in which the particular character-font shapes represented are a function of the fonts and the particular characters in each font identified in said text, said means including means for deriving, from said old set of font resources, font descriptions of character-font combinations identified in said text and for placing said derived font descriptions in said new set of font resouces.
35. A computer system as in claim 34 wherein:
said means for receiving an old set of font resources includes means for receiving individual font resources which include font descriptions from different fonts; and
said means for creating a new set of font resources includes means for creating individual resources which include font descriptions from different fonts.
36. A computer system as in claim 34:
wherein said old and new sets of font resources both contain outline font descriptions written in a first font description language, each of which font descriptions describes a sequence of outline segments which define each of the one or more outlines of the shape of a character in an associated font;
further including means for receiving outline font descriptions which are written in a second font description language, each of which also describes a sequence of outline segments which define each of the one or more outlines of the shape of a character in an associated font; and
wherein said means for creating said new set of one or more font descriptions further includes:
means for translating font descriptions written in said second font description language which describe the shape of character-font combinations identified in said text into corresponding new font descriptions written in said first font description language, and
means for placing said translated new font descriptions in said new set of font resources.
37. A computer system as in claim 36 wherein said means for translating includes:
means for modeling the given character-font shape described by a given font description written in said second font description language including:
means for identifying description-independent segmentation points in the one or more outlines represented by the outline segments of the given font description, the location of which description-independent points is a function of each such outline's shape, independently of the sequence and segmentation of the outline segments included in the font descriptions written in said second language;
means for approximating the shape of the outline defined by the given font description between adjacent description-independent points with new segments bounded at those adjacent description-independent points; and
means for including said new segments in a sequence of outline segments which said translated new font description uses to define said character-font shape in said first language.
38. A computer system as in claim 34 wherein:
said means for receiving an old set of font resources includes means for receiving a plurality of old font resources each of which includes a description of one or more physical fonts and font descriptions of less than all the characters associated with each such physical font;
said means for deriving and placing font descriptions includes means for deriving, from multiple font resources of the old set, font descriptions of character-font combinations of a given font identified in said text and for placing those derived font descriptions in the new set of font resources.
39. A computer system as in claim 34 wherein said means for creating a new set of font resources creates a plurality of new font resources.
40. A computer system as in claim 34 wherein said means for creating a new set of font resources includes means for excluding from said new set of font resources font descriptions which are contained in a base set of one or more font resources.
41. A computer system comprising:
means for receiving an indication of a given character-font combination, that is, of a given character in a given font, for which a shape description is desired;
means for finding which of a plurality of font resources, each of which includes font descriptions of a different set of characters in said given font, contains a font description of said given character-font combination; and
means for using the font description of said given character-font combination found to provides a description of the corresponding character-font shape.
42. A computer system as in claim 41 wherein the means for accessing font resources includes means for accessing font resources, each of which includes a description of multiple physical fonts and font descriptions of one or more character-font shape associated with each such physical font.
43. A computerized system as in claim 42 wherein said means for accessing font resources includes means for accessing a plurality of font resources, each including descriptions of, and font descriptions for, one or more of the same physical fonts.
44. A computer system as in claim 41:
further including means for receiving a text containing a plurality of characters and an identification for each such character of an associated font; and
wherein:
said means for receiving an indication of a given character-font combination for which a shape description is desired includes means for receiving such an indication for each of a given plurality of characters-font combinations identified in said text; and
said means for using the a found font description includes means for rendering the shape of each of said given plurality of character-font combinations in an image of a portion of said text.
45. A computer system comprising:
means for receiving different portions of a body of text, each of which contains a plurality of characters and has a font associated with each such character;
means for associating a different plurality of font resources which each such text portion, wherein each font resource includes font descriptions of one or more character-font combinations in each of one or more fonts;
means for accessing the plurality of font resources associated with a given text portion to obtain font descriptions of character-font combinations associated with the given text portion, said means including means for accessing the font description of different character-font combinations from the same font from different ones of the font resources associated with the given text portion; and
means for using the font descriptions obtained for a given text portion to render an image of that text portion.
46. A computer system as in claim 45:
wherein said means for receiving different text portions includes means for receiving said text portions over a computer network; and
further including means for receiving over the network font resources associated with a such text portion received over the network.
47. A computer system as in claim 46 further including:
means for storing font resources which have been received over the network in a cache in conjunction with the rendering of one text portion when rendering subsequent text portions; and
means for determining if a given font resource in the set of font resources associated with a text portion to be rendered is currently stored in said cache, and, when not, for transmitting a message for causing the given font resource to be transmitted to said computer system over said network.
48. A computer system as in claim 46 wherein:
said individual text portions received by said computer system each contain an identification of the set of font resources to be associated with it; and
said means for associating different pluralities of font resources with different text portions includes means for reading said identification of a set of font resources from said received text portions.
49. A computer system comprising:
means for receiving a plurality of font resources, each of which includes one or more physical fonts and font descriptions of the shape of a variable number of characters in each such physical font; and
means for creating a new font resource, including means for combining in said new font resource font descriptions of different characters of a given physical font derived from different ones of said received font resources.
50. A computer system as in claim 49:
further including an operating system having a font manager in which a font resource having font descriptions corresponding to a single physical font and having a pre-defined format can be installed, said operating system having functions which can be called to render the shape of a font description in an installed font; and
wherein said means for creating a new font resource creates such an installed font.
51. A computer system as in claim 49 wherein said means for creating a new font resource includes means for creating a new font resource which includes font descriptions from different physical fonts.
Description
FIELD OF THE INVENTION
The present invention relates to computer font technology, that is, the computer technology of representing and generating the shapes of alphanumeric characters and other images used with text.
BACKGROUND OF THE INVENTION
Since the beginning of the written word, creators of documents have been concerned not only with how their words would sound to the ear if spoken, but also with how they appear to the eye when read. Before the advent of print, calligraphy was a major art form. With print, the art of creating and using fonts has superseded calligraphy in importance.
A font is a set of shapes representing each character in an alphanumeric character set. Usually the shapes of different characters in each font share certain characteristics, such as horizontal and vertical position of certain shape features, the general width of their vertical and horizontal strokes, and whether or not they are serifed, bold, or italic, so that the characters of a given font look appropriate together.
Commonly a font is identified by a basic font name, such as "Courier", "Arial", "Helvetica", or "Times New Roman" which identifies the general shapes of its characters, independent of size. These basic font names are often trademarks owned by the designers of the font. The basic font name is often followed by a point size designation which specifies the size of that font. Sometimes other words are inserted between the basic font name and the point size, such as "bold", which means its strokes are to be thicker; "narrow", which means its entire characters are to be made more narrow; "italic", which means its characters are to be slanted; or "oblique", which is used for sans serifed characters and means its characters are to be slanted.
The ability to vary fonts has many advantages. It lets a user vary the size of his letters to pack text more densely when necessary and to allow text to be more easily read. Using different fonts also has the ability to visually distinguish different parts of the text. This makes texts easier to scan and use. In addition, some texts are more visually pleasing than others, whereas some are easier to read. Different fonts appeal to different aesthetic senses. Some appear traditional, some modern, some art nouveau, some art deco, some hand written, some humorous, and some shocking. The ability to select from a wide variety of fonts greatly increases the ability to tune the aesthetic message of a document.
When the computer age started, most computers only represented text in one font. In the last decade or so, however, an increasing percentage of computer systems have the ability to display and print text in several different fonts. Most such computers have font resources which contain pre-defined font descriptions for the shape of each character of each of the fonts it can handle. The pre-defined font descriptions describe character shapes in a specified form or language.
Some font languages represent shapes as bitmap images which can be translated directly to the pixels on a video display or a laser printer. This has the advantage of being fast, but it has the disadvantage of requiring a different set of font descriptions for each different size.
More recently there has been a trend to scalable font languages. These languages define character shapes in terms of the one or more outlines which define its shape. Each such outline is defined by a move to a starting location and then a sequence of outline segments, each of which is either a line or a curve, such as a Quadratic or Cubic Bezier curve or a circular arc, followed by a move to the standard position for starting the next letter. A Bezier curve is a well-known type of curve defined by its two on-curve endpoints and one or two off-curve control points located between them. Quadratic Bezier curves only have one off-curve control point, with the curve at each endpoint being tangent to a line from that endpoint to the control point and with the angle of the curve reflecting the angle formed by those tangent lines. Cubic Bezier curves have two off-curve control points, with the curve at each endpoint being tangent to the line to its closest control point and with the curve's extent in the general direction of each such tangent near an endpoint being a function of the length from that endpoint to the tangent's associated control point. The lines and segments are usually defined in a resolution of either 1000.times.1000 or
2048.times.2048 units, called outline resolution units, or ORUs. Since these font descriptions define a shape in terms of lines and curves and since that definition is made with a high resolution, they can be used to generate font images of virtually any desired size.
In scalable font technology the set of font descriptions defining the outline shapes of each character in a character set can be considered a base, or physical, font. The variously sized fonts generated from such a physical font are considered logical fonts, because they do not have separate shape descriptions associated with their characters, but rather generate such shapes at the specified size from the scalable physical font description. Using such nomenclature, there would be, for example, physical font associated with the base font name "Arial", and that physical font would have associated with it any logical font which had the name "Anal" followed by a point size specification, such as "Arial 12" or "Arial 24". Normally a separate physical font is provided for font names which include "Bold", "Italic", or "Narrow", but fonts with the word "Oblique" in their name are often generated by slanting the shapes of the corresponding physical font, and the same could be done, if necessary for "Italic" if no corresponding italic physical or base font is provided.
There are currently several major scalable font languages. They include PostScript, developed by Adobe Systems Incorporated, of 1585 Charleston Road, Mountain View, Calif. 94039, TrueType, developed by Apple Computer, Inc., 20525 Mariani Avenue, Cupertino, Calif. 95014; Speedo, developed by Bitstream Inc., the assignee of this application; and Intellifont, developed by the AGFA division of Miles Inc, 90 Industrial Way, Wilmington, Mass. 01887. Each of these languages uses a different code or format to describe shapes and represents shapes in different ways. For example, TrueType uses quadratic Bezier curves to define the shape of curve segments, whereas PostScript and Speedo use Cubic Bezier curves, and Intellifont use circular arcs.
For a computer to render a font named in a given document, it requires not only a bitmapped or scalable font description of that font's characters, but also software, called a font interpreter, that knows how to interpret the particular code in which each font language's font descriptions are written and convert them into a bitmap pattern or a sequence of moves and outline segments.
Unfortunately, not all computers have the same font descriptions or the ability to interpret the same font languages. This creates a problem if an electronic document is created on a first computer using one or more given fonts and is then transferred to second computer which does not have those fonts or which cannot interpret them. In such a case, when the document is shown or printed on the second computer it has different fonts than intended. This can cause the document to have a very different, and often undesired appearance, and can disrupt its spacing and pagination. In highly formatted text, such a text with columns, this can make the text almost unreadable. In addition, some fonts have special characters not found in other fonts, or use different character codes than are commonly used in other fonts so that such a font mismatch can not only disrupt the appearance and organization of a document, but can also cause information to be lost or be garbled.
One solution to the problem of making fonted text portable is to send a copy of all fonts and font interpreters needed to properly render the characters of a document along with it. Unfortunately this has many problems. First, finding out what fonts and interpreters need to be sent with each such document and installing them on the viewing machine would be labor intensive. Furthermore, it would present legal problems because, even though the actual shape of fonts have long been held not to be copyrightable, both the code and sequence of outline segments contained in font descriptions have been considered by many to be copyrightable, and thus cannot be installed in a new machine without legal permission.
There have been multiple prior attempts to deal with this problem.
A first prior approach is to use software that enables the computer playing back a document to attempt to approximate a font called for in the document with a font which is similar, if it has one. Such systems attempt to replace one serifed font with another, one italic with another, and so on. Unfortunately, this approach still requires that the computer playing back a document have fonts which approximate those it is to replace, and the approximations are often disappointing.
Another prior technique amplifies this first approach by using software that sends information along with documents explaining the size of each character in each of the fonts used. This enables corresponding software in the playing computer to stretch or compress whatever font it is using to approximate a missing font to produce a font which has the same spacing. This provides the valuable advantage of preventing the formatting of documents from being upset due to spacing differences, but is still is only an approximation.
Another prior approach has been to embed, or include, font descriptions with the document so the party at the other end can use them. The makers of such embeddable fonts have designed them so they can only be used in the document in which they have been included and thus have granted a license for such a copy of their font descriptions to be made without requiring express permission. Unfortunately, all such systems of which we are aware only work with fonts of one language and assume that the computer on which their documents are to be played has interpreters for that language. Thus the documents produced cannot be properly reproduced if the machine playing them back does not have the proper font interpreter and it even if does, it can only provide insured portability for fonts written in that interpreters one language.
Another prior approach is to have a document recorder application which records bitmap images of all character-font shapes included in a document from the font interpreter of the computer creating the document and embeds them in a copy of the document. The resulting portable document is designed to be viewed or printed from a player application on another computer. The player renders the shape of each character in the document from its associated embedded font. The program has the ability to, in effect, creates bitmapped physical and logical fonts. That is, if the user decides he or she does not want to have to store separate bitmap images for the same shape font in different sizes, the system will store it in one size and on playback attempt to generate bitmap patterns at different sizes from it.
This approach appears to avoid copyright problems, because it has long been held that the shape of fonts is not copyrightable and the bitmap patterns copied are determined largely by the shape of the font's original pre-defined font descriptions rather than from the actual code or sequence of moves and outline segments used in that description. It also has that advantage of being able to play back any font handled by the computer creating the document. It has the disadvantages of requiring a large amount of memory to produce a large variety of fonts accurately.
The issue of being able to see fonted documents on machines other than those on which they have been created is being made even more important by the ever increasing use of computer networking. Such networking is constantly increasing the amount of time people spend viewing text created on other machines, and the number of different machines from which they are receiving such text. Because the communication rates of many network links is rather limited, the amount of time it requires to communicate the fonts associated with a document can become a major consideration. For example, just one TrueType outline font can commonly be as big as sixty-five thousand bytes. If a document included ten fonts, it would require six hundred and fifty thousand bytes to send the fonts necessary to render it. At a 14.4Kbit communication bandwidth common for many business and home connections to electronic networks, it would take over seven minutes to receive, render, and see such a documents, a length of time which would be unacceptable in many applications.
But there is a strong impetus to be able to freely use fonts on electronic networks. Fonts make text more appealing, more interesting, and more capable of highlighting different types of information. For example, the rate of usage of the World Wide Web (the "Web") has recently been growing exponentially. One of the many benefits of the Web is that it allows users to hop from one data base to another any where in the world with the click of a mouse. This lets users "surf" the Web in the same was as the television remote control lets users "surf", or change between channels. In such an environment it is important for Web sites to be able to quickly provides users with distinctive and attractive screens so as to better catch and please the user's eye in cyberspace's intense competition for attention.
Text on the Web is written in HTML, a text mark-up language. An HTML text contains a sequence of ASCII charcters which include tags, sequences of characters which an HTML browser, a program for displaying HTML text in a formatted manner, reads and understands. Most tags are used to indicate the text type of an adjacent portion of the HTML files displayable text. Currently, most bowsers let their individual users select which logical fonts are to be used to display each of the different text types recognized by the Browser in response to such format tags. This can often create problems because the person creating the HTML document has no way of knowing what font is going to be used to show what text. As a result those who prepare HTML documents have little control over how they will appear to most users.
On-line services often have more control over over how their screens appear to users than people who develop Web sites. This is because their users usually run software provided by the on-line service which can be programmed to render screens in a desired manner. Currently many such programs come with a CD ROM which allows the user's computer to store many of the images and fonts necessary to renders screens without the need to have them sent over the network. This works well for many purposes, but has the drawback that it makes it virtually impossible for the on-line service to use any fonts which are not on the CD ROM.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide an apparatus and method for creating and playing back portable documents, that is documents in which text with a variety of different fonts can be accurately played back by a machine which does not previously have font descriptions and font interpreters for all of that document's fonts.
It is yet another object of the present invention to provide such an apparatus and method which creates such portable documents and/or their associated font descriptions automatically.
It is still another object of the present invention to provide such an apparatus and method which creates such documents and/or their associated font descriptions quickly.
It is yet another object of the present invention to provide such an apparatus and method which creates portable font descriptions which do not require much storage space.
It is still another object of the present invention to provide an apparatus and method for automatically creating new font descriptions of character shapes defined in old font descriptions while avoiding copying certain features in such old font descriptions which are not required to describe those shapes.
It is yet another object of the invention to provide an apparatus and method for enabling fonted electronic documents to be rapidly transmitted over electronic networks.
It is still another object of the invention to provide an apparatus and method for enabling fonted electronic documents to be rapidly viewed over electronic networks.
It is still another object of the invention to facilitate the mantenance of font descriptions for a body of text as that body is changed.
It is still another object of the invention to facilitate the use of fonted text on the World Wide Web.
According to one aspect of the invention a computerized system translates predefined font descriptions into new font descriptions and then installs those new descriptions into a computer's operating system so those descriptions' shapes can be rendered by standard operating system calls for the rendering of character shapes. Preferably the new font shape descriptions depend only on the shapes defined by the predefined font descriptions, and not the manner in which those shapes have been defined. Preferably the new font descriptions are created on one computer system and then transfered to, and installed on, a second computer system, often one that does not have all of the original pre-defined font descriptions used to create the new font descriptions. Usually the new font descriptions translated are specific to a particular body of text. These new font descriptions are often translated into one font description language and then transfered to one or more computers in conjunction with the transfer of all or a portion of the body of text. The computer which receives the new font descriptions translates them into a language its operating system's font functions supports, installs them, and then uses them to render the portion of text received.
BRIEF DESCRIPTION OF THE DRAWINGS
These and other aspects of the present invention will become more evident upon reading the following description of the preferred embodiment in conjunction with the accompanying drawings, in which:
FIG. 1 is a high level block diagram of one embodiment of the invention in which a first computer converts an input text written using a plurality of pre-defined font descriptions into a portable document having new font descriptions and in which a second computer receives the portable document and renders an image of it using the new font descriptions it contains;
FIG. 2 is a high level block diagram of a version of the embodiment show in FIG. I in which the portable document is communicated between first and second computers on a removable mass storage medium;
FIG. 3 is a high level block diagram of a version of the embodiment shown in FIG. 1 in which the portable document is communicated between first and second computers over an electronic data network;
FIG. 4 is a diagram of the functional interface of a character shape recorder software module designed according to the present invention for a plurality of uses, including use as the character shape recorder of the first computer in FIG. 1;
FIG. 5 is a diagram of the functional interface of a character shape player software module designed according to the present invention for a plurality of uses, including use as the character shape player of the second computer shown in FIG. 1;
FIG. 6 is a more detailed schematic diagram of the functional elements of the first computer shown in FIG. 1, in which the character shape recorder of FIG. 4 is used, including the major functional steps performed by the document builder and character shape player;
FIG. 7 is a more detailed flow chart of the functional steps performed by the CsrSetFontSpecs function shown in the character shape recorder in FIGS. 4 and 6;
FIG. 8 is a schematic diagram of the list of physical font records created by the character shape recorder of FIG. 4 and 6, of the list of logical font records and the binary tree of character records the recorder can associated with each such physical font record, and of the links which it makes between such character records and the glyph program strings ("GPSs") which contain new descriptions of the shapes of such characters;
FIG. 9 is a more detailed flow chart of the functional steps performed by the CsrDoChar function which is part of the character shape recorder in FIGS. 4 and 6;
FIG. 10 is a schematic diagram of the following data structures created by the character shape recorder of FIGS. 4 and 6: the character shape array, the open contour structure, the hierarchical contour tree into which contour are placed once closed, the division of that tree's contour structures into glyph elements, the glyph records created in association with each such glyph element, and the glyph program strings ("GPSs") which contain new shape descriptions derived from the contours of each such glyph element;
FIGS. 11 and 12 are a diagramatic representations of how step 364 of FIG. 9 divides curve segments received by the character shape array at inflection and X extreme points, respectively;
FIG. 13 is a more detailed description of the corner detection functionality described in step 366 of FIG. 9;
FIGS. 14A-D, 15A-C, and 16A-C are diagrams used to illustrate the corner detection steps of FIG. 13;
FIGS. 17 and 18 are more detailed flow charts of the steps used to perform the curve depth analysis of step 422 of FIG. 9;
FIG. 19 is a schematic diagram of the binary tree of glyph records, of the type shown in FIG. 10, produced by the character shape recorder of FIGS. 4 and 6, and of the matching which is performed by that recorder for each new glyph records to see if the shape represented by its associated glyph program string ("GPS") matches that of the glyph programming string associated with any glyph record already in the tree;
FIG. 20 is a schematic representation of the data element contained in the portable font resource shown in FIGS. 1, 6, and 21;
FIG. 21 is a more detailed schematic diagram of the functional elements of the second computer shown in FIG. 1, in which the character shape player of FIG. 5 is used, including the major functional steps performed by the page builder and character shape recorder.
FIG. 22 is a high level block diagram of a version of an embodiment of the invention in which portable font resource ("PFR") files are created for HTML files of a World Wide Web site and communicated across the internet in conjunction with their associated HTML files to allow those files to be view by Web browsers with their intended fonts;
FIG. 23 is a highly simplified flow chart of the functional steps performed by the HTTP server of a World Wide Web site in the embodiment of the invention shown in FIG. 22;
FIG. 24 shows the text of an HTML file, benefits.html, shown in FIG. 22 without any of the extensions to the HTML language used with FIG. 22's embodiment of the invention;
FIGS. 25 and 26 shows how differently the HTML file shown in FIG. 24 can appear on the screens of different Web Browers because of prior HTML files's inability to control the fonts with which such an HTML is displayed;
FIG. 27 shows the same HTML file as in FIG. 24 after tags defined by FIG. 22's embodiment of the invention have been added to it to enable it to specify the fonts to be associated with various portions of its text and to identify portable font resource files containing the font descriptions necessary to render them;
FIG. 28 shows how the HTML file of FIG. 27 appears when rendered by a Web browser using FIG. 22's embodiment of the invention;
FIG. 29 is a highly simplified flow chart of the functional steps performed by the main function of a program, MakePfrsForFiles, which is used to create one or more portable font resource ("PFR") files for set of HTML files which have their fonts defined by fonts installed in the operating system, by other PFR files, or by both;
FIG. 30 is a diagram of the functional interface of a character shape player ("CSP") software module which is very similar to that shown in FIG. 5, except that it includes several new functions, such as CspOpenAlt1, and CspCreateDynamicFont which are important for understanding FIG. 22's embodiment of the invention;
FIG. 31 illustrates data structures, including a PFR cache and PfrAccessTable, which are used to create a dynamic font, that is a font which contains font descriptions from multiple PFRs;
FIG. 32 is a highly simplified flow chart of the functional steps performed by the function CsrWriteResource called by MakePfrsForFiles program of FIG. 29 to create one or more PFR files from the font descriptions created by MakePfrsForFiles;
FIG. 33 is a highly simplified flow chart of the functional steps performed by the main function of the Web browser program, browser.exe, shown in FIG. 22;
FIG. 34 is a highly simplified flow chart of the functional steps performed by the AccessNewDoc function used by the Web browser of FIG. 22 to access an HTML file over the Web and to display it on a computer screen;
FIG. 35 is a highly simplified flow chart of the functional steps performed by the GetUrlFile used by the Web browser of FIG. 22 to access files over the net identified by Uniform Resource Locator, or URL;
FIG. 36 is a highly simplified flow chart of the functional steps performed by the GetAndDisplayPfrs function used by the Web browser of FIG. 22 to obtain over the net, and cache, any of an HTML file's associated PFR files which the browser does not already have cached, and to display the HTML file once all its PFR files have been cached;
FIG. 37 is a highly simplified flow chart of the functional steps performed by the DisplayNewScreen function used by the Web browser of FIG. 22 to display a screen of an HTML file;
FIG. 38 is a highly simplified flow chart of the functional steps performed by the InstallPfrs function used by the Web browser of FIG. 22 to convert all of the fonts contained in an HTML file's PFR files into fonts compatible with the font manager of the operating system of the browser's computer and to install those converted fonts into the operating system so they can be rendered by calls to the font manager;
FIG. 39 is a highly simplified flow chart of the functional steps performed by the TTSetFont function used by the InstallPfrs function of FIG. 38 to perform the actual conversion from PFR font descriptions into installable fonts; and
FIG. 40 shows an empty screen of the Web browsers shown in FIG. 22;
DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
FIG. 1 provides an overview of a system 100 for creating and playing back portable fonted documents. This system includes a first computer 102 in which the portable document 104 can be created, and its accompanying video monitor 106. It also includes a second computer system 108 in which the portable document can be played back, and its accompanying video monitor 110 and printer 112.
The computers 102 and 108 are preferably computers, such as personal computers or computer workstations, which include memory devices for storing program instructions and data structures and one or more processing element for executing such instructions and manipulating such data structures. As the computer's one or more processors execute such instructions, it forms the functional element described for each of these computers.
The first computer 102 includes a document builder 114. This document builder has means for receiving a fonted input text 116. Such a text can be received from an external source, such as a disk or data network, or it can be created in a program running on the first computer, such as a word processor or desktop publishing program. The input text is comprised of a sequence of font names, text characters, and positioning codes. Normally each text character is associated with the first font name to precede it in the sequence, and each such font name has associated with it a set of coded pre-defined font descriptions in the computer's font resource 122 describing the shape of each character in that font.
The document builder places codes corresponding to each of the input text's successive font names, text characters, and position codes into the text 118 of the portable document 104. In addition, for each unique combination of a character and font name in the input text, the document builder creates a new font description for the shape described in its corresponding pre-defined font description.
It does this by causing the first computer's font interpreter 120 to interpret the character-font shape's pre-defined font description in the computer's font resource 122. The font interpreter translates the coded pre-defined font description into a sequence of moves, lines, and curves which define the outline of the character-font shape. It provides these to the document builder. The document builder, in turn, supplies this interpreted shape description to the first computer's character shape recorder ("CSR") 124. The CSR includes the capability to model the shape contained in the interpreted description, and to produce a new font description which is virtually independent of any aspects of the interpreted font description which are not required by the shape it represents. The CSR returns this new font description to the document builder, which then places it in the portable documents portable font resource 126, indexed by the codes used to represent its associated font and character in the portable document's text 118.
Both the first computer 102 and the second computer 108 include a device for communicating information between them. As is indicated in FIG. 2, this device can be a device 128A for communicating the portable font resource from the first to the second computer on a removable mass storage medium 130, such as a magnetic or optical disk, CD, or tape. The removable medium 130 can include singly produced copies, or mass produced copies. As is indicated in FIG. 3 it can also be a network interface
128B which can communicate the portable document over a network 132. The network 132 can include LANs, WANs, telecom connections, on-line services, the internet, and, in the future, the so-called information highway.
The second computer 108 also includes a page builder 134 and a character shape player ("CSP") 136. The page builder creates a rendered image, such as a page image or a screen image from the portable document. It reads the successive font, character, and position codes from the text 118 of the portable document 104. It uses the font codes to determine the font associated with each character. It uses the position codes to position the characters in the rendered image. In response to each character code, it asks the CSP to generate the shape for that character given its associated font code. The CSP generates this shape from the new font description indexed under that character and font in the Portable Font Resource 126. It delivers this shape to the page builder which places it at the proper location in the rendered image, and which then sends that rendered image either to an output device, such as the video monitor 110 or the printer 112.
Thus, it can be seen that the embodiment of the invention shown in FIG. 1 allows a fonted document created with the font interpreters and pre-defined font resources of the first computer, such as that shown in the first computer's display 106, to be communicated to, and visually rendered with virtually the exact same appearance by a second computer which does not have those font interpreters and font resources. And it does so without copying the copyrightable shape-independent aspects of the first computer's pre-defined font descriptions.
Since the character shape recorder 124 of the first computer can create a new font description for any shape described to it as a sequence of moves, lines, and quadratic and cubic Bezier curves, it can create new font descriptions from any font description language which the first computer's font interpreter can interpret into such a sequence of move, lines, and curves. Since all the major font description languages have associated font interpreters which can provide such output, or output which can be easily converted into such a form, this means the invention can be used with all such font description languages, even if they occur in the same document.
In some alternate embodiments of the invention the document builder includes means for placing representations of bitmap fonts in the portable font resource 126. This includes means for recording the bitmap pattern received from the font interpreter 120 for small fonts directly as the font descriptions for such images in the portable font resource. The document builder in such embodiments also includes means, used when larger bitmaps are received, for performing edge detection on the bitmap pattern, creating a move instruction to a first point on each edge in the pattern, and a line corresponding to the distance between each successive point on that edge, and supplying that sequence of moves and line segment to the character shape recording process described above. With these features, it can be seen that the invention enables virtually any document created with virtually any font to be accurately reproduced on another computer which does not contain the original font descriptions from which it was created.
The basic concept disclosed in FIG. 1 has many applications. In some, the document builder 114 and character shape recorder 124 are built directly into a user application, such as a word processor, draw program, or desktop publisher. In others, it is built into the operating system. In others still it is placed in a driver module which is interfaced to as a printer driver, so that it can interface to virtually any major application designed to run on its associated computer platform.
Similarly, in some applications the page builder 134 and character shape player 136 are built into a much larger user application. In others, it is part of special portable document viewer application. And in others still, it is built into the operating system.
The nature of the portable document varies with use of the document builder 114, recorder 124, page builder 134, and character shape player 136. For example, in many systems in which these modules are all built into a much larger user application, the portable document is a normal file for that application. In systems in which the document builder and recorder are in a print driver module and the page builder and player are part of a document viewer program, the portable font document cannot normally be read by the application which originally created its fonted text. In systems in which the document builder, recorder, page builder, and player are incorporated into the operating system, any file produced by any application compatible with that operating system can be a portable document 104.
In some embodiments, a single computer includes both the document builder and recorder, as well as the page builder and player, so that computer can both send and receive portable documents.
In some embodiments the portable document includes the page builder and player code so a computer reading the portable document can view the portable documents text and fonts without having to previously have a copy of the page builder and recorder.
FIGS. 4 and 5 show a preferred embodiment of the character shape recorder 124 and character shape player 136, respectively. In this embodiment, both the recorder and player 136 have been designed as discrete software modules. They have been modularized so their code can be used in a plurality of different software applications, different computers, and different operating systems. They have been written in the commonly used C programming language which is supported on almost all major computer systems. They do not include any functions which are operating system dependent. And they do not include much functionality that is likely to vary from application to application.
In some embodiments, for example, the recorder and the player are part of a software application that run on Unix, IBM PC compatible, and Apple Macintosh computers. In each machine dependent version of this application they are surrounded with code which interfaces with the operating system, performs the functions of the document and page builders, and creates portable documents which can be read by the corresponding versions of the application on the other types of computers. This enables fonted portable documents created on one type of computer to be played back with virtually the exact same appearance on another types of computer.
The modularization of the recorder's and the player's functionality also allows them to be used for purposes different than that described in FIG. 1. For example, in one embodiment of the invention the recorder is used as part of a program which creates sets of new font descriptions from sets of pre-defined font descriptions, independently of any input text. Once created, such new fonts can then be used with any application containing a player module.
In FIGS. 4 and 5 the function calls which can be made by host software using each module are shown on the left. These are the functions 150-158 in FIG. 4 and 170-178 in FIG. 5. In these figures, the function calls made by the module back to its host software are shown on the right. These so-called "callback" functions are numbered 160-165 in FIG. 4 and 190-202 in FIG. 5. The code of the functions on the left in each figure is part the recorder or player module. The code of the callback functions on the right is included in the host software which uses such modules.
In FIG. 4, the functions CsrMoveTo, CsrLineTo, CsrQuadraticTo, and CsrCubicTo, are pointed to by a line from the callback function ExecChar because these functions are called by ExecChar to deliver the moves, lines, and curves which define a character's shape to the recorder.
FIG. 6 provides a more detailed schematic view of the functional elements shown in the first computer 102 in FIG. 1. It shows how the document builder 114 interacts as the host program for the modular character shape recorder 124 to convert the input text 116, which uses pre-defined font descriptions, into the portable document 14.
The document builder includes a main program 204 and the callback functions 160-165 shown on the right-hand side of FIG. 4.
The first step shown for the document builder's main program is step 210. This calls the CSR's CsrOpen function 150. In step 212, CsrOpen opens and initializes the player software module 124, giving it the memory buffer and temporary files it needs to work and setting up its initial data structures.
Once this function returns, the document builder's next step 214 performs a loop until it has processed all the codes in the input text 116. For each successive code received from the input text this loop performs the steps 216, 218, 220, and
222 shown indented under it.
Step 216 tests to see if the received code is a font name, such as the codes 217 shown in the input text. If so, its substeps 224, 226, 228, and 230 are performed. Step 224 saves the basic font name portion from the full font name received and points pFontld to it. Step 226 calculates the fonts attributes, such as its size, whether or not it is obliqued, and whether it is a solid or outlined font, from the full font name received and stores it in a data structure called FontAttributes. Then step 228 calls the CSR function CsrSetFontSpecs 151 with pFontld and FontAttributes.
FIG. 7 provides a more detailed description of CsrSetFontSpecs operation. In step 300, it searches the linked list of physical font records 302 shown at the top of FIG. 8, known as the physical font list, for a physical font record with a pFontlD value 304 pointing to the same physical font name as the pFontlD with which CsrSetFontSpecs has been called. If such a match is not fond, meaning the CSR has no record for the specified physical font, step 306 creates such a physical font record by performing steps 308, 310, and 312. Step 308 actually creates a new physical font record data structure 302, having the specified pFontlD value, and places it at the end of the physical font list. Step 310 calls the host document builder's GetFontinfo callback function 162 shown in FIG. 6, to get information from the font interpreter about the physical font and it places this information in the new physical font record. This includes the ORU resolution in which the font interpreter defines the moves, lines, and curves of that physical font's shapes. It also includes the name of the physical font. Step 312 calls the document builder's GetCharlD and ExecChar functions for each of a small sub-set of alphanumeric characters used in a process known as "hinting". For each such character, first it calls GetCharlD, which returns the character code used to identify that character in the first computer's font interpreter, and then it calls ExecChar with the character code GetCharlD returns for that character, to get the character's shape.
This is done to get a measure of the standard horizontal and vertical positions, and standard thickness associated with certain character features in the physical font. These hinting value are recorded in the physical font record, and are ultimately stored with the physical font in the portable document. This is done so they can be used by the character shape player to shift the position of important edges of a character's outlines when the character is rendered, so as to produce more attractive images, given the granularity of the pixel pattern used. Hinting is well known in computer font technologies. The important thing here is to note is that the hinting information recorded in the portable document 104 is derived not from hinting information contained in the pre-defined font descriptions in the first computers font resources, but rather from the actual positions and sizes of character features in the font.
ExecChar 164 is an important callback function used by both CsrSetFontSpecs and CsrDoChar. It is called by CSR functions with the name the font interpreter uses for a given character, which is normally the code for that character in the input text. It responds by calling the first computer's font interpreter 120 for that character in the current font indicated by pFontlD and FontAttributes. If the font is a scalable font, ExecChar responds to each move, line, quadratic Bezier curve, or cubic Bezier curve received from the font interpreter, respectively by calling CsrMoveTo, CsrLineTo, CsrQuadraticTo, or CsrCubicTo to deliver the definition of that move or outline segment to the CSR. In some document builders, if the font interpreter returns a bitmap pattern, ExecChar responds by performing edge detection on the bitmap, and then describes each edge detected to the CSR with an initial move to one of its points, followed by the sequence of lines between each successive point on that edge.
Whether or not the physical font record matching the specified pFontlD previously existed or was just created by steps 308, 310, and 312, step 314 makes that physical font records the currently active physical font.
Then step 316 searches the linked list of logical font records 318 associated with the currently active physical font record 302 for a logical font record having FontAttribute values 319 matching those with which CsrSetFontSpecs was called. These values include the fontMatrix, which defines how the physical font is to be scaled and slanted (if at all) to produce a character shape defined in document coordinates. It also includes information about whether or not the character shape is to be rendered in solid or outline form, and if in outline form, how thick the outlines should be and how they should join at angles. If such a prior logical font record having the specified FontAttributes is not found, step 320 creates a new logical font records at the end of the logical font list hanging from the current physical font record and records the specified FontAttribute values 319 in it. Then step 322 makes the previously existing or newly created logical font with matching FontAttributes the CSR's currently active logical font, and step 324 returns to the document builder with a code which uniquely identifies the currently active logical font pointed to by pFontCode.
After CsrSetFontSpecs returns to the document builder, step 230 places the FontCode 217A pointed to by pFontCode into the sequence of codes in the text 118 of the portable document. Once this is done the program advances to the top of loop 214
to process the next code received from the input text.
If the code received from the input text is a code 219 representing a character, the test in step 218 will be met and steps 236 and 238 will be performed.
Step 236 calls the CSR's CsrDoChar function 152 for the character. This function, which is shown in more detail in FIG. 9, is one of the most important parts of the CSR, because it actually performs the character-font shape recording process. Its first step, step 328, searches the binary tree of character records 330, shown in FIG. 8, which is hung off the currently active physical font record 302 for a character record having a charCode 332 matching that for which CsrDoChar has been called. The tree is a binary tree, a well known type of data structure, because each of its character record can point to two child character records, one through a pNextUp pointer 340 and one through a pNextDown pointer 342. Records are added to the tree such that all records descending from a given record which have a charCode less than that of the given record descend from the given record's pNextDown pointer and all records descending from it which have a higher charCode descend from pNextUp. This enables the tree to be rapidly searched, by following pNextDown or pNextUp, respectively, at each record if the specified charCode is less or greater than the charCode at that record. This process is followed until either a record which matches the specified charCode is found or a pNextDown or pNextUp with a zero pointer is found, meaning such a matching character record does not exist in the tree If such a matching charCode is found in one of the current physical font's associated character records, a previous call to CsrDoChar has already recorded the shape of the current character in the current font, and thus CsrDoChar has nothing further to do. In this case step 334 returns to the document builder. If such a match is not found, step 336 causes the rest of the steps shown in FIG. 9 to perform character shape recording.
The first step in the character shape recording, step 338, creates a new character record data structure 330 and inserts it into the binary tree at the appropriate location, given its charCode. If pRootCharacter has a zero value, the tree is empty indicating this is the first character being processed for the current physical font. In this case the new character record is inserted as the root of the tree and pRootCharacter is pointed to it. If the tree isn't empty, the new character record is inserted at the point at which the above described search of the tree encountered a zero pNextDown or pNextUp pointer, and that pointer is pointed to the new record. The system checks to see if the tree is unbalanced, with many more records depending from one side of some of its records than from the other. If so it is rearranged to balance it so that the tree has as few levels as possible, and thus can be searched most rapidly.
Once step 338 has inserted the character record for the character being processed into the character tree, step 340 initializes character shape processing by setting up its associated initial data structures, including the beginning of the character shape array 339 shown in FIG. 10. The character array 339 stores, in a succession of point structs 341, the points which describe the outline segments received from the document builder's ExecChar function 164. Then step 342 calls the document builder's ExecChar function 164 for the character, which responds by calling the CSR's CsrMoveTo, CsrLineTo, CsrQuadraticTo, and CsrCubicTo functions 153, 154, 155, and 156 shown in FIG. 6, for each move, line, quadratic Bezier curve, and cubic Bezier curve, respectively, supplied to ExecChar from the first computer's font interpreter. Once ExecChar has been called, CsrDoChar waits for ExecChar to return, and during this wait the CSR performs initial character shape recording through the operation of the Csr.sub.-- To functions 153-156 which ExecChar calls. For simplicity, in FIG. 9 and the description of it that follows that wait and the steps performed by the Csr.sub.-- To functions will be represented by the until loop 344 and the steps indented under it, as if they were part of the CsrDoChar function.
When the function called by ExecChar is CsrMoveTo, step 346 causes steps 348 and 350 to be performed. Step 348 tests to see if there is already an open contour structure 349A, as shown in FIG. 9, and if so it performs steps 352 and 354. The open contour structure 349A is used to receive information, including outline segments, derived from the shape of the current outline being processed in the current character-font combination for which CsrDoChar has been called. If there is such a previously open contour, the CsrMoveTo call indicates a move away from the outline it represents to the start of a new outline. In this case, step 352 finalizes the information in the previously open contour 349A and closes it. Then step 352 places that closed contour 349 into the contour tree 356, a hierarchical tree of such closed contour structures also shown in FIG. 10. Whether or not there was a previously open contour when the call to CsrMoveTo was made, by the time step 350 is reached there is not, and that step opens a new contour with its first point being that determined by the displacement indicated by CsrMoveTo.
When ExecChar calls CsrLineTo, CsrQuadraticTo, or CsrCubicTo, step 358 causes the steps 360, 362, 364, 366, and 368 indented under it in FIG. 9 to be executed.
Step 360 exits with an error if no contour is open, because CsrLineTo, CsrQuadraticTo, and CsrCubicTo all defined a line segment relative to a previously defined point in the current contour, and if there is no such contour open, the system would not know how to interpret them.
Step 362 stores the points associated with each successive outline segment by a Csr.sub.-- To function. Each call by ExecChar to CsrLineTo adds one point to the array, the on-outline endpoint of a line from the previous point in the array. Each call to CsrQuadraticTo adds two points to the array, first an off-outline control point of a quadratic Bezier curve which starts with the previous point in the array, followed by the on-outline endpoint of that curve. And each call to CsrCubicTo adds three points to the array, the two off-outline control points of a cubic Bezier curve which starts with the previous point in the array, followed by the on-outline endpoint of that curve.
Step 364 differentiates each curved segment received by a call to CsrQuadraticTo or CsrCubicTo to see if that curve contains an inflection point or an XY extreme point (actually a point having a horizontal or vertical tangent). If it finds any such points it marks them as such in the character shape array, or if such points are other than on an endpoint already in the character shape array, it subdivides the curve at such a marked point, and replaces the set of points representing the undivided curve with a set of points representing each of the curves resulting from the subdivisioin.
FIG. 11 shows a cubic Bezier curve 402 having an inflection point in its middle. This curve is originally represented by three points received from CsrCubicTo, first control point 404, a second control point 406, and an endpoint 408. The curve is also defined by the previous point 410 in the character shape array. Step 364 would detect that this curve has an inflection point 412. Since this point is not one of the curve's two endpoints 408 or 410, it subdivides the curves at the inflection point 412 into two new curves 411 and 413, each with two control points 415 and 416, and 417 and 418, respectively. The curve 411 has the inflection point 412 as its endpoint. The curve 413 has the endpoint 408 of the original curve as its endpoint. The points 415, 416, 412, 417, and 418 are inserted into the character shape array in place of the original curve's two control points 404 and 406. FIG. 12 shows a cubic Bezier curve 402A which is likewise split into two new curves at a horizontal tangent point.
Step 366 checks to see if there are any on-outline points in the character shape array which have line or curve segments defined on both sides of them in the array, and, if so, for each such point it checks to see if that point should be marked as a corner or tangent. Tangents are selected simply by picking points which are not labeled as a corner and which are between a curve segment and a line segment, where the line segment is of sufficient length that it is unlikely a single cubic Bezier curve could approximate the shape of both of them. Each such point is also compared with the maximum and minimum values for both the X and Y coordinates stored in the contours ContourBBox, and if it has a coordinate greater or lesser than any such maximum or minimum respectively, that maximum or minimum is updated to equal the coordinate. If the point is an X maximum, the direction of the angle formed at it, either clockwise or counterclockwise, as determined by the process of FIG. 13, is recorded as the contours actual direction.
FIG. 13 illustrates the process used to pick points which should be marked as corners and to associate a direction with such corners, if possible. This process is performed to insure that apparent corners which could have resulted from the outline resolution unit ("ORU") quantization in shape descriptions received by the CSR are not labeled as corner points. It comprises the steps 370-376.
Step 370 finds the left-most and the right-most vectors 1L and 1R, respectively, shown in FIG. 14B from the point 380 preceding the point 381 being tested in the character shape array to a square 384. This square is two outline resolution units (ORUs) on a side, and it is centered around the tested point 381. "Left" and "right" are defined relative to the direction in which outline segments have been received in the character shape array. Step 372 finds the left-most and right-most vectors 2L and 2R, respectively, from the point 381 being tested to a similar two ORU square 386 centered around the point 382 which follows the tested point in the character shape array.
The vectors 1L and 1R represent the range of possible directions for the vector from point 380 to point 381, given the possible quantization error in the location of each such point. Similarly, the vectors 2L and 2R represent the range of possible directions for the vector from point 381 to point 382, given the possible error in those points.
Where the segment before or after the tested point 381 is a curve, the point 380 or 382, respectively, will be an off-curve control point. This is not a problem, however, since the line from the endpoint of a quadratic or cubic Bezier curve to its nearest control point is the tangent of that curve at its endpoint, and, thus a line from the endpoint to that control point reflects the angle made with the adjacent outline segment at that endpoint.
Once steps 370 and 372 have calculated the vectors 1L, 1R, 2L, and 2R, steps 373, 374, 375, and 376 perform a series of tests to see how the tested point 381 should be labeled. Step 373 tests to see if the vectors 2L and 2R each form left angles greater than zero and less than one hundred and eighty degrees with both 1L and 1R. In the example of FIGS. 14, this means it tests to see if both vectors 2L and 2R fall within the angular range 377 shown in FIG. 14C. If this test is met, it means all possible vectors between points 381 and 382, given the possible quantization error, form a left angle with all possible vectors between points 380 and 381, given that possible error, and, thus, step 373 labels the tested point 381 as a definite left corner.
If the test of step 373 is not met, step 374 tests to see if the vectors 2L and 2R each form right angles greater than zero and less than one hundred and eighty degrees with both 1L and 1R. In the example of FIGS. 14, this means it tests to see if both vectors 2L and 2R fall within the angular range 378 shown in FIG. 14C. If the test of step 374 is met, it means that all possible vectors between points 381 and 382, given the possible quantization error, form a right angle with all possible vectors between points 380 and 381, given that possible error, and thus, it labels the tested point as a definite right angle.
If neither the tests in step 373 and 374 are met, step 375 tests to see if 2L forms a right angle which is greater than zero degrees and no greater than one hundred and eighty degree with 1R and it tests to see if 2R forms a left angle greater than zero degrees and no greater than one hundred and eighty degrees with 1L. In the example of FIGS. 14, this means it tests to see that no portion of the range of possible directions between 2L and 2R falls within the range of possible directions 381, shown in FIG. 14C, between 1L and 1R. If the conditions of step 375 are met, it means that none of the possible vectors between point 381 and 382, could form a straight line with any of the possible vectors between points 380 and 382, given that possible quantization error, and so step 375 labels the point as a definite corner. But it marks the point as a corner of either left or right angle, because neither the tests of steps 373 and 374 have been met.
If none of the tests in steps 373, 374, and 375 have been met, step 376 marks the point as not being a corner.
The application of these tests to the set of points shown in FIGS. 14A and 14B is shown in FIG. 14D. In this figure it can be seen that range of possible vectors between 2L and 2R falls into the portion 377 of the arc which is clearly to the left of the range of possible vectors between 1L and 2R. Thus, the test of step 373 is met and the tested point is labeled as a definite left turn, one which has too sharp an angle to have resulted from ORU quantization. This is indicated in FIG. 14A, because even if the X and Y value of each point 380, 381, and 382 were allowed to vary in either direction by the maximum ORU rounding error of one half ORU, as indicated by the one ORU squares 398 centered around those points, it would be impossible to draw a straight line 400, shown as a dotted line in the figures, through those points.
In the case shown in FIG. 1A-C, the apparent left angle between the points 380A, 381A, and 382A is sufficiently slight, given the distance between them, that a line 400A could be drawn which touches all three squares 398A, indicating that the apparent angle between the points could have been created by ORU rounding errors. As is indicated in FIGS. 15C, none of the tests of steps 373, 374, and 375 will be met because the range of possible vector directions between 2L and 2R does not lie entirely to the left, entirely to the right, or entirely out of the range of possible vector directions between 1L and 1R. This being the case, step 376 labels the tested point as a non-corner.
In the case shown in FIG. 16A-C, the apparent left angle is sufficiently sharp that it is clearly a corner, but the quantization error is large enough that it could actually be a right turn, as indicated by the dotted angled line 400A, rather than a left turn. In this case, as is indiated in FIG. 16C, the range of possible vector directions between 2L and 2R is neither entirely to the left of, or entirely to the right of, the range of possible directions indicated by 1L and 1R, and thus the tests of steps 373 and 374 will not be met. But that range of possible directions indicated by 2L and 2R is entirely outside of the range of possible directions indicated by 1L and 1R, and, thus, the test of step 375 is met and the tested point is labeled as a corner of either left or right direction. This being the case, the character shape recorder will use the point as a marked point for segmentation purposes in step 368 of FIG. 9, but it will not use the corner for a calculations of contour direction in step 366 of that figure if that corner is an X maximum. Instead it will leave the last definate direction, if any, associated with a corner which was at the time of its processing an X maximum as the actual direction of the contour.
Once steps 364 and 366 have been performed, step 368 performs steps 420, 422, 424, and 426 for the portion of the outline segment in the character shape array located between successive pairs of points which have been marked as inflections, XY extremes, corners, or tangents by steps 364 and 366.
Step 420 approximates any such portion of the outline, which may cover one or more segments in the character shape array, with a line or cubic Bezier curve. If the outline portion between the two marked points is a simple line or cubic Bezier curve, then that line or Bezier curve is used as the approximation. Otherwise, line or curve fitting techniques are used to find the approximation.
If the outline portion is approximated with a curve, step 422 calculates the "depth" of the approximating curve. That is, it calculates the number of times the curve has to be recursively sub-divided in two, before the worst error between such a subdivision and the vector between its endpoints would be less than one half ORU. This value is used by the character shape player when it reads the character shape from the portable font resource so it knows how finely it has to subdivide each curve to accurately render it with vector approximations.
FIG. 17 shows the steps of the main program which performs this depth analysis, and FIG. 18 shows the steps of the recursive subroutine which actually performs the recursive subdivision. The main program has four major steps 430, 432, 434, and
436.
Step 430 checks if the distance between the vector spanning the curve's endpoints and each of the curve's control points is less than one half ORU. If so, it returns with a depth of 0, since the curve does not need to be subdivided at all to be approximated within the limits of the rounding error by a vector between its endpoints. The distance between the vector and the curve's control points is used because, by the nature of cubic Bezier curves, such a vector can never have a greater distance to any point on its associated cubic Bezier curve than its greatest distance to one of that curve's control points, and because it is mathematically much simpler to find the maximum distance from the vector to the two control points than it is to find the maximum distance from the vector to the curve.
If the test of step 430 is not met, step 432 calls the RecursiveSubdivision subroutine of FIG. 18. As shown in FIG. 18, this subroutine is called with pointers to the 1stEnd, 1stControlPoint, 2ndControlPoint, and 2ndEnd of the cubic Bezier curve it is to subdivide. It is also called with the depth of is recursion. The subroutine comprises steps 440, 442, 444, 446, and 448.
Step 440 tests to see if the value of depth with which the subroutine is called is greater than the current value of maxDepth, the maximum depth reached so far by any recursion performed on the entire curve. If so it sets the value of maxDepth equal to the recursion's depth. Then step 442 finds the midpoint of the Bezier curve with which the recursion has been called and divides that curve into two new two Bezier curves at that midpoint. Then step 444 finds which of the new sub-curves has the greatest distance from a vector between its endpoints and one of its two control points. Once this has been done, step 446 tests to see if this greatest distance is less than one half ORU. If so, step 446 stores 1stEnd and 2ndEnd in a structure called deepestSubCurve, so the routine shown in FIG. 17 will be able to tell where the curve with the deepest recursion ended, and it returns to that routine. If not, step 448 calls the RecursiveSubdivision subroutine for the newly formed sub-curve with the greatest distance between a vector spanning its endpoints and one of its two control points.
As those skilled in computer programming will appreciate, this RecursiveSubroutine will keep dividing a given Bezier curve in half, picking the worst fitted half, and then dividing that half in half, until the worst fitted half is fitted to within one half ORU. At that point maxDepth will hold the level of the deepest recursion and deepestSubCurve will hold the endpoints of the deepest sub-curve. Then the deepest recursion will return to the recursion that called it, and that recursion will return to the recursion that called it, and so on, until the initial calls to RecursiveSubroutine returns to step 432 of FIG. 17.
At this point step 434 tests to see if one of the endpoints of the deepest sub-curve stored in deepestSubCurve is one of the end points of the entire curve for which the depth calculation is being made. If so, it calls the RecursiveSubdivision subroutine again, this time for the half of the entire curve which contains the opposite end of the entire curve from that containing the deepest sub-curve found by the prior recursion. This is done because the deviation between the subdivisions of a given cubic Bezier curve and vector approximations to those subdivision will either have one local maximum, which is the global maximum for the entire curve, somewhere between the curve's two endpoints, or two local maximum located at each of the curve's two endpoints, one of which might require deeper recursion than the other. In the first case, the recursion of the first call to the RecursiveSubroutine in step 432 are guaranteed to catch the maximum deviation for the entire curve. But in the second case, the half of the entire curve which has the greatest deviation at the first level of recursion might not be the one having the end with the deepest local maximum, and, thus, the recursions of step 432 might not find the curves true maximum depth. Step 434 causes the recursion to be performed for the other half of the entire curve in this second case to ensure that the depth of both ends of the entire curve will be found, so that maxDepth will contain that deepest depth.
The depth finding algorithm shown in FIGS. 17 and 18 significantly speeds the operation of the character shape recording because it only pursues recursion on the half of each sub-curve which is worst fitted by a vector, thus preventing the amount of computation required for the depth analysis from going up exponentially with the depth of the curve.
Returning now to FIG. 9, after step 422 has been completed, step 424 inserts the approximated segment calculated by step 420 into the point array 339A of the open contour struct 349A shown in FIG. 10. It can be seen that the segmentation of the outline segments represented by points on curve and control points in the contour's point array are dependent on the horizontal and vertical tangents, inflection points, filtered corners, and boundaries between curves and significant lines found in the shape defined by the outline segments received from ExecChar calls to the CSR, rather than by the actual segmentation of those received outline segments.
Once newly approximated outline segments have been placed into the open contour 349A, step 426 deletes from the character shape array all points which are not part of a segment which has not yet been approximated or which are not needed to process such an unapproximated segement. It does this to conserve memory, since such points have no further use.
Either step 346 or 358 and its respective sub-steps are repeated for each of ExecChar's calls to the CSR during the processing of a given character-font shape.
Each subsequent time a call to CsrMoveTo is received from ExecChar, it indicates the end of the description of one contour, or outline, in the shape being described by ExecChar and either the beginning of another such contour or, if there are no more such contours, the move to the starting position for the next character which marks the completion of that shape's description by ExecChar. In either case, when such a subsequent call to CsrMoveTo is received, step 352 completes and closes the open contour 349A and step 354 places in its proper place into the contour tree.
Step 354 places it into the hierarchical contour tree 356 as follows:
If the contour tree is empty, it points a global variable pContourRoot to the new contour. If the contour tree is not empty, scan the list of contours at the top level. For each scanned contour, if the new one encloses it, remove the scanned contour from the list and add it to the new contour's daughter list, pointed to by pDaugther 452. If the new contour is enclosed by the scanned contour, restart the scanning process with the scanned contour's daughters. When the end of the list being scanned is reached, add the new contour to the list. The actual contour insertion process maintains a consistent order for sibling lists to ensure that the glyph matching, described below, is reliable. The order is based on the value of xmin in the contour's bounding box, ContourBBox. In the event of a tie, the order ymin, xmax, or ymax is used until a difference is found. There should be no case of distinct sibling contours that have identical bounding boxes.
In the example shown in FIG. 10, the contour 349B associated with the outside outline of the circle in the registered trademark symbol 453, will ultimately be placed at the first, or highest, level of the contour tree because it enclose all that symbol's other contours. The contour 349C, associated with inside outline of that circle, will be a 2nd level contour. The contour 349D, associated with the outside outline of the "R" in the registered trademark symbol, will be a 3rd level contour. And the contour 349E, associated with the inside outline of the "R" will be a fourth level contour. It should be understood that some characters will have multiple contours at one level. For example, the shape "%2" will have three contours all at the first level, whereas the shape "B" will have one contour at the first level and two depending from it at that second.
Once ExecChar returns to CsrDoChar at step 460 shown in FIG. 9, each outline of the character-font shape should be recorded in a closed contour structure 349, and each of those structures should be organized into a hierarchy indicating which encloses which. At this point an open contour exists which was created by step 350 by the last CsrMoveTo called by ExecChar, that associated with the character-font shape's escapement. Step 460 saves the location of the initial point in this open contour to calculate the escapement value for the shape being recorded and closes the open contour.
Then step 462 splits the contour tree 356 into two level sub-trees. That is, it groups each odd level contour and its zero or more daughter contours into a sub-tree 355. For example, in FIG. 10, the first level contour 349B, which represents the outside outline of the circle of the ".RTM." symbol, and the contour 349C, which represent inside contour of that circle will be grouped into one sub-tree, and the contour 349D and 349E which represent the outer and inner outlines of that symbols "R" are grouped into another subtree. It turns out that each of these two level subtrees corresponds to a glyph element, that is, to an unconnected solid shape.
Once the contour tree has been separated into sub-trees corresponding to glyph elements, step 464 performs steps 466, 468, 470, 472, 474, 476, and 478 for each such glyph element.
Step for 466 standardizes the direction of the contour. That is, it checks to see if the sequence of outline segments in the top level, or outer, contour in each glyph element has a counter-clockwise direction, and if not it reverses the order of those segments to have such a counterclockwise direction. Similarly, it check to see if the segments of the second level, or inner, contours of the glyph have a clockwise direction, and if not it orders them to have that direction. This has the advantage of having the inner and outer contours of all glyph elements have the same direction, respectively, regardless of the direction in which those contours were delivered to the CSR.
Step 468 picks a standard start point for each contour. Because each contour is closed, the start point is arbitrary. However, in order to facilitate glyph matching and to optimize playback performance, the start point for each contour is picked based on a few simple rules. For outer contours, the start point is chosen to be the lowest point in the contour. If there are several equally lowest points, the rightmost one is chosen. For inner contours, the start point is chosen to be the highest point in the contour. If there are several equally highest points, the rightmost one is chosen. The indexes of both possible start points is already set in the contour data structure during character shape processing.
Picking the appropriate point is therefore simply a case of picking one of two indexes based on the desired direction of the contour.
Step 470 builds edge and stroke lists. Edge lists are lists of all horizontal and vertical edges of any significance, including horizontal and vertical tangents, in the shape. Strokes are pairs of such edges which represent the opposing sides of a given horizontal or vertical feature in the shape. These values are used in hinting.
Step 472 generates a glyph record 482 and glyph program string ("GPS") 484, as shown in FIG. 10, for the glyph element. The glyph program string represents the sequence of outline segments in each of the glyph element's associated contours after those sequences have been standardized in steps 466 and 468 in the order in of those contours in the glyph element's associated sub-tree 355. It can be seen that the shape description is independent of any aspects of sequence of outline segments received from ExecChar for the glyph's shape which are not mandated by that shape itself. This GPS is added to the end of a sequence of GPSs in the GPS memory. Its location and size in this memory is indicated by glyphProgramStringOffset 454 and glyphProgStringSize 452, respectively, in the Glyph record. The glyph record also calculates a glyph signature 456. The signature is a compact byte string that has a high probability of uniquely identifying a glyph. This identification is independent of position and scale factor. It includes the glyph's number of contours, the number horizontal and vertical edges calculated in step 470, the relative size of the right most stroke calculated, the relative position of the left edge of rightmost stroke, the relative size of the topmost stoke, the relative position of lower edge of topmost stroke, the number of outside corners in outside contour, the number of inside corners in outside contour, the number of outside corners in inside contours, and the number of inside corners in inside contours. In this signature the positions and sizes are all relative to the glyph's bounding box, so that glyphs of the same shape, but different size, will have the same signature.
Once a new glyph record 482 and its associated new GPS 484A have been created, step 474 searches a binary tree 481, shown in FIG. 19, of all the glyph records 482 made for previously recorded glyph shapes. It searches this tree for a glyph record having the same signature. This tree is organized into a binary tree by the numerical value comprised of the collective bytes in each glyph record's signature. This is done to facilitate rapid searching for matching glyph shapes. In each glyph record in the tree, the pointer pNextDown 482 points to the descending branch of the tree whose glyph records have signatures with a lower value. The pointer pNextUp 484 to the descending branch whose corresponding glyph values have higher signature values. And the pointer pNextEqual 486 points to the glyph records, if any, which have the same signature value. A group of glyph records 482C, having equal signature values is shown in FIG. 19.
If the search finds a glyph record 482B, as shown in FIG. 19, having the same signature as a new glyph record 482A, step 476 performs steps 488 and 490. Step 488 compares the sequence of points in the GPS 484B pointed to by the glyph record 482B having the same signature as the new glyph record 482A with the points in the new glyph record's associated GPS 484A. Before this match is done the bounding boxes of the two glyph shapes are normalized to the same size, so the match will be scale independent. This enables the shape of the "R" in ".RTM." to match that in "R", and the shape of the "1" in "1/2" to match that in "1". In the example shown, is it assumed the points in the GPS 484B associated with glyph record 482B do not match those of the new glyph record's GPS 484A.
If there are a group of sibling glyph records in the glyph tree whose signature matches that of the new glyph record 482A, then the new glyph record's associated GPS 484A is compared against the GPS's of each of those sibling glyph records. In the example of FIG. 19, this means GPS 484A is also compared against the GPS 484D, associated with the glyph record 482D. In the example, it is assumed these two GPSs match.
The ability to make such a match rapidly is greatly facilitated by the fact that the order of contours, the direction of contours, and the start point of contours in each GPS are standardized, and independent of the particular manner in which the shape of that glyph was delivered to the CSP by ExecChar. This means that glyphs with the same shape, whether received from different characters, different fonts, or even different font description languages will almost always have the exact same GPS, allowing for scaling and rounding errors, and thus can be rapidly matched.
If an exact match, allowing for rounding error, is found, as in the case of GPSs 484A and 484D in FIG. 19, step 490 normally deletes the new glyph record's GPS 484A, and points the glyphProgramStringOffset and glyphProgramStringSize values in the new glyph record 482A to the matching GPSs 484D. If the new glyph record's GPS has a different size than the previously recorded matching GPS, scaling information to convert the glyph described in the previously recorded matching GPS to the proper size is associated with the new glyph