US5295235A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Polygon engine for updating computer graphic display employing compressed bit map data
Assignee: Individual
•
Filing: 1992-02-14
•
Granted: 1994-03-15
•
Expires: 2012-02-14
Abstract
Abstract The polygon engine of this invention is a technique for rendering a computer graphic display using a compressed data format. A display list of objects for the next frame is converted into a list of spans for each horizontal line of the display. The polygon engine converts the list of spans for all objects into a set of run-length-encoded bit map lines for the next frame. Conflicts between overlapping objects are resolved based upon a depth value of the corresponding objects. Any remaining unspecified pixels are filled with a predetermined background color. Lastly, the polygon engine updates the frame buffer to correspond to this set of run-length-encoded bit map lines, preferably by comparing run-length-encoded bit map lines for the next frame with those for the current frame and writing only changed pixels into the frame buffer. An alternative embodiment of this invention uses compressed data in the form of trapezoids whose parallel sides are horizontal. A hardware extension of the polygon engine uses a run-length-encoded bit map frame buffer to specify the display.
Inventors
- 👤 Steve Newman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 02:14
CPC Classifications
G; G09; G09G; G09G5/00; G09G5/36; G09G5/39; G09G5/393; G06; G06T; G06T11/00; G06T11/40; G06T15/00; G06T15/50; G06T15/80
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
252 words
A method of rendering a plurality of objects which form a computer graphic display into a frame buffer having a plurality of scan lines comprising the steps of: specifying the objects into a list for the next frame of the display, each object comprising a plurality of pixels, each pixel of the object having an identical color; converting each object of said list of objects into a list of spans, each span corresponding to a horizontal line of the display for the next frame, each span defining a group of horizontally adjacent pixels of a corresponding single object in terms of horizontal offset, pixel count, depth, and color; merging said list of spans for all objects of said list of objects into a single master list of spans, whereby each span for each object for a particular horizontal line appears in said master list of spans for that horizontal line; resolving the depth of said spans in said master list by choosing the color for each span of overlap from the overlapping span having the least depth value; converting said master list of spans into a set of run-length-encoded bit map lines for the next frame, each run-length-encoded bit map line defining all sets of horizontally adjacent pixels having the same color, each set including the number of pixels and the color for that set; and updating the frame buffer by writing each run-length-encoded bit map line into a corresponding scan line of the plurality of scan lines in the frame buffer.
Claim 2
Independent Claim
252 words
A method of rendering a plurality of objects which form a computer graphic display into a frame buffer having a plurality of scan lines comprising the steps of: specifying the objects into a list for the next frame of the display, each object comprising a plurality of pixels, each pixel of the object having an identical color; converting each object of said list of objects into a list of spans, each span corresponding to a horizontal line of the display for the next frame, each span defining a group of horizontally adjacent pixels of a corresponding single object in terms of horizontal offset, pixel count, depth, and color; merging said list of spans for all objects of said list of objects into a single master list of spans, whereby each span for each object for a particular horizontal line appears in said master list of spans for that horizontal line; resolving the depth of said spans in said master list by choosing the color for each span of overlap from the overlapping span having the least depth value; converting said master list of spans into a set of run-length-encoded bit map lines for the next frame, each run-length-encoded bit map line defining all sets of horizontally adjacent pixels having the same color, each set including the number of pixels and the color for that set; and updating the frame buffer by writing each run-length-encoded bit map line into a corresponding scan line of the plurality of scan lines in the frame buffer.
Claim 3
Dependent Claim
42 words
The method of rendering a computer graphic display as claimed in claim 1, further comprising the step of: sorting said list of objects for the next frame in left to right order prior to converting each object into a list of spans.
Claim 4
Dependent Claim
70 words
The method of rendering a computer graphic display as claimed in claim 1, wherein said step of converting said lists of spans for said list of objects into a set of run-length-encoded bit map lines for the next frame further includes: sorting said spans for each horizontal line of said master list of spans in left to right order; and filling any remaining unspecified pixels with a predetermined background color.
Claim 5
Dependent Claim
95 words
The method of rendering a computer graphic display as claimed in claim 1, wherein said step of updating the frame buffer includes: comparing said set of run-length-encoded bit map lines for the next frame with the set of run-length-encoded bit map lines for the current frame to determined each pixel having a color different in the next frame than in the present frame; and writing into corresponding locations in the frame buffer only the color in the next frame of those pixels having a color different in the next frame than in the present frame.
Claim 6
Independent Claim
147 words
A method of rendering a computer graphic display into a frame buffer having a plurality of scan lines comprising the steps of: specifying a list of polygons for the next frame of the display, each polygon having a corresponding color; converting each polygon of said list of polygons into a set of trapezoids whose parallel sides are horizontal; converting said set of trapezoids for all polygons of said list of polygons into a set of nonoverlapping trapezoids; updating the frame buffer to correspond to said set of nonoverlapping trapezoids for the next frame by comparing the set of nonoverlapping trapezoids for the current frame with the set of nonoverlapping trapezoids for the next frame; determining a set of difference trapezoids having a color different in the next frame than in the present frame; and storing a corresponding color only into each pixel represented by said difference trapezoids.
Claim 7
Independent Claim
147 words
A method of rendering a computer graphic display into a frame buffer having a plurality of scan lines comprising the steps of: specifying a list of polygons for the next frame of the display, each polygon having a corresponding color; converting each polygon of said list of polygons into a set of trapezoids whose parallel sides are horizontal; converting said set of trapezoids for all polygons of said list of polygons into a set of nonoverlapping trapezoids; updating the frame buffer to correspond to said set of nonoverlapping trapezoids for the next frame by comparing the set of nonoverlapping trapezoids for the current frame with the set of nonoverlapping trapezoids for the next frame; determining a set of difference trapezoids having a color different in the next frame than in the present frame; and storing a corresponding color only into each pixel represented by said difference trapezoids.
Claim 8
Dependent Claim
61 words
The method of rendering a computer graphic display as claimed in claim 5, wherein said step of converting each polygon of said list of polygons into a set of trapezoids consists of drawing horizontal lines through said polygons such that at least one end point of each horizontal line is a vertex point of the polygon to which it is associated.
Claim 9
Dependent Claim
42 words
The method of rendering a computer graphic display as claimed in claim 5, further comprising the step of: sorting said list of polygons for the next frame in left to right order prior to converting each polygon into a set of trapezoids.
Claim 10
Dependent Claim
58 words
The method of rendering a computer graphic display as claimed in claim 5, wherein: said step of converting said set of trapezoids for all polygons of said list of polygons into a set of nonoverlapping trapezoids includes assigning a depth value to each trapezoid of the set of trapezoids converting from each polygon of said list of polygons.
Claim 11
Dependent Claim
50 words
The method of rendering a computer graphic display as claimed in claim 8, wherein: said step of converting the set of trapezoids for all polygons of said list of polygons into a set of nonoverlapping trapezoids includes comparing depth values for overlapping trapezoids and discarding trapezoids with larger depth values.
Claim 12
Dependent Claim
41 words
The method of rendering a computer graphic display as claimed in claim 5, wherein said step of updating the frame buffer includes: filling any pixels not within said set of nonoverlapping trapezoids for the next frame with a predetermined background color.
Claim 13
Dependent Claim
45 words
The method of rendering a computer graphic display as claimed in claim 5, wherein said step of updating the frame buffer includes: storing a corresponding color into each pixel of each of said nonoverlapping trapezoids for the next frame using special purpose polygon filling hardware.
Claim 14
Dependent Claim
114 words
The method of rendering a computer graphic display as claimed in claim 5, wherein said step of updating the frame buffer includes: rendering each nonhorizontal side of each of said set of nonoverlapping trapezoids in the next frame in expanded pixels at an expanded scale relative to the frame buffer, whereby plural expanded pixels correspond to a single pixel in the frame buffer, and writing into each pixel in the frame buffer corresponding to the nonhorizontal side of each of said set of nonoverlapping trapezoids in the current frame a combination of the color of each of the trapezoids on either side of the nonhorizontal side of each of said set of nonoverlapping trapezoids.
Claim 15
Dependent Claim
69 words
The method of rendering a computer graphic display as claimed in claim 5, each trapezoid comprised of a plurality of individual pixels each having a color, wherein the step of converting said set of trapezoids for all polygons of said list of polygons into a set of nonoverlapping trapezoids is accomplished by choosing the color for each trapezoid of overlap from the overlapping trapezoid having the least depth value.
References Cited (Backward Citations)
US4709231A
Cited
US4792981A
Cited
US4855938A
Cited
US4885703A
Cited
US4847677A
Cited
US5129051A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-03-14 | 1997-09-13 | 1998-03-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-03-14 | 2001-09-13 | 2002-03-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-03-14 | 2005-09-13 | 2006-03-15 | $7700.00 | Window Closed / Lapsed |