Efficient triangular shaped meshes

• US 7,209,137 B2
• Filed: 09/12/2002
• Issued: 04/24/2007
• Est. Priority Date: 09/12/2002
• Status: Expired due to Term

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Brokenshire, Daniel Alan, Johns, Charles Ray, Minor, Barry L., Nutter, Mark Richard
• Primary Examiner(s): Tung, Kee M.
• Assistant Examiner(s): Nguyen, Hau
• Application Number:
  US10/242,523
• Publication Number:
  US 20040051715A1
• Time in Patent Office: 1,685 Days
• Field of Search: 345/419, 345/420, 345/423, 345/553, 345/557
• US Class Current: 345/423
• CPC Class Codes: G06T 15/00 3D [Three Dimensional] image rendering
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

The present invention renders a triangular mesh for employment in graphical displays. The triangular mesh comprises triangle-shaped graphics primitives. The triangle-shaped graphics primitives represent a subdivided triangular shape. Each triangle-shaped graphics primitive shares defined vertices with adjoining triangle-shaped graphics primitives. These shared vertices are transmitted and employed for the rendering of the triangle-shaped graphics primitives.

Claims

1. A method for employing video information associated with a triangular mesh, comprising:

(a) deriving a plurality of adjacent triangle primitives of a first row of triangle primitives and at least a next row of triangle primitives, wherein each triangle primitive comprises at least one lower vertex and at least one upper vertex;

(b) defining unique mesh vertices that are required to construct the triangular mesh, wherein each unique mesh vertex represents a vertex of one or more triangle primitives;

(c) for the first row of triangle primitives, caching lower unique mesh vertices and upper unique mesh vertices, wherein each unique mesh vertex is only represented once;

(d) overwriting lower unique mesh vertices of the next row of triangle primitives with the upper unique mesh vertices of the first row of triangle primitives;

(e) caching upper unique mesh vertices of the next row of triangle primitives; and

(f) repeating steps (d)–

(e) as necessary, thereby generating a triangular mesh.

2. The method of claim 1, further comprising the step of rendering the triangular mesh.

3. The method of claim 1, wherein the step of deriving further comprises the step of subdividing a triangular shape into triangle primitives.

4. The method of claim 3, wherein the step of subdividing comprises creating a substantially equalized bisection.

5. The method of claim 4, wherein the subdividing comprises creating a substantially equalized n-section.

6. A method for transmitting display information, comprising:

subdividing a triangular shape of display information into triangle primitives, wherein each triangle primitive has at least one lower vertex and at least one upper vertex;

defining unique mesh vertices that represent the triangle primitives, wherein each unique mesh vertex is a vertex of at least one triangle primitive;

transmitting unique mesh vertices, wherein each unique mesh vertex is only transmitted once, wherein the step of transmitting further comprises;

(a) transmitting and caching lower unique mesh vertices and upper unique mesh vertices of a first row of triangle primitives;

(b) overwriting lower unique mesh vertices of a next row of triangle primitives with the upper unique mesh vertices of the first row of triangle primitives;

(c) transmitting and caching upper unique mesh vertices of the next row of triangle primitives;

(d) repeating steps (b)–

(c) as necessary; and

rendering a triangular mesh from the plurality of triangle primitives.

7. The method of claim 6, wherein the subdividing comprises recursively performing substantially equalized bisections.

8. The method of claim 6, wherein the subdividing comprises creating a substantially equalized n-section.

9. The method of claim 6, wherein the step of subdividing further decomposes a subdivision into further subdivisions, but not exceeding the maximum receptive capacity of a vertex cache.

10. A computer program product for employing video information associated with a triangular mesh, the computer program product having a medium with a computer program embodied thereon, the computer program comprising:

(a) computer code for deriving a plurality of adjacent triangle primitives of a first row of triangle primitives and at least a next row of triangle primitives, wherein each triangle primitive comprises at least one lower vertex and at least one upper vertex;

(b) computer code for defining unique mesh vertices that are required to construct the triangular mesh, wherein each unique mesh vertex represents a vertex of one or more triangle primitives;

(c) computer code for caching lower unique mesh vertices and upper unique mesh vertices of the first row of triangle primitives, wherein each unique mesh vertex is only represented once;

(d) computer code for overwriting lower unique mesh vertices of the next row of triangle primitives with the upper unique mesh vertices of the first row of triangle primitives;

(e) computer code for caching upper unique mesh vertices of triangle primitives; and

(f) repeating steps (d)–

(e) as necessary, thereby generating a triangular mesh.

11. A method for employing video information associated with a triangular mesh, comprising:

deriving a plurality of contiguous triangle primitives from the video information, wherein each triangle primitive comprises two lower and one upper vertices or two upper and one lower vertices;

for each contiguous triangle primitive in a first row (r=1) of triangle primitives, wherein the first row is an outer row of the triangular mesh, caching both the upper and lower vertices;

for each contiguous triangle primitive in a second row or y row, where y=r+1, of triangle primitives adjacent to the first row or r row, caching only the vertices that do not overlap the vertices in the first row or r row and overwriting the overlapping vertices of the second row or y row with the overlapping vertices of the first row or r row, such that each vertex in the second row or y row is cached only once;

add 1 to r; and

for each y row, repeating the above two steps until no more rows exists, thereby creating the triangular mesh.