Nesting using rigid body simulation

Patent metadata

Field	Value
Publication number	US-10783289-B2
Application number	US-201715706614-A
Country	US
Kind code	B2
Filing date	Sep 15, 2017
Priority date	Sep 18, 2012
Publication date	Sep 22, 2020
Grant date	Sep 22, 2020

Abstract

Embodiments of the invention provide systems and methods for nesting objects in 2D sheets and 3D volumes. In one embodiment, a nesting application simplifies the shapes of parts and performs a rigid body simulation of the parts dropping into a 2D sheet or 3D volume. In the rigid body simulation, parts begin from random initial positions on one or more sides and drop under the force of gravity into the 2D sheet or 3D volume until coming into contact with another part, a boundary, or the origin of the gravity. The parts may be dropped according to a particular order, such as alternating large and small parts. Further, the simulation may be translation- and/or position-only, meaning the parts do not rotate and/or do not have momentum, respectively. Tighter packing may be achieved by incorporating user inputs and simulating jittering of the parts using random forces.

First claim

We claim:

1. A method implemented by a processor, the method comprising:
for each part included in a plurality of parts:
selecting a location at which to drop the part into a representation of a piece of material to use in manufacturing an object represented by the part, and
performing a simulation of dropping the part into the representation from the selected location; and

generating a nesting of the parts included in the plurality of parts based on the simulations to provide a pattern for manufacturing the objects from the piece of the material.

2. The method of claim 1 , further comprising simplifying the shapes of the parts included in the plurality of parts prior to performing the rigid-body simulation.

3. The method of claim 2 , wherein, for each part included in the plurality of parts, simplifying includes expanding concave regions of a polygon or mesh representing the part.

4. The method of claim 3 , further comprising decomposing each polygon or mesh into a union of convex pieces.

5. The method of claim 1 , further comprising jittering the parts included in the plurality of parts with random forces, and accepting a packing configuration after jittering the parts when a packing density of the parts in the representation increases.

6. The method of claim 5 , further comprises performing a simulated annealing, wherein a new configuration after jittering the parts and performing the simulated annealing is accepted based on a temperature value and a change in packing density.

7. The method of claim 1 , further comprising receiving user input repositioning a first part included in the plurality of parts, and, while performing at least one of the simulations, repositioning the first part according to the user input.

8. The method of claim 1 , wherein at least one of the simulations comprises a position-only simulation in which at least one of a momentum variable or a time variable is zero.

9. The method of claim 1 , wherein at least one simulation comprises a translation-only simulation in which at least one part is modeled as having infinite moments of inertia.

10. The method of claim 1 , wherein the representation includes holes that are modeled as obstacles in one or more of the simulations.

11. The method of claim 1 , wherein, across a plurality of the simulations, a first predefined number of large parts and a second predefined number of small parts are dropped interchangeably.

12. The method of claim 1 , wherein the piece of the material is a sheet of the material, and the representation is a two-dimensional (2D) representation of the sheet of the material.

13. The method of claim 1 , wherein the piece of the material is a volume of the material, and the representation is a three-dimensional (3D) representation of the volume of the material.

14. A non-transitory computer-readable medium including instructions that, when executed by a processor, configure the processor to perform the steps of:
for each part included in a plurality of parts:
selecting a location at which to drop the part into a two-dimensional (2D) representation or into a three-dimensional (3D) representation of a piece of material to use in manufacturing an object represented by the part, and
performing a simulation of dropping the part into the 2D representation or into the 3D representation from the selected location; and

generating a nesting of the parts included in the plurality of parts based on the simulations to provide a pattern for manufacturing the objects from the piece of the material.

15. The non-transitory computer-readable medium of claim 14 , further comprising simplifying the shapes of the parts included in the plurality of parts prior to performing the rigid-body simulation.

16. The non-transitory computer-readable medium of claim 15 , wherein, for each part included in the plurality of parts, simplifying includes expanding concave regions of a polygon or mesh representing the part.

17. The non-transitory computer-readable medium of claim 16 , further comprising decomposing each polygon or mesh into a union of convex pieces.

18. The non-transitory computer-readable medium of claim 14 , further comprising jittering the parts included in the plurality of parts with random forces, and accepting a packing configuration after jittering the parts when a packing density of the parts in the 2D representation or 3D representation increases.

19. The non-transitory computer-readable medium of claim 18 , further comprises performing a simulated annealing, wherein a new configuration after jittering the parts and performing the simulated annealing is accepted based on a temperature value and a change in packing density.

20. The non-transitory computer-readable medium of claim 14 , further comprising receiving user input repositioning a first part included in the plurality of parts, and, while performing at least one of the simulations, repositioning the first part according to the user input.

21. The non-transitory computer-readable medium of claim 14 , wherein at least one of the simulations comprises a position-only simulation in which at least one of a momentum variable or a time variable is zero.

22. The non-transitory computer-readable medium of claim 14 , wherein at least one simulation comprises a translation-only simulation in which at least one part is modeled as having infinite moments of inertia.

23. The non-transitory computer-readable medium of claim 14 , wherein the 2D representation or the 3D representation includes holes that are modeled as obstacles in one or more of the simulations.

24. The non-transitory computer-readable medium of claim 14 , wherein, across a plurality of the simulations, a first predefined number of large parts and a second predefined number of small parts are dropped interchangeably.

25. The non-transitory computer-readable medium of claim 14 , wherein the piece of the material is a sheet of the material.

26. The non-transitory computer-readable medium of claim 14 , wherein the piece of the material is a volume of the material.

27. A system, comprising:
a memory storing instructions; and
a processor that is coupled to the memory and, when executing the instructions, is configured to:
for each part included in a plurality of parts:
select a location at which to drop the part into a two-dimensional (2D) representation of a sheet of material to use in manufacturing an object represented by the part or into a three-dimensional (3D) representation of a volume of a material to use in manufacturing a 3D object represented by the part, and
perform a simulation of dropping the part into the 2D representation or into the 3D representation from the selected location, and

generate a nesting of the parts included in the plurality of parts based on the simulations to provide a pattern for manufacturing the objects from the sheet of the material or for manufacturing the 3D objects from the volume of the material.

Assignees

• Autodesk Inc

Inventors

• Griffith Saul
• Wicke Martin
• Pasko Keith
• Irving Geoffrey
• Calisch Samuel Eli
• Gilman Tucker
• Benoit Daniel
• Bachrach Jonathan

Classifications

• G06F2119/18

  Manufacturability analysis or optimisation for manufacturability · CPC title

• G06F2113/24

  Sheet material · CPC title

• G06F30/10

  Geometric CAD · CPC title

• G06F30/20 Primary

  Design optimisation, verification or simulation (optimisation, verification or simulation of circuit designs G06F30/30) · CPC title

• Y02P90/02

  Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS] · CPC title