# US 2015/0103073 A1 · Efficient compression of 3d models based on octree decomposition

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

- Number: US 2015/0103073 A1
- Document ID: US20150103073A1
- Status: Published application
- Kind: A1
- Application number: 14/372,922
- Filed: 2012-02-09
- Published: 2015-04-16
- Earliest claimed: 2012-02-09
- Assignees: Thomson Licensing
- Inventors: Jiang Tian; Wenfei Jiang; Kangying Cai
- Web page: https://patentgrep.com/patent/US20150103073A1

## CPC

- G06T 17/005: {Tree description, e.g. octree, quadtree}
- G06T 9/001: {Model-based coding, e.g. wire frame}
- G06T 9/40: Tree coding, e.g. quadtree, octree
- G06T 15/04: Texture mapping
- H04N 19/129: Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO]
- H04N 19/134: characterised by the element, parameter or criterion affecting or controlling the adaptive coding
- H04N 19/91: Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
- H04N 19/96: Tree coding, e.g. quad-tree coding
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

To reduce the entropy of occupancy codes of an octree and improve compression efficiency, the present principles provide a method and an apparatus for traversing sub-cells in a cell according to the geometrical property of 3D models. That is, a surface smoothness measure is calculated for each sub-cell and the sub-cells are traversed in a pre-determined order of surface smoothness measures. To compute the surface smoothness measure, a sub-cell is connected to neighboring cells of its parent cell to form triangles and angles. Subsequently, the triangle areas or angular measures are used to compute the surface smoothness measure. When the connectivity information is not available in the 3D model data, the present principles also provide a method and an apparatus for estimating the connectivity.

## Claims

### Claim 1

A method for generating or decoding a bitstream representing a 3D model, comprising the steps of:
determining a surface smoothness measure for each one of a plurality of sub-cells of a cell in an octree, the octree being representative of the 3D model; and
determining a traversal order of the sub-cells of the cell in response to the surface smoothness measures of the sub-cells.

### Claim 2 (depends on 1)

The method of claim 1, wherein the traversal order corresponds to an ascending or descending order of the surface smoothness measures.

### Claim 3 (depends on 1)

The method of claim 1, wherein the step of determining the surface smoothness measure comprises, for a particular sub-cell of the cell:
forming a plurality of triangles in response to the particular sub-cell and neighboring cells of the cell, wherein each one of the triangles is defined by a point representative of the particular sub-cell and two points representative of two cells of the neighboring cells;
determining an area for the each one of the triangles; and
determining the surface smoothness measure for the particular sub-cell in response to the areas of the plurality of triangles.

### Claim 4 (depends on 3)

The method of claim 3, wherein the surface smoothness measure is determined to be a sum of the areas.

### Claim 5 (depends on 1)

The method of claim 1, wherein the step of determining the surface smoothness measure comprises, for a particular sub-cell of the cell:
forming a plurality of angles in response to the particular sub-cell and neighboring cells of the cell, wherein each one of the angles is defined by a point representative of the particular sub-cell and two points representative of two cells of the neighboring cells, the point representative of the particular sub-cell corresponding to a vertex of the each one of the angles; determining the surface smoothness measure for the particular sub-cell in response to the angular measures of the plurality of angles.
determining an angular measure for the each one of the angle; and
determining the surface smoothness measure for the particular sub-cell in response to the angular measures of the plurality of angles.

### Claim 6 (depends on 5)

The method of claim 5, wherein the surface smoothness measure is determined to be a sum of the angular measures.

### Claim at position 7

-8. (canceled)

### Claim 9 (depends on 1)

The method of claim 1, further comprising the steps of:
determining a plurality of cells as the neighboring cells;
determining a sorted order of the neighboring cells, wherein the two cells of the neighboring cells are adjacent to each order in the sorted order; and
connecting the two cells of the neighboring cells.

### Claim 10 (depends on 9)

The method of claim 9, wherein the step of determining the sorted order comprises the steps of:
determining a projection direction in response to the cell and the neighboring cells;
projecting the cell and the neighboring cells to a 2D plane; and
sorting the neighboring cells in a counter-clockwise or a clockwise order around the cell in the 2D plane.

### Claim 11 (depends on 10)

The method of claim 10, wherein the step of determining the projection direction comprises the steps of:
forming a plurality of vectors, each one of the plurality of vectors is defined by the cell and one cell of the neighboring cells
determining a set of absolute inner products for each axis of three coordinate axes, wherein each absolute inner product in the set of absolute inner products is formed between a corresponding coordinate axis and a respective one of the plurality of vectors;
determining a minimum absolute inner product for the set of absolute inner products; and
determining a coordinate axis as the projection direction, wherein the coordinate axis corresponds to a maximum of the three minimum absolute inner products for the three sets of absolute inner products.

