US11897203B1  Frequency domain spatial packing for 3D fabrication  Google Patents
Frequency domain spatial packing for 3D fabrication Download PDFInfo
 Publication number
 US11897203B1 US11897203B1 US17/955,843 US202217955843A US11897203B1 US 11897203 B1 US11897203 B1 US 11897203B1 US 202217955843 A US202217955843 A US 202217955843A US 11897203 B1 US11897203 B1 US 11897203B1
 Authority
 US
 United States
 Prior art keywords
 arrangement
 parts
 spatial frequency
 frequency domain
 domain representation
 Prior art date
 Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
 Active
Links
 238000004519 manufacturing process Methods 0.000 title claims abstract description 30
 238000012856 packing Methods 0.000 title description 9
 238000000034 method Methods 0.000 claims description 42
 238000009826 distribution Methods 0.000 claims description 23
 238000012545 processing Methods 0.000 claims description 11
 238000003860 storage Methods 0.000 claims description 3
 238000000926 separation method Methods 0.000 abstract description 3
 239000000463 material Substances 0.000 description 23
 238000013459 approach Methods 0.000 description 17
 238000006073 displacement reaction Methods 0.000 description 16
 230000006870 function Effects 0.000 description 10
 238000011002 quantification Methods 0.000 description 5
 239000013598 vector Substances 0.000 description 5
 230000008901 benefit Effects 0.000 description 3
 239000000654 additive Substances 0.000 description 2
 230000000996 additive effect Effects 0.000 description 2
 238000003491 array Methods 0.000 description 2
 230000003247 decreasing effect Effects 0.000 description 2
 230000008569 process Effects 0.000 description 2
 239000007787 solid Substances 0.000 description 2
 239000004593 Epoxy Substances 0.000 description 1
 238000012952 Resampling Methods 0.000 description 1
 230000003466 anticipated effect Effects 0.000 description 1
 238000000149 argon plasma sintering Methods 0.000 description 1
 239000011230 binding agent Substances 0.000 description 1
 238000001514 detection method Methods 0.000 description 1
 238000010586 diagram Methods 0.000 description 1
 238000010801 machine learning Methods 0.000 description 1
 238000003801 milling Methods 0.000 description 1
 239000000203 mixture Substances 0.000 description 1
 238000012986 modification Methods 0.000 description 1
 230000004048 modification Effects 0.000 description 1
 239000012782 phase change material Substances 0.000 description 1
 238000012805 postprocessing Methods 0.000 description 1
 239000000843 powder Substances 0.000 description 1
 230000002787 reinforcement Effects 0.000 description 1
 238000004088 simulation Methods 0.000 description 1
 230000007704 transition Effects 0.000 description 1
 238000013519 translation Methods 0.000 description 1
 238000009827 uniform distribution Methods 0.000 description 1
 239000011800 void material Substances 0.000 description 1
Images
Classifications

 G—PHYSICS
 G06—COMPUTING; CALCULATING OR COUNTING
 G06F—ELECTRIC DIGITAL DATA PROCESSING
 G06F30/00—Computeraided design [CAD]
 G06F30/20—Design optimisation, verification or simulation

 B—PERFORMING OPERATIONS; TRANSPORTING
 B29—WORKING OF PLASTICS; WORKING OF SUBSTANCES IN A PLASTIC STATE IN GENERAL
 B29C—SHAPING OR JOINING OF PLASTICS; SHAPING OF MATERIAL IN A PLASTIC STATE, NOT OTHERWISE PROVIDED FOR; AFTERTREATMENT OF THE SHAPED PRODUCTS, e.g. REPAIRING
 B29C64/00—Additive manufacturing, i.e. manufacturing of threedimensional [3D] objects by additive deposition, additive agglomeration or additive layering, e.g. by 3D printing, stereolithography or selective laser sintering
 B29C64/30—Auxiliary operations or equipment
 B29C64/386—Data acquisition or data processing for additive manufacturing
 B29C64/393—Data acquisition or data processing for additive manufacturing for controlling or regulating additive manufacturing processes

 B—PERFORMING OPERATIONS; TRANSPORTING
 B29—WORKING OF PLASTICS; WORKING OF SUBSTANCES IN A PLASTIC STATE IN GENERAL
 B29C—SHAPING OR JOINING OF PLASTICS; SHAPING OF MATERIAL IN A PLASTIC STATE, NOT OTHERWISE PROVIDED FOR; AFTERTREATMENT OF THE SHAPED PRODUCTS, e.g. REPAIRING
 B29C64/00—Additive manufacturing, i.e. manufacturing of threedimensional [3D] objects by additive deposition, additive agglomeration or additive layering, e.g. by 3D printing, stereolithography or selective laser sintering
 B29C64/10—Processes of additive manufacturing
 B29C64/171—Processes of additive manufacturing specially adapted for manufacturing multiple 3D objects

 B—PERFORMING OPERATIONS; TRANSPORTING
 B29—WORKING OF PLASTICS; WORKING OF SUBSTANCES IN A PLASTIC STATE IN GENERAL
 B29C—SHAPING OR JOINING OF PLASTICS; SHAPING OF MATERIAL IN A PLASTIC STATE, NOT OTHERWISE PROVIDED FOR; AFTERTREATMENT OF THE SHAPED PRODUCTS, e.g. REPAIRING
 B29C64/00—Additive manufacturing, i.e. manufacturing of threedimensional [3D] objects by additive deposition, additive agglomeration or additive layering, e.g. by 3D printing, stereolithography or selective laser sintering
 B29C64/30—Auxiliary operations or equipment
 B29C64/386—Data acquisition or data processing for additive manufacturing

 B—PERFORMING OPERATIONS; TRANSPORTING
 B33—ADDITIVE MANUFACTURING TECHNOLOGY
 B33Y—ADDITIVE MANUFACTURING, i.e. MANUFACTURING OF THREEDIMENSIONAL [3D] OBJECTS BY ADDITIVE DEPOSITION, ADDITIVE AGGLOMERATION OR ADDITIVE LAYERING, e.g. BY 3D PRINTING, STEREOLITHOGRAPHY OR SELECTIVE LASER SINTERING
 B33Y50/00—Data acquisition or data processing for additive manufacturing

 B—PERFORMING OPERATIONS; TRANSPORTING
 B33—ADDITIVE MANUFACTURING TECHNOLOGY
 B33Y—ADDITIVE MANUFACTURING, i.e. MANUFACTURING OF THREEDIMENSIONAL [3D] OBJECTS BY ADDITIVE DEPOSITION, ADDITIVE AGGLOMERATION OR ADDITIVE LAYERING, e.g. BY 3D PRINTING, STEREOLITHOGRAPHY OR SELECTIVE LASER SINTERING
 B33Y50/00—Data acquisition or data processing for additive manufacturing
 B33Y50/02—Data acquisition or data processing for additive manufacturing for controlling or regulating additive manufacturing processes

 G—PHYSICS
 G06—COMPUTING; CALCULATING OR COUNTING
 G06F—ELECTRIC DIGITAL DATA PROCESSING
 G06F2113/00—Details relating to the application field
 G06F2113/10—Additive manufacturing, e.g. 3D printing
