PROCESS PLANNING FOR SHAPE DEPOSITION

MANUFACTURING

a dissertation
submitted to the department of mechanical engineering
and the committee on graduate studies
of stanford university
in partial fulfillment of the requirements
for the degree of
doctor of philosophy

By
Krishnan Ramaswami
January 1997

c Copyright 2000 by Krishnan Ramaswami
All Rights Reserved

ii
I certify that I have read this dissertation and that in
my opinion it is fully adequate, in scope and quality, as
a dissertation for the degree of Doctor of Philosophy.

Friedrich B. Prinz
(Principal Adviser)

I certify that I have read this dissertation and that in

my opinion it is fully adequate, in scope and quality, as
a dissertation for the degree of Doctor of Philosophy.

Kosuke Ishii

I certify that I have read this dissertation and that in

my opinion it is fully adequate, in scope and quality, as
a dissertation for the degree of Doctor of Philosophy.

David Beach

Approved for the University Committee on Graduate

Studies:

iii
Abstract

Solid Freeform Fabrication (SFF) refers to a class of rapid manufacturing process that
builds parts by incremental material deposition and fusion of thin 2-1/2 dimensional
layers. Over this past decade, SFF has taken the manufacturing industry to new
heights. However, parts produced by SFF processes exhibit a stair-step surface
texture due to the presence of 2-1/2 dimensional layers and exhibit limited material
properties. These issues are addressed by a modified SFF process called Shape
Deposition Manufacturing. Shape Deposition Manufacturing (SDM) is a novel layered
manufacturing process in which multi-material structures with embedded components
can be fabricated. In SDM, the layers are truly three dimensional in nature and are
built using a combination of material addition and material removal processes. The
need for an automated and robust process planner is more in the case of SDM as
it attempts to build fully functional parts directly from CAD models. This thesis
focuses on the process planning issues in Shape Deposition Manufacturing.
The major issues in process planning for SDM involves the generation of 3-D
layers and generation of deposition and CNC cutter paths for these 3-D layers. In
SDM, the CAD model is decomposed into 3-D layers of varying thickness based
upon both geometric and material criteria. The layers are further decomposed
into manufacturable volumes called compacts. Silhouette edges and silhouette loops
are identified to help the decomposition of models into 3-D layers and compacts.
Unlike techniques used in existing SFF methods which divide models into equally
spaced slices, the present algorithm decomposes models into compacts which are

iv
not necessarily planar and equally spaced. Solely based on geometric evaluations
a feasible sequence of material addition and removal processes is found for these
compacts. Each compact is deposited to the near-net shape using material deposition
techniques. Deposition paths are generated for the 2-D cross-section obtained by the
XY projection of the compact. The compact is then machined to the required shape
through a series of CNC cutting operations. The absence of fixturing problems and
tool accessibility problems helps in fully automating the generation of CNC cutter
paths. Several parts of varying complexity were built using this process planner and
the results will be discussed.

v
Acknowledgements

I take this opportunity to express my sincere appreciation to my adviser Prof. Fritz

Prinz for his support and guidance in pursuing this research. He kept me free of
financial worries and provided the much needed encouragement over the last four
years. He provided an excellent research atmosphere that was very helpful in the
successful completion of this work.
I would like to thank Prof. Kincho Law for serving as the chair of my thesis
committee. I would also like to thank the other members of my thesis committee,
Prof. David Beach, Prof. Kos Ishii and Prof. Paul Losleben for their valuable com-
ments and useful suggestions. Thanks are also due to Prof. Yasushi Yamaguchi of
Univ. of Tokyo for many exciting and useful discussions.
I am grateful to my former colleagues of the Engineering Design Research Center
at Carnegie Mellon University and the current colleagues of the Rapid Prototyping
Lab at Stanford University for their support and encouragement in the course of this
research. In particular, I would like to thank Dr. Levent Gürsöz for the inspiring
conversations during the initial stages of this work, and Dr. Robert Merz for his
valuable suggestions on different aspects of this work. I would also like to thank
Sylvia Walters for efficiently handling all the administrative details.
I want to thank my friends in the different parts of this country for their support
and friendship. In particular, my friends in Pittsburgh and Bay area deserve special
credit for making me feel at home by providing an enjoyable social atmosphere.
Finally, I wish to express my special thanks to my father and the other members
of my family for their support and encouragement during the course of this work.

vi
Contents

Abstract iv

Acknowledgements vi

1 Introduction 1
1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Solid Freeform Fabrication . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Review of SFF processes . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Limitations of SFF . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Present Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Shape Deposition Manufacturing 11

2.1 The SDM Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Process planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3 Spatial Decomposition 20
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2.2 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.3 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2.4 Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

vii
 3.3 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4 Deposition Path Generation 38

4.1 Deposition Methods in SDM . . . . . . . . . . . . . . . . . . . . . . . 39
4.2 Generation of deposition paths . . . . . . . . . . . . . . . . . . . . . . 40
4.2.1 Types of deposition paths . . . . . . . . . . . . . . . . . . . . 41
4.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5 CNC Cutter Path Generation 50

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.2 Rough Cutting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.3 Two Dimensional Profile cutting . . . . . . . . . . . . . . . . . . . . . 55
5.4 Offset of TwoD Profiles . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

6 3-D Cutter Path Generation 60

6.1 Finishing operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.2 Collision Free Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.2.1 Collision types . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.2.2 Collision Detection and Avoidance . . . . . . . . . . . . . . . 66
6.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

7 Software Issues 70
7.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
7.2 CAD system requirements . . . . . . . . . . . . . . . . . . . . . . . . 71
7.3 CAD System Comparison . . . . . . . . . . . . . . . . . . . . . . . . 74
7.4 Implementation issues . . . . . . . . . . . . . . . . . . . . . . . . . . 76

8 Applications 79
8.1 Geometrically complex parts . . . . . . . . . . . . . . . . . . . . . . . 80
8.1.1 IMS-T2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8.2 Next generation metal tooling . . . . . . . . . . . . . . . . . . . . . . 82

viii
 8.2.1 GM Injection molding Tool . . . . . . . . . . . . . . . . . . . 83
8.3 Non-conventional parts . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.3.1 Parts with interacting geometric features . . . . . . . . . . . . 84
8.3.2 Conformable, Embedded Electro-mechanical parts . . . . . . . 87
8.3.3 Assembled mechanisms . . . . . . . . . . . . . . . . . . . . . . 89

9 Conclusions and Future work 91

9.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
9.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

A Kinematic Transformations 99
A.1 Coordinate systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
A.2 Kinematic equations . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

Bibliography 104

ix
List of Figures

1.1 THE WORKING PRINCIPLE OF SFF . . . . . . . . . . . . . . . . . . . . . . . . 3

2.1 THE SDM PROCESS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.2 A SCHEMATIC OF THE SDM SETUP . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 DIFFICULTIES WITH CONVENTIONAL CAD/CAM PROCESSES . . . . . . . . . . . . 15
2.4 PROCESS PLANNING STEPS IN SDM . . . . . . . . . . . . . . . . . . . . . . 17

3.1 SEQUENCE OF OPERATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.2 TYPES OF SURFACES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3 SILHOUETTE EDGES AND LOOPS . . . . . . . . . . . . . . . . . . . . . . . . 23
3.4 PART AND ITS SUPPORT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.5 COMPACT DECOMPOSITION OF THE PART . . . . . . . . . . . . . . . . . . . . . 24
3.6 COMPACT DECOMPOSITION OF THE SUPPORT . . . . . . . . . . . . . . . . . . . 25
3.7 CYCLIC ORDERING . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.8 COMPACT DECOMPOSITION USING INFINITE SWEEP . . . . . . . . . . . . . . . . 29
3.9 FIRST THREE STAGES OF THE ALGORITHM . . . . . . . . . . . . . . . . . . . . 31
3.10 DECOMPOSITION ALONG CONCAVE SILHOUETTE EDGES . . . . . . . . . . . . . . 32
3.11 MODEL WITH SELF-INTERSECTING PROJECTED SILHOUETTE LOOP . . . . . . . . . . 33
3.12 DECOMPOSITION TO ELIMINATE SELF-INTERSECTIONS OF PROJECTED SILHOUETTE LOOP 34
3.13 SPLITTING SILHOUETTE LOOPS TO AVOID CYCLIC ORDERING . . . . . . . . . . . . 35
3.14 COMPACT DECOMPOSITION WITH PROCESS SEQUENCE . . . . . . . . . . . . . . 36

4.1 WORKING PRINCIPLE OF MICROCASTING . . . . . . . . . . . . . . . . . . . . . 39

4.2 WORKING PRINCIPLE OF LASER DEPOSITION SYSTEM . . . . . . . . . . . . . . . 40

x
4.3 TYPES OF DEPOSITION PATHS . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.4 MAT OF A RECTANGLE . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.5 MAT BASED DEPOSITION PATH . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.6 RECTANGULAR HULL CONSTRUCTION . . . . . . . . . . . . . . . . . . . . . . 46
4.7 ZIGZAG PATH GENERATION . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.8 TOWER DEPOSITION PATTERN . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.9 CONVEX DECOMPOSITION FOR DEPOSITION . . . . . . . . . . . . . . . . . . . 48
4.10 CROSS HATCH DEPOSITION . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.1 CNC CUTTING STAGES IN SDM . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.2 PLANING OPERATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.3 VOLUME Vrc TO BE ROUGH CUT . . . . . . . . . . . . . . . . . . . . . . . . 53
5.4 STEPS IN THE ROUGH CUT ALGORITHM . . . . . . . . . . . . . . . . . . . . . 54
5.5 TYPES OF ROUGH CUT PATHS . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.6 DEGENERACIES IN CURVE OFFSET . . . . . . . . . . . . . . . . . . . . . . . 56
5.7 OFFSET COMPUTATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.8 OFFSET MODEL WITHOUT DEGENERACIES . . . . . . . . . . . . . . . . . . . . 58

6.1 TYPES OF CUTTER REGIONS . . . . . . . . . . . . . . . . . . . . . . . . . . 61

6.2 SURFACE SHRINKING FOR FLAT-END MILLED REGIONS . . . . . . . . . . . . . . . 64
6.3 INTERSECTION CURVES FOR 3-AXIS MILLED REGIONS . . . . . . . . . . . . . . . 65
6.4 TYPES OF GOUGING . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

7.1 CAD SYSTEM COMPARISON CHART . . . . . . . . . . . . . . . . . . . . . . . 77

8.1 CAD MODEL OF IMS-T2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

8.2 COMPACT DECOMPOSITION OF THE SUPPORT IN IMS-T2 . . . . . . . . . . . . . . 81
8.3 IMS-T2 MANUFACTURED WITH SDM . . . . . . . . . . . . . . . . . . . . . . 82
8.4 INJECTION MOLDING TOOL . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
8.5 CAD MODEL OF TILTED FRAMES . . . . . . . . . . . . . . . . . . . . . . . . 84
8.6 SILHOUETTE CURVES AND LOOPS . . . . . . . . . . . . . . . . . . . . . . . . 85
8.7 SPATIAL DECOMPOSITION OF TILTED FRAMES . . . . . . . . . . . . . . . . . . . 86
8.8 TILTED FRAMES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

xi
8.9 VUMAN EMBEDDED ELECTRONIC STRUCTURE . . . . . . . . . . . . . . . . . . 88
8.10 CAD MODEL OF SIMON GAME PIECE . . . . . . . . . . . . . . . . . . . . . . . 88
8.11 SDM-SIMON GAME . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
8.12 CRANK AND PISTON MECHANISM . . . . . . . . . . . . . . . . . . . . . . . . 90

A.1 COORDINATE SYSTEMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

xii
Chapter 1

Introduction

1.1 Problem Statement

In a global competitive environment that is intense and dynamic, the development
of new products and processes increasingly is a focal point of competition. As an
example, CAD/CAM systems are required that can quickly produce physical objects
directly from CAD models. Rapid fabrication is useful for such manufacturing tasks
as prototyping, low-volume parts production and for producing the custom tooling
for high-volume production. A new class of manufacturing process, Solid freeform
fabrication, addresses this challenge. Solid Freeform Fabrication (SFF) is a class of
rapid manufacturing process that builds parts by incremental material deposition
and fusion of thin 2-1/2 dimensional layers. Over this past decade, Solid freeform
fabrication has taken the manufacturing industry to new heights. However, parts
produced by SFF processes exhibit a stair-step surface texture due to the presence
of 2-1/2 dimensional layers and exhibit limited material properties. These issues
are addressed by a modified SFF process called Shape Deposition manufacturing
(SDM).In SDM, layers are truly three dimensional in nature. In SDM, parts are
built by incremental material deposition and material removal of these 3-D layers.
Naturally a new manufacturing process such as SDM poses new challenges in process
planning. This thesis focuses on the process planning issues in Shape Deposition
Manufacturing.

1
CHAPTER 1. INTRODUCTION 2

The need for an automated and robust process planner is important in the case
of SDM as it attempts to build fully functional parts directly from CAD models.
The major issues in process planning for SDM involves the generation of 3-D layers
and generation of deposition and CNC cutter paths for these 3-D layers. 3-D layers
of varying thickness are generated from CAD models. The thickness of the layers
are based on geometric and process constraints. Deposition paths are generated for
depositing these layers. The deposited layer is then machined to the required shape
through a series of CNC cutting operations. The CNC cutter paths are generated
for roughing and finishing operations. The generation of CNC cutter paths has to be
fully automatic as human intervention with so many layers would render the process
impractical.

1.2 Solid Freeform Fabrication

Solid Freeform Fabrication [42], [70] is an emerging manufacturing technology that
builds parts directly from CAD models using only material addition rather than
the conventional material removal processes. SFF, which is also known as desktop
manufacturing, is actually a subset to the rapid-prototyping area of net-shape man-
ufacturing. In SFF, a three dimensional solid or surface model of CAD design is
geometrically sectioned into planar layers of constant thickness (Figure 1.1). Each
cross-sectional planar layer is then sent to a SFF machine. Each layer is created
by incremental material build-up of the two-dimensional cross section to a uniform
thickness. The overhanging regions of the part are supported either by a sacrificial
support material, (Figure 1.1) or by predesigned supports like pillars and trusses that
are built into the part model. The support structure is removed after the model
building is completed.
One of the main advantages of SFF is its ability to build complex parts from a
CAD model in a very short time with very little human intervention. With SFF,
the prototype of a complex part can be built in a short time, therefore designers and
engineers can evaluate a design very quickly. This will help in substantially reducing
the total time from concept to full-scale production. SFF is also used in making
CHAPTER 1. INTRODUCTION 3

Planar
3-D Geometry
Decomposition Cross-Section

Sacrificial Primary
Support Material
Material

Figure 1.1: THE WORKING PRINCIPLE OF SFF

molds and dies with lower toolmaking time and cost. Due to its sequential, layered
approach SFF can be used to build parts that would be impractical or impossible
to build with traditional approaches. Some examples would be parts with internal
channels or parts with mechanisms assembled during fabrication.

1.2.1 Review of SFF processes

Stereolithography (SLA) SLA [33] is the first commercially available SFF process.
An elevator platform is submerged in a vat of liquid photo-polymeric resin and
held near the surface. A low-power ultraviolet laser scans the surface of the
liquid to partially cure the layer. After a layer is built, the elevator drops a user
specified distance and a new coating of liquid resin covers the solidified layer
and a new layer is scanned by the laser. When all layers are completed, the
part is removed, cleaned and post-cured in a fluorescent oven with ultraviolet
light to solidify any uncured resin. The part is finished by sanding and/or
glass-bead blasting. For parts with overhanging features, support structures
are needed. The support structure consists of vertical members extending from
the platform to the part. The process planning effort in SLA is trivial. It
consists of determination of layer cross-sections and generation of laser scan
paths for the cross-section. A more challenging planning effort would be the
CHAPTER 1. INTRODUCTION 4

automatic design of support structures [29].

Fused deposition modeling (FDM) In an FDM process [32], a spool of thermo-

plastic filament feeds into a heated nozzle which traces an exact outline of each
cross-section layer of the part. The movement of the nozzle is controlled by
a computer. The material solidifies in 0.1s after exiting the nozzle. After one
layer is finished, the nozzle moves up a programmed distance in z direction for
building the next layer. Due to the short solidification time, FDM process does
not need supports. But in some cases, a support may still be required to reduce
part distortion. The process planning effort in FDM consists of generation of
paths for nozzle motion. In complex parts, design of support structure needs to
be handled.

Laminated object manufacturing (LOM) The LOM process [19] produce parts
from bonded paper, plastic, metal or composite sheet stock. In this process,
a layer of sheet material is glued or welded to the previous layer, and then a
laser beam follows the contour of the part cross-section to cut it to the required
shape. The excess material of every sheet is either removed by vacuum suction
or remains as next layer’s support. The process planning involves generation of
contours to be followed by the laser.

Solid ground curing Cubital’s Solider [39] process uses a photo-masking technique
to solidify a whole layer of liquid photo-polymer at one time. A mask is
generated by electrostatically charging a glass plate with a negative image of
the layer’s cross-section. The mask is then positioned over a uniform layer of
liquid photo-polymer and exposed under the ultraviolet light such that only the
area shaded by the mask is left in liquid form. The liquid polymer is removed
and is replaced with hot wax. After the wax has cooled, the layer is milled
flat to the specified thickness. The mask plate is discharged and the cycle is
repeated. When the part is constructed, the supporting wax is removed either
by melting or by using a solvent. The process planning effort is mainly in the
generation of mask.
CHAPTER 1. INTRODUCTION 5

Selective laser sintering(SLS) SLS [12] uses laser to sinter successive layers of
powder instead of liquid. In the SLS process, a thin layer of heat-fusible powder
is a spread over a surface by a counter-rotating roller. A laser traces the cross-
section of the layer on the powder surface, sintering the portions exposed to the
laser beam. The roller spreads another layer of powder over the sintered one
and the process continues till the part is completed. The unsintered powder on
every layer acts as support during the building process. Post processing of SLS
parts involves the removal of binder. The process planning effort involves the
generation of laser trajectories. With some materials, the product may suffer
shrinkage and warpage due to sintering and cooling. In such cases, an interesting
process planning problem would to be offset for shrinkage in the CAD model.

Three-dimensional printing (3D Printing) 3D printing [53] is another powder

