# US 2019/0378307 A1 · Grid Retaining Irregular Network in 3D

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

- Number: US 2019/0378307 A1
- Document ID: US20190378307A1
- Status: Published application
- Kind: A1
- Application number: 16/402,765
- Filed: 2019-05-03
- Published: 2019-12-12
- Earliest claimed: 2018-05-03
- Assignees: The Government of the United States of America, as represented by the Secretary of the Navy
- Applicants: The Government of the United States of America, as represented by the Secretary of the Navy
- Inventors: David Marks; Brian S. Bourgeois
- Web page: https://patentgrep.com/patent/US20190378307A1

## CPC

- G06T 9/001: {Model-based coding, e.g. wire frame}
- G06T 17/20: Finite element generation, e.g. wire-frame surface description, {tesselation}
- H03M 7/30: Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M 7/70: {Type of the data to be coded, other than image and sound}
- H03M 7/3059: {Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression}
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

Systems and methods are provided for compression of 3 dimensional (3D) geophysical (e.g., air temp, water temp, wind, current, humidity, salinity, etc.) datasets that contain regions of NaNs (IEEE standard representation for Not a Number) that represent land, i.e. geographic positions that do not have valid data. Embodiments of the present disclosure allow constraint of the error magnitude by a user specified threshold, where compression and error are inherent tradeoffs.

## Claims

### Claim 1

A method for compressing data, the method comprising:
forming, using a compressor device, a mesh based on the data, wherein the mesh comprises a plurality of triangles;
tessellating, using the compressor device, the plurality of triangles to form a right-triangulated irregular network (RTIN) structure being capable of being fully reduced to two triangles, the RTIN structure including a plurality of points and a plurality of edges;
compressing, using the compressor device, the data using the RTIN structure;
producing, using a compressor device, a unique index number for every point within the RTIN structure;
determining, using the compressor device, whether a difference between each point in the RTIN structure and a corresponding point in the data exceeds an error threshold; and
for each point in the RTIN structure, if the difference between the point and the corresponding point in the original data set exceeds the error threshold, record the computed index value of the point in the RTIN structure and the value of that point in the data in a keep list.

### Claim 2 (depends on 1)

The method of claim 1, wherein the mesh is a Delaunay mesh.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
receiving a query for a value of queried a point in the RTIN structure;
determining whether an index value of the queried point is in the keep list; and
returning a keep list value of the queried point in the keep list if the index value of the queried point is in the keep list.

### Claim 5 (depends on 4)

The method of claim 4, further comprising:
returning a value of the queried point in the RTIN structure if the index value of the queried point is in not the keep list.

### Claim 6 (depends on 1)

The method of claim 1, wherein compressing the data further comprises:
(a) incrementing an iteration number;
(b) selecting a first subset of points from the plurality of points based on angles that edges of the plurality of edges form with the each of the plurality of points;
(c) for each of the points in the first subset, selecting one of the plurality of edges for deletion evaluation based on the iteration number and the selected point, the selected edge having an opposing edge of opposite orientation from the selected edge;
(d) locating a second subset of the plurality of points, the second subset including the points of the plurality of points along the selected edge;
(e) for each of the points in the first subset, removing the selected point and the opposing edge if the points of the second subset meet the pre-selected criteria;
(f) for each of the points in the first subset not removed in (e), marking the not-removed points as not available to be selected in (b); and
(g) repeating (a) through (f) until no points are found in (b).

### Claim 7 (depends on 6)

The method of claim 6, further comprising:
prior to removing the selected point:
determining a first resulting interpolated length along an axis that will remain after the selected point is deleted,
determining whether a first difference between the first resulting interpolated length and a first corresponding length in the mesh exceeds the error threshold,
determining a second resulting interpolated length along an axis that will be removed after the selected point is deleted,
determining whether a second difference between the second resulting interpolated length and a second corresponding length in the mesh exceeds the error threshold, and
removing the point if neither the first difference nor the second difference exceeds the error threshold.

### Claim 8 (depends on 7)

