Voronoi Diagrams, Offsetting and Tool Path Generation

Tool path generation for pocket machining is a rich source of important practical algorithmic problems in geometry. In prior work we gave algorithmic studies of several problems associated with optimizing the motion of a tool. We have also developed the leading practical algorithm for computing offsets of polygonal pockets, based on our robust and efficient Voronoi diagram code `VRONI`. We propose to deepen the link between Voronoi diagrams and machining by developing and applying Voronoi- based methods to high-speed machining (HSM) of pockets. High-speed machining attempts to exploit the improved quality of both tools and controls to enable high-speed cutter movements; recent work carried out at Boeing demonstrated the tremendous advantage that HSM promises for companies. We propose to provide a thorough algorithmic foundation for HSM based on tools and concepts of computational geometry. We will use our expertise in geometric decomposition problems to study how a general pocket can be partitioned into `nice` shapes that are suited for HSM using smooth spiral tool paths. Both the decomposition and the tool paths will be generated by means of Voronoi diagrams and other algorithmic or combinatorial methods of discrete geometry (rather than by solving PDEs as done at Boeing). In order to keep our algorithms general enough to be widely applicable, we will abstract machine dynamics and material properties by casting them into mathematical models. Besides working on a thorough mathematical and algorithmic foundation for HSM we will place our emphasis on converting our algorithms into actual software, in order to jump-start future work by providing colleagues and companies with ready-to-use libraries. To achieve this goal we propose to extend the functionality of our Voronoi code, VRONI, significantly by designing and implementing algorithms for dynamically maintaining a Voronoi diagram under the insertion and deletion of point sites, straight-line segments and circular arcs. This major extension of VRONI will be accompanied by the development of software for several other tools that will be used for HSM tool path generation. These tools will be implemented as small modules of their own and, thus, will be generally applicable. Hence, while focusing on HSM as the key application that will drive this oriented basic research, several of the tools that we propose to develop will be applicable to diverse technical fields, including, but not limited to, CAD/CAM and GIS, thereby broadening the practical impact of the work proposed.

Tool path generation for pocket machining is a rich source of important practical algorithmic problems in computational geometry. Computational geometry is a field of (theoretical) computer science which is concerned with the efficient solution of problems that bear a geometric flavor. One of the key data structures of computational geometry is the so-called Voronoi diagram; its use provides the algorihmic basis for efficient solutions to a variety of geometric problems. In this project we deepened the link between Voronoi diagrams and machining by developing and applying Voronoi-based methods to high-speed machining (HSM) of pockets. High-speed machining attempts to exploit the improved quality of both tools and controls to enable high-speed cutter movements; recent work carried out at Boeing demonstrated the tremendous advantage that HSM promises for companies. Based on tools and concepts of computational geometry we provided a thorough algorithmic foundation for HSM. In particular, we used our expertise in geometric decomposition problems to study how a general pocket can be partitioned into "nice" shapes that are suited for HSM using smooth spiral tool paths. Both the decomposition and the actual generation of the HSM tool paths was generated by means of Voronoi diagrams and other algorithmic or combinatorial methods of discrete geometry: We plant an impulse on the Voronoi diagram and grow disks centered on the Voronoi diagram in order to obtain a spiral curve. This curve is subjected to a smoothing operation which converts it into smooth spiral tool path that is suitable for HSM machining. For the computation of Voronoi diagrams we extended the functionality of our Voronoi code, VRONI, significantly by designing and implementing an algorithm for handling circular arcs without approximation by straight-line segments. This extension, named "ArcVRONI", makes VRONI the first and only (known) code world-wide which can compute the Voronoi diagram of a set of points, line segments and circular arcs. In addition to HSM machining as the focal point of this project we used our expertise on Voronoi diagrams also for solving other related problems. For instance, we developed an efficient algorithm (and cast it into a code) that allows to approximate polygonal curves by smooth curves consisting of circular arcs. Of course, this module is used for our own work on HSM tool paths, but it is also of theoretical and practical interest outside of the scope of this project. All algorithms designed in the course of this project were implemented and tested carefully on contrived and real-world data. In the meantime, the University of Salzburg has started to license the resulting software modules to companies for commercial use. Hence, the practical impact and technology transfer achieved by this project can certainly be regarded as a success story.