based SFF technique. In this process, an inkjet sprays liquid binder onto a layer
of powder tracing out the cross-sectional pattern. Another layer of powder is
spread over the previous one and the process is repeated. After completion the
part is subjected heat treatment to enhance the bonding of the glued powder
and then the unbonded powder is removed. The unbonded powder of each layer
serves as the support during the layering process. Generation of cross-sectional
pattern for the inkjet is the main process planning issue. During the sintering
process there might be significant shrinkage. Modification in the CAD model
to account for this shrinkage will be an interesting process planning problem.

Ballistic particle manufacturing (BPM) In BPM, a piezo-driven inkjet nozzle

is used to shoot molten material droplets that cold-weld onto a previously
deposited layer. The cross section of the layer is scanned by the nozzle. After a
layer is formed, the base plate is lowered by a specified distance and a new layer
is created over the previous layer and this is repeated till the part is completed.
Support structures are needed to support overhanging features. The support
material that is used is a water-soluble synthetic wax. The process planing
effort is to generate deposition paths for the nozzle. In order to avoid excess
material in any area, different deposition path patterns have to be explored.
CHAPTER 1. INTRODUCTION 6

Recursive mask and deposit(MD ∗ ) MD ∗ [68] is based on thermal spraying in

which parts are manufactured by successively spraying cross-sectional layers.
A disposable paper mask of the part cross-section is cut out with a laser.
The mask is placed on the top layer of the growing part and the material is
thermally sprayed through the mask by a robotically manipulated spray gun.
Since the material being sprayed can be changed layer by layer or within a
layer, multi-material parts can be manufactured by this process. Support is
provided by a portion of mask in low melting material and by a sacrificial low
melting support material for high melting materials. The process planning effort
involves generation of laser beam trajectories to cut each cross-section.[45]

1.2.2 Limitations of SFF

While the SFF processes are very useful for rapidly creating prototypes, there are
inherent limitations in these processes for creating high quality functional parts. The
limitations could be classified under geometric and process and material categories.

Geometric limitations In all SFF processes, layers consist of two-dimensional

cross-sections that are built up to a uniform thickness. This will result in a
stair-step surface texture (Figure 1.1). Also, many of the SFF process uses
a faceted geometry as the input model. In a faceted representation, a higher
tessellation resolution is needed for creating an accurate model. While a higher
resolution works for simple models, it becomes almost impractical in the case
of complex models with freeform surfaces.

Process and Material limitations None of the SFF processes have the capability
to produce parts with properties equivalent to those made with conventional
manufacturing technologies. SFF parts have to be post-processed before they
can be used. Most of the post-processing methods either modify the properties
of the material or alter the shape of the part. For example, in 3D printing,
liquid infiltration is done in order to produce dense parts and this might affect
the resulting material properties. In SLS, parts might suffer shrinkage due to
sintering and cooling. In theory, shrinkage can be compensated by modifying
CHAPTER 1. INTRODUCTION 7

the original CAD model, but it is very difficult to predict the actual shrinkage for
any complex shape. Shrinkage might also cause the buildup of residual stresses.
Residual stresses will also be caused due to temperature gradients between
layers. These residual stresses might lead to distortions and delaminations. The
poor surface quality could also be partially attributed to the material deposition
process. During the material deposition process, the surface tension of the
material prevents the generation of geometrically well-defined surfaces between
layers . The current SFF processes are restricted to a limited set of materials.
Processes like SLA, Solid ground curing and FDM are restricted to polymers.
Processes like SLS and 3D printing use a wider range of materials but have
shrinkage problems.

Thus while offering the benefit of building complex parts directly from CAD
models in a short time, SFF suffers from poor geometric and material tolerances.
On the other hand, conventional methods using CNC machining can deliver high
geometric and material quality, but are limited in part complexity. CNC machining
is also expensive and requires human intervention for generating CNC cutter paths
and for designing and selecting fixtures. Thus a process that combines the layered
principle of SFF processes and the accuracy of CNC machining will seem to be a step
in the right direction. Shape deposition manufacturing (SDM) is such a process that
takes advantage of both material addition and material subtraction.

1.3 Present Work

This work addresses the process planning issues in SDM. Being a new manufacturing
process, SDM poses new challenges in process planning. As a first effort, the process
planning steps in SDM are identified. The major steps in process planning for SDM
1
involves the generation of compacts and generation of deposition and CNC cutter
paths for these compacts. An algorithm for the decomposition of any CAD model into
compacts is described. This decomposition facilitates the manufacture of complex,

1
A compact is a manufacturable volume in SDM and will be described in Chapter 3.
CHAPTER 1. INTRODUCTION 8

multi-material objects in SDM. The concept of silhouette loops is introduced to help

in this decomposition process. Silhouette edges are identified and are arranged in
the form of silhouette loops and the decomposition requirements are expressed in
terms of silhouette edges and loops. The decomposition algorithm also generates the
process sequence for these compacts. Algorithms for generating deposition paths are
described. Some of the factors that influences the derivation of deposition paths are
identified. Algorithms for deriving spiral and zigzag deposition paths are described.
Methods are also outlined to derive a few other deposition paths from these two types
of paths. Algorithms for generating CNC cutter paths for compacts is described. A
fully automated approach for CNC cutter path generation is described that takes
advantage of the benefits such as absence of fixturing and tool accessibility problems,
offered by the SDM process. A new representation, manhattan solid, has been
proposed for generating efficient rough cutting algorithms. The generation of 2-D
cutter paths is made robust by proposing a robust algorithm for offsetting 2-D cross-
section. A new classification scheme based on the curvature information has been
proposed for the surfaces of the model that helps in generation of fully automatic 3-D
cutter paths. A great deal of effort was spent in identifying the ideal CAD system for
the implementation of these algorithms. The process planner was implemented in two
different CAD systems both of which partially met the requirements. The algorithms
have been verified by building several complex test parts.

1.4 Thesis Outline

SDM is a modified solid freeform fabrication process that can manufacture arbitrarily
complex shaped structures directly from CAD models in an automated environment.
In addition, the SDM process allows the manufacture of multi-material and embedded
structures that cannot be produced with the traditional manufacturing techniques.
Chapter 2 gives an overview of the SDM process outlining the various processing
steps needed to produce a part. Chapter 2 also outlines the process planning issues
in SDM.
In SDM, the CAD model is decomposed into 3-D layers of varying thickness based
CHAPTER 1. INTRODUCTION 9

upon both geometric and material criteria. The layers are further decomposed into
compacts that have all their newly deposited surfaces to be non-undercut. Two
approaches to this problem of spatial decomposition are explained in Chapter 3. Both
the approaches rely on the generation of silhouette edges. The concept of silhouette
edges and the process of generating them will also be explained in Chapter 3
Each compact is deposited to the near-net shape using material deposition tech-
niques. Deposition paths are generated for the 2-D cross-section obtained by the XY
projection of the compact. Chapter 4 describes the generation of deposition paths.
Due to the nature of the deposition methods, the generation of deposition paths has
to avoid revisiting the same position and should not leave any gaps. Chapter 4 also
describes the various deposition methods used in SDM.
SDM is different than other SFF processes in that it uses both material deposition
and material removal processes to build a layer. The material removal process in
SDM is done using CNC machining. Chapter 5 describes the generation of CNC
cutter paths in SDM. CNC cutter path generation can be broadly separated into two
categories, 2-D and 3-D cutter path generation. This chapter mainly deals with 2-D
cutter path generation. 2-D cutting can be further classified into rough cutting and
2-D profile cutting, both of which require the offset of 2-D cross-section. Chapter 5
also describes the generation of offsets of 2-D models.
Chapter 6 deals with the 3-D cutter path generation. Success has been eluding
researchers in automating the generation of CNC cutter paths. It can be partially
attributed to fixturing problems and tool accessibility problems. In the case of SDM,
the absence of both these problems motivates us to find a method to successfully
generate fully automatic 3-D CNC cutter paths. In Chapter 6, such a method is
described. The surfaces of the model are subdivided and classified based on the
cutting method. Cutter paths are then generated for each of these surface types.
During the various process planning steps in SDM, the CAD model undergoes
a series of geometric operations. In order to withstand the complex geometric
operations, a powerful geometric engine should serve as a backbone for the process
planner. Chapter 7 describes the requirements of a geometric engine for the process
planner. It also describes the geometric modelers that were used for process planning
CHAPTER 1. INTRODUCTION 10

in SDM and some of the implementation difficulties in using those modelers.

In Chapter 8 a variety of test parts that were built with the process planner are
shown. The process planning problems in building some of those parts are described.
Chapter 9 concludes the thesis by outlining the accomplishments of this work.
Some of the process planning issues that are not addressed in this work are discussed.
Some suggestions for improving some of the methods given in this work are outlined.
Appendix A describes the inverse and direct kinematic transforms that are needed
to convert the cutter paths into machine codes.
Chapter 2

Shape Deposition Manufacturing

Solid Freeform Fabrication (SFF) has been widely investigated as a way to auto-
matically fabricate parts directly from CAD models for applications in the area of
rapid prototyping and short-run manufacturing. But it remains a goal to be able
to directly build high performance metal shapes using SFF techniques. Fully dense
metal parts that have accurate dimensions and good surface appearance are often
required for such applications as custom tooling and production-ready prototypes.
Shape Deposition Manufacturing (SDM) is a manufacturing technique that attempts
to address the issue of directly creating fully functional metal shapes. In addition,
SDM also has the potential to produce multi-material, functionally graded, embedded
heterogeneous structures made of metal, plastic and ceramic materials.

2.1 The SDM Process

Shape Deposition Manufacturing [25],[43],[44] is a manufacturing process that creates
functional metal parts by incremental material deposition and material removal. It
combines the benefits of SFF (handling complex geometries), CNC milling (accurate
and precise with good surface quality) and weld-based deposition (superior material
properties). The steps involved in building parts with SDM is shown in Figure 2.1.
In SDM, the CAD model is decomposed into simpler building block called com-
pacts. The compacts are deposited as near-net shape using a deposition method

11
CHAPTER 2. SHAPE DEPOSITION MANUFACTURING 12

Figure 2.1: THE SDM PROCESS

such as plasma or laser based deposition process. After deposition, each layer is
accurately machined to net shape using CNC milling or EDM. Processes such as
shot-peening are used to control the build-up of residual stresses. Sensors, electronic
components, prebuilt mechanical parts or circuits can be embedded into each layer.
After completing one layer, the next layer is deposited and the process is repeated
till the part is completed. In SDM, support for overhanging features is provided by
the sacrificial support material. Each layer is embedded in the support material. The
CAD model of the support structure is obtained as the compliment of original CAD
model. The support structure is built along with the original model and follows the
SDM cycle shown in Figure 2.1. After the part is completed, the support material
CHAPTER 2. SHAPE DEPOSITION MANUFACTURING 13

is removed either by a melting or etching process. Multi-material and functional-

gradient parts can be built by depositing different materials within each layer following
the same cycle.
The SDM setup consists several subprocessing stations for material deposition,
material removal, cleaning and stress relieving. The parts are built on a pallet that
is transported between different stations by a transfer robot. Each station has a
pallet receiver mechanism that locates and clamps the pallet. Pallet transfer between
individual stations is handled by a control program in the computer. The control
program also downloads and executes the trajectories on the individual stations.
A schematic of the setup is shown in Figure 2.2. Thermal deposition techniques

Figure 2.2: A SCHEMATIC OF THE SDM SETUP

have been explored in SDM in order to produce high quality parts. While spraying
techniques suffer from poor bonding properties, traditional welding based approaches
suffer from penetration problems created by excessive heat input. In SDM, material
is deposited by plasma or laser based droplet-deposition process that ensure good
metallurgical bonding between layers without excessive heating of the substrate
material. Other deposition processes that are currently being explored include
selective casting of two-component or UV-curable resins, hot pressing of powders,
sputtering and ceramic deposition. In SDM, material removal is done using a 5-
axis CNC milling machine. The CNC cutter paths generated by the process planner
CHAPTER 2. SHAPE DEPOSITION MANUFACTURING 14

are downloaded to the machine in the DNC mode. Other material removal stations
that will be included in the future include EDM (electro discharge machining) and
a 3-axis CNC milling machine for handling abrasive materials. The residual cutting
fluids or the residue from the deposition process are removed in a washer that has the
capability to spray a water-jet at different speeds. A shot peener is used to relieve
stresses in the part. The shot peener uses a conventional pressurized media delivery
system.
Some of the current application areas of SDM are

• Shape conformable embedded electro-mechanical structures

• Manufacture of custom tools

– Injection molds with cooling channels

– Tools with multi-material inserts
– Tools with embedded sensors

• Functional prototype parts

• Complex shaped parts made of hard-to-machine materials.

2.2 Process planning

In conventional CAD/CAM systems that rely on CNC machines to build parts,
process planning plays a significant role. Process planning in such systems requires
identification of machining features. Sarma and Wright [54] identifies two levels of
planning for the conventional CAD/CAM systems. Macroplanning is a higher level
planning that deals with access directions of features, process sequencing and selection
of appropriate fixtures. Microplanning deals with tool path planning and selection of
tools and process parameters. Although progress has been made towards automating
these planning tasks, significant human intervention is still required which results
in long lead times and expensive parts. Some of the difficulties in automating the
conventional CAD/CAM processes are:
CHAPTER 2. SHAPE DEPOSITION MANUFACTURING 15

• Inaccessibility of some areas of the model by the cutting tool Figure 2.3a. This
could be caused either due to insufficient tool length or due to inaccessible
surfaces in the model.

• Part-specific fixturing Figure 2.3b. In order to access undercut surfaces, special

fixture or refixturing is needed. The design and selection of fixtures involves
considerable human expertise and is difficult to automate.

Inaccessible by tool Fixturing problems

Figure 2.3: DIFFICULTIES WITH CONVENTIONAL CAD/CAM PROCESSES

• Generation of cutting tool trajectories for complex geometries. Geometric rea-

soning becomes a difficult task in the case of complex geometries. Problems like
gouging and collisions becomes more difficult to handle in complex geometries.
Multiple re-fixturing might be necessary to cut certain shapes without collisions.
Verification tools are needed to ensure the correctness of the generated paths.

On the other hand, one of the clear advantages with SFF processes is the ability
to produce physical objects from CAD models in a completely automated fashion
with very little process planning effort. SFF processes operate on planar geometries
that makes them essentially independent of the part complexity. Support structures
eliminate the need for custom fixturing and permit undercut features to be built up.
The process planning effort in most of the SFF processes involves the generation of
2-D cross-sections and generation of scan paths for the 2-D cross-sections. Since it
is possible to solve these issues in a robust and autonomous fashion, producing parts
CHAPTER 2. SHAPE DEPOSITION MANUFACTURING 16

using the SFF processes requires very little human intervention. Of course, issues
such as shrinkage compensation and support structure determination would make
the process planning effort in SFF processes more challenging.
In SDM, there is a full 3-D shape control of all surfaces and it also uses material
removal operations like CNC cutting. Both these make the process planning effort
in SDM more complex than that of SFF processes. Figure 2.4 shows the process
planning steps involved in SDM. In SDM, the CAD model is first decomposed into
layers of varying thickness based upon both geometric and process criteria. Each
layer is further subdivided into simpler building blocks called compacts that are of
single material and which have all their newly deposited surfaces to be non-undercut
surfaces. The compacts are then sequenced for subsequent planning operations.
The compacts are deposited as near-net shapes using the deposition paths. The
parameters for deposition paths, such as path spacing, deposition feedrate and height
of deposit are dependent on the deposition method used and material being deposited.
This information is obtained from the process database. The deposited compacts are
machined to net shape using CNC cutting operations. The CNC cutter paths are
transformed to machine coordinates and into the machine readable format. The
CNC cutter paths are generated with different types of cutting tools with varying
sizes. The feed-rate and the spindle speed are based on the cutter used and the
material being cut. This information is derived from the tool database. Deposition
paths and CNC cutter paths are then generated for the next compact and the path
generation cycle is repeated till all the compacts are processed.
One of the key challenges in process planning for SDM is to develop robust
algorithms to automatically decompose any CAD solid model into a set of layers
and compacts. This problem involves extensive geometric reasoning and is very
difficult to be solved manually. Thus, it is essential that this is done in an automated
fashion. With a host of interesting geometric issues, a robust solution to this problem
will be a challenging task. The other major area in process planning for SDM is
path planning. Path planning encompasses generation of deposition trajectories and
cutting trajectories. Though there are some common issues in deposition and cutting
path generation, there are some basic issues that separates these two problems. The
CHAPTER 2. SHAPE DEPOSITION MANUFACTURING 17

CAD Model

Min/Max
Adaptive Layer Thickness
layer
Generation

Compact Process
Non-Monotonic
Generation Layer Database

Layer/Compact
Sequence

Deposition Path

Tool
Database

CNC Cutter Path

Machine Code

Figure 2.4: PROCESS PLANNING STEPS IN SDM

CHAPTER 2. SHAPE DEPOSITION MANUFACTURING 18

deposition path generation is highly influenced by the process whereas the cutting
path generation is governed more by geometry than by the process. Trajectories
generated for droplet-based deposition methods used in SDM control the integrity of
the deposited material. It is very important to maintain accurate path spacing and
torch angles to avoid gaps or overlaps in the deposit. A variety of trajectory patterns
should be explored to overcome issues like unsymmetrical deposition properties,
localized heating and thermal cycling. On the other hand, cutter path generation is
mainly dictated by geometric complexities. As explained before, automation of CNC
cutter path generation has not been possible. But in SDM, it is very essential that
it is automated as human intervention with so many layers would cause considerable
delays in the process. Also, with the original model decomposed into compacts, it is
intuitively difficult to generate the CNC trajectories. At the same time, this process
offers some benefits which helps towards this automation. The compacts won’t have
any undercut features and since the compacts won’t be too high, all areas of the
compact will be within the reach of the tool and there is no need to consider fixturing
problems. Thus generation of CNC cutter paths in an automated fashion would be
another major task of the process planning system.

