Compressed representation of changing meshes and method to decompress

• US 6,184,897 B1
• Filed: 01/14/1998
• Issued: 02/06/2001
• Est. Priority Date: 01/15/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gueziec, Andre, Taubin, Gabriel
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US09/006,771
• Time in Patent Office: 1,119 Days
• Field of Search: 345/440, 345/441, 345/423, 345/418, 345/121
• US Class Current: 345/440
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame

Abstract

A computer implemented representation and a method for encoding and decoding sequences of changes of a manifold triangular mesh. The representation is composed of a base manifold triangular mesh and a succession of specialized mesh surgery operations that may be of a different type. The methods encode or decode any sequence of mark, move, cut, delete, close, fill, or add operations. The mark operation specifies a type of mark and a set of marked elements. The move operation determines a set of displaced vertices from a set of marked elements, and applies a set of vertex displacements to the set of displaced vertices. The cut operation cuts the changing mesh through a set of marked edges. The close operation is applied to one or more boundaries that are determined when the type of mark is a boundary type, and the one or more boundaries are determined by a marked elements variable. The fill operation adds the triangles of a simple polygon to a manifold triangular mesh by establishing a one to one correspondence between a contiguous subset of boundary edges of the manifold triangular mesh and the same number of contiguous edges of a loop defined by the boundary of the simple polygon. The add operation is preferably specified by an incremental manifold triangular mesh and a sequence of stitches, where the incremental manifold triangular mesh is a manifold triangular mesh, and where a stitch is a one to one correspondence between a contiguous subset of boundary edges of one boundary of the manifold triangular mesh and the same number of contiguous edges of boundary edges of one boundary of the incremental manifold triangular mesh.

Claims

1. A method for encoding a representation of a three dimensional scene, comprising the steps of:

generating surface data representing polygonal surfaces, the polygonal surfaces comprising a plurality of elements;

generating first data representing a first operation with respect to elements of said polygonal surfaces;

generating second data representing a second operation with respect to elements of the polygonal surfaces, wherein the second operation is different from the first operation, and wherein the first and second operations are performed in a predetermined sequence with respect to elements of the polygonal surfaces to generate a representation of a three dimensional scene; and

performing the first and second operations in a predetermined sequence on the surface data with respect to elements of said polygonal surfaces to generate a representation of a three dimensional scene.

2. A method as in claim 1, wherein the step of performing includes preliminary steps of:

grouping the surface data, the first data, and the second data to form at least one message; and

communicating the at least one message to a target node where the first and second operations are performed in the predetermined sequence with respect to elements of the polygonal surfaces to generate the representation of the three dimensional scene.

3. A method as in claim 1, wherein the first and second operations are one of a mark operation, a move operation, a cut operation, a delete operation, a close operation, and a fill operation.

4. A method as in claim 3, wherein the mark operation operates in accordance with a mark data structure comprised of a type of mark field and a marked elements field, wherein the type of mark field designates one of a none type, a vertex type, a triangle type, an edge type, a connected component type, or a boundary type.

5. A method as in claim 4, wherein the marked elements field is comprised of one or more mark bits, each mark bit corresponding to one element of a manifold triangular mesh, and a value of each mark bit specifying whether a corresponding element is marked or is not marked.

6. A method as in claim 5, wherein bits of the marked elements field are compressed.

7. A method as in claim 5, wherein bits of the marked elements field are compressed by one run-length encoding or entropy encoding.

8. A method as in claim 4, wherein the move operation operates in accordance with a move data structure comprised of a parameters field and one or more data fields each of which is associated with one marked vertex of a current manifold triangular mesh.

9. A method as in claim 8, wherein data in the data fields is quantized.

10. A method as in claim 8, wherein data in the data fields is quantized and entropy encoded.

11. A method as in claim 8, wherein the move operation is performed in accordance with a method comprised of the steps of:

determining a set of displaced vertices from values of the type of mark field and the set of marked elements field, wherein for the case where the type of marked elements field indicates a vertex type, the set of displaced vertices is comprised of the vertices determined by the set of marked elements, else the set of displaced vertices is comprised of all the vertices belonging to the marked elements;

