Global,Dense Multiscale Reconstruction for a Billion Points

We present a variational approach for surface reconstruction from a set of oriented points with scale information. We focus particularly on scenarios with nonuniform point densities due to images taken from different distances. In contrast to previous methods, we integrate the scale information in the objective and globally optimize the signed distance function of the surface on a balanced octree grid. We use a finite element discretization on the dual structure of the octree minimizing the number of variables. The tetrahedral mesh is generated efficiently with a lookup table which allows to map octree cells to the nodes of the finite elements. We optimize memory efficiency by data aggregation, such that robust data terms can be used even on very large scenes. The surface normals are explicitly optimized and used for surface extraction to improve the reconstruction at edges and corners.     

Finite element approximation of elliptic partial differential equations on implicit surfaces

The aim of this paper is to investigate finite element methods for the solution of elliptic partial differential equations on implicitly defined surfaces. The problem of solving such equations without triangulating surfaces is of increasing importance in various applications, and their discretization has recently been investigated in the framework of finite difference methods. For the two most frequently used implicit representations of surfaces, namely level set methods and phase-field methods, we discuss the construction of finite element schemes, the solution of the arising discretized problems, and provide error estimates. The convergence properties of the finite element methods are illustrated by computations for several test problems.     

A finite element based level set method for two-phase incompressible flows

We present a method that has been developed for the efficient numerical simulation of two-phase incompressible flows. For capturing the interface between the phases the level set technique is applied. The continuous model consists of the incompressible Navier–Stokes equations coupled with an advection equation for the level set function. The effect of surface tension is modeled by a localized force term at the interface (so-called continuum surface force approach). For spatial discretization of velocity, pressure and the level set function conforming finite elements on a hierarchy of nested tetrahedral grids are used. In the finite element setting we can apply a special technique to the localized force term, which is based on a partial integration rule for the Laplace–Beltrami operator. Due to this approach the second order derivatives coming from the curvature can be eliminated. For the time discretization we apply a variant of the fractional step θ-scheme. The discrete saddle point problems that occur in each time step are solved using an inexact Uzawa method combined with multigrid techniques. For reparametrization of the level set function a new variant of the fast marching method is introduced. A special feature of the solver is that it combines the level set method with finite element discretization, Laplace–Beltrami partial integration, multilevel local refinement and multigrid solution techniques. All these components of the solver are described. Results of numerical experiments are presented.     

Automated interrogation and adaptive subdivision of shape using medial axis transform

We present a method for the generation of coarse and fine finite element meshes on multiply connected surfaces. Our method is based on the medial axis transform (MAT) which is employed to decompose a complex shape into topologically simple subdomains. One important property of our approach is that MAT is effectively employed to automatically extract some important shape characteristics and their length scales. Using this technique, we can create a coarse subdivision of a complex surface and select local element size to generate fine triangular meshes within individual subregions. The MAT allows us to carry out these processes in an automated manner. Thus, our approach can lead to integration of automated finite element (FE) mesh generation schemes into existing FE preprocessing systems. We also briefly discuss several design and analysis applications, which include adaptive surface approximations and adaptive h- and p-version finite element analysis (FEA) processes, in order to demonstrate our method.     

A High-Order Local Projection Stabilization Method for Natural Convection Problems

In this paper, we propose a local projection stabilization (LPS) finite element method applied to numerically solve natural convection problems. This method replaces the projection-stabilized structure of standard LPS methods by an interpolation-stabilized structure, which only acts on the high frequencies components of the flow. This approach gives rise to a method which may be cast in the variational multi-scale framework, and constitutes a low-cost, accurate solver (of optimal error order) for incompressible flows, despite being only weakly consistent. Numerical simulations and results for the buoyancy-driven airflow in a square cavity with differentially heated side walls at high Rayleigh numbers (up to \(Ra=10^7\)) are given and compared with benchmark solutions. Good accuracy is obtained with relatively coarse grids.     

The variational multiscale method for laminar and turbulent flow

Summary  The present article reviews the variational multiscale method as a framework for the development of computational methods for the simulation of laminar and turbulent flows, with the emphasis placed on incompressible flows. Starting with a variational formulation of the Navier-Stokes equations, a separation of the scales of the flow problem into two and three different scale groups, respectively, is shown. The approaches resulting from these two different separations are interpreted against the background of two traditional concepts for the numerical simulation of turbulent flows, namely direct numerical simulation (DNS) and large eddy simulation (LES). It is then focused on a three-scale separation, which explicitly distinguishes large resolved scales, small resolved scales, and unresolved scales. In view of turbulent flow simulations as a LES, the variational multiscale method with three separated scale groups is refered to as a “variational multiscale LES”. The two distinguishing features of the variational multiscale LES in comparison to the traditional LES are the replacement of the traditional filter by a variational projection and the restriction of the effect of the unresolved scales to the smaller of the resolved scales. Existing solution strategies for the variational multiscale LES are presented and categorized for various numerical methods. The main focus is on the finite element method (FEM) and the finite volume method (FVM). The inclusion of the effect of the unresolved scales within the multiscale environment via constant-coefficient and dynamic subgrid-scale modeling based on the subgrid viscosity concept is also addressed. Selected numerical examples, a laminar and two turbulent flow situations, illustrate the suitability of the variational multiscale method for the numerical simulation of both states of flow. This article concludes with a view on potential future research directions for the variational multiscale method with respect to problems of fluid mechanics.     

