Compacting Voxelized Polyhedra via Tree Stacking

dc.contributor.authorHao, Yue
dc.contributor.authorLien, Jyh-Ming
dc.contributor.editorLee, Jehee and Theobalt, Christian and Wetzstein, Gordonen_US
dc.description.abstractVolume 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.en_US
dc.description.sectionheadersVoxels and Polycubes
dc.description.seriesinformationComputer Graphics Forum
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectGeneral and reference
dc.subjectComputing methodologies
dc.subjectMesh geometry models
dc.subjectVolumetric models
dc.titleCompacting Voxelized Polyhedra via Tree Stackingen_US