Surface Smoothing and Quality Improvement of Quadrilateral/Hexahedral Meshes with Geometric Flow

Manifold-Constrained Geometric Optimization via Local Parameterizations

Many geometric optimization problems contain manifold constraints that restrict the optimized vertices on some specified manifold surface. The constraints are highly nonlinear and non-convex, therefore existing methods usually suffer from a breach of condition or low optimization quality. In this article, we present a novel divide-and-conquer methodology for manifold-constrained geometric optimization problems. Central to our methodology is to use local parameterizations to decouple the optimization with hard constraints, which transforms nonlinear constraints into linear constraints. We decompose the input mesh into a set of developable or nearly-developable overlapping patches with disc topology, then flatten each patch into the planar domain with very low isometric distortion, optimize vertices with linear constraints and recover the patch. Finally, we project it onto the constrained manifold surface. We demonstrate the applicability and robustness of our methodology through a variety of geometric optimization tasks. Experimental results show that our method performs much better than existing methods.

Digital Surface Regularization With Guarantees

Voxel based modeling is a very attractive way to represent complex multi-material objects. Beside artistic choices of pixel/voxel arts, representing objects as voxels allows efficient and dynamic interactions with the scene. For geometry processing purposes, many applications in material sciences, medical imaging or numerical simulation rely on a regular partitioning of the space with labeled voxels. In this article, we consider a variational approach to reconstruct interfaces in multi-labeled digital images. This approach efficiently produces piecewise smooth quadrangulated surfaces with some theoretical stability guarantee. Non-manifold parts at intersecting interfaces are handled naturally by our model. We illustrate the strength of our tool for digital surface regularization, as well as voxel art regularization by transferring colorimetric information to regularized quads and computing isotropic geodesic on digital surfaces.

3D mesh processing using GAMer 2 to enable reaction-diffusion simulations in realistic cellular geometries

Recent advances in electron microscopy have enabled the imaging of single cells in 3D at nanometer length scale resolutions. An uncharted frontier for in silico biology is the ability to simulate cellular processes using these observed geometries. Enabling such simulations requires watertight meshing of electron micrograph images into 3D volume meshes, which can then form the basis of computer simulations of such processes using numerical techniques such as the finite element method. In this paper, we describe the use of our recently rewritten mesh processing software, GAMer 2, to bridge the gap between poorly conditioned meshes generated from segmented micrographs and boundary marked tetrahedral meshes which are compatible with simulation. We demonstrate the application of a workflow using GAMer 2 to a series of electron micrographs of neuronal dendrite morphology explored at three different length scales and show that the resulting meshes are suitable for finite element simulations. This work is an important step towards making physical simulations of biological processes in realistic geometries routine. Innovations in algorithms to reconstruct and simulate cellular length scale phenomena based on emerging structural data will enable realistic physical models and advance discovery at the interface of geometry and cellular processes. We posit that a new frontier at the intersection of computational technologies and single cell biology is now open.

An Application of Manifold Learning in Global Shape Descriptors

With the rapid expansion of applied 3D computational vision, shape descriptors have become increasingly important for a wide variety of applications and objects from molecules to planets. Appropriate shape descriptors are critical for accurate (and efficient) shape retrieval and 3D model classification. Several spectral-based shape descriptors have been introduced by solving various physical equations over a 3D surface model. In this paper, for the first time, we incorporate a specific manifold learning technique, introduced in statistics and machine learning, to develop a global, spectral-based shape descriptor in the computer graphics domain. The proposed descriptor utilizes the Laplacian Eigenmap technique in which the Laplacian eigenvalue problem is discretized using an exponential weighting scheme. As a result, our descriptor eliminates the limitations tied to the existing spectral descriptors, namely dependency on triangular mesh representation and high intra-class quality of 3D models. We also present a straightforward normalization method to obtain a scale-invariant and noise-resistant descriptor. The extensive experiments performed in this study using two standard 3D shape benchmarks—high-resolution TOSCA and McGill datasets—demonstrate that the present contribution provides a highly discriminative and robust shape descriptor under the presence of a high level of noise, random scale variations, and low sampling rate, in addition to the known isometric-invariance property of the Laplace–Beltrami operator. The proposed method significantly outperforms state-of-the-art spectral descriptors in shape retrieval and classification. The proposed descriptor is limited to closed manifolds due to its inherited inability to accurately handle manifolds with boundaries.

