Decomposition of 3D geometry into developable surface patches and 2D cut patterns

Patent metadata

Field	Value
Publication number	US-9619587-B2
Application number	US-201313859051-A
Country	US
Kind code	B2
Filing date	Apr 9, 2013
Priority date	Apr 9, 2012
Publication date	Apr 11, 2017
Grant date	Apr 11, 2017

Abstract

Embodiments disclosed herein provide techniques for decomposing 3D geometry into developable surface patches and cut patterns. In one embodiment, a decomposition application receives a triangulated 3D surface as input and determines approximately developable surface patches from the 3D surface using a variant of k-means clustering. Such approximately developable surface patches may have undesirable jagged boundaries, which the decomposition application may eliminate by generating a data structure separate from the mesh that contains patch boundaries and optimizing the patch boundaries or, alternatively, remeshing the mesh such that patch boundaries fall on mesh edges. The decomposition application may then flatten the patches into truly developable surfaces by re-triangulating the patches as ruled surfaces. The decomposition application may further flatten the ruled surfaces into 2D shapes and lay those shapes out on virtual sheets of material. A person, or machinery, may cut out those shapes from physical sheets of material based on the layout.

First claim

We claim:

1. A computer-implemented method for decomposing three-dimensional (3D) geometry into developable surface patches, comprising:
receiving the 3D geometry;
growing, via a processor, surface patches from faces in the 3D geometry until the surface patches become stabilized by:
selecting one or more seed faces, from the faces in the 3D geometry, as initializations of the surface patches, and
up to a distance threshold, iteratively adding faces to the surface patches, wherein, at each iteration, a face with minimum distance to a patch proxy is added to a patch associated with the patch proxy, wherein the patch proxy includes an axis and an opening angle,
wherein the surface patches become stabilized when, as a result of a particular iteration, less than a threshold amount of a total area of the faces in the 3D geometry is added to a surface patch or is reassigned to a different surface patch; and

cutting one or more physical sheets of material based on the faces of the surface patches.

2. The method of claim 1 , wherein growing surface patches further comprises, merging two patches if no face in the two patches has a distance to a second patch proxy greater than the distance threshold.

3. The method of claim 1 , wherein growing surface patches further comprises, if less than a threshold surface area remains unassigned to a patch, removing the distance threshold and growing patches until every face of the 3D geometry is assigned to a patch.

4. The method of claim 1 , wherein the distance between a given face and a proxy is measured as a difference between a cosine of the opening angle of the proxy and a dot product of a normal of the given face and the axis of the proxy.

5. The method of claim 1 , further comprising, optimizing patch boundaries by:
optimizing an energy by moving boundary points in a data structure which represents the patch boundaries as a set of the boundary points connected with springs; and
remeshing the 3D geometry such that the boundary points are vertices on the 3D geometry.

6. The method of claim 1 , further comprising, optimizing patch boundaries by, iteratively:
computing an energy gradient for each of a plurality of contour points;
moving the contour points in directions of negative energy gradients; and
identifying intersections between edges of the 3D geometry and the moved contour,
wherein the contour points lie on either an edge or a vertex of the 3D geometry.

7. The method of claim 1 , further comprising, flattening each surface patch into one of the developable surface patches by re-triangulating the surface patch as a ruled surface.

8. The method of claim 7 , further comprising,
flattening the developable surface patches into 2D shapes; and
determining a packing of the 2D shapes on a sheet.

9. The method of claim 8 , further comprising, removing pieces from a sheet of material based on the packing of the 2D shapes on the virtual sheet.

10. The method of claim 1 , wherein the seed faces are user-specified.

11. A non-transitory computer-readable storage medium storing instructions, which when executed by a computer system, perform operations for decomposing three-dimensional (3D ) geometry into developable surface patches, the operations comprising:
receiving the 3D geometry;
growing surface patches from faces in the 3D geometry until the surface patches become stabilized by:
selecting one or more seed faces, from the faces in the 3D geometry, as initializations of the surface patches, and
up to a distance threshold, iteratively adding faces to the surface patches, wherein, at each iteration, a face with minimum distance to a patch proxy is added to a patch associated with the patch proxy, wherein the patch proxy includes an axis and an opening angle,
wherein the surface patches become stabilized when, as a result of a particular iteration, less than a threshold amount of a total area of the faces in the 3D geometry is added to a surface patch or is reassigned to a different surface patch; and

cutting one or more physical sheets of material based on the faces of the surface patches.

12. The non-transitory computer-readable storage medium of claim 11 , wherein growing surface patches further comprises, merging two patches if no face in the two patches has a distance to a second patch proxy greater than the distance threshold.

13. The non-transitory computer-readable storage medium of claim 11 , wherein growing surface patches further comprises, if less than a threshold surface area remains unassigned to a patch, removing the distance threshold and growing patches until every face of the 3D geometry is assigned to a patch.

14. The non-transitory computer-readable storage medium of claim 11 , wherein the distance between a given face and a proxy is measured as a difference between a cosine of the opening angle of the proxy and a dot product of a normal of the given face and the axis of the proxy.

15. The non-transitory computer-readable storage medium of claim 11 , the operations further comprising, optimizing patch boundaries by:
optimizing an energy by moving boundary points in a data structure which represents the patch boundaries as a set of the boundary points connected with springs; and
remeshing the 3D geometry such that the boundary points are vertices on the 3D geometry.

16. The non-transitory computer-readable storage medium of claim 11 , the operations further comprising, optimizing patch boundaries by, iteratively:
computing an energy gradient for each of a plurality of contour points;
moving the contour points in directions of negative energy gradients; and
identifying intersections between edges of the 3D geometry and the moved contour,
wherein the contour points lie on either an edge or a vertex of the 3D geometry.

17. The non-transitory computer-readable storage medium of claim 11 , the operations further comprising, flattening each surface patch into one of the developable surface patches by re-triangulating the surface patch as a ruled surface.

18. The non-transitory computer-readable storage medium of claim 17 , the operations further comprising,
flattening the developable surface patches into 2D shapes; and
determining a packing of the 2D shapes on a sheet.

19. The non-transitory computer-readable storage medium of claim 18 , the operations further comprising, removing pieces from a sheet of material based on the packing of the 2D shapes on the virtual sheet.

20. A system, comprising:
a processor; and
a memory, wherein the memory includes an application program configured to perform operations for decomposing three-dimensional (3D ) geometry into developable surface patches, the operations comprising:
receiving the 3D geometry,
growing surface patches from faces in the 3D geometry until the surface patches become stabilized by:
selecting one or more seed faces, from the faces in the 3D geometry, as initializations of the surface patches; and
up to a distance threshold, iteratively adding faces to the surface patches, wherein, at each iteration, a face with minimum distance to a patch proxy is added to a patch associated with the patch proxy, wherein the patch proxy includes an axis and an opening angle,
wherein the surface patches become stabilized when, as a result of a particular iteration, less than a threshold amount of a total area of the faces in the 3D geometry is added to a surface patch or is reassigned to a different surface patch, and

cutting one or more physical sheets of material based on the faces of

Assignees

• Autodesk Inc

Inventors

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

Classifications

• G06F30/00 Primary

  Computer-aided design [CAD] · CPC title

• G06F2113/24

  Sheet material · CPC title

• G06F30/10 Primary

  Geometric CAD · CPC title

• G06F17/50 Primary

  Physics · mapped topic

• G06F2217/42

  Physics · mapped topic