determining vertex displacements corresponding to the vertices in the set of displaced vertices from data contained in the move data structure; and

applying the determined vertex displacements to the current manifold triangular mesh to produce a new manifold triangular mesh.

12. A method as in claim 11, wherein each vertex displacement is decomposed as a sum of a global vertex displacement and a relative vertex displacement, wherein the global vertex displacement is encoded in the parameters field of the move data structure, and wherein the relative vertex displacement is encoded in the data fields of the move data structure.

13. A method as in claim 12, wherein the global vertex displacement has a same value for all displaced vertices.

14. A method as in claim 12, wherein the global vertex displacement has potentially different values for different displaced vertices, and is represented as a predictor function of one or more global displacement parameters that are encoded in the parameters field of the move data structure.

15. A method as in claim 14, wherein the predictor function is further a function of one or more neighboring vertices of the vertex.

16. A method as in claim 14, wherein the predictor function is represented by one global displacement parameter having a value equal to an average of vectors which go from the vertex to each neighboring vertex, multiplied by the global displacement parameter.

17. A method as in claim 4, wherein the delete operation is performed in accordance with a method comprised of the steps of:

determining, from values of the type of mark field and the marked elements field, a set A comprised of triangles to be deleted from a current manifold triangular mesh;

determining a set B comprised of a boundary of removed region edges;

cutting the current manifold triangular mesh through the set B of edges;

removing from the current manifold triangular mesh the set A of triangles and all vertices of the removed triangles to produce a new manifold triangular mesh; and

re-enumerating the remaining vertices and triangles of the new manifold triangular mesh.

18. A method as in claim 4, wherein the close operation operates in accordance with a close data structure comprised of one or more close boundary records each corresponding to one marked boundary of a current manifold triangular mesh, each of said close boundary records comprising a root boundary index field and a closing tree field that describes a rooted tree that defines a bounding loop, the rooted tree having a root node corresponding to a first bounding loop node.

19. A method as in claim 18, wherein the close operation is performed in accordance with a method comprised of the steps of:

constructing a bounding loop defined by the rooted tree;

establishing a correspondence between boundary vertices and rooted tree nodes;

determining boundary clusters and identifying all vertices in each boundary cluster, wherein each boundary cluster is associated with one rooted tree node;

determining positions of the identified vertices;

removing unused vertices from the current manifold triangular mesh;

replacing references to the removed vertices with references to the identified vertices; and

re-enumerating the vertices and triangles.

20. A method as in claim 4, wherein the fill operation operates in accordance with a fill data structure comprised of one or more fill boundary records each of which corresponds to one marked boundary of a current manifold triangular mesh, wherein each of the fill boundary records is comprised of a root boundary index field and a simple polygon field that describes a simple polygon having a boundary that defines a loop with a simple polygon root vertex, and wherein the associated root boundary index field specifies a first boundary vertex associated with the simple polygon root vertex.

21. A method as in claim 20, wherein the fill operation is performed in accordance with a method comprised of the steps of:

determining correspondences between boundary vertices and vertices of the simple polygon are determined; and

appending triangles of the simple polygon to the current manifold triangular mesh to produce a new manifold triangular mesh.

22. A method as in claim 4, wherein the add operation operates in accordance with an add data structure comprised of an incremental mesh connectivity record, at least one stitch record, and at least one incremental data record.

23. A method as in claim 22, wherein each stitch record is comprised of a stitch data structure comprised of next boundary record, an incremental boundary field that identifies a corresponding boundary of incremental connectivity, an orientation of the incremental boundary field, a length field that indicates a number of edges of each boundary that must be stitched, an optional start field that indicates the start of the stitch in the boundary of the current manifold triangular mesh, and an incremental start field that indicates the start of the stitch in the boundary of the incremental connectivity.

24. A method as in claim 23, wherein the add operation is performed in accordance with a method comprised of the steps of:

determining boundaries of a set of triangles defining an incremental connectivity;

applying all required stitches having corresponding stitch data structures, wherein those boundaries of the current manifold triangular mesh to be stitched are identified using boundary marks;

determining those vertices that are referenced in the incremental connectivity but not stitched to vertices of the current manifold triangular mesh;

