Polygon engine for updating computer graphic display employing compressed bit map data
First Claim
1. 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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
13 Claims
-
1. 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. - View Dependent Claims (2, 3, 4)
-
-
5. 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. - View Dependent Claims (6, 7, 8, 9, 10, 11, 12, 13)
-
Specification