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).