Efficient geometric algorithms for workpiece orientation in 4- and 5-axis NC machining

• Published in: Computer aided design 1996-08, Vol.28 (8), p.577-587
• Main Authors: Gupta, Prosenjit, Janardan, Ravi, Majhi, Jayanth, Woo, Tony
• Format: Article
• Language: English
• Subjects: Applied sciences; arrangements; Artificial intelligence; computational geometry; Computer aided design; Computer science; control theory; systems; duality; Exact sciences and technology; Industrial design, planning, organization, safety; Mechanical engineering. Machine design; NC machining; Pattern recognition. Digital image processing. Computational geometry; Software; spherical polygons; topological sweep; visibility map; workpiece set-up
• ISSN: 0010-4485; 1879-2685
• DOI: 10.1016/0010-4485(95)00071-2

In 4- and 5-axis NC machines, the time to dismount, recalibrate, and remount the workpiece after each set of accessible faces of the workpiece has been machined can be considerable in comparison to the actual machining time. Unfortunately, the problem of minimizing the number of setups is NP-hard. In this paper, efficient algorithms are given for a greedy heuristic, where the goal is to find an orientation for the workpiece which maximizes the number of faces that can be machined in a single setup—using either a ball-end or a filletend cutter. The algorithms are based on geometric duality, topological sweep, interesting new properties concerning intersection and covering on the unit-sphere, and on techniques for efficiently constructing and searching an arrangement of polygons on the unit-sphere. The results imply that the optimal number of set-ups can be approximated to within a logarithmic factor. Evidence is also provided that it may not be possible to improve substantially on the proposed algorithms.