2.3 Summary
This chapter described the SDM process and the process planning issues in SDM.
SDM is a layered manufacturing process that employs material deposition and
material removal processes for creating a part. Process planning is an important
component in any manufacturing process. In conventional manufacturing processes
that employ CNC machining, process planning involves selection and design of
fixtures and generation of CNC cutter paths. This still needs significant human
intervention resulting in long lead times and expensive parts. In SFF processes,
process planning involves generation of 2-D cross-sections by slicing the CAD model
and generation of scan paths for these 2-D cross-sections. This needs very little
human intervention. Process planning in SDM has some similarities and differences
with the above mentioned methods of process planning. In SDM, similar to SFF, the
CHAPTER 2. SHAPE DEPOSITION MANUFACTURING 19

CAD model has to be decomposed into simpler models but the difference is that these
simpler models are 3-D models and are no longer 2-D cross-sections. Then similar to
CNC process planning, cutter paths have to be generated for these 3-D models, but
the difference is that the cutter path planning has to be fully automatic and is free
of fixturing problems.
Chapter 3

Spatial Decomposition

3.1 Introduction
As mentioned before SFF parts are processed by decomposing 3-D CAD models into
thin cross sectional layers which are used to plan the material deposition strategy
for each layer. The physics of the material deposition process (e.g. surface tension)
frequently prevents the generation of geometrically well defined surfaces between cross
sections. Instead, surfaces with a stair step appearance may be created. In contrast,
Shape Deposition Manufacturing (SDM) takes advantage of both material addition
and subtraction. The SDM strategy is to first decompose a CAD model into simpler
building blocks called compacts.
A key challenge in SDM is to develop robust algorithms capable of automatically
decomposing any 3-D model into a set of layers and compacts which can be fabricated
by combined additive and subtractive process. To define the nature of the geometric
problems involved, we describe the sequence of fabrication steps first. Each layer
consists of a primary material and a sacrificial support material. For example,
consider the object in Figure 3.1 which is decomposed into three planar layers. The
layers comprising the primary material are classified as follows:

• Class 1 has only non-undercut features

• Class 2 has only undercut features

20
CHAPTER 3. SPATIAL DECOMPOSITION 21

• Class 3 is a combination of 1 and 2.

Both
Undercut

Non-undercut

Class 1

Class 2

Class 3

Figure 3.1: SEQUENCE OF OPERATIONS

Figure 3.1 shows the sequence of operations for these three class of layers. For class
1 the primary material is deposited first and then machined to net shape. Next,
the sacrificial support material is deposited and planed together with the primary
material. This sequence is reversed for class 2 objects. Class 3 geometries must
be decomposed into compacts such that the strategies of class 1 and class 2 can
be invoked recursively depending on the local geometry. As an example, a support
compact is deposited and cut first followed by deposition and cutting of the primary
material. Finally the rest of the support material can be deposited to complete the
layer.
This description serves to indicate some of the issues in shape decomposition
for SDM processing. The following section aims at generalizing the definitions of
geometric entities which will then lead into the development of the decomposition
algorithm [52].
CHAPTER 3. SPATIAL DECOMPOSITION 22

3.2 Overview

3.2.1 Definitions
The surfaces of the model are classified into three categories (Figure 3.2). If N̂(u, v)

N
N
N
N N

Non-undercut Undercut Non-monotonic

Figure 3.2: TYPES OF SURFACES

is the normal vector on any point (u, v) of the surface S and b̂ is the unit vector in
the build-up direction, then

• S is an undercut surface if N̂ (u, v) · b̂ < 0 for all (u, v) in the domain of S

• S is a non-undercut surface if N̂(u, v) · b̂ ≥ 0 for all (u, v) ∈ S

• S is a non-monotonic surface if it has both undercut and non-undercut portions.

A layer is a section of the model that is bound between two horizontal planes. A
layer can consist of multiple materials and can have a variable thickness. In general,
a layer cannot be processed in one SDM process cycle.
A compact is the fundamental building block of the SDM process. A compact
is composed of single material and has all its newly deposited surfaces to be non-
undercut surfaces. A compact can be processed in one SDM process cycle.
The next four definitions are illustrated in Figure 3.3.
Silhouette edges are defined as those curves on the surface of the model along
which N̂(u, v) · b̂ = 0. Silhouette edges serves as the boundary between undercut and
non-undercut portions of the surface.
CHAPTER 3. SPATIAL DECOMPOSITION 23

a
b

b a

a - Convex surface silhouette edge

b - Convex boundary silhouette edge Silhouette loops
c - Concave boundary silhouette edge

Figure 3.3: SILHOUETTE EDGES AND LOOPS

A convex silhouette edge is a silhouette edge where the surface across the edge is
convex. Thus a convex silhouette edge has its adjacent undercut surface below its
adjacent non-undercut surface.
A concave silhouette edge is a silhouette edge where the surface across the edge is
concave. Thus a concave silhouette edge has its adjacent undercut surface above its
adjacent non-undercut surface.
Silhouette loops are the loops formed by the connecting the silhouette edges into
a closed contour. A silhouette loop can consist of both concave and convex silhouette
edges.
Build-up direction is the direction along which the part is built up. At present,
parts in SDM are built along the z direction. Thus, without loss of generality, z
direction (0,0,1) is assumed to be the built-up direction in the rest of this chapter.

3.2.2 Basic concepts

Some of the concepts in this section and the subsequent sections will be explained
with the help of models of part and support shown in Figure 3.4. The main goal
is to decompose the given CAD model into compacts that could be processed in a
single step. We should also determine the sequence of compacts based on its geometry.
Figure 3.5 and Figure 3.6 shows the spatial decomposition of the part and the support
CHAPTER 3. SPATIAL DECOMPOSITION 24

CAD model of part CAD model of support

Figure 3.4: PART AND ITS SUPPORT

respectively. It will be shown later that this is not the only solution. The part model

P2 P3

P1

Spatial decompostion
of part model

Figure 3.5: COMPACT DECOMPOSITION OF THE PART

is decomposed into layers P1, P2, P3 and doesn’t need any subdivision. The layers
S1,S2 of the support model do not need any subdivision, but layer S3 has to be
subdivided into compacts S3 1 and S3 2. The process sequence for this set of layers
and compacts will be P1-S1-S2-P2-S3 2-P3-S3 1.
Silhouette edges are used as the starting point in the decomposition algorithm.
There are two types of silhouette edges in a given model, surface silhouette edges
and boundary silhouette edges. Surface silhouette edges are those that exist inside a
surface and boundary silhouette edges are those that serve as the common boundary
CHAPTER 3. SPATIAL DECOMPOSITION 25

S2

S1

S3

S3_1

S3_2

Spatial decomposition
of support model

Figure 3.6: COMPACT DECOMPOSITION OF THE SUPPORT

edge between two surfaces. The surface silhouette edges are present only in non-
monotonic surfaces and are used to subdivide the surface into monotonic surfaces.
At the end of this subdivision, the model will consist only of boundary silhouette
edges. These boundary silhouette edges are connected to form closed silhouette loops.
Figure 3.3 shows the silhouette edges and loops in the example part. Partition surfaces
are obtained as ruled surfaces by sweeping a certain set of silhouette edges along the
z direction. These partition surfaces are used to decompose the model into layers and
compacts.
Since a compact can consist of both undercut and non-undercut surfaces, a
compact with undercut surfaces can be processed only when all other compacts with
which the current compact shares its entire undercut surface have been created. Each
CHAPTER 3. SPATIAL DECOMPOSITION 26

compact is accumulated on the pre-built non-undercut surfaces of other compacts and

provides new non-undercut surfaces for supporting other compacts to be processed
later. Since silhouette loops represent the common boundary between undercut and
non-undercut portions, they play a very important role in the generation of compacts.
Any portion of the model with purely concave silhouette edges cannot be a
compact because the non-undercut surface cannot be reached from top as there is
an undercut surface hanging over a non-undercut surface. The exception to this is if
the concave silhouette edge has its adjacent non-undercut surface as a vertical surface.
A convex silhouette edge and a concave silhouette edge appear as a pair, because a
convex silhouette edge for the part model is a concave silhouette edge for the support
model and vice versa. For instance, a spherical surface of a positive ball has a convex
silhouette circle while that of a negative ball has a concave silhouette circle.

3.2.3 Related work

The concepts of silhouette edges and loops are well known in the context of hidden
line/surface removal algorithms. Appel[4] proposed a hidden line removal algorithm
based on quantitative invisibility, which stands for the number of covering surfaces
such that quantitative invisibility at visible points is equal to zero. He pointed out
that quantitative invisibility changes when a point passes through a silhouette edge.
Hornung[28] as well as Schweitzer and Cobb[55] indicated that connected silhouette
edges form a closed loop. Walter[64] uses silhouette edges as a means for surface
rendering. He generates silhouette edges as point sequences and uses them to compute
sight indices that are then used to clarify the visibility of the surface. However, these
studies were aimed at generating projected images rather than decomposition of CAD
models. Silhouette edges were used just for eliminating hidden parts of lines or for
determining the ends of scan lines.
Researchers in the graphics area have also looked at the problem of generating
surface silhouette edges. Schweitzer and Cobb[55] use a surface intersection method
to compute silhouette edges on tensor product polynomial surfaces. In their approach,
normal surface N , obtained by the surface representation of the normals at each point
CHAPTER 3. SPATIAL DECOMPOSITION 27

on the surface S, is intersected with xy plane to obtain the silhouette edges. Their
method was limited to bicubic patches and the algorithm has limitations when the
normal surface is degenerate. Beusmans[6] outlines a method to generate silhouette
edges of a model using its spherical image. The spherical mapping relates the points
on the surface of a model with points on a unit sphere representing all possible surface
normals. The algorithm makes use of the fact that the spherical image of a silhouette
edge is confined to the great circle on the unit sphere. In this method, the extraction
of silhouette edges is free of degeneracies and fairly straightforward subject to the
generation of the spherical image of the object.

3.2.4 Requirements
The requirement for each compact is as follows:

• A ray cast along the z-axis from the top should enter the compact through its
non-undercut surface and exit through its undercut surface.

• Any non-undercut surface of a compact cannot be covered by its own undercut

surfaces.

• The ray hits a non-undercut surface and an undercut surface at most once.

These requirements can be expressed in terms of the silhouette edges and silhouette
loops as below.

Concave silhouette edges: There shouldn’t be any concave silhouette edge in a

compact. In a model with concave silhouette edges, the non-undercut surface is
covered by its own undercut surface. Here, the silhouette edge indicate a local
self-overlap like in a bellow.

Self-intersections of a projected silhouette loop: The xy projection of the sil-

houette loop shouldn’t have any self-intersections. If the projection of a
silhouette loop has self-intersections, then there exists at least one ray that
will hit a non-undercut surface and an undercut surface more than once. Here,
there exists a global self-overlap like in a spiral shape.
CHAPTER 3. SPATIAL DECOMPOSITION 28

Even if each compact fulfills the above two requirements, it might so happen that the
compact cannot be processed due to a sequence conflict between the compacts.
The compacts have to be ordered based on their relative z positions. The compact
with a lower z value must be sequenced before the one with a higher z value. The
z position of a compact is its minimum z value. All the compacts must be simply
ordered in a sequence to be processed. However it is sometimes impossible to sort
all compacts in a sequence based on the relative z positions. This could happen
if there exist cyclic ordering relation as shown in Figure 3.7. Here A covers B, B
covers C, and C covers A. This means A cannot be processed before B, B cannot be
processed before C, and C cannot be processed before A. Therefore none of them can
be processed in the given form. In terms of silhouette loops, this requirement can be
stated as follows.
Cyclic ordering among silhouette loops If the ordering relations between sil-
houette loops of compacts form a cycle, those compacts cannot be processed in
a sequence.

A<C
A C<B
B
B<A

Figure 3.7: CYCLIC ORDERING

3.3 Algorithm
The algorithm decomposes the given model such that the resulting set of compacts
satisfies the following conditions.
CHAPTER 3. SPATIAL DECOMPOSITION 29

1. No concave silhouette edges in a compact.

2. No self-intersections of the projected silhouette loop of the compact.

3. Silhouette loops of different compacts do not have a cyclic ordering among them.

Concave silhouette loop

P2
P1

Figure 3.8: COMPACT DECOMPOSITION USING INFINITE SWEEP

The algorithm has some similarities to the Weiler-Atherton hidden surface algo-
rithm which subdivides the polygons by clipping with other polygons based on a depth
sort of the polygons[66]. In our approach we subdivide a solid model by clipping with
silhouette edges.
CHAPTER 3. SPATIAL DECOMPOSITION 30

In order to decompose a model using silhouette edges, one approach is to use swept
surfaces obtained by sweeping those silhouette loops that violate the conditions above,
along the z-direction. Since an infinitely long prism separates the entire space into
two regions, a sufficiently long swept surface of the silhouette loop will split the model.
Figure 3.8 shows the decomposition of the example part using this method. Here,
the concave silhouette loop is swept along the positive z-direction to split the model
into two compacts, P1 and P2. It can be observed that both the compacts satisfy
the three conditions.
In SDM, these compacts might have to be split further using horizontal planes
in order to satisfy some process constraints. In keeping with the nature of the
process, in our second method we use horizontal planes together with swept surfaces
to decompose the model. The use of horizontal planes has the following advantages:

• Some process constraints that impose maximum depth requirements can be

accommodated. The maximum depth requirement is dictated by factors such
as cutting tool length (such that all portions of compact that needs to be cut is
accessible by the tool) and maximum deposition height (such that we get good
quality deposits).

• The bonding between compacts is usually better across horizontal sections.

• The swept surface along the z-direction could be bound by the horizontal planes.

The steps involved in this algorithm are given below:

1. Generation of monotonic surfaces

Non-monotonic surfaces are sub-divided into monotonic surfaces by splitting
them along the silhouette edges on the surface (Figure 3.9). At the end of this
step, all the surfaces of the model can be categorized into either undercut or
non-undercut.

2. Generation and Classification of silhouette edges

Silhouette edges separating undercut surfaces from non-undercut surfaces are
identified for the entire model (Figure 3.9). These edges are then classified into
CHAPTER 3. SPATIAL DECOMPOSITION 31

Step 1 : Monotonic surface generation Step 2: Generation of silhouettes

Step 3: Decomposition along horizontal planes

Figure 3.9: FIRST THREE STAGES OF THE ALGORITHM

concave and convex silhouette edges based on the configuration of the adjacent
surfaces.

3. Model decomposition along horizontal planes

All continuous segments of concave silhouette edges are detected and the model
is split along horizontal planes passing through both the lowest and highest
points of the concave silhouette segment (Figure 3.9).

4. Generation of silhouette loops

CHAPTER 3. SPATIAL DECOMPOSITION 32

The algorithm recalculates silhouette edges on subdivided model and creates

silhouette loops by tracing the silhouette edges. One silhouette edge is selected
first to start the silhouette loop. Then the silhouette edge which joins it next is
added to the loop. This process is continued till the first edge is reached again.
The same procedure is repeated until all the silhouette edges have been added
to silhouette loops. The silhouette loops are projected onto the xy-plane and
the intersections among the projected silhouette edges are examined.

Decomposition along open concave silhouette edges

Figure 3.10: DECOMPOSITION ALONG CONCAVE SILHOUETTE EDGES

5. Decomposition along concave silhouette edges

Concave silhouette edges are swept along the z-direction to form partition
surfaces. These partition surfaces are used to decompose the model. The
method for generation of partition surface depends on the nature and interaction
of concave silhouette edges.

• If the projected silhouette loop containing the concave silhouette edges

has self-intersections between the concave silhouette edges, the sub-loop
having its ends at the intersection point(s) is used to obtain the swept
partition surface.
CHAPTER 3. SPATIAL DECOMPOSITION 33

• If the silhouette loop contains both concave and convex silhouette edges,
then there will be isolated concave silhouette edges. Each of these iso-
lated concave silhouette edge will have an undercut surface and a non-
undercut surface as its adjacent faces. The partition surface is obtained
by sweeping the boundary of the adjacent undercut surface along the z-
direction.(Figure 3.10).
• If the entire silhouette loop is made up of concave silhouette edges, the
silhouette loop is swept in the z-direction to generate the partition surfaces.

This step eliminates all the concave silhouette edges.

Silhouette loop

CAD model

Projected silhouette loop

Figure 3.11: MODEL WITH SELF-INTERSECTING PROJECTED SILHOUETTE LOOP

6. Decomposition to eliminate self-intersections of projected silhouette loop

The algorithm detects all self-intersections of the projected silhouette loops.
If there are self-intersections, there will be an even number of them. The
overlapping portion of the self-intersecting loop is swept to form the partition
surface that is used to decompose the model.
CHAPTER 3. SPATIAL DECOMPOSITION 34

To illustrate this, consider the example shown in Figure 3.11. The model
consists of four triangular prisms joined to form a spiral shape. Figure 3.11
also shows the silhouette loop and projected silhouette loop for this model. It
should be noted that silhouette loop is entirely made up of convex silhouette
edges. By sweeping the overlapping portion(Figure 3.12) of the silhouette loop
the model is decomposed into two compacts C1 and C2 as shown in Figure 3.12.

Overlapping portion
of silhouette loop

C2

C1

Figure 3.12: DECOMPOSITION TO ELIMINATE SELF-INTERSECTIONS OF PROJECTED SILHOUETTE LOOP

7. Decomposition to eliminate cyclic ordering

At this stage no projected silhouette loop has self-intersections. The algorithm
detects intersections between any pair of silhouette loops and determines the
ordering relation according to the relative depth of them. If there is a cyclic
ordering among the silhouette loops, one of the models containing the silhouette
CHAPTER 3. SPATIAL DECOMPOSITION 35

loop causing the cyclic ordering is split (Figure 3.13) by sweeping the overlap-
ping portion of the silhouette loop. It can be observed that this case is similar
to the self-intersection case.

Overlapping portion A<C

of A to be split C<B
A B
B<A

A3 A2 < C
B C<B
B < A3
A2 C

A1

Figure 3.13: SPLITTING SILHOUETTE LOOPS TO AVOID CYCLIC ORDERING

8. Determination of process sequence

Figure 3.14 shows the decomposition of the example part and the support using
this algorithm. The part is split into two compacts P1 and P2 and the support
is split into three compacts S1, S2 and S3. Now the compacts have to be
ordered to determine the process sequence. This is based on the nature of
shared faces between different compacts. If a compact contains an undercut face
(S1), then the compact containing the corresponding non-undercut face (P1)
has to be processed before it. Thus for each compact, a list of compacts to be
CHAPTER 3. SPATIAL DECOMPOSITION 36

