# US 2019/0318507 A1 · Increased density of batches for improved progressive mesh compression

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0318507 A1
- Document ID: US20190318507A1
- Status: Published application
- Kind: A1
- Application number: 15/951,963
- Filed: 2018-04-12
- Published: 2019-10-17
- Earliest claimed: 2018-04-12
- Assignees: Google Inc.
- Applicants: Google LLC
- Inventors: Michael Hemmer; Pierre Alliez; Cedric Portaneri
- Web page: https://patentgrep.com/patent/US20190318507A1

## CPC

- G06T 9/001: {Model-based coding, e.g. wire frame}
- G06T 17/20: Finite element generation, e.g. wire-frame surface description, {tesselation}
- H04N 19/91: Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

An encoder includes a processor and a memory. The encoder may perform a method of progressive compression. In one example implementation, the method may include determining priority values associated with collapse of each edge of a plurality of edges. The method may further include selecting a first edge from the plurality of edges, determining adjusted priority values of edges in a vicinity of the selected first edge, selecting a second edge from remaining edges of the plurality of edges after the selecting of the first edge, and collapsing the selected edges such that vertex split information is generated that is based on the collapsing of the selected edges. In some implementations, the method may further include entropy encoding of the vertex split information.

## Claims

### Claim 1

A computer-implemented method of progressive mesh compression, comprising:
determining, by an encoder, priority values associated with collapse of each edge of a plurality of edges, a priority value of an edge determined based on an associated error metric value of the edge;
selecting, by the encoder, a first edge from the plurality of edges, the first edge selected from the plurality of edges based on the first edge having a highest priority value of the plurality of the edges;
determining, by the encoder, adjusted priority values of edges in a vicinity of the selected first edge;
selecting, by the encoder, a second edge from remaining edges of the plurality of edges after the selecting of the first edge, the second edge selected based on the second edge having a highest adjusted priority value; and
collapsing, by the encoder, the selected edges such that vertex split information is generated that is based on the collapsing of the selected edges.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
entropy encoding, by the encoder, the vertex split information.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
transmitting, from the encoder, the generated split vertex information to a decoder in response to a message received from the decoder.

### Claim 4 (depends on 1)

The method of claim 1, wherein the adjusted priority value associated with an edge is determined based on an allowed variance to the priority value associated with the edge, an actual number of edges blocked by the edge, and a maximum number of edges that could be blocked by the edge.

### Claim 5 (depends on 1)

The method of claim 1, wherein an edge is added to the independent set of edges when a collapse of the edge is not being blocked by collapse of other edges that are already included in the independent set of edges.

### Claim 6 (depends on 1)

The method of claim 1, wherein the collapse of an edge further comprises:
collapsing the edge that connects two vertices using a full-edge or a half-edge collapse operation.

### Claim 7 (depends on 1)

The method of claim 1, wherein a highest priority value corresponds to a lowest error metric value.

### Claim 8

An encoder, comprising:
a processor; and
a memory, the memory including instructions configured to cause the processor to:
determine priority values associated with collapse of each edge of a plurality of edges, a priority value of an edge determined based on an associated error metric value of the edge;
select a first edge from the plurality of edges, the first edge selected from the plurality of edges based on the first edge having a highest priority value of the plurality of the edges;
determine adjusted priority values of edges in a vicinity of the selected first edge;
select a second edge from remaining edges of the plurality of edges after the selecting of the first edge, the second edge selected based on the second edge having a highest adjusted priority value; and
collapse the selected edges determined such that vertex split information is generated that is based on the collapsing of the selected edges.

### Claim 9 (depends on 8)

The encoder of claim 8, further comprising instructions to cause the processor to:
entropy encode the vertex split information.

### Claim 10 (depends on 8)

The encoder of claim 8, further comprising instructions to cause the processor to:
transmit the generated split vertex information to a decoder in response to a message received from the decoder.

### Claim 11 (depends on 8)

The encoder of claim 8, wherein the adjusted priority value associated with an edge is determined based on an allowed variance to the priority value associated with the edge, an actual number of edges blocked by the edge, and a maximum number of edges that could be blocked by the edge.

### Claim 12 (depends on 8)

The encoder of claim 8, wherein an edge is added to the independent set of edges when a collapse of the edge is not being blocked by collapse of other edges that are already included in the independent set of edges.

### Claim 13 (depends on 8)

The encoder of claim 8, wherein a highest priority value corresponds to a lowest error metric value.

### Claim 14

A non-transitory computer-readable storage medium having stored thereon computer executable program code which, when executed on a computer system, causes the computer system to perform a method of progressive mesh compression, comprising:
determining, by an encoder, priority values associated with collapse of each edge of a plurality of edges, a priority value of an edge determined based on an associated error metric value of the edge;
selecting, by the encoder, a first edge from the plurality of edges, the first edge selected from the plurality of edges based on the first edge having a highest priority value of the plurality of the edges;
determining, by the encoder, adjusted priority values of edges in a vicinity of the selected first edge;
selecting, by the encoder, a second edge from remaining edges of the plurality of edges after the selecting of the first edge, the second edge selected based on the second edge having a highest adjusted priority value; and
collapsing, by the encoder, the selected edges such that vertex split information is generated that is based on the collapsing of the selected edges.

### Claim 15 (depends on 14)

The computer-readable storage medium of claim 14, further comprising code for:
entropy encoding, by the encoder, the vertex split information.

### Claim 16 (depends on 14)

The computer-readable storage medium of claim 14, further comprising code for:
transmitting, from the encoder, the generated split vertex information to a decoder in response to a message received from the decoder.

### Claim 17 (depends on 14)

The computer-readable storage medium of claim 14, wherein the adjusted priority value associated with an edge is determined based on an allowed variance to the priority value associated with the edge, an actual number of edges blocked by the edge, and a maximum number of edges that could be blocked by the edge.

### Claim 18 (depends on 14)

The computer-readable storage medium of claim 14, wherein an edge is added to the independent set of edges when a collapse of the edge is not being blocked by collapse of other edges that are already included in the independent set of edges.

### Claim 19 (depends on 14)

The computer-readable storage medium of claim 14, further comprising code for:
collapsing the edge that connects two vertices using a full-edge or a half-edge collapse operation.

### Claim 20 (depends on 14)

The computer-readable storage medium of claim 14, wherein a highest priority value corresponds to a lowest error metric value.