Patent US2254727A successfully refreshed from Google Patents.
US6480201B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Alpha regions
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1999-08-24
•
Granted: 2002-11-12
•
Expires: 2019-08-24
Abstract
Abstract An image storage and processing method constructs, clips, fills, and combines arbitrary 2-dimensional shapes in an advanced graphics system. The method supports processing of anti-aliased images by compressing the image into a novel AlphaRegion data structure. AlphaRegion encodes into the data structure both the partially transparent as well as the fully opaque alpha values of an image according to rectangular bands. A band is a contiguous series of scan lines that have the same pattern of alpha values in a single direction. AlphaRegion encoding results in a more compact representation than possible in a conventional bitmap, but without losing the anti-aliasing features. AlphaRegion can be constructed either by supersampling sub-scan lines of an image, from the scan lines of a gray-scale image, from an existing conventional 1-bit Region or alpha mask buffer, or directly from a scan-line conversion of a geometric shape. AlphaRegion stores image data into three arrays, yInfo, xInfo and alphaData. Methods provided with AlphaRegion include rendering methods for filling or clipping the area on the drawing surface and methods for combining two AlphaRegions using boolean combination operators OR, AND, XOR, SUBTRACT, or SUBTRACT_FROM.
Inventors
- 👤 Ikko Fushiki
- 👤 Hock S. Lee
- 👤 J. Andrew Goossen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 19:16
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/005
Claims Analysis
Total Claims: 42
Claim 1
Independent Claim
124 words
A method for encoding an arbitrary 2-dimensional shape represented as a grid of pixels in a graphics system, comprising: scanning one or more semi-transparent spans of pixels in the grid, wherein at least one span has an alpha value pattern recurring elsewhere in the grid; for the scanned semi-transparent spans of pixels in the grid: recording data identifying the semi-transparent span of pixels in the grid; and recording the alpha values of the semi-transparent span of pixels in the grid, wherein the alpha values for one span can be referenced for at least one other span having a recurring pattern of alpha values without re-recording the alpha values of the other span, and alpha values for transparent and opaque pixels are omitted from recording.
Claim 2
Independent Claim
124 words
A method for encoding an arbitrary 2-dimensional shape represented as a grid of pixels in a graphics system, comprising: scanning one or more semi-transparent spans of pixels in the grid, wherein at least one span has an alpha value pattern recurring elsewhere in the grid; for the scanned semi-transparent spans of pixels in the grid: recording data identifying the semi-transparent span of pixels in the grid; and recording the alpha values of the semi-transparent span of pixels in the grid, wherein the alpha values for one span can be referenced for at least one other span having a recurring pattern of alpha values without re-recording the alpha values of the other span, and alpha values for transparent and opaque pixels are omitted from recording.
Claim 3
Dependent Claim
23 words
The method of claim 1 wherein the identifying data comprises a pair of values comprising the location and extent of the semi-transparent span.
Claim 4
Dependent Claim
18 words
The method of claim 2 wherein the extent of the semi-transparent span is recorded as a negative value.
Claim 5
Dependent Claim
18 words
The method of claim 1 further comprising recording data identifying an opaque span of pixels in the grid.
Claim 6
Dependent Claim
23 words
The method of claim 4 wherein the identifying data comprises a pair of values comprising a location and extent of the opaque span.
Claim 7
Dependent Claim
18 words
The method of claim 5 wherein the extent of the opaque span is recorded as a positive value.
Claim 8
Dependent Claim
55 words
The method of claim 3 wherein recording the alpha values of a semi-transparent span of pixels in a grid is limited to recording the data representing a single occurrence of a recurring pattern of alpha values, and the data identifying each location in the grid of pixels where the recurring pattern of alpha values occurs.
Claim 9
Dependent Claim
41 words
The method of claim 7 wherein the data identifying the location of the recurring pattern is stored as an offset to a location in memory where the data representing the single occurrence of the recurring pattern of alpha values was recorded.
Claim 10
Dependent Claim
37 words
The method of claim 8 wherein the data representing the recurring pattern of alpha values is stored as the pair of values comprising the location and extent of the recurring pattern, and the recurring pattern's alpha values.
Claim 11
Dependent Claim
45 words
The method of claim 9 wherein the offset to the location in memory includes an offset to the location of the pair of values comprising the location and extent of the recurring pattern, and an offset to the location of the recurring pattern's alpha values.
Claim 12
Dependent Claim
23 words
The method of claim 4 further comprising recording data representing a total number of semi-transparent and opaque spans in the grid of pixels.
Claim 13
Dependent Claim
13 words
The method of claim 1 wherein the semi-transparent span of pixels is horizontal.
Claim 14
Dependent Claim
13 words
The method of claim 1 wherein the semi-transparent span of pixels is vertical.
Claim 15
Dependent Claim
13 words
The method of claim 4 wherein the opaque span of pixels is horizontal.
Claim 16
Dependent Claim
13 words
The method of claim 4 wherein the opaque span of pixels is vertical.
Claim 17
Independent Claim
181 words
A method for encoding an arbitrary 2-dimensional shape represented as a grid of pixels in a graphics system, comprising: subdividing the shape into a series of rectangular areas, at least one rectangular area having an identical pattern of pixels occurring at least twice in the rectangular area in a first direction of the grid; for the rectangular areas: identifying the starting location and extent of a span of pixels in the rectangular area, wherein the span of pixels is either semi-transparent or opaque; recording the starting location and extent of the semi-transparent and opaque spans recording the alpha values of the semi-transparent spans; and recording the starting location and extent of the rectangular area, wherein the starting location is one corner of the rectangular area, and wherein the extent is a number of lines of pixels in the rectangular area in a second direction of the grid; wherein alpha values for identical patterns of pixels in the rectangular area are not re-recorded for adjacently recurring occurrences of the pattern; and alpha values for opaque spans of pixels are omitted from recording.
Claim 18
Independent Claim
181 words
A method for encoding an arbitrary 2-dimensional shape represented as a grid of pixels in a graphics system, comprising: subdividing the shape into a series of rectangular areas, at least one rectangular area having an identical pattern of pixels occurring at least twice in the rectangular area in a first direction of the grid; for the rectangular areas: identifying the starting location and extent of a span of pixels in the rectangular area, wherein the span of pixels is either semi-transparent or opaque; recording the starting location and extent of the semi-transparent and opaque spans recording the alpha values of the semi-transparent spans; and recording the starting location and extent of the rectangular area, wherein the starting location is one corner of the rectangular area, and wherein the extent is a number of lines of pixels in the rectangular area in a second direction of the grid; wherein alpha values for identical patterns of pixels in the rectangular area are not re-recorded for adjacently recurring occurrences of the pattern; and alpha values for opaque spans of pixels are omitted from recording.
Claim 19
Dependent Claim
47 words
The method of claim 16 wherein recording the alpha values of the semi-transparent spans is limited to recording only a single occurrence of an identical pattern of alpha values, and to recording the location in each rectangular area in which the identical pattern of alpha values occurs.
Claim 20
Dependent Claim
52 words
The method of claim 16 wherein recording the location and extent of the semi-transparent and opaque spans is limited to recording only a single occurrence of an identical pattern of locations and extents, and to recording the location in each rectangular area in which the identical pattern of locations and extents occurs.
Claim 21
Dependent Claim
24 words
The method of claim 16 wherein recording the semi-transparent and opaque spans includes recording the total number of spans occurring in each rectangular area.
Claim 22
Dependent Claim
19 words
The method of claim 16 further comprising recording the total number of rectangular areas subdividing the arbitrary 2-dimensional shape.
Claim 23
Dependent Claim
25 words
The method of claim 16 wherein extents of semi-transparent spans are recorded as negative values, and extents of opaque spans are recorded as positive values.
Claim 24
Dependent Claim
118 words
A computer-readable medium having stored thereon an alpha image data structure representing an image of an arbitrary shape in a graphics system comprising: data representing the starting location and extent of a span of pixels in the image, wherein the span of pixels is semi-transparent; and data representing the alpha values quantifying the opacity of each pixel of the semi-transparent span; wherein the data structure is operable to represent transparent and opaque pixels without storing an alpha value for the transparent or opaque pixels; and alpha values for a recurring pattern of alpha values are omitted from re-recording in the data structure when the recurring pattern of alpha values recurs adjacently to another, identical pattern of alpha values.
Claim 25
Dependent Claim
118 words
A computer-readable medium having stored thereon an alpha image data structure representing an image of an arbitrary shape in a graphics system comprising: data representing the starting location and extent of a span of pixels in the image, wherein the span of pixels is semi-transparent; and data representing the alpha values quantifying the opacity of each pixel of the semi-transparent span; wherein the data structure is operable to represent transparent and opaque pixels without storing an alpha value for the transparent or opaque pixels; and alpha values for a recurring pattern of alpha values are omitted from re-recording in the data structure when the recurring pattern of alpha values recurs adjacently to another, identical pattern of alpha values.
Claim 26
Dependent Claim
24 words
The alpha image data structure of claim 22 further comprising data identifying each location in the image having an identical span of semi-transparent pixels.
Claim 27
Dependent Claim
23 words
The alpha image data structure of claim 22 further comprising data representing the total number of spans of semi-transparent pixels in the image.
Claim 28
Dependent Claim
24 words
The alpha image data structure of claim 22 wherein the data representing the extent of the semi-transparent spans of pixels is a negative value.
Claim 29
Dependent Claim
18 words
The alpha image data structure of claim 22 wherein the alpha values are of a 16-bit data type.
Claim 30
Dependent Claim
18 words
The alpha image data structure of claim 22 wherein the alpha values are of a 32-bit data type.
Claim 31
Dependent Claim
58 words
The alpha image data structure of claim 22 wherein the alpha image data structure further comprises: data representing a starting location of a beginning line of each semi-transparent or opaque span of pixels in the image; and a data element representing the number of adjacent lines in the image having an identical pattern of semi-transparent and opaque pixels.
Claim 32
Independent Claim
162 words
A method for encoding alpha values for an arbitrary 2-dimensional shape represented as a grid of pixels in a graphics system, the method comprising: identifying one or more rectangular areas in the grid comprising one or more adjacent rows or columns having identical patterns of pixels; for rectangular areas in the grid: recording the location of a first row or column and the quantity of rows or columns within the rectangular area; identifying in the first row or column spans of one or more contiguous pixels having no pixels of a first predetermined alpha value or a second predetermined alpha value; for the row or column spans: recording the alpha values of the span; and recording data identifying the span; wherein alpha values for pixels having the first predetermined alpha value or the second predetermined alpha value are not recorded for the rectangular areas and alpha values for adjacent rows or columns having identical patterns are not re-recorded for the rectangular areas.
Claim 33
Independent Claim
162 words
A method for encoding alpha values for an arbitrary 2-dimensional shape represented as a grid of pixels in a graphics system, the method comprising: identifying one or more rectangular areas in the grid comprising one or more adjacent rows or columns having identical patterns of pixels; for rectangular areas in the grid: recording the location of a first row or column and the quantity of rows or columns within the rectangular area; identifying in the first row or column spans of one or more contiguous pixels having no pixels of a first predetermined alpha value or a second predetermined alpha value; for the row or column spans: recording the alpha values of the span; and recording data identifying the span; wherein alpha values for pixels having the first predetermined alpha value or the second predetermined alpha value are not recorded for the rectangular areas and alpha values for adjacent rows or columns having identical patterns are not re-recorded for the rectangular areas.
Claim 34
Dependent Claim
36 words
The method of claim 29 wherein the data identifying the span comprises the location within the first row or column and extent of the span, and a reference to the location of the recorded alpha values.
Claim 35
Dependent Claim
42 words
The method of claim 29 further comprising: for each rectangular area in the grid, identifying in the first row or column opaque spans of one or more contiguous pixels having no semi-transparent or transparent pixels and recording data identifying each opaque span.
Claim 36
Dependent Claim
27 words
The method of claim 31 wherein the data identifying an opaque span comprises the location within the first row or column and extent of the opaque span.
Claim 37
Dependent Claim
20 words
The method of claim 32 wherein extents of opaque spans and extents of semi-transparent spans are recorded with different signs.
Claim 38
Dependent Claim
23 words
The method of claim 29 wherein a reference to the locations of the recorded data identifying spans is recorded for the rectangular areas.
Claim 39
Dependent Claim
25 words
The method of claim 29 wherein the first predetermined alpha value indicates a transparent pixel and the second predetermined alpha value indicates an opaque pixel.
Claim 40
Dependent Claim
125 words
A computer-implemented method of encoding alpha values of a set of pixels defining a shape, the method comprising: storing alpha values for a set of pixel rectangles forming the shape, wherein at least one of the pixel rectangles comprises an adjacently-recurring pattern of alpha values; and for pixel rectangles having the adjacently-recurring pattern of alpha values, storing the alpha values of the adjacently-recurring pattern once for the pixel rectangle and storing information indicating that the pattern adjacently recurs within the pixel rectangle; wherein the stored alpha values omit pixels of a first pre-determined alpha value and indicate the extent of a span of pixels of a second pre-determined alpha value without storing an alpha value for the span of pixels of the second pre-determined value.
Claim 41
Dependent Claim
125 words
A computer-implemented method of encoding alpha values of a set of pixels defining a shape, the method comprising: storing alpha values for a set of pixel rectangles forming the shape, wherein at least one of the pixel rectangles comprises an adjacently-recurring pattern of alpha values; and for pixel rectangles having the adjacently-recurring pattern of alpha values, storing the alpha values of the adjacently-recurring pattern once for the pixel rectangle and storing information indicating that the pattern adjacently recurs within the pixel rectangle; wherein the stored alpha values omit pixels of a first pre-determined alpha value and indicate the extent of a span of pixels of a second pre-determined alpha value without storing an alpha value for the span of pixels of the second pre-determined value.
Claim 42
Dependent Claim
25 words
The method of claim 36 wherein the first pre-determined alpha value indicates a transparent pixel and the second pre-determined alpha value indicates an opaque pixel.
References Cited (Backward Citations)
US5216755A
Cited
US5289566A
Cited
US4602286A
Cited
US4524421A
Cited
US5459529A
Cited
US5682469A
Cited
US5999189A
Cited
US5883678A
Cited
US5745095A
Cited
US5748789A
Cited
US5983190A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-11-11 | 2006-05-13 | 2006-11-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-11-11 | 2010-05-13 | 2010-11-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-11-11 | 2014-05-13 | 2014-11-12 | $7700.00 | Window Closed / Lapsed |