Sara Anne McMains

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-00-1119
October 2000

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2000/CSD-00-1119.pdf

Solid freeform fabrication (SFF) refers to a class of technologies used for making rapid prototypes of 3-D parts. With these processes, a triangulated boundary representation of the CAD model of the part is "sliced" into horizontal 2.5-D layers of uniform thickness that are successively deposited, hardened, fused, or cut, depending on the particular process, and attached to the layer beneath. The stacked layers form the final part.

The current de facto standard interface to these machines, STL, has many shortcomings. We have developed a new "Solid Interchange Format" (SIF) for use as a digital interface to SFF machines. SIF includes constructs for specifying surface and volume properties, precision information, and transmitting unevaluated Boolean trees. We have also developed a 2-D variant, LSIF (Layered SIF), for describing the sliced layers.

Many solid modeling applications require information not only about the geometry of an object but also about its "topology" -- the connectivity of its faces, edges, and vertices. We have designed a new topological data structure, the loop edge data structure (LEDS), specifically targeted at supporting SFF software. For very large data sets, the topological data structure itself can be bigger than core memory, and a naive algorithm for building it becomes prohibitively slow due to memory thrashing. We have developed an algorithm for building the LEDS efficiently from a boundary representation, even when it doesn't fit in main memory, improving software performance for highly tessellated parts by two orders of magnitude.

We have implemented an analysis and cleanup tool for faceted B-reps on top of this data structure. The analysis module reports basic topological information about the part and checks the boundary for cracks. The cleanup module closes cracks via intelligent vertex merging.

We have developed a new sweep-plane slicing algorithm that also operates on the LEDS. Our slicer outputs LSIF, passing along the unevaluated booleans to be resolved at the 2-D level. This slicer exploits the coherence between the finely spaced parallel slices needed for SFF process planning and fabrication. Its performance is two to three times faster than that of a comparison commercial STL slicer on typical parts.

Advisor: Carlo H. Séquin

BibTeX citation:

@phdthesis{McMains:CSD-00-1119,
    Author = {McMains, Sara Anne},
    Title = {Geometric Algorithms and Data Representation for Solid Freeform Fabrication},
    School = {EECS Department, University of California, Berkeley},
    Year = {2000},
    Month = {Oct},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2000/6430.html},
    Number = {UCB/CSD-00-1119},
    Abstract = {Solid freeform fabrication (SFF) refers to a class of technologies used for making rapid prototypes of 3-D parts. With these processes, a triangulated boundary representation of the CAD model of the part is "sliced" into horizontal 2.5-D layers of uniform thickness that are successively deposited, hardened, fused, or cut, depending on the particular process, and attached to the layer beneath. The stacked layers form the final part. <p>The current de facto standard interface to these machines, STL, has many shortcomings. We have developed a new "Solid Interchange Format" (SIF) for use as a digital interface to SFF machines. SIF includes constructs for specifying surface and volume properties, precision information, and transmitting unevaluated Boolean trees. We have also developed a 2-D variant, LSIF (Layered SIF), for describing the sliced layers. <p>Many solid modeling applications require information not only about the geometry of an object but also about its "topology" -- the connectivity of its faces, edges, and vertices. We have designed a new topological data structure, the loop edge data structure (LEDS), specifically targeted at supporting SFF software. For very large data sets, the topological data structure itself can be bigger than core memory, and a naive algorithm for building it becomes prohibitively slow due to memory thrashing. We have developed an algorithm for building the LEDS efficiently from a boundary representation, even when it doesn't fit in main memory, improving software performance for highly tessellated parts by two orders of magnitude. <p>We have implemented an analysis and cleanup tool for faceted B-reps on top of this data structure. The analysis module reports basic topological information about the part and checks the boundary for cracks. The cleanup module closes cracks via intelligent vertex merging. <p>We have developed a new sweep-plane slicing algorithm that also operates on the LEDS. Our slicer outputs LSIF, passing along the unevaluated booleans to be resolved at the 2-D level. This slicer exploits the coherence between the finely spaced parallel slices needed for SFF process planning and fabrication. Its performance is two to three times faster than that of a comparison commercial STL slicer on typical parts.}
}

EndNote citation:

%0 Thesis
%A McMains, Sara Anne
%T Geometric Algorithms and Data Representation for Solid Freeform Fabrication
%I EECS Department, University of California, Berkeley
%D 2000
%@ UCB/CSD-00-1119
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2000/6430.html
%F McMains:CSD-00-1119