short line

Topological Changes


In applications with a moving boundary, the deformation of the domain is themain obstacle in obtaining a tractable physical model. In addition, some of these applications exhibit topological changes (i.e. pinching or joining of disjoint parts of the interface) and prove even more difficult to model. Examples of this are budding of lipid bio-membranes [2], droplet pinching in an electro-wetting device [3, 17], and many other types of fluid flow [4].

One popular method for capturing free surface motion is the level set method [10, 11], which advects a scalar field function whose zero level set represents the interface. Level set methods have the advantage of being completely Eulerian and can automatically handle topological changes, though the physics underlying such changes is often not well resolved. In particular, level set methods require a small amount of diffusion to allow for topological changes to occur. This can cause problems with mass conservation and requires special handling [6] or refinement [9]. Another issue of the level set method, for curvature driven flows, is they typically use an explicit calculation of the interface curvature which can create numerical artifacts and noise. Other implicit surface methods include the phase field method [19, 14], which uses a diffuse interface model (as opposed to a sharp or explicit interface). Phase field methods have similar advantages and drawbacks as the level set method.

Alternatively, one can use an explicit representation of the interface (i.e. an interface mesh) and there exist numerical methods that take advantage of the intrinsic representation of the interface [1, 5, 8]. However, the main disadvantage of these explicit surface representations is the computational difficulty in handling large deformations of the mesh. In two dimensions, the mesh can be adjusted through local re-meshing [13] or mesh smoothing [7], but can still be awkward. In three dimensions, it is not clear what the best methods are for adjusting a mesh as it deforms.

The method we developed takes inspiration from some of the ideas in the above references and combines them in a novel way to generate meshes of arbitrary domains. In addition, we introduce a shape optimization approach for ensuring mesh conformity. We emphasize that our re-meshing method does not need to be executed at every time step of the simulation. The number of re-meshes only depends on the continuous deformation being approximated and the number of topological changes. See my paper [20] for more details.

Algorithm Overview

Timestep Loop Diagram

Our algorithm primarily consists of a special re-meshing routine that is embedded inside a time stepping loop (see Figure 1). We make extensive use of distance functions and shape skeletons to resolve the shape and topology of the domain when generating a new mesh. We also use a shape optimization approach to ensure that the new mesh conforms to the boundary of the domain. Topological changes are implemented by locally diffusing the distance function in the neighborhood of the change.

The main point of our algorithm is to provide a way for generating meshes that can follow an arbitrarily complex deformation and can continue through topological changes without having to specify the type of topological change, or specify geometric details, or perform surgery on the mesh. Even if the physics of the topological change is well understood, it is not necessarily clear what the mesh should be after the change. This is especially important in threedimensions. Therefore, this algorithm is an answer to the question of how to compute and mesh through a topological change, but not to the question of modeling the physics of the change itself.


--- Rotating Vortices
In this simulation, we prescribe a velocity field that is a two-by-two array of counter-rotating vortices, and the divergence of the velocity is zero. The initial domain shape is a circle inside a unit square; the initial mesh was generated by the commercial package “MeshGen”. The vertices of the boundary move with the given velocity field and the rest of the vertices move by extending the vector velocity on the boundary using a harmonic extension.

--- Pinching Droplet by EWOD
Next, we use a simulation of an Electro-Wetting On Dielectric (EWOD) device to drive the motion of a water droplet to a topological change (droplet pinching). The device consists of two parallel plates very close together with a water droplet squashed in between with air surrounding it, hence the problem is effectively 2-D Hele-Shaw flow with surface tension. A 3x3 array of square electrodes is embedded in the bottom plate, which are used for applying voltages that can change the effective surface tension locally [12]. For more details about the model, variational formulation, and numerical method, see [15, 17, 16, 18]. --- Joining Droplets by Surface Tension
In this last experiment, we use the EWOD simulation without any electrical forcing. Hence, the flow is purely due to surface tension. This example shows how our method handles connecting or joining droplets.


