Polycube Simplification for Coarse Layouts of Surfaces and Volumes.

Abstract: Representing digital objects with structured meshes that embed a coarse block decomposition is a relevant problem in applications like computer animation, physically-based simulation and Computer Aided Design (CAD). One of the key ingredients to produce coarse block structures is to achieve a good alignment between the mesh singularities (i.e., the corners of each block). In this paper we improve on the polycube-based meshing pipeline to produce both surface and volumetric coarse block-structured meshes of general shapes. To this aim we add a new step in the pipeline. Our goal is to optimize the positions of the polycube corners to produce as coarse as possible base complexes. We rely on re-mapping the positions of the corners on an integer grid and then using integer numerical programming to reach the optimal. To the best of our knowledge this is the first attempt to solve the singularity misalignment problem directly in polycube space. Previous methods for polycube generation did not specifically address this issue. Our corner optimization strategy is efficient and requires a negligible extra running time for the meshing pipeline. In the paper we show that our optimized polycubes produce coarser block structured surface and volumetric meshes if compared with previous approaches. They also induce higher quality hexahedral meshes and are better suited for spline fitting because they reduce the number of splines necessary to cover the domain, thus improving both the efficiency and the overall level of smoothness throughout the volume.

Authors: G. Cherchi, M. Livesu, R. Scateni.
Polycube Simplification for Coarse Layouts of Surfaces and Volumes.
Computer Graphics Forum, 35(5):11-20, (SGP 2016, Berlino, Germania).
Wiley, June 2016.

An Interactive Editor for Curve-Skeletons: SkeletonLab.

Abstract: Curve-skeletons are powerful shape descriptors able to provide higher level information on topology, structure and semantics of a given digital object. Their range of application is wide and encompasses computer animation, shape matching, modelling and remeshing. While a universally accepted definition of curve-skeleton is still lacking, there are currently many algorithms for the curve-skeleton computation (or skeletonization) as well as different techniques for building a mesh around a given curve-skeleton (inverse skeletonization). Despite their widespread use, automatically extracted skeletons usually need to be processed in order to be used in further stages of any pipeline, due to different requirements. We present here an advanced tool, named SkeletonLab, that provides simple interactive techniques to rapidly and automatically edit and repair curve skeletons generated using different techniques proposed in literature, as well as handcrafting them. The aim of the tool is to allow trained practitioners to manipulate the curve-skeletons obtained with skeletonization algorithms in order to fit their specific pipelines or to explore the requirements of newly developed techniques.

Authors: S. Barbieri, P. Meloni, F. Usai, L. D. Spano, R. Scateni.
An Interactive Editor for Curve-Skeletons: SkeletonLab.
Computers & Graphics, 60:23-33.
Elsevier, 2016.

Extraction of the Quad Layout of a Triangle Mesh Guided by its Curve-Skeleton.

Abstract: Starting from the triangle mesh of a digital shape, mainly an articulated object, we produce a coarse quad layout that can be used in character modeling and animation. Our quad layout follows the intrinsic object structure described by its curve skeleton; it contains few irregular vertices of low degree; it can be immediately refined into a semi-regular quad mesh; it provides a structured domain for UV-mapping and parametrization. Our method is fast, one-click and it does not require any parameter setting. The user can steer and refine the process through simple interactive tools during the construction of the quad layout.

F. Usai, M. Livesu, E. Puppo, M. Tarini, R. Scateni
Extraction of the Quad Layout of a Triangle Mesh Guided by its Curve-Skeleton.
ACM Transactions on Graphics, 35(1):6:1-6:13, (presented atSiggraph Asia 2015, Kobe, Giappone).
ACM, November 2015.

Curvature-based blending of closed planar curves

Abstract: A common way of blending between two planar curves is to linearly interpolate their signed curvature functions and to reconstruct the intermediate curve from the interpolated curvature values. But if both input curves are closed, this strategy can lead to open intermediate curves. We present a new algorithm for solving this problem, which finds the closed curve whose curvature is closest to the interpolated values. Our method relies on the definition of a suitable metric for measuring the distance between two planar curves and an appropriate discretization of the signed curvature functions.

M. Saba, T. Schneider, K. Hormann, R. Scateni.
Curvature-based blending of closed planar curves.
Graphical Models, 76(5):263-272 (GMP 2014, Singapore, SN).
Elsevier, September 2014.

PolyCut: Monotone Graph-Cuts for PolyCube Base-Complex Construction

Abstract: PolyCubes, or orthogonal polyhedra, are useful as parameterization base-complexes for various operations in computer graphics. However, computing quality PolyCube base-complexes for general shapes, providing a good trade-off between mapping distortion and singularity counts, remains a challenge. Our work improves on the state-of-the-art in PolyCube computation by adopting a graph-cut inspired approach. We observe that, given an arbitrary input mesh, the computation of a suitable PolyCube base-complex can be formulated as associating, or labeling, each input mesh triangle with one of six signed principal axis directions. Most of the criteria for a desirable PolyCube labeling can be satisfied using a multi-label graph-cut optimization with suitable local unary and pairwise terms. However, the highly constrained nature of PolyCubes, imposed by the need to align each chart with one of the principal axes, enforces additional global constraints that the labeling must satisfy. To enforce these constraints, we develop a constrained discrete optimization technique, PolyCut, which embeds a graph-cut multi-label optimization within a hill-climbing local search framework that looks for solutions that minimize the cut energy while satisfying the global constraints. We further optimize our generated PolyCube base-complexes through a combination of distortionminimizing deformation, followed by a labeling update and a final PolyCube parameterization step. Our PolyCut formulation captures the desired properties of a PolyCube base-complex, balancing parameterization distortion against singularity count, and produces demonstrably better PolyCube base-complexes then previous work.

Authors: M. Livesu, N. Vining, A. Sheffer, J. Gregson, R. Scateni.
PolyCut: Monotone Graph-Cuts for PolyCube Base-Complex Construction.
ACM Transactions on Graphics, 32(6):171:1-171:12 (Siggraph Asia2013, Hong Kong).
ACM, November 2013.