Iterative packing optimization

• US 8,868,230 B2
• Filed: 04/26/2012
• Issued: 10/21/2014
• Est. Priority Date: 04/26/2012
• Status: Active Grant

• Current Assignee: Disney Enterprises Incorporated (The Walt Disney Company)
• Original Assignee: Disney Enterprises Incorporated (The Walt Disney Company)
• Inventors: McNaull, Patrick, Boyle, Bryant, Ngo, J. Thomas, Tschanz, Michael
• Primary Examiner(s): BORISSOV, IGOR N
• Application Number:
  US13/457,229
• Publication Number:
  US 20130290220A1
• Time in Patent Office: 908 Days
• Field of Search: 705/1.1, 705/7.11, 705/7.26, 705/7.35, 705/28, 705/29, 705/400, 703/1, 703/2, 703/7, 425/375, 715/243, 715/204, 715/255, 382/100, 382/173, 706/19, 534/52, 534/74, 700/96, 700/95, 700/217, 700/216, 700/171, 414/791.8, 414/801, 414/802
• US Class Current: 700/217
• CPC Class Codes: B29C 64/386 Data acquisition or data processing for additive manufacturing
• CPC Class Codes: B33Y 50/00 Data acquisition or data processing for additive manufacturing
• CPC Class Codes: G05B 19/4097 characterised by using design data to control NC machines, e.g. CAD/CAM G05B19/4093 takes precedence
• CPC Class Codes: G05B 2219/35162 Determine workpiece placement, nesting in blank, optimize, minimize loss material
• CPC Class Codes: G05B 2219/49023 3-D printing, layer of powder, add drops of binder in layer, new powder
• CPC Class Codes: G06F 30/00 Computer-aided design [CAD]

Abstract

An iterative method and system for performing the method are described that implement a technique to fit irregularly shaped items into a defined space. In particular, one example may take the form of a method including predetermining one or more layouts for a defined space. Each layout has a plurality of shapes. The method also includes receiving a set having a plurality of items and determining one or more configurations formed by assigning to each shape in the layout an item from the set. The items match the shapes to which they are assigned. Additionally, the method includes scoring each configuration and selecting one configuration based at least in part upon the scoring.

Claims

1. A method of placing items in a defined space of a 3-D print bed comprising:

predetermining one or more layouts for the defined space, each layout comprising a plurality of shapes;

maintaining a queue in a computer readable medium, the queue having an order of irregularly shaped items, each of the irregularly shaped items having at least one assigned characteristic;

determining at least two configurations of items within the defined space according to a selected metric by a processor, wherein the at least two configurations of items are determined by assigning to each shape in the one or more layouts an irregularly shaped item from the queue, the irregularly shaped item matching at least one of a plurality of irregularly shaped items identified as matching the shape to which the irregularly shaped item is assigned;

determining a relative rank of at least two of the configurations by the processor; and

selecting, at least in part based on the determined rank, a configuration, wherein the configuration conforms to the print bed for 3-D printing a subset of the irregularly shaped items in the queue.

2. The method of claim 1 wherein maintaining the queue comprises:

receiving irregularly shaped items into the queue; and

removing irregularly shaped items from the queue upon selecting the configuration, wherein the irregularly shaped items that are included in the subset are removed.

3. The method of claim 1, wherein determining at least two configurations comprises obtaining a binary representation of each of the irregularly shaped items.

4. The method of claim 3, wherein obtaining a binary representation comprises obtaining a top-down view of the irregularly shaped items.

5. The method of claim 3, wherein obtaining a binary representation comprises generating multiple two-dimensional slices of each of the irregularly shaped items.

6. The method of claim 1, wherein determining at least two configurations comprises:

collapsing a 3-D point cloud into a plane; and

identifying a boundary of the collapsed point cloud.

7. The method of claim 1, wherein determining a relative rank of at least two configurations comprises computing a cost to print using each of the at least two configurations.

8. The method of claim 7, wherein computing a cost comprises summing a height cost, a bin-occupancy cost, and a shipment delay cost for each configuration.

9. The method of claim 1, wherein the selected metric comprises one of:

a packing density metric, a minimum number of items metric, or a maximum cost metric.

13. The method of claim 1, wherein determining the relative rank of at least two of the configurations comprises obtaining a 3-D print quality degradation of each of the at least two configurations.

14. The method of claim 1, wherein determining the relative rank of at least two of the configurations comprises obtaining a future demand optimization of each of the at least two configurations.

10. A method comprising:

generating, by a processor, a plurality of layouts in a defined space of a 3-D print bed, wherein each of the layouts comprises a plurality of shapes;

receiving a set of irregularly shaped items;

generating a plurality of configurations of items by correlating irregularly shaped items from the set with the plurality of layouts, wherein each configuration is generated by assigning each shape in the plurality of layouts an irregularly shaped item from the subset that matches at least one of a plurality of shaped items identified as matching the shape to which the irregularly shaped item is assigned;

selecting one of the plurality of configurations;

generating a batch of irregularly shaped items by a 3-D printing process using the selected configuration; and

updating the set by removing irregularly shaped items generated in the batch from the set.

11. The method of claim 10, wherein generating a plurality of layouts comprises using a morphological technique.

12. The method of claim 11 further comprising using a genetic technique to maintain the plurality of layouts.