Compacting Voxelized Polyhedra via Tree Stacking

Yue Hao and Jyh-Ming Lien


Volume compaction is a geometric problem that aims to reduce the volume of a polyhedron via shape transform. Compactable structures are easier to transport and in some cases easier to manufacture, therefore, they are commonly found in our daily life (e.g. collapsible containers) and advanced technology industries (e.g., the recent launch of 60 Starlink satellites compacted in a single rocket by SpaceX). It is known in the literature that finding a universal solution to compact an arbitrary 3D shape is computationally challenging. Previous approaches showed that stripifying mesh surface can lead to optimal compaction, but the resulting structures were often impractical. In this paper, we propose an algorithm that cuts the 3D orthogonal polyhedron, tessellated by thick square panels, into a tree structure that can be transformed into compact piles by folding and stacking. We call this process tree stacking. Our research found that it is possible to decompose the problem into a pipeline of several solvable local optimizations. We also provide an efficient algorithm to check if the solution exists by avoiding the computational bottleneck of the pipeline. Our results show that tree stacking can efficiently generate stackable structures that have better folding accuracy and similar compactness comparing to the most compact stacking using strips.


Volume Compaction via Thick Polyhedral Surface Stacking, Yue Hao and Jyh-Ming Lien, Proceedings of Pacific Graphics 2019, Special Issue of the Eurographics journal, Computer Graphics Forum (CGF), Oct 2019
Web Site / Paper(pdf) / Poster(pdf) / BibTeX


Our previous work showed that it is possible to stack a stripified unfolding for any 3D shape efficiently. The chain-structured stacking suffers large gaps and self-intersections in the folded shape due to the imperfect control. This is because as the quad face is located further down in the link chain from the base link, it gains cumulative errors from the previous links in the forward kinematics. In order to have structures that are suitable for self-folding with imperfect motion control, we can minimize the chain components in the structure.


The folding inaccuracy of (left) chain-structured stacking and (right) tree-structured stacking of the Table-154 model with small Gaussian noises (zero means and 0.01 rad standard deviation) added to the target hinges angles.




Volume Ratio (VR) measures the total volume reduced.
Compactness Ratio (CR) measures the reduction in terms of width + length + height.


Key Result: Gaining significant folding accuracy, the proposed method only sacrifices a small amount of compactness.


Related Papers

Super Compaction and Pluripotent Shape Transformation via Algorithmic Stacking for 3D Deployable Structures, Zhonghua Xi and Yu-Ki Lee and Young-Joo Lee and Yunhyeong Kim and Huangxin Wang and Yue Hao and Young-Chang Joo and In-Suk Choi and Jyh-Ming Lien, CoRR, 2018
Paper (pdf) / BibTeX

Continuous Unfolding of Polyhedra - a Motion Planning Approach, Zhonghua Xi and Jyh-Ming Lien, 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Sep. 2015
Web Site / Paper(pdf) / BibTeX

Computer Science @ George Mason University