Geometry compression for regular and irregular mesh structures

• US 6,525,722 B1
• Filed: 06/14/1999
• Issued: 02/25/2003
• Est. Priority Date: 08/04/1995
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Deering, Michael F.
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US09/332,322
• Time in Patent Office: 1,352 Days
• Field of Search: 345/419, 345/420, 345/423, 345/427, 345/428, 382/232, 382/233, 382/241, 382/242, 382/243, 382/248, 382/251
• US Class Current: 345/419
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame

Abstract

A method for compressing 3D geometry data that is capable of compressing both regularly tiled and irregularly tiled surfaces is disclosed. In one embodiment, the method comprises examining 3D geometry data to detect the presence of regularly tiled surface portions. The 3D geometry data is then compressed by: (1) encoding any regularly tiled surface portion using a first encoding method, and (2) encoding any irregularly tiled surface portions using a second encoding method, wherein the second encoding method is different from the first encoding method. The first encoding method may encode the regularly tiled surface portions as vertex rasters, while the second method may encode the irregularly tiled surface portions by geometry compression using a generalized triangle mesh.

Claims

1. A computer-implemented method for compressing 3D geometric data representing one or more 3D objects, comprising:

examining the 3D geometric data to detect the presence of regularly tiled surface

portions, and compressing the 3D geometric data by;

encoding one or more regularly tiled surface portions using a first encoding method, and

encoding one or more irregularly tiled surface portions using a second encoding method, wherein the second encoding method is different from the first encoding method.

2. The method as recited in claim 1, wherein the first encoding method encodes the regularly tiled surface portions as vertex rasters.

3. The method as recited in claim 2, further comprising encoding an extent value for each regularly tiled surface portion, wherein the extent values each define an arrangement of the vertices to be compressed.

4. The method as recited in claim 3, wherein the first encoding method further comprises:

specifying the initial values for selected interpolatable parameters within the regularly tiled surface'"'"'s geometric data, and

specifying delta values indicative of how the selected parameters vary across the regularly tiled surface.

5. The method as recited in claim 3, wherein the first encoding method further comprises specifying per-vertex information for vertices which deviate from the specified delta values.

6. The method as recited in claim 5, wherein the first encoding method further comprises specifying per-vertex information for vertexes that do not deviate from the specified delta values but have additional information not represented by the delta values.

7. The method as recited in claim 6, wherein the per-vertex information is compressed by reducing the number of bits used to represent the constituent vertex parameter values.

8. The method as recited in claim 7, wherein the vertex parameter values are selected from the group consisting of position, normal, color, texture, material, and lighting information.

9. The method as recited in claim 2, wherein the second encoding method encodes the irregularly tiled surfaces as a generalized triangle mesh.

10. The method as recited in claim 2, wherein the examining comprises detecting pluralities of vertexes above a predetermined size in which at least one vertex parameter varies in predictable manner within a predetermined tolerance.

11. The method as recited in claim 2, wherein the examining comprises detecting pluralities of vertexes above a predetermined size that share at least one vertex parameter that is mathematically related within a predetermined maximum variance, and wherein the at least one vertex parameter is selected from the group consisting of:

position, normals, colors, texture map coordinates, texture information, material information, lighting information and surface material properties.

12. The method as recited in claim 2, wherein the examining comprises detecting pluralities of vertexes above a predetermined size that share at least one vertex parameter that is amenable to delta encoding with a predetermined maximum delta.

13. The method as recited in claim 2, wherein the examining comprises detecting pluralities of vertexes above a predetermined size that that share at least one vertex parameter that is capable of delta-delta encoding with a predetermined maximum delta.

14. The method as recited in claim 1, further comprising embedding opcodes within the compressed 3D geometric data indicative of whether the following vertex is encoded using the first encoding method or the second encoding method.

15. The method as recited in claim 1, further comprising embedding opcodes within the compressed 3D geometric data indicative of whether the following surface is encoded using the first method or the second method.

16. The method as recited in claim 11, wherein the opcodes each comprise a header and a body, wherein the header comprises a variable-length tag providing length information about the opcodes.

17. The method as recited in claim 12, further comprising generating error checking and correction information for the compressed 3D geometric information.

18. The method as recited in claim 13, further comprising storing the compressed 3D geometry information and error checking and correction information on computer-readable media for distribution and future decoding.

19. The method as recited in claim 13, further comprising transmitting the compressed 3D geometry information and error checking and correction information across a computer network.

