________________________________________________________________

* PI Phone Number: (617) 253-4555

* PI Fax Number: (617) 253-8125

* PI Street Address: MIT Room 5-428, 77 Massachusetts Avenue

* PI City,State,Zip: Cambridge, MA 02139-4307

* PI E-mail Address: nmp@mit.edu, sachs@mit.edu

* Grant/Contract Number: N00014-96-1-0857

* Period of Performance: 5/15/97 - 9/30/99

_________________________________________________________________

* Number of refereed papers submitted not yet published: 0

* Number of refereed papers published: 1

* Number of unrefereed reports and articles: 3

* Number of books or parts thereof submitted but not published:0

* Number of books or parts thereof published:0

* Number of project presentations: 10

* Number of patents filed but not yet granted: 0

* Number of patents granted and software copyrights: 5

* Number of graduate students supported >= 25% of full time: 2

* Number of post-docs supported >= 25% of full time: 1

* Number of minorities supported: 0

_________________________________________________________________

The objective of our work is to identify barriers to and propose solutions for the representation, design, and information processing of models consisting of graded material. The motivation for this work comes from the capability of some Solid Freeform Fabrication (SFF) process, such as 3D Printing, to locally control the composition of a part as it is fabricated (similar to color ink-jet printing, except in 3D). One of the major obstacles to realizing this potential is the lack of an information pathway from the designer's intent to the fabrication of the part.

Initially, there are two major issues to solving this problem: (1) representation of graded material models and (2) the processing of graded material models. To address the former, we have explored the possibilities of decomposing models into sub-regions, to which material information is attached. Two data structures for representing this information have been considered: a finite element based approach (a tetrahedral mesh interpolating nodes with material information) and a generalized decomposition approach (extending the concepts for B-rep modeling with explicit topology to cellular modeling with compositions over regions). For the latter issue, the processing of models, the paradigm set by image processing is followed. We treat the initial model as an ideal, piecewise continuous representation of an object with graded composition. This data is then sampled and filtered into discrete material primitives (similar to how color images are processed for display or hardcopy output) for fabrication through 3D Printing.

_________________________________________________________________

Technical progress in this project has involved identifying an information pathway from the designer to the manufacturing process and proposing and testing solutions to make this pathway efficient. A prototype system has been developed and tested with the fabrication of several visualization models, in which colored binder was used to represent the graded material in the fabricated object.

To convey information about a design from the designer to the manufacturing machine, a pathway for information flow has been defined and developed in prototype form. The pathway begins with the capture of the designer's geometric intent through a commercial CAD system. The model is then meshed into tetrahedral elements using a commercial meshing package. This tetrahedral representation is then loaded into a composition design module, through which the designer assigns material information to the model. With the material design complete, the model is sliced into layers of triangular meshes. These layers, with their associated material information, are processed into machine instructions to drive the process.

The information flow begins with the capture of the designer's intent for a model with graded composition. To address this issue, a solid modeling method known as the Cell-Tuple data structure was implemented to provide a relational data base between the topological cells of the model: vertices, edges, faces, and regions. Geometric and material information of the corresponding dimension was associated with each cell to define the shape and composition of the object. Initially, the prototype modeler is implemented with only point, line, triangle, and tetrahedron definitions, with the composition described in terms of Bézier formulations. With the restriction of working with exclusively tetrahedral meshes, the use of a general, relational database for the topology was deemed too expensive. A second modeling method based on a finite element data structure was implemented, in which a set of tetrahedral elements interpolate nodes in space with associated material information. To further address the issue of memory requirements, analysis of different data structures has been conducted to determine the optimal method to capture the designer's intent. The results of this analysis lead us to the conclusion that a generalized data structure, extending the concepts of B-rep modelers to include graded material information, is the most memory efficient in terms representing a designer's intent accurately.