VolRoverN: enhancing surface and volumetric reconstruction for realistic dynamical simulation of cellular and subcellular function

Establishing meaningful relationships between cellular structure and function requires accurate morphological reconstructions. In particular, there is an unmet need for high quality surface reconstructions to model subcellular and synaptic interactions among neurons and glia at nanometer resolution. We address this need with VolRoverN, a software package that produces accurate, efficient, and automated 3D surface reconstructions from stacked 2D contour tracings. While many techniques and tools have been developed in the past for 3D visualization of cellular structure, the reconstructions from VolRoverN meet specific quality criteria that are important for dynamical simulations. These criteria include manifoldness, water-tightness, lack of self- and object-object-intersections, and geometric accuracy. These enhanced surface reconstructions are readily extensible to any cell type and are used here on spiny dendrites with complex morphology and axons from mature rat hippocampal area CA1. Both spatially realistic surface reconstructions and reduced skeletonizations are produced and formatted by VolRoverN for easy input into analysis software packages for neurophysiological simulations at multiple spatial and temporal scales ranging from ion electro-diffusion to electrical cable models.

Multiscale geometric modeling of macromolecules I: Cartesian representation

This paper focuses on the geometric modeling and computational algorithm development of biomolecular structures from two data sources: Protein Data Bank (PDB) and Electron Microscopy Data Bank (EMDB) in the Eulerian (or Cartesian) representation. Molecular surface (MS) contains non-smooth geometric singularities, such as cusps, tips and self-intersecting facets, which often lead to computational instabilities in molecular simulations, and violate the physical principle of surface free energy minimization. Variational multiscale surface definitions are proposed based on geometric flows and solvation analysis of biomolecular systems. Our approach leads to geometric and potential driven Laplace-Beltrami flows for biomolecular surface evolution and formation. The resulting surfaces are free of geometric singularities and minimize the total free energy of the biomolecular system. High order partial differential equation (PDE)-based nonlinear filters are employed for EMDB data processing. We show the efficacy of this approach in feature-preserving noise reduction. After the construction of protein multiresolution surfaces, we explore the analysis and characterization of surface morphology by using a variety of curvature definitions. Apart from the classical Gaussian curvature and mean curvature, maximum curvature, minimum curvature, shape index, and curvedness are also applied to macromolecular surface analysis for the first time. Our curvature analysis is uniquely coupled to the analysis of electrostatic surface potential, which is a by-product of our variational multiscale solvation models. As an expository investigation, we particularly emphasize the numerical algorithms and computational protocols for practical applications of the above multiscale geometric models. Such information may otherwise be scattered over the vast literature on this topic. Based on the curvature and electrostatic analysis from our multiresolution surfaces, we introduce a new concept, the polarized curvature, for the prediction of protein binding sites.

Multiscale Multiphysics and Multidomain Models I: Basic Theory