20. The method as recited in claim 1, wherein the first encoding method encodes the regularly tiled surfaces as vertex rasters, and wherein the second encoding method encodes the irregularly tiled surfaces as a generalized triangle mesh.

21. The method of claim 1,

wherein said encoding one or more regularly tiled surface portions using a first encoding method comprises encoding any regularly tiled surface portions using the first encoding method, and

wherein said encoding one or more irregularly tiled surface portions using a second encoding method comprises encoding any irregularly tiled surface portions using the second encoding method.

23. The method as recited in claim 21, wherein the 3D geometry data includes information describing a plurality of vertices representing at least one surface of a 3D graphics object, wherein the first portion represents a first surface portion of the 3D graphics object, and wherein the second portion represents a second surface portion of the 3D graphics object.

24. The method as recited in claim 21, wherein the encoded first surface portion and the encoded second surface portion are compressed at independent compression rates.

25. The method as recited in claim 21, wherein the first compression technique comprises:

encoding an extent value which defines an arrangement of the vertices within the first surface portion, and

encoding vertex parameter values corresponding to the vertices within the first surface portion.

27. The method as recited in claim 25, wherein the first portion comprises a regular polygon mesh, and wherein the first compression method comprises encoding a beginning position of the regular polygon mesh and encoding a size of the regular polygon mesh.

29. The method of claim 27, wherein the irregular polygonal mesh portion is characterized by an irregular arrangement of vertices defining polygons.

31. The method of claim 29, further comprising compressing the compressed regular polygon mesh using the second compression method.

33. The method of claim 31, wherein the at least one regular polygonal mesh portion is characterized by a regular arrangement of polygons selected from the group consisting of rectangles, rhombuses, triangles, hexagons and parallelograms.

35. The method of claim 27, further comprising transmitting the compressed data over a network.

37. The software program as recited in claim 35, wherein said second compression method utilizes the predictable manner of change in vertex properties with said regular surface portions to achieve a second level of compression greater than the first level of compression achieved by the first compression method.

38. The software program as recited in claim 35, further comprising a fourth plurality of instructions configured to store the compressed three-dimensional graphics data on computer-readable media.

39. The software program as recited in claim 37, further comprising a fifth plurality of instructions configured to generate opcodes that are embedded within the compressed three-dimensional graphics data, wherein the opcodes are indicative of which type of compression was used on corresponding surface portions.

22. A computer-implemented method for compressing 3D geometry data, the method comprising:

receiving the 3D geometry data;

examining the 3D geometric data to detect the presence of groups of vertices that each have one or more parameters that change in a predictable manner,

wherein said examining determines that a first portion of the 3D geometry data comprises at least one group of vertices such that each of the vertices in the group has one or more parameters that change in a predictable manner;

encoding the first portion of the 3D geometry data using a first compression technique, wherein the encoding the first portion generates an encoded first surface portion;

encoding a second portion of the 3D geometry data using a second compression technique, wherein the second portion is different than the first portion, wherein the encoding the second portion generates an encoded second surface portion; and

storing the encoded first surface portion and the encoded second surface portion.

26. A computer-implemented method for compressing 3D geometry data, the method comprising:

receiving the 3D geometry data;

examining the 3D geometric data to detect the presence of groups of vertices that each have one or more parameters that change in a predictable manner,

wherein said examining determines that a first portion of the 3D geometry data comprises at least one group of vertices such that each of the vertices in the group has one or more parameters that change in a predictable manner;

encoding connectivity information for the first portion of the 3D geometry data using a first compression method;

encoding connectivity information for a second portion of the 3D geometry data using a second compression method;

encoding vertex parameter values of the first portion and the second portion of the 3D geometry data using a third compression method; and

storing the encoded connectivity information of the first portion of the 3D geometry data, the encoded connectivity information of the second portion of the 3D geometry data, and the encoded vertex parameters of the first portion and the second portion of the 3D geometry data.

28. A computer-implemented method for compressing a data stream of geometry data representing a 3D object, the method comprising:

converting the geometry data into a mesh format, wherein the mesh format includes at least one irregular polygonal mesh portion and at least one regular polygonal mesh portion, wherein the at least one regular polygonal mesh portion is characterized by a regular arrangement of vertices defining polygons;

examining the 3D geometric data to detect the presence of groups of vertices that each have one or more parameters that change in a predictable manner,

wherein said examining detects the at least one regular polygonal mesh portion as comprising at least one group of vertices such that each of the vertices in the group has one or more parameters that change in a predictable manner;