processed before it is placed before it in the compact sequence list. This process
is repeated for all compacts. The process sequence for this set of compacts will
be P1-S1-S2-P2-S3.

S3
S2
P2

P1

S1

Sequence - P1 -> S1 -> S2 -> P2 -> S3

Figure 3.14: COMPACT DECOMPOSITION WITH PROCESS SEQUENCE

3.4 Summary
An algorithm for the decomposition of any 3-D model into layers and compacts was
described. This decomposition method enables the manufacture of complex, multi-
material objects in SDM. Geometric model decomposition is accomplished through a
sequence of geometric operations. Silhouette edges and silhouette loops are identified
to help in the decomposition of model. The geometric requirements to be satisfied by
CHAPTER 3. SPATIAL DECOMPOSITION 37

a compact are expressed in terms of these silhouette edges and loops. The algorithm
then progresses to decompose the given model into compacts whose silhouette edges
and loops do not violate any of those requirements. Unlike techniques used in
SFF methods which divide models into equally spaced slices, the present algorithm
decomposes models into layers which are not necessarily planar and equally spaced.
This has the advantage that the surface information of the original model is preserved
and utilized for further process planning steps including CNC cutter path generation.
In addition, processing methods permitting, relatively thick layers can be fabricated
at once resulting in an increased building rate. Another key step of the present
algorithm is the determination of the process sequence. Solely based on geometric
arguments a feasible sequence of material addition and removal processes is found.
Chapter 4

Deposition Path Generation

In SDM, material is deposited by a variety of deposition techniques. Most of the parts

were built using plasma or laser based droplet-deposition process. In addition to these,
some of the other deposition processes being explored in SDM include selective casting
of two-component or UV-curable resins, ceramic deposition, sputtering, plasma arc-
jet coating and hot pressing of powders. The deposition path generation is dependent
on the nature of the deposition process. Deposition path generation for processes that
have fine, statistically distributed particles are somewhat independent of geometric
complexity. On the other hand, deposition paths for processes that have coarse,
discreetly deposited particles are influenced by geometric complexity. Also, the
property of the deposited material will be influenced by the deposition path trajectory.
Thus it is important to understand some of the deposition methods that are used in
SDM. Also, one of factors that limits the quality of parts in SDM is the accumulation
of residual thermal stresses. It might be possible to reduce this effect by selecting
an appropriate deposition path. The next section describes some of the deposition
techniques used in SDM. In the following section, methods are described to generate
different types of depositions paths.

38
CHAPTER 4. DEPOSITION PATH GENERATION 39

4.1 Deposition Methods in SDM

Microcasting Microcasting [43],[67] is a droplet-based deposition process that com-
bines the benefits of welding and thermal spraying. Figure 4.1 shows the
working principle of microcasting. An arc is established between a tungsten
electrode and a charged contact tip in gas-filled environment. A wire that is

Wire feed

Gas feed
AAAA
Gas feed

AAAA
AAAA
AA
Power Supply
-+

Inerting shroud
AAA
AAA A
AAA Tungsten Electrode

Shielding Gas Substrate

Figure 4.1: WORKING PRINCIPLE OF MICROCASTING

fed through the charged contact tip melts in the arc forming a molten droplet.
The molten droplet falls from the wire when its weight overcomes the surface
tension. The droplet is accelerated by gravity and falls on the substrate. In
contrast to the small droplets produced by thermal spraying, microcast droplets
are relatively large (1 to 3 mm dia.). Due to their large volume-to-surface ratio,
they remain superheated until impacting the substrate and contain sufficient
energy to locally remelt the underlying substrate to form metallurgical bonding
upon solidification.

Laser Deposition system The laser deposition process [20] is similar to laser
CHAPTER 4. DEPOSITION PATH GENERATION 40

cladding or laser welding. Figure 4.2 shows the schematic of the laser deposition
system. Metal powder is injected into a melt pool at the laser focus on the
substrate. As the laser scans over the surface, the injected powder fuses onto
the substrate. Since the laser can be positioned accurately, and the material
is deposited only where the laser strikes the surface, it is possible to deposit
near-net shapes using this deposition method.

Laser

Powder

Deposit

Substrate

Figure 4.2: WORKING PRINCIPLE OF LASER DEPOSITION SYSTEM

4.2 Generation of deposition paths

Some of the factors that will influence the type of deposition path are :

• Accumulation of thermal stresses - Thermal stresses will accumulate if there is

an uneven heating of the surface. Thus, if the deposition path is unsymmetrical,
it will result in thermal stresses.

• Number of deposition segments - If there are many discontinuous deposition

CHAPTER 4. DEPOSITION PATH GENERATION 41

segments, the deposition gun might have to be switched off between different
segments or might have to be moved fast.

• Robustness - The deposition paths should be generated irrespective of the

complexity of the geometry.

• Uneven material deposition - We should try to avoid revisiting the same position
in the path as this will result in extra material deposition in those areas with
the associated reheating. Uneven material deposition will also result in those
areas of the path where the deposition gun spends more time. (eg., places where
the deposition gun reverses its direction)

• Avoiding gaps in the path - All portions of the given geometry should be covered
by the deposition gun. Since, gaps would result in serious problems, it is better
to be conservative in depositing the material.

4.2.1 Types of deposition paths

Deposition path planning is in many ways similar to path planning for pocket milling.
The work by Held [26] serves as a good reference for research in the context of cutter
path generation for pocket milling. The above factors make the deposition path
generation a more constrained problem compared to pocket milling and thus warrants
a different approach. The deposition paths are generated for the 2-D cross-section
obtained by the XY projection of the compact. These cross-sections have to be offset
by a certain distance before generating the deposition paths. The offsetting operation
is similar to the one described in Chapter 5, Section 5.4. Geometrically, the deposition
paths could be classified into two types (Figure 4.3):

• Spiral paths - It comprises of a series of contours that are parallel to the

boundary of the 2-D cross-section.

• Zigzag paths - The path segments correspond to back and forth motions in a
fixed direction within the boundary of the 2-D cross-section.

It is possible to derive a variety of deposition path patterns from these two paths.
CHAPTER 4. DEPOSITION PATH GENERATION 42

Spiral Path Zigzag Path

Figure 4.3: TYPES OF DEPOSITION PATHS

Spiral Paths

Spiral paths could be generated by two methods - Recursive offsetting method and
MAT based method.The distance d between successive offsets will be a function of
the deposition width w and is dependent on the type of deposition process.

Recursive offsetting method In this method the 2-D cross-section is shrunk re-
cursively using the offset operation. The shrunk cross-sections could be obtained
by two methods.

• By offsetting the original cross-section by −d, −2d and so on till a null

shrunk cross-section is obtained.

Ais = Ao − i ∗ d ∗ b̂ (4.1)

Ais is the ith shrunk cross-section

Ao is the original cross-section
CHAPTER 4. DEPOSITION PATH GENERATION 43

b̂ is the unit binormal vector

i = 0, 1, ...n where Ans = NULL

• By offsetting the previous cross-section by −d and repeating the process

till a null cross-section is obtained.

Ais = Ai−1
s − d ∗ b̂ (4.2)

Ais is the ith shrunk cross-section

b̂ is the unit binormal vector
i = 1, ...n where Ans = NULL
A0s = Ao , the original cross-section

The deposition path is obtained by employing the collection of the shrunk cross-
sections, [Ais , i = 0, ...n − 1], as centerline trajectories for the deposition gun.

MAT based method The Medial Axis Transform (MAT) was defined by Blum [7]
as an alternate description of the shape of an object. The MAT of a 2-D model
could be defined as the closure of the set of the centers of maximal circles which
can be fit inside the object (Figure 4.4). In the literature, algorithms have
been described to generate the MAT of 2-D models [23],[36]. The algorithm

Maximal circles MAT

Figure 4.4: MAT OF A RECTANGLE

described by Gursoy and Patrikalakis [23], handles multiply connected regions

with boundary elements that can be composed of straight lines, circular arcs
and NURBS curves. The radius of the maximal circle is stored as an attribute of
CHAPTER 4. DEPOSITION PATH GENERATION 44

the points of MAT. Figure 4.5 shows the steps involved in obtaining a deposition
path based on the MAT of the model.

MAT of the model

A path obtained from MAT

Figure 4.5: MAT BASED DEPOSITION PATH

In order to generate the deposition paths based on the MAT based method, the
MAT of the 2-D model is generated along with the radius function at each point.
The successive offset cross-sections are obtained from the MAT by growing the
MAT model in multiples of d. The grown cross-section at the k th level can be
thought of as the union of circles of radius k ∗ d and centers along the MAT.
If the growing distance k ∗ d is greater than the radius of the maximal circle
at any point, then that point is not grown and the grown cross-section will be
divided into sub-regions at these points. The process is stopped if all points
have their maximal circle radii less than the growing distance. In contrast to
CHAPTER 4. DEPOSITION PATH GENERATION 45

the recursive offsetting method, with the MAT based method it is possible to
have uniform overlaps between successive paths by splitting the radius function
into equal intervals.

It can be noted that with spiral paths, we might get overdeposition or gaps in portions
of the 2-D model. The former occurs at distances less than d of offsets to unrelated
portions of the boundary. The latter occurs at regions between offsets that are of
width greater than d, wherein portions of offset segments might have been eliminated
to avoid self-intersections of the offset. Also, the fact that the thickness of the model
at a generic region may not be an integral multiple of d will lead to overlaps or gaps.

Zigzag paths

ln Zigzag path generation a series of parallel segments are generated along a direction
V . The common choices of V are the X or Y direction. But the optimal direction
would be parallel to the longer axis of the rectangular hull of the cross-section.
The rectangular hull is the minimum-area rectangle that encloses the cross-section.
Toussaint[61] describes a linear time algorithm to obtain the rectangular hull of a
simple polygon. His algorithm makes use of a theorem proposed by Freeman and
Shapiro[21].

Theorem 4.1 The rectangle of minimum area enclosing a convex polygon has a side
collinear with one of the edges of the polygon.

Based on this theorem the algorithm for constructing the rectangular hull (Figure 4.6)
can be described as below.

• Construct a polygonal model of the given cross-section.

• Construct the convex hull of the polygonized model. Algorithms for construct-
ing the convex hull could be found in the books related to computational
geometry [48], [56].

• Generate a set V of vectors parallel to the sides of the convex hull.

CHAPTER 4. DEPOSITION PATH GENERATION 46

a) Polygonal model b) Convex Hull c) Rectangular Hull

Figure 4.6: RECTANGULAR HULL CONSTRUCTION

• For each vector V in V, construct a rectangle R oriented along V by finding the

extremal points along V and along V 0 , where V 0 is ⊥ to V .

• The rectangular hull is given by the rectangle Rmin with the minimum area.

Parallel line segments are generated corresponding to the short or long axis of
rectangular hull of the 2-D cross-section. These set of segments are intersected with
the 2-D model to generate the set of parallel segments confined within the boundary
of the cross-section as shown in Figure 4.7. The end points of the segments at the
boundary are joined to generate continuous path segments. The relative merits of
spiral paths and zigzag paths have been studied by Wang et al. [65] in the context
of NC tool path generation. In their observation, the difference in total path length
to cover various convex polygonal regions between the spiral and zigzag paths is not
very large, typically < 5%. This will be true only if an optimal direction V selected
for the zigzag path. Thus if the direction for the zigzag path is chosen using the
above mentioned method, zigzag paths and spiral paths are not very much different
in terms of minimizing the total path length. Farouki et al. [18] have discussed the
advantages and limitations of these paths in the context of layered manufacturing
processes.
CHAPTER 4. DEPOSITION PATH GENERATION 47

a) Parallel Line segments b) Intersecting with the original shape

Figure 4.7: ZIGZAG PATH GENERATION

But with an evolving process like SDM, it is difficult to select the correct deposition
pattern. For most of the shapes, it might be possible to select the zigzag or the spiral
path as the deposition pattern. If these patterns are found to be unsuitable, it is
possible to find other deposition patterns as described below.

First pass of tower pattern Second pass of tower pattern

(shown in blue )

Figure 4.8: TOWER DEPOSITION PATTERN

Tower pattern This type of pattern has been discussed in Fessler et. al.,[20]. This
pattern can be derived from the zigzag pattern by selecting every alternate
segment of the zigzag pattern in the first pass and selecting the remaining
CHAPTER 4. DEPOSITION PATH GENERATION 48

segments in the next pass as shown in Figure 4.8. In this pattern, the deposits
will have a larger surface area to volume ratio during the cooling phase and this
will allow them to deform freely as they cool before they are constrained by the
adjacent deposits.

6
5
7

1 3

Figure 4.9: CONVEX DECOMPOSITION FOR DEPOSITION

Convex decomposition In this pattern, the given shape would be decomposed into
convex regions [8]. Each convex region could be deposited using the zigzag or the
spiral pattern. Thus, for example the shape shown in Figure 4.9 is decomposed
into seven convex regions and each of these seven regions can be deposited using
the spiral pattern. One of the advantages with this pattern would be that the
total path length would be near-minimal. If the shape is decomposed into many
convex regions, this pattern will also have the advantages of the tower pattern.

Cross hatch pattern If zigzag paths are generated in two perpendicular directions,
it will result in a cross-hatch pattern as shown in Figure 4.10. In the case of
the rectangular hull, the two directions would be parallel to the sides of the
rectangle. This pattern would avoid any gaps in the deposit. Its impact on the
residual stresses is not clear.
CHAPTER 4. DEPOSITION PATH GENERATION 49

Figure 4.10: CROSS HATCH DEPOSITION

4.3 Summary
Two droplet based deposition methods, microcasting and laser deposition system,
and algorithms to generate deposition paths were described. It was seen that the
deposition paths should be generated such that it prevents accumulation of thermal
stresses, avoids uneven material deposition and avoids gaps in the path. Two types of
deposition paths, spiral and zigzag paths were identified. Spiral paths were generated
by either recursive offsetting method or MAT based method and zigzag paths were
generated by an algorithm based on rectangular hull construction. Three other
deposition patterns that could be derived from spiral and zigzag paths were described.
The selection of a particular pattern depends on the type of the deposition method
and the quality requirements of the part. In SDM, the choice of the deposition pattern
type has been made based on heuristics and experience. Over time, as we get a better
understanding of the physics of the deposition process, it will be possible to select an
appropriate deposition pattern for a given deposition process.
Chapter 5

CNC Cutter Path Generation

5.1 Introduction
Research in CNC cutter path generation could be broadly classified into two areas.

• Automatic tool path generation using feature recognition techniques.

• Generation of CNC tool paths for sculptured surfaces.

In feature based techniques [1], [2], [62], full automation is possible only with com-
plete enumeration of all the manufacturing features which is practically impossible.
Thus manual input becomes essential at one stage in any feature based technique. In
non-feature based techniques, most of the work has been done in generating cutter
paths for surface models rather than solid models. And there too full automation has
been difficult due to gouging problems. In both these methods, automation becomes
impossible in the presence of undercut features. Problems related to tool accessibility
in deeper areas of the model and fixture related problem makes the automation of
CNC cutter path generation a daunting task.
In SDM, the compact is machined to the required shape through a series of CNC
cutting operations.The compact to be machined is free of undercut features and with
the small height of layers there won’t be any tool accessibility problems. Since the
CAD model will be decomposed into layers and compacts, the intuitive feeling for
features is lost and hence feature based techniques are not suited. Also, the generation

50
CHAPTER 5. CNC CUTTER PATH GENERATION 51

CAD Model of the Layer

(With Process and Tool Information)

Rough Cut Operation

Results in near-net shape of the layer

2-D Profile Cutting

Provides tool accessibility

If model non-prismatic

Finishing Operation
3-D cutting resulting in final shape

Figure 5.1: CNC CUTTING STAGES IN SDM

of CNC cutter paths has to be fully automatic in this process, as human intervention
with so many layers would cause considerable delays. Figure 5.1 shows the CNC
cutting stages in SDM. The first two steps, rough cutting and 2-D profile cutting,
primarily deals with 2-D geometric features and are classified under 2-D cutter path
generation and the last step, finish cutting, deals with 3-D geometric features and is
classified under 3-D cutter path generation. This chapter describes the steps involved
in generating 2-D cutter paths [50], [51] and the next chapter deals with 3-D cutter
path generation.

5.2 Rough Cutting

The first step after the deposition of material is a rough cutting operation aimed
at generating the near-net shape of the layer. The deposited layer is typically 2 12
times the height of the model and is about 1 12 times the size of the model in the
CHAPTER 5. CNC CUTTER PATH GENERATION 52

XY direction(Figure 5.2). The layer is machined to the safe height (model height
+ tolerance) through a series of planing steps(Figure 5.2 a-c). The planing path is

a)

Deposited Material

Bounding box of model

b)

Deposited material

c)

Planing steps

Figure 5.2: PLANING OPERATION

generated corresponding to the maximal XY rectangle of the deposited layer starting

at the top of the layer till the safe height is reached in steps of the depth of cut
allowable for the tool. At the end of the planing operation the deposited material
would be reduced to the height of a box enclosing the layer . The rough cutting
operation involved in producing the near-net shape of the layer from this box is
1
realized thorough an operation which we call manhattan decomposition.

In the literature there are very few references for efficient rough cutting algorithms.
In a recent work by Lee et al [37] the octree representation of a model is used in
efficient tool selection for the rough cutting operation. Manhattan decomposition is
an extension of the octree representation of a model. In manhattan decomposition,
adjoining full octants at the same level of the octree are joined to form manhattan
solids and the cutter paths are generated for these manhattan solids. The steps
involved in the algorithm are :

1. The model of the volume to be rough cut (Vrc ) is obtained by subtracting the
model of the layer from the model of the box left after the planing operation
(Figure 5.3).

1
A manhattan solid is defined as a solid in which the angle between the faces of the solid will be
either 90o or 270o
CHAPTER 5. CNC CUTTER PATH GENERATION 53

Vrc

Figure 5.3: VOLUME Vrc TO BE ROUGH CUT

2. Vrc is enclosed in a hexahedron. This hexahedron is subdivided into eight

hexahedron by equally dividing the height, depth and width of the hexahedron
(Figure 5.4a) . Let L = min(depth,width). Each hexahedron is classified into full
(completely inside the solid), empty (completely outside the solid) and partial
(partially inside/outside the solid). The classification of hexahedron is based on
the octree encoding algorithm by Krishnan et. al [35]. The full hexahedrons are
examined for cutting (steps 3 - 5) and the partial hexahedrons undergo further
sub-division (step 6)

