# US 2021/0191360 A1 · Techniques for determining fabricability of designs by searching for forbidden patterns

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

- Number: US 2021/0191360 A1
- Document ID: US20210191360A1
- Status: Published application
- Kind: A1
- Application number: 16/721,589
- Filed: 2019-12-19
- Published: 2021-06-24
- Earliest claimed: 2019-12-19
- Assignees: X Development LLC
- Applicants: X Development LLC
- Inventors: Albin Lee Jones
- Web page: https://patentgrep.com/patent/US20210191360A1

## CPC

- G05B 19/4093: characterised by part programming, e.g. entry of geometrical information as taken from a technical drawing, combining this with machining and material information to obtain control information, named part program, for the NC machine
- G05B 19/4099: Surface or curve machining, making three-dimensional [3D] objects, e.g. desktop manufacturing
- B29C 64/386: Data acquisition or data processing for additive manufacturing
- B33Y 50/00: Data acquisition or data processing for additive manufacturing
- G06F 17/141: {Discrete Fourier transforms}
- G06F 30/20: Design optimisation, verification or simulation (optimisation, verification or simulation of circuit designs G06F30/30)
- G06F 30/30: Circuit design
- G05B 2219/35134: 3-D cad-cam
- G05B 2219/35305: Before machining, verify if all different machining start points are correct
- G05B 2219/49007: Making, forming 3-D object, model, surface
- Y02P 90/02: Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]
- 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)
- Y02P: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN THE PRODUCTION OR PROCESSING OF GOODS

## Abstract

In some embodiments, techniques are provided for verifying that a fabrication system can fabricate a proposed segmented design. A paintbrush pattern that represents capabilities of the fabrication system is determined. One or more forbidden patterns that the fabrication system is not capable of fabricating are determined based on the paintbrush pattern. The proposed segmented design is then searched for the forbidden patterns. If any forbidden patterns are found, the proposed segmented design is determined to not be fabricable by the fabrication system. If no forbidden patterns are found, then the proposed segmented design is determined to be fabricable by the fabrication system.

## Claims

### Claim 1

A method of verifying fabricability of a segmented design for a physical device to be fabricated by a fabrication system, the method comprising:
receiving a proposed segmented design;
searching the proposed segmented design for forbidden patterns of a set of forbidden patterns, wherein each forbidden pattern indicates a pattern of segments that is not fabricable by the fabrication system; and
determining the fabricability of the proposed segmented design based on results of the searching for the forbidden patterns.

### Claim 2 (depends on 1)

The method of claim 1, wherein the proposed segmented design is a two-dimensional design segmented into pixels, or a three-dimensional design segmented into voxels.

### Claim 3 (depends on 1)

The method of claim 1, further comprising determining the set of forbidden patterns based on capabilities of the fabrication system.

### Claim 4 (depends on 3)

The method of claim 3, wherein the capabilities include at least one of a minimum feature size and a minimum feature shape.

### Claim 5 (depends on 3)

The method of claim 3, wherein determining the set of forbidden patterns based on the capabilities of the fabrication system includes:
determining a first forbidden pattern based on the capabilities of the fabrication system;
adding the first forbidden pattern to the set of forbidden patterns;
determining a set of translated patterns by at least rotating and flipping the first forbidden pattern; and
adding the set of translated patterns to the set of forbidden patterns.

### Claim 6 (depends on 1)

The method of claim 1, wherein searching the proposed segmented design for forbidden patterns for the set of forbidden patterns includes, for each forbidden pattern in the set of forbidden patterns, computing a cross-correlation between the forbidden pattern and the proposed segmented design.

### Claim 7 (depends on 1)

The method of claim 1, wherein searching the proposed segmented design for forbidden patterns for the set of forbidden patterns includes, for each forbidden pattern in the set of forbidden patterns:
determining a discrete Fourier transform of the proposed segmented design;
pre-computing a discrete Fourier transform of the forbidden pattern; and
calculating an inverse discrete Fourier transform of the result to detect the forbidden patterns.

### Claim 8 (depends on 7)

The method of claim 7, wherein the discrete Fourier transform is a number theoretic transform.

### Claim 9 (depends on 1)

The method of claim 1, further comprising, in response to determining that the proposed segmented design is fabricable, providing the segmented design to the fabrication system to manufacture the physical device.

### Claim 10 (depends on 9)

The method of claim 9, wherein providing the segmented design to the fabrication system to manufacture the physical device includes providing the segmented design to a photolithography system.

### Claim 11

A non-transitory computer-readable storage medium having instructions stored thereon that, in response to execution by one or more processors of a computing system, cause the computing system to perform actions for verifying fabricability of a segmented design for a physical device to be fabricated by a fabrication system, the actions comprising:
receiving a proposed segmented design;
searching the proposed segmented design for forbidden patterns of a set of forbidden patterns, wherein each forbidden pattern indicates a pattern of segments that is not fabricable by a fabrication system; and
determining the fabricability of the proposed segmented design based on results of the searching for the forbidden patterns.

### Claim 12 (depends on 11)

The computer-readable storage medium of claim 11, wherein the proposed segmented design is a two-dimensional design segmented into pixels, or a three-dimensional design segmented into voxels.

### Claim 13 (depends on 11)

The computer-readable storage medium of claim 11, wherein the actions further comprise determining the set of forbidden patterns based on capabilities of the fabrication system.

### Claim 14 (depends on 13)

The computer-readable storage medium of claim 13, wherein the capabilities include at least one of a minimum feature size and a minimum feature shape.

### Claim 15 (depends on 13)

The computer-readable storage medium of claim 13, wherein determining the set of forbidden patterns based on the capabilities of the fabrication system includes:
determining a first forbidden pattern based on the capabilities of the fabrication system;
adding the first forbidden pattern to the set of forbidden patterns;
determining a set of translated patterns by at least rotating and flipping the first forbidden pattern; and
adding the set of translated patterns to the set of forbidden patterns.

### Claim 16 (depends on 11)

The computer-readable storage medium of claim 11, wherein searching the proposed segmented design for forbidden patterns for the set of forbidden patterns includes, for each forbidden pattern in the set of forbidden patterns, computing a cross-correlation between the forbidden pattern and the proposed segmented design.

### Claim 17 (depends on 11)

The computer-readable storage medium of claim 11, wherein searching the proposed segmented design for forbidden patterns for the set of forbidden patterns includes, for each forbidden pattern in the set of forbidden patterns:
determining a discrete Fourier transform of the proposed segmented design;
pre-computing a discrete Fourier transform of the forbidden pattern; and
calculating an inverse discrete Fourier transform of the result to detect the forbidden patterns.

### Claim 18 (depends on 17)

The computer-readable storage medium of claim 17, wherein the discrete Fourier transform is a number theoretic transform.

### Claim 19 (depends on 11)

The computer-readable storage medium of claim 11, wherein the actions further comprise, in response to determining that the proposed segmented design is fabricable, providing the segmented design to the fabrication system to manufacture the physical device.

### Claim 20 (depends on 19)

The computer-readable storage medium of claim 19, wherein providing the segmented design to the fabrication system to manufacture the physical device includes providing the segmented design to a photolithography system.