compressing the at least one irregular polygonal mesh portion using a first compression method, wherein the first compression method achieves a first level of compression; and

compressing the at least one regular polygonal mesh portion using a second compression method, wherein the second compression method utilizes the regular arrangement of the vertices to achieve a second level of compression greater than the first level of compression achieved by the first compression method.

30. The method of claim 28, further comprising compressing the compressed regular polygon mesh and irregular polygonal mesh portions using a third compression method.

32. The method of claim 30, wherein the at least one regular polygonal mesh portion is characterized by a regular arrangement of quadrilaterals of a same type.

34. The method of claim 32, wherein the at least one regular polygon mesh and the at least one irregular polygon mesh each comprise a lattice of vertices.

36. A software program for compressing three-dimensional graphics data, wherein the software program is embodied on computer-readable media and comprises:

a first plurality of instructions configured to detect regular surface portions within the three-dimensional graphics data, wherein said regular surface portions have vertices with one or more properties that change in a predictable manner;

a second plurality of instructions configured to compress irregular surface portions using a first compression method and achieve a first level of compression; and

a third plurality of instructions configured to compress irregular surface portions using a second compression method, wherein said second compression method differs from said first compression method.

40. A method for compressing 3D geometric data representing one or more 3D objects, comprising:

programmatically examining the 3D geometric data to detect the presence of regularly tiled surface portions, and

programmatically compressing the 3D geometric data by;

encoding one or more regularly tiled surface portions using a first encoding method, wherein the first encoding method comprises encoding a first value for each regularly tiled surface portion, wherein the first value defines an arrangement of the vertices to be compressed, and

encoding one or more irregularly tiled surface portions using a second encoding method, wherein the second encoding method is different from the first encoding method.

41. A method for compressing 3D geometric data representing one or more 3D objects, comprising:

examining the 3D geometric data to detect the presence of regularly tiled surface portions; and

compressing the 3D geometric data by;

encoding one or more regularly tiled surface portions using a first encoding method, wherein the first encoding method comprises;

encoding a value for each regularly tiled surface portion, wherein the value defines an arrangement of the vertices to be compressed;

specifying values indicative of how selected parameters of the vertices vary across the regularly tiled surface; and

specifying per-vertex information for vertices which deviate from said specified values; and

encoding one or more irregularly tiled surface portions using a second encoding method, wherein the second encoding method is different from the first encoding method.

42. The method as recited in claim 41, wherein the first encoding method encodes the regularly tiled surface portions as vertex rasters.

43. The method as recited in claim 41, wherein said encoding a value for each regularly tiled surface portion comprises encoding an extent value for each regularly tiled surface portion, wherein the extent values each define an arrangement of the vertices to be compressed.

44. The method as recited in claim 41, wherein the second encoding method encodes the irregularly tiled surfaces as a generalized triangle mesh.

45. The method as recited in claim 41, wherein said specifying values comprises:

specifying initial values for selected interpolatable parameters within the regularly tiled surface'"'"'s geometric data; and

specifying delta values indicative of how the selected parameters vary across the regularly tiled surface.

46. The method as recited in claim 45, wherein said specifying per-vertex information comprises specifying per-vertex information for vertices which deviate from the specified delta values.

47. The method as recited in claim 46, wherein said specifying per-vertex information comprises specifying per-vertex information for vertexes that do not deviate from the specified delta values but have additional information not represented by the delta values.

48. The method as recited in claim 41, wherein the first encoding method further comprises:

compressing the per-vertex information by reducing the number of bits used to represent the constituent vertex parameter values.

49. The method as recited in claim 41, wherein the vertex parameter values are selected from the group consisting of:

position, normal, color, texture, material, and lighting information.

50. The method as recited in claim 41, further comprising embedding opcodes within the compressed 3D geometric data indicative of whether the following vertex is encoded using the first encoding method or the second encoding method.

51. The method as recited in claim 41, further comprising embedding opcodes within the compressed 3D geometric data indicative of whether the following surface is encoded using the first method or the second method.

52. The method as recited in claim 51, wherein the opcodes each comprise a header and a body, wherein the header comprises a variable-length tag providing length information about the opcodes.

53. The method as recited in claim 41, further comprising generating error checking and correction information for the compressed 3D geometric information.

54. The method as recited in claim 53, further comprising storing the compressed 3D geometry information and error checking and correction information on computer-readable media for distribution and future decoding.

55. The method as recited in claim 53, further comprising transmitting the compressed 3D geometry information and error checking and correction information across a computer network.