3. The full hexahedrons are then joined with the neighboring full hexahedrons
in the X and Y directions to form the manhattan solid(s). The largest tool
diameter that could be used at this stage is d = min(Li ) where Li is the
min(depth,width) of the ith hexahedron in the solid. There will be 2l layers
of manhattan solids, where l is the level of octree decomposition. For each of
these solid, the shape to be machined SectionSM is got as the projection of
manhattan solid(s) on the XY plane (Figure 5.4b).

4. The cutter path is then generated for SectionSM ’s at different height levels
depending on the allowable depth of cut of the tool. A flat end-mill is used for
this operation.
CHAPTER 5. CNC CUTTER PATH GENERATION 54

Full Partial
b) SectionSMof Manhattan solid

a) Octree Generation
(top view)

c) SectionSM after tool offset

by d/2

Figure 5.4: STEPS IN THE ROUGH CUT ALGORITHM

5. SectionSM is offset for the tool radius before the path is generated (Figure 5.4c).
Since the cross-section will contain only edges that are parallel to X or Y axes
and since the cutter diameter is chosen as min(Li ), the offset section can be
generated without much computational effort. The path could be either lawn
mower type of cutting or spiral cutting (Figure 5.5). Due to the cylindrical
shape of the tool, there will be an un-cut area of the manhattan solids at
convex corners. The full hexahedrons corresponding to these un-cut areas go
into further subdivision after subtracting the areas that were machined.

6. The partial hexahedrons and the hexahedrons generated from the previous step
are subdivided as mentioned in step 2 and the steps 3-5 are repeated till the
required resolution level is reached. The subdivision in width or depth direction
will be stopped if at any level, the width or depth of a hexahedron is smaller
than the smallest tool available and will be stopped in the height direction if
the height becomes smaller than a certain tolerance value.
CHAPTER 5. CNC CUTTER PATH GENERATION 55

Lawn Mower type Spiral

Cutting Cutting
Figure 5.5: TYPES OF ROUGH CUT PATHS

5.3 Two Dimensional Profile cutting

After the rough cutting operation a two dimensional profile cutting is done in order
to provide tool accessibility for the final five-axis contouring operation. In the case
of the prismatic models, this two dimensional cutting operation will also serve as
the final contouring operation. The model (M2d ) for this operation is the bottom
cross-section of the layer. Since the layers in SDM manufacturing will not have
any undercut features, profiling the bottom cross-section will not pose any cutter
interference problems. The generation of cutter path in this step requires an offsetting
of (M2d ) by the radius of the cutter. The offsetting operation is described in the next
section.
The method for generation of cutter paths depends on the type of offset operation
used. If the linearized offset method is used, the cutter path is generated by traversing
along the vertices of the offset model.

5.4 Offset of TwoD Profiles

Extensive research has been done in offsets of curves with most of the methods being
approximate offsets [11],[47], [60]. The offset curve Co (t) of a curve C(t) is defined as
Co (t) = C(t) + r * b̂(t) where b̂(t) is the binormal vector to the curve at parameter
CHAPTER 5. CNC CUTTER PATH GENERATION 56

value t. The offset curves generated thus, will have degenerate cases [47] as shown
in Figure 5.6. These degenerate offset curves when used for machining will result
in gouging or un-cut areas. Also, the curves are assumed to possess a well-defined
tangent vector at each point. In our approach we make use of an offset algorithm for
a polygon model to generate the offset of the two dimensional model.
The curves forming the edges of the model are approximated by linear segments

B
E

A - Requires additional curve segments

B - Entire curve segment to be removed
C - Loop and Cusps
D - Self intersecting offsets
E - Portions of curve segment to be removed

Figure 5.6: DEGENERACIES IN CURVE OFFSET

such that the deviation between the linear segments and the curves is less than the
tolerance of the NC machine. Thus the new model (M2dl ) consists of linear segments
as its edges (Figure 5.7a). This new model is now offset for the radius of the cutter.
In order to avoid gouging, it is ensured that no portion of the offset is closer to the
model than the offset distance. The steps involved are:

• For each edge of the model, a face model is formed. Let v1 and v2 be the
vertices of the edge. Let αi be the angle between the edges meeting at vertex
vi where the angle αi is measured at the inside of the cross-section. Depending
on value of αi the location of offset vertices of the face model are determined
(Figure 5.7b).
CHAPTER 5. CNC CUTTER PATH GENERATION 57

nv2 a) Linearized model nv2

v v

2 2

t 1

r 2
b
v1 d

nv1
1 1

v1 nv1
v1
nv1 nnv1
b) Face model of edge e c) Modified face model of edge e

Figure 5.7: OFFSET COMPUTATION

– If αi ≤ π, (convex corner)

nvi = vi + (−di t̂ + −r b̂) (5.1)

else if αi ≥ π (concave corner)

nvi = vi + −r b̂ (5.2)

where,

di = r tan (π − αi )/2f ori = 1, 2 (5.3)

r = radius of the cutter

t̂ = unit tangent vector along the edge (from v1 to v2 )
CHAPTER 5. CNC CUTTER PATH GENERATION 58

b̂ = unit binormal vector pointing in the direction of the face

– The face model corresponding to the edge is formed by the vertices

v1 , nv1 , nv2 , v2 , v1 taken in that order.

• The face models of all the edges are then merged with the original model M2dl
to form the offset model M2do

• The boundary edges of M2do gives the required offset model (Figure 5.8).

• As shown in Figure 5.8, all the degenerate cases are handled in a robust manner
by this method.

Figure 5.8: OFFSET MODEL WITHOUT DEGENERACIES

• In the case of convex corners, when the angle between the edges is too small, d1
could be very high thus moving the offset vertex far from the corner. Though
this will not result in any gouging while cutting it will delay the machining
process. This could be taken care by generating one more vertex whenever the
angle is less than π /2. (Figure 5.7c) nnv1 = v1 + −r(cos α1 /2 t̂ + sin α1 /2 b̂)
and d1 used in equation 5.3 is modified to be r tan (π − α1 )/4. Similar relation
will apply for vertex v2 except for the change of sign of t̂. In such cases, the face
model would be formed by the vertices v1 , nnv1 , nv1 , nnv2 (if α2 ≤ π/2),nv2 , v2 .

• The cutter path is generated by traversing along the vertices of the offset model.
CHAPTER 5. CNC CUTTER PATH GENERATION 59

5.5 Summary
A sequence of CNC cutting operations have been proposed to generate the required
shape of the compact in an automated fashion. Cutter path generation for the
operations that deals with 2-D geometric features have been described. A new
method of decomposition, manhattan decomposition, that is an extension of octree
decomposition, has been proposed for generating efficient rough cutting paths. The
degeneracies that could occur during the offset of 2-D cross-sections, an operation
that is required for generating 2-D cutter paths, have been identified. A robust
offset algorithm has been described that handles all those degeneracies by offsetting
the polygonized model. The 2-D cutting operation serves as the final contouring
operation in the case of prismatic solids and serves to provide tool accessibility for
3-D cutting in the case of non-prismatic solids.
Chapter 6

3-D Cutter Path Generation

6.1 Finishing operation

The final cutting operation employed in realizing the shape of the layer is the finishing
cutting operation. The CNC cutter path is to be generated for the layer composed
of free-form surfaces. This is in many ways similar to the conventional NC tool path
generation problem. In contrast to conventional methods, we don’t have undercut
features and fixturing problems. Since our layers are thin, all areas of the layer will
be within the reach of the tool. Our approach has to be fully automatic as manual
intervention with so many layers in the model will introduce considerable delay in
the process and it is also intuitively difficult for a person to debug the path in the
absence of the whole model.
Though NC cutter path generation is an actively researched area, few papers
related to automatic 5-axis NC cutter path generation are published. Most of the
earlier papers [9],[16],[30] primarily dealt with 3-axis milling using a ball end mill
cutter. Some of the recent publications [14],[40] have addressed the issues of 5-axis
milling. In the work by Li and Jerard [40], a method is described for the generation
of gouge-free 5-axis tool paths for composite surface patches. Their method uses
the polygonal representation of the surfaces. Elber [14] describes an approach which
reduces the accessibility problem of 5-axis milling on a convex surface to a 3-axis
accessibility problem which subsequentally helps in generating 5-axis tool paths for

60
CHAPTER 6. 3-D CUTTER PATH GENERATION 61

convex surfaces.
In our approach we decompose the model into three types of regions (Figure 6.1.

• Flat-end milled regions : Regions of the model that could be cut with a
flat-end mill that is positioned with its axis aligned along the normal to the
surface.

• Peripheral milled regions : Regions of the model that could be cut with a
flat-end mill with its side tangential to the surface.

• Three axis milled regions : Regions of the model that are cut with the x,y,z
axis movements of the cutter. The ball-end milled regions comes under this
category.

Flat-end milled Peripheral milled

Three axis milled

Figure 6.1: TYPES OF CUTTER REGIONS

Due to the geometrical nature of the layers in our process, it should be possible to
machine all surfaces with the ball-end mill cutter. But for low curvature surfaces, flat-
end mills are shown to give a better surface finish and are found to reduce the overall
cutting time compared to the ball-end mill [63]. Thus based on curvature information,
the regions of the layer are assigned to one of the above mentioned categories.
CHAPTER 6. 3-D CUTTER PATH GENERATION 62

The theory behind surface curvatures is well understood in differential geometry

[13],[34]. For our model decomposition, we need only the Gaussian curvature of
a surface. The Gaussian curvature at the parameter value (u,v) of a surface S is
K(u, v) = κ1 κ2 where κ1 and κ2 are the principal curvatures at the parameter value
(u.v). Thus if X(u,v) is a regular parametric surface, the Gaussian curvature could
be expressed as [13],

eg − f 2
K = (6.1)
EG − F 2

where,
* +
∂2X
e = N, (6.2)
∂u2
* +
∂2X
f = N, (6.3)
∂u∂v
* +
∂2X
g = N, (6.4)
∂v 2
* +
∂X ∂X
E = , (6.5)
∂u ∂u
* +
∂X ∂X
F = , (6.6)
∂u ∂v
* +
∂X ∂X
G = , (6.7)
∂v ∂v
,
∂X ∂X ∂X ∂X
N = X X (6.8)
∂u ∂v ∂u ∂v

where h·, ·i denotes an inner product.

Those regions of the surface for which K = 0, is developable or ruled, those for
which K > 0, is concave or convex and those for which K < 0 is saddle. Thus by
finding the zero set of K it is possible to separate the regions into developable/ruled
or concave/convex or saddle. In [15], the numerator of equation 6.1 is computed
symbolically as a scalar field by using unnormalized surface normal N̂ which is given
by the numerator of equation 6.8. The numerator of equation 6.1 is then given by
CHAPTER 6. 3-D CUTTER PATH GENERATION 63

êĝ−fˆ
Num = where ê, fˆ, ĝ are of the same form as equations 6.2, 6.3, 6.4 with N
kN̂ 2 k
replaced by N̂. The numerator of Num is then represented as NURBS, and the zero
set of it is found using the contouring techniques developed for free-form surfaces. This
will be the zero set of K as well. Then by assuming the curvature continuity of the
surfaces, trimmed surfaces are created, each of which is completely convex, concave
or saddle. The saddle regions can be identified by the sign of Num at a single point in
each trimmed surface, while the convex and concave regions are identified by finding
the sign of one of the principal curvatures at a point. Thus, this method is attractive
for separating well-behaved surfaces into convex, concave and saddle regions. But
this method ignores the possibility of developable regions and assumes the surface to
be regular and curvature continuous. Also, the computation of scalar fields for higher
order NURBS surfaces required the surfaces to be split into Bezier patches.
In the presence of the imperfect surfaces, a fully numerical technique may be better
suited. A grid of points is formed in the surface. The principal curvatures κ1 (p) and
κ2 (p) are computed at each point on the grid. p is then grouped into a sub-grid based
on the values of principal curvatures.

• If κ1 (p) > 0, κ2 (p) > 0, p is grouped in the concave grid.

• If κ1 (p) < 0, κ2 (p) < 0, p is grouped in the convex grid.

• If κ1 (p) > 0, κ2 (p) < 0

or p is grouped in the saddle grid
κ1 (p) < 0, κ2 (p) > 0

• If κ1 (p) = 0, or κ2 (p) = 0, p is grouped in the developable grid.

The original surfaces are then trimmed to the sub-grids to form the trimmed
surface patches each of which is completely convex, concave, saddle or developable.

These trimmed surface patches are further categorized as:

• Convex patches - Since convex patches could be machined with the flat-end mill
cutter, they are categorized as flat-end milled regions.
CHAPTER 6. 3-D CUTTER PATH GENERATION 64

• Saddle patches - The parts of saddle patches for which one of the principal
curvatures has a low positive value are categorized as flat-end milled regions
and the rest is categorized as three axis milled regions.

• Concave patches - Only those parts of concave patches where both the principal
curvatures are low, are categorized as flat-end milled regions and the rest comes
under three axis milled regions.

• Developable patches - The developable patches could be machined using the

side of the cutter if the cutter axis is aligned along the principal direction with
zero curvature. Hence the developable patches are categorized as peripheral
milled regions

The cutter paths are then generated for the three regions.

Figure 6.2: SURFACE SHRINKING FOR FLAT-END MILLED REGIONS

• Cutter path for flat-end milled regions : No surface offset operations are needed
for flat-end milled regions[40]. In this, the operation involved in compensating
for the tool radius is surface shrinking, in which the the curves bounding the
surface are moved along the surface by a distance given by the radius of the
tool (Figure 6.2). Cutter paths are generated by indexing the tool along the
the shrunk surface with the orientation of the tool along the surface normal.
CHAPTER 6. 3-D CUTTER PATH GENERATION 65

Isoparametric curves along with the surface normal information are used for
this purpose.

• Cutter path for peripheral-end milled regions : Cutter path generation for
peripheral end milled regions requires the computation of offset surfaces at a
distance equal to the radius of the cutter. Since the peripheral end milled regions
are composed of developable or ruled surfaces, there won’t be any degeneracies
that occur in surface offset operations. The cutter paths are generated by
orienting the tool along the principal direction with zero curvature.

a) Surface to be 3-axis milled b) Intersection curves

Figure 6.3: INTERSECTION CURVES FOR 3-AXIS MILLED REGIONS

• Cutter path for three axis milled regions : Most of the literature for CNC
cutter path generation [9],[30],[59] has been written for this category. In most
of these cases ball-end mills are used. Here we consider two approaches. One
is the use of adaptively extracted isocurves [16] to generate cutter paths. This
method requires the computation of the offset surfaces. In a work by Tang et
al. [59], an offset algorithm has been described that not only offsets surfaces
but offsets boundary curves of the surfaces to generate tool paths that are
smooth and have minimal un-cut area. But the offset surface may contain
degeneracies like self-intersections [3] which are difficult to detect effectively.
Hence, from a practical consideration, we have used intersection curves obtained
by intersecting the region with parallel planes to generate the cutter paths
(Figure 6.3). The intersection curves are offset for the radius of the tool in a
manner similar to that described in the previous section and these offset curves
are used to cutter trajectories with the cutter oriented along the z-direction.
CHAPTER 6. 3-D CUTTER PATH GENERATION 66

6.2 Collision Free Paths

In the previous section, the cutter paths were generated without considering the cutter
interference problem [38]. Cutter interference could be caused due to the interaction
between different regions of the model and those between the model and machine
components. The paths are generated to be executed in a 5-axis NC machine with
two revolute joints and three prismatic joints. While the joint limits of the prismatic
joints are of less importance (as the size of the parts are usually well within the
limits), the joint limits of revolute joints have to be considered while generating the
paths.

6.2.1 Collision types

The paths can have collision from the following sources.

• Single surface gouging (SSG) : Gouging results when the tool overcuts the
part surface (Figure 6.4 a). SSG is often encountered when the tool size is too
large relative to the concave radius of curvature.

• Multiple surface gouging (MSG) : This type of gouging occurs when the
tool positioned in correct position results in an interference with the adjacent
surface(s) (Figure 6.4 b).

• Collision with Machine Structure (CMS) : This occurs when the machine
components (tool head, coolant supply, etc.,) collide with the workpiece.

• Revolute Joint Limits (RJL) : Though this is not an actual collision, the
limits on the revolute joints can be modeled as artificial stops.

6.2.2 Collision Detection and Avoidance

Two objects are in collision if the distance between them is zero. Thus collision
detection is related to distance computation between objects. The collision detection
for the first two types of collision (SSG and MSG) will involve identifying collision
CHAPTER 6. 3-D CUTTER PATH GENERATION 67

a) Single Surface Gouging

b) Multiple Surface Gouging

Figure 6.4: TYPES OF GOUGING

between the tool and the part surface. SSG will be handled during cutter path
generation in the case of flat-end milled and peripheral-end milled regions. In the
case of three-axis milled regions we might have SSG since cutter paths were generated
from iso-curves. Since the paths for different regions were generated independently
without considering the interactions with neighboring regions, the cutter paths have
to be checked for MSG and CMS. RJL will be an issue only in the case of flat-end
milled and peripheral end-milled regions. It could be handled either at the cutter
path generation stage or at this stage. In order to avoid a computational overhead at
the cutter path generation stage, RJL is also handled at this stage. The joint limits
are modeled as artificial stops and is captured under CMS. Since there are going to
be a large number of points on the part surface along which the tool will travel, the
number of collision checks will be very large. Thus an efficient algorithm has to be
used for collision detection. The algorithm described by Quinlan [49] is adapted for
this purpose.
A hierarchical boundary representation is built for the part model, tool, machine
components and the artificial stops. The bounding representation consists of an
approximately balanced binary tree with the property that the union of all the leaf
CHAPTER 6. 3-D CUTTER PATH GENERATION 68

spheres completely contains the surface of the object.

