# US 11,029,665 B2 · Density rank matrix generation for three-dimensional printing

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

- Number: US 11,029,665 B2
- Document ID: US11029665B2
- Status: Granted
- Kind: B2
- Application number: 16/072,270
- Filed: 2016-04-29
- Published: 2019-01-31
- Granted: 2021-06-08
- Earliest claimed: 2016-04-29
- Assignees: Hewlett-Packard Development Company, L.P.
- Applicants: Hewlett-Packard Development Company, L.P.
- Inventors: Robert Ulichney
- Web page: https://patentgrep.com/patent/US11029665B2

## CPC

- G05B 19/4099: Surface or curve machining, making three-dimensional [3D] objects, e.g. desktop manufacturing
- B29C 64/10: Processes of additive manufacturing
- B29C 64/386: Data acquisition or data processing for additive manufacturing
- B33Y 10/00: Processes of additive manufacturing
- B33Y 50/00: Data acquisition or data processing for additive manufacturing
- G06F 7/00: Methods or arrangements for processing data by operating upon the order or content of the data handled (logic circuits H03K19/00)
- H04N 1/405: Halftoning, i.e. converting the picture signal of a continuous-tone original into a corresponding signal showing only two levels
- G05B 2219/49007: Making, forming 3-D object, model, surface
- G05B: CONTROL OR REGULATING SYSTEMS IN GENERAL; FUNCTIONAL ELEMENTS OF SUCH SYSTEMS; MONITORING OR TESTING ARRANGEMENTS FOR SUCH SYSTEMS OR ELEMENTS (systems for controlling or regulating non-electric variables G05D; systems for regulating electric or magnetic variables G05F; control devices or systems insofar as characterised by mechanical features only G05G)
- B29C: SHAPING OR JOINING OF PLASTICS; SHAPING OF MATERIAL IN A PLASTIC STATE, NOT OTHERWISE PROVIDED FOR; AFTER-TREATMENT OF THE SHAPED PRODUCTS, e.g. REPAIRING (making preforms B29B11/00; making laminated products by combining previously unconnected layers which become one product whose layers will remain together B32B37/00 - B32B41/00)
- B33Y: ADDITIVE MANUFACTURING, i.e. MANUFACTURING OF THREE-DIMENSIONAL [3D] OBJECTS BY ADDITIVE DEPOSITION, ADDITIVE AGGLOMERATION OR ADDITIVE LAYERING, e.g. BY 3D PRINTING, STEREOLITHOGRAPHY OR SELECTIVE LASER SINTERING
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

According to an example, density rank matrix generation for three-dimensional printing may include determining dimensions of a density rank matrix based on a skeleton line specification of a lattice structure and a density rank matrix size specification. A number of elements of the density rank matrix may be determined based on the dimensions of the density rank matrix. The elements may be sorted based on an analysis of a property of each of the elements relative to the lattice structure. The density rank matrix may be generated based on the sorting of the elements.

## Claims

### Claim 1

A method for density rank matrix generation for three-dimensional printing, the method comprising:
determining, based on a skeleton line specification of a lattice structure and a density rank matrix size specification, dimensions of a density rank matrix, the density rank matrix including a minimum distance for each element of the density rank matrix to a line of a line skeleton of the lattice structure;
determining, based on the dimensions of the density rank matrix, a number of elements of the density rank matrix;
sorting, by a processor, the elements based on an analysis of a property of each of the elements relative to the lattice structure; and
generating, based on the sorting of the elements, the density rank matrix.

### Claim 2 (depends on 1)

The method according to claim 1, further comprising:
normalizing the density rank matrix to generate a density threshold matrix;
receiving specifications of a three-dimensional input object; and
comparing each of the specifications of the three-dimensional input object to a corresponding threshold value in the density threshold matrix to determine whether to generate a voxel.

### Claim 3 (depends on 2)

The method according to claim 2, wherein comparing each of the specifications of the three-dimensional input object to the corresponding threshold value in the density threshold matrix to determine whether to generate the voxel further comprises:
applying a modulo operation to each threshold value in the density threshold matrix;
determining whether a specification of a three-dimensional input object is greater than a corresponding modulo based threshold value, wherein the corresponding modulo based threshold value represents a threshold value to which the modulo operation is applied;
in response to a determination that the specification of the three-dimensional input object is greater than the corresponding modulo based threshold value, indicating generation of the voxel; and
in response to a determination that the specification of the three-dimensional input object is less than or equal to the corresponding modulo based threshold value, indicating not to generate the voxel.

### Claim 4 (depends on 1)

The method according to claim 1, wherein the lattice structure includes a tetrahedral-octahedral lattice structure.

### Claim 5 (depends on 4)

The method according to claim 4, wherein the tetrahedral-octahedral lattice structure includes a repeating period including a dimensional ratio of 1, 1, and √2, respectively, relative to first, second, and third axis of the line skeleton of the tetrahedral-octahedral lattice.

### Claim 6 (depends on 1)

The method according to claim 1, wherein determining, based on the skeleton line specification and the density rank matrix size specification, dimensions of the density rank matrix further comprises:
determining a dimension of the density rank matrix along a first axis; and
determining the dimensions of the density rank matrix along second and third axes as a function of a period size of the lattice structure and a voxel aspect ratio of a printer that is to generate an output object based on the density rank matrix.

