Robust Edge-Preserved Surface Mesh Polycube Deformation

Hui Zhao, Na Lei, Xuan Li, Peng Zeng, Ke Xu, Xianfeng Gu

Abstract

Polycube construction is a fundamental problem in computer graphics, essential for applications like hexahedral remeshing and texture mapping. We present a robust and automatic algorithm that deforms surface meshes of arbitrary topology into polycube shapes. By utilizing an iterative Poisson system based on face normal rotations, our method achieves edge preservation and handles meshes with boundaries or non-orientable surfaces. Experimental results demonstrate that our approach outperforms existing state-of-the-art methods in speed, robustness, and efficiency.

Introduction

A polycube is a 3D representation where every face is aligned with the standard Cartesian axes (X, Y, or Z). These structures serve as ideal domains for volumetric parameterization and hexahedral mesh generation. However, automatically generating polycubes from complex organic or high-genus meshes remains a significant challenge due to topological degeneracies and the high computational cost of non-linear optimization. This paper introduces a method that is simple to implement, fast, and robust enough to handle nearly any input mesh.

Methodology

Our approach decomposes the polycube construction process into three distinct stages: segmentation, topological assignment, and geometric deformation.

Segmentation and Topology

The initial stage involves partitioning the input mesh into several "charts." Each chart is then assigned to one of the six primary axis directions (±X, ±Y, ±Z). This explicit separation allows the algorithm to avoid the local minima traps that often plague joint optimization frameworks.

Figure 1: Initial segmentation of the Stanford Bunny into axis-aligned charts.

Iterative Poisson Deformation

The core contribution is a face normal rotation-based deformation. Instead of solving a complex, non-linear energy minimization problem, we utilize an iterative Poisson system. By treating the target rotations as known constants derived from the topological assignment, we transform the problem into a sequence of simple linear equations ($Lx = b$). By recomputing rotation matrices at each step and solving the linear system again, the mesh gradually "snaps" into a polycube shape. This approach is not only computationally efficient but also naturally preserves the local metric (edge lengths and areas) of the original mesh better than vertex-based alternatives.

Results and Discussion

We evaluated our algorithm on hundreds of models of varying complexity, including standard datasets like the Stanford 3D Scanning Repository and the Aim@Shape collection.

Robustness and Speed

The algorithm demonstrates exceptional robustness, successfully processing models with high genus (multiple holes), open boundaries, and complex branching. Because the core computation involves solving linear systems, our method is significantly faster than previous non-linear optimization techniques. In many cases, the polycube shape is virtually finalized within the first few iterations.

Figure 6: The final polycube deformation of the Stanford Bunny, showing sharp edge preservation and axis alignment.

Versatility

A key advantage of our face-based rotation method is its ability to handle non-orientable surfaces (such as the Costa surface) and meshes with holes—cases where vertex-based methods often fail. Quantitative analysis shows that our method maintains lower edge and area distortion compared to previous state-of-the-art techniques.

Conclusion and Future Work

We have presented a simple yet powerful algorithm for automatic polycube deformation. By leveraging an iterative Poisson framework, we achieve a robust solution that preserves the geometric characteristics of the input mesh while ensuring strict axis alignment. While the current method does not strictly guarantee a bijective (one-to-one) mapping, future work will focus on incorporating additional constraints to prevent self-intersections in extreme deformation cases.

Summary updated

Abstract

The problem of polycube construction or deformation is an essential problem in computer graphics. In this paper, we present a robust, simple, efficient and automatic algorithm to deform the meshes of arbitrary shapes into their polycube ones. We derive a clear relationship between a mesh and its corresponding polycube shape. Our algorithm is edge-preserved, and works on surface meshes with or without boundaries. Our algorithm outperforms previous ones in speed, robustness, efficiency. Our method is simple to implement. To demonstrate the robustness and effectiveness of our method, we apply it to hundreds of models of varying complexity and topology. We demonstrat that our method compares favorably to other state-of-the-art polycube deformation methods.
BibTeX
@inproceedings{zhao2017robust,
  author = {Hui Zhao and Na Lei and Xuan Li and Peng Zeng and Ke Xu and Xianfeng Gu},
  title = {{Robust Edge-Preserved Surface Mesh Polycube Deformation}},
  booktitle = {PG (Short Papers)},
  year = {2017},
  url = {https://openreview.net/forum?id=l4JuWWXeVLy},
}
Figure