determining whether all vertices referenced in the incremental connectivity have been stitched to vertices of the current manifold triangular mesh;

if yes,

appending an incremental geometric connectivity and optional properties to the current manifold triangular mesh to produce a new manifold triangular mesh;

else first reconstructing the incremental geometry and optionally reconstructing the properties of the corresponding incremental manifold triangular mesh.

25. A method as in claim 1, wherein the surface data forms a part of a data structure comprised of a specification of a base triangular mesh and said first and second operations.

26. A computer implemented method for operating on a manifold triangular mesh having a representation comprised of a base manifold triangular mesh, comprising steps of:

marking elements of a current manifold triangular mesh using a data structure that specifies a type of mark and a set of marked elements of the current manifold triangular mesh, the type of mark including a vertex type, a triangle type, an edge type, a connected component type, a boundary type, and a none type;

operating on the marked elements of the current manifold triangular mesh using individual ones of a plurality of sequentially applied mesh surgery operations comprised of mark, move, cut, delete, close, fill, and add mesh surgery operations; and

obtaining a new manifold triangular mesh.

27. A method as in claim 26, wherein the move operation determines a set of displaced vertices from a set of marked vertices, and applies a set of vertex displacements to the set of displaced vertices.

28. A method as in claim 26, wherein the cut operation cuts the current manifold triangular mesh through a set of marked edges.

29. A method as in claim 26, wherein the close operation is applied to marked boundaries.

30. A method as in claim 26, wherein the fill operation adds triangles of a simple polygon to the current manifold triangular mesh by establishing a one to one correspondence between a contiguous subset of boundary edges of the manifold triangular mesh and the same number of contiguous edges of a loop defined by a boundary of the simple polygon.

31. A method as in claim 26, wherein the add operation is specified by an incremental manifold triangular mesh and a sequence of stitches, where the incremental manifold triangular mesh is a manifold triangular mesh, and where a stitch is a one to one correspondence between a contiguous subset of boundary edges of one boundary of the manifold triangular mesh and the same number of contiguous edges of boundary edges of one boundary of the incremental manifold triangular mesh.

32. A data structure for encoding a representation of a three dimensional scene comprising surface data representing polygonal surfaces, comprising:

a base triangular mesh record;

a first operation record for specifying a first operation to be performed on said base triangular mesh record; and

at least one additional operation record for specifying a different operation to be performed after a completion of said first operation for generating a resulting manifold triangular mesh.

33. A data structure as in claim 32, wherein said base triangular mesh record is comprised of a vertex positions array, a triangle array, and one or more optional property arrays.

34. A data structure as in claim 32, wherein said base triangular mesh record is a compressed record comprised of a vertex positions array, a triangle array, and one or more optional property arrays.

35. A data structure as in claim 32, wherein said operation records specify one of a mark operation, a move operation, a cut operation, a delete operation, a close operation, and a fill operation.

36. A data structure as in claim 32, wherein one of said operation records specifies a mark operation that operates in accordance with a mark data structure comprised of a type of mark field and a marked elements field, wherein the type of mark field designates one of a none type, a vertex type, a triangle type, an edge type, a connected component type, or a boundary type.

37. A data structure as in claim 36, wherein the marked elements field is comprised of one or more mark bits, each mark bit corresponding to one element of a manifold triangular mesh, and a value of each mark bit specifying whether a corresponding element is marked or is not marked.

38. A data structure as in claim 37, wherein bits of the marked elements field are compressed.

39. A data structure as in claim 32, wherein one of said operation records specifies a move operation that operates in accordance with a move data structure comprised of a parameters field and one or more data fields each of which is associated with one marked vertex of a current manifold triangular mesh.

40. A data structure as in claim 39, wherein data in the data fields is at least one of quantized and entropy encoded.

41. A data structure as in claim 32, wherein one of said operation records specifies a fill operation that operates in accordance with a fill data structure comprised of one or more fill boundary records each of which corresponds to one marked boundary of a current manifold triangular mesh, wherein each of the fill boundary records is comprised of a root boundary index field and a simple polygon field that describes a simple polygon having a boundary that defines a loop with a simple polygon root vertex, and wherein the associated root boundary index field specifies a first boundary vertex associated with the simple polygon root vertex.