Variational formulations for surface tension,capillarity and wetting

The interest in the simulation of flows with significant surface tension effects has grown significantly in recent years. This has been driven by the substantial advances made in the measurement and manufacturing of microscopic systems, since at small length scales surface phenomena are dominant. In this article, surface tension, capillarity and wetting effects are discussed in terms of the virtual–work principle and shape sensitivity, starting from first principles and arriving at variational formulations that are adequate for numerical treatment (by finite elements, for example). To make the exposition self-contained, some elements of differential geometry are recalled using a formulation that is fully in Cartesian coordinates and may thus be more friendly to readers not familiar with covariant derivatives. All necessary results are proved in this Cartesian formulation. Several numerical examples computed with a finite element/level set formulation are used to illustrate this challenging physical problem.     

A strong convergence theorem for a general split equality problem with applications to optimization and equilibrium problem

The purpose of this paper is to introduce and study an iterative algorithm for solving a general split equality problem. The problem consists of finding a common element of the set of common zero points for a finite family of maximal monotone operators, the set of common fixed points for a finite family of demimetric mappings and the set of common solutions of variational inequality problems for a finite family of inverse strongly monotone mappings in the setting of infinite-dimensional Hilbert spaces. Using our iterative algorithm, we state and prove a strong convergence theorem for approximating a solution of the split equality problem. As special cases, we shall utilize our results to study the split equality equilibrium problems and the split equality optimization problems. Our result complements and extends some related results in literature.     

Unified analysis of enriched finite elements for modeling cohesive cracks

Aiming to provide a justified theoretical ground based on which different enriched finite elements can be systematically compared, we developed in this work a unified framework for modeling cohesive cracks using the variational multiscale method. The kinematics (i.e. coarse and fine scale displacement and strain fields) and statics (i.e. coarse and fine scale equilibrium equations) are thoroughly investigated in both continuum and discrete settings. With respect to the fine scale kinematics and statics adopted in the embedded finite element method (EFEM) and the extended finite element method (XFEM), we mainly discuss four groups of enriched finite elements with non-uniform discontinuity modes, i.e. the kinematically optimal symmetric EFEM and XFEM, as well as, the kinematically and statically optimal non-symmetric EFEM and XFEM. In all these methods, the enrichment parameters can be regarded either as element-wise local or continuous global variables. The enriched finite elements with material/element/node enrichments are then exemplified in an increasing order of their respective capabilities in representing the fine scale kinematics, and the interrelations between them are also discussed. Owing to this unified framework, we are able to clarify some existing points of view related to EFEM and XFEM. It is found that, if the same fine scale statics is used and the same local/global property is assumed for the involved enrichment parameters, XFEM can be regarded as a kinematically enhanced EFEM since it accounts for a more general fine scale kinematics than that (i.e. relative rigid body motions and self-stretching) considered in EFEM. Finally, several simple, but sufficiently representative, numerical examples are presented to show the significance in appropriately reflecting the fine scale kinematics and statics in an enriched finite element for modeling cohesive cracks.     

Spatially adaptive techniques for level set methods and incompressible flow

