Nesting using rigid body simulation

Patent metadata

Field	Value
Publication number	US-9495484-B2
Application number	US-201314029353-A
Country	US
Kind code	B2
Filing date	Sep 17, 2013
Priority date	Sep 18, 2012
Publication date	Nov 15, 2016
Grant date	Nov 15, 2016

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 for nesting a plurality of parts, comprising:
receiving the plurality of parts, each part including geometry which represents a 2D or 3D object which is to be manufactured from a material; and
performing a rigid body simulation to generate the nesting of the parts, the rigid body simulation comprising, for each of one or more of the parts:
selecting a location for dropping the part into 2D sheet geometry or 3D volume geometry which represents a sheet or volume of the material, respectively, and
simulating a dropping of the part into the 2D sheet geometry or 3D volume geometry from the selected location,

wherein the nesting of the parts provides a pattern for manufacturing the 2D or 3D objects represented by the parts from the sheet or volume of the material.

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

3. The method of claim 2 , wherein the 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 method of claim 1 , the rigid body simulation further comprising:
jittering the parts with random forces; and
accepting a packing configuration after the jittering if a packing density of the parts in the 2D sheet geometry or 3D volume geometry increases.

5. The method of claim 4 , the rigid body simulation further comprising, performing a simulated annealing, wherein the new configuration after the jittering and the simulated annealing is accepted based on a temperature value and a change in packing density.

6. The method of claim 1 , further comprising:
receiving user input repositioning one of the parts; and
while performing the rigid body simulation, repositioning the one of the parts according to the user input.

7. The method of claim 1 , wherein the rigid body simulation is a position-only simulation for the one or more parts in which at least one of momentum variables and a time variable is zero.

8. The method of claim 1 , wherein the rigid body simulation is a translation-only simulation for the one or more parts in which the one or more parts are modeled as having infinite moments of inertia.

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

10. The 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 storing instructions, which when executed by a computer system, perform operations for nesting a plurality of parts, the operations comprising:
receiving the plurality of parts, each part including geometry which represents a 2D or 3D object which is to be manufactured from a material; and
performing a rigid body simulation to generate the nesting of the parts, the rigid body simulation comprising, for each of one or more of the parts:
selecting a location for dropping the part into 2D sheet geometry or 3D volume geometry which represents a sheet or volume of the material, respectively, and
simulating a dropping of the part into the 2D sheet geometry or 3D volume geometry from the selected location,

wherein the nesting of the parts provides a pattern for manufacturing the 2D or 3D objects represented by the parts from the sheet or volume of the material.

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

13. The computer-readable storage medium of claim 11 , wherein the 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 computer-readable storage medium of claim 11 , the rigid body simulation further comprising:
jittering the parts with random forces; and
accepting a packing configuration after the jittering if a packing density of the parts in the 2D sheet geometry or 3D volume geometry increases.

15. The computer-readable storage medium of claim 14 , the rigid body simulation further comprising, performing a simulated annealing, wherein the new configuration after the jittering and the simulated annealing is accepted based on a temperature value and a change in packing density.

16. The computer-readable storage medium of claim 11 , the operations further comprising:
receiving user input repositioning one of the parts; and
while performing the rigid body simulation, repositioning the one of the parts according to the user input.

17. The computer-readable storage medium of claim 11 , wherein the rigid body simulation is a position-only simulation for the one or more parts in which at least one of momentum variables and a time variable is zero.

18. The computer-readable storage medium of claim 11 , wherein the rigid body simulation is a translation-only simulation for the one or more parts in which the one or more parts are modeled as having infinite moments of inertia.

19. The 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.

20. A system, comprising:
a processor; and
a memory, wherein the memory includes an application program configured to perform operations for estimating a state-space controller from a set of video frames, the operations comprising:
receiving the plurality of parts, each part including geometry which represents a 2D or 3D object which is to be manufactured from a material, and
performing a rigid body simulation to generate the nesting of the parts, the rigid body simulation comprising, for each of one or more of the parts:
selecting a location for dropping the part into 2D sheet geometry or 3D volume geometry which represents a sheet or volume of the material, respectively; and
simulating a dropping of the part into the 2D sheet geometry or 3D volume geometry from the selected location;

wherein the nesting of the parts provides a pattern for manufacturing the 2D or 3D objects represented by the parts from the sheet or volume of the material.

Assignees

• Autodesk Inc
• Autodesk Llp

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/42

  Physics · mapped topic