This work extends our earlier two-domain formulation of a differential geometry based multiscale paradigm into a multidomain theory, which endows us the ability to simultaneously accommodate multiphysical descriptions of aqueous chemical, physical and biological systems, such as fuel cells, solar cells, nanofluidics, ion channels, viruses, RNA polymerases, molecular motors and large macromolecular complexes. The essential idea is to make use of the differential geometry theory of surfaces as a natural means to geometrically separate the macroscopic domain of solvent from the microscopic domain of solute, and dynamically couple continuum and discrete descriptions. Our main strategy is to construct energy functionals to put on an equal footing of multiphysics, including polar (i.e., electrostatic) solvation, nonpolar solvation, chemical potential, quantum mechanics, fluid mechanics, molecular mechanics, coarse grained dynamics and elastic dynamics. The variational principle is applied to the energy functionals to derive desirable governing equations, such as multidomain Laplace-Beltrami (LB) equations for macromolecular morphologies, multidomain Poisson-Boltzmann (PB) equation or Poisson equation for electrostatic potential, generalized Nernst-Planck (NP) equations for the dynamics of charged solvent species, generalized Navier-Stokes (NS) equation for fluid dynamics, generalized Newton's equations for molecular dynamics (MD) or coarse-grained dynamics and equation of motion for elastic dynamics. Unlike the classical PB equation, our PB equation is an integral-differential equation due to solvent-solute interactions. To illustrate the proposed formalism, we have explicitly constructed three models, a multidomain solvation model, a multidomain charge transport model and a multidomain chemo-electro-fluid-MD-elastic model. Each solute domain is equipped with distinct surface tension, pressure, dielectric function, and charge density distribution. In addition to long-range Coulombic interactions, various non-electrostatic solvent-solute interactions are considered in the present modeling. We demonstrate the consistency between the non-equilibrium charge transport model and the equilibrium solvation model by showing the systematical reduction of the former to the latter at equilibrium. This paper also offers a brief review of the field.

New software developments for quality mesh generation and optimization from biomedical imaging data

In this paper we present a new software toolkit for generating and optimizing surface and volumetric meshes from three-dimensional (3D) biomedical imaging data, targeted at image-based finite element analysis of some biomedical activities in a single material domain. Our toolkit includes a series of geometric processing algorithms including surface re-meshing and quality-guaranteed tetrahedral mesh generation and optimization. All methods described have been encapsulated into a user-friendly graphical interface for easy manipulation and informative visualization of biomedical images and mesh models. Numerous examples are presented to demonstrate the effectiveness and efficiency of the described methods and toolkit.

A three-dimensional finite element model of human atrial anatomy: new methods for cubic Hermite meshes with extraordinary vertices

High-order cubic Hermite finite elements have been valuable in modeling cardiac geometry, fiber orientations, biomechanics, and electrophysiology, but their use in solving three-dimensional problems has been limited to ventricular models with simple topologies. Here, we utilized a subdivision surface scheme and derived a generalization of the "local-to-global" derivative mapping scheme of cubic Hermite finite elements to construct bicubic and tricubic Hermite models of the human atria with extraordinary vertices from computed tomography images of a patient with atrial fibrillation. To an accuracy of 0.6 mm, we were able to capture the left atrial geometry with only 142 bicubic Hermite finite elements, and the right atrial geometry with only 90. The left and right atrial bicubic Hermite meshes were G1 continuous everywhere except in the one-neighborhood of extraordinary vertices, where the mean dot products of normals at adjacent elements were 0.928 and 0.925. We also constructed two biatrial tricubic Hermite models and defined fiber orientation fields in agreement with diagrammatic data from the literature using only 42 angle parameters. The meshes all have good quality metrics, uniform element sizes, and elements with aspect ratios near unity, and are shared with the public. These new methods will allow for more compact and efficient patient-specific models of human atrial and whole heart physiology.

High-order fractional partial differential equation transform for molecular surface construction

Fractional derivative or fractional calculus plays a significant role in theoretical modeling of scientific and engineering problems. However, only relatively low order fractional derivatives are used at present. In general, it is not obvious what role a high fractional derivative can play and how to make use of arbitrarily high-order fractional derivatives. This work introduces arbitrarily high-order fractional partial differential equations (PDEs) to describe fractional hyperdiffusions. The fractional PDEs are constructed via fractional variational principle. A fast fractional Fourier transform (FFFT) is proposed to numerically integrate the high-order fractional PDEs so as to avoid stringent stability constraints in solving high-order evolution PDEs. The proposed high-order fractional PDEs are applied to the surface generation of proteins. We first validate the proposed method with a variety of test examples in two and three-dimensional settings. The impact of high-order fractional derivatives to surface analysis is examined. We also construct fractional PDE transform based on arbitrarily high-order fractional PDEs. We demonstrate that the use of arbitrarily high-order derivatives gives rise to time-frequency localization, the control of the spectral distribution, and the regulation of the spatial resolution in the fractional PDE transform. Consequently, the fractional PDE transform enables the mode decomposition of images, signals, and surfaces. The effect of the propagation time on the quality of resulting molecular surfaces is also studied. Computational efficiency of the present surface generation method is compared with the MSMS approach in Cartesian representation. We further validate the present method by examining some benchmark indicators of macromolecular surfaces, i.e., surface area, surface enclosed volume, surface electrostatic potential and solvation free energy. Extensive numerical experiments and comparison with an established surface model indicate that the proposed high-order fractional PDEs are robust, stable and efficient for biomolecular surface generation.