Since the seminal work of [Sussman, M, Smereka P, Osher S. A level set approach for computing solutions to incompressible two-phase flow. J Comput Phys 1994;114:146–59] on coupling the level set method of [Osher S, Sethian J. Fronts propagating with curvature-dependent speed: algorithms based on Hamilton–Jacobi formulations. J Comput Phys 1988;79:12–49] to the equations for two-phase incompressible flow, there has been a great deal of interest in this area. That work demonstrated the most powerful aspects of the level set method, i.e. automatic handling of topological changes such as merging and pinching, as well as robust geometric information such as normals and curvature. Interestingly, this work also demonstrated the largest weakness of the level set method, i.e. mass or information loss characteristic of most Eulerian capturing techniques. In fact, [Sussman M, Smereka P, Osher S. A level set approach for computing solutions to incompressible two-phase flow. J Comput Phys 1994;114:146–59] introduced a partial differential equation for battling this weakness, without which their work would not have been possible. In this paper, we discuss both historical and most recent works focused on improving the computational accuracy of the level set method focusing in part on applications related to incompressible flow due to both of its popularity and stringent accuracy requirements. Thus, we discuss higher order accurate numerical methods such as Hamilton–Jacobi WENO [Jiang G-S, Peng D. Weighted ENO schemes for Hamilton–Jacobi equations. SIAM J Sci Comput 2000;21:2126–43], methods for maintaining a signed distance function, hybrid methods such as the particle level set method [Enright D, Fedkiw R, Ferziger J, Mitchell I. A hybrid particle level set method for improved interface capturing. J Comput Phys 2002;183:83–116] and the coupled level set volume of fluid method [Sussman M, Puckett EG. A coupled level set and volume-of-fluid method for computing 3d and axisymmetric incompressible two-phase flows. J Comput Phys 2000;162:301–37], and adaptive gridding techniques such as the octree approach to free surface flows proposed in [Losasso F, Gibou F, Fedkiw R. Simulating water and smoke with an octree data structure, ACM Trans Graph (SIGGRAPH Proc) 2004;23:457–62].     

Least-squares finite element formulation for shear-deformable shells

We present a least-squares based finite element formulation for the numerical analysis of shear-deformable shell structures. The variational problem is obtained by minimizing the least-squares functional, defined as the sum of the squares of the shell equilibrium equations residuals measured in suitable norms of Hilbert spaces. The use of least-squares principles leads to a variational unconstrained minimization problem where compatibility conditions between approximation spaces never arise, i.e. stability requirements such as inf–sup conditions never arise. The proposed formulation retains the generalized displacements and stress resultants as independent variables and, in view of the nature of the variational setting upon which the finite element model is built, allows for equal-order interpolation. A p-type hierarchical basis is used to construct the discrete finite element model based on the least-squares formulation. Exponentially fast decay of the least-squares functional is verified for increasing order of the modal expansions. Several well established benchmark problems are solved to demonstrate the predictive capability of the least-squares based shell elements. Shell elements based on this formulation are shown to be effective in both membrane- and bending-dominated states.     

Construction of Shapes Arising from the Minkowski Problem Using a Level Set Approach

The Minkowski problem asks a fundamental question in differential geometry whose answer is not only important in that field but has real world applications as well. We endeavor to construct the shapes that arise from the Minkowski problem by forming a PDE that flows an initial implicitly defined hypersurface to an approximation of the shape under the level set framework. Tools and ideas found in the various applications of level set methods are gathered to generate this PDE. Numerically, its solution is determined by incorporating high order finite difference schemes over the uniform grid available in the framework. Finally, we use our approach in various test cases to generate various shapes arising from different given data in the Minkowski problem.     

Surface Smoothing Procedures in Computational Contact Mechanics

This work addresses the problems arising in the finite element simulation of contact problems undergoing large deformation. The frictional contact problem is formulated in the continuum framework, introducing the interface laws for the normal and tangential stress components in the contact area. The variational formulation is presented, considering different methods to enforce the contact constraints. The spatial discretization within the finite element method is applied, as well as the temporal discretization required to solve the three sources of nonlinearities: geometric, material and frictional contact. The discretization of contact surfaces is discussed in detail, including different surface smoothing procedures. This numerical strategy allows to solve the difficulties associated with the discontinuities in the contact surface geometry introduced by finite element discretization, which leads to nonphysical oscillations of the contact force for large sliding problems. The geometrical accuracy of different interpolation methods is evaluated, paying particular attention to the Nagata patch interpolation recently proposed. In this framework, the Node-to-Nagata contact elements are developed using the augmented Lagrangian method to regularize the variational frictional contact problem. The techniques used to search for contact in case of large deformations are discussed, including self-contact phenomena. Several numerical examples are presented, comprising both the contact between deformable and rigid obstacles and the contact between deformable bodies. The results show that the accuracy and robustness of the numerical simulations is improved when the contact surface is smoothed with Nagata patches.     

Flux-free Finite Element Method with Lagrange Multipliers for Two-fluid Flows

In this paper we consider the flux-free finite element method based on the Eulerian framework for immiscible incompressible two-fluid flows, which is defined so as to preserve the mass of each fluid. This method is derived from the variational formulation including the flux-free constraint for the Navier–Stokes equations by the Lagrange multiplier technique. Focusing on the stationary problem, we prove the well-posedness of the finite element solution by a discrete inf-sup condition and show basic error estimates. Moreover we also show the stability of the fractional-step projection finite element scheme for the non-stationary problem. Finally, we give some numerical results to validate our method.     

Mixed finite element method and high-order local artificial boundary conditions for exterior problems of elliptic equation

