Bi-level iso-surface compression

• US 7,230,616 B2
• Filed: 01/02/2003
• Issued: 06/12/2007
• Est. Priority Date: 07/31/2002
• Status: Expired due to Term

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Taubin, Gabriel
• Primary Examiner(s): Chauhan, Ulka
• Assistant Examiner(s): Prendergast, Roberta
• Application Number:
  US10/336,496
• Publication Number:
  US 20040021662A1
• Time in Patent Office: 1,622 Days
• Field of Search: 345/420, 345/424, 345/419, 345/427
• US Class Current: 345/424
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00

Abstract

Methods, structures and systems for encoding and decoding isosurface data. An encoder process takes volume data and an isolevel as input and produces compressed isosurface data as output. The compressed isosurface data produced by an encoder process is composed of an occupancy image record, an optional intersection points record, and an optional normal vectors record. An occupancy image is compressed with a context-based arithmetic encoder. Compressed isosurface data can be stored in a data storage device or transmitted through a communication medium to a remote computer system, where the decoder process is executed. The decoder processes take compressed surface data as input and produce surface data as output. The decoder processes first reconstructs the occupancy image by decoding the occupancy image record. An in-core isosurface decoder process produces a polygon mesh as a surface representation. An out-of-core isosurface decoder process produces a set of oriented points as a surface representation.

Claims

1. A computer system comprising a memory, a data structure stored in the memory of the computer system for representing an approximate isosurface, the approximate isosurface approximating a level set of a scalar function, the scalar function defined by function values and a 3D regular grid, the 3D regular grid comprising a plurality of grid vertices and a plurality of grid edges, each grid edge having two edge ends, each edge end being a grid vertex, the level set defined by an isolevel, each function value corresponding to one grid vertex of the 3D regular grid, the data structure embodied in computer-readable material used in at least one of a computer graphics application and scientific visualization application to representing isosurface data in compressed form, and having mesh connectivity and a substantial first proportion of geometric information encoded to a fraction of a bit per Marching Cubes vertex with a context based arithmetic coder, and having any remaining second proportion of geometric information in the form of one quantized scalar value per intersecting grid edge, and specifying the location the corresponding Marching Cubes vertex more precisely, being efficiently encoded in scan-order with the same mechanism, the data structure comprising:

an occupancy image record,

the occupancy image record including an encoded occupancy image,

the encoded occupancy image being the result of applying a binary encoding algorithm to an existing occupancy image,

the existing occupancy image composed of occupancy bits,

each occupancy bit corresponding with the grid vertex of the 3D regular grid, each occupancy bit being equal to one of a first value and a second value, and

each occupancy bit having a corresponding function value, each occupancy bit being equal to the first value if the corresponding function value is less than the isolevel, and to the second value if the corresponding function value is higher than the isolevel.

2. A computer system as recited in claim 1, wherein the binary encoding algorithm is a context-based arithmetic coder,

the context based arithmetic coder encoding the bits of the occupancy image in a scanning order,

the context-based arithmetic coder using a different context word to encode each current bit of the occupancy image,

the context word composed of context word bits,

each context word bit being equal to a preceding occupancy bit, and

the preceding occupancy bit being a bit of the occupancy image preceding the current bit in the scanning order.

3. A computer system as recited in claim 1, further comprising:

an intersection points record,

the intersection points record composed of normalized intersection parameters,

each normalized intersection parameter associated with an intersecting grid edge,

each intersecting grid edge having two edge ends, each edge end being one of the grid vertices, wherein two grid nodes being neighbors in the 3D regular grid, the occupancy bits corresponding to the two grid nodes having different values.

4. A computer system as recited in claim 3, wherein the normalized intersection parameters are numbers between zero and one.

5. A computer system as recited in claim 4, wherein the normalized intersection parameters are quantized.

6. A computer system as recited in claim 5, wherein the normalized intersection parameters are compressed.

7. A computer system as recited in claim 5, wherein the quantized normalized intersection parameters are represented as one or more point bitplane three-dimensional images, and each point bitplane three-dimensional image is compressed using the context-based arithmetic coder.

8. A computer system as recited in claim 1, further comprising a normal vector record, the normal vector record composed of normal vectors, each normal vector associated with the intersecting grid edge.

