1. The Field of the Invention
The present invention relates to rendering graphical objects such as text. More specifically, the present invention relates to appropriately rendering a graphical object when a corresponding outline has excessive control points.
2. Background and Related Art
Computing technology has transformed the way we work and play. Computing systems now take a wide variety of forms including desktop computers, laptop computers, tablet PCs, Personal Digital Assistants (PDAs), and the like. Even household devices (such as refrigerators, ovens, sewing machines, security systems, and the like) have varying levels of processing capability and thus may be considered computing systems. As time moves forward, processing capability may be incorporated into a number of devices that traditionally did not have processing capability. Accordingly, the diversity of computing systems may likely increase.
Almost all computing systems that interface with human beings use a display to convey information. In many cases, the appeal of the display is considered an important attribute of the computing system. Display of textual information (e.g., Latin-based characters) typically includes processing glyphs that represent characters of a font. A glyph includes control points and instructions for connecting the control points such that an outline of a corresponding character can be generated in an arbitrary grid space (e.g., a pixel grid). Often, characters will be defined for display at a larger size and higher resolution and then mathematically scaled down (or otherwise manipulated) when the characters are to be rendered at smaller sizes and lower resolutions (or as bold, italic, etc.). Thus, a reduced number of descriptions, and potentially only one description, for a character (per font) need be stored.
To scale down a character, the location of control points can be divided by a scaling factor. For example, to scale a character down by a scaling factor of 10, the coordinates of each control point defining the character (at the higher resolution) can be divided by 10. It may be that control points defining a character for display on a 100×100 grid are to be scaled down for display on a 10×10 grid. Thus, a control point at grid position (50, 30) can be scaled down to a control point at grid position (5, 3), a control point at grid position (70, 70) can be scaled down to a control point at grid position (7, 7), etc. Accordingly, a smaller outline representing the character may be calculated and there is a reduced need for storing a number of different sizes of bit-maps for the character.
The smaller outline can then be analyzed to identify grid locations (e.g., pixels) that are to be turned on and that are to be turned off (a process often referred to as “scan conversion”). One scan conversion algorithm determines if the center of a grid position is inside or outside a resulting scaled down outline. When the center of a grid position is inside the scaled down outline the grid position is turned on. On the other hand, when the center of a grid position is outside the scaled down outline the grid position is turned off.
Unfortunately, at times, and especially at lower resolutions, the results of scan conversion produce an unacceptable representation of a character. Unacceptable character representations can result from rounding errors in the scaling down process or from the scan conversion process itself. Further, rounding errors have a greater affect on character representation when a single grid location (e.g., a pixel) is on scale with the features of a character. For example, a rounding error that causes one grid location to be inappropriately turned on (or turned off) on a 50×50 grid may not even be detectable by the human eye. However, a rounding error that causes one grid location to be inappropriately turned on (or turned off) on a 4×4 grid may result in a character that is perceived as unacceptable to the human eye. Thus, at lower resolutions scan conversion can even fail to preserve the topology of the original outline of the character, for example, causing disconnected grid locations, inappropriately located features, and lack of symmetry.
For example, when an outline has a reduced number of control points associated with a corresponding character feature, scan conversion of the outline can result in the corresponding character feature being rendered at a non-optimal location in a grid space. A number of characters in Latin (Greek, Cyrillic, etc.) fonts have a horizontal stroke (“cross-bar”) somewhere between the top and the bottom of the character. For example, a capital “H” has a cross-bar approximately halfway between the top and the bottom. FIG. 1 depicts an outline 100 of Times New Roman capital “H”. By design, the position of the cross-bar is marginally above the mathematical halfway point of the vertical stroke of the “H”. That is, distance 101 is less than distance 102.
However, by the time the “H” is rendered at a smaller size and lower resolution (e.g., 9 pt on a 96 dpi device), accumulated quantization errors can result in the cross-bar being rendered below the mathematical halfway point. Rendering the cross-bar below the half-way points is less than optimal, since the cross-bar was, by design, to be rendered above the halfway point. Pixel pattern 103 represents the pixels that would be turned on to render Times New Roman capital “H” at 9 pt and at 96 dpi resolution (i.e., the results of performing scan conversion on outline 100). As depicted in pixel pattern 103, the cross-bar is below the mathematical halfway point of the vertical stroke of the “H”.
One cause of non-optimal rendering results from the “H” having control points on the edges of the cross-bar, but not having control points, for example, on an imaginary line (represented by dashed line 104) along the center between the edges of the cross-bar. Traditional hinting solutions thus add a first constraint to a first control point, for example, on the top edge of the cross-bar (control point 107). The first constraint enforces a proportional position of the first control point in vertical direction relative to other control points on the base line (e.g. control point 109) and the caps line (e.g., control point 106). Subsequently, traditional solutions also add a second constraint to a second control point, for example, on the bottom edge of the cross-bar (control point 108). The second constraint enforces a distance between the second control point on the bottom edge and the previously constrained first control point (control point 106) on the top edge.
Since both the first and second constraints will have to round positions in the vertical direction to the nearest grid position (e.g., pixel), each of the first and second constraints can introduce a rounding error of up to half a pixel, either way (up or down). In unfortunate cases, these rounding errors accumulate (e.g., both the first and second constraints round down)—to place the cross-bar below the mathematical halfway point.
Further, when an outline passes through the center of one or more grid locations, scan conversion of the outline can result in the character being rendered asymmetrically in a grid space. Italic fonts pose a particularly challenging problem because the jagged nature of diagonal strokes makes italic fonts more difficult to process, and quantization errors can compound the problem.
As previously mentioned, all scan-converters have to define is an interior pixel, even in cases where a pixel could just as well be an interior or an exterior pixel (e.g., when an outline passes through the center of the pixel). For example, TrueType® defines that when an outline is through the center of a pixel, the pixel is to be turned on. Thus, if an outline is a straight line, and if the line's run and rise (slope) reduce to a pair of odd numbers, the outline will pass through one or more pixel centers, and TrueType® will turn on a pixel, which may look like an extra pixel.
Referring now to FIG. 2, FIG. 2 depicts an Arial Italic Capital “H”. The right edge of the left italic stroke (from control point 211 to control point 214) may rise 5 pixels for every pixel it runs across—a total of 2 pixels over and 10 pixels up, which reduces to a pair of odd numbers 1 and 5—and we can readily observe extra pixels (pixels 231, 232, and 233). Further, even when pixels having their centers exactly on an outline are turned off problems can still occur. For example, in FIG. 2, if pixels whose centers are exactly on the outline were to be turned off (instead of on), there would be two missing pixels (pixels 234 and 236), yielding a discontinuity in the pixel pattern. One approach is to define pixels whose centers are exactly on an outline to alternate between interior and exterior pixels as edges alternate between left and right edges. While this could solve the problem for some italic strokes, such an alternating approach would also introduce new problems on round strokes. For example, such an alternating approach could lead to asymmetrical pixel patterns in characters such as, an “O”.
Further, any movement of control points to comply with constraints can cause control points to be moved to inexact locations. Utilizing a control point that is at an inexact location for further calculations can result in non-optimal rendering of a corresponding character in a grid space. Often, hinting control points can include aligning some control points with other control points. For example, still referring to FIG. 2, control points 212 and 213 may have to be aligned with control points 211 and 214 because control points 211 and 214 may have been moved as a result of complying with their own constraints (e.g., constrained to caps and base lines respectively). While the act of aligning is a mathematically exact concept, its implementation in terms of a font hinting language (e.g., TrueType®) likely introduces numerical inaccuracies, because the internal numerical precision of font hint processors is typically limited. For example, the font hinting language TrueType® uses 6 binary places to store fractional control point location data and thus every numerical result can be accurate to only 26th or 1/64 of a pixel. Accordingly, the result of aligning, for example, control point 212 with its parent points 211 and 214 will be accurate to the nearest 1/64 of a pixel only—at best.
More specifically, since the line from control point 214 to control point 211 is 2 pixels over and 10 pixels up (as depicted in pixel pattern 203), it will run 0.2 pixels over for every pixel up. Accordingly, it should be 1.2 pixels over at control point 3, because control point 3 is 6 pixels up, or in terms of 1/64 of a pixel, it should be 1 12.8/64 pixel over. Unfortunately, 12.8/64 is beyond the precision limit of most, if not all, font hint processors. That is, 12.8/64 simply cannot be represented, and has to be rounded one way or the other (e.g., up or down to the nearest 1/64). Hint processors are typically configured with a default rounding behavior, for example, to always truncate, always round down, or always round up. In FIG. 2, and seemingly by chance, control points of the cross-bar are rounded down, even though rounding up would be a better approximation of the actual value (12.8 is closer to 13 than to 12). This error appears to be harmless, because it led neither to a spurious pixel, nor to a missing pixel.
Conversely, for control point 215, which again is over by 1 12.8/64 pixel, rounding down did lead to a spurious pixel (pixel 235), while rounding up would have prevented it. Moreover, the generality of typical font hint processors can produce results that are off by a fraction of a pixel, irrespective of the direction of rounding. Thus, even if rounding were to be correct, alignment problems can still result.
Additionally, character outlines that have too many control points can result in non-optimal rendering of a corresponding character in a grid space. For example, erroneous pixels can potentially arise when the exact shapes of outlines have increased complexity. For example, FIG. 3 depicts a Palatino Italic “H”. The Palatino Italic “H” includes significantly more control points than the Arial Italic “H” depicted in FIG. 2. The edges of the strokes of the Palatino Italic “H” are slightly curved, and thus include extra control points to model these curves. As depicted in FIG. 3, these control points are positioned in a seemingly random fashion on outline 300. Applying traditional scan conversion to outline 300 would result in a non-optimal pixel pattern, such as, for example, pixel pattern 303.
Unfortunately, some hint processors refer to control points by consecutive number and removing a control point can cause other control points to be renumbered. Thus, renumbering control points can cause existing hinting instructions to refer to incorrect control point numbers. For example, removing what may be viewed as extraneous control points on outline 300 could cause existing hints to be inappropriately applied to any remaining control points (or not be applied at all). Inappropriate application of hints to remaining control points can significantly degrade a corresponding pixel pattern.
Accordingly, to compensate for the sometimes non-optimal or inappropriate results of scan conversion (e.g., at lower point sizes and lower resolutions), a human typographer programmatically controls the scan conversion process on an ad-hoc basis by manually adding delta-exception hints (e.g., TrueType® instructions) to character outlines. Delta-exception hints are hints which are specific to individual characters and specific to a particular type size. That is, for each type size (of a font) at which there is an unfortunate quantization problem, the human typographer has to add possibly a plurality of delta-exception instructions, as appropriate. Since delta-exception hints are so specific, delta-exception hints are typically stored along with the character the delta-exception hints will be applied to (e.g., in a font file). Moreover, the use of delta-exception hints is an iterative process requiring repeated visual inspection of a plurality of type sizes before and after the application of corresponding exception instructions, which is laborious and prone to introduction of inconsistencies.
Due in part to the wide variety of different artistic and technical features in different fonts, delta-exception hints must also be tailored to an individual font. That is, delta-exception hints for one font typically can not be reused for other fonts (even for the same character). Thus, for each new font, a typographer is required to iteratively determine appropriate delta-exception hints. Accordingly, the resources needed to compensate for non-optimal or inappropriate results of scan conversion across a variety of different fonts can be quite large. Therefore, what would be advantageous are mechanisms for automating the optimization of pixel patterns.