Compression of simple geometric models using spanning trees
First Claim
1. A data structure in a computer memory representing a set of points of a n-dimensional space, the data structure comprising:
- a table of runs describing a rooted tree, the rooted tree having one or more nodes, each node being a regular node, a branching node, or a leaf node, each node of the rooted tree represents a point of the n-dimensional space, the table of runs having one or more records, each record representing a run of the rooted tree, a run having a first node that is a leaf or branching node and a last node that is a leaf or branching node and the run connecting one or more regular nodes between the first node and the last node where the connection between every pair of consecutive nodes in the run is an edge, each record having a length of run field in terms of the number of edges in the run, a leaf field indicating if the run ends at a leaf node, and a last run field indicating if the run represented by the record is the last one with the same first node in the rooted tree, the records given by an order of tree traversal with respect to the root node.
1 Assignment
0 Petitions
Accused Products
Abstract
A computer system stores and transmits compressed simple triangular meshes. The computer uses a data structure that represents a simple 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 simple triangular mesh, transmitting this information between computers, and compressing and decompressing this transmitted information.
75 Citations
38 Claims
-
1. A data structure in a computer memory representing a set of points of a n-dimensional space, the data structure comprising:
a table of runs describing a rooted tree, the rooted tree having one or more nodes, each node being a regular node, a branching node, or a leaf node, each node of the rooted tree represents a point of the n-dimensional space, the table of runs having one or more records, each record representing a run of the rooted tree, a run having a first node that is a leaf or branching node and a last node that is a leaf or branching node and the run connecting one or more regular nodes between the first node and the last node where the connection between every pair of consecutive nodes in the run is an edge, each record having a length of run field in terms of the number of edges in the run, a leaf field indicating if the run ends at a leaf node, and a last run field indicating if the run represented by the record is the last one with the same first node in the rooted tree, the records given by an order of tree traversal with respect to the root node. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
11. A data structure for representing a simple triangular mesh in n-dimensional space, comprising:
-
a table of vertex runs describing a vertex spanning tree, the vertex spanning tree having one or more vertex nodes, each vertex node being a regular vertex node, a branching vertex node, or a leaf vertex node, each vertex node of the vertex spanning tree associated with a vertex of the mesh, the table of vertex runs having one or more vertex run records, each vertex run record representing a vertex run of the vertex spanning tree, the vertex run having a first vertex node that is a leaf or branching vertex node and a last vertex node that is a leaf or branching vertex node and the vertex run connecting one or more regular vertex nodes between the first vertex node and the last vertex node where the connection between every pair of consecutive vertex nodes is a vertex tree edge, each vertex run record having a length of vertex run field given by the number of vertex tree edges in the vertex run, a vertex leaf field indicating if the last vertex node of the vertex run represented by the vertex run record is a leaf vertex node, and a vertex last run field indicating if the vertex run is the last vertex run sharing the same first vertex node, the vertex runs given by an order of traversal of the vertex spanning tree with respect to a vertex root node; a table of triangle runs describing a triangle spanning tree, the triangle spanning tree having one or more triangle nodes, each triangle node being a regular triangle node, a branching triangle node, or a leaf triangle node, each triangle node of the triangle spanning tree associated with a triangle of the mesh, the table of triangle runs having one or more triangle run records, each triangle run record representing a triangle run of the triangle spanning tree, the triangle run having a first triangle node that is a leaf or branching triangle node and a last triangle node that is a leaf or branching triangle node and the run connecting one or more regular triangle nodes between the first triangle node and the last triangle node where the connection between every pair of consecutive triangle nodes is a triangle tree edge, each triangle run record having a length of triangle run field given by the number of triangle tree edges in the triangle run represented by the triangle run record, and a triangle leaf field indicating if the last triangle node of the triangle run represented by the triangle record is a leaf triangle node, the triangle runs given by an order of traversal of the triangle spanning tree with respect to a triangle root node; a marching record having a triangle root field and one or more sequences of marching commands, the triangle root field describing how to construct the triangle associated with a triangle root node of the triangle spanning tree, each sequence of marching commands indicating how to construct triangles from one of the triangle runs by advancing to a next vertex along a left run boundary or a right run boundary of the triangle run, the marching commands given by the order of traversal of the triangle spanning tree with respect to the triangle root node; and an associated data record, the associated data record having one or more associated data fields, each associated data field with information about the position of one of the vertices of the simple triangular mesh, the associated data fields given by an order of traversal of the vertex spanning tree with respect to the vertex root node. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28)
-
-
29. One or more computer systems for compressing and decompressing a geometric model, each computer system comprising:
-
a central processing unit for executing processes; a memory; a table of vertex runs residing on the memory describing a vertex spanning tree, the vertex spanning tree having one or more vertex nodes, each vertex node being a regular vertex node, a branching vertex node, or a leaf vertex node, each vertex node of the vertex spanning tree associated with a vertex of the mesh, the table of vertex runs having one or more vertex run records, each vertex run record representing a vertex run of the vertex spanning tree, the vertex run having a first vertex node that is a leaf or branching vertex node and a last vertex node that is a leaf or branching vertex node and the vertex run connecting one or more regular vertex nodes between the first vertex node and the last vertex node where the connection between every pair of consecutive vertex nodes is a vertex tree edge, each vertex run record having a length of vertex run field given by the number of vertex tree edges in the vertex run, a vertex leaf field indicating if the last vertex node of the vertex run represented by the vertex run record is a leaf vertex node, and a vertex last run field indicating if the vertex run is the last vertex run sharing the same first vertex node, the vertex runs given by an order of traversal of the vertex spanning tree with respect to a vertex root node; a table of triangle runs residing on the memory describing a triangle spanning tree, the triangle spanning tree having one or more triangle nodes, each triangle node being a regular triangle node, a branching triangle node, or a leaf triangle node, each triangle node of the triangle spanning tree associated with a triangle of the mesh, the table of triangle runs having one or more triangle run records, each triangle run record representing a triangle run of the triangle spanning tree, the triangle run having a first triangle node that is a leaf or branching triangle node and a last triangle node that is a leaf or branching triangle node and the run connecting one or more regular triangle nodes between the first triangle node and the last triangle node where the connection between every pair of consecutive triangle nodes is a triangle tree edge, each triangle run record having a length of triangle run field given by the number of triangle tree edges in the triangle run represented by the triangle run record, and a triangle leaf field indicating if the last triangle node of the triangle run represented by the triangle record is a leaf triangle node, the triangle runs given by an order of traversal of the triangle spanning tree with respect to a triangle root node; a marching record residing on the memory having a triangle root field and one or more sequences of marching commands, the triangle root field describing how to construct the triangle associated with a triangle root node of the triangle spanning tree, each sequence of marching commands indicating how to construct triangles from one of the triangle runs by advancing to a next vertex along a left run boundary or a right run boundary of the triangle run, the marching commands given by the order of traversal of the triangle spanning tree with respect to the triangle root node. - View Dependent Claims (30, 31, 32, 33, 34)
-
-
35. A compression process comprising the steps of:
-
building a vertex spanning tree and a triangle spanning tree from a geometric model; describing the vertex spanning tree with a table of vertex runs; describing the triangle spanning tree with a table of triangle runs; 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 according to the table of vertex runs. - View Dependent Claims (36, 37)
-
-
38. A decompression process comprising the steps of:
-
reconstructing vertex positions; constructing a bounding loop; determining relative indices of one or more Y-bounding loop nodes; and reconstructing and linking one or more triangle strips.
-
Specification