University of Houston

In a variety of computer graphics and engineering applications, such as physically-based deformation or free-form deformation, volumetric representations are often required. Among many different types of volumetric mesh representations, structured representations, e.g., hexahedral meshes, are often preferred over unstructured representations, e.g., tetrahedral meshes. A hexahedral mesh maintaining certain quality usually has a certain amount of well-placed singularities that are distributed on the boundary or inside the volume. Tracing from the singularities of a hex-mesh, one can extract the coarsest version of it, which is referred to as the base-complex – an all-cuboid structure. A hex-mesh with less cuboids in its base-complex is more suitable for PDE solving, tensor-product/trivariate spline fitting, Isogeometric Analysis (IGA), and multi-grid and adaptive computations. However, coarser structure may lead to hexahedral elements with large distortion, which in turn reduces the accuracy and convergence rate of the subsequent computations. In general, to produce hex-meshes with coarse structure while maintain high geometric quality remains an open and challenging problem. This dissertation aims to explore a first and effective solution to this problem from two aspects: 1) the generation of a hex-mesh with a coarse and controllable base-complex structure from any given input; and 2) the simplification and optimization of the base-complex of a given initial valid all-hex mesh.

To achieve the first goal, a new volumetric decomposition technique is introduced for the generation of a simple and predictable structured hex-mesh. In addition, the orientation of the structure can be controlled by the user. Specifically, given an input polygonal surface model, the proposed pipeline employs a generalized sweeping strategy to decompose the volume enclosed by it into a sequence of 2-manifold level sets based on a user-specified 3D harmonic function. The structures of the 2D level sets are then extracted, and the final 3D partitioning strategy is constructed via matching the 2D structure over the adjacent level sets. A valid all-hex mesh can then be generated from the partitioning strategy. This pipeline has been applied to a variety of 3D objects to demonstrate its utility.

To simply the base-complex of an input hex-mesh, a first and complete framework is developed to reduce the number of hexahedral components (i.e., cuboids) in the base-complex by removing the misalignments among singularities. In particular, given an initial semi-structured hex-mesh as the input, its singularity structure and the corresponding base-complex are extracted first. Second, the misalignment candidates in the obtained base-complex are identified and removed procedurally. To reduce the distortion in the resulting base-complex after fixing the misalignments, a structure-aware reparameterization is performed to optimize the placement of singularities. This framework has been shown very effective in reducing the numbers of cuboids in a large number of hex-meshes generated with a variety of state-of-the-art methods, while maintaining a high local element quality.

After fixing misalignments in the base-complex, to further reduce the complexity of the hex-mesh structure, the proposed dissertation will investigate a solution to cancel pairs or groups of singularities. The ultimate goal is to generate a hex-mesh with reasonably good quality from an initial hex-mesh that can be easily obtained from a tetrahedral or hybrid mesh. This will greatly simplify the hex-mesh generation, making hex-meshes more accessible to various applications. To support the development of valid and effective cancellation operations, a novel visualization system will be first developed to help understand the relations among singularities in hex-meshes.