Dissertation
ALGORITHMS FOR PATH PLANNING IN 3D PRINTING
Washington State University
Doctor of Philosophy (PhD), Washington State University
01/2021
DOI:
https://doi.org/10.7273/000005463
Handle:
https://hdl.handle.net/2376/119324
Abstract
In my thesis we have addressed the questions on path planning in additive manufacturing(AM) by tackling problems related to geometry and tool path traversal in a graphical
setting. By using graphical models for tool path planning, we can ensure the required mechanical
properties are satisfied by imposing appropriate constraints. The overall goal is
to characterize the mathematical aspects of the AM problem and to develop efficient algorithms
with provable guarantees of performance and quality for tool path planning. We have
creatively used mathematical techniques from combinatorial and computational topology,
discrete optimization, computational complexity, graph theory, and computational geometry
for theoretical results and to design and implement efficient algorithms.
We proposed an Euler transformation that transforms a given d-dimensional cell complex
K for d = 2; 3 into a new d-complex ^K in which every vertex is part of a same even
number of edges. Hence every vertex in the graph ^G that is the 1-skeleton of ^K has an even degree, which makes ^G Eulerian, i.e., it is guaranteed to contain an Eulerian tour. Meshes
whose edges admit Eulerian tours are crucial in coverage problems arising in several applications
including 3D printing and robotics.
We developed a framework that creates a new polygonal mesh representation of the 3D
domain of a layer-by-layer 3D printing job on which I identify a single, continuous tool
paths covering each connected piece of the domain in every layer. I present a tool path
algorithm that traverses each such continuous tool path with no crossovers.
In a third line of work, I explored efficient optimization of toolpaths based on multiple
criteria for large instances of 3d printing problems. I first showed that the minimum
turn cost 3d printing problem is NP-hard, even when the region is a simple polygon. I developed
SFCDecomp, a space filling curve based decomposition framework to solve large
instances of 3d printing problems efficiently by solving these optimization subproblems
independently. For the Buddha, this framework builds toolpaths over a total of 799,716
nodes across 169 layers, and for the Bunny it builds toolpaths over 812,733 nodes across
360 layers.
Metrics
61 File views/ downloads
126 Record Views
Details
- Title
- ALGORITHMS FOR PATH PLANNING IN 3D PRINTING
- Creators
- Prashant Gupta
- Contributors
- Bala Krishnamoorthy (Advisor)Kevin R. Vixie (Committee Member)Matt Hudelson (Committee Member)
- Awarding Institution
- Washington State University
- Academic Unit
- Department of Mathematics and Statistics
- Theses and Dissertations
- Doctor of Philosophy (PhD), Washington State University
- Publisher
- Washington State University
- Number of pages
- 153
- Identifiers
- 99900592155301842
- Language
- English
- Resource Type
- Dissertation