A divide-and-conquer approach for automatic polycube map construction

Polycube map is a global cross-surface parameterization technique, where the polycube shape can roughly approximate the geometry of modeled objects while retaining the same topology. The large variation of shape geometry and its complex topological type in real-world applications make it difficult to effectively construct a high-quality polycube that can serve as a good global parametric domain for a given object. In practice, existing polycube map construction algorithms typically require a large amount of user interaction for either pre-constructing the polycubes with great care or interactively specifying the geometric constraints to arrive at the user-satisfied maps. Hence, it is tedious and labor intensive to construct polycube maps for surfaces of complicated geometry and topology. This paper aims to develop an effective method to construct polycube maps for surfaces with complicated topology and geometry. Using our method, users can simply specify how close the target polycube mimics a given shape in a quantitative way. Our algorithm can both construct a similar polycube of high geometric fidelity and compute a high-quality polycube map in an automatic fashion. In addition, our method is theoretically guaranteed to output a one-to-one map. To demonstrate the efficacy of our method, we apply the automatically-constructed polycube maps in a number of computer graphics applications, such as seamless texture tiling, T-spline construction, and quadrilateral mesh generation. (C) 2009 Elsevier Ltd. All rights reserved.