Definitions
 This invention relates to packing of objects for 3D fabrication.
 One approach to 3D fabrication of a batch of parts is to spatially arrange the parts to specify an overall fabrication volume fully containing the parts. Each part is positioned in a particular orientation in the volume, and the parts are fabricated together, for example, using a jetting additive fabrication approach in which layers of material are progressively added to form the overall fabrication volume.
 the specified volume generally includes support material on which parts are formed, and at least some parts are separated from one another by the support material.
 the chosen arrangement of the parts in the fabrication volume may affect the speed and/or cost of fabrications according to factors, including for instance the overall height to the volume (i.e., the height of the topmost part) or the amount of support material that is needed to form the overall build volume.
 arrangement of the parts 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.
 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.
 an approach to arranging more than two parts involves successive iterations in which in each iteration a part is place relatively to previously placed parts, until all the parts are placed, thereby defining the overall arrangement.
 the iterations may involve moving or removing previously placed parts.
 the overall build volume i.e., a threedimensional shape
 the overall build volume may be predefined, or at least partly resulting from the arrangement of the parts. For example, as many parts as possible may be arranged into a predefined volume, while in other examples, some aspects of the shape (e.g., the overall height) may be determined as a result of the arrangement procedure.
 a method for arranging a plurality of parts into a build volume for threedimensional fabrication includes receiving a specification of a shape each part of a plurality of parts.
 the specification of a shape may be a voxelbased representation.
 the parts are arranged in a build volume. This arranging includes, for each 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.
 the arranging of the first part includes using a first spatial frequency representation of the shape of the first part determined from the first part as well as using a second spatial frequency representation of the arrangement, and using these spatial frequency representations determining a relative location of the first part and the arrangement.
 the first part is then added to the arrangement at the determined relative location.
 a specification of a build volume for threedimensional fabrication is formed according to the arrangement and provided for use in a threedimensional fabrication system.
 aspects can include one of more of the following features.
 a spatial frequency of shapes of at least some parts of the plurality of parts is determined.
 Determining the relative location of the first part and the arrangement includes processing the first spatial frequency representation and the second spatial frequency representation to yield a third spatial frequency representation, and processing the third spatial frequency representation to yield third spatial representation.
 Determining the relative location of the first part and the arrangement further includes processing the third spatial representation includes searching the third spatial representation for the relative location for the arrangement.
 the first spatial frequency representation of the shape of the first part comprises a Fourier Transform of a volume occupied by the first part
 the second spatial frequency representation of the arrangement comprises a Fourier Transform of a spatial preference distribution at offsets of the first part and the arrangement
 the spatial preference distribution represents one or more of (a) a preference for placement of the first part in proximity to parts of the arrangement, (b) a preference to reduce support volume for supporting placed parts, and (c) a preference of reduced height of arrangement of parts within the build volume.
 Using the first spatial frequency representation of the shape of the first part determined from the first part and the second spatial frequency representation of the arrangement includes determining a third spatial frequency representation over offsets of the first part relative to the arrangement.
 Using the first spatial frequency representation of the shape of the first part determined from the first part and the second spatial frequency representation of the arrangement further includes determining a spatial distribution over offsets of the first part relative to the arrangement.
 Determining a spatial distribution over offsets of the first part relative to the arrangement includes determining an inverse Fourier Transform of the third spatial frequency distribution.
 a plurality of rotations of the first part are used to determine a rotation of said first part for adding to the arrangement.
 a spatial frequency representation of the first part is determined in each of the plurality of rotations.
 the spatial frequency representation of the arrangement represents a build volume without any parts yet placed within it.
 a system for arranging a plurality of parts into a build volume for threedimensional fabrication 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 perform all the steps of any one of methods set forth above.
 the hardware processors may comprise a graphics processing units capable of parallel computations.
 a nontransitory machinereadable medium comprising instructions stored thereon, the instructions when executed by one or more hardware processors cause said processors to perform all the steps of any one of the methods set forth above.
 FIG. 1 is a system diagram.
 FIG. 2 is a 2dimensional view of a build volume specification.
 FIG. 3 illustrates a preference distribution based on a build volume boundary, and a first part for placement.
 FIG. 4 illustrates a 2dimensional view of a preference distribution based on a build volume boundary and placement of the first part, and a second part for placement.
 FIG. 5 illustrates a 2dimensional view of a preference distribution based on a build volume boundary and placement of the first and second parts, and a thrid part for placement.
 FIG. 6 illustrates a 2dimensional view of a preference distribution based on a build volume boundary and placement of the first, second and third parts.
 FIG. 7 is a 2dimensional view of a nonseparable part arrangement.
 FIG. 8 is a 2dimensional view of a separable part arrangement.
 FIG. 9 is a 2dimensional view of a part placement formed with lowresolution voxels.
 FIG. 10 is a 2dimensional view of placement of parts of FIG. 9 at an original resolution.
 an additive fabrication system 100 includes a printer 140 , which includes a printhead assembly 142 , which can controllably jet a number of materials, including a support material (e.g., a phasechange material, such as a wax) and at least one build material (e.g., a curable material, such as an ultraviolet light curable epoxy).
 a controller 144 receives vision feedback from a vision system 146 , and controls the printhead assembly 142 and a threedegreeof freedom motion system for a build platform 148 , such that the coordination of movement of the build platform and jetting of materials from the printhead assembly 142 causes successive layers of material to be deposited to form a 3D object according to a specification received by the controller.
 Suitable fabrication systems 100 are described in U.S. Pat. Nos. 10,252,466, 10,994,490, and 10,456,984 and copending application Ser. No. 17/197,581, filed Mar. 10, 2021, the entire contents of which are incorporated herein by reference.
 the specification 130 of the build volume is provided to the printer 140 .
 This specification describes the overall arrangement of individual parts 122 a  z and support material 123 (leaving unfilled volume 125 in the build volume) that is to be printed by the printer.
 the specification is stored in a data structure, which is used by the controller to determine which material (if any) to print at each threedimensional addressable location in the build volume.
 this data structure comprises a voxel representation in which each voxel (i.e., each regularly arranged region, such as a cube) is associated with one or alternatively a mixture of materials, or is identified as being empty.
 a solid model representation is used, for example, with bounding surfaces (e.g., planar tessellations) defining transitions between materials (e.g., between the support material and a build material, between build materials, and/or between a build material and “empty” space).
 bounding surfaces e.g., planar tessellations
 this specification is determined by an arranger 120 , which implements a procedure described below to use specifications of the shapes (and optional internal multibuildmaterial structures) of multiple parts of a part inventory 110 that are to be fabricated.
 shape specifications 112 a  z may be represented as voxel representations or solid models.
 One procedure that is implemented by the arranger 120 determines the possible (i.e., nonoverlapping) relative positions of a part relative to another part or relative to a fixed arrangement of multiple other parts or objects.
 the shapes of each part can be represented as an arrays of indicator values, ⁇ A (x, y, z) and ⁇ B (x, y, z) , that have a value 1 if that (x, y, z) indexed voxel is within the volume of the part and 0 otherwise.
 the array is an N ⁇ N ⁇ N array, where N is greater than the maximum size of the build volume in any direction, for example, at least twice the maximum size.
 the indices (x, y, z) are relative to an origin point (e.g., the lowest occupied coordinate index in each dimension) for each of the shapes. With such arrays, if their origins are aligned, then the sum of ⁇ A (x, y, z) ⁇ B (x, y, z) over all locations (x, y, z) is zero if there is no overlap, and is greater than zero, specifically representing the number of overlapping voxels, when the objects overlap.
 the elements of the displacement t are assumed positive, and ⁇ B is assumed zero with negative coordinate indices.
 a search over relative displacements t of the objects to find those displacements in which the objects do not overlap can involve substantial computation for each possible displacement to determine if there is no overlap.
 DTF Discrete Fourier Transform
 F A ( ⁇ ) ⁇ x f A ( x ) ⁇ exp ⁇ (  j ⁇ ⁇ ⁇ x ⁇ ( 2 ⁇ ⁇ / N ) )
 j is the square root of ⁇ 1 and ⁇ is the dot (inner) product of two vectors
 ⁇ ( ⁇ 1 , ⁇ 2 , ⁇ 3 ) are spatial frequency indices (i.e., 0 ⁇ i ⁇ N) and the summation is over each of the dimensions (0 ⁇ x i ⁇ N).
 F A is an N ⁇ N ⁇ N array (i.e., a threedimensional array) of complex quantities (in general).
 a computationally efficient procedure for computing the DFT is the Fast Fourier Transform (FFT).
 FFT Fast Fourier Transform
 particular FFT implementations that take advantage of knowledge that the input in the spatial domain is real while the output in the transform domain is complex are used to reduce the number of arithmetic operations, while in other examples, the real representations are first converted to complex number form before performing the FFT, and then retaining only the real part of a result after performing the inverse FFT.
 rotation of the shape in multiples of 90 degrees around any axis corresponds to a relatively simple manipulation of the DFT of the shape.
 the DFT of the rotated part can be computed directly from the DFT of the part without rotation by changing the order of indices and/or negation or complexconjugate operations on values.
 rotations other than by multiplex of 90 degrees around the axes may be considered for packing, for example it is possible to attempt different possible object orientations by using a uniform distribution of orientations over the sphere. Different rotational discretization can be obtained by subdividing an icosahedron. Some orientations can be excluded from the search if they are undesired.
 some object orientations can cause surface or warping artifacts.
 Some orientations may be found with geometrybased approaches. For example, one way is aligning the parts with the void space with the iterative closest point algorithm. Rotating the object in the frequency domain with arbitrary angles (i.e., non 90 degrees) may require resampling in the frequency domain, which may lead to precision loss, in which case rotation may be preferably performed in the spatial sample (voxel) domain, with the spatial frequency domain representations being computed after spatial rotation.
 This process may be repeated maintaining a shape of all the placed parts, which can be represented as an object A, and repeating the process above:
 each displacement for which g A,B (t) is zero can be further quantified, for example, according to a criterion such as the largest remaining unused space (i.e., to leave space for unused objects), the lowest maximum height of an object, closeness to other parts, etc. But it may be recognized that computing such quantifications may themselves be computationally expensive.
 voxels in the volume are assigned penalty for filling, and in one example, voxels near other objects may be preferably filled as compared to voxels that are far from any object, which are penalized.
 a penalty causes parts to be placed close to one another.
 the indicator function ⁇ (x) is denoted with a superscript ⁇ c (x) (for “collision”), and a preference function ⁇ d (x) (“d” for “density”) is introduced that has the voxel based penalty for placing further objects.
 ⁇ c for “collision”
 d preference function
 g A , B d ( t ) ⁇ x f A d ( x ) ⁇ f B c ( x  t ) such that a preferred displacement t minimizes g d .
 the selection of a best displacement t ⁇ above can be performed by minimizing g A,B d (t) over the set of displacements .
 density may be defined as a smearing (e.g., a convolution) of the collision indicator with a kernel function.
 the density function ⁇ A d (x) can be any function that smoothly extends the collision indicator into the empty space and differentiates positions that are near or far from the list of placed objects A. For example, by computing a distance function, or convolving the collision indicator with a suitable kernel function (a box or Gaussian kernel).
 a “volume” metric which generally penalizes placing parts in a manner that increases the support volume.
 support material 230 is generally placed below parts 222 , but is not needed above parts in the build volume 220 (shown as unfilled region 235 ).
 a goal is to determine the resulting volume of support material or the total volume of support and built material that results from placement of a part.
 a voxelbased penalty may be defined as
 the top surface indicator is define as:
 volumebased penalty may be defined as
 g A , B v ( t ) ⁇ x f A v ( x ) ⁇ f B t ( x  t ) and a selection of displacement t may be chosen to minimize g A,B v (t). As above, this penalty can be computed in the spatial frequency domain.
 the heightbased penalty may be defined as:
 g A , B h ( t ) ⁇ x f A h ( x ) ⁇ f B c ( x  t )
 selection of a displacement t may be chosen to minimize a combined penalty such as ⁇ g A,B h (t)+(1 ⁇ )g A,B v (t) for some relative weighting 0 ⁇ 1 or as ⁇ 1 g A,B d (t)+ ⁇ 2 g A,B v (t)+ ⁇ 3 g A,B h (t) for some relative weighting
 One way of guaranteeing the separability is to make sure the placement t of object B following a noncolliding path from the outside of the tray. To do that, after g A,B c (t) is computed, some locations outside of the tray are marked as valid. Then, starting from those locations, all reachable locations via a noncolliding and translationonly path can be efficiently found through a breadth first search or floodfill on g A,B c (t). Another way of doing this is using a physical based simulator, where in each simulation step, a force is applied to object B until B is separated from A, or after a certain computational budget is reached. Yet another way of doing this is using a geometrybased path planning approach, where the path is found by constructing the Configuration space (Cspace). The latter two approaches maybe more expensive than the first one, but they can search for noncolliding path with part rotations.
 Cspace Configuration space
 the disassemble procedure can be executed per each part placement (step 2g. above) or as a postprocess (procedure step 3.).
 the benefit of per part checking is it ensures every intermediate tray A satisfying the separable constraint, at the cost of higher computing expense.
 the postprocess checking requires less computing, but already placed parts maybe removed in the postprocess, resulting in less immediate feedback. If all packed parts are relatively convex, the tray is assumed to be separable and the disassemble procedure is skipped.
 the procedure above can be considered a “greedy” procedure in which once a part is placed, it is not moved.
 An alternative procedure may include iterations in which a part is removed from the partial assembly.
 the selection of the part to add or remove at an iteration may be made on other criteria than size. For example, parts may be selected at random. Similarly, parts to add may be selected at random, possibly biased in favor of adding larger objects.
 a machinelearning (e.g., reinforcement learning) approach may be used for the selection of a part to add or remove based on the shapes of the parts and/or the state of the partial assembly. Note that the particular procedure for selecting and placing parts is a solution to a combinatorial problem, and there are a number of viable alternative approaches.
 A* search strategy where the user needs to provide a heuristic function, that estimates the total cost of given search branch approximately.
 the procedure above can be extended to support packing of multiple trays. Given a list of unpacked objects, one way of doing this is to pack the first tray with procedure 2., take the “unplaced” list, and pack the next tray, until all the objects are packed. An alternative is to first allocate a fixed number of trays, for each part, computing the preference score for each tray, and placing the part into the best fitting tray.
 a quantification based on the height dimension of the displacement vector may be used to account for the resulting overall height of the top of the part being placed.
 a single convolution may be performed to combine the criteria for nonoverlapping parts and proximity of placed parts, for example, by transitioning from a large penalty just inside the existing parts to a preference just outside these parts.
 a large penalty just inside the existing parts to a preference just outside these parts.
 such large discontinuities in the preference distribution have undesirable numerical computation aspects, and therefore separately addressing these two factors is preferred.
 FIGS. 4  6 an example illustrating successive placement of three parts based on a nonoverlapping and proximity preference are illustrated.
 a 2dimensional view is provided (e.g., which can be interpreted as a 2dimensional analog of the procedures described above, or a crosssection view of a 3dimensional implementation).
 the object A is made up of only the boundary of the build volume, and a preference distribution ⁇ A d (x) 330 (with darker representing increased preference) shows preference to placing the next part near the build volume boundary.
 a first part B has a shape represented by ⁇ B c (x) 322 , which is defined relative to its origin 323 .
 a suitable positioning of the part B is then at the selected offset 333 illustrated on the preference distribution 330 .
 the object A is updated to be the combination of the build volume boundary and the placed first part, and the resulting preference distribution ⁇ A d (x) 430 shows preference to placing the second part near placed first part.
 a second part B has a shape represented by ⁇ B c (x) 422 , which is defined relative to its origin 423 .
 a suitable positioning of the second part B is then at the selected offset 433 illustrated on the preference distribution 430 .
 the object A is updated to be the combination of the build volume boundary and the placed parts, and the resulting preference distribution ⁇ A d (x) 530 shows preference to placing the third part near placed parts.
 a third part B has a shape represented by ⁇ B c (x) 522 , which is defined relative to its origin 523 .
 a suitable positioning of the second part B is then at the selected offset 533 illustrated on the preference distribution 530 .
 the object A is updated to be the combination of the build volume boundary and the placed parts, and the resulting preference distribution ⁇ A d (x) 630 .
 a packing procedure uses a lower resolution (e.g., downsampled voxel representation) to determine initial placements, which can then be refined using higher resolution representations (e.g., by successively moving each placed part incrementally relative to the other placed parts, where the original geometry is used for collision detection.).
 a lower resolution e.g., downsampled voxel representation
 higher resolution representations e.g., by successively moving each placed part incrementally relative to the other placed parts, where the original geometry is used for collision detection.
 Implementations of the approaches described above are amenable to parallelization, and more particularly to implementation on Graphics Processing Units (GPUs).
 GPUs Graphics Processing Units
 the Fourier Transform computations, as well as the search to locate best offsets for placements can be performed on a GPU.
 the approaches described above may be suitable to a box shaped build volume, arbitraryshaped build volume can also be supported.
 the bounding box of the build volume is first computed, any voxels that are outside of the specified build volume are marked as occupied.
 a different fabrication system may use a cylindrical build volume. The minimum separation distance can be satisfied by simply expanding the object voxels.
 the approaches can be used in variety 2D and 3D packing/arrangement problems, for example, for arranging packages for storage or shipment.
 the approaches can be used not only for jetted fabrication, but other printing approaches as well, for example, involving powderbased binder jetting/laser sintering.
 the packing approach can also be applied to 2D packing problems, for example, for CNC milling.