### Claim 12 (depends on 1)

The method of claim 1, further comprising:
determining a bit for the each one of the sub-cells, wherein the bit indicates whether a corresponding sub-cell is empty;
forming a bit string using the determined bits for the sub-cells in response to the traversal order; and
entropy coding the bit string into the bitstream.

### Claim 13 (depends on 1)

The method of claim 1, further comprising:
decoding a bit string from the bitstream; and
determining a bit for a corresponding sub-cell in response to the traversal order, wherein the bit indicates whether the corresponding sub-cell is empty.

### Claim 14

An apparatus for generating or decoding a bitstream representing a 3D model, comprising:
means for determining a surface smoothness measure for each one of a plurality of sub-cells of a cell in an octree, the octree being representative of the 3D model; and
means for determining a traversal order of the sub-cells of the cell in response to the surface smoothness measures of the sub-cells.

### Claim 15 (depends on 14)

The apparatus of claim 14, wherein the traversal order corresponds to an ascending or descending order of the surface smoothness measures.

### Claim 16 (depends on 14)

The apparatus of claim 14, wherein the means for determining the surface smoothness measure comprises, for a particular sub-cell of the cell:
means for forming a plurality of triangles in response to the particular sub-cell and neighboring cells of the cell, wherein each one of the triangles is defined by a point representative of the particular sub-cell and two points representative of two cells of the neighboring cells;
means for determining an area for the each one of the triangles; and
means for determining the surface smoothness measure for the particular sub-cell in response to the areas of the plurality of triangles.

### Claim 17 (depends on 16)

The apparatus of claim 16, wherein the surface smoothness measure is determined to be a sum of the areas.

### Claim 18 (depends on 14)

The apparatus of claim 14, wherein the means for determining the surface smoothness measure comprises, for a particular sub-cell of the cell:
means for forming a plurality of angles in response to the particular sub-cell and neighboring cells of the cell, wherein each one of the angles is defined by a point representative of the particular sub-cell and two points representative of two cells of the neighboring cells, the point representative of the particular sub-cell corresponding to a vertex of the each one of the angles;
means for determining an angular measure for the each one of the angle; and
means for determining the surface smoothness measure for the particular sub-cell in response to the angular measures of the plurality of angles.

### Claim 19 (depends on 18)

The apparatus of claim 18, wherein the surface smoothness measure is determined to be a sum of the angular measures.

### Claim 20 (depends on 14, 16, 18)

The apparatus of claim 14, wherein the means for of determining the surface smoothness measure is selected from one of the apparatus of claims 16 and 18, in response to a magnitude of the surface smoothness measure.

### Claim at position 20

-22. (canceled)

### Claim 23 (depends on 14)

The apparatus of claim 14, wherein the means for determining the sorted order comprises:
means for determining a projection direction in response to the cell and the neighboring cells;
means for projecting the cell and the neighboring cells to a 2D plane; and
means for sorting the neighboring cells in a counter-clockwise or clockwise order around the cell in the 2D plane.

### Claim 24 (depends on 23)

The apparatus of claim 23, wherein the means for determining the projection direction comprises:
means for forming a plurality of vectors, each one of the plurality of vectors is defined by the cell and one cell of the neighboring cells;
means for determining a set of absolute inner products for each axis of three coordinate axes, wherein each absolute inner product in the set of absolute inner products is formed between a corresponding coordinate axis and a respective one of the plurality of vectors;
means for determining a minimum absolute inner product for the set of absolute inner products; and
means for determining a coordinate axis as the projection direction, wherein the coordinate axis corresponds to a maximum of the three minimum absolute inner products for the three sets of absolute inner products.

### Claim 25 (depends on 14)

The apparatus of claim 14, further comprising:
means for determining a bit for the each one of the sub-cells, wherein the bit indicates whether a corresponding sub-cell is empty;
means for forming a bit string using the determined bits for the sub-cells in response to the traversal order; and
means for coding the bit string into the bitstream.

### Claim 26 (depends on 14)

The apparatus of claim 14, further comprising:
means for decoding a bit string from the bitstream; and
means for determining a bit for a corresponding sub-cell in response to the traversal order, wherein the bit indicates whether the corresponding sub-cell is empty.

### Claim at position 25

27-28. (canceled)
