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



R Janardan, I Ilinkin, J Schwerdt, Miles E. Smid, J J. Majhi, 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 CAD models using a relatively small and inexpensive 3D printer attached to a personal computer. LM provides the designer with an additional level of physical verification that makes it possible to detect and correct design flaws that may have, otherwise, gone unnoticed in the virtual model. 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 and also lends itself naturally to applications where the model needs to be built as several pieces, such as in the manufacture of mold halves for injection molding. Furthermore, this approach is very efficient in its use of so-called support structures that are generated by the LM process. This paper presents the 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. Experimental results are given for randomly generated convex polyhedra with up to 200,000 vertices. These algorithms are then generalized to non-convex 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.
Proceedings Title
Proceedings of ACM Symposium on Computational Geometry
Conference Location


3D, CAD model, layered manufacturing, rapid prototyping


Janardan, R. , Ilinkin, I. , Schwerdt, J. , Smid, M. , Majhi, J. and Sriram, R. (2001), A Decomposition-Based Approach to Layered Manufacturing, Proceedings of ACM Symposium on Computational Geometry, , USA (Accessed May 17, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created December 31, 2000, Updated October 12, 2021