Landscapes
 Engineering & Computer Science (AREA)
 Chemical & Material Sciences (AREA)
 Materials Engineering (AREA)
 Manufacturing & Machinery (AREA)
 Physics & Mathematics (AREA)
 Optics & Photonics (AREA)
 Mechanical Engineering (AREA)
 Theoretical Computer Science (AREA)
 Computer Hardware Design (AREA)
 Evolutionary Computation (AREA)
 Geometry (AREA)
 General Engineering & Computer Science (AREA)
 General Physics & Mathematics (AREA)
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.
Description
This invention relates to packing of objects for 3D fabrication.
One approach to 3D fabrication of a batch of parts is to spatially arrange the parts to specify an overall fabrication volume fully containing the parts. Each part is positioned in a particular orientation in the volume, and the parts are fabricated together, for example, using a jetting additive fabrication approach in which layers of material are progressively added to form the overall fabrication volume. The specified volume generally includes support material on which parts are formed, and at least some parts are separated from one another by the support material.
The chosen arrangement of the parts in the fabrication volume may affect the speed and/or cost of fabrications according to factors, including for instance the overall height to the volume (i.e., the height of the topmost part) or the amount of support material that is needed to form the overall build volume.
There is a need to arrange the parts relative to one another to achieve desirable overall printing characteristics, including one or a combination of a fastest anticipated printing time and lowest material cost.
In one aspect, in general, arrangement of the parts 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.
In some examples, an approach to arranging more than two parts involves successive iterations in which in each iteration a part is place relatively to previously placed parts, until all the parts are placed, thereby defining the overall arrangement. In some examples, the iterations may involve moving or removing previously placed parts.
The overall build volume (i.e., a threedimensional shape) that bounds the arrangement of parts may be predefined, or at least partly resulting from the arrangement of the parts. For example, as many parts as possible may be arranged into a predefined volume, while in other examples, some aspects of the shape (e.g., the overall height) may be determined as a result of the arrangement procedure.
In one aspect, in general, a method for arranging a plurality of parts into a build volume for threedimensional fabrication includes receiving a specification of a shape each part of a plurality of parts. In some instances, the specification of a shape may be a voxelbased representation. The parts are arranged in a build volume. This arranging includes, for each 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. The arranging of the first part includes using a first spatial frequency representation of the shape of the first part determined from the first part as well as using a second spatial frequency representation of the arrangement, and using these spatial frequency representations determining a relative location of the first part and the arrangement. The first part is then added to the arrangement at the determined relative location. Finally, a specification of a build volume for threedimensional fabrication is formed according to the arrangement and provided for use in a threedimensional fabrication system.
Aspects can include one of more of the following features.
A spatial frequency of shapes of at least some parts of the plurality of parts is determined.
Determining the relative location of the first part and the arrangement includes processing the first spatial frequency representation and the second spatial frequency representation to yield a third spatial frequency representation, and processing the third spatial frequency representation to yield third spatial representation.
Determining the relative location of the first part and the arrangement further includes processing the third spatial representation includes searching the third spatial representation for the relative location for the arrangement.
In any of the preceding combination, the first spatial frequency representation of the shape of the first part comprises a Fourier Transform of a volume occupied by the first part, and the second spatial frequency representation of the arrangement comprises a Fourier Transform of a spatial preference distribution at offsets of the first part and the arrangement.
The spatial preference distribution represents one or more of (a) a preference for placement of the first part in proximity to parts of the arrangement, (b) a preference to reduce support volume for supporting placed parts, and (c) a preference of reduced height of arrangement of parts within the build volume.
Using the first spatial frequency representation of the shape of the first part determined from the first part and the second spatial frequency representation of the arrangement includes determining a third spatial frequency representation over offsets of the first part relative to the arrangement.
Using the first spatial frequency representation of the shape of the first part determined from the first part and the second spatial frequency representation of the arrangement further includes determining a spatial distribution over offsets of the first part relative to the arrangement.
Determining a spatial distribution over offsets of the first part relative to the arrangement includes determining an inverse Fourier Transform of the third spatial frequency distribution.
In any of the previous combinations, for at least the first part of the plurality of parts, a plurality of rotations of the first part are used to determine a rotation of said first part for adding to the arrangement.
A spatial frequency representation of the first part is determined in each of the plurality of rotations.
In any of the preceding combinations, for at least one part of the plurality of parts, the spatial frequency representation of the arrangement represents a build volume without any parts yet placed within it.
In another aspect, in general, a system for arranging a plurality of parts into a build volume for threedimensional 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 perform all the steps of any one of methods set forth above. At least some of the hardware processors may comprise a graphics processing units capable of parallel computations.
In another aspect, in general, a nontransitory machinereadable medium comprising instructions stored thereon, the instructions when executed by one or more hardware processors cause said processors to perform all the steps of any one of the methods set forth above.
Other features and advantages of the invention are apparent from the following description, and from the claims.
Referring to FIG. 1 , an additive fabrication system 100 includes a printer 140, which includes a printhead assembly 142, which can controllably jet a number of materials, including a support material (e.g., a phasechange material, such as a wax) and at least one build material (e.g., a curable material, such as an ultraviolet light curable epoxy). A controller 144 receives vision feedback from a vision system 146, and controls the printhead assembly 142 and a threedegreeof freedom motion system for a build platform 148, such that the coordination of movement of the build platform and jetting of materials from the printhead assembly 142 causes successive layers of material to be deposited to form a 3D object according to a specification received by the controller. Suitable fabrication systems 100 are described in U.S. Pat. Nos. 10,252,466, 10,994,490, and 10,456,984 and copending application Ser. No. 17/197,581, filed Mar. 10, 2021, the entire contents of which are incorporated herein by reference.
Continuing to refer to FIG. 1 , the specification 130 of the build volume is provided to the printer 140. This specification describes the overall arrangement of individual parts 122 az and support material 123 (leaving unfilled volume 125 in the build volume) that is to be printed by the printer. The specification is stored in a data structure, which is used by the controller to determine which material (if any) to print at each threedimensional addressable location in the build volume. In some examples, this data structure comprises a voxel representation in which each voxel (i.e., each regularly arranged region, such as a cube) is associated with one or alternatively a mixture of materials, or is identified as being empty. In other examples, a solid model representation is used, for example, with bounding surfaces (e.g., planar tessellations) defining transitions between materials (e.g., between the support material and a build material, between build materials, and/or between a build material and “empty” space).
Regardless of the specific form of the data structure representing build volume specification 130, this specification is determined by an arranger 120, which implements a procedure described below to use specifications of the shapes (and optional internal multibuildmaterial structures) of multiple parts of a part inventory 110 that are to be fabricated. These shape specifications 112 az may be represented as voxel representations or solid models.
One procedure that is implemented by the arranger 120 determines the possible (i.e., nonoverlapping) relative positions of a part relative to another part or relative to a fixed arrangement of multiple other parts or objects. For example, for two parts, A and B, the shapes of each part can be represented as an arrays of indicator values, ƒ_{A}(x, y, z) and ƒ_{B}(x, y, z) , that have a value 1 if that (x, y, z) indexed voxel is within the volume of the part and 0 otherwise. For example, the array is an N×N×N array, where N is greater than the maximum size of the build volume in any direction, for example, at least twice the maximum size. Note that the indices (x, y, z) are relative to an origin point (e.g., the lowest occupied coordinate index in each dimension) for each of the shapes. With such arrays, if their origins are aligned, then the sum of ƒ_{A}(x, y, z)ƒ_{B}(x, y, z) over all locations (x, y, z) is zero if there is no overlap, and is greater than zero, specifically representing the number of overlapping voxels, when the objects overlap. For simplicity of notation, the triple (x, y, z) is denoted as a vector x=(x_{1}, x_{2}, x_{3}) below.
To the extent that object B is displaced by in the three dimensions according to a vector t, then if there is no overlap, the following sum over all locations x must be zero:
For example, the elements of the displacement t are assumed positive, and ƒ_{B }is assumed zero with negative coordinate indices. A search over relative displacements t of the objects to find those displacements in which the objects do not overlap can involve substantial computation for each possible displacement to determine if there is no overlap.
While computing g_{A,B}(t) for all t may be computationally expensive, a preferable approach is to first compute the Discrete Fourier Transform (DTF) of the array for each part to represent the shape in a spatial frequency domain. For example, for part A, this computation can be expressed as:
where j is the square root of −1 and · is the dot (inner) product of two vectors, and ω=(ω_{1}, ω_{2}, ω_{3}) are spatial frequency indices (i.e., 0≤ω_{i}<N) and the summation is over each of the dimensions (0≤x_{i}<N). Note that F_{A }is an N×N×N array (i.e., a threedimensional array) of complex quantities (in general). For conciseness, this computation of the DFT can be expressed as F_{A}=(ƒ_{A}) , and the inverse operation is expressed as ƒ_{A}= ^{−1}(F_{A}).
A useful property of the DTF is that one the summation over possible relative displacements shown above can be expressed as
G _{A, B}(ω)=F _{A}(ω)F_{B}*(ω)
where the superscript * denotes a complex conjugate operation (negating the imaginary component of the complex number) and the multiplication of F_{A }and F_{B }is elementwise over frequencies ω. Therefore, determining the relative displacements for which there is no overlap involves computing:
g _{A,B}= ^{−1}(G _{A, B})
G _{A, B}(ω)=F _{A}(ω)F_{B}*(ω)
where the superscript * denotes a complex conjugate operation (negating the imaginary component of the complex number) and the multiplication of F_{A }and F_{B }is elementwise over frequencies ω. Therefore, determining the relative displacements for which there is no overlap involves computing:
g _{A,B}= ^{−1}(G _{A, B})
A computationally efficient procedure for computing the DFT is the Fast Fourier Transform (FFT). In some examples, particular FFT implementations that take advantage of knowledge that the input in the spatial domain is real while the output in the transform domain is complex are used to reduce the number of arithmetic operations, while in other examples, the real representations are first converted to complex number form before performing the FFT, and then retaining only the real part of a result after performing the inverse FFT.
Note that rotation of the shape in multiples of 90 degrees around any axis (keeping the origin of the array fixed) corresponds to a relatively simple manipulation of the DFT of the shape. In particular, for each of the 23 possible combined rotations of a part, the DFT of the rotated part can be computed directly from the DFT of the part without rotation by changing the order of indices and/or negation or complexconjugate operations on values. More generally, rotations other than by multiplex of 90 degrees around the axes may be considered for packing, for example it is possible to attempt different possible object orientations by using a uniform distribution of orientations over the sphere. Different rotational discretization can be obtained by subdividing an icosahedron. Some orientations can be excluded from the search if they are undesired. For example, some object orientations can cause surface or warping artifacts. Some orientations may be found with geometrybased approaches. For example, one way is aligning the parts with the void space with the iterative closest point algorithm. Rotating the object in the frequency domain with arbitrary angles (i.e., non 90 degrees) may require resampling in the frequency domain, which may lead to precision loss, in which case rotation may be preferably performed in the spatial sample (voxel) domain, with the spatial frequency domain representations being computed after spatial rotation.
Turning now to a procedure for choosing a placement of a part B relative to a part A by determining the offset vector t, one way is to perform the following placement procedure:
1. Compute G_{A,B}(ω)=F_{A}(ω)F_{B}*(ω)
This process may be repeated maintaining a shape of all the placed parts, which can be represented as an object A, and repeating the process above:

 1. ƒ_{A}(x)←shape of build volume (e.g., a onevoxel wide bounding surface of the permitted build volume)
 2. Repeat for each unplaced part B (e.g., in order of decreasing size):
 a. Place B relative to A using a placement procedure at a “best” offset t
 b. Replace A with the combination of A and B (i.e.,
ƒ_{A}(x)←ƒ_{A}(x)+ƒ_{B}(x−t) or F _{A}(ω)←F _{A}(ω)+F _{B}(ω)exp(+jω·t))
Note that there may be a number of different ways in which the best displacement t may be determined. For example, each displacement for which g_{A,B}(t) is zero can be further quantified, for example, according to a criterion such as the largest remaining unused space (i.e., to leave space for unused objects), the lowest maximum height of an object, closeness to other parts, etc. But it may be recognized that computing such quantifications may themselves be computationally expensive.
In an alternative, for a given object A (e.g., the assembly of a number of parts), voxels in the volume are assigned penalty for filling, and in one example, voxels near other objects may be preferably filled as compared to voxels that are far from any object, which are penalized. Such a penalty causes parts to be placed close to one another. Below, the indicator function ƒ(x) is denoted with a superscript ƒ^{c }(x) (for “collision”), and a preference function ƒ^{d}(x) (“d” for “density”) is introduced that has the voxel based penalty for placing further objects. With this density function, an overall penalty for positioning a part B near an object (e.g., an assembly of parts) A can be quantified as
such that a preferred displacement t minimizes g^{d}. Note that as with the nonoverlap (i.e., noncollision) criterion, this can also be computed in the spatial frequency domain as:
G _{A,B} ^{d}(ω)=F _{A} ^{d}(ω)F _{B} ^{c}*(ω)
and
g _{A,B} ^{d}= ^{−1}(G _{A,B} ^{d})
One way of computing ƒ_{A} ^{d}(x) from ƒ_{A} ^{c}(x) is as a distance field of the existing object A, which is computed for every voxel (x). For each voxel, ƒ_{A} ^{d}(x) measures the distance to the closest voxel that is occupied by the existing object A. It is defined as zero on the occupied voxels (i.e., ƒ_{A} ^{d}(x)=0 if ƒ_{A} ^{c}(x)=1), and ramps up as the voxel moves away from the occupied voxel.
Using this computation, the selection of a best displacement tϵ above can be performed by minimizing g_{A,B} ^{d}(t) over the set of displacements .
In an alternative, the density may be defined as a preference, such that a maximum may be sought over displacements for which g_{A,B} ^{c}(t)=0. For example, one can define density as a smearing (e.g., a convolution) of the collision indicator with a kernel function. In principle the density function ƒ_{A} ^{d}(x) can be any function that smoothly extends the collision indicator into the empty space and differentiates positions that are near or far from the list of placed objects A. For example, by computing a distance function, or convolving the collision indicator with a suitable kernel function (a box or Gaussian kernel).
Another quantification of possible (i.e., nonoverlapping/noncolliding) positionings of a part B relative to an object A is based on a “volume” metric, which generally penalizes placing parts in a manner that increases the support volume. Referring to FIG. 2 , support material 230 is generally placed below parts 222, but is not needed above parts in the build volume 220 (shown as unfilled region 235). A goal is to determine the resulting volume of support material or the total volume of support and built material that results from placement of a part. A voxelbased penalty may be defined as
where x_{3 }is the height coordinate of x (i.e., increasing as the height increases) and
height_{A}(x _{1} , x _{2})=max x _{3 }over ƒ_{A} ^{c}(x _{1} , x _{2} , x _{3})=1.
To compute total occupied volume (including support) of the part being placed, the top surface indicator is define as:
With these definitions, volumebased penalty may be defined as
and a selection of displacement t may be chosen to minimize g_{A,B} ^{v}(t). As above, this penalty can be computed in the spatial frequency domain.
Another quantification of possible positionings of a part B relative to an object A is based on a “height” metric, which generally penalizes placing parts in a manner that increases the height and/or prefers placing part a low as possible. For example, a voxelbased penalty may be defined as:
ƒ_{A} ^{h}(x)=αx_{3 }
where α is a positive penalization factor, for example, α=2. The heightbased penalty may be defined as:
ƒ_{A} ^{h}(x)=αx_{3 }
where α is a positive penalization factor, for example, α=2. The heightbased penalty may be defined as:
In some examples, selection of a displacement t may be chosen to minimize a combined penalty such as θg_{A,B} ^{h}(t)+(1−θ)g_{A,B} ^{v}(t) for some
An example over an overall packing procedure using an approach described above may be summarized as follows:

 1. ƒ_{A} ^{c}(x)←shape of build volume
 2. Repeat for each unplaced part B (e.g., in order of decreasing size):
 a. Compute G_{a,b} ^{c}(ω)=F_{A} ^{c}(ω)F_{B} ^{c}*(ω)
 b. Compute g_{A,B} ^{c}= ^{−1}(G_{A,B} ^{c})
 c. Compute F_{A} ^{d }and F_{A} ^{v }from ƒ_{A} ^{c }and F_{B} ^{t }from ƒ_{B} ^{c }
 d. Compute G_{A,B} ^{d}(ω)=F_{A} ^{d}(ω)F_{B} ^{c}*(ω) and G_{A,B} ^{v}(ω)=F_{A} ^{v}(ω)F_{B} ^{t}*(ω)
 e. Compute g_{A,B} ^{pen}= ^{−1}(θG_{A,B} ^{d}+(1−θ)G_{A,B} ^{v})
 f. Search for t such that g_{A,B}(t)=0 and minimizes g_{A,B} ^{pen}(t)
 g. (Optional) Ensure the placing of B at t guarantees A can be disassembled/separated (see below)
 h. Locally refine the placement t using the original geometry of the shape (see below)
 i. If there exists a possible t replace A with the combination of A and B, otherwise add B to an “unplaced” list
 3. (Optional) If 2g. is not enabled, dissemble the tray A as a post processing step, which guarantees that after printing, all parts can be separated from each other, e.g., there are no parts placed inside of a cavity of another part in a way that cannot be removed (as shown in
FIG. 7 ). a. Iterate over all placed objects in A, dissemble all separable parts
 b. Remove one or more parts from A that are not separable, move them to an “interlocked” list, and then loop over the remaining parts and dissemble them
 c. Repeating step b until the tray A is empty
 d. Iterate over all parts in the “interlocked” list, and then place them into the tray again, following procedures described in 2, with the step 2.g enabled
