Monte-Carlo-Based Mesh Generation

You can run Java-demos for Line, Square, Cube, or Sphere.
Or download mc_mesh_demo.tbz file
unpack with tar tar -xvjf and run demos with
appletviewer name.html
where name = line, square, or cube.

Summary

Mesh generation, which discretizes computation geometries into small elements, is an important preprocessing part for numerical methods such as finite volume methods and finite volume methods. Computational domains are represented in meshless numerical methods by nodes, or in mesh-based methods by elements connected by nodes. Good nodal distribution is essential for the convergence of numerical methods. In our study a new approach based on Monte Carlo simulation is proposed for node distribution.

Monte Carlo (MC) methods are stochastic techniques, which use random numbers and probability statistics to solve problems. MC methods are widely used in various fields. MC methods are capable of investigate complex systems such as large energy systems, which consist of hundreds or thousands of atoms.

In the proposed mesh generation method surface or volume domains to be discretized are treated as atomic systems, and mesh nodes are considered as interacting particles. Particles are inserted/removed into/from the system, as well as displaced, using Grand Canonical Monte Carlo method. With energy minimization by the Monte Carlo simulation, a good number of particles, i.e. nodes, are distributed with desired separation from each other. The nodal separation is controlled by a predefined node spacing function. For mesh-based numerical methods, well-shaped triangular mesh elements can then be generated by connecting the nodes with constrained Delaunay methods.

Advantages

The GCMC method is conceptually simple and has a straightforward implementation. The resulting algorithm algorithm has the following advantages:

Simple robust and numerically stable.
Works in an identical way for both 2D and 3D cases.
Applicable for both mesh-based and meshless methods.

Comparative analysis of different algorithms

Several algorithms are implemented: Monte Carlo (MC), Grand Canonical MC, Molecular Dynamics (MD), Molecular Dynamics - Monte Carlo (MDMC), and Molecular Dynamics - Grand Canonical Monte Carlo (MDGCMC).

The distict characteristics of the algorithms are:

Monte-Carlo (MC): The number of nodes is fixed. Nodes are moved with random selection of both the direction and the length of the displacement along the direction.

Grand Cannonical Monte-Carlo (GCMC): The same as MC, but the number of nodes is selected so as to minimize the total system energy.

Molecular Dynamics (MD): Nodes are moved into the direction of cumulative interaction force. The displacements are proportional to the magnitude of the force.

Molecular Dynamics - Monte-Carlo (MDMC): The number of nodes is fixed. Nodes are moved into the direction of cumulative interaction force. The displacements along the direction are selected randomly.

Molecular Dynamics - Grand Canonical Monte-Carlo (MDGCMC): The same as MDMC before, but the number of nodes is selected so as to minimize the total system energy.

As can be seen from demo examples below, MD method is quite impractical for node placement. MC method leads to a more accurate and uniform node placement, compared to MDMC. However the latter is much faster. Likewise, MDGCMC method is fater than GCMC, but can lead to void regions. The optimum strategy can be running the MDGCMC algorithm at the beginning and GCMC in the final stages.

Demonstration examples

In the demo examples the Lennart Jones potential is used to control the dynamics of the particles.

Java-applets with the demonstration of the method can be run for Line, Square Cube, and Sphere.

Source codes

Here are the the source codes of the demo examples, which are also available as a tar-gzipped file.

Bibliography

Journal Article.
AUTHOR={Smirnov, A.V. and Zhang, H.},
TITLE={Physically-Based Node Distributions for Mesh Generation},
JOURNAL={International Journal of Modelling and Simulation},
NUMBER={205-4582},
VOLUME=28,
PUBLISHER={ACTA Press / IASTED},
YEAR=2008,

Conference Proceedings.

AUTHOR={Zhang, H. and Smirnov, A.},
TITLE="{Node Generation for Meshless Methods by Monte Carlo Simulation}",
BOOKTITLE={8th US National Congress on Computational Mechanics},
SERIES={USNCCM-05},
NUMBER={43.3.3},
YEAR=2005,
ADDRESS={Austin, TX},
URL

Ph.D. Thesis

@phdthesis{ZhWVU05,
AUTHOR={Hanzhou Zhang},
TITLE={Mesh Generation for Voxel-Based Objects},
SCHOOL={West Virginia University},
NOTE={Scientific advisor: A.Smirnov},
YEAR=2005,
PAGES=122

Journal Article.

AUTHOR={Zhang, H. and Smirnov, A. V.},
TITLE="{Node placement for triangular mesh generation by Monte Carlo simulation}",
JOURNAL={\bf International Journal for Numerical Methods in Engineering},
YEAR=2005,
NUMBER=7,
VOLUME=64,
PAGES={973-989},
PUBLISHER={John Wiley & Sons, Ltd.},
URL
dx.doi.org

Concerence Paper.
AUTHOR={Zhang, H. and Smirnov, A.V.},
TITLE={Surface Mesh Generation for Voxel-Based Objects by Energy Minimization},
BOOKTITLE={International Conference on Imaging Science Systems and Technology: Computer Graphics},
EDITOR={H.R.Arabnia},
YEAR=2005,
DATE={June 27-30},
PUBLISher={CSREA Press},
ADDRESs={LasVegas, Nevada},
PAGES={55-61},
FILE={/home/andrei/projects/ring/tex/CISST.05},
URL

Conference Paper.

AUTHOR={Hanzhou Zhang and Andrei V. Smirnov},
TITLE="{Node Distribution for Numerical Methods with Monte Carlo Simulation}",
BOOKTITLE={IASTED International Conference on Modelling and Simulation (MS 2005)},
SERIES={MS-05},
NUMBER={459-037},
PAGES={363-368},
YEAR=2005,
ADDRESS={Cancun, Mexico},
URL

Worshop.

AUTHOR = {Andrei V. Smirnov and Hanzhou Zhang},
TITLE = {Surface Mesh Generation on Voxel-Based Objects},
BOOKTITLE ={13th International Meshing Roundtable},
ADDRESS={Williamsburg, Virginia USA},
DATE={SEptember 19-22},
PAGES={291-298},
YEAR =2004,
URL

Journal Article.

AUTHOR={Smirnov, A.V.},
TITLE={Tool assisted mesh generation based on a tissue-growth
model},
JOURNAL={\bf Medical and Biological Engineering and Computing},
VOLUME=41, 
NUMBER=4,
YEAR=2003,
PAGES={494-497}