9. A computer system as recited in claim 8, wherein the normal vectors are quantized.

10. A computer system as recited in claim 8, wherein the normal vectors are compressed.

11. A computer system as recited in claim 9, wherein the quantized normal vectors are represented as one or more normal bitplane three-dimensional images, and each normal bitplane three-dimensional image is compressed using a context-based arithmetic coder.

12. An encoding method comprising:

determining values of occupancy bits of an occupancy image as a function of a 3D regular grid, a scalar function and an isolevel, the occupancy image embodied in computer-readable material for use in at least one of a computer graphics application and a scientific visualization application to represent isosurface data in compressed form, and having mesh connectivity and a substantial first proportion of geometric information encoded to a fraction of a bit per Marching Cubes vertex with a context based arithmetic coder, and having any remaining second proportion of geometric information in the form of one quantized scalar value per intersecting grid edge, and specifying the location the corresponding Marching Cubes vertex more precisely, being efficiently encoded in scan-order with the same mechanism, the method further comprising;

visiting the nodes of the three-dimensional grid in a scanning order,

visiting the nodes of the three-dimensional grid in a scanning order,

comparing the function value associated with each node with the isolevel,

setting a value of the occupancy bit associated with each node to a first value if the function value is less than the isolevel,

setting the value of the occupancy bit associated with each node to a second value if the function value is higher than the isolevel, and

employing the occupancy bit value associated with each node in said occupancy image embodied in said computer-readable material for use in said at least one of said computer graphics application and said scientific visualization application to represent isosurface data in compressed form.

13. A method as recited in claim 12, further comprising determining the point location values.

14. A method as recited in claim 12, further comprising determining the normal vector values.

15. An article of manufacture comprising a computer readable medium having computer readable program code means embodied therein for causing data compression, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 12.

16. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for data compression, said method steps comprising the steps of claim 12.

17. A decoding method comprising reconstructing an isosurface polygon mesh from an occupancy image, comprising the steps of:

taking compressed surface data as input and producing surface data as output, said mesh having mesh connectivity and a substantial first proportion of geometric information encoded to a fraction of a bit per Marching Cubes vertex with a context based arithmetic coder, and having any remaining second proportion of geometric information in the form of one quantized scalar value per intersecting grid edge, and specifying the location the corresponding Marching Cubes vertex more precisely, being efficiently encoded in scan-order with the same mechanism;

reconstructing the occupancy image by decoding an occupancy image record;

determining intersection edges and decoding intersection points and corresponding normal vectors from an intersection points record and an normal vectors record, respectively, if present in the compressed isosurface data;

assigning default values to the intersection points and corresponding normal vectors, if the intersection points record and normal vectors record are not present in the compressed isosurface data, and

employing results of the steps of reconstructing, determining and assigning in said occupancy image embodied in a computer-readable material for use in at least one of a computer graphics application and a scientific visualization application to represent the isosurface data.

18. A method comprising an in-core isosurface decoder process embodied in computer-readable material producing a polygon mesh as a surface representation, said mesh having mesh connectivity and a substantial first proportion of geometric information encoded to a fraction of a bit per Marching Cubes vertex with a context based arithmetic coder, and having any remaining second proportion of geometric information in the form of one quantized scalar value per intersecting grid edge, and specifying the location the corresponding Marching Cubes vertex more precisely, being efficiently encoded in scan-order with the same mechanism, the process including:

taking as input compressed isosurface data without an optional intersection points record and without a normal vectors record;

setting normalized intersection points to a default value of one half,

giving normal vectors default values being a function of neighboring intersection point values;

using a smoothing algorithm as a global predictor to form and improve a quality of a reconstructed polygon mesh, and

employing results of the steps of setting, giving and using in producing said polygon mesh as said surface representation, embodied in said computer-readable material for use in at least one of a computer graphics application and a scientific visualization application.

19. A method as recited in claim 18, further comprising at least one of

storing compressed isosurface data in a data storage device;

transmitting the compressed isosurface data through a communication medium to a remote computer system wherein the process is executed.

20. A method as recited in claim 18, including reconstructing the polygon mesh from an occupancy image.

21. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for data decompression, said method steps comprising the steps of claim 18.

22. An article of manufacture comprising a computer readable medium having computer readable program code means embodied therein for causing data control, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 19.

23. A method comprising an out-of-core isosurface decoder process producing a set of oriented points as a surface representation, the process including:

taking as input compressed isosurface data with any optional intersection points record and any optional normal vectors record;

generating one oriented point after decoding and reconstructing each said any optional intersection point and corresponding said any optional normal vector, and

employing results of the steps of taking and generating in producing said set of oriented points as said surface representation, embodied in a computer-readable material for use in at least one of a computer graphics application and a scientific visualization application; and

reconstructing an isosurface polygon mesh from said set of oriented points as a surface representation, said mesh having mesh connectivity and a substantial first proportion of geometric information encoded to a fraction of a bit per Marching Cubes vertex with a context based arithmetic coder, and having any remaining second proportion of geometric information in the form of one quantized scalar value per intersecting grid edge, and specifying the location the corresponding Marching Cubes vertex more precisely, being efficiently encoded in scan-order with the same mechanism.

24. A system comprising:

a memory of a computer system storing the data structure for representing an isosurface polygonal mesh and having mesh connectivity and a substantial first proportion of geometric information encoded to a fraction of a bit per Marching Cubes vertex with a context based arithmetic coder, and having any remaining second proportion of geometric information in the form of one quantized scalar value per intersecting grid edge, and specifying the location the corresponding Marching Cubes vertex more precisely, being efficiently encoded in scan-order with the same mechanism, the isosurface polygonal mesh approximating a level set of a scalar function, the scalar function defined by function values and a regular three-dimensional grid, the level set defined by an isolevel, each function value associated with a node of the regular three-dimensional grid, the data structure having an occupancy record, the occupancy record including a three-dimensional occupancy image, the three-dimensional occupancy image composed of occupancy bits, each occupancy bit associated with a node of the three-dimensional grid, each occupancy bit being equal to either a first value or a second value, each occupancy bit having a corresponding function value, each occupancy bit being equal to the first value if the corresponding function value is less than the isolevel, and to the second value if the corresponding function value is higher than the isolevel.

25. A method comprising:

storing a data structure for representing an isosurface polygonal mesh, and having mesh connectivity and a substantial first proportion of geometric information encoded to a fraction of a bit per Marching Cubes vertex with a context based arithmetic coder, and having any remaining second proportion of geometric information in the form of one quantized scalar value per intersecting grid edge, and specifying the location the corresponding Marching Cubes vertex more precisely, being efficiently encoded in scan-order with the same mechanism, the isosurface polygonal mesh approximating a level set of a scalar function, the scalar function defined by function values and a regular three-dimensional grid, the level set defined by an isolevel, each function value associated with a node of the regular three-dimensional grid,

providing the data structure with an occupancy record, the occupancy record including a three-dimensional occupancy image, the three-dimensional occupancy image composed of occupancy bits, each occupancy bit associated with a node of the three-dimensional grid, each occupancy bit being equal to either a first value or a second value, each occupancy bit having a corresponding function value,

setting each occupancy bit being equal to the first value if the corresponding function value is less than the isolevel, and to the second value if the corresponding function value is higher than the isolevel, and

employing each occupancy bit value in said occupancy image embodied in a computer-readable material for use in at least one of a computer graphics application and a scientific visualization application to represent isosurface data.

26. An encoding apparatus comprising:

means for determining values of occupancy bits of an occupancy image as a function of a 3D regular grid, a scalar function and an isolevel, and having mesh connectivity and a substantial first proportion of geometric information encoded to a fraction of a bit per Marching Cubes vertex with a context based arithmetic coder, and having any remaining second proportion of geometric information in the form of one quantized scalar value per intersecting grid edge, and specifying the location the corresponding Marching Cubes vertex more precisely, being efficiently encoded in scan-order with the same mechanism, the means including;

means for visiting nodes of the three-dimensional grid in scanning order,

means for comparing a function value associated with each node with the isolevel,

means for setting a value of the occupancy bit associated with each node to a first value if the function value is less than the isolevel, and

means for setting the value of the occupancy bit associated with each node to a second value if the function value is higher than the isolevel.