Geometric algorithms for layered manufacturing

Layered Manufacturing is a technology that allows physical prototypes of three-dimensional models to be built from their digital representation, as a stack of two-dimensional layers. One of the key problems is the choice of a suitable direction in which the model should be oriented and built, so as to minimize the number of layers, the stair-stepping effect, the volume of the support structures that are generated during the build, or the area of contact between the prototype and the support structures, or a combination of these measures. Other problems of interest include orienting the model so that one or more prescribed facets are not in contact with supports, determining a direction to fill in the individual layers, and decomposing the model into two or more submodels and building them independently so as to reduce the amount of support structures. In this survey, we give an overview of efficient geometric algorithms for these problems. The algorithms use a large variety of techniques from computational geometry, such as convex hulls, Voronoi diagrams, spherical sweep, ray-shooting, Boolean operations on polygons, and arrangements.