56. The method as recited in claim 41, wherein the examining comprises detecting pluralities of vertexes above a predetermined size in which at least one vertex parameter varies in a predictable manner within a predetermined tolerance.

57. The method as recited in claim 41, wherein the examining comprises detecting pluralities of vertexes above a predetermined size that share at least one vertex parameter that is mathematically related within a predetermined maximum variance, and wherein the at least one vertex parameter is selected from the group consisting of:

position, normals, colors, texture map coordinates, texture information, material information, lighting information and surface material properties.

58. The method as recited in claim 41, wherein the examining comprises detecting pluralities of vertexes above a predetermined size that share at least one vertex parameter that is amenable to delta encoding with a predetermined maximum delta.

59. The method as recited in claim 41, wherein the examining comprises detecting pluralities of vertexes above a predetermined size that that share at least one vertex parameter that is capable of delta-delta encoding with a predetermined maximum delta.

60. The method as recited in claim 41, wherein the first encoding method encodes the regularly tiled surfaces as vertex rasters, and wherein the second encoding method encodes the irregularly tiled surfaces as a generalized triangle mesh.

61. A method for compressing 3D geometry data, the method comprising

receiving the 3D geometry data;

encoding a first portion of the 3D geometry data using a first compression technique wherein the first portion includes a regularly tiled surface portion, wherein the encoding the first portion generates an encoded first surface portion, wherein said encoding the first portion comprises;

encoding a value for the regularly tiled surface portion, wherein the value defines an arrangement of the vertices to be compressed;

specifying values indicative of how selected parameters of the vertices vary across the regularly tiled surface portion; and

specifying per-vertex information for vertices which deviate from said specified values; and

encoding a second portion of the 3D geometry data using a second compression technique, wherein the encoding the second portion generates an encoded second surface portion; and

storing the encoded first surface portion and the encoded second surface portion.

62. The method as recited in claim 61, wherein the 3D geometry data includes information describing a plurality of vertices representing at least one surface of a 3D graphics object, wherein the first portion represents a first surface portion of the 3D graphics object, and wherein the second portion represents a second surface portion of the 3D graphics object.

63. The method as recited in claim 61, wherein the encoded first surface portion and the encoded second surface portion are compressed at independent compression rates.

64. A method for compressing 3D geometry data, the method comprising:

receiving the 3D geometry data;

encoding connectivity information for a first portion of the 3D geometry data using a first compression method, wherein the first portion comprises a regular polygon mesh, and wherein the first compression method comprises encoding a beginning position of the regular polygon mesh and encoding a size of the regular polygon mesh;

encoding connectivity information for a second portion of the 3D geometry data using a second compression method;

encoding vertex parameter values of the first portion and the second portion of the 3D geometry data using a third compression method; and

storing the encoded connectivity information of the first portion of the 3D geometry data, the encoded connectivity information of the second portion of the 3D geometry data, and the encoded vertex parameters of the first portion and the second portion of the 3D geometry data.

65. A method for compressing a data stream of geometry data representing a 3D object, the method comprising:

converting the geometry data into a mesh format, wherein the mesh format includes at least one irregular polygonal mesh portion and at least one regular polygonal mesh portion, wherein the at least one regular polygonal mesh portion is characterized by a regular arrangement of vertices defining polygons;

compressing the at least one irregular polygonal mesh portion using a first compression method, wherein the first compression method achieves a first level of compression; and

compressing the at least one regular polygonal mesh portion using a second compression method, wherein the second compression method utilizes the regular arrangement of the vertices to achieve a second level of compression greater than the first level of compression achieved by the first compression method;

compressing the compressed regular polygon mesh and irregular polygonal mesh portions using a third compression method.

66. The method of claim 65, wherein the irregular polygonal mesh portion is characterized by an irregular arrangement of vertices defining polygons.

67. The method of claim 65,

further comprising compressing the compressed regular polygon mesh using the second compression method.

68. The method of claim 65, wherein the at least one regular polygonal mesh portion is characterized by a regular arrangement of quadrilaterals of a same type,”

69. The method of claim 65, wherein the at least one regular polygonal mesh portion is characterized by a regular arrangement of polygons selected from the group consisting of rectangles, rhombuses, triangles, hexagons and parallelograms.

70. The method of claim 65, wherein the at least one regular polygon mesh and the at least one irregular polygon mesh each comprise a lattice of vertices.

71. The method of claim 65, further comprising transmitting the compressed data over a network.