To ensure the manufacturability of the packed tray A, all the packed parts should be able to separate from each other. For example, as shown in FIG. 7 , the object B cannot be separated from A following a noncolliding path. On the other hand, the configuration in FIG. 8 can be successfully separated. Additional steps are used to ensure this constraint.
One way of guaranteeing the separability is to make sure the placement t of object B following a noncolliding path from the outside of the tray. To do that, after g_{A,B} ^{c}(t) is computed, some locations outside of the tray are marked as valid. Then, starting from those locations, all reachable locations via a noncolliding and translationonly path can be efficiently found through a breadth first search or floodfill on g_{A,B} ^{c}(t). Another way of doing this is using a physical based simulator, where in each simulation step, a force is applied to object B until B is separated from A, or after a certain computational budget is reached. Yet another way of doing this is using a geometrybased path planning approach, where the path is found by constructing the Configuration space (Cspace). The latter two approaches maybe more expensive than the first one, but they can search for noncolliding path with part rotations.
The disassemble procedure can be executed per each part placement (step 2g. above) or as a postprocess (procedure step 3.). The benefit of per part checking is it ensures every intermediate tray A satisfying the separable constraint, at the cost of higher computing expense. On the other hand, the postprocess checking requires less computing, but already placed parts maybe removed in the postprocess, resulting in less immediate feedback. If all packed parts are relatively convex, the tray is assumed to be separable and the disassemble procedure is skipped.
The procedure above can be considered a “greedy” procedure in which once a part is placed, it is not moved. An alternative procedure may include iterations in which a part is removed from the partial assembly. Also, the selection of the part to add or remove at an iteration may be made on other criteria than size. For example, parts may be selected at random. Similarly, parts to add may be selected at random, possibly biased in favor of adding larger objects. In some examples, a machinelearning (e.g., reinforcement learning) approach may be used for the selection of a part to add or remove based on the shapes of the parts and/or the state of the partial assembly. Note that the particular procedure for selecting and placing parts is a solution to a combinatorial problem, and there are a number of viable alternative approaches. One of such approaches is a beamsearch strategy, where only few most promising search directions are explored. Another one is A* search strategy, where the user needs to provide a heuristic function, that estimates the total cost of given search branch approximately. Yet another strategy learns the heuristic functions by exploring the combinatory space, for example, Qlearning.
The procedure above can be extended to support packing of multiple trays. Given a list of unpacked objects, one way of doing this is to pack the first tray with procedure 2., take the “unplaced” list, and pack the next tray, until all the objects are packed. An alternative is to first allocate a fixed number of trays, for each part, computing the preference score for each tray, and placing the part into the best fitting tray.
In some alternatives, rather than the volume quantification, a quantification based on the height dimension of the displacement vector may be used to account for the resulting overall height of the top of the part being placed.
In an alternative, a single convolution may be performed to combine the criteria for nonoverlapping parts and proximity of placed parts, for example, by transitioning from a large penalty just inside the existing parts to a preference just outside these parts. However, in at least some implementations, such large discontinuities in the preference distribution have undesirable numerical computation aspects, and therefore separately addressing these two factors is preferred.
Referring to FIGS. 46 , an example illustrating successive placement of three parts based on a nonoverlapping and proximity preference are illustrated. A 2dimensional view is provided (e.g., which can be interpreted as a 2dimensional analog of the procedures described above, or a crosssection view of a 3dimensional implementation).
In FIG. 3 , the object A is made up of only the boundary of the build volume, and a preference distribution ƒ_{A} ^{d}(x) 330 (with darker representing increased preference) shows preference to placing the next part near the build volume boundary. A first part B has a shape represented by ƒ_{B} ^{c}(x) 322, which is defined relative to its origin 323. A suitable positioning of the part B is then at the selected offset 333 illustrated on the preference distribution 330.
Referring to FIG. 4 , after placement of first part, the object A is updated to be the combination of the build volume boundary and the placed first part, and the resulting preference distribution ƒ_{A} ^{d}(x) 430 shows preference to placing the second part near placed first part. A second part B has a shape represented by ƒ_{B} ^{c}(x) 422, which is defined relative to its origin 423. A suitable positioning of the second part B is then at the selected offset 433 illustrated on the preference distribution 430.
Referring to FIG. 5 , after placement of first and second parts, the object A is updated to be the combination of the build volume boundary and the placed parts, and the resulting preference distribution ƒ_{A} ^{d}(x) 530 shows preference to placing the third part near placed parts. A third part B has a shape represented by ƒ_{B} ^{c}(x) 522, which is defined relative to its origin 523. A suitable positioning of the second part B is then at the selected offset 533 illustrated on the preference distribution 530.
Referring to FIG. 6 , after placement of first, second and third parts, the object A is updated to be the combination of the build volume boundary and the placed parts, and the resulting preference distribution ƒ_{A} ^{d}(x) 630.
In some alternatives, a packing procedure uses a lower resolution (e.g., downsampled voxel representation) to determine initial placements, which can then be refined using higher resolution representations (e.g., by successively moving each placed part incrementally relative to the other placed parts, where the original geometry is used for collision detection.). For example, FIG. 9 shows an arrange of part B near part A found by low resolution voxels, while FIG. 10 shows a refinement of the arrangement at an original resolution in which the parts are able to be arranged more closely to one another.
Implementations of the approaches described above are amenable to parallelization, and more particularly to implementation on Graphics Processing Units (GPUs). For example, the Fourier Transform computations, as well as the search to locate best offsets for placements can be performed on a GPU.
While the approaches described above may be suitable to a box shaped build volume, arbitraryshaped build volume can also be supported. In this case, the bounding box of the build volume is first computed, any voxels that are outside of the specified build volume are marked as occupied. For example, a different fabrication system may use a cylindrical build volume. The minimum separation distance can be satisfied by simply expanding the object voxels. Furthermore, while described in the context of arranging parts in a build volume for 3D fabrication, the approaches can be used in variety 2D and 3D packing/arrangement problems, for example, for arranging packages for storage or shipment. Within the domain of 3D fabrication, the approaches can be used not only for jetted fabrication, but other printing approaches as well, for example, involving powderbased binder jetting/laser sintering. The packing approach can also be applied to 2D packing problems, for example, for CNC milling.
A number of embodiments of the invention have been described. Nevertheless, it is to be understood that the foregoing description is intended to illustrate and not to limit the scope of the invention, which is defined by the scope of the following claims. Accordingly, other embodiments are also within the scope of the following claims. For example, various modifications may be made without departing from the scope of the invention. Additionally, some of the steps described above may be order independent, and thus can be performed in an order different from that described.
Claims (18)
1. A method for arranging a plurality of parts into a build volume for threedimensional 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 threedimensional fabrication according to the arrangement; and
providing the build volume specification for use in a threedimensional fabrication system.
2. The method of claim 1 , wherein the specification of the shape comprises a voxel representation of locations occupied in the shape.
3. The method of claim 1 , further comprising determining spatial frequency domain representations of shapes of at least some parts of the plurality of parts.
4. 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.
5. 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.
6. A method for arranging a plurality of parts into a build volume for threedimensional 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 threedimensional fabrication according to the arrangement; and
providing the specification of the build volume for use in a threedimensional 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.
7. 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.
8. 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.
9. 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.
10. 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.
11. 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.
12. 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.
13. The method of claim 12 , further comprising determining a spatial frequency domain representation of the first part in each of the plurality of rotations.
14. 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.
15. 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.
16. A system for arranging a plurality of parts into a build volume for threedimensional 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 threedimensional fabrication according to the arrangement; and
provide the build volume specification for use in a threedimensional fabrication system.
17. The system of claim 16 , wherein at least some of the hardware processors comprise graphics processing units capable of parallel computations.
18. A nontransitory machinereadable 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 threedimensional fabrication according to the arrangement; and
provide the build volume specification for use in a threedimensional fabrication system.
Priority Applications (3)
Application Number  Priority Date  Filing Date  Title 

