Multi-criteria geometric optimization problems in Layered Manufacturing

Abstract

In Layered Manufacturing, the choice of the build direction for the model influences several design criteria, including the number of layers, the volume and contact-area of the support structures, and the surface finish. These, in turn, impact the throughput and cost of the process. In this paper, efficient geometric algorithms are given to reconcile two or more of these criteria simultaneously, under three formulations of multi-criteria optimization: Finding a build direction which (i) optimizes the criteria sequentially, (ii) optimizes their weighted sum, or (iii) allows the criteria to meet designer-prescribed thresholds. While the algorithms involving "support volume" or "contact area" apply only to convex models, the solutions for "surface finish" and "number of layers" are applicable to any polyhedral model. Some of the latter algorithms have also been implemented and tested on real-world models obtained from industry. The geometric techniques used include construction and searching of certain arrangements on the unit-sphere, 3-dimensional convex hulls, Voronoi diagrams, point location, and hierarchical representations. Additionally, solutions are also provided, for the first time, for the constrained versions of two fundamental geometric problems, namely polyhedron width and largest empty disk on the unit-sphere.