US6175372B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for estimating the memory required for scan conversation of a glyph
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-06-27
•
Granted: 2001-01-16
•
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:19
CPC Classifications
G; G06; G06T; G06T11/00; G06T11/20; G06T11/23; G06T9/00
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
191 words
A method for calculating an estimate of the maximum amount of memory required to support scan conversion of a glyph comprising a plurality of reversals, each of said reversals having a reversal sense of either a positive reversal sense or a negative reversal sense, said glyph superimposed on a pixel grid comprising a plurality of scan lines having identifying scan line numbers, said method comprising the steps of: detecting the location on said plurality of scan lines for each of said reversals of said glyph, each location defined by a corresponding one of said scan line numbers; determining whether each of said detected reversals has a positive reversal sense defined by a local minimum or a negative reversal sense defined by a local maximum; calculating a first sum by summing said scan line numbers associated with said detected reversals having a negative sense; calculating a second sum by summing said scan line numbers associated with said detected reversals having a positive sense; and calculating a difference term by subtracting said second sum from said first sum, said difference term being proportional to said estimate of the maximum amount of said memory.
Claim 2
Independent Claim
191 words
A method for calculating an estimate of the maximum amount of memory required to support scan conversion of a glyph comprising a plurality of reversals, each of said reversals having a reversal sense of either a positive reversal sense or a negative reversal sense, said glyph superimposed on a pixel grid comprising a plurality of scan lines having identifying scan line numbers, said method comprising the steps of: detecting the location on said plurality of scan lines for each of said reversals of said glyph, each location defined by a corresponding one of said scan line numbers; determining whether each of said detected reversals has a positive reversal sense defined by a local minimum or a negative reversal sense defined by a local maximum; calculating a first sum by summing said scan line numbers associated with said detected reversals having a negative sense; calculating a second sum by summing said scan line numbers associated with said detected reversals having a positive sense; and calculating a difference term by subtracting said second sum from said first sum, said difference term being proportional to said estimate of the maximum amount of said memory.
Claim 3
Dependent Claim
32 words
The method recited in claim 1 further comprising the step of storing said scan line number and said reversal sense for each of said detected reversals prior to calculating said first sum.
Claim 4
Dependent Claim
25 words
The method recited in claim 2 further comprising the step of sorting said detected reversals based upon an ascending order of said scan line numbers.
Claim 5
Dependent Claim
22 words
The method recited in claim 1 , wherein said detecting step comprises traversing said glyph to locate local maximum and local minimum.
Claim 6
Independent Claim
243 words
A method for calculating an estimate of the maximum amount of memory required to support scan conversion of a glyph comprising a plurality of reversals, each of said reversals having a reversal sense of either a positive reversal sense or a negative reversal sense, said glyph superimposed on a pixel grid comprising a plurality of scan lines, said method comprising the steps of: detecting each of said reversals for said glyph; determining whether each of said detected reversals has a positive reversal sense defined by a local maxima or a negative reversal sense defined by a local minima; calculating an index by incrementing a count for each of said detected reversals having said positive reversal sense and located adjacent to said scan lines, and decrementing said count for each of said detected reversals having said negative reversal sense and located adjacent each to said scan lines, whereby each of said scan lines located adjacent to one of said reversals is assigned a particular value of said index; counting the number of consecutive scan lines associated with each of said particular value of said index to produce a scan line range corresponding to each of said particular value of said index; calculating a memory range for each of said scan line ranges by multiplying said scan line range by said corresponding particular value of said index; and calculating said estimate of the maximum amount of said memory by summing each of said memory ranges.
Claim 7
Independent Claim
243 words
A method for calculating an estimate of the maximum amount of memory required to support scan conversion of a glyph comprising a plurality of reversals, each of said reversals having a reversal sense of either a positive reversal sense or a negative reversal sense, said glyph superimposed on a pixel grid comprising a plurality of scan lines, said method comprising the steps of: detecting each of said reversals for said glyph; determining whether each of said detected reversals has a positive reversal sense defined by a local maxima or a negative reversal sense defined by a local minima; calculating an index by incrementing a count for each of said detected reversals having said positive reversal sense and located adjacent to said scan lines, and decrementing said count for each of said detected reversals having said negative reversal sense and located adjacent each to said scan lines, whereby each of said scan lines located adjacent to one of said reversals is assigned a particular value of said index; counting the number of consecutive scan lines associated with each of said particular value of said index to produce a scan line range corresponding to each of said particular value of said index; calculating a memory range for each of said scan line ranges by multiplying said scan line range by said corresponding particular value of said index; and calculating said estimate of the maximum amount of said memory by summing each of said memory ranges.
Claim 8
Dependent Claim
44 words
The method recited in claim 5 further comprising the step of storing said reversal sense for each of said detected reversals and an identifying number for each of said scan lines located adjacent to one of said detected reversals prior to calculating said index.
Claim 9
Dependent Claim
37 words
The method recited in claim 6 further comprising the step of sorting said stored reversal sense for each of said detected reversals based upon an ascending order of said identifying number for each of said scan lines.
Claim 10
Dependent Claim
26 words
The method recited in claim 5 , wherein said detecting step comprises traversing said glyph to locate each of said local maxima and said local minima.
Claim 11
Dependent Claim
73 words
The method recited in claim 1 , further comprising the steps of: determining whether a dropout control feature has been selected; if so, then determining a number of bytes of memory required to support scan conversion by multiplying the difference term by four; and if the dropout control feature has not been selected, then determining a number of bytes of memory required to support scan conversion by multiplying the difference term by two.
Claim 12
Dependent Claim
71 words
The method recited in claim 1 , further comprising the steps of: determining whether a dropout control feature has been selected; if so, then determining a number of bytes of memory required to support scan conversion by multiplying the estimate by four; and if the dropout control feature has not been selected, then determining a number of bytes of memory required to support scan conversion by multiplying the estimate by two.
Claim 13
Dependent Claim
141 words
A computer-readable medium on which is stored a computer program for calculating the workspace memory required to support scan conversion of a glyph comprising a plurality of reversals, each of the reversals having either a positive reversal sense or a negative reversal sense, the glyph superimposed on a pixel grid comprising a plurality of scan lines having identifying scan line numbers, the computer program comprising instructions which, when executed by the computer, perform the steps of: calculating a first sum by summing the scan line numbers associated with the reversals having a negative sense; calculating a second sum by summing the scan line numbers associated with the reversals having a positive sense; and calculating a difference term by subtracting the second sum from the first term, the difference term being proportional to the estimate of the maximum amount of the memory.
Claim 14
Dependent Claim
141 words
A computer-readable medium on which is stored a computer program for calculating the workspace memory required to support scan conversion of a glyph comprising a plurality of reversals, each of the reversals having either a positive reversal sense or a negative reversal sense, the glyph superimposed on a pixel grid comprising a plurality of scan lines having identifying scan line numbers, the computer program comprising instructions which, when executed by the computer, perform the steps of: calculating a first sum by summing the scan line numbers associated with the reversals having a negative sense; calculating a second sum by summing the scan line numbers associated with the reversals having a positive sense; and calculating a difference term by subtracting the second sum from the first term, the difference term being proportional to the estimate of the maximum amount of the memory.
Claim 15
Dependent Claim
32 words
The computer-readable medium recited in claim 11 , wherein the computer program comprises further instructions that, when executed, perform a step of detecting the reversals and the reversal senses of the glyph.
Claim 16
Dependent Claim
26 words
The computer-readable medium recited in claim 12 , wherein the step of detecting the reversals and the reversal senses of the glyph comprises traversing the glyph.
Claim 17
Dependent Claim
39 words
The computer-readable medium recited in claim 12 , wherein the computer program comprises further instructions that, when executed, perform a step of storing the scan line numbers associated with the reversals and the reversal senses in a data structure.
Claim 18
Dependent Claim
37 words
The computer-readable medium recited in claim 14 , wherein the data structure is an array, and the computer program comprises further instructions that, when executed, perform a step of sorting the array by ascending scan line number.
Claim 19
Dependent Claim
151 words
A computer-readable medium on which is stored a computer program for calculating the workspace memory required to support scan conversion of a glyph, the glyph comprising a plurality of reversals, each of said reversals having either a negative reversal sense or a positive reversal sense, the glyph superimposed on a pixel grid comprising a plurality of scan lines, each scan line having a scan line number, the computer program comprising instructions which, when executed, perform the steps of: calculating a plurality of scan line ranges for the glyph by determining the reversal sense and reversal location of each reversal, calculating an index for each scan line using the reversal sense and reversal location of each scan line, and determining the number of consecutive scan lines associated with each particular index; calculating a memory range for each of the scan line ranges; and calculating the workspace memory by summing the memory ranges.
Claim 20
Dependent Claim
151 words
A computer-readable medium on which is stored a computer program for calculating the workspace memory required to support scan conversion of a glyph, the glyph comprising a plurality of reversals, each of said reversals having either a negative reversal sense or a positive reversal sense, the glyph superimposed on a pixel grid comprising a plurality of scan lines, each scan line having a scan line number, the computer program comprising instructions which, when executed, perform the steps of: calculating a plurality of scan line ranges for the glyph by determining the reversal sense and reversal location of each reversal, calculating an index for each scan line using the reversal sense and reversal location of each scan line, and determining the number of consecutive scan lines associated with each particular index; calculating a memory range for each of the scan line ranges; and calculating the workspace memory by summing the memory ranges.
References Cited (Backward Citations)
US4878183A
Cited
US5155805A
Cited
US5200740A
Cited
US5068803A
Cited
US5255357A
Cited
US5408598A
Cited
US5301267A
Cited
US5428728A
Cited
US5422990A
Cited
WO1994006094A1
Cited
US5454070A
Cited
US5381521A
Cited
WO1994029843A1
Cited
US5579030A
Cited
US5933157A
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) | 2004-01-16 | 2004-07-17 | 2005-01-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-01-16 | 2008-07-17 | 2009-01-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-01-16 | 2012-07-17 | 2013-01-16 | $7700.00 | Window Closed / Lapsed |