72. A software program for compressing three-dimensional graphics data, wherein the software program is embodied on computer-readable media and comprises:

a first plurality of instructions configured to detect regular surface portions within the three-dimensional graphics data, wherein said regular surface portions have vertices with one or more properties that change in a predictable manner;

a second plurality of instructions configured to compress irregular surface portions using a first compression method and achieve a first level of compression,

a third plurality of instructions configured to compress regular surface portions using a second compression method, wherein said second compression method differs from said first compression method, wherein the third plurality of instructions are operable to;

encode a value for each regularly tiled surface portion, wherein the value defines an arrangement of the vertices to be compressed;

specify values indicative of how selected parameters of the vertices vary across the regularly tiled surface; and

specify per-vertex information for vertices which deviate from said specified values.

73. The software program as recited in claim 72, wherein said second compression method utilizes the predictable manner of change in vertex properties with said regular surface portions to achieve a second level of compression greater than the first level of compression achieved by the first compression method.

74. The software program as recited in claim 72, further comprising a fourth plurality of instructions configured to store the compressed three-dimensional graphics data on computer-readable media.

75. The software program as recited in claim 72, further comprising a fourth plurality of instructions configured to generate opcodes that are embedded within the compressed three-dimensional graphics data, wherein the opcodes are indicative of which type of compression was used on corresponding surface portions.

76. A method for compressing 3D geometric data representing one or more 3D objects, comprising:

examining the 3D geometric data to detect the presence of regularly tiled surface portions;

compressing the 3D geometric data by;

encoding any regularly tiled surface portions using a first encoding method; and

encoding any irregularly tiled surface portions using a second encoding method, wherein the second encoding method is different from the first encoding method; and

generating error checking and correction information for the compressed 3D geometric information.

77. A method for compressing 3D geometric data representing one or more 3D objects, comprising:

examining the 3D geometric data to detect the presence of regularly tiled surface portions, wherein the examining comprises detecting pluralities of vertexes above a predetermined size in which at least one vertex parameter varies in predictable manner within a predetermined tolerance;

compressing the 3D geometric data by;

encoding any regularly tiled surface portions using a first encoding method; and

encoding any irregularly tiled surface portions using a second encoding method, wherein the second encoding method is different from the first encoding method.

78. A method for compressing 3D geometric data representing one or more 3D objects, comprising:

examining the 3D geometric data to detect the presence of regularly tiled surface portions, wherein the examining comprises detecting pluralities of vertexes above a predetermined size that share at least one vertex parameter that is mathematically related within a predetermined maximum variance, and wherein the at least one vertex parameter is selected from the group consisting of;

position, normals, colors, texture map coordinates, texture information, material information, lighting information and surface material properties;

compressing the 3D geometric data by;

encoding any regularly tiled surface portions using a first encoding method; and

encoding any irregularly tiled surface portions using a second encoding method, wherein the second encoding method is different from the first encoding method.

79. A method for compressing 3D geometric data representing one or more 3D objects, comprising:

examining the 3D geometric data to detect the presence of regularly tiled surface portions, wherein the examining comprises detecting pluralities of vertexes above a predetermined size that share at least one vertex parameter that is amenable to delta encoding with a predetermined maximum delta;

compressing the 3D geometric data by;

encoding any regularly tiled surface portions using a first encoding method; and

encoding any irregularly tiled surface portions using a second encoding method, wherein the second encoding method is different from the first encoding method.

80. A method for compressing 3D geometric data representing one or more 3D objects, comprising:

examining the 3D geometric data to detect the presence of regularly tiled surface portions, wherein the examining comprises detecting pluralities of vertexes above a predetermined size that that share at least one vertex parameter that is capable of delta-delta encoding with a predetermined maximum delta;

compressing the 3D geometric data by;

encoding any regularly tiled surface portions using a first encoding method; and

encoding any irregularly tiled surface portions using a second encoding method, wherein the second encoding method is different from the first encoding method.

81. A method for compressing 3D geometric data representing one or more 3D objects, comprising:

encoding one or more regularly tiled surface portions in the 3D geometric data using a first encoding method, wherein the first encoding method comprises;

encoding a value for each regularly tiled surface portion, wherein the value defines an arrangement of the vertices to be compressed;

specifying values indicative of how selected parameters of the vertices vary across the regularly tiled surface; and

specifying per-vertex information for vertices which deviate from said specified values; and

encoding one or more irregularly tiled surface portions in the 3D geometric data using a second encoding method, wherein the second encoding method is different from the first encoding method.