[1] E. Baensch, P. Morin, and R. H. Nochetto. A finite element method for surface diffusion: the parametric case. Journal of Computational Physics, 203:321–343, 2005.

[2] T. Baumgart, S. T. Hess, and W. W. Webb. Imaging coexisting fluid domains in biomembrane models coupling curvature and line tension. Nature, 425:821–824, October 2003.

[3] S. K. Cho, H. Moon, J. Fowler, S.-K. Fan, and C.-J. Kim. Splitting a liquid droplet for electrowetting-based microfluidics. In International Mechanical Engineering Congress and Exposition, New York, NY, Nov 2001. ASME Press. ISBN: 0791819434.

[4] M. V. Dyke. An Album of Fluid Motion. Parabolic Press, May 1982.

[5] G. Dziuk. An algorithm for evolutionary surfaces. Numerische Mathematik, 58(1):603–611, 1990.

[6] D. Enright, R. P. Fedkiw, J. Ferziger, and I. Mitchell. A hybrid particle level set method for improved interface capturing. Journal of Computational Physics, 183:83–116, 2002.

[7] J.M. Escobar, G.Montero, R.Montenegro, and E. Rodriguez. An algebraic method for smoothing surface triangulations on a local parametric space. International Journal for Numerical Methods in Engineering, 66(4):740–760, 2006.

[8] T. Y. Hou, J. S. Lowengrub, and M. J. Shelley. Boundary integral methods for multicomponent fluids and multiphase materials. Journal of Computational Physics, 169:302–362, 2001.

[9] F. Losasso, F. Gibou, and R. Fedkiw. Simulating water and smoke with an octree data structure. In ACM Trans. Graph. (SIGGRAPH Proc.), pages 457–462, Los Angeles, 2004.

[10] S. Osher and R. Fedkiw. Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag, New York, NY, 2003.

[11] S. A. Sethian. Level Set Methods and Fast Marching Methods, 2nd Edition. Cambridge University Press, New York, NY, 1999.

[12] B. Shapiro, H. Moon, R. Garrell, and C.-J. Kim. Equilibrium behavior of sessile drops under surface tension, applied external fields, and material variations. Journal of Applied Physics, 93(9):5794–5811, 2003.

[13] J. R. Shewchuk. Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. In M. C. Lin and D. Manocha, editors, Applied Computational Geometry: Towards Geometric Engineering, volume 1148 of Lecture Notes in Computer Science, pages 203–222. Springer-Verlag, May 1996. From the First ACM Workshop on Applied Computational Geometry.

[14] Y. Sun and C. Beckermann. Diffuse interface modeling of two-phase flows based on averaging: mass and momentum equations. Physica D, 198:281, 2004.

[15] S. W. Walker, A. Bonito, and R. H. Nochetto. Mixed finite element method for electrowetting on dielectric with contact line pinning. accepted to Interfaces and Free Boundaries, 2009.

[16] S. W. Walker and B. Shapiro. A control method for steering individual particles inside liquid droplets actuated by electrowetting. Lab on a Chip, 5:1404–1407, October 2005.

[17] S. W. Walker and B. Shapiro. Modeling the fluid dynamics of electrowetting on dielectric (ewod). Journal of Microelectromechanical Systems, 15(4):986–1000, August 2006.

[18] S. W. Walker, B. Shapiro, and R. H. Nochetto. Electrowetting with contact line pinning: Computational modeling and comparisons with experiments. Physics of Fluids, 21(10):102103, 2009.

[19] P. Yue, J. J. Feng, C. Liu, and J. Shen. A diffuse-interface method for simulating two-phase flows of complex fluids. Journal of Fluid Mechanics, 515:293, 2004.

[20] R. H. Nochetto and S. W. Walker. A hybrid variational front tracking-level set mesh generator for problems exhibiting large deformations and topological changes. Journal of Computational Physics, 229(18):6243-6269, 2010.