Collision occurs when the distance between different objects is less than an
epsilon value (which is based on the desired accuracy of detection). The bounding
representation helps in narrowing down the pairs of surfaces for which distance has
to be computed. After narrowing down to the pairs of surfaces, the distance between
those surfaces have to be computed. Since a method to compute distances between
any two surfaces is not known, the surfaces will described by convex polygons and
the distance algorithms for convex objects will be used to compute the distance. One
well known convex representation of a surface is the triangulated surface.
For those points for which collision occurs, an alternate solution has to be proposed
to avoid collision. In most cases the solution might be to go for ball end mill cut. But
there are a couple of issues that makes this problem tricky. First, there will not be
one-to-one correspondence between the different types of cutter regions. Next, there
won’t be one-to-one correspondence between the polygonized surface and the actual
surface. Hence as a first step, the solution is to generate the cutter paths for all types
of cutter regions and test them for collision and drop those points at which collision
occurs. If some regions of the model are still left un-cut, the next cutter size is chosen
and the process repeated.

6.3 Summary
An algorithm has been proposed for fully automatic 3-D cutter path generation for
a compact. Based on the curvature data, the surfaces of the model were grouped
under four categories, concave, convex, saddle and developable surface patches. These
patches were subsequently grouped into three types, flat-end milled, peripheral-end
milled and three-axis milled cutter regions. Methods of cutter path generation were
described for each of those regions. This chapter also described the way to avoid cutter
interference problem that could be caused due to the interaction between different
regions of the model and those between the model and machine components. A
robotic collision detection algorithm has been modified and used for this purpose.
Before being downloaded into the CNC machine, the cutter paths would have to be
CHAPTER 6. 3-D CUTTER PATH GENERATION 69

transformed relative to the CNC machine coordinate system. Appendix A describes

these kinematic transforms. The algorithm presented in this chapter could be
enhanced by considering the problem of maintaining continuity in cutter paths across
surface patches and the three types of cutter regions.
Chapter 7

Software Issues

The CAD model undergoes a variety of geometric operations during different stages of
process planning. In order to withstand the complex geometric operations, a powerful
and robust geometric engine should serve as a backbone for the process planner. The
geometric engine should also have the capability to create new models and accept
different input formats. Some of the terms used in the context of geometric modeling
are described in the next section.

7.1 Terminology
The following definitions have been culled from various geometric modeling and solid
modeling texts [17],[27],[41],[46].
B-rep stands for Boundary representation. Here the object is represented in terms of
its surface boundaries: vertices, edges and faces. It is the widely used representation
of a solid model. Traditionally B-reps were restricted to planar, polygonal boundaries.
In the past decade, there have been many efforts to incorporate parametric surfaces
as boundaries in B-rep and these are also referred to as exact B-rep.
CSG stands for constructive solid geometry. In CSG, simple primitives are combined
by means of regularized Boolean set operators. An object is stored as a tree with
operators at the internal nodes and primitives at the nodes. Transformations such as
rotation and translation are also represented as nodes.

70
CHAPTER 7. SOFTWARE ISSUES 71

NURBS stands for nonuniform rational B-splines. These are rational B-spline curves
that are becoming the standard curve and surface descriptors in CAD. NURBS entities
are defined by a set of control points and rational blending functions.
Manifold topology. Most of the B-rep geometric modelers support only solids with
two-manifold topology. Every point on a two-manifold topology has some arbitrarily
small neighborhood around it that can be considered topologically the same (homeo-
morphic) as a disk in the plane. If there is any point on the boundary that does not
satisfy the two-manifold condition, the object is classified as non-manifold.

7.2 CAD system requirements

Traditionally, surface modeling has been the widely used representation for CNC path
planning. It is only in the past five years, solid models are being used for CNC path
generation. In systems that use solid models, the solid modeling information is used
to check collisions and the cutter paths are still generated on a surface-by-surface
basis. Thus the solid needs to be represented as an exact B-rep in such systems. In
SFF processes, linear tessellated geometry has been used to represented the solid.
This kind of representation originally evolved for applications in rendering, but has
become popular in SFF due to its ease of generation. In SDM, due to the nature of
geometric operations and its ability to handle complex shapes, a more sophisticated
geometric engine is needed. Some of the requirements of the geometric engine in SDM
are:

Availability in the form of an API API stands for Application Procedural Inter-
face, wherein the geometric engine is provided in the form of libraries consisting
of user-callable routines. The process planner for SDM is implemented using
a high level programming language such as C or C++ by calling different
geometric routines at different stages of the planner. An effective way to provide
this interface is in the form of an API library.

Ability to handle mixed-dimensional operations In SDM, the same compact is

used for a variety of tasks such as deposition path generation, 2-D cutter path
CHAPTER 7. SOFTWARE ISSUES 72

generation and 3-D cutter path generation. As part of the geometric querying
process, both the two-dimensional and the three-dimensional representations of
the solid are used. Thus the geometric engine should be able to accommodate
entities of mixed dimensionality.

Ability to handle non-manifold topology Though almost all physical artifacts

are two-manifold objects, the domain of two-manifold topology does not have
closure under set boolean operations. Thus non-manifold configurations can
occur as a result of boolean operations involving manifold objects. In the case
of SDM, non-manifold configurations could result during slicing in the compact
decomposition process. Also, SDM has the capability to produce multi-material
objects and it is very difficult to handle such objects with two-manifold topology.

Ability to handle freeform (NURBS) surfaces As opposed to standard SFF

processes, one of the main differences in geometry in SDM is its capability
to reproduce freeform surfaces. Thus, in order to make take advantage of this,
the geometric engine should be able to handle NURBS surfaces. Some of the
key challenges in handling NURBS surfaces involves providing robust surface-
surface intersection routines and providing geometric queries on those surfaces.

Graphical front-end It would be useful if the geometric engine has an user interface
that will help in creating and editing solid models. The graphical front-end
would also be helpful as a debugging tool.

Neutral formats The models for SDM can come from different sources and the
process planner should have the capability to handle these models. If the models
were created using the same geometric engine as used by the process planner,
then the process planner should be able to read in those models. But if the model
was created using a different geometric engine, then it has to be converted into a
neutral format and the geometric engine should have the ability to accept those
neutral formats. Some of the standard neutral formats for geometric models
are:
CHAPTER 7. SOFTWARE ISSUES 73

STEP STEP stands for STandard for the Exchange of Product model data and
it is an ISO standard that was developed to allow exchange of engineering
product data. In STEP, the geometric information is captured by an
application protocol called AP203. Some of commercial solid modelers
have a STEP AP203 translator module and some of the remaining ones
are developing a STEP AP203 translator.
IGES IGES stands for Initial Graphics Exchange Specification and is the
precursor to STEP. IGES permitted the exchange of product definition
data by representing geometric and topological data in a neutral format.
It was difficult to represent solid model information in an unambiguous
manner using the IGES format. Most of the commercial CAD packages
have the capability to output their results in the IGES format.
STL It is the defacto standard among the SFF systems. In this format, the
model is represented by a collection of triangular facets. In order to
represent a solid model in this format, the faces of the model have to
be tessellated. Though it is a very simple representation and could be
generated by any CAD system, it is approximate and lacks in topological
information.

In addition to the capability of reading models in these neutral formats, the

geometric engine should also be capable to output its model in these standard
neutral formats.

Geometric functionality In addition to providing the basic functions such as

boolean operations, the geometric engine should be rich in its functionality. In
the implementation of the process planner, there will often be situations where
there will be a need to know geometric properties such as surface normals,
surface curvatures, curve tangents, etc. Another useful functionality would be
the sweep functionality which was needed as part of the compact decomposition
algorithm. Though it might be possible to implement geometric property
evaluations and sweep functionality as part of the process planner, it would
be efficient if it is implemented within the geometric engine.
CHAPTER 7. SOFTWARE ISSUES 74

Robustness Last but not the least, the geometric engine should be robust. The
process planner is intended to be free of human intervention and if the underly-
ing geometric engine fails often, it would be difficult to achieve that goal. The
CAD model will undergo a variety of geometric operations within the process
planner wherein it might encounter some degenerate geometric configurations.
It would be best if the geometric engine handles such degenerate cases. If not,
it should at least be able to identify them and report them as errors. Also,
the geometric engine should be consistent in its results and should never return
incorrect results. If the calling routine is unaware of an incorrect result being
returned, it might lead to disastrous consequences.

7.3 CAD System Comparison

There weren’t many systems that met all the CAD requirements. One of requirements
that is essential for the process planner is some sort of API functionality as it would
have been infeasible to implement the process planner without API functionality. As
far as we know, there were only five systems that had API functionality. These were:

1. NOODLES : NOODLES is a geometric modeling kernel developed at the

Engineering Design Research Center of Carnegie Mellon University. NOODLES
is based on non-manifold boundary representation and is available in the form
of an API library. It is robust and handles mixed dimensional operations. One
of the greatest drawbacks with NOODLES is that it cannot handle freeform
surfaces. Thus all models created with NOODLES will have faceted geometry.
Also, being a non-commercial system there is no provision to interchange models
in neutral formats except for the STL format. NOODLES provides the basic
primitives and boolean operations among those primitives to aid in model
creation. It also permits geometric and topological queries on its geometric
entities. An interface called DISH was developed at EDRC of Carnegie Mellon
University to provide a graphical front-end for NOODLES.
CHAPTER 7. SOFTWARE ISSUES 75

2. ACIS : ACIS is a geometric modeler from Spatial Technology Inc.. ACIS is

the most popular geometric modeler available in the form of an API library.
ACIS handles freeform geometry and permits geometric queries on its entities.
Though it claims to handle non-manifold geometry, it is fundamentally a
manifold modeler with limited non-manifold functionality. It is also not truly
mixed-dimensional and it primarily deals with three-dimensional geometry with
special functions to handle two-dimensional and mixed-dimensional operations.
Though it doesn’t come with a powerful graphical interface, there are commer-
cial solid modeling packages such as AutoCAD from AutoDesk Inc. that can
be used as the graphical front-end for ACIS. ACIS doesn’t have provision to
handle models in neutral formats, but there are quite a few commercial systems
that can handle two-way translation of ACIS models into neutral formats such
as IGES, STEP and STL. ACIS is not very robust and in our experience, it was
failing or producing incorrect results in some situations. But the encouraging
fact is that ACIS is continually under upgrade and development and hopefully
in the future it will be a robust geometric modeler.

3. Pro/DEVELOP : Pro/DEVELOP is a toolkit that offers the ability to access

geometric information created with Pro/ENGINEER of Parametric Technology
Corporation. Pro/ENGINEER is one of the most popular CAD systems. It is
known to be a robust CAD system. It is a parametric, feature-based modeling
system with ability to handle freeform geometry. But, it was not a serious
candidate in our case as Pro/DEVELOP has only a small fraction of the
functionality provided by Pro/ENGINEER and also Pro/ENGINEER doesn’t
have mixed-dimensional capability and is a manifold modeling system.

4. SHAPES : SHAPES is a geometric modeling library from XOX Corporation.

SHAPES is a truly non-manifold boundary representation system and it can
handle freeform surfaces. It is dimension independent and thus can handle
mixed-dimensional operations. It is fairly robust. Some of its drawbacks are its
lack of functionality, non-availability of powerful user interface and inability to
interchange models in neutral formats. It offers only limited geometric queries
CHAPTER 7. SOFTWARE ISSUES 76

on its entities and there aren’t any commercial systems that can translate models
in neutral formats to SHAPES models.

5. Parasolid : Parasolid is a boundary-representation geometric modeler developed

by EDS Unigraphics. Parasolid is supplied as an API library and supports
freeform surfaces. It has a powerful user interface available as part of the
Unigraphics CAD system. Unigraphics also has the facility to do a two-way
translation of parasolid models into neutral formats. Parasolid offers geometric
and topological enquiries on its entities. Though it offers some support for non-
manifold operations, parasolid is not fully non-manifold. It is not dimension
independent, but it offers some support for mixed-dimensional operations.
Though its robustness has not been fully tested, the initial indications are that
it won’t be very robust due to its ambiguous handling of non-manifold and
mixed-dimensional operations.

These CAD systems were evaluated against the CAD system requirements. Figure 7.1
shows a chart indicating the performance of different CAD systems against those
requirements. In the chart, the amount of filling of a CAD system/function box
indicates the availability of that function in that CAD system.

7.4 Implementation issues

The first version of the process planner was implemented in NOODLES [58] in C
language. NOODLES was selected as the initial system as it was available in-house
and it could handle non-manifold topology [24] and it was available as an API library.
Being the first prototype of the planner, it underwent several revisions and also helped
us in refining our data structures. This planner failed in some degenerate geometric
configurations which were caused by points on the model that were very close to
each other. These problems were overcome by tweaking some of the parameters of
the modeling system. But the biggest hurdles were the lack of support for freeform
geometry and inability to handle models in neutral format. Some effort was spent to
add freeform functionality in NOODLES, but since it was turning out to be a major
CHAPTER 7. SOFTWARE ISSUES 77

NOODLES ACIS Pro SHAPES ParaSolid

DEVELOP

API

Mixed
Dimensionality

Non-manifold

Free-form
Surfaces

Graphical
front-end

Neutral
formats

Geometric
Functionality

Robustness

Figure 7.1: CAD SYSTEM COMPARISON CHART

effort, it was dropped and the next version of the process planning system for SDM
was implemented using ACIS [31] geometric modeler in C++ language. ACIS was
selected as it claimed to have non-manifold and mixed-dimensional capability and it
was available in the form of an API library and it was a very popular system. But as
the implementation of process planner in ACIS progressed, we started facing quite a
few robustness issues. Some of the ACIS functions were replaced by our own functions
and this took care some of the problems. On the positive side, ACIS comes up with
a new release every few months wherein they attempt to make it more robust. On
the downside, the new releases are not downward compatible and thus it warrants
CHAPTER 7. SOFTWARE ISSUES 78

rewriting portions of the planner. Initially, without a powerful graphical interface

model creation was very difficult in ACIS. This problem was overcome with the release
of AutoCAD version 13. Currently, the process planner is being implemented in
SHAPES and Parasolid.
Chapter 8

Applications

Several parts were built in SDM using this process planner. The parts were varied
in nature and all the aspects of the process planner were put to test. Most of the
parts were built successfully using the process planner. In the case of some parts, the
process planner had to be modified to overcome some errors. Most of these errors
were due to the underlying geometric modeling kernel. Building these parts also
helped in a better understanding of some of the finer aspects of the process which
subsequentally helped in improving the process planner. The parts that were built
using SDM could be broadly classified into three categories.

• Geometrically complex parts

• Next generation metal tooling

• Non-conventional parts

In the following sections, some example parts will be shown in each of the above
categories highlighting the process planning aspects wherever necessary. I would like
to thank my colleagues in SDM lab of CMU and RPL lab in Stanford for their effort
in building these parts.

79
CHAPTER 8. APPLICATIONS 80

8.1 Geometrically complex parts

These are parts with complex geometrical shapes that would require significant time
and effort with the conventional methods. In the conventional manufacturing meth-
ods, these parts would be almost impossible to produce without human intervention.
In SDM, with the availability of a process planner, these parts could be produced in
a fairly automated fashion.

8.1.1 IMS-T2

Figure 8.1: CAD MODEL OF IMS-T2

IMS-T2 is one of the first test parts built using the SDM process. It was one
of the test parts that was used in a world-wide assessment of rapid prototyping
technologies [5]. At the time when this part was built, the process planner was in its
early stages and was built on top of the NOODLES geometric modeling kernel [58].
The compacts were generated manually and the cutting paths were generated using
the process planner. The model shown in Figure 8.1 was constructed as a CSG tree
CHAPTER 8. APPLICATIONS 81

in NOODLES. Since NOODLES is a polygonal modeler all the freeform surfaces of

the model were approximated by facets. The support model was decomposed into 8
compacts. The compacts C1−C7 shown in Figure 8.2 were generated by doing a rigid
sweep of all the undercut surfaces of the model in the −Z direction. C8 (Figure 8.2)
was obtained by subtracting the union of previous seven compacts with the part model
from a block bigger in size than the bounding box of the model. These compacts along

C7
C6

C5

C2
C4
C3

C1

a) Compacts C1 - C7

C8

b) Wireframe rendering of compact 8

Figure 8.2: COMPACT DECOMPOSITION OF THE SUPPORT IN IMS-T2

with part model were sliced into 29 layers using horizontal planes to satisfy the process
constraints. This resulted in a total of 79 compacts. The 2-D cutter paths for rough
cutting and profiling were generated for the bottom cross-section of these compacts.
Because of the polygonal representation of the compacts, there were some tiny facets
for which 3D cutting strategies could not be generated. The presence of so many
facets resulted in large CNC files. These factors prompted us to seriously consider a
nonlinear geometric modeling kernel. After this part was completed, some effort was
CHAPTER 8. APPLICATIONS 82

spent in adding the nonlinear functionality to NOODLES. Since this seemed to be a

long-term effort, ACIS [31] was adopted as the geometric modeling kernel for the next
version of the planner. Figure 8.3 shows the stainless steel IMS-T2 part produced
with the SDM process. Copper was used as the support material and was etched out
after the part was completed. The materials were deposited using microcasting. This
part helped us to identify some of the process planning issues and also demonstrated
the usefulness of the planner.

Figure 8.3: IMS-T2 MANUFACTURED WITH SDM

8.2 Next generation metal tooling

Next generation metal tooling are dies for injection molding with a strong steel
exterior, conformable cooling channels, multi-material inserts such as copper and
INV ART M and embedded sensors. Such tools have quite a few advantages. The steel
exterior would provide a solid base for the die, cooling channels and copper inserts
would help in heat distribution and avoid forming hot spots in the tool, materials with
low coefficient of thermal expansion such as INV ART M would control distortion in
geometry and the embedded sensors such as thermocouples would help to measure
certain parameters during molding.
CHAPTER 8. APPLICATIONS 83

8.2.1 GM Injection molding Tool

The design for the tool was provided by GM as engineering drawings. The CAD model
of the mold halves were created in the test harness provided by ACIS [31]. Internal U
shaped cooling channels and models corresponding to copper inserts were also created
in the model. All the concave silhouette loops were on horizontal planes and the
model and support were sliced along these planes. Since all the compacts were 2.5D
structures, the deposition paths and 2-D cutter paths were generated corresponding
to the bottom cross-section of each compact. This part didn’t require any 3-D cutter
paths. Figure 8.4 shows the injection molding tool made with the SDM process. The

Figure 8.4: INJECTION MOLDING TOOL