High-order fractional partial differential equation transform for molecular surface construction

Fractional derivative or fractional calculus plays a significant role in theoretical modeling of scientific and engineering problems. However, only relatively low order fractional derivatives are used at present. In general, it is not obvious what role a high fractional derivative can play and how to make use of arbitrarily high-order fractional derivatives. This work introduces arbitrarily high-order fractional partial differential equations (PDEs) to describe fractional hyperdiffusions. The fractional PDEs are constructed via fractional variational principle. A fast fractional Fourier transform (FFFT) is proposed to numerically integrate the high-order fractional PDEs so as to avoid stringent stability constraints in solving high-order evolution PDEs. The proposed high-order fractional PDEs are applied to the surface generation of proteins. We first validate the proposed method with a variety of test examples in two and three-dimensional settings. The impact of high-order fractional derivatives to surface analysis is examined. We also construct fractional PDE transform based on arbitrarily high-order fractional PDEs. We demonstrate that the use of arbitrarily high-order derivatives gives rise to time-frequency localization, the control of the spectral distribution, and the regulation of the spatial resolution in the fractional PDE transform. Consequently, the fractional PDE transform enables the mode decomposition of images, signals, and surfaces. The effect of the propagation time on the quality of resulting molecular surfaces is also studied. Computational efficiency of the present surface generation method is compared with the MSMS approach in Cartesian representation. We further validate the present method by examining some benchmark indicators of macromolecular surfaces, i.e., surface area, surface enclosed volume, surface electrostatic potential and solvation free energy. Extensive numerical experiments and comparison with an established surface model indicate that the proposed high-order fractional PDEs are robust, stable and efficient for biomolecular surface generation.

Geometric modeling of subcellular structures, organelles, and multiprotein complexes

Recently, the structure, function, stability, and dynamics of subcellular structures, organelles, and multiprotein complexes have emerged as a leading interest in structural biology. Geometric modeling not only provides visualizations of shapes for large biomolecular complexes but also fills the gap between structural information and theoretical modeling, and enables the understanding of function, stability, and dynamics. This paper introduces a suite of computational tools for volumetric data processing, information extraction, surface mesh rendering, geometric measurement, and curvature estimation of biomolecular complexes. Particular emphasis is given to the modeling of cryo-electron microscopy data. Lagrangian-triangle meshes are employed for the surface presentation. On the basis of this representation, algorithms are developed for surface area and surface-enclosed volume calculation, and curvature estimation. Methods for volumetric meshing have also been presented. Because the technological development in computer science and mathematics has led to multiple choices at each stage of the geometric modeling, we discuss the rationales in the design and selection of various algorithms. Analytical models are designed to test the computational accuracy and convergence of proposed algorithms. Finally, we select a set of six cryo-electron microscopy data representing typical subcellular complexes to demonstrate the efficacy of the proposed algorithms in handling biomolecular surfaces and explore their capability of geometric characterization of binding targets. This paper offers a comprehensive protocol for the geometric modeling of subcellular structures, organelles, and multiprotein complexes.

An atlas-based geometry pipeline for cardiac Hermite model construction and diffusion tensor reorientation

