Method of producing a sequence of triangles from a vertex raster with and without half resolution edges while decompressing a compressed geometry stream

• US 6,028,607 A
• Filed: 01/15/1998
• Issued: 02/22/2000
• Est. Priority Date: 01/15/1998
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Chan, Jeffrey M.
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): NGUYEN, THU V
• Application Number:
  US09/007,525
• Time in Patent Office: 768 Days
• Field of Search: 345/418, 345/419, 345/420, 345/423, 345/441, 345/202, 345/203, 345/511
• US Class Current: 345/419
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A method of producing a sequence of triangles from a compressed geometry stream that includes an array of vertices includes steps of parsing vertices and pushing the parsed vertices into a buffer until the last vertex of the current row of the array is parsed and pushed. The first vertex of the current row is then re-used from the buffer and drawn. The first vertex of the next row is then parsed from the geometry stream, pushed into the buffer and drawn. Thereafter, it is determined whether a quad split bit is asserted. If the quad split bit is not asserted, the next vertex from the current row is parsed, pushed into the buffer, and drawn. The next vertex of the previous row is then re-used from the buffer and the re-used next vertex is drawn. If the quad split bit is asserted, the next vertex of the previous row is re-used from the buffer and drawn. The next vertex from the current row is then parsed and pushed into the buffer. Thereafter, the method returns to the determining step until the last vertex of the current row is reached, and returns to the first vertex re-using step until the last vertex of the array is reached. A triangle is formed from each three consecutive drawn vertices, to thereby create the sequence of triangles, starting from the beginning of each row. The raster may include one or more half-resolution edges, wherein alternate vertices are dropped and not drawn.

Claims

1. A method of producing a sequence of triangles from a geometry stream containing an array of vertices, comprising the steps of:

parsing vertices from the geometry stream and pushing the parsed vertices into a mesh buffer until a last vertex of a current row of the array is parsed and pushed;

re-using a first vertex of the current row from the mesh buffer and drawing the re-used first vertex;

parsing a first vertex of a next row from the geometry stream, pushing the first vertex into the mesh buffer and drawing the first vertex;

determining if a quad split bit is asserted;

when the quad split bit is not asserted, parsing a next vertex from a current row of the array, pushing the parsed next vertex into the mesh buffer, drawing the parsed next vertex, and re-using a next vertex of a previous row from the mesh buffer and drawing the re-used next vertex;

when the quad split bit is asserted, re-using the next vertex of the previous row from the mesh buffer and drawing the re-used next vertex, parsing and drawing the next vertex of the current row of the array and pushing the parsed next vertex of the current row into the mesh buffer; and

returning to the determining step until the last vertex of the current row is reached, and returning to the first vertex re-using step until a last vertex of the array of vertices is reached,

whereby, a triangle is formed from each three consecutive drawn vertices, to thereby create the sequence of triangles, starting from the beginning of each row.

2. The method of producing a sequence of triangles according to claim 1, wherein none of the vertices of a first row of the array are drawn until the re-using step.

3. The method of producing a sequence of triangles according to claim 1, further including a step of loading the first vertex of the current row into working registers from the mesh buffer following the first vertex re-use step, to interpolate the first vertex of the next row therefrom.

4. The method of producing a sequence of triangles according to claim 1, wherein each of the vertices includes a plurality of attributes and wherein along a half resolution edge, vertices that are pushed into the mesh buffer and drawn alternate with vertices that are not drawn and for which only placeholders devoid of attributes are pushed into the mesh buffer.

5. The method of producing a sequence of triangles according to claim 1, wherein, to create a half resolution edge along a bottom row of the array, every other vertex along the bottom row is dropped and a placeholder therefor is pushed into the mesh buffer and wherein remaining vertices of a bottom and next adjacent row are processed by omitting a first and every other next vertex re-using and drawing step, and by modifying the next vertex re-using step to re-use only vertices from the previous row that have not been dropped.

6. The method of producing a sequence of triangles according to claim 1, wherein, to create a top half resolution edge, upon reaching a top row of the array, the following steps are carried out until the last vertex of the array of vertices is reached:

re-using a first vertex of the previous row from the mesh buffer,

parsing the first vertex of the top row from the geometry stream, drawing the parsed first vertex and pushing the parsed first vertex into the mesh buffer,

re-using the next vertex of the previous row from the mesh buffer,

parsing the next vertex from the geometry stream and dropping the parsed next vertex,

allocating an entry in the mesh buffer as a placeholder for the dropped next vertex, and not drawing the dropped next vertex,

parsing the next vertex from the geometry stream, drawing the parsed next vertex and pushing the parsed next vertex into the mesh buffer and

re-using the next vertex of the previous row from the mesh buffer.

7. The method of producing a sequence of triangles according to claim 6, wherein each of the vertices includes a plurality of attributes and wherein the first vertex of the previous row re-using step loads the attributes of the re-used vertex into working registers.

