Title: Geometry Processing Tools for Hexahedral Meshing
Biography: Alla Sheffer is a professor of Computer Science at the University of British Columbia. She investigates algorithms for geometry processing focusing on computer graphics applications. She is particularly interested in geometric interpretation of designer intent when conveying shape. Alla regularly publishes at selective computer graphics venues such as SIGGRAPH and SIGGRAPH Asia. She holds 5 recent patents on methods for shape communication and hexahedral mesh generation. She received an IBM faculty award, Killam Research Fellowship, NSERC DAS, NSERC I2I, and the Audi Production Award. She served on the PCs for SIGGRAPH, SIGGRAPH Asia, Eurographics, and other key graphics conferences; co-chaired the PCs for SGP'06, Sketches & Posters at SIGGRAPH Asia'10, IEEE SMI'13, and IMR'2001; and will co-chair the PC for Eurographics'18. She served on the editorial boards of ACM TOG, IEEE TVCG, Computer Graphics Form, Graphical Models, Computers & Graphics, and CAGD.
Abstract: Automatic, quality hexahedral mesh generation had been considered the holy grail of finite element meshing for several decades. While hexahedral mesh elements are preferred by a variety of simulation techniques, automatic construction quality all-hex meshes of general shapes had remained elusive. My talk will present recent techniques for hexahedral mesh generation and mesh optimization that significantly improve the state of the art, enabling better quality, fully automatic hex-meshing of complex shapes. Our hexing method is centered around three key observations. First we note that given a low distortion mapping between the input model and a PolyCube (a solid formed from a union of cubes), one can hex-mesh the input model by simply transferring a regular hex grid from the PolyCube to the input model using this mapping. For a given input model our challenge therefore is to construct a suitable PolyCube and a corresponding volumetric map. Second, we note that for a given PolyCube base-complex, PolyCube geometry and mapping computation can be cast as a distortion minimizing constrained deformation problem, which can be solved using classical geometry processing techniques. Lastly, 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 Poly-Cubes, 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 distortion-minimizing deformation, followed by a labeling update and a final PolyCube parameterization step. Our approach enables fully automatic generation of high-quality hexahedral meshes for complex shapes and improves on the state of the art in hexahedral meshing.
The usability of hexahedral meshes depends on the degree to which the shape of their elements deviates from a perfect cube; a single concave, or inverted element makes a mesh unusable. While a range of methods exist for discretizing 3D objects with an initial topologically suitable hex mesh, their output meshes frequently contain poorly shaped and even inverted elements, requiring a further quality optimization step. I will describe our novel framework for optimizing hex-mesh quality capable of generating inversion-free high-quality meshes from such poor initial inputs. We recast hex quality improvement as an optimization of the shape of overlapping cones, or unions, of tetrahedra surrounding every directed edge in the hex mesh, and show the two to be equivalent. We then formulate cone shape optimization as a sequence of convex quadratic optimization problems, where hex convexity is encoded
via simple linear inequality constraints. We validate our algorithm by comparing it against previous work, and demonstrate a significant improvement in both worst and average element quality.
Title: Coming coon
Abstract: Coming soon
Title: Coming soon