part is made from 316L stainless steel. One half of the tool has four copper deposits.
The part material was deposited using the laser system and microcasting was used to
deposit the support material. Some of the small features that could not be cut with
end-mills were machined with EDM.
CHAPTER 8. APPLICATIONS 84

8.3 Non-conventional parts

The most widely recognized advantage of layered manufacturing is the relative ease of
fabricating complex geometric shapes. But a process such as SDM that builds parts by
incremental material deposition and material removal has far-reaching potential. We
could fabricate parts that are either impossible or almost impossible to manufacture
with conventional manufacturing methods. These parts are referred to as non-
conventional parts. The non-conventional parts could further be categorized as

• Parts with interacting geometric features

• Conformable, embedded electro-mechanical parts

• Assembled mechanisms

8.3.1 Parts with interacting geometric features

Figure 8.5: CAD MODEL OF TILTED FRAMES

These are parts with complex geometric interactions that makes them almost
impossible to manufacture as a single piece with conventional methods. The parts in
this category will make full use of the compact decomposition algorithm.
CHAPTER 8. APPLICATIONS 85

Tilted frames

Figure 8.5 shows the CAD model of a part that is very difficult, if not impossible
to manufacture by conventional methods. The part was designed and subsequently
built using SDM by Merz[43]. This model serves as a good test case for the compact
decomposition algorithm. Figure 8.6 shows the silhouette edges and loops for this
model.

Figure 8.6: SILHOUETTE CURVES AND LOOPS

The model is then sliced into layers with horizontal planes passing through the
lowest and the highest points of the concave silhouette edges (Figure 8.7a). Except
for layer3, the decomposed models in all other layers do not violate any of the
requirements to be satisfied by a compact. Layer3 is further decomposed as shown in
Figure 8.7b such that all the compacts satisfy the three requirements. The support
model is decomposed in a similar fashion and the compacts are sequenced for SDM
processing.
The deposition paths were generated corresponding to union of the top and bottom
cross-sections for each compact. The zigzag deposition strategy was used. 2-D cutter
paths were generated corresponding to the bottom cross-section of the compacts. For
some of these cross-sections, there were self-intersections of the offset model which
CHAPTER 8. APPLICATIONS 86

Layer4

Layer3

Layer2

Layer1 b) Further decomposition of layer3

a) Decomposition using horizontal planes

Figure 8.7: SPATIAL DECOMPOSITION OF TILTED FRAMES

were effectively handled by the planner. All the faces that had to be cut with a 3-D
cutter were identified as peripheral milled regions and the corresponding cutter paths
were generated. Figure 8.8 shows the tilted frames part produced using the SDM
process. The part was made out of stainless steel and copper was used as the support
material. Microcasting was used to deposit the materials. We faced some difficulties
with the ACIS kernel when building this part. Some of the models produced after the
compact decomposition were incorrect. This can be attributed to the non-uniform
handling of non-manifold features in ACIS. Some slight changes to the model helped
us to alleviate the problems.
CHAPTER 8. APPLICATIONS 87

Figure 8.8: TILTED FRAMES

8.3.2 Conformable, Embedded Electro-mechanical parts

One other category of parts that are made possible by the SDM process are the
embedded electronic parts [67]. These are parts in which the housing could be
composed of different materials to provide strength, lightness and toughness. Inside
the housing, electronic circuits that are pre-fabricated are embedded. The housing
can be of conformable shapes. Such parts are compact, will be rugged in harsh
environments and can made to have a very good aesthetic appeal. In the current
planner, the pre-fabricated electronic circuits are inserted manually.

VuMan

VuMan [57] is a personalized wearable computer that can store maps for navigational
aids or detailed assembly drawings for service or maintenance applications. VuMan
was built in the AutoCADT M solid modeler. The AutoCAD T M model is saved in the
ACIS format. Only the support model had to be decomposed into compacts. Both
the model and the support were decomposed into three layers using horizontal planes
to facilitate the insertion of the printed circuit boards (PCB). The model was made
out of two-component polyurethane and was deposited manually and partially cured
before machining. The bottom layer of the support and the top layer of the part
involved 3-D cutting strategies. In this part, all three types of cutter regions were
present. The conical portions were cut using the peripheral end mill strategy, some
CHAPTER 8. APPLICATIONS 88

of the cylindrical portions were cut with the flat end mill strategy and three axis mill
strategy was used for some of the blended regions.

Figure 8.9: VUMAN EMBEDDED ELECTRONIC STRUCTURE

Figure 8.9 shows the completed VuMan structure and cut-away view of VuMan
CAD model. As mentioned earlier, the part was built out of two-component
polyurethane mixture and wax was used as the support material. The PCBs were
electrically interconnected using pin receptacles. Component parts which were not
fully embedded were protected during deposition with plastic covers which were
machined away during the final machining operation.

Simon game

Figure 8.10: CAD MODEL OF SIMON GAME PIECE

CHAPTER 8. APPLICATIONS 89

Simon game is a popular 2-button hand-held game. This is another example of

embedded electronic structure built with SDM. The CAD design of Simon part was
first done in NOODLES as a CSG tree. The CSG tree primitives and operations were
then replicated in the ACIS test harness to create the ACIS model. Figure 8.10 shows
the CAD model of the simon game part. Figure 8.11 shows the simon game piece

Figure 8.11: SDM-SIMON GAME

manufactured with SDM. It is made of two component polyurethane and wax was
used as the support material. The wax was melted out at the end. Two Prefabricated
PCBs were inserted manually at an intermediate stage of the process.

8.3.3 Assembled mechanisms

SDM was also used to produce simple mechanisms. It is possible to produce fully
assembled functional mechanisms in an integrated fashion with the SDM process.
This is mainly made possible by the presence of the sacrificial support structure that
holds the moving parts of the assembly while the part is built. Once the support
structure is removed the moving parts are free to move again. Figure 8.12 shows
the photograph of a simple crank and piston mechanism made with SDM. The CAD
model was built in the ACIS test harness. All the concave silhouette loops were on
horizontal planes and the compacts were generated by slicing along these planes. The
deposition paths and 2-D cutter paths were generated corresponding to the bottom
cross-section of each compact. The part was made from stainless steel with copper
CHAPTER 8. APPLICATIONS 90

Figure 8.12: CRANK AND PISTON MECHANISM

as the support material. Stainless steel was deposited using the laser station and
microcasting was used to deposit the support material.
Chapter 9

Conclusions and Future work

9.1 Contributions
Identification of process planning issues The process planning requirements for
a novel manufacturing process, SDM were identified. The three dimensional
nature of the SDM process introduces some new challenges in process planning.
There are some differences as well as similarities between the process plan-
ning issues in SDM and the process planning issues in existing manufacturing
technologies. In conventional manufacturing processes like CNC machining,
process planning deals with selection and design of fixtures and generation of
CNC cutter paths. In SFF processes, process planning deals with slicing the
model with a set of parallel planes and generation of scan paths for the 2-D
cross-sections. In SDM process one of the main differences is that the model
has to be decomposed into 3D layers and compacts. Also, special attention
has to be paid to the generation of deposition paths in order to avoid thermal
stresses. With the absence of fixturing and tool inaccessibility issues, CNC path
generation could be viewed from a whole new angle. Thus a process plan has
been outlined to manufacture the part directly from a CAD model. This will
facilitate people from remote places to use our facility. With the tremendous
growth of internet, such a capability will be of a great value. The approach
presented here is thought to be relevant for a range of newly emerging SFF

91
CHAPTER 9. CONCLUSIONS AND FUTURE WORK 92

technologies. Also, the planning for fabrication of MEMS (Micro Electronic

Mechanical Systems ) devices is expected to benefit from the ideas of this work.

Compact decomposition An algorithm for the decomposition of any CAD model

into layers and compacts was described. This decomposition method enables
the manufacture of complex, multi-material objects with the help of SDM.
Geometric model decomposition is accomplished through a sequence of geo-
metric operations. Silhouette edges and silhouette loops are identified to help
the decomposition of models into layers and compacts. Unlike techniques used
in existing SFF methods which divide models into equally spaced slices, the
present algorithm decomposes models into layers which are not necessarily
planar and equally spaced. This has the advantage that the surface information
of the original model is preserved and utilized for further process planning
steps including CNC cutter path generation. In addition, processing methods
permitting, relatively thick layers can be fabricated at once resulting in an
increased building rate.
Another key step of this algorithm is the determination of the process sequence.
Solely based on geometric arguments a feasible sequence of material addition
and removal processes is found. This sequence is not unique and the number of
generated compacts is not necessarily minimal. The present algorithm focussed
on the creation of robust solutions.
Some of the ideas presented in this algorithm could also be used in other
areas such as parting plane determination and convex decomposition of models.
Also, the algorithm could be useful for some of the SFF processes that are
entertaining the idea of variable layer thickness. A modification of this algorithm
could be used for the determination of support structures in processes such as
Stereolithography and FDM.
In the existing manufacturing methods, the CAD model is approximated to
suit the process planning needs, and it is nearly impossible to reconstruct the
original CAD model. In the case of SFF, the CAD model is approximated by
a faceted representation and in the case of CNC machining, the CAD model is
CHAPTER 9. CONCLUSIONS AND FUTURE WORK 93

treated as a surface model. In SDM, the decomposition process doesn’t lose any
geometric information from the CAD model and thus it is possible to reconstruct
the original CAD model from the compacts. One of the main reasons for such an
accurate representation is that the same compact is used for deriving deposition
paths as well as CNC cutter paths and is also used in determining the process
sequence.

Deposition path generation Some of the factors that influence the derivation of
deposition path were identified. In SDM, the deposition paths will have a direct
influence on the quality of the final part. In particular, deposition paths for
droplet based deposition methods can influence the accumulation of residual
thermal stresses. Thus it is important to consider the geometric complexity
of the part in deriving the deposition paths. Due to the evolving nature of
the process, it is difficult to decide on a single deposition pattern for all cases.
Methods were outlined to derive spiral and zigzag deposition paths. It was also
shown that a variety of other deposition patterns could be derived from these
two types of paths. As the process matures, a more intelligent choice of these
paths will be possible.

CNC cutter path generation Methods have been outlined to generate CNC cut-
ter paths in a completely automated fashion for each compact. Though
extensive research has been done in the area of CNC cutter path generation,
success has been eluding the researchers in completely automating the process.
Most of the existing work doesn’t consider the problem in its entirety which
can be described as producing the final shape from the initial stock. Instead
methods have been outlined to solve sub-problems such as surface machining,
rough cutting, pocket milling, etc.. The reasons for a lack of automation and
the lack of solution to the entire problem as a whole could be attributed to
issues such as fixturing and the inaccessibility of tool to certain portions of
the model. Also, the presence of complex undercut features will need multiple
fixturing that makes it very difficult to automate the process. In SDM, with the
decomposition of the model into compacts, there won’t be any tool accessibility
CHAPTER 9. CONCLUSIONS AND FUTURE WORK 94

problems and due to the presence of support material, undercut features need
not be machined. Also, SDM doesn’t need any complex fixturing operation.
Thus, in this work a fully automated approach has been described for CNC
cutter path generation. It should be noted that this automation is also an
important need for SDM as human intervention with so many compacts would
cause considerable delays. Also, it will be difficult for a CNC programmer to
generate the paths as some of the original features would have been decomposed
into non-intuitive features.
The method described in this work offers a solution for the problem in its
entirety, wherein a series of CNC cutting operations are used to arrive at the
final shape of the part. A new method of decomposition, manhattan decom-
position, has been proposed for generating efficient rough cutting algorithms.
A robust algorithm has been proposed for generating the offset of 2-D profiles.
This algorithm handles all the degeneracies that could result from the offset
operation. An algorithm has been proposed for fully automatic 3-D cutter path
generation of a solid model without undercut features. The surfaces of the
model were grouped under three types of cutter regions based on the curvature
information and the methods of cutter path generation for each of these regions
were described. A robotic collision detection algorithm has been modified to
generate collision free paths. The methods described for CNC cutter path
generation are also applicable in areas outside SDM, if the model is free of
undercut features.

CAD system requirements The requirements to be met by a geometric modeling

kernel for the process planner were identified. In contrast to SFF processes,
SDM needs a more accurate representation of the model. Also, SDM’s ability
to handle multi-material components warrants the need for a non-manifold
geometric modeler. During the different stages of process planning, the 2-D
and 3-D models are used alternatively. Thus the kernel should be able to
support mixed dimensional operations. The planner was implemented under
two different geometric modeling kernels and two other geometric modeling
CHAPTER 9. CONCLUSIONS AND FUTURE WORK 95

kernels are being currently explored.

Several parts were built using this process planner. It served as a very useful
tool to automatically build several complex parts. It would have been impractical
to build these parts without the aid of an automated process planner. In addition
to corroborating the ideas presented in this work, the process planner also helped us
in giving a better understanding of some process related issues and some planning
related issues.

9.2 Future work

With an evolving process such as SDM, new functionalities needs to be added to
the process planner as we gain a better understanding of the process. In that sense,
this work could be considered as laying the ground work for a SDM process planning
system. When using the process planner, the need for additional features was felt
by its users. Some of these features have been implemented in the current system.
In the following paragraphs, suggestions are given for further improving the process
planner.

Additional constraints in Compact decomposition The algorithm for compact

decomposition presented in this work gives a solution purely based on geometric
constraints. Future work in compact decomposition can address the issues
of optimality through consideration of non geometric issues such as process
economics and material quality. Some of the compacts generated with the
current algorithm will have wedge shaped features. In order to process these
wedge shaped compacts, cutting tools of infinitely small radius are needed and
thus could be shaped only in an EDM machine. Thus, it would be useful
if the compact decomposition algorithm could avoid generating wedge shaped
compacts. One possible approach would be to sweep in the horizontal direction
V = f (X, Y ), instead of the vertical direction in such regions. Of course the
interaction of the swept volume with other compacts needs to be handled.
CHAPTER 9. CONCLUSIONS AND FUTURE WORK 96

Silhouette edges and loops could be generated in the V direction to handle

the interaction with other compacts.
Due to finite radius of the tool, sharp corners in concave portions of the part
will be rounded off by the tool. Such regions could be further decomposed
along these sharp corners to generate compacts that doesn’t have any concave
sharp corners. In this case, the edges forming the sharp corner will replace the
silhouette edges of the current algorithm.
The algorithm for compact decomposition doesn’t guarantee the minimum
number of compacts. The infinite sweep algorithm generates a near minimal
set of compacts, but it was found to be less suited to the process. In the future,
if the optimal number of compacts becomes an issue, infinite sweep algorithm
could be further explored.

Correction based process planning In some cases, due to shrinkage and warpage,
the final shape of the part produced by SDM varies in size and shape from the
actual model. Shrinkage and warpage occurs due to the accumulation of internal
residual stresses. In the case of ceramics and some thermoplastics, the part
could shrink by as much as 50 %. In these circumstances, the original model
could be modified to take care of these effects such that the part produced
by SDM is closer to the original shape. This is in some sense similar to the
modifications done to the mold in the casting process. In order to do this
correction based planning, we need to have a much better understanding of the
process characteristics and the influence of different process parameters on the
final shape. The original model could be subjected to the process condition
in a simulated environment and an FEM analysis could be done on the model
to estimate the shrinkage and residual stresses. The original model would be
modified to compensate for shrinkage and to reduce the residual stresses. The
main challenges in such an effort would be

• Effective modeling of the process conditions

• Automatic interpretation of the results of FEM analysis
CHAPTER 9. CONCLUSIONS AND FUTURE WORK 97

• Automatic modification of the original model based on the results of the

analysis

In order to effectively exchange data between the original model and the analysis
model, an intermediate representation will be needed. One such possible
representation would be the probabilistic model proposed by Yamaguchi, et.
al. [69]. The probabilistic model can represent uncertain shapes with the use of
a probability field. The probability field could be changed based on the results
of the analysis which will seamlessly modify the original model.
Selection of appropriate deposition paths could also be based on such a cor-
rection based scheme. In the case of droplet-based deposition process, the
deposition paths will have a direct influence on the residual stresses of the
part. Different deposition patterns could be characterized based on the resulting
residual stresses in the part. Then based on the geometry of the part and the
process conditions, an appropriate deposition pattern could be selected.

Enhancements to the CNC cutting algorithm The algorithm for 3-D cutting
didn’t consider the problem of maintaining continuity in cutter paths across
surface patches. If we have C 2 continuity across surface patches, continuity in
cutter paths could be maintained by considering multiple patches at the time
of decomposing the model into three types of cutter regions. To ensure that we
don’t have any un-cut material along the boundaries between different surface
patches, the boundaries could be machined with a ball-end mill.
The cusp height in 3-D cutting could be minimized by selecting the appropriate
step-over distance (distance between two successive paths). Choi et. al., [10]
have proposed a 2D constrained optimization problem to minimize the cusp
height. In their formulation, cusp height is derived as a function of cutter
orientation angles for a given step-over distance. Their formulation could be
modified such that the cusp height is a function of the step-over distance for
given cutter orientation angles. This function could then be optimized to give
the minimum cusp height.
CHAPTER 9. CONCLUSIONS AND FUTURE WORK 98

Incorporation of sacrificial walls In the case of materials with low viscosity that
have a tendency to flow after deposition, the deposited material will have to
be contained by building walls surrounding the part. Though the selection of
the material to be used for such walls is still under investigation, the process
planning effort could be directed in automating the building of such walls into
the part. Methodologies for removing these walls should also be included as
part of the process planner.
Appendix A

Kinematic Transformations

Chapters 5 and 6 described algorithms to generate CNC cutter paths for a compact.
These paths were generated relative to the coordinate system attached to CAD model.
These paths are ultimately executed in a 5-axis CNC milling machine. In SDM, two
makes of CNC milling machines have been used :

• FADAL VMC 6030 with a Tsudacoma TTNC-301 rotary/tilt table.

• MAHO MH 600 C with rotary axes.

The cutter paths are supplied to the CNC machine in the form of CNC machine code
program, a listing of motion and control commands needed to execute the desired
paths with the proper set of parameters. Before the cutter paths are expressed in
terms of the machine code, the cutter paths will have to be transformed relative to
the tool coordinate frame of the machine. This can be accomplished by modeling
the CNC machine as a robotic manipulator and then use Denavit-Hartenberg (D-
H) [22] representation to describe the relationships between different parts of the
machine. The D-H representation results in a 4X4 homogeneous transformation
matrix representing one coordinate system with respect to another coordinate system.
In the following section, these transformations are derived for the MAHO machine.
The transformations for the FADAL machine could be derived in a similar fashion.

