Approximate Pyramidal Shape Decomposition
SIGGRAPH Asia 2014
Ruizhen Hu Honghua Li Hao Zhang Daniel Cohen-Or
Simon Fraser University Zhejiang University Tel Aviv University

Figure 1: A 3D object resembling the CCTV tower in Beijing is decomposed into three pyramidal parts, resulting in significant saving in time and material when 3D printed via layered fabrication.


A shape is pyramidal if it has a flat base with the remaining boundary forming a height function over the base. Pyramidal shapes are optimal for molding, casting, and layered 3D printing. However, many common objects are not pyramidal. We introduce an algorithm for approximate pyramidal shape decomposition. The general exact pyramidal decomposition problem is NP-hard. We turn this problem into an NP-complete problem which admits a practical solution. Specifically, we link pyramidal decomposition to the Exact Cover Problem (ECP). Given an input shape S, we develop clustering schemes to derive a set of building blocks for approximate pyramidal parts of S. The building blocks are then combined to yield a set of candidate pyramidal parts. Finally, we employ Knuth's Algorithm X over the candidate parts to obtain solutions to ECP as pyramidal shape decompositions. Our solution is equally applicable to 2D or 3D shapes, and to shapes with polygonal or smooth boundaries, with or without holes. We demonstrate our algorithm on numerous shapes and evaluate its performance.


High quality, 39.5MB      Low quality, 8.49MB




@article {Hu_siga14,
title = {Approximate Pyramidal Shape Decomposition},
author = {Ruizhen Hu and Honghua Li and Hao Zhang and Daniel Cohen-Or},
journal = {ACM Transactions on Graphics, (Proc. of SIGGRAPH Asia 2014)},
volume = {33},
number = {6},
month = nov,
year = {2014},
issn = {0730-0301},
pages = {213:1--213:12},
articleno = {213},
numpages = {12},


We first thank the anonymous reviewers for their valuable comments and suggestions. We are grateful to Joseph Mitchell for his comments on our work. Thanks also go to Hadar Elor for careful proofreading of early drafts of the paper and Ligang Liu for some initial discussions. This work is supported in part by grants from Natural Sciences and Engineering Research Council of Canada (No. 611370), China Scholarship Council, the Israeli Ministry of Science, and the Israel Science Foundation.