Patent US6088041A successfully refreshed from Google Patents.
US6088041A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of dropout control for scan conversion of a glyph comprising a plurality of discrete segments
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-06-27
•
Granted: 2000-07-11
•
Expires: 2017-06-27
Abstract
Abstract An improved scan converter to support the efficient and accurate display of character outlines by pixel-oriented display devices. To conserve the finite resource of memory, the improved scan converter supports an efficient use of available memory workspace by accurately determining an upper bound for the amount of memory required to support scan conversion calculations. To achieve improvements in speed and character image quality, the improved scan converter renders the spline segments of a character outline by using a second order equation to calculate an implicit function based on the control points of each segment. The improved scan converter further addresses in a systematic manner the rendering of an endpoint located on a scan line to determine whether the pixel associated with the endpoint should be activated. This decision is based upon the direction of approach to and exit from this endpoint for the pair of segments connected to the endpoint. The improved scan converter also reduces the number of calculations requiring sub-pixel precision to support the selection of a pixel located nearest the contour, thereby providing an improved solution for dropout condition.
Inventors
- 👤 Dean Dayton Ballard
- 👤 Eliyezer Kohen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 18:47
CPC Classifications
G; G06; G06T; G06T11/00; G06T11/20; G06T11/23; G06T9/00
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
238 words
A method of dropout control for scan conversion of a glyph comprising a plurality of discrete line segments and spline segments, comprising: detecting each intersection of one of said plurality of said segments, each of said intersections representing a transition entry defined by pixel coordinates and a transition sense value, and placing in response thereto each transition entry into one of a pair of transition tables, said transition tables having opposite transition sense values; detecting a potential dropout in response to a selected pair of said transition entries generated by first and second ones of said plurality of segments crossing a particular one of plurality of scan lines, said selected pair of transition entries being in said transition tables for a same location of said pixel coordinates through which said particular scan line passes and having opposite transition sense values; retrieving from said transition tables said pixel coordinates associated with said selected pair of transition entries; determining with sub-pixel accuracy first scan-direction coordinates for the intersection of said first segment and said particular scan line based upon the type of said first segment; determining with sub-pixel accuracy second scan-direction coordinates for the intersection of said second segment and said particular scan line based upon the type of said second segment, and determining a pixel having a pixel center nearest to a midpoint between said first and second scan-direction coordinates and activating the pixel having said nearest pixel center.
Claim 2
Independent Claim
238 words
A method of dropout control for scan conversion of a glyph comprising a plurality of discrete line segments and spline segments, comprising: detecting each intersection of one of said plurality of said segments, each of said intersections representing a transition entry defined by pixel coordinates and a transition sense value, and placing in response thereto each transition entry into one of a pair of transition tables, said transition tables having opposite transition sense values; detecting a potential dropout in response to a selected pair of said transition entries generated by first and second ones of said plurality of segments crossing a particular one of plurality of scan lines, said selected pair of transition entries being in said transition tables for a same location of said pixel coordinates through which said particular scan line passes and having opposite transition sense values; retrieving from said transition tables said pixel coordinates associated with said selected pair of transition entries; determining with sub-pixel accuracy first scan-direction coordinates for the intersection of said first segment and said particular scan line based upon the type of said first segment; determining with sub-pixel accuracy second scan-direction coordinates for the intersection of said second segment and said particular scan line based upon the type of said second segment, and determining a pixel having a pixel center nearest to a midpoint between said first and second scan-direction coordinates and activating the pixel having said nearest pixel center.
Claim 3
Dependent Claim
40 words
The method recited in claim 1, wherein placing each transition entry into one of said pair of transition tables comprises assigning a unique index number to each transition entry and placing each transition entry within one of said transition tables.
Claim 4
Dependent Claim
70 words
The method recited in claim 2, wherein retrieving said pixel coordinates corresponding to each of said pair of transition entries for said first segment and said second segment comprises locating said index number for each of said first segment and said second segment, said pixel coordinates being retrieved to supply an initial set of pixel coordinates for supporting the determination, in sub-pixel coordinates, of said first and second scan-direction coordinates.
Claim 5
Dependent Claim
95 words
The method recited in claim 1, wherein determining with sub-pixel accuracy said first scan-direction coordinates for the intersection of said first segment and said particular scan line comprises: if said first segment is a line segment, then solving simultaneous linear equations to determine with sub-pixel accuracy said first scan-direction coordinates for the intersection of said first segment and said particular scan line; and if said first segment is a spline, then using recursive division to determine with sub-pixel accuracy said first scan-direction coordinates for the intersection of said first segment and said particular scan line.
Claim 6
Dependent Claim
95 words
The method recited in claim 4, wherein determining with sub-pixel accuracy said second scan-direction coordinates for the intersection of said second segment and said particular scan line comprises: if said second segment is a line segment, then solving simultaneous linear equations to determine with sub-pixel accuracy said second scan-direction coordinates for the intersection of said second segment and said particular scan line; and if said second segment is a spline, then using recursive division to determine with sub-pixel accuracy said second scan-direction coordinates for the intersection of said second segment and said particular scan line.
Claim 7
Dependent Claim
13 words
A computer-readable medium having computer-executable instructions for performing the method of claim 1.
Claim 8
Dependent Claim
13 words
A computer-readable medium having computer-executable instructions for performing the method of claim 5.
Claim 9
Dependent Claim
11 words
A computer system adapted to perform the method of claim 1.
Claim 10
Independent Claim
182 words
A method for correcting dropout while scan converting a glyph, comprising: without calculating sub-pixel coordinates, detecting a first intersection of a first segment of the glyph with a scan line of a pixel grid on which the glyph is superimposed; storing a first transition entry that includes a first transition sense and first coordinates of a first pixel center adjacent to the first intersection; without calculating sub-pixel coordinates, detecting a second intersection of a second segment of the glyph with the scan line; storing a second transition entry that includes a second transition sense and second coordinates of a second pixel center adjacent to the second intersection; detecting a dropout condition by comparing the first transition entry and the second transition entry; in response to detecting the dropout condition, calculating first scan-direction coordinates that represent a location of the first intersection in sub-pixel coordinates and calculating second scan-direction coordinates that represent a location of the second intersection in sub-pixel coordinates; and activating a pixel having a pixel center nearest to a midpoint between the first scan-direction coordinates and the second scan-direction coordinates.
Claim 11
Independent Claim
182 words
A method for correcting dropout while scan converting a glyph, comprising: without calculating sub-pixel coordinates, detecting a first intersection of a first segment of the glyph with a scan line of a pixel grid on which the glyph is superimposed; storing a first transition entry that includes a first transition sense and first coordinates of a first pixel center adjacent to the first intersection; without calculating sub-pixel coordinates, detecting a second intersection of a second segment of the glyph with the scan line; storing a second transition entry that includes a second transition sense and second coordinates of a second pixel center adjacent to the second intersection; detecting a dropout condition by comparing the first transition entry and the second transition entry; in response to detecting the dropout condition, calculating first scan-direction coordinates that represent a location of the first intersection in sub-pixel coordinates and calculating second scan-direction coordinates that represent a location of the second intersection in sub-pixel coordinates; and activating a pixel having a pixel center nearest to a midpoint between the first scan-direction coordinates and the second scan-direction coordinates.
Claim 12
Dependent Claim
65 words
The method of claim 9, wherein detecting the dropout condition by comparing the first transition entry to the second transition entry comprises determining that the first transition sense is opposite of the second transition sense and the first coordinates of the first pixel center adjacent to the first intersection are identical to the second coordinates of the second pixel center adjacent to the second intersection.
Claim 13
Dependent Claim
56 words
The method of claim 10, wherein storing the first transition entry comprises storing the first transition entry in a first transition table for storing transition entries having identical transition senses, and wherein storing the second transition entry comprises storing the second transition entry in a second transition table for storing transition entries having identical transition senses.
Claim 14
Dependent Claim
90 words
The method of claim 9, wherein calculating the first scan-direction coordinates comprises: if the first segment is a spline, then using recursive subdivision to calculate the first scan-direction coordinates; and if the first segment is a line, then solving simultaneous equations to calculate the first scan-direction coordinates; and wherein calculating the second scan-direction coordinates comprises: if the second segment is a spline, then using recursive subdivision to calculate the second scan-direction coordinates; and if the second segment is a line, then solving simultaneous equations to calculate the second scan-direction coordinates.
Claim 15
Dependent Claim
13 words
A computer-readable medium having computer-executable instructions for performing the method of claim 9.
Claim 16
Dependent Claim
13 words
A computer-readable medium having computer-executable instructions for performing the method of claim 10.
Claim 17
Dependent Claim
13 words
A computer-readable medium having computer-executable instructions for performing the method of claim 12.
Claim 18
Dependent Claim
11 words
A computer system adapted to perform the method of claim 9.
References Cited (Backward Citations)
US5155805A
Cited
US5200740A
Cited
US5068803A
Cited
US5233336A
Cited
US5255357A
Cited
US5408598A
Cited
US5301267A
Cited
US5857067A
Cited
US5355449A
Cited
US5428728A
Cited
US5422990A
Cited
WO1994006094A1
Cited
US5454070A
Cited
US5623558A
Cited
US5381521A
Cited
WO1994029843A1
Cited
US5579030A
Cited
US5684510A
Cited
US5598520A
Cited
US5790126A
Cited
US5867173A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-07-11 | 2004-01-10 | 2004-07-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-07-11 | 2008-01-10 | 2008-07-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-07-11 | 2012-01-10 | 2012-07-11 | $7700.00 | Window Closed / Lapsed |