# US 11,897,203 B1 · Frequency domain spatial packing for 3D fabrication > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,897,203 B1 - Document ID: US11897203B1 - Status: Granted - Kind: B1 - Application number: 17/955,843 - Filed: 2022-09-29 - Granted: 2024-02-13 - Earliest claimed: 2022-09-29 - Assignees: Inkbit, LLC - Applicants: Inkbit, LLC - Inventors: Qiaodong Cui; Wojciech Matusik; Victor Rong - Web page: https://patentgrep.com/patent/US11897203B1 ## CPC - B29C 64/393: for controlling or regulating additive manufacturing processes - G06F 30/20: Design optimisation, verification or simulation (optimisation, verification or simulation of circuit designs G06F30/30) - B29C 64/171: specially adapted for manufacturing multiple 3D objects - B29C 64/386: Data acquisition or data processing for additive manufacturing - B33Y 50/00: Data acquisition or data processing for additive manufacturing - B33Y 50/02: for controlling or regulating additive manufacturing processes - G06F 2113/10: Additive manufacturing, e.g. three-dimensional [3D] printing - 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) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - 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 ## Abstract Arrangement of the parts, particularly addressing arrangement for 3D fabrication, makes use of spatial frequency domain representations of the parts, such that acceptable (or optionally desirable) relative locations (and optionally orientations) of a part relative to another part or an arrangement of multiple other parts makes use of spatial frequency domain representations of the parts. In some examples, acceptable relative locations may be defined as relative locations that do not result in parts spatially overlapping and/or maintain a desired (e.g., minimum, average, etc.) separation between parts. ## Claims ### Claim 1 A method for arranging a plurality of parts into a build volume for three-dimensional fabrication, the method comprising: receiving a specification of a shape for each part of a plurality of parts; arranging the parts in a build volume, including for at least a first part of the plurality of parts arranging the first part relative to an arrangement including one or more previously arranged parts of the plurality of parts; using a first spatial frequency domain representation of the shape of the first part determined from the first part and using a second spatial frequency domain representation of the arrangement; determining a location of the first part relative to the arrangement; and adding the first part to the arrangement at the determined location; forming a build volume specification for three-dimensional fabrication according to the arrangement; and providing the build volume specification for use in a three-dimensional fabrication system. ### Claim 2 (depends on 1) The method of claim 1, wherein the specification of the shape comprises a voxel representation of locations occupied in the shape. ### Claim 3 (depends on 1) The method of claim 1, further comprising determining spatial frequency domain representations of shapes of at least some parts of the plurality of parts. ### Claim 4 (depends on 1) The method of claim 1, wherein determining the location of the first part relative to the arrangement includes processing the first spatial frequency domain representation and the second spatial frequency domain representation to yield a third spatial frequency domain representation, and processing the third spatial frequency domain representation to yield third spatial representation. ### Claim 5 (depends on 4) The method of claim 4, wherein determining the location of the first part relative to the arrangement further includes processing the third spatial domain representation including searching the third spatial representation for the location. ### Claim 6 A method for arranging a plurality of parts into a build volume for three-dimensional fabrication, the method comprising: receiving a specification of a shape for each part of a plurality of parts; arranging the parts in a build volume, including for at least a first part of the plurality of parts arranging the first part relative to an arrangement including one or more previously arranged parts of the plurality of parts; using a first spatial frequency representation of the shape of the first part determined from the first part and using a second spatial frequency representation of the arrangement, determining a location of the first part relative to the arrangement; and adding the first part to the arrangement at the determined location; forming a build volume specification for three-dimensional fabrication according to the arrangement; and providing the specification of the build volume for use in a three-dimensional fabrication system, wherein using a first spatial frequency representation of the shape of the first part comprises a Fourier Transform of a volume occupied by the first part. ### Claim 7 (depends on 1) The method of claim 1, wherein using the second spatial frequency domain representation of the arrangement comprises a Fourier Transform of a preference distribution at a set of possible offsets of the first part relative to the arrangement. ### Claim 8 (depends on 7) The method of claim 7, wherein the preference distribution represents one or more of (a) a preference for placement of the first part in proximity to the arrangement, (b) a preference to reduce support volume for supporting the first part and the arrangement, and (c) a preference of reduced overall height of the first part and the arrangement within the build volume. ### Claim 9 (depends on 1) The method of claim 1, wherein using the first spatial frequency domain representation of the shape of the first part determined from the first part and the second spatial frequency domain representation of the arrangement includes determining a third spatial frequency domain representation over a set of possible offsets of the first part relative to the arrangement. ### Claim 10 (depends on 9) The method of claim 9, wherein using the first spatial frequency domain representation of the shape of the first part determined from the first part and the second spatial frequency domain representation of the arrangement further includes determining a spatial distribution over a set of possible offsets of the first part relative to the arrangement. ### Claim 11 (depends on 10) The method of claim 10, wherein determining a spatial distribution over a set of possible offsets of the first part relative to the arrangement includes determining an inverse Fourier Transform of the third spatial frequency domain distribution. ### Claim 12 (depends on 1) The method of claim 1, wherein for at least the first part of the plurality of parts, using a plurality of rotations of the first part to determine a rotation of said first part for adding to the arrangement. ### Claim 13 (depends on 12) The method of claim 12, further comprising determining a spatial frequency domain representation of the first part in each of the plurality of rotations. ### Claim 14 (depends on 1) The method of claim 1, wherein for at least one part of the plurality of parts, the spatial frequency domain representation of the arrangement represents a build volume without any parts yet placed within it. ### Claim 15 (depends on 1) The method of claim 1, wherein the specification of the shape comprises a voxel representation of locations occupied in the shape; wherein determining the location of the first part relative to the arrangement includes processing the first spatial frequency domain representation and the second spatial frequency domain representation to yield a third spatial frequency domain representation, and processing the third spatial frequency domain representation to yield a third spatial representation; wherein using a first spatial frequency domain representation of the shape of the first part comprises a Fourier Transform of a volume occupied by the first part; and wherein using the second spatial frequency domain representation of the arrangement comprises a Fourier Transform of a preference distribution at a set of possible offsets of the first part relative to the arrangement. ### Claim 16 A system for arranging a plurality of parts into a build volume for three-dimensional fabrication, the system comprising one or more hardware processors, and a storage for instructions for execution by said one or more hardware processors that when executed cause the system to: receive a specification of a shape for each part of a plurality of parts; arrange the parts in a build volume, including for at least a first part of the plurality of parts arranging the first part relative to an arrangement including one or more previously arranged parts of the plurality of parts; using a first spatial frequency domain representation of the shape of the first part determined from the first part and using a second spatial frequency domain representation of the arrangement; determining a location of the first part relative to the arrangement; and adding the first part to the arrangement at the determined location; form a build volume specification for three-dimensional fabrication according to the arrangement; and provide the build volume specification for use in a three-dimensional fabrication system. ### Claim 17 (depends on 16) The system of claim 16, wherein at least some of the hardware processors comprise graphics processing units capable of parallel computations. ### Claim 18 A non-transitory machine-readable medium comprising instructions stored thereon, the instructions when executed by one or more hardware processors cause said processors to: receive a specification of a shape for each part of a plurality of parts; arrange the parts in a build volume, including for at least a first part of the plurality of parts arranging the first part relative to an arrangement including one or more previously arranged parts of the plurality of parts; using a first spatial frequency domain representation of the shape of the first part determined from the first part and using a second spatial frequency domain representation of the arrangement; determining a location of the first part relative to the arrangement; and adding the first part to the arrangement at the determined location; form a build volume specification for three-dimensional fabrication according to the arrangement; and provide the build volume specification for use in a three-dimensional fabrication system.