8. The method of producing a sequence of triangles according to claim 1, wherein to create a left half resolution edge, upon reaching a last vertex of a first row of the array, the following steps are carried out until the last vertex of the array of vertices is reached:

re-using the first vertex of current row from the mesh buffer and drawing first vertex;

re-pushing the re-used first vertex into the mesh buffer;

parsing first vertex of next row from geometry stream, and dropping the parsed first vertex;

allocating an entry in the mesh buffer as a placeholder for the dropped first vertex;

parsing next vertex of current row from geometry stream, pushing the parsed next vertex into mesh buffer and drawing the parsed next vertex;

re-using the next vertex of the previous row from the mesh buffer and drawing the re-used next vertex;

returning to the determining step until a last vertex of the current row is reached;

re-using first vertex of previous row from the mesh buffer and drawing re-used first vertex;

re-using the first vertex of the current row from the mesh buffer and not drawing the re-used first vertex of the current row

parsing first vertex of next row from geometry stream and pushing parsed first vertex into the mesh buffer and drawing parsed first vertex;

re-using next vertex of previous row from the mesh buffer;

parsing next vertex of current row from geometry stream, pushing next vertex of current row into the mesh buffer and drawing pushed next vertex, and

returning to the determining step until the last vertex of the current row is reached.

9. The method of producing a sequence of triangles according to claim 1, wherein, to create a right half resolution edge, upon reaching a second to last vertex of a second row of the array, the following steps are carried out until the last vertex of the array of vertices is reached:

re-using a last vertex of a previous row, and re-pushing re-used last vertex into the mesh buffer;

parsing last vertex of current row from the geometry stream, and completely dropping the last vertex of current row;

returning to the first vertex of the current row re-using step;

returning to the determining step until the second to last vertex of the current row is reached,

parsing the last vertex of the current row from the geometry stream, pushing parsed last vertex into the mesh buffer,

re-using last vertex of row that is two rows previous to current row, and

returning to the first vertex of the current row re-using step, to the determining step and to the last vertex of previous row re-using step until the last vertex of the array is reached.

10. The method of producing a sequence of triangles according to claim 9, wherein, when a vertex is completely dropped, no vertex and no placeholder mesh buffer pushing step is carried out.

11. The method of producing a sequence of triangles according to claim 1, wherein each re-using step includes a step of selectively reading a plurality of vertex attributes stored in the mesh buffer without re-loading working registers.

12. A method of generating a sequence of triangles from a compressed geometry stream containing an array of vertices, each of the vertices including a plurality of attributes, comprising the steps of:

traversing the array and selectively issuing, for each vertex of the array, one of a draw command and a don'"'"'t draw command, and by carrying out at least one of a vertex drop step, to drop the attributes of selected vertices of the array, a mesh buffer pushing step, to push the attributes of selected vertices of the array into a mesh buffer, a mesh buffer re-use step, to read vertex attributes previously pushed into the mesh buffer, a working registers load step, to load vertex attributes into working registers, and a mesh buffer re-push step, to read vertex attributes previously pushed into the mesh buffer and to re-push the attributes in another location of the mesh buffer; and

during the traversing step, decompressing the geometry stream by utilizing attributes of vertices loaded into the working registers, the loaded working registers storing vertex attributes to allow interpolation of attributes of subsequent vertices in the geometry stream therefrom,

whereby a plurality of triangles is generated to form the sequence, each of the plurality of triangles being defined by three consecutive vertices for which a draw command has been issued, starting from the beginning of each row.

13. A method of generating triangles according to claim 12, wherein the vertex drop step drops attributes of selected vertices located on at least one edge of the array of vertices by pushing only a placeholder devoid of attributes into the mesh buffer, thereby creating at least one edge having dropped vertices, resulting in at least one half resolution edge defining triangles of larger size than triangles located in an interior of the array.

14. A method of generating triangles according to claim 13, wherein the selected vertices are every alternate vertex along the at least one edge of the array of vertices.

15. A method of generating triangles according to claim 12, wherein the working register load steps includes a step of selectively loading vertex attributes from the mesh buffer following a mesh buffer re-use step.

16. A method of generating triangles according to claim 12, wherein the mesh buffer re-push step is carried out when subsequent mesh buffer push operations would overwrite vertex attributes that were previously pushed into the mesh buffer and that will be subsequently needed for later mesh buffer re-use operations,

whereby, a smaller mesh buffer may be used than would be possible without the mesh buffer re-push step.

17. A method of generating triangles according to claim 12, wherein for each vertex of the first row of vertices of the array, a don'"'"'t draw command is issued, and a mesh buffer pushing step is carried out, to store the attributes thereof into the mesh buffer for a subsequent mesh buffer re-use step.