Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

A Decomposition-Based Approach to Layered Manufacturing



I Llinkin, R Janardan, J J. Majhi, J Schwerdt, Miles E. Smid, Ram D. Sriram


This paper introduces a new approach for improving the performance and versatility of Layered Manufacturing (LM), which is an emerging technology that makes it possible to build physical prototypes of 3D parts directly from their computer models using a ?3D printer? attached to a personal computer. Current LM processes work by viewing the computer model as a single, monolithic unit. By contrast, the approach proposed here decomposes the model into a small number of pieces, by intersecting it with a suitably chosen plane, builds each piece separately using LM, and then glues the pieces together to obtain the physical prototype. This approach allows large models to be built quickly in parallel. Furthermore, it is very efficient in its use of so-called support structures that are generated by the LM process. This paper presents the first provably correct and efficient geometric algorithms to decompose polyhedral models so that the support requirements (support volume and area of contact) are minimized. Algorithms based on the plane-sweep paradigm are first given for convex polyhedra. These algorithms run in O(n log n) time for n-vertex convex polyhedra and work by generating expressions for the support volume and contact-area as a function of the height of the sweep plane, and optimizing them during the sweep. These algorithms are then generalized to nonconvex polyhedra, which are considerably more difficult due to the complex structure of the supports. It is shown that, surprisingly, non-convex polyhedra can be handled by first identifying certain critical facets using a technique called cylindrical decomposition, and then applying the algorithm for convex polyhedra to these critical facets. The resulting algorithms run in O(n2 log n) time. Also given is a method for controlling the size of the decomposition, so that the number of pieces generated is within a user-specified limit. Experimental results show that the proposed approach can achieve significant reduction in support requirements in both the convex and the non-convex case.
Journal of Computation Geometry: Theory and Applications


Computational geometry, Cylindrical decomposition, Layered manufacturing, Optimization, Plane sweep, Rapid prototyping


Llinkin, I. , Janardan, R. , Majhi, J. , Schwerdt, J. , Smid, M. and Sriram, R. (2002), A Decomposition-Based Approach to Layered Manufacturing, Journal of Computation Geometry: Theory and Applications, [online], (Accessed May 31, 2023)
Created May 31, 2002, Updated October 12, 2021