Winding order test for digital fonts

• US 7,639,258 B1
• Filed: 08/15/2006
• Issued: 12/29/2009
• Est. Priority Date: 03/31/2004
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Arnold, R. David, Dowling, Terence S.
• Primary Examiner(s): Sajous; Wesner
• Application Number:
  US11/464,743
• Time in Patent Office: 1,232 Days
• Field of Search: 345/586, 345/606, 345643-644, 345441-443, 345467-472, 382/181, 382/197, 382201-203, 382/185, 382/224, 358/1.1, 358/525, 715/263, 715/269
• US Class Current: 345/469
• CPC Class Codes: G06F 40/126 Character encoding
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves

Abstract

Methods and apparatus, including computer program products, that implement a method for determining a winding order for a glyph associated with a font. The glyph has an outline that has an outside path. In one aspect, a method includes identifying four extrema points of the outline, each being an intersection of two vectors obtained from the outline; and for each of the points, calculating a cross product of the two vectors intersecting at the point. A positive result indicates that the outside path is wound in a first direction, and a negative result indicates that the outside path is wound in an opposite, second direction. The winding order of the outside path is determined based on the cross products calculated. In a particular implementation, the method determines that the outside path is wound counter clockwise when three or four of the results are positive.

Claims

1. A computer-implemented method, comprising:

receiving a glyph, the glyph having an outline that has an outside path;

identifying four extrema points of the outline, each extrema point being an intersection of two vectors obtained from the outline;

for each of the extrema points, calculating a cross product of the two vectors intersecting at the extrema point, wherein a positive result of the cross product indicates that the outside path is wound in a first direction, and wherein a negative result of the cross product indicates that the outside path is wound in an opposite, second direction; and

determining a winding order of the outside path based on the cross products calculated;

wherein the receiving step is performed by a computing device.

2. The method of claim 1, wherein the first direction is counter clockwise and the second direction is clockwise.

3. The method of claim 1, wherein the glyph is associated with a font, and determining the winding order of the outside path comprises:

determining that the outside path is wound in the first direction when three or four of the cross product results are positive, regardless of a default winding order for the font.

4. The method of claim 1, wherein the glyph is associated with a font, and determining the winding order of the outside path comprises:

determining that the outside path is wound in the second direction when three or four of the results are negative, regardless of a default winding order for the font.

5. The method of claim 1, wherein the glyph is associated with a font and a font type, and determining the winding order of the outside path comprises:

determining that the outside path is wound in a default winding direction unless the cross products indicate otherwise, the default winding direction being obtained from the font and the font type.

6. The method of claim 1, wherein the glyph is associated with a font, and determining the winding order of the outside path comprises:

determining that the outside path is wound in a default winding direction for the font when two of the results are positive and two of the results are negative.

7. The method of claim 1, further comprising:

identifying, based on the winding order of the outside path, an outward direction for a line segment tangent to the outside path.

8. The method of claim 7, further comprising:

providing the outward direction to a rasterizer of a rendering engine.

9. The method of claim 1, further comprising:

providing the winding order to a rasterizer of a rendering engine.

10. A computer-program product, tangibly stored on non-volatile memory, the product comprising instructions operable to cause a computing device to perform a method comprising:

receiving a glyph, the glyph having an outline that has an outside path;

identifying four extrema points of the outline, each extrema point being an intersection of two vectors obtained from the outline;

for each of the extrema points, calculating a cross product of the two vectors intersecting at the extrema point, wherein a positive result of the cross product indicates that the outside path is wound in a first direction, and wherein a negative result of the cross product indicates that the outside path is wound in an opposite, second direction; and

determining a winding order of the outside path based on the cross products calculated.

11. The product of claim 10, wherein the first direction is counter clockwise and the second direction is clockwise.

12. The product of claim 10, wherein the glyph is associated with a font and determining the winding order of the outside path comprises:

determining that the outside path is wound in the first direction when three or four of the results are positive, regardless of a default winding order for the font.

13. The product of claim 10, wherein the glyph is associated with a font, and determining the winding order of the outside path comprises:

determining that the outside path is wound in the second direction when three or four of the results are negative, regardless of a default winding order for the font.

14. The product of claim 10, wherein the glyph is associated with a font and a font type, and determining the winding order of the outside path comprises:

determining that the outside path is wound in a default winding direction unless the cross products indicate otherwise, the default winding direction being obtained from the font and the font type.

15. The product of claim 10, wherein the glyph is associated with a font, and determining the winding order of the outside path comprises:

determining that the outside path is wound in a default winding direction for the font when two of the results are positive and two of the results are negative.

16. The product of claim 10, further comprising:

identifying, based on the winding order of the outside path, an outward direction for a line segment tangent to the outside path.

17. The method of claim 16, further comprising:

providing the outward direction to a rasterizer of a rendering engine.

18. The product of claim 10, further comprising:

providing the winding order to a rasterizer of a rendering engine.

19. A system comprising:

means for receiving a glyph, the glyph having an outline that has an outside path;

means for identifying four extrema points of the outline, each extrema point being an intersection of two vectors obtained from the outline;

means for calculating a cross product of the two vectors intersecting at the extrema point for each of the extrema points, wherein a positive result of the cross product indicates that the outside path is wound in a first direction, and wherein a negative result of the cross product indicates that the outside path is wound in an opposite, second direction; and

means for determining a winding order of the outside path based on the cross products calculated.

20. The system of claim 19, further comprising:

means for identifying, based on the winding order of the outside path, an outward direction for a line segment tangent to the outside path;

means for providing the outward direction to a rasterizer of a rendering engine; and

means for providing the winding order to a rasterizer of a rendering engine.

21. The system of claim 19, wherein the first direction is counter clockwise and the second direction is clockwise.

22. The system of claim 19, wherein the glyph is associated with a font, and the means for determining the winding order of the outside path comprises:

means for determining that the outside path is wound in the first direction when three or four of the results are positive, regardless of a default winding order for the font.

23. The system of claim 19, wherein the glyph is associated with a font, and the means for determining the winding order of the outside path comprises:

means for determining that the outside path is wound in the second direction when three or four of the results are negative, regardless of a default winding order for the font.

24. The system of claim 19, wherein the glyph is associated with a font and a font type, and the means for determining the winding order of the outside path comprises:

means for determining that the outside path is wound in a default winding direction unless the cross products indicate otherwise, the default winding direction being obtained from the font and the font type.

25. The system of claim 19, wherein the glyph is associated with a font, and the means for determining the winding order of the outside path comprises:

means for determining that the outside path is wound in a default winding direction for the font when two of the results are positive and two of the results are negative.