Compression of geometric models using spanning trees
First Claim
1. A data structure stored in a memory of a computer system for representing the connectivity of a connected n-dimensional triangular mesh, the data structure comprising:
- a table of vertex runs with one or more vertex run records that describe a vertex spanning tree connecting two or more vertices on the triangulated mesh, each vertex run record having a vertex last field, a length of vertex run field, and a vertex leaf field;
a table of triangle runs having one or more triangle run records, each triangle run record having a triangle leaf field indicating if a triangle is a leaf of a triangle run of a triangle tree, a length of triangle run field indicating a length of the the triangle run, and one or more jump information fields each having information about a jump edge in the triangle run, the triangle run being a triangulated polygon cut from the triangular mesh by cutting the triangular mesh along the vertex spanning tree; and
a marching record having one or more triangle root fields with a triangle root and a sequence of marching commands describing how to construct the triangles in the triangulated polygon with the triangle root as a root.
1 Assignment
0 Petitions
Accused Products
Abstract
A computer system stores and transmits compressed triangular meshes. The computer uses a data structure that represents a triangular mesh in n-dimensional space. The data structure has a table of vertex runs, a table of triangle runs, zero or more marching records, which provide the connectivity information of the triangular mesh. The data structure also has zero or more associated data records that include the geometric information of the triangular mesh. The table of triangle runs and the marching record have information that describes how to construct a triangular mesh (therefore, the polygon vertices and the boundary edges). The table of vertex runs describes a vertex spanning tree that provides additional connectivity information to construct the triangular mesh from the polygon. The associated data record determines the exact position of the triangular mesh in space. The system also includes ways for creating this data structure from a triangular mesh, transmitting this information between computers, and compressing and decompressing this transmitted information.
-
Citations
32 Claims
-
1. A data structure stored in a memory of a computer system for representing the connectivity of a connected n-dimensional triangular mesh, the data structure comprising:
-
a table of vertex runs with one or more vertex run records that describe a vertex spanning tree connecting two or more vertices on the triangulated mesh, each vertex run record having a vertex last field, a length of vertex run field, and a vertex leaf field; a table of triangle runs having one or more triangle run records, each triangle run record having a triangle leaf field indicating if a triangle is a leaf of a triangle run of a triangle tree, a length of triangle run field indicating a length of the the triangle run, and one or more jump information fields each having information about a jump edge in the triangle run, the triangle run being a triangulated polygon cut from the triangular mesh by cutting the triangular mesh along the vertex spanning tree; and a marching record having one or more triangle root fields with a triangle root and a sequence of marching commands describing how to construct the triangles in the triangulated polygon with the triangle root as a root.
-
-
2. A data structure stored in one or more memories of a computer representing the connectivity of a connected n-dimensional triangular mesh with a plurality of triangles each with three vertices and three edges, each of the edges connecting two of the vertices, the data structure comprising:
-
a vertex record describing a rooted vertex spanning tree being a set of one or more of the edges called cut edges, each of the vertices connected to one or more of the cut edges; a jump edge record that describes a set of one or more of the edges being jump edges, the jump edges not being in the set of cut edges; and a polygon record describing one or more triangulated polygons, each triangulated polygon having one or more polygon triangles, each of the polygon triangles corresponding to a respective triangle in the connected n dimensional triangular mesh, the triangulated polygons resulting by cutting the connected n dimensional triangular mesh through all of the cut and jump edges. - View Dependent Claims (3, 4)
-
-
5. A computer having one or more memories and one or more central processing units (CPUs), the computer further comprising:
-
a data structure stored in one or more memories of a computer representing the connectivity of a connected n-dimensional triangular mesh with a plurality of triangles each with three vertices and three edges, each of the edges connecting two of the vertices, the data structure comprising; a vertex record describing a rooted vertex spanning tree being a set of one or more of the edges called cut edges, all of the vertices being connected by the cut edges; a jump edge record that describes a set of one or more of the edges being jump edges, the jump edges not being in the set of cut edges; and a polygon record describing one or more triangulated polygons, each triangulated polygon having one or more polygon triangles, each of the polygon triangles corresponding to a respective triangle in the connected n dimensional triangular mesh, the triangulated polygon resulting by cutting the connected n dimensional triangular mesh through all of the cut and jump edges. - View Dependent Claims (6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A computer having one or more memories and one or more central processing units (CPUs), the computer further comprising:
a data structure stored in one or more of the memories for representing the connectivity of a connected n-dimensional triangular mesh with a plurality of triangles each with three vertices and three edges, each of the edges connecting two of the vertices, the data structure comprising; a table of vertex runs with one or more vertex run records that describe a vertex spanning tree connecting two or more of the vertices on the triangular mesh, each vertex run record having a vertex last field, a length of vertex run field, a vertex leaf field, and a vertex order of traversal; a table of triangle runs with one or more triangle run records that describe one or more triangle trees, each triangle tree connecting one or more triangles of the triangle mesh and comprises one or more triangle runs, each triangle run record corresponding to one triangle run, each triangle run record having a triangle leaf field indicating if a triangle is a leaf of a triangle run of a triangle tree, a length of triangle run field indicating a length of the triangle run, and one or more jump information fields each having information about a jump edge in the triangle run, each triangle tree corresponding to a triangulated polygon resulting from cutting the triangular mesh along the vertex spanning tree, the table of triangle runs having a triangle order of traversal; a marching record having one or more triangle root fields with a triangle root and a sequence of marching commands describing how to construct the triangles in the triangulated polygon with the triangle root as a root; and an associated data record that defines a position of each of the vertices. - View Dependent Claims (15, 16, 17, 18, 19, 20)
-
21. A computer system, having two or more computers, each computer having one or more memories, one or more central processing units (CPUs), and one or more communication interfaces connected to and communicating over one or more networks, the system comprising:
a data structure stored in one or more of the memories of one or more of the computers, the data structure representing a connected n-dimensional triangular mesh, the data structure further comprising; a table of vertex runs with one or more vertex run records that describe a vertex spanning tree connecting two or more vertices on the triangular mesh, each vertex run record having a vertex last field, a length of vertex run field, and a vertex leaf field; a table of triangle runs with one or more triangle run records that describe one or more triangle trees, each triangle tree connecting one or more triangles of the triangle mesh and comprises one or more triangle runs, each triangle run record corresponding to one triangle run, each triangle run record having a triangle leaf field indicating if a triangle is a leaf of a triangle run of a triangle tree, a length of triangle run field indicating a length of the triangle run, and one or more jump information fields each having information about a jump edge in the triangle run, each triangle tree corresponding to a triangulated polygon resulting from cutting the triangular mesh along the vertex spanning tree, the table of triangle runs having a triangle order of traversal; a marching record having one or more triangle root fields with a triangle root and a sequence of marching commands describing how to construct the triangles in the triangulated polygon with the triangle root as a root; and an associated data record that defines a position of each the vertices. - View Dependent Claims (22, 23, 24, 25, 26)
-
27. A process, executed by a computer for creating a representation of a connected three dimensional triangular mesh having a plurality of mesh triangles, comprising the steps of:
-
building a vertex spanning tree and a triangle spanning forest composed of one or more triangle trees, each triangle tree with one or more triangles corresponding to respective mesh triangles in the triangular mesh, the triangles having edges; determining that one or more of the edges are jump edges; building a vertex spanning tree table with one or more vertex runs for traversing the vertex spanning tree; building a triangle spanning tree table with one or more triangle runs for traversing a respective triangle spanning tree; and establishing a marching record that defines how to construct one or more of the triangles in the triangle spanning tree while traversing the triangle spanning tree in a triangle order of traversal. - View Dependent Claims (28, 29)
-
-
30. A decompression process comprising the steps of:
-
receiving a data structure with a table of vertex runs, an associated data record, a table of triangle runs, and a marching record; reconstructing one or more vertex positions; constructing a vertex position array by traversing the table of vertex runs in a vertex order of traversal, the vertex position array having the vertex positions; constructing a bounding loop by traversing the table of vertex runs; determining one or more relative indices of one or more Y-bounding loop nodes; and reconstructing and linking one or more triangle strips.
-
-
31. A computer system for creating a representation of a connected three dimensional triangular mesh having a plurality of mesh triangles, comprising:
-
means for building a vertex spanning tree and a triangle spanning forest composed of one or more triangle trees, each triangle tree with one or more triangles corresponding to respective mesh triangles in the triangular mesh, the triangles having edges; means for determining that one or more of the edges are jump edges; means for building a vertex spanning tree table with one or more vertex runs for traversing the vertex spanning tree; means for building a triangle spanning tree table with one or more triangle runs for traversing a respective triangle spanning tree; and means for establishing a marching record that defines how to construct one or more of the triangles in the triangle spanning tree while traversing the triangle spanning tree in a triangle order of traversal.
-
-
32. A computer system performing decompression process comprising:
-
means for receiving a data structure with a table of vertex runs, an associated data record, a table of triangle runs, and a marching record; means for reconstructing one or more vertex positions; means for constructing a vertex position array by traversing the table of vertex runs in a vertex order of traversal, the vertex position array having the vertex positions; means for constructing a bounding loop by traversing the table of vertex runs; means for determining one or more relative indices of one or more Y-bounding loop nodes; and means for reconstructing and linking one or more triangle strips.
-
Specification