Fabrication of free form structures from planar materials

• US 6,819,966 B1
• Filed: 12/06/2003
• Issued: 11/16/2004
• Est. Priority Date: 12/06/2003
• Status: Expired due to Fees

• Current Assignee: Paul E. Haeberli
• Original Assignee: Paul E. Haeberli
• Inventors: Haeberli, Paul E.
• Primary Examiner(s): Von Buhr, Maria N.
• Application Number:
  US10/730,391
• Time in Patent Office: 346 Days
• Field of Search: 345/418-420, 345/441-443, 345/619-622, 345/964, 700/95-98, 700/117, 700/118, 700/180-185, 703/1, 703/2
• US Class Current: 700/98
• CPC Class Codes: G06F 30/00 Computer-aided design [CAD]
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics
• CPC Class Codes: G06T 2219/021 Flattening
• CPC Class Codes: G06T 2219/2008 Assembling, disassembling
• CPC Class Codes: Y10S 715/964 CAD or CAM, e.g. interactive design tools

Abstract

A free form source model is divided into surface sections by identifying external boundary edges and internal boundary edges. The boundaries are connected or further divided as necessary to achieve a perimeter about each surface section which is a single closed curve. Doubly curved surfaces may also be subdivided. A developable output surface which approximates each source model surface section is then determined by calculating the minimum cost triangulation of each source model perimeter. Costs to be minimized may include the deviation of the triangle surface normal from the edge normal, the degree of bending between adjacent triangles, or the departure of the approximated surface from the original surface. The two-dimensional boundary of the flattened surface guides fabrication of output segments from sheet material, which may be assembled into an output object comprised entirely of developable surfaces.

Claims

1. A method for producing an output surface composed of developable surface elements corresponding to a three-dimensional source model surface, comprising the steps of:

identifying boundaries on the source model surface which divide the source model surface into at least one surface section such that each surface section is bounded by a single closed curve which defines a surface section perimeter;

representing each surface section perimeter by a plurality of vertices positioned along the surface section perimeter to define a perimeter polygon;

for each of the at least one surface section, examining a plurality of possible divisions of the surface section into triangles which connect the vertices of the perimeter polygon, and assigning costs to each of the plurality of possible divisions based on a function which relates individual triangles to each other, or to some characteristic of the source surface, or both, and comparing the costs of each of said plurality of possible divisions to determine the optimal triangulation of each perimeter polygon, each triangulation corresponding to a developable surface which has the perimeter polygon as a perimeter;

using each optimal triangulation to define a perimeter of a flattened output surface element; and

outputting instructions for fabricating from a sheet material each output surface element to have the defined perimeter of the output surface element.

2. The process of claim 1 wherein the step of identifying boundaries on the source model surface further comprises the step of identifying surface sections that have a plurality of closed curves, and connecting the closed curves to form a single closed curve.

3. The process of claim 1 wherein the step of identifying boundaries on the source model surface further comprises the step of identifying those surface sections which have surfaces which are doubly curved, and dividing said surface sections by at least one line which extends inwardly from the perimeter and returns to the perimeter and extends along the original surface section.

4. The process of claim 1 further comprising the steps of:

cutting the plurality of segments from sheet material; and

assembling the plurality of segments to form an output object.

5. The process of claim 1 wherein the step of outputting instructions comprises printing lines on the definite material.

6. The process of claim 1 wherein the step of examining a plurality of possible divisions of the surface section into triangles comprises examining substantially all possible divisions.

7. The process of claim 1 wherein the step of assigning costs to each of the plurality of possible divisions includes the step of determining a bend cost between adjacent triangles by carrying out the steps of:

determining the surface normal of each triangle within a possible division; and

comparing the differences in the surface normals between each pair of adjacent triangles, and assigning costs to a possible division according to the degree of difference between surface normals.

8. The process of claim 7 wherein the bend cost between two adjacent triangles is determined such that the surface normal of a first triangle is {right arrow over (N)}₁, and the surface normal of second triangle which is adjacent to the first triangle along an edge e is {right arrow over (N)}₂, and the bend cost BendCost is determined according to the following relationship, where f is a function of length(e) and BendDelta:

9. The process of claim 1 wherein the step of assigning costs to each of the plurality of possible divisions includes the step of determining an edge cost for the edges of each triangle within a triangulation which lie on the perimeter polygon by carrying out the steps of:

determining surface normals of the source model surface section at each vertex along the perimeter polygon;

dividing the sum of the edge normals at vertices on each end of an edge under consideration, by the sum of the edge normal magnitudes to determine an average edge normal; and

assigning a cost by multiplying the length of the edge under consideration times the average difference between the average edge normal and the surface normal of the triangle.

10. The method of claim 1 wherein the step of outputting instructions includes outputting instructions to form surface element identifying numbers which project from each surface element.

11. A method for producing an output surface composed of at least one developable surface element corresponding to a three-dimensional source model surface, comprising the steps of:

identifying boundaries on the source model surface which divide the source model surface into at least one surface section such that each surface section is bounded by a single closed curve which defines a surface section perimeter;

representing each surface section perimeter by a plurality of vertices positioned along the surface section perimeter to define a perimeter polygon;

examining a plurality of alternative divisions of at least one surface section into triangles which connect the vertices of the perimeter polygon, and assigning costs to each of the plurality of alternative divisions such that a better approximation to the source model surface section has a lower cost, and selecting a lowest cost division of the surface section into a plurality of triangles in which at least one suspended triangle extends between vertices on the perimeter polygon such that said suspended triangle has only chords extending between vertices but no edges lying on the perimeter polygon;

flattening each output perimeter polygon optimal triangulation to define a planar output surface element perimeter; and

outputting instructions for a cutting tool for fabricating from a planar material each output surface element by cutting along its output surface element perimeter.

12. The process of claim 11 wherein the step of identifying boundaries on the source model surface further comprises the step of identifying surface sections that have a plurality of closed curves, and connecting the closed curves to form a single closed curve.

13. The process of claim 11 wherein the step of identifying boundaries on the source model surface further comprises the step of identifying those surface sections which have surfaces which are doubly curved, and dividing said surface sections by at least one line which extends inwardly from the perimeter and returns to the perimeter and extends along the original surface section, wherein the at least one dividing line begins at a first point and terminates at a second point which is either identical to the first point or spaced from the first point along the perimeter.

14. The process of claim 11 further comprising the steps of:

cutting the plurality of segments from planar material; and

assembling the plurality of segments to form an output object.

15. A process for forming an output object assembled from sheet elements, the output object having a surface which approximates the surface of a source model, comprising the steps of:

dividing the source model surface into a plurality of surface sections;

identifying the perimeter of each surface section;

approximating each surface section perimeter with a perimeter polygon comprised of a plurality of vertices which lie on said surface section perimeter and which are connected by line segments;

determining a low cost triangulation of each perimeter polygon by comparing a first triangulation to at least one second different triangulation, wherein a cost is determined for each triangulation by applying a function which compares an attribute of each triangle of a possible triangulation with a like attribute of an adjacent triangle of said possible triangulation, or with an attribute of one or more vertices of said triangle on the source model surface section;

flattening the determined low cost triangulations of all the perimeter polygons;

outputting the flattened triangulations as sheet elements; and

assembling the output sheet elements to form the output object.

16. The process of claim 15 wherein in the step of determining a cost for each triangulation as a function of comparing an attribute of each triangle, the attribute is selected from the group consisting of triangle surface normal, triangle surface area, and combined triangle edge length.

17. The process of claim 15 wherein the cost is determined for each triangulation as a function of one or more of the following attributes:

the maximum or minimum angle defined within a triangle;

the combined length of the edges of a triangle;

the surface area of a triangle;

the difference in surface normal between the triangle and an adjacent triangle;

the difference in surface normal between the triangle and some function of the surface normals of the vertices on the source model surface section; and

the difference in position between the surface of the triangle and the source model surface section defined between the vertices of the triangle.

18. A method for producing an output surface composed of developable surface elements corresponding to an arbitrary three-dimensional source model surface, comprising the steps of:

