Bin packing in 3d printers

Abstract

Disclosed herein is a technique to efficiently pack a print volume of 3D printers having print jobs with a large number of objects. The technique positions unique objects that adhere to a similar structural pattern more closely when the degree of variation between the objects is small. Thus, while each object is unique, a greater extent of similarity between the objects causes a given group of objects to be positioned more closely to one another in the print area of the 3D printer.

1 . A method comprising:
 generating a repeating orientation pattern for packing a plurality of digital 3D objects into a volume that represents a print region of a 3D printer, wherein generation of said repeating orientation pattern prioritizes volumetric efficiency in packing the plurality of digital 3D objects into the volume, wherein the plurality of digital 3D objects have in common a structural pattern, and wherein at least some of the plurality of digital 3D objects have a different size or shape from one another; and   assigning each of the plurality of digital 3D objects to a corresponding position in the repeating orientation pattern, wherein 3D digital objects are assigned positions in the repeating orientation pattern based on similarity of variation from the structural pattern.   
     
     
         2 . The method of  claim 1 , wherein said determining the repeating orientation pattern includes:
 simulating a plurality of orientation schemes of representative digital objects of the plurality of digital 3D objects in digital space, each orientation permutation including a number of the representative digital objects positioned respective of one another;   evaluating volumetric requirements for each orientation permutation; and   identifying an orientation scheme that prioritizes volumetric efficiency to use as the repeating orientation pattern.   
     
     
         3 . The method of  claim 2 , wherein said simulating is iterated a number of times, and wherein each iteration increases a number of the representative digital objects that are positioned respective of one another. 
     
     
         4 . The method of  claim 1 , further comprising:
 assigning each of the plurality of digital 3D objects to a like subset of a plurality of like subsets, wherein a like subset is a subset of the plurality of digital 3D objects including a number of digital 3D objects found in an iteration of the repeating orientation pattern; and   wherein said assigning each of the plurality of digital 3D objects to the corresponding position in the repeating orientation pattern is performed by positioning the plurality of like subset as a unit, one like subset at a time.   
     
     
         5 . The method of  claim 1 , further comprising:
 sorting each of the plurality of digital 3D into pairs based on similarity of variation from the structural pattern between a first digital 3D object and a second digital 3D object included in each pair respectively; and   wherein said assigning each of the plurality of digital 3D objects to the corresponding position in the repeating orientation pattern is performed by positioning each of the pairs as a unit, one pair at a time.   
     
     
         6 . The method of  claim 1 , further comprising:
 sorting the plurality of digital 3D objects in order of placement into the volume corresponding to a print region of a 3D printer based on adherence to the repeating orientation pattern.   
     
     
         7 . The method of  claim 1 , wherein the position in the repeating orientation pattern includes a spatial location in the volume corresponding to a print region of a 3D printer and a particular print cycle of the 3D printer. 
     
     
         8 . The method of  claim 1 , wherein the repeating orientation pattern is a column of digital 3D objects stacked one on top of another in parallel alignment, and the repeating orientation pattern is repeated within the volume corresponding to a print region of a 3D printer a number of times. 
     
     
         9 . The method of  claim 1 , wherein the repeating orientation pattern is stacking digital 3D objects one on top of another in parallel alignment and alternating descending and ascending width of stacks. 
     
     
         10 . The method of  claim 1 , wherein each respective digital 3D object includes a partner 3D object that is complementary to the respective digital 3D object and is included within the same print cycle. 
     
     
         11 . The method of  claim 1 , further comprising:
 determining a geometric profile of the structural pattern and a common style of deviation from the structural pattern across the plurality of digital 3D objects.   
     
     
         12 . The method of  claim 11 , wherein said determining the repeating orientation pattern is based on the geometric profile of the structural pattern and the common style of deviation from the structural pattern. 
     
     
         13 . The method of  claim 12 , wherein the geometric profile or deviation from the structural pattern is used to match convex surfaces of digital 3D objects to concave surfaces of adjacent digital 3D objects. 
     
     
         14 . The method of  claim 1 , wherein the repeating orientation pattern extends across a number of print cycles of the 3D printer. 
     
     
         15 . The method of  claim 14 , wherein each digital 3D object includes metadata describing a non-geometric parameter, and said assigning each of the plurality of digital 3D objects to the corresponding position in the repeating orientation pattern is further based on a similarity between the non-geometric parameter across the plurality of digital 3D objects. 
     
     
         16 . The method of  claim 1 , wherein 3D digital objects that have greater similarity of variation from the structural pattern are assigned positions in the repeating orientation pattern more proximate to one another than 3D digital objects that have lesser similarity of variation from the structural pattern.
 assigning each of the plurality of digital 3D objects to a corresponding position   
     
     
         17 . A method comprising:
 pairing a first digital object and a second digital object of a plurality of 3D digital objects, wherein the plurality of 3D digital objects have in common a structural pattern and vary in shape or size from one another, and said pairing is in response to a determination that the first digital object and the second digital object satisfy a specified shape or size similarity criterion relative to each other; and   positioning the first digital object adjacent to the second digital object in a volume corresponding to a print region of a 3D printer.   
     
     
         18 . The method of  17 , wherein said positioning is according to a specified repeating orientation pattern. 
     
     
         19 . A system comprising:
 a memory that stores a 3D print volume for use by a 3D printer; and   a processor configured to access data representing a plurality of digital 3D objects to be 3D printed, all of the plurality of digital 3D objects having in common a structural pattern, at least some of the plurality of digital 3D objects differing from each other in size or shape, the processor further configured to define a plurality of groups of the digital 3D objects, such that all of the 3D digital objects within each group satisfy a specified similarity criterion, relative to each other, for variation from the structural patter, the processor further configured to assign each of the plurality of digital 3D objects to a corresponding position in the 3D print volume, according to a repeating orientation pattern, based on the defined plurality of groups.   
     
     
         20 . The system of  claim 19 , wherein the processor is further configured to determine the repeating orientation pattern by:
 simulate a plurality of orientation permutations of representative digital objects of the plurality of digital 3D objects in digital space, each orientation permutation including a number of the representative digital objects positioned respective of one another;   evaluate volumetric requirements for each orientation permutation;   identify an orientation scheme that prioritizes volumetric efficiency to use as the repeating orientation pattern.   
     
     
         21 . The system of  claim 19 , where the processor is further configured to determine a geometric profile of the structural pattern and a common style of deviation from the structural pattern across the plurality of digital 3D objects. 
     
     
         22 . The system of  claim 21 , wherein said determination of the repeating orientation pattern is based on the geometric profile of the structural pattern and the common style of deviation from the structural pattern. 
     
     
         23 . The system of  claim 22 , wherein the geometric profile or deviation from the structural pattern is used to match convex surfaces of digital 3D objects to concave surfaces of adjacent digital 3D objects.