US17/955,843 US11897203B1 (en)  20220929  20220929  Frequency domain spatial packing for 3D fabrication 
PCT/US2023/034076 WO2024073024A1 (en)  20220929  20230929  Frequency domain spatial packing for 3d fabrication 
US18/520,791 US20240173925A1 (en)  20220929  20231128  Frequency domain spatial packing for 3d fabrication 
Applications Claiming Priority (1)
Application Number  Priority Date  Filing Date  Title 

US17/955,843 US11897203B1 (en)  20220929  20220929  Frequency domain spatial packing for 3D fabrication 
Related Child Applications (1)
Application Number  Title  Priority Date  Filing Date 

US18/520,791 Continuation US20240173925A1 (en)  20220929  20231128  Frequency domain spatial packing for 3d fabrication 
Publications (1)
Publication Number  Publication Date 

US11897203B1 true US11897203B1 (en)  20240213 
Family
ID=88600576
Family Applications (2)
Application Number  Title  Priority Date  Filing Date 

US17/955,843 Active US11897203B1 (en)  20220929  20220929  Frequency domain spatial packing for 3D fabrication 
US18/520,791 Pending US20240173925A1 (en)  20220929  20231128  Frequency domain spatial packing for 3d fabrication 
Family Applications After (1)
Application Number  Title  Priority Date  Filing Date 