identifying boundaries on the source model surface which divide the source model surface into surface sections such that each surface section is bounded by a single closed curve which defines a surface section perimeter;

for each surface section perimeter, selecting a plurality of vertices spaced along the surface section perimeter, the plurality of vertices defining a perimeter polygon, and each vertex lying on the source model surface section;

searching for an optimal triangulation comprised of a set of triangles which do not overlap, and which are connected along triangular sides, wherein each triangle has three vertices which are vertices of the perimeter polygon, the triangulation defining a surface which fills the perimeter polygon, wherein the step of searching for an optimal triangulation comprises;

performing an analysis of at least two different triangulations by using a first function applied to each triangle of the analyzed triangulation to determine a value of the first function for said analyzed triangulation, the optimal triangulation being that one of the at least two different triangulations which has the lowest value, wherein the first function is a function which relates an attribute of each triangle of an analyzed triangulation to an attribute of the source model surface, or to an attribute of an adjacent triangle;

flattening each optimal triangulation by bringing each triangle of the set of triangles into the same plane by rotation about edges shared by triangles to define a planar output surface element perimeter; and

outputting instructions for a cutting tool for fabricating from a planar material each output surface element by cutting along its output surface element perimeter.

19. The method of claim 18 wherein the first function is a function which relates an attribute of each triangle of an analyzed triangulation to an attribute of the source model surface section, and the searching for an optimal triangulation further comprises applying a second function which relates an attribute of each triangle of an analyzed triangulation to an attribute of an adjacent triangle.

20. The method of claim 18 wherein the first function comprises determining a bend value between adjacent triangles by determining the surface normal of each triangle and comparing the differences in the surface normals between each pair of adjacent triangles.

21. The process of claim 18 wherein the first function comprises determining an edge cost for the edges of each triangle within a triangulation which lie on the perimeter polygon by carrying out the steps of:

determining surface normals of the source model surface section at each vertex along the perimeter polygon;

dividing the sum of the edge normals at vertices on each end of an edge under consideration, by the sum of the edge normal magnitudes to determine an average edge normal; and

assigning a cost by multiplying the length of the edge under consideration times the average difference between the average edge normal and the surface normal of the triangle.

22. The method of claim 18 wherein the step of searching for an optimal triangulation further comprises evaluating all the possible triangulations and selecting the triangulation in which the first function is at a minimum.

23. The method of claim 18 wherein the first function is a function of one or more of the following attributes:

the maximum or minimum angle defined within a triangle;

the combined length of the edges of a triangle;

the surface area of a triangle;

the difference in surface normal between the triangle and an adjacent triangle;

the difference in surface normal between the triangle and some function of the surface normals of the vertices on the source model surface section; and

the difference in position between the surface of the triangle and the source model surface section defined between the vertices of the triangle.

24. A method for creating a set of at least one developable surface patch corresponding to a three-dimensional source model surface, comprising the steps of:

identifying boundaries on the source model surface to identify a surface section bounded by a single closed curve which defines a surface section perimeter;

representing the surface section perimeter by a plurality of vertices positioned along the surface section perimeter to define a perimeter polygon;

examining a plurality of possible divisions of the surface section into triangles which connect the vertices of the perimeter polygon, and assigning costs to each of the plurality of possible divisions based on a function which relates individual triangles to each other, or to some characteristic of the source surface or both, and comparing the costs of each of said plurality of possible divisions, this comparison serving to determine an optimal triangulation of the perimeter polygon, the optimal triangulation corresponding to a developable surface which has the perimeter polygon as a perimeter; and

deriving the set of at least one developable surface patch corresponding to the optimal triangulation.

25. The method of claim 24 wherein the determined optimal triangulation has at least one suspended triangle which extends between vertices on the perimeter polygon such that said suspended triangle has only chords extending between vertices but no edges lying on the perimeter polygon.

26. The method of claim 25 wherein the step of deriving the at least one developable surface patch comprises defining a separate developable surface patch corresponding to each suspended triangle found in the optimal triangulation.

27. The method of claim 24 wherein the step of denying the at least one developable surface patch comprises defining at least one NURBS patch.