Here we present a novel atlas-based geometry pipeline for constructing three-dimensional cubic Hermite finite element meshes of the whole human heart from tomographic patient image data. To build the cardiac atlas, two superior atria, two inferior ventricles as well as the aorta and the pulmonary trunk are first segmented, and epicardial and endocardial boundary surfaces are extracted and smoothed. Critical points and skeletons (or central-line paths) are identified, following the cardiac topology. The surface model and the path tree are used to construct a hexahedral control mesh via a skeleton-based sweeping method. Derivative parameters are computed from the control mesh, defining cubic Hermite finite elements. The thickness of the atria and the ventricles is obtained using segmented epicardial boundaries or via offsetting from the endocardial surfaces in regions where the image resolution is insufficient. We also develop a robust optical flow approach to deform the constructed atlas and align it with the image from a second patient. This registration method is fully-automatic, and avoids manual operations required by segmentation and path extraction. Moreover, we demonstrate that this method can also be used to deformably map diffusion tensor MRI data with patient geometries to include fiber and sheet orientations in the finite element model.

Biomolecular surface construction by PDE transform

This work proposes a new framework for the surface generation based on the partial differential equation (PDE) transform. The PDE transform has recently been introduced as a general approach for the mode decomposition of images, signals, and data. It relies on the use of arbitrarily high-order PDEs to achieve the time-frequency localization, control the spectral distribution, and regulate the spatial resolution. The present work provides a new variational derivation of high-order PDE transforms. The fast Fourier transform is utilized to accomplish the PDE transform so as to avoid stringent stability constraints in solving high-order PDEs. As a consequence, the time integration of high-order PDEs can be done efficiently with the fast Fourier transform. The present approach is validated with a variety of test examples in two-dimensional and three-dimensional settings. We explore the impact of the PDE transform parameters, such as the PDE order and propagation time, on the quality of resulting surfaces. Additionally, we utilize a set of 10 proteins to compare the computational efficiency of the present surface generation method and a standard approach in Cartesian meshes. Moreover, we analyze the present method by examining some benchmark indicators of biomolecular surface, that is, surface area, surface-enclosed volume, solvation free energy, and surface electrostatic potential. A test set of 13 protein molecules is used in the present investigation. The electrostatic analysis is carried out via the Poisson-Boltzmann equation model. To further demonstrate the utility of the present PDE transform-based surface method, we solve the Poisson-Nernst-Planck equations with a PDE transform surface of a protein. Second-order convergence is observed for the electrostatic potential and concentrations. Finally, to test the capability and efficiency of the present PDE transform-based surface generation method, we apply it to the construction of an excessively large biomolecule, a virus surface capsid. Virus surface morphologies of different resolutions are attained by adjusting the propagation time. Therefore, the present PDE transform provides a multiresolution analysis in the surface visualization. Extensive numerical experiment and comparison with an established surface model indicate that the present PDE transform is a robust, stable, and efficient approach for biomolecular surface generation in Cartesian meshes.

Variational multiscale models for charge transport

