Nesting using rigid body simulation

Patent metadata

Field	Value
Publication number	US-9767233-B2
Application number	US-201615351302-A
Country	US
Kind code	B2
Filing date	Nov 14, 2016
Priority date	Sep 18, 2012
Publication date	Sep 19, 2017
Grant date	Sep 19, 2017

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 computer-implemented method for generating a manufacturing pattern for a plurality of parts, the method comprising:
performing, via a processor, a rigid-body simulation for the plurality of parts, wherein, for each part included in the plurality of parts, the rigid-body simulation comprises:
selecting a location at which to drop the part into a two-dimensional (2D) sheet geometry or into a three-dimension (3D) volume geometry, wherein the 2D sheet geometry represents a sheet of a material to be used to manufacture an object represented by the part, and wherein the 3D volume geometry represents a volume of a material to be used to manufacture a 3D object represented by the part, and
performing a simulation of dropping the part into the 2D sheet geometry or into the 3D volume geometry from the selected location; and

generating, via the processor, a nesting of the parts based on the simulations, wherein the nesting of parts provides a pattern for manufacturing the objects represented by the plurality of parts from the sheet of the material or for manufacturing the 3D objects represented by the plurality of parts from the volume of the material.

2. The computer-implemented 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 computer-implemented 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, and wherein each polygon or mesh is further decomposed into a union of convex pieces after the simplification.

4. The computer-implemented method of claim 1 , wherein performing the rigid-body simulation further comprises:
jittering the parts included in the plurality of parts with random forces; and
accepting a packing configuration after jittering the parts if a packing density of the parts in the 2D sheet geometry or 3D volume geometry increases.

5. The computer-implemented method of claim 4 , wherein performing the rigid-body simulation 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.

6. The computer-implemented method of claim 1 , further comprising:
receiving user input repositioning a first part included the plurality of parts; and
while performing the rigid-body simulation, repositioning the first part according to the user input.

7. The computer-implemented method of claim 1 , wherein the rigid-body simulation comprises a position-only simulation for at least one part included in the plurality of parts in which at least one of a momentum variable and a time variable is zero.

8. The computer-implemented method of claim 1 , wherein the rigid-body simulation comprises a translation-only simulation for at least one part included in the plurality of parts in which the at least one part is modeled as having infinite moments of inertia.

9. The computer-implemented method of claim 1 , wherein the 2D sheet geometry or the 3D volume geometry includes holes that are modeled as obstacles in the rigid-body simulation.

10. The computer-implemented method of claim 1 , wherein, in the rigid-body simulation, a first predefined number of large parts and a second predefined number of small parts are dropped interchangeably.

11. A non-transitory computer-readable storage medium including instructions that, when executed by a processor, configure the processor to perform the steps of:
performing a rigid-body simulation for a plurality of parts, wherein, for each part included in the plurality of parts, the rigid-body simulation comprises
performing one or more operations to simulate dropping the part into a two-dimensional (2D) sheet geometry or into a three-dimension (3D) volume geometry, wherein the 2D sheet geometry represents a sheet of a material to be used to manufacture an object represented by the part, and wherein the 3D volume geometry represents a volume of a material to be used to manufacture a 3D object represented by the part; and

generating a nesting of the parts based on the simulation, wherein the nesting of parts provides a pattern for manufacturing the objects represented by the plurality of parts from the sheet of the material or for manufacturing the 3D objects represented by the plurality of parts from the volume of the material.

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

13. The non-transitory computer-readable storage medium of claim 12 , wherein, for each part included in the plurality of parts, simplifying includes expanding concave regions of a polygon or mesh representing the part, and wherein each polygon or mesh is further decomposed into a union of convex pieces after the simplification.

14. The non-transitory computer-readable storage medium of claim 11 , wherein performing the rigid-body simulation further comprises:
jittering the parts included in the plurality of parts with random forces; and
accepting a packing configuration after jittering the parts if a packing density of the parts in the 2D sheet geometry or 3D volume geometry increases.

15. The non-transitory computer-readable storage medium of claim 14 , wherein performing the rigid-body simulation 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.

16. The non-transitory computer-readable storage medium of claim 11 , further comprising:
receiving user input repositioning a first part included the plurality of parts; and
while performing the rigid-body simulation, repositioning the first part according to the user input.

17. The non-transitory computer-readable storage medium of claim 11 , wherein the rigid-body simulation comprises a position-only simulation for at least one part included in the plurality of parts in which at least one of a momentum variable and a time variable is zero.

18. The non-transitory computer-readable storage medium of claim 11 , wherein the rigid-body simulation comprises a translation-only simulation for at least one part included in the plurality of parts in which the at least one part is modeled as having infinite moments of inertia.

19. The non-transitory computer-readable storage medium of claim 11 , wherein the 2D sheet geometry or the 3D volume geometry includes holes that are modeled as obstacles in the rigid-body simulation.

20. The non-transitory computer-readable storage medium of claim 11 , wherein, in the rigid-body simulation, a first predefined number of large parts and a second predefined number of small parts are dropped interchangeably.

21. A system, comprising:
a memory storing instructions; and
a processor that is coupled to the memory and, when executing the instructions, is configured to:
perform a simulation for a plurality of parts, wherein, for each part included in the plurality of parts, the simulation comprises
performing one or more operations to simulate dropping the part into a two-dimensional (2D) sheet geometry or into a three-dimension (3D) volume geometry; and

generate a nesting of the parts based on the simulation, w

Assignees

• Autodesk Inc

Inventors

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

Classifications

• G06F30/00

  Computer-aided design [CAD] · CPC title

• G06F2119/18

  Manufacturability analysis or optimisation for manufacturability · CPC title

• G06F30/20 Primary

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

• G06F2113/24

  Sheet material · CPC title

• G06F2217/12

  Physics · mapped topic