Bi-level iso-surface compression

• US 7,847,799 B2
• Filed: 03/27/2007
• Issued: 12/07/2010
• Est. Priority Date: 07/31/2002
• Status: Active Grant

• 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 D
• Application Number:
  US11/692,123
• Publication Number:
  US 20070206007A1
• Time in Patent Office: 1,351 Days
• Field of Search: 345/419, 345/420, 345/424, 345/427, 382/131, 382/132, 382/232, 382/287, 382/233, 382/247
• 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 method comprising an out-of-core isosurface decoder process producing a set of oriented points as a surface representation, the process comprising:

receiving as input;

compressed isosurface data generated by an isosurface encoder process;

a three-dimensional grid used to define function values of a scalar function of an approximate isosurface, said three-dimensional grid comprising a plurality of grid vertices and grid edges, wherein each intersecting grid edge comprises two edge ends, the edge ends being grid nodes, the grid nodes being neighbors in the three-dimensional grid, with occupancy bits of an occupancy image corresponding to the grid nodes;

wherein the occupancy bit values are a function of the three-dimensional grid, the scalar function and an isolevel, with one quantized scalar value per intersecting grid edge; and

intersection points and intersection point surface normals;

decoding the occupancy image, the intersection points, and the intersection point surface normals by scanning the volume data-in scan order;

wherein for each grid vertex there are exactly three other grid vertices, which are neighbors of the grid vertex and precede the grid vertex in the scan order;

reconstructing a geometry of the surface representation from a location of the intersection points and the intersection point normals;

using an out-of-core isosurface decoder process for producing the set of oriented points as a surface representation, and the decoder process generates at least one oriented point;

constructing a current context word by combining occupancy bits corresponding to grid vertices previously visited;

decoding a current occupancy bit from an occupancy image record of the compressed isosurface data with respect to the current context;

comparing the current occupancy bit with the occupancy bit corresponding to the previously visited neighbor grid vertex to determine if an intersection point exists along the edge connecting the current grid vertex and the previously visited grid vertex;

determining the location of the intersection point along the edge if the occupancy bit values are different;

deriving a normalized intersection point parameter;

determining a normal vector corresponding to the intersection point parameter;

deriving an intersection point normal vector;

performing an additional geometry smoothing step to improve a quality of the reconstructed surface representation;

generating one oriented point after decoding and reconstructing each intersection point and corresponding normal vector; and

reconstructing an isosurface polygon mesh from an occupancy image, comprising 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 of the corresponding Marching Cubes vertex more precisely in scan-order.

2. A method as recited in claim 1, further comprising a decompression step comprising reconstructing an isosurface polygon mesh from the occupancy image.

3. The method of claim 1, wherein the step of deriving the normalized intersection point parameter comprises decoding the normalized intersection point parameter from an intersection point'"'"'s record if the compressed isosurface data includes the intersection points record.

4. The method of claim 1, wherein the step of deriving the normalized intersection point parameter comprises setting the normalized intersection point parameter to a default value if the compressed isosurface data does not include the intersection points record.

5. The method of claim 1 wherein the step of deriving the intersection point normal vector comprises decoding the normal vector from the normal vectors record if said normal vectors record is included in the compressed isosurface data.

6. The method of claim 1 wherein the step of deriving the intersection point normal vector comprises setting the normal vector to a default value if the normal vector is not included in the compressed isosurface data.

7. A non-transitory computer-readable storage medium comprising:

a data structure representing an approximate isosurface, said data structure comprising;

compressed isosurface data generated by an isosurface encoder process, said compressed isosurface data comprising an encoded occupancy image, an optional intersection points record, and an optional normal vectors record;

a three-dimensional grid used to define function values of a scalar function of the approximate isosurface, said three-dimensional grid comprising a polygonal mesh structure, a plurality of grid vertices and a plurality of grid edges, a level set defined by an isolevel, each scalar function value corresponding to one grid vertex of the three-dimensional grid, and one quantized scalar value per intersecting grid edge; and

an out-of-core isosurface decoder algorithm program that produces a set of oriented points as a surface representation, wherein the decoder process takes as input a compressed isosurface data with the optional intersection points record and the normal vectors record, and immediately after decoding and reconstructing each intersection point and corresponding normal vector, the decoder process generates at least one oriented point;

wherein the encoded occupancy image is 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; and

wherein the data structure further comprises;

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;

any remaining second proportion of geometric information in a form of one quantized scalar value per intersecting grid edge;

a location of the corresponding Marching Cubes vertex being specified by being efficiently encoded in scan-order.