The method of claim 7, further comprising:
determining that the point should not be removed if the first difference or the second difference exceeds the error threshold.

### Claim 9 (depends on 6)

The method of claim 6, further comprising:
if the selected point is not removed in (e):
determining whether each point adjacent to the selected point corresponds to a not a number (NaN) value, and
removing the selected point if each point adjacent to the selected point corresponds to a not a number (NaN) value and the selected point corresponds to a NaN value.

### Claim 10 (depends on 1)

The method of claim 1, further comprising:
replacing not a number (NaN) values in the data with a mean value for a row containing the NaN value.

### Claim 12 (depends on 1)

The method of claim 1, further comprising:
replacing not a number (NaN) values in the data with a mean value for a layer containing the NaN value.

### Claim 13

A device for compressing data, the device comprising:
a memory storing data to be compressed; and
a compressor device configured to:
form a mesh based on the data, wherein the mesh comprises a plurality of triangles,
tessellate the plurality of triangles to form a right-triangulated irregular network (RTIN) structure being capable of being fully reduced to two triangles, the RTIN structure including a plurality of points and a plurality of edges,
compress the data using the RTIN structure,
produce a unique index number for every point within the RTIN structure,
determine whether a difference between each point in the RTIN structure and a corresponding point in the data exceeds an error threshold, and
for each point in the RTIN structure, if the difference between the point and the corresponding point in the original data set exceeds the error threshold, record the computed index value of the point in the RTIN structure and the value of that point in the data in a keep list.

### Claim 14 (depends on 1)

The device of claim 1, wherein the compressor device is further configured to:
receive a query for a value of queried a point in the RTIN structure;
determine whether an index value of the queried point is in the keep list; and
return a keep list value of the queried point in the keep list if the index value of the queried point is in the keep list.

### Claim 15 (depends on 1)

The device of claim 1, wherein the compressor device is further configured to:
(a) increment an iteration number;
(b) select a first subset of points from the plurality of points based on angles that edges of the plurality of edges form with the each of the plurality of points;
(c) for each of the points in the first subset, select one of the plurality of edges for deletion evaluation based on the iteration number and the selected point, the selected edge having an opposing edge of opposite orientation from the selected edge;
(d) locate a second subset of the plurality of points, the second subset including the points of the plurality of points along the selected edge;
(e) for each of the points in the first subset, remove the selected point and the opposing edge if the points of the second subset meet the pre-selected criteria;
(f) for each of the points in the first subset not removed in (e), mark the not-removed points as not available to be selected in (b); and
(g) repeat (a) through (f) until no points are found in (b).

### Claim 16 (depends on 15)

The device of claim 15, wherein the compressor device is further configured to:
prior to removing the selected point:
determine a first resulting interpolated length along an axis that will remain after the selected point is deleted,
determine whether a first difference between the first resulting interpolated length and a first corresponding length in the mesh exceeds the error threshold,
determine a second resulting interpolated length along an axis that will be removed after the selected point is deleted,
determine whether a second difference between the second resulting interpolated length and a second corresponding length in the mesh exceeds the error threshold, and
remove the point if neither the first difference nor the second difference exceeds the error threshold.

### Claim 17 (depends on 16)

The device of claim 16, wherein the compressor device is further configured to:
determine that the point should not be removed if the first difference or the second difference exceeds the error threshold.

### Claim 18 (depends on 15)

The device of claim 15, wherein the compressor device is further configured to:
if the selected point is not removed in (e):
determine whether each point adjacent to the selected point corresponds to a not a number (NaN) value, and
remove the selected point if each point adjacent to the selected point corresponds to a not a number (NaN) value and the selected point corresponds to a NaN value.

### Claim 19 (depends on 1)

The device of claim 1, wherein the compressor device is further configured to:
replace not a number (NaN) values in the data with a mean value for a row containing the NaN value.

### Claim 20 (depends on 1)

The device of claim 1, wherein the compressor device is further configured to:
replace not a number (NaN) values in the data with a mean value for a layer containing the NaN value.
