Computing feasible toolpaths for 5-axis machines

We present several algorithms for computing a feasible toolpath of certain characteristics for sculpting a given surface using a 5-axis numerically controlled (NC) machine. A toolpath specifies the orientations of a cutting tool at each point of a path taken by the tool. When a single toolpath does not exist, we find the minimum number of toolpaths needed by the cutting tool. Previous algorithms are all heuristics with no quality guarantee of a solution and with no analysis of the running time. We obtain optimal solutions and provide time analysis for all our algorithms. We model the problem using a directed, layered graph G (representing the sculpting constraints) such that a feasible toolpath corresponds to a certain path in G. We give efficient methods for several path problems in such graphs (e. g. , finding a path in an unweighted or vertex-weighted version of G, computing the minimum number of paths whose union spans all the layers of an edge-weighted G, etc).

Authors

• Danny Z. Chen University of Notre Dame
• Ewa Misiołek

Keywords

• Shortest paths
• Computer-aided manufacturing
• Range minimum query
• Sweeping