This work presents a few variational multiscale models for charge transport in complex physical, chemical and biological systems and engineering devices, such as fuel cells, solar cells, battery cells, nanofluidics, transistors and ion channels. An essential ingredient of the present models, introduced in an earlier paper (Bulletin of Mathematical Biology, 72, 1562-1622, 2010), is the use of differential geometry theory of surfaces as a natural means to geometrically separate the macroscopic domain from the microscopic domain, meanwhile, dynamically couple discrete and continuum descriptions. Our main strategy is to construct the total energy functional of a charge transport system to encompass the polar and nonpolar free energies of solvation, and chemical potential related energy. By using the Euler-Lagrange variation, coupled Laplace-Beltrami and Poisson-Nernst-Planck (LB-PNP) equations are derived. The solution of the LB-PNP equations leads to the minimization of the total free energy, and explicit profiles of electrostatic potential and densities of charge species. To further reduce the computational complexity, the Boltzmann distribution obtained from the Poisson-Boltzmann (PB) equation is utilized to represent the densities of certain charge species so as to avoid the computationally expensive solution of some Nernst-Planck (NP) equations. Consequently, the coupled Laplace-Beltrami and Poisson-Boltzmann-Nernst-Planck (LB-PBNP) equations are proposed for charge transport in heterogeneous systems. A major emphasis of the present formulation is the consistency between equilibrium LB-PB theory and non-equilibrium LB-PNP theory at equilibrium. Another major emphasis is the capability of the reduced LB-PBNP model to fully recover the prediction of the LB-PNP model at non-equilibrium settings. To account for the fluid impact on the charge transport, we derive coupled Laplace-Beltrami, Poisson-Nernst-Planck and Navier-Stokes equations from the variational principle for chemo-electro-fluid systems. A number of computational algorithms is developed to implement the proposed new variational multiscale models in an efficient manner. A set of ten protein molecules and a realistic ion channel, Gramicidin A, are employed to confirm the consistency and verify the capability. Extensive numerical experiment is designed to validate the proposed variational multiscale models. A good quantitative agreement between our model prediction and the experimental measurement of current-voltage curves is observed for the Gramicidin A channel transport. This paper also provides a brief review of the field.

Topologically correct reconstruction of tortuous contour forests

Motivated by the need for correct and robust 3D models of neuronal processes, we present a method for reconstruction of spatially realistic and topologically correct models from planar cross sections of multiple objects. Previous work in 3D reconstruction from serial contours has focused on reconstructing one object at a time, potentially producing inter-object intersections between slices. We have developed a robust algorithm that removes these intersections using a geometric approach. Our method not only removes intersections but can guarantee a given minimum separation distance between objects. This paper describes the algorithm for geometric adjustment, proves correctness, and presents several results of our high-fidelity modeling.

An Automatic 3D Mesh Generation Method for Domains with Multiple Materials

This paper describes an automatic and efficient approach to construct unstructured tetrahedral and hexahedral meshes for a composite domain made up of heterogeneous materials. The boundaries of these material regions form non-manifold surfaces. In earlier papers, we developed an octree-based isocontouring method to construct unstructured 3D meshes for a single-material (homogeneous) domain with manifold boundary. In this paper, we introduce the notion of a material change edge and use it to identify the interface between two or several different materials. A novel method to calculate the minimizer point for a cell shared by more than two materials is provided, which forms a non-manifold node on the boundary. We then mesh all the material regions simultaneously and automatically while conforming to their boundaries directly from volumetric data. Both material change edges and interior edges are analyzed to construct tetrahedral meshes, and interior grid points are analyzed for proper hexahedral mesh construction. Finally, edge-contraction and smoothing methods are used to improve the quality of tetrahedral meshes, and a combination of pillowing, geometric flow and optimization techniques is used for hexahedral mesh quality improvement. The shrink set of pillowing schemes is defined automatically as the boundary of each material region. Several application results of our multi-material mesh generation method are also provided.

A Fast Variational Method for the Construction of Resolution Adaptive C-Smooth Molecular Surfaces

We present a variational approach to smooth molecular (proteins, nucleic acids) surface constructions, starting from atomic coordinates, as available from the protein and nucleic-acid data banks. Molecular dynamics (MD) simulations traditionally used in understanding protein and nucleic-acid folding processes, are based on molecular force fields, and require smooth models of these molecular surfaces. To accelerate MD simulations, a popular methodology is to employ coarse grained molecular models, which represent clusters of atoms with similar physical properties by psuedo- atoms, resulting in coarser resolution molecular surfaces. We consider generation of these mixed-resolution or adaptive molecular surfaces. Our approach starts from deriving a general form second order geometric partial differential equation in the level-set formulation, by minimizing a first order energy functional which additionally includes a regularization term to minimize the occurrence of chemically infeasible molecular surface pockets or tunnel-like artifacts. To achieve even higher computational efficiency, a fast cubic B-spline C(2) interpolation algorithm is also utilized. A narrow band, tri-cubic B-spline level-set method is then used to provide C(2) smooth and resolution adaptive molecular surfaces.