The mixed finite element method is used to solve the exterior elliptic problem with high-order local artificial boundary conditions. New unknowns are introduced to reduce the order of the derivatives to two. This leads to an equivalent mixed variational problem such that the normal finite element can be used and special finite elements are no longer needed on the adjacent layer of the artificial boundary. Error estimates are obtained for some local artificial boundary conditions with prescribed order. Numerical examples are presented and the results demonstrate the effectiveness of this method.     

A Review of Statistical Approaches to Level Set Segmentation: Integrating Color,Texture, Motion and Shape

Since their introduction as a means of front propagation and their first application to edge-based segmentation in the early 90’s, level set methods have become increasingly popular as a general framework for image segmentation. In this paper, we present a survey of a specific class of region-based level set segmentation methods and clarify how they can all be derived from a common statistical framework. Region-based segmentation schemes aim at partitioning the image domain by progressively fitting statistical models to the intensity, color, texture or motion in each of a set of regions. In contrast to edge-based schemes such as the classical Snakes, region-based methods tend to be less sensitive to noise. For typical images, the respective cost functionals tend to have less local minima which makes them particularly well-suited for local optimization methods such as the level set method. We detail a general statistical formulation for level set segmentation. Subsequently, we clarify how the integration of various low level criteria leads to a set of cost functionals. We point out relations between the different segmentation schemes. In experimental results, we demonstrate how the level set function is driven to partition the image plane into domains of coherent color, texture, dynamic texture or motion. Moreover, the Bayesian formulation allows to introduce prior shape knowledge into the level set method. We briefly review a number of advances in this domain.     

Computation of incompressible bubble dynamics with a stabilized finite element level set method

This paper presents a stabilized finite element method for the three dimensional computation of incompressible bubble dynamics using a level set method. The interface between the two phases is resolved using the level set approach developed by Sethian [Level Set Methods and Fast Marching Methods, Cambridge University Press, 1999], Sussman et al. [J. Comput. Phys. 114 (1994) 146], and Sussman et al. [J. Comput. Phys. 148 (1999) 81–124]. In this approach the interface is represented as a zero level set of a smooth function. The streamline-upwind/Petrov–Galerkin method was used to discretize the governing flow and level set equations. The continuum surface force (CSF) model proposed by Brackbill et al. [J. Comput. Phys. 100 (1992) 335–354] was applied in order to account for surface tension effects. To restrict the interface from moving while re-distancing, an improved re-distancing scheme proposed in the finite difference context [J. Comput. Phys. 148 (1999) 81–124] is adapted for finite element discretization. This enables us to accurately compute the flows with large density and viscosity differences, as well as surface tension. The capability of the resultant algorithm is demonstrated with two and three dimensional numerical examples of a single bubble rising through a quiescent liquid, and two bubble coalescence.     

Rosenbrock-type methods applied to finite element computations within finite strain viscoelasticity

In this article time-adaptive high-order Rosenbrock-type methods are applied to the system of differential–algebraic equations which results from the space-discretization using finite elements based on a constitutive model of finite strain viscoelasticity. It is shown that in this smooth problem more efficient finite element computations result in comparison to classical finite element approaches since the time integration on the basis of Rosenbrock-type methods does not lead to a system of non-linear equations. In other words, all aspects of implicit finite elements as local iterations on Gauss-point level and global equilibrium iterations do not occur. The first introduction to this approach proposed by Hartmann and Wensch [22] is extended here to the case of finite strain applications, where the geometrical non-linear deformation has an essential contribution to the non-linearities. Additionally, a clear decomposition into local (element or Gauss-point) work and global computational work using the Schur-complement is introduced to exploit the classical finite element character. Moreover, the extension to the reaction force computation, which is different to the classical approach, and the influence to mixed element formulations, here, the three-field formulation for displacements, pressure and dilatation, are discussed. The performance of various Rosenbrock-type methods is investigated and shows that for low accuracy requirements as in order one methods, the proposal yields a drastic reduction of the computational time.     

Automating the Finite Element Method

The finite element method can be viewed as a machine that automates the discretization of differential equations, taking as input a variational problem, a finite element and a mesh, and producing as output a system of discrete equations. However, the generality of the framework provided by the finite element method is seldom reflected in implementations (realizations), which are often specialized and can handle only a small set of variational problems and finite elements (but are typically parametrized over the choice of mesh). This paper reviews ongoing research in the direction of a complete automation of the finite element method. In particular, this work discusses algorithms for the efficient and automatic computation of a system of discrete equations from a given variational problem, finite element and mesh. It is demonstrated that by automatically generating and compiling efficient low-level code, it is possible to parametrize a finite element code over variational problem and finite element in addition to the mesh.