# US 2019/0318508 A1 · Vertex split connectivity prediction 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/0318508 A1
- Document ID: US20190318508A1
- Status: Published application
- Kind: A1
- Application number: 15/951,969
- 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/US20190318508A1

## CPC

- G06T 9/001: {Model-based coding, e.g. wire frame}
- G06T 9/004: {Predictors, e.g. intraframe, interframe coding}
- G06T 17/20: Finite element generation, e.g. wire-frame surface description, {tesselation}
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## 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 identifying a pair of partitioning vertices to be connected to a split vertex associated with a collapse of an edge, creating the split vertex by collapsing the edge, encoding partitioning vertex information associated with the pair of partitioning vertices, the encoding of the partitioning vertex information based on an ordering of vertices of an umbrella of the split vertex, and the ordering of vertices of the umbrella determined based on a geometric shape and connectivity of the umbrella, and generating vertex split information that includes the partitioning vertex information. In another example implementation, the method may include entropy encoding the vertex split information prior to being transmitted.

## Claims

### Claim 1

A computer-implemented method of progressive mesh compression, comprising:
identifying, by an encoder, a pair of partitioning vertices to be connected to a split vertex associated with a collapse of an edge;
creating, by the encoder, the split vertex by collapsing the edge;
encoding, by the encoder, partitioning vertex information associated with the pair of partitioning vertices, the encoding of the partitioning vertex information based on an ordering of vertices of an umbrella of the split vertex, and the ordering of vertices of the umbrella determined based on a geometric shape and connectivity of the umbrella; and
generating, by the encoder, vertex split information that includes the partitioning vertex information.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
transmitting, from the encoder, the vertex split 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 ordering of vertices of the umbrella further comprises:
determining a diameter of the umbrella, the diameter being determined based on a maximum possible distance between a pair of the vertices of the umbrella;
determining a distance between each of the vertices of the umbrella and a perpendicular bisector of the diameter; and
sorting the vertices of the umbrella in an increasing order of the determined distance.

### Claim 5 (depends on 4)

The method of claim 4, wherein the perpendicular bisector is perpendicular to the diameter and splits the diameter into two equal halves, and wherein the pair of partitioning vertices are on opposite sides of the diameter of the umbrella.

### Claim 6 (depends on 1)

The method of claim 1, wherein the encoding further comprises:
encoding each partitioning vertex of the pair of partitioning vertices with a first value; and
encoding each non-partitioning vertex of the vertices of the umbrella with a second value, and wherein the first value is different from the second value.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
encoding each partitioning vertex of the pair of partitioning vertices with a first value;
encoding each non-partitioning vertex of the vertices of the umbrella with a second value, and wherein the first value is different from the second value; and
terminating the encoding in response to encoding the two partitioning vertices.

### Claim 8 (depends on 1)

The method of claim 1, wherein the split vertex is created by collapsing the edge based on a full-edge or a half-edge collapse operation.

### Claim 9

An encoder, comprising:
a processor; and
a memory, the memory including instructions configured to cause the processor to:
identify a pair of partitioning vertices to be connected to a split vertex associated with a collapse of an edge;
create the split vertex by collapsing the edge;
encode partitioning vertex information associated with the pair of partitioning vertices, the encoding of the partitioning vertex information based on an ordering of vertices of an umbrella of the split vertex, and the ordering of vertices of the umbrella determined based on a geometric shape and connectivity of the umbrella; and
generate vertex split information that includes the partitioning vertex information.

### Claim 10 (depends on 9)

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

### Claim 11 (depends on 9)

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

### Claim 12 (depends on 9)

The encoder of claim 9, further comprising instructions to cause the processor to:
determine a diameter of the umbrella, the diameter being determined based on a maximum possible distance between a pair of the vertices of the umbrella;
determine a distance between each of the vertices of the umbrella and a perpendicular bisector of the diameter; and
sort the vertices of the umbrella in an increasing order of the determined distance.

### Claim 13

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:
identifying, by an encoder, a pair of partitioning vertices to be connected to a split vertex associated with a collapse of an edge;
creating, by the encoder, the split vertex by collapsing the edge;
encoding, by the encoder, partitioning vertex information associated with the pair of partitioning vertices, the encoding of the partitioning vertex information based on an ordering of vertices of an umbrella of the split vertex, and the ordering of vertices of the umbrella determined based on a geometric shape and connectivity of the umbrella; and
generating, by the encoder, vertex split information that includes the partitioning vertex information.

### Claim 14 (depends on 13)

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

### Claim 15 (depends on 13)

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

### Claim 16 (depends on 13)

The computer-readable storage medium of claim 13, wherein the ordering of vertices of the umbrella further comprises code for:
determining a diameter of the umbrella, the diameter being determined based on a maximum possible distance between a pair of the vertices of the umbrella;
determining a distance between each of the vertices of the umbrella and a perpendicular bisector of the diameter; and
sorting the vertices of the umbrella in an increasing order of the determined distance.

### Claim 17 (depends on 16)

The computer-readable storage medium of claim 16, wherein the perpendicular bisector is perpendicular to the diameter and splits the diameter into two equal halves, and wherein the pair of partitioning vertices are on opposite sides of the diameter of the umbrella.

### Claim 18 (depends on 13)

The computer-readable storage medium of claim 13, wherein the encoding further comprises code for:
encoding each partitioning vertex of the pair of partitioning vertices with a first value; and
encoding each non-partitioning vertex of the vertices of the umbrella with a second value, and wherein the first value is different from the second value.

### Claim 19 (depends on 13)

The computer-readable storage medium of claim 13, further comprising code for:
encoding each partitioning vertex of the pair of partitioning vertices with a first value;
encoding each non-partitioning vertex of the vertices of the umbrella with a second value, and wherein the first value is different from the second value; and
terminating the encoding in response to encoding the two partitioning vertices.

### Claim 20 (depends on 13)

The computer-readable storage medium of claim 13, wherein the split vertex is created by collapsing the edge based on a full-edge or a half-edge collapse operation.