Polycube Shape Space. (14th November 2019)

• Record Type: Journal Article
• Authors: Zhao, Hui; Li, Xuan; Wang, Wencheng; Wang, Xiaoling; Wang, Shaodong; Lei, Na; Gu, Xiangfeng
• Is Part Of: Computer graphics forum. Volume 38:Number 7(2019)
• Page Start: 311
• Page End: 322
• Publication Date: 2019-11-14
• Subjects: CCS Concepts -- Mathematics of computing → Graphs and surfaces -- Computing methodologies → Mesh models -- Mesh geometry models; Computer graphics -- Periodicals; 006.605
• DOI: 10.1111/cgf.13839
• Languages: English
• ISSNs: 0167-7055

Abstract

Abstract: There are many methods proposed for generating polycube polyhedrons, but it lacks the study about the possibility of generating polycube polyhedrons. In this paper, we prove a theorem for characterizing the necessary condition for the skeleton graph of a polycube polyhedron, by which Steinitz's theorem for convex polyhedra and Eppstein's theorem for simple orthogonal polyhedra are generalized to polycube polyhedra of any genus and with non‐simply connected faces. Based on our theorem, we present a faster linear algorithm to determine the dimensions of the polycube shape space for a valid graph, for all its possible polycube polyhedrons. We also propose a quadratic optimization method to generate embedding polycube polyhedrons with interactive assistance. Finally, we provide a graph‐based framework for polycube mesh generation, quadrangulation, and all‐hex meshing to demonstrate the utility and applicability of our approach.