US18/520,791 Pending US20240173925A1 (en)  20220929  20231128  Frequency domain spatial packing for 3d fabrication 
Country Status (2)
Country  Link 

US (2)  US11897203B1 (en) 
WO (1)  WO2024073024A1 (en) 
Citations (7)
Publication number  Priority date  Publication date  Assignee  Title 

US20180133969A1 (en) *  20150731  20180517  HewlettPackard Development Company, L.P.  Parts arrangement determination for a 3d printer build envelope 
US20200057030A1 (en) *  20151113  20200220  Honeywell Federal Manufacturing & Technologies, Llc  System and method for inspecting parts using dynamic response function 
US20200193716A1 (en) *  20161219  20200618  HewlettPackard Development Company, L.P.  Arrangement determination for 3d fabricated parts 
US20210039320A1 (en) *  20180427  20210211  HewlettPackard Development Company, L.P.  Userassisted parts packing optimization 
US20210162659A1 (en) *  20180817  20210603  HewlettPackard Development Company, L.P.  Packing a threedimensional build bed 
WO2021154244A1 (en) *  20200129  20210805  HewlettPackard Development Company, L.P.  Generation of an object model for three dimensional printers 
US20210283850A1 (en) *  20171215  20210916  HewlettPackard Development Company, L.P.  Parts packing for a build volume 
Family Cites Families (3)
Publication number  Priority date  Publication date  Assignee  Title 