### Claim 7 (depends on 6)

The method according to claim 6, further comprising:
determining, based on the skeleton line specification, a unit skeleton line set as a list of lines defined by two end points; and
scaling the unit skeleton line set by multiplying values of the unit skeleton line set with corresponding dimensions of the density rank matrix along the first, second, and third axes.

### Claim 8 (depends on 1)

The method according to claim 1, wherein determining, based on the dimensions of the density rank matrix, the number of elements of the density rank matrix further comprises:
multiplying the dimensions of the density rank matrix along first, second, and third axes to determine the number of elements of the density rank matrix.

### Claim 9 (depends on 1)

The method according to claim 1, wherein sorting the elements based on the analysis of the property of each of the elements relative to the lattice structure further comprises:
determining, for each of the elements, distances of each element from each specified line of the line skeleton of the lattice structure;
determining, from the distances, the minimum distance for each of the elements;
sorting the elements according to corresponding minimum distances defined by the minimum distance for each of the elements; and
replacing each of the elements with a rank value that corresponds to an order of the sorting of the elements.

### Claim 10 (depends on 1)

The method according to claim 1, further comprising:
determining an unassigned element of the density rank matrix; and
for each unassigned element of the density rank matrix, assigning a minimum distance associated with the unassigned point to the unassigned element.

### Claim 11

An apparatus for density rank matrix generation for three-dimensional printing comprising:
a processor; and
a memory storing machine readable instructions that when executed by the processor cause the processor to:
determine a dimension of a density rank matrix along a first axis, the density rank matrix including a minimum distance for each element of the density rank matrix to a line of a line skeleton of a lattice structure;
determine dimensions of the density rank matrix along second and third axes as a function of a period size of the lattice structure that is to be used to generate an output object and a voxel aspect ratio of a printer that is to be used to generate the output object based on the density rank matrix;
determine, based on all of the dimensions of the density rank matrix, a number of elements of the density rank matrix;
sort the elements based on an analysis of a property of each of the elements relative to the lattice structure; and
generate, based on the sorting of the elements, the density rank matrix.

### Claim 12 (depends on 11)

The apparatus for density rank matrix generation for three-dimensional printing according to claim 11, further comprising machine readable instructions that when executed by the processor further cause the processor to:
determine, based on a skeleton line specification of the lattice structure, a unit skeleton line set as a list of lines defined by two end points; and
scale the unit skeleton line set by multiplying values of the unit skeleton line set with corresponding dimensions of the density rank matrix along the first, second, and third axes.

### Claim 13 (depends on 11)

The apparatus for density rank matrix generation for three-dimensional printing according to claim 11, wherein the lattice structure includes a tetrahedral-octahedral lattice structure.

### Claim 14 (depends on 11)

The apparatus for density rank matrix generation for three-dimensional printing according to claim 11, further comprising machine readable instructions that when executed by the processor further cause the processor to:
determine, for each of the elements, distances of each element from each specified line of the line skeleton of the structure;
determine, from the distances, the minimum distance for each of the elements;
sort the elements according to corresponding minimum distances defined by the minimum distance for each of the elements; and
replace each of the elements with a rank value that corresponds to an order of the sorting of the elements.

### Claim 15 (depends on 11)

The apparatus for density rank matrix generation for three-dimensional printing according to claim 11, further comprising machine readable instructions that when executed by the processor further cause the processor to:
determine an unassigned element of the density rank matrix; and
for each unassigned element of the density rank matrix, assign a minimum distance associated with the unassigned point to the unassigned element.

### Claim 16

A non-transitory computer readable medium having stored thereon machine readable instructions to provide density rank matrix generation for three-dimensional printing, the machine readable instructions, when executed, cause a processor to:
determine, based on a skeleton line specification of a structure that is to be used to generate an output object and a density rank matrix size specification, dimensions of a density rank matrix, the density rank matrix including a minimum distance for each element of the density rank matrix to a line of a line skeleton of the structure;
determine, based on the dimensions of the density rank matrix, a number of elements of the density rank matrix by multiplying the dimensions of the density rank matrix along first, second, and third axes to determine the number of elements of the density rank matrix;
sort the elements based on an analysis of a property of each of the elements relative to the structure; and
generate, based on the sorting of the elements, the density rank matrix.

### Claim 17 (depends on 16)

The non-transitory computer readable medium according to claim 16, wherein the structure includes a tetrahedral-octahedral lattice structure.

### Claim 18 (depends on 16)

The non-transitory computer readable medium according to claim 16, wherein the machine readable instructions to sort the elements based on the analysis of the property of each of the elements relative to the structure, further comprise machine readable instructions to:
determine, for each of the elements, distances of each element from each specified line of the line skeleton of the structure;
determine, from the distances, the minimum distance for each of the elements;
sort the elements according to corresponding minimum distances defined by the minimum distance for each of the elements; and
replace each of the elements with a rank value that corresponds to an order of the sorting of the elements.

### Claim 19 (depends on 16)

The non-transitory computer readable medium according to claim 16, wherein the machine readable instructions to sort the elements based on the analysis of the property of each of the elements relative to the structure, further comprise machine readable instructions to:
determine an unassigned element of the density rank matrix; and
for each unassigned element of the density rank matrix, assign a minimum distance associated with the unassigned point to the unassigned element.