99
APPENDIX A. KINEMATIC TRANSFORMATIONS 100

A.1 Coordinate systems

In order to derive the kinematic equations, we need to establish different coordinate
systems corresponding to the different moving parts of the CNC machine. Figure A.1
shows the placement of different coordinate systems for the MAHO CNC machine.

d2
d3 d4

YA
Z
A ZA A O ZO P ZP
ZZ
Z
XO XP XZ

B
Y
ZB
B
XB
X

Figure A.1: COORDINATE SYSTEMS

O is the base coordinate system that is fixed in space and it is located at the top of
the face plate. B is the coordinate system attached to the B-axis rotary table and d1
and d2 are the distances between the origins of O and B along the X and Z directions
of O when B is in its starting position. A is the coordinate system attached to the
A-axis rotary face plate and coincides with O in its starting position. Z is the tool
coordinate system and it attached to the tip of the tool. d3 is the distance between
O and Z along the Z direction of O when Z is in its starting position. d3 will be
equal to the sum of the thicknesses of the air-collar, pallet receiver and base pallet.
APPENDIX A. KINEMATIC TRANSFORMATIONS 101

P is the part coordinate system and it is located at the origin of the part model. d4
is a buffer height and will be equal to the distance between the top of the base pallet
and part origin.

A.2 Kinematic equations

~ ) pairs, where P (x, y, z) gives
The cutter paths are generated as a list of (P (x, y, z), V
the coordinates of the point on the part and V ~ gives the direction of a tool vector at
that point. These have to be expressed in terms of translational coordinates (X , Y, Z)
and rotational coordinates A, B of the CNC machine. These coordinates are attached
to the different coordinate systems as follows : X , Y and B motions are attached to
B, A motion is attached to A and Z motion is attached to Z. By deriving the
homogeneous transformation P TZ , relating the tool coordinate system Z to the part
coordinate system P , we could derive relations for expressing X , Y, Z, A, B in terms of
~ . In the following expressions, i Tj is a homogeneous transformation that
(x, y, z) and V
specifies the location of the jth coordinate frame with respect to the ith coordinate
frame.
 
cosB 0 sinB X + d1
 
 
 0 1 0 Y 
O
TB =



 −sinB 0 cosB d2 
 
0 0 0 1
 
cosA −sinA 0 −d1
 
 
 −sinA −cosA 0 
0
B
TA =





0 0 −1 −d2 

0 0 0 1
 
1 0 0 0
 
 
 0 1 0 0 
O
TZ =



 0

0 1 Z + d3 

0 0 0 1
APPENDIX A. KINEMATIC TRANSFORMATIONS 102

 
1 0 0 0
 
 
 0 −1 0 0 
P
TA =



 0

0 −1 −(d3 + d4 ) 

0 0 0 1

P
TZ = P
TA ∗A TZ
= P
TA ∗A TO ∗O TZ (A.1)

where A TO is the inverse of O TA which in turn is given by the product of O TB and

B
TA . Substituting the expressions for the transformation matrices in Equation A.1
we get,
 
cosAcosB −sinA −cosAsinB P
TZ (1, 4)
 
 
 sinAcosB cosA −sinAsinB P
TZ (2, 4) 
P
TZ =



 sinB 0 cosB P
TZ (3, 4) 
 
0 0 0 1

where,

P
TZ (1, 4) = YsinA + [d1 − (Z − d2 + d3 )sinB − (X + d1 )cosB]cosA (A.2)
P
TZ (2, 4) = [d1 − (Z − d2 + d3 )sinB − (X + d1 )cosB]sinA − YcosA (A.3)
P
TZ (3, 4) = −(X + d1 )sinB + (Z − d2 + d3 )cosB + d2 − d3 − d4 (A.4)

~ is oriented along the Z-axis of the tool coordinate

The given tool vector V
system. Thus it will equivalent to the third column of the transformation matrix
P
TZ . Equating the corresponding components we get,

~ [0] = −cosAsinB
V (A.5)
~ [1] = −sinAsinB
V (A.6)
~ [2] = cosB
V (A.7)
APPENDIX A. KINEMATIC TRANSFORMATIONS 103

From the equations A.5, A.6 and A.7, we can obtain the expressions for A and B
as follows:

A = arctan(−V
~ [1], −V
~ [0]) (A.8)
B = arctan(−[V
~ [0]cosA + V~ [1]sinA], −V
~ [2]) (A.9)

The tool coordinate system Z will be located at the given point P (x, y, z) of the
part. Thus the coordinates of P should be substituted to the LHS of the equations
A.2, A.3 and A.4 to obtain,

x = YsinA + [d1 − (Z − d2 + d3 )sinB − (X + d1 )cosB]cosA (A.10)

y = [d1 − (Z − d2 + d3 )sinB − (X + d1 )cosB]sinA − YcosA (A.11)
z = −(X + d1 )sinB + (Z − d2 + d3 )cosB + d2 − d3 − d4 (A.12)

From the equations A.10, A.11 and A.12, we obtain the expressions for X , Y and
Z as follows:

X = −[z − (d2 − d3 − d4 )]sinB − [xcosA + ysinA − d1 ]cosB − d1 (A.13)

Y = xsinA − ycosA (A.14)
Z = −[xcosA + ysinA − d1 ]sinB − [z − (d2 − d3 − d4 )]cosB + d2 − d3(A.15)

The equations A.8, A.9, A.13, A.14 and A.15 gives the expressions for CNC
machine coordinates A, B, X , Y, Z in terms of the cutter path pairs (P (x, y, z), V
~ ).
Bibliography

[1] L. Alting and H. Zhang. Computer aided process planning: The state of the art
survey. International Journal of Production Research, 27(4):553–585, 1989.

[2] D. C. Anderson and T. C. Chang. Geometric reasoning in feature based design

and process planning. Computer & Graphics, 14:225–235, 1990.

[3] S. Aomura and T. Uehara. Self-intersection of an offset surface. Computer Aided

Design, 22(7):417–422, September 1990.

[4] A. Appel. The notion of quantitative invisibility and the machine rendering. In
The ACM National Conference, pages 387–393. Thompson Books, 1967.

[5] R. F. Aubin. A world wide assessment of rapid prototyping technologies.

Technical Report UTRC Report 94-13, United Technologies Research Center,
East Hartford, CT, January 1994.

[6] Jack M. H. Beusmans. Computing occluding contours using spherical images.

CVGIP: Image Understanding, 53(1):97–111, 1991.

[7] H. Blum. A Transformation for Extracting New Descriptions of Shape, pages

362 – 380. M. I. T. Press, Cambridge, MA, 1967.

[8] B. Chazelle and D. P. Dobkin. Optimal convex decompositions. In Computational

Geometry, pages 63–133. North-Holland, Amsterdam, Netherlands, 1985.

[9] B. K. Choi and C. S. Jun. Ball-end cutter interference avoidance in NC machining

of sculptured surfaces. Computer Aided Design, 21(6):371–378, 1989.

104
BIBLIOGRAPHY 105

[10] B. K. Choi, J. W. Park, and C. S. Jun. Cutter-location data optimization in

5-axis surface machining. Computer Aided Design, 25(6):377–386, June 1993.

[11] Sabine Coquillart. Computing offsets of B-spline curves. Computer Aided Design,
19(6):305–309, 1987.

[12] C. R. Deckard and Joseph J. Beaman. Recent advances in selective laser

sintering. In Fourteenth conference on production research technology, pages
447–452, University of Michigan, Ann Arbor, Oct 1987.

[13] Manfredo P. DoCarmo. Differential Geometry of Curves and Surfaces. Prentice

Hall, Inc., New Jersey, 1976.

[14] G. Elber. Accessibility in 5-axis milling environment. Computer Aided Design,

26(11):797–802, November 1994.

[15] G. Elber and E. Cohen. Second-order surface analysis using hybrid symbolic and
numeric operators. ACM Transactions on Graphics, 12(2):160–178, April 1993.

[16] G. Elber and E. Cohen. Tool path generation for freeform surface models. In
Second ACM/IEEE Symposium on Solid Modeling and Applications, pages 419–
427, Montreal,Canada, May 1993.

[17] G. Farin. Curves and Surfaces for CAGD. Academic Press, New York, 1988.

[18] R.T. Farouki, T. Koenig, K.A. Tarabanis, J.U. Korein, and J.S. Batchelder.
Path planning with offset curves for layered fabrication processes. Journal of
Manufacturing Systems, 14(5):355–368, 1995.

[19] M. Faygin and B. Hsieh. Laminated Object Manufacturing (LOM): A simpler

process. In Proceedings of the Solid Freeform Fabrication Symposium, pages
123–130, University of Texas at Austin, August 1991.

[20] J.R. Fessler, R. Merz, A. H. Nickel, F. B. Prinz, and L.E. Weiss. Laser deposition
of metals for shape deposition manufacturing. In Proceedings of the Solid
Freeform Fabrication Symposium, University of Texas at Austin, August 1996.
BIBLIOGRAPHY 106

[21] H. Freeman and R. Shapira. Determining the minimum-area encasing rectangle

for an arbitrary closed curve. Communications of the ACM, 18:409–413, July
1975.

[22] K. S. Fu, R. C. Gonzalez, and C. S. G. Lee. Robotics: Control, Sensing, Vision,

and Intelligence. McGraw-Hill, 1987.

[23] H. N. Gursoy and N.M.Patrikalakis. An automatic coarse and fine surface

mesh generation scheme based on medial axis transform: Part I algorithms.
Engineering with Computers, 8:121–137, 1992.

[24] Levent Gursoz, Young Choi, and Fritz Prinz. Vertex-Based representation of
Non-Manifold Boundaries, pages 107 – 130. North - Holland, New York, 1988.

[25] K. Hartmann, R. Krishnan, R. Merz, G. Neplotnik, F. B. Prinz, L. Schultz,

M. Terk, and L.E. Weiss. Robot-assisted shape deposition manufacturing. In
Proceedings of IEEE International Conference on Robotics and Automation,
pages 2890–2895, San Diego, CA, May 1994.

[26] M. Held. On the computational geometry of pocket machining. Springer-Verlag,

Berlin, 1991.

[27] C. M. Hoffmann. Geometric and Solid Modeling, An Introduction. Morgan

Kaufmann Publishers, 1989.

[28] C. Hornung. An approach to a calculation-minimized hidden line algorithm. In

EUROGRAPHICS ’81, pages 31–42. North-Holland, 1981.

[29] J. Hur and K. Lee. Efficient algorithm for automatic support structure generation
in layered manufacturing. In Proceedings of the ASME Design Engineering Tech-
nical Conferences and Computers in Engineering Conference, Irvine, California,
August 1996.

[30] J. S. Hwang. Interference-free tool-path generation in the NC machining of para-

metric compound surfaces. Computer Aided Design, 24(12):667–676, December
1992.
BIBLIOGRAPHY 107

[31] Spatial Technology Inc. ACIS Geometric Modeler. Spatial Technology Inc.,
Boulder, CO, 1993.

[32] Stratasys Inc. Fast, precise, safe prototype with FDM. In Proceedings of the
Solid Freeform Fabrication Symposium, pages 115–122, University of Texas at
Austin, August 1991.

[33] Paul F. Jacobs. Rapid Prototyping & Manufacturing : fundamentals of stere-

olithography. Society of Manufacturing Engineers, Dearborn, MI, 1992.

[34] Erwin Kreyszig. Differential Geometry. Dover Publications, Inc., New York,
1991.

[35] R. Krishnan, A. Das, and B. Gurumoorthy. Octree encoding of B-rep based

objects. Computers & Graphics, 20(1):107–114, 1996.

[36] D. T. Lee. Medial axis transformation of a planar shape. IEEE Transactions on

Pattern Analysis and Machine Intelligence, 4:363–369, 1982.

[37] Kunwoo Lee, Tae Ju Kim, and Sung Eui Hong. Generation of toolpath with
selection of proper tools for rough cutting process. Computer Aided Design,
26(11):822–831, Nov 1994.

[38] Yuan-Shin Lee and Tien-Chien Chang. 2-phase approach to global tool inter-
ference avoidance in 5-axis machining. Computer Aided Design, 27(10):715–729,
October 1995.

[39] H. Levi. Accurate rapid prototyping by the solid ground curing technology.
In Proceedings of the Solid Freeform Fabrication Symposium, pages 110–114,
University of Texas at Austin, August 1991.

[40] Susan X. Li and Robert B. Jerard. 5-axis machining of sculptured surfaces with
a flat-end cutter. Computer Aided Design, 26(3):165–178, March 1994.

[41] M. Mantyla. An Introduction to Solid Modeling. Computer Science Press, 1988.

BIBLIOGRAPHY 108

[42] Harris L. Marcus and David L. Bourell. Solid freeform fabrication. Advanced
Materials and Processes, 144(3):28–35, September 1993.

[43] R. Merz. Shape Deposition Manufacturing. PhD thesis, Institut für Allgemeine
Elektrotechnik und Elektronik,Technische Universität Wien, May 1994.

[44] R. Merz, F. B. Prinz, K. Ramaswami, M. Terk, and L.E. Weiss. Shape deposition
manufacturing. In Proceedings of the Solid Freeform Fabrication Symposium,
pages 1–8, University of Texas at Austin, August 1994.

[45] R. Merz, F. B. Prinz, and L. E. Weiss. Planning mask cutting for thermal
spray deposition. Technical Report EDRC 24-73-91, EDRC, Carnegie Mellon
University, September 1991.

[46] M. E. Mortenson. Geometric Modeling. John Wiley and Sons, 1985.

[47] B. Pham. Offset curves and surfaces : a brief survey. Computer Aided Design,
24(4):223–229, April 1992.

[48] F. P. Preparata and M. I. Shamos. Computational geometry : an introduction.

Springer-Verlag, New York, 1985.

[49] Sean Quinlan. Efficient distance computation between non-convex objects. In

Proceedings of IEEE International Conference on Robotics and Automation,
pages 3324–3330, San Diego, CA, May 1994.

[50] K. Ramaswami and F. B. Prinz. CNC cutter path generation in shape deposition
manufacturing. In Concurrent Product and Process Engineering, pages 213–220.
American Society of Mechanical Engineers, Design Engineering Division, New
York, 1995.

[51] K. Ramaswami and F. B. Prinz. Feature free CNC cutter path generation.
In Advances in Mechanical Engineering, Volume I-Design and Manufacturing,
pages 481–491. Narosa Publishing House, India, 1996.
BIBLIOGRAPHY 109

[52] K. Ramaswami, Y. Yamaguchi, and F. B. Prinz. Spatial partitioning of solids

for solid freeform fabrication. In Submitted to the Fourth ACM Symposium on
Solid Modeling and Applications, May 1997.

[53] E. Sachs, P. Williams, D. Brancazio, M. Cima, and K. Kremmin. Three

dimensional printing: rapid tooling and prototypes directly from a CAD model.
In Proceedings of Manufacturing International ’90, pages 131–136, Atlanta, GA,
March 1990.

[54] S. E. Sarma and P. K. Wright. Algorithms for the minimization of setups and tool
changes in simply fixturable components in milling. Journal of Manufacturing
Systems, 15(2):95–112, 1996.

[55] Dino Schweitzer and Elizabeth S. Cobb. Scanline rendering of parametric surface.
Computer Graphics, 16(3):265–271, 1982.

[56] R. Sedgewick. Algorithms in C. Addison-Wesley, 1990.

[57] A. Smailagic and D. P. Siewiorek. A case study in embedded systems design :

VuMan 2 wearable computer. IEEE Design & Test of Computers, 10(4):56–67,
Sept 1993.

[58] A. Sudhalkar, R. Bhargava, R. Mattikalli, and J. M. Chen. An introduction to

the NOODLES geometric modeling system. Technical report, EDRC, Carnegie
Mellon University, Pittsburgh, CT, October 1990.

[59] Kai Tang, Charles C. Cheng, and Yakove Dayan. Offsetting surface boundaries
and 3-axis gouge-free surface machining. Computer Aided Design, 27(12):915–
927, December 1995.

[60] Wayne Tiller and Eric G. Hanson. Offsets of two-dimensional profiles. IEEE
Computer Graphics & Applications, 4:36–46, September 1984.

[61] G. T. Toussaint. Pattern recognition and geometrical complexity. In Proceedings

of the 5th International Conference on Pattern Recognition, Florida, December
1980.
BIBLIOGRAPHY 110

[62] J. H. Vanderbrande and A. A. G. Requicha. Spatial reasoning for the automatic

recognition of machining features in solid models. IEEE Transactions on Pattern
Analysis and Machine Intelligence, 15(12):1269–1285, 1993.

[63] G. W. Vickers and K. W. Quan. Ball-mills versus end-mills for curved surface
machining. Journal of Engineering for Industry (Transactions of the ASME),
111:22–26, February 1989.

[64] Rolf Walter. Visibility of surfaces via differential geometry. Computer Aided
Geometric Design, 7(1-4):353–373, 1990.

[65] H. Wang, H. Chang, and R.A. Wysk. An analytical approach to optimize NC tool
path planning for face milling flat convex polygonal surfaces. IIE Transactions,
20(3):325–332, 1988.

[66] Kevin Weiler and Peter Atherton. Hidden surface removal using polygon area
sorting. Computer Graphics, 11(2):214–222, 1977.

[67] L.E. Weiss, R. Merz, F. B. Prinz, G. Neplotnik, P. Padmanabhan, L. Schultz,

and K. Ramaswami. Layered manufacturing of heterogenous structures. Journal
of Manufacturing Systems, 1996 (submitted).

[68] Lee Weiss, Fritz Prinz, Duane Adams, and Dan Siewiorek. Thermal spray shape
deposition. Journal of Thermal Spray Technology, 1(3):231–237, September 1992.

[69] Y. Yamaguchi, H. Nakamura, and F. Kimura. Probabilistic solid modeling: A

new approach for handling uncertain shapes. In Geometric Modeling for Product
Realization, pages 95–108. Elsevier Science Publishers, 1993.

[70] Xue Yan and P. Gu. A review of rapid prototyping technologies and systems.
Computer Aided Design, 28(4):307–318, April 1996.