Along with the underlying representation of graded material models, algorithms for design and interrogation have been explored. Methods to assign composition information based on distance functions have been implemented. A designer can "design" an intended variation for the composition as a function of distance from a point, line, plane, of a collection of triangles (defined by the object's boundary, for instance). The values for the nodes in the model are then automatically assigned according to their computed distance from the boundary. To further improve upon the performance of these algorithms, a bucket sorting algorithm has been implemented for efficiently computing the distance of nodes to a set of triangles. Our investigation shows a considerable improvement in processing time for a bucket sorted assignment when compared to an exhaustive search approach to designing compositions.

Once a model is designed, it must be processed into machine instructions. This begins with the slicing of the model into layers of triangular meshes. Each layer is then filtered into machine instructions. To perform this filtering, a halftoning technique from image processing has been adapted for 3D graded material information. Compositions over the layers are sampled and compared to a 3D threshold lattice. A binary representation approximating the original, continuous tone values, is output which is then translated into machine instructions for fabrication. The 3D threshold lattice is defined according to a newly developed algorithm, extending the Bayer algorithm for 2D threshold arrays for image processing into 3D. The resulting lattice of threshold values is assigned so as to reduce low frequency variations in the digital representation. This algorithm also takes into account technical limitations in the machine, only generating lattices that can be represented within the memory limits of the current hardware implementation in the 3D Printer.

_________________________________________________________________

_________________________________________________________________

_________________________________________________________________

1. Prototype Name: FGM Object Modeler

+ Availability: Prototype phase, for evaluation within MIT.

+ Description: Consists of a topological data structure capable of maintaining a solid model decomposed into vertices, edges, faces, and regions, with the necessary connectivity between the topological entities. These topological entities, or cells, maintain geometric and material information in terms of FGMDomains. The Bezier formulation for curves, triangles, and tetrahedra, have been implemented as initial FGMDomains, to provide analytic descriptions of smoothly varying material designs. Design tools for assigning compositions to model have been implemented. Models can be visualized as solids, faces, edges, or vertices, with or without material information. Sliced view of the model can be displayed as well as cuberille renderings of the cells. Currently, models are accepted in the form of a tetrahedral mesh (generated through a commercial meshing program) or a triangulated boundary of the object (in the form of an STL file).

2. Prototype Name: FGMDomain Viewer

+ Availability: Prototype phase, for evaluation within MIT.

+ Description: Initially intended as a test bed for developing FGMDomains to be incorporated into the above modeler, this application has been extended to handle tetrahedral models in terms of a finite element data structure (as oppose to the generalized, cellular structure used above). Tools for visualizing the finite element mesh, defining a material, assigning a composition to the mesh, and processing the model for fabrication have been implemented. This application allows the handling of large tetrahedral meshes than a more sophisticated generalized data structure would. Models are accepted in the form of a tetrahedral mesh (generated through a commercial meshing program). When a "composition" has been designed within a model, the model is processed, consisting of slicing the model into layers for subsequent post-processing into machine instructions. This application incorporates efficient sorting techniques for the design and interrogation of compositions within FGM models. One example is the design of graded material from the boundary, in which a composition profile is designed as a function of distance from the model's boundary and then assigned over the nodes of the tetrahedral mesh using a bucket sorting algorithm.

3. Prototype Name: Halftone3D

+ Availability: Prototype phase, for evaluation within MIT.

+ Description: In the processing of models for fabrication with local composition control, the model is sliced into layers (planar triangular meshes). The material composition over these layers is given in terms of continuous values. To satisfy the need to convert these continuous values into discrete material placements, the "Halftone3D" application samples the compositions over the layers and writes the desired material placements to a file.

4. Prototype Name: Make3DDither

+ Availability: Prototype phase, for evaluation within MIT.

+ Description: In order to convert a continuous representation of the material into discrete material placements, a dither pattern is used. This program generates a dither pattern satisfying the constraints of the 3D printing while minimizing the low frequency fluctuation of the material variation.

5. Prototype Name: FGMto3DP

+ Availability: Prototype phase, for evaluation within MIT.

+ Description: After a design as been processed into discrete placements of material primitives, the information must be encoded into machine instructions for the 3D Printer. The output instructions are then used to drive the fabrication process.

_________________________________________________________________

None.

_________________________________________________________________

_________________________________________________________________

+ US Citizen/Permanent Resident: No

+ Graduated: Ph.D. 06/97

+ Job: Design and development of algorithms to convert continuous tone representations of smoothly graded material designs into discrete representations for fabrication through 3D Printing.

+ US Citizen/Permanent Resident: US Citizen

+ Thesis: Analysis of Functionally Graded Material Object Representation Methods. (tentative)

+ Graduated: Ph.D. expected 12/99

+ Job: Analysis of data structures for representing objects with smoothly graded material compositions, development of prototype system for capturing the designers intend and processing of models.

+ US Citizen/Permanent Resident: No

+ Thesis: Algorithms for Design and Interrogation of FGM Solids. (tentative)

+ Graduated: M.S. expected 12/99

+ Job: Development and analysis of tools for the design and interrogation of models consisting of smoothly graded material compositions, development of algorithms for assigning composition information efficiently to large, tetrahedral models.

_________________________________________________________________

None.

_________________________________________________________________

NSF DMII has funded related work on SFF at MIT.

_________________________________________________________________

None.

_________________________________________________________________