US10252466B2 (en)  20140728  20190409  Massachusetts Institute Of Technology  Systems and methods of machine vision assisted additive fabrication 
EP3554798B1 (en)  20161216  20201202  Massachusetts Institute of Technology  Adaptive material deposition for additive manufacturing 
US10994490B1 (en)  20200731  20210504  Inkbit, LLC  Calibration for additive manufacturing by compensating for geometric misalignments and distortions between components of a 3D printer 

2022
 20220929 US US17/955,843 patent/US11897203B1/en active Active

2023
 20230929 WO PCT/US2023/034076 patent/WO2024073024A1/en unknown
 20231128 US US18/520,791 patent/US20240173925A1/en active Pending
Patent Citations (7)
Publication number  Priority date  Publication date  Assignee  Title 

US20180133969A1 (en) *  20150731  20180517  HewlettPackard Development Company, L.P.  Parts arrangement determination for a 3d printer build envelope 
US20200057030A1 (en) *  20151113  20200220  Honeywell Federal Manufacturing & Technologies, Llc  System and method for inspecting parts using dynamic response function 
US20200193716A1 (en) *  20161219  20200618  HewlettPackard Development Company, L.P.  Arrangement determination for 3d fabricated parts 
US20210283850A1 (en) *  20171215  20210916  HewlettPackard Development Company, L.P.  Parts packing for a build volume 
US20210039320A1 (en) *  20180427  20210211  HewlettPackard Development Company, L.P.  Userassisted parts packing optimization 
US20210162659A1 (en) *  20180817  20210603  HewlettPackard Development Company, L.P.  Packing a threedimensional build bed 
WO2021154244A1 (en) *  20200129  20210805  HewlettPackard Development Company, L.P.  Generation of an object model for three dimensional printers 
NonPatent Citations (6)
Title 

KatchalskiKatzir, Ephraim, Isaac Shariv, Miriam Eisenstein, Asher A. Friesem, Claude Aflalo, and Ilya A. Vakser. "Molecular surface recognition: determination of geometric fit between proteins and their ligands by correlation techniques." Proceedings of the National Academy of Sciences 89, No. 6 (1992): 21952199. 
Lysenko, Mikola, and Vadim Shapiro. "Effective contact measures." ComputerAided Design 70 (2016): 134143. 
Lysenko, Mikola, Saigopal Nelaturi, and Vadim Shapiro. "Group morphology with convolution algebras." In Proceedings of the 14th ACM symposium on solid and physical modeling, pp. 1122. 2010. 
Nelaturi, Saigopal, Mikola Lysenko, and Vadim Shapiro. "Rapid mapping and exploration of configuration space." (2012): 021007. 
Nelaturi, Saigopal, Morad Behandish, Amir M. Mirzendehdel, and Johan de Kleer. "Automatic support removal for additive manufacturing post processing." ComputerAided Design 115 (2019): 135146. 
Zhao et al., "A Comparative Review of 3D Container Loading Algorithms," International Transactions in Operational Research, pp. 139, 2014. 
Also Published As
Publication number  Publication date 

US20240173925A1 (en)  20240530 
WO2024073024A1 (en)  20240404 
Similar Documents
Publication  Publication Date  Title 

Fortune  Voronoi diagrams and Delaunay triangulations  
Hoppe et al.  Mesh optimization  
US8903693B2 (en)  Boundary handling for particlebased simulation  
Musialski et al.  Reducedorder shape optimization using offset surfaces.  
US6133921A (en)  Constructing shape skeletons of 3D objects using generalized Voronoi diagrams  
Ghosh  A mathematical model for shape description using Minkowski operators  
US8442805B2 (en)  Efficient computation of Voronoi diagrams of general generators in general spaces and uses thereof  
US20160096318A1 (en)  Three dimensional (3d) printer system and method for printing 3d objects with userdefined material parameters  
Tunkelang  A numerical optimization approach to general graph drawing  
Grebennik et al.  Combinatorial configurations in balance layout optimization problems  
EP1559060A2 (en)  Analysis of geometric surfaces by conformal structure  
US11847391B2 (en)  Computer system for simulating physical processes using surface algorithm  
Lozano et al.  An efficient algorithm to generate random sphere packs in arbitrary domains  
Cui et al.  Dense, InterlockingFree and Scalable Spectral Packing of Generic 3D Objects.  
US11897203B1 (en)  Frequency domain spatial packing for 3D fabrication  
Doškář et al.  Levelset based design of Wang tiles for modelling complex microstructures  
Vernengo et al.  Interactive design and variation of hull shapes: pros and cons of different CAD approaches  
Liu et al.  Automatic sizing functions for unstructured mesh generation revisited  
US8229247B1 (en)  Method and apparatus for structure preserving editing in computer graphics  
KR101682296B1 (en)  3 dimensional printer device and method for positioning 3 dimensional object  
Bole et al.  Integrating parametric hull generation into early stage design  
WO2019156947A1 (en)  System and method for design and manufacture of steady lattice structures  
Dorn et al.  Voxelbased General Voronoi Diagram for Complex Data with Application on Motion Planning  
Zhuang et al.  Dynamics simulationbased packing of irregular 3D objects  
US20060170688A1 (en)  Timedependent animation of a 3D object 
Legal Events
Date  Code  Title  Description 

FEPP  Fee payment procedure 
Free format text: ENTITY STATUS SET TO UNDISCOUNTED (ORIGINAL EVENT CODE: BIG.); ENTITY STATUS OF PATENT OWNER: SMALL ENTITY 

FEPP  Fee payment procedure 
Free format text: ENTITY STATUS SET TO SMALL (ORIGINAL EVENT CODE: SMAL); ENTITY STATUS OF PATENT OWNER: SMALL ENTITY 

STCF  Information on status: patent grant 
Free format text: PATENTED CASE 