HomePage Per-Olof Persson
http://www.mit.edu/~persson/software.html
Software
Meshing:
- DistMesh – A Simple Mesh Generator in MATLAB
Educational MATLAB codes:
- Tridiagonal Eigenvalues in MATLAB – Interface to LAPACK routines for computing eigenvalues of tridiagonal matrices and singular values of bidiagonal matrices
- Level Set Demo – Simple MATLAB scripts for illustration of explicit/implicit interface tracking, reinitialization, and the fast marching method (undocumented, but see presentations for slides and notes).
- fempoisson.m – Solves the Poisson equation on an unstructured grid (square in this example but easy to change) using linear finite elements. Good start to learn about implementation of FEM.
- poiunit.m – Fourier solution of Poisson’s equation on the unit line, square, or cube. Good for verification of Poisson solvers, but slow if many Fourier terms are used (high accuracy).
- laplacefft.m – Solve the Laplace equation on a rectangular domain using the FFT. Supports Dirichlet or Dirichlet/Neumann conditions. Contains the following short functions for discrete Sine and Cosine transforms:
- Implementation of Finite Element-Based Navier-Stokes Solver
————————–end HomePage
http://www-math.mit.edu/~persson/mesh/gallery_images.html
3-D meshes, the left plots show surface meshes and the right plots show cross sections.
———–
http://people.scs.fsu.edu/~burkardt/m_src/distmesh/distmesh.html
DISTMESH is a MATLAB library which generates and manipulates unstructured meshes in 2D, 3D and general ND. The code is relatively simple, and the user is able to define a variety of geometric shapes, and desired mesh densities.
DISTMESH can be a very quick and flexible means of computing a set of points in a region. However, keep in mind the following flaws:
- Especially if you are have specified some fixed points which must appear in the mesh, it is possible for DISTMESH to return multiple instances of the same point. For finite element applications, in particular, this can result in catastrophe. The program TABLE_MERGE can fix this.
- The nodes produced by DISTMESH are not ordered or sorted in any way whatsoever.
- Because the nodes are not ordered in any way, the triangular elements produced by DISTMESH will typically contain nodes with widely ranging indices. For finite element applications, this can result in a system matrix with an unnecessarily outrageous bandwidth. The program TRIANGULATION_RCM can fix this, after the fact.
- The triangles produced by DISTMESH are not necessarily oriented; they are just as likely to have positive or negative orientation. Some finite element programs insist that all triangles have positive orientation. The program TRIANGULATION_ORIENT can fix this, after the fact.
- When DISTMESH is trying to approximate a boundary, particularly a long straight boundary, it is possible for several points that really belong on the boundary to be slightly out of line. This means that they will be used to form a triangle, of very small area, and terrible conditioning. This can result in perplexing problems near the boundary.
- Because DISTMESH uses tolerances, it is possible for some nodes to lie outside the boundary of the region; it is possible for some triangles on the boundary to lie partially outside the region; it is possible for triangles that lie partly on the boundary, but entirely within the region, to be deleted, leaving a triangular hole.
- Once you have the mesh, you may want to know which nodes lie on the boundary. You’ll want this information, for instance, if you need to impose boundary conditions on such nodes. You can get a list of the boundary nodes using the program TRIANGULATION_BOUNDARY_NODES.
Usage:
- [ p, t ] = distmesh_2d ( fd, fh, h, box, iteration_max, fixed );
- takes:
- fd, the name of a distance function defining the region;
- fh, the name of a mesh density function;
- h, the nominal mesh spacing;
- box, defining a box that contains the region;
- iteration_max, which limits the number of iterations;
- fixed, a list of points which must be included in the mesh.
and returns a triangulation defined by:
- p, a list of node coordinates;
- t, a list of node indices forming triangles;
Related Data and Programs:
DIST_PLOT is a MATLAB program which creates a color contour plot of the distance functions that are used by DISTMESH.
DISTMESH_3D is a MATLAB program which is a subset of the DISTMESH routines, exclusively for 3D problems.
TABLE_IO is a MATLAB library which reads and writes files using the TABLE format; these routines are used by DISTMESH when creating some output files.
TABLE_MERGE is a FORTRAN90 program which removes duplicate points from a TABLE file; it can also remove points that are « close » to each other;
TEST_TRIANGULATION is a MATLAB library which defines some test regions for triangulation.
TRIANGLE is a C program which triangulates a region.
TRIANGULATION_BOUNDARY_NODES is a MATLAB program which reads data defining a triangulation and determines which nodes lie on the boundary.
TRIANGULATION_DISPLAY_OPEN_GL is a C++ program which reads files defining a triangulation and displays an image using Open GL.
TRIANGULATION_L2Q is a MATLAB program which reads data defining a linear triangulation and adds midpoint nodes to create a quadratic triangulation.
TRIANGULATION_MASK is a MATLAB program which is compiled with a user routine that defines a region; it then reads data defining a triangulation and removes all triangles that are outside the region. This is one way to clean up an unconstrained Delaunay triangulation of a nonconvex region.
TRIANGULATION_ORDER3 is a data directory which discusses order 3 triangulations; The node and triangle files output by DISTMESH are an example of such triangulations.
TRIANGULATION_ORIENT is a MATLAB program which reads data defining a triangulation, makes sure that every triangle has positive orientation, and if not, writes a corrected triangle file.
TRIANGULATION_PLOT is a MATLAB program which plots a triangulation.
TRIANGULATION_RCM is a MATLAB program which reads data defining a triangulation, and uses the Reverse Cuthill McKee algorithm to reorder the nodes so as the reduce the bandwidth of the corresponding adjacency matrix. This can be very helpful for cases where the data is to be handled by a frontal technique, or treated as a banded linear system.
TRIANGULATION_REFINE is a MATLAB program which reads data defining a triangulation and creates a refinement of the triangulation by subdividing each triangle.
Author:
DISTMESH is Copyright (C) 2004 Per-Olof Persson.
This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place – Suite 330, Boston, MA 02111-1307, USA.
If you use DISTMESH in any program or publication, please acknowledge its authors by citing the reference.
Reference:
- http://math.mit.edu/~persson/
Per-Olof Persson’s web site. - Per-Olof Persson and Gilbert Strang,
A Simple Mesh Generator in MATLAB,
SIAM Review,
Volume 46, Number 2, June 2004, pages 329-345,
Available online at ../../pdf/persson_distmesh.pdf
Tar File:
A GZIP’ed TAR file of the contents of this directory is available. This is only done as a convenience for users who want ALL the files, and don’t want to download them individually. This is not a convenience for me, so don’t be surprised if the tar file is somewhat out of date.
- distmesh_m_src.tar.csh the commands used to create the GZIP’ed TAR file.
- distmesh_m_src.tar.gz the GZIP’ed TAR file.
Source Code:
- boundedges.m finds the surface edges in a triangular mesh.
- circumcenter.m computes the circumcenters of the triangles that form a triangulation of a set of nodes.
- dcircle.m returns the signed distance of one or more points to a circle.
- ddiff.m returns the signed distance of one or more points to a region defined as the set difference of two regions.
- dexpr.m returns the signed distance of one or more points to a region defined by a general symbolic expression.
- dintersect.m returns the signed distance to a region that is the intersection of two regions.
- distmesh_2d.m computes a mesh of a given 2D region.
- distmesh_nd.m computes a mesh of a given ND region.
- dmatrix.m returns the signed distance to a region by interpolation of known distance values on a Cartesian grid.
- dpoly.m returns the signed distance of one or more points to a polygon.
- drectangle.m returns the signed distance of one or more points to a rectangle.
- drectangle0.m, returns the signed distance of one or more points to a rectangle.
- dsegment.cpp (C++ file), a version of the algorithm for the signed distance of one or more points to a set of line segments, for use with a non-Windows version of MATLAB. This file must be compiled, and the corresponding MEX file must be available to define the MATLAB/C++ interface.
- dsegment.dll (binary file), a Windows DLL file, returns the signed distance of one or more points to a set of line segments.
- dsegment.m a pure MATLAB version of DSEGMENT, which returns the signed distance of one or more points to a set of line segments. This routine will be significantly slower than the MEXGLX or DLL versions.
- dsegment.mexglx (binary file), used on non-Windows machines to allow MATLAB to calculate the DSEGMENT algorithm (distance to a line segment) by calling a compiled C++ routine (dsegment.cpp).
- dsphere.m returns the signed distance of one or more points to a sphere.
- dunion.m returns the signed distance to a region that is the union of two regions.
- hmatrix.m computes the mesh size function by interpolation from values specified on a Cartesian grid.
- huniform.m computes a uniform mesh size function.
- meshdemo_nd.m demonstrates the use of the program for higher dimensional problems.
- post_2d.m performs postprocessing for output from DISTMESH_2D.
- protate.m rotates a set of points by a given angle.
- pshift.m shifts a set of points by a given increment.
- r8_epsilon.m returns the R8 arithmetic precision.
- simp_plot_2d.m displays a plot of the triangles that form a mesh in 2D.
- simp_plot_2d_demo.m reads and displays the node and triangle data for each problem.
- simp_plot_3d.m displays a plot of the tetrahedrons that form a mesh in 3D.
- simpqual.m computes the simplex quality of the mesh.
- simpvol.m computes the volume of a simplex.
- surftri.m finds the surface triangles in a tetrahedral mesh.
- timestamp.m prints the current YMDHMS time as a timestamp.
- timestring.m returns the current YMDHMS time as a string.
- triangulation_order3_plot.m writes a PostScript file containing an image of the mesh.
- uniformity.m computes the uniformity of the mesh.
Routines to read and write data to files (borrowed from TABLE_IO) include:
- dtable_data_read.m reads the data of a double precision table file.
- dtable_data_write.m writes the data of a double precision table file.
- dtable_header_read.m reads the header of a double precision table file.
- dtable_header_write.m writes the header of a double precision table file.
- dtable_read.m reads a double precision table file.
- dtable_write.m writes a double precision table file.
- file_column_count.m counts the number of columns in a table file.
- file_row_count.m counts the number of rows in a table file.
- itable_data_read.m reads the data of an integer table file.
- itable_data_write.m writes the data of an integer table file.
- itable_header_read.m reads the header of an integer table file.
- itable_header_write.m writes the header of an integer table file.
- itable_read.m reads an integer table file.
- itable_write.m writes an integer table file.
- s_len_trim.m returns the length of a string to the last nonblank.
- s_word_count.m counts the number of « words » in a string.
———-
DistMesh Function Reference
boundedges
Syntax: | e=boundedges(p,t) |
---|---|
Description: | Find all the boundary edges e in triangular mesh p,t. |
Comments: | Useful for implementation of boundary conditions for PDE solvers. See surftri for 3-D version. |
circumcenter
Syntax: | [pc,r]=circumcenter(p,t) |
---|---|
Description: | Compute the circumcenters pc and the circumradii r for all triangles in the mesh p,t. |
Comments: | Not vectorized. |
dcircle
Syntax: | d=dcircle(p,xc,yc,r) |
---|---|
Description: | Compute signed distance function for circle centered at xc,yc with radius r. |
Comments: |
ddiff
Syntax: | d=ddiff(d1,d2) |
---|---|
Description: | Compute signed distance function for set difference of two regions described by signed distance functions d1,d2. |
Comments: | Not exactly the true signed distance function for the difference, for example around corners. |
dellipse
Syntax: | d=dellipse(p,axes) |
---|---|
Description: | Compute distance from points p to the ellipse centered at the origin with axes=[a,b]. |
Comments: | C++ code, uses LAPACK for eigenvalue problem. |
dellipsoid
Syntax: | d=dellipsoid(p,axes) |
---|---|
Description: | Compute distance from points p to the ellipsoid centered at the origin with axes=[a,b,c]. |
Comments: | C++ code, uses LAPACK for eigenvalue problem. |
dexpr
Syntax: | d=dexpr(p,fin,nit,alpha) |
---|---|
Description: | Compute signed distance function for general implicit expression fin. The parameters nit and alpha have the default values 20 and 0.1. |
Comments: | Requires the Symbolic Toolbox, although easy to rewrite to accept derivatives of fin as inputs. The performance is poor, a simple C implementation makes a big difference. |
dintersect
Syntax: | d=dintersect(d1,d2) |
---|---|
Description: | Compute signed distance function for set intersection of two regions described by signed distance functions d1,d2. |
Comments: | Not exactly the true signed distance function for the intersection, for example around corners. |
distmesh2d
Syntax: | [p,t]=distmesh2d(fd,fh,h0,bbox,pfix,fparams) |
---|---|
Description: | 2-D Mesh Generator. See other documentation for details on usage. |
Comments: |
distmeshnd
Syntax: | [p,t]=distmeshnd(fd,fh,h0,bbox,pfix,fparams) |
---|---|
Description: | 3-D Mesh Generator. See other documentation for details on usage. |
Comments: |
dmatrix
Syntax: | d=dmatrix(p,xx,yy,dd) |
---|---|
Description: | Compute signed distance function by interpolation of the values dd on the Cartesian grid xx,yy. |
Comments: | xx,yy can be created with meshgrid. |
dmatrix3d
Syntax: | d=dmatrix3d(p,xx,yy,zz,dd) |
---|---|
Description: | Compute signed distance function by interpolation of the values dd on the Cartesian grid xx,yy,zz. |
Comments: | xx,yy,zz can be created with ndgrid. |
dpoly
Syntax: | d=dpoly(p,pv) |
---|---|
Description: | Compute signed distance function for polygon with vertices pv. |
Comments: | Uses dsegment and inpolygon. It is usually good to provide pv as fix points to distmesh2d. |
drectangle
Syntax: | d=drectangle(p,x1,x2,y1,y2) |
---|---|
Description: | Compute signed distance function for rectangle with corners (x1,y1), (x2,y1), (x1,y2), (x2,y2). |
Comments: | Incorrect distance to the four corners, see drectangle0 for a true distance function. |
drectangle0
Syntax: | d=drectangle0(p,x1,x2,y1,y2) |
---|---|
Description: | Compute signed distance function for rectangle with corners (x1,y1), (x2,y1), (x1,y2), (x2,y2). |
Comments: | See drectangle for simpler version ignoring corners. |
dsegment
Syntax: | ds=dsegment(p,pv) |
---|---|
Description: | Compute distance from points p to the line segments in pv. |
Comments: | C++ code, used by dpoly. |
dsphere
Syntax: | d=dsphere(p,xc,yc,zc,r) |
---|---|
Description: | Compute signed distance function for sphere centered at xc,yc,zc with radius r. |
Comments: |
dunion
Syntax: | d=dunion(d1,d2) |
---|---|
Description: | Compute signed distance function for set union of two regions described by signed distance functions d1,d2. |
Comments: | Not exactly the true signed distance function for the union, for example around corners. |
fixmesh
Syntax: | [p,t]=fixmesh(p,t) |
---|---|
Description: | Remove duplicated and unused nodes from p and update t correspondingly. Also make all elements orientations equal. |
Comments: |
hmatrix
Syntax: | h=hmatrix(p,xx,yy,dd,hh) |
---|---|
Description: | Compute mesh size function by interpolation of the values hh on the Cartesian grid xx,yy. |
Comments: | xx,yy can be created with meshgrid. The parameter dd is not used, but included to get a syntax consistent with dmatrix. |
hmatrix3d
Syntax: | h=hmatrix3d(p,xx,yy,zz,dd,hh) |
---|---|
Description: | Compute mesh size function by interpolation of the values hh on the Cartesian grid xx,yy,zz. |
Comments: | xx,yy,zz can be created with ndgrid. The parameter dd is not used, but included to get a syntax consistent with dmatrix. |
huniform
Syntax: | h=huniform(p) |
---|---|
Description: | Implements the trivial uniform mesh size function h=1. |
Comments: |
meshdemo2d
Syntax: | meshdemo2d |
---|---|
Description: | Demonstration of distmesh2d. |
Comments: |
meshdemond
Syntax: | meshdemond |
---|---|
Description: | Demonstration of distmeshnd. |
Comments: |
mkt2t
Syntax: | [t2t,t2n]=mkt2t(t) |
---|---|
Description: | Compute element connectivities from element indices. |
Comments: |
protate
Syntax: | p=protate(p,phi) |
---|---|
Description: | Rotate points p the angle phi around origin. |
Comments: |
pshift
Syntax: | p=pshift(p,x0,y0) |
---|---|
Description: | Move points p by (x0,y0). |
Comments: |
simpplot
Syntax: | simpplot(p,t,expr,bcol,icol) |
---|---|
Description: | Plot 2-D or 3-D mesh p,t. The parameters expr, bcol, icol are only used in 3-D and they have default values. |
Comments: |
simpqual
Syntax: | q=simpqual(p,t,type) |
---|---|
Description: | Compute qualities of triangular or tetrahedral elements in the mesh p,t. If type==1 (default) the inradius/outradius expression is used. If type==2 a slightly different expression is used. |
Comments: |
simpvol
Syntax: | v=simpvol(p,t) |
---|---|
Description: | Compute the signed volumes of the simplex elements in the mesh p,t. |
Comments: |
surftri
Syntax: | tri=surftri(p,t) |
---|---|
Description: | Find all the surface triangles tri in tetrahedral mesh p,t. |
Comments: | Used by simpplot. Also useful for implementation of boundary conditions for PDE solvers. See boundedges for 2-D version. |
uniformity
Syntax: | u=uniformity(p,t,fh,fparams) |
---|---|
Description: | Computes « uniformity measure », that is, how close the element sizes in the mesh p,t are to the desired mesh size function fh. |
Comments: |
————
Examples and Tests:
MESHDEMO_2D runs all the 2D tests:
- meshdemo_2d.m demonstrates the use of the program for 2D problems.
- meshdemo_2d_output.txt the output from a run of MESHDEMO_2D.
P01 is the circle:
- p01_demo.m runs the problem.
- p01_fd.m the signed distance function.
- p01_fh.m a uniform mesh density function.
- p01_mesh.png a PNG image of the mesh.
- p01_nodes.txt the mesh nodes of the problem.
- p01_triangles.txt the mesh triangles of the problem.
P02 is the circle with a hole:
- p02_demo.m runs the problem.
- p02_fd.m the signed distance function.
- p02_fh.m a uniform mesh density function.
- p02_mesh.png a PNG image of the mesh.
- p02_nodes.txt the mesh nodes of the problem.
- p02_triangles.txt the mesh triangles of the problem.
P03 is the square with a hole:
- p03_demo.m runs the problem.
- p03_fd.m the signed distance function.
- p03_fh.m a uniform mesh density function.
- p03_mesh.png a PNG image of the mesh.
- p03_nodes.txt the mesh nodes of the problem.
- p03_triangles.txt the mesh triangles of the problem.
P04 is the hexagon with hexagonal hole:
- p04_demo.m runs the problem.
- p04_fd.m the signed distance function.
- p04_fh.m a uniform mesh density function.
- p04_mesh.png a PNG image of the mesh.
- p04_nodes.txt the mesh nodes of the problem.
- p04_triangles.txt the mesh triangles of the problem.
P05 is the horn:
- p05_demo.m runs the problem.
- p05_fd.m the signed distance function.
- p05_fh.m a nonuniform mesh density function.
- p05_mesh.png a PNG image of the mesh.
- p05_nodes.txt the mesh nodes of the problem.
- p05_triangles.txt the mesh triangles of the problem.
P06 is the superellipse:
- p06_demo.m runs the problem.
- p06_fd.m the signed distance function.
- p06_fh.m a nonuniform mesh density function.
- p06_mesh.png a PNG image of the mesh.
- p06_nodes.txt the mesh nodes of the problem.
- p06_triangles.txt the mesh triangles of the problem.
P07 is the bicycle seat:
- p07_demo.m runs the problem.
- p07_fd.m the signed distance function.
- p07_fh.m a uniform mesh density function.
- p07_mesh.png a PNG image of the mesh.
- p07_nodes.txt the mesh nodes of the problem.
- p07_triangles.txt the mesh triangles of the problem.
P08 is the holey pie slice:
- p08_demo.m runs the problem.
- p08_fd.m the signed distance function.
- p08_fh.m a nonuniform mesh density function.
- p08_mesh.png, a PNG image of the mesh.
- p08_nodes.txt the mesh nodes of the problem.
- p08_triangles.txt the mesh triangles of the problem.
P09 is Jeff Borggaard’s square with two hexagonal holes:
- p09_demo.m runs the problem.
- p09_fd.m the signed distance function.
- p09_fh.m a uniform mesh density function.
- p09_mesh.png a PNG image of the mesh.
- p09_nodes.txt the mesh nodes of the problem.
- p09_triangles.txt the mesh triangles of the problem.
P10 is the unit square:
- p10_demo.m runs the problem.
- p10_fd.m the signed distance function.
- p10_fh.m a uniform mesh density function.
- p10_mesh.png a PNG image of the mesh.
- p10_nodes.txt the mesh nodes of the problem.
- p10_triangles.txt the mesh triangles of the problem.
P11 is the L-shaped region:
- p11_demo.m runs the problem.
- p11_fd.m the signed distance function.
- p11_fh.m a uniform mesh density function.
- p11_mesh.png a PNG image of the mesh.
- p11_nodes.txt the mesh nodes of the problem.
- p11_triangles.txt the mesh triangles of the problem.
P12 is the John Shadid’s H-shaped region:
- p12_demo.m runs the problem.
- p12_fd.m the signed distance function.
- p12_fh.m a uniform mesh density function.
- p12_mesh.png a PNG image of the mesh.
- p12_nodes.txt the mesh nodes of the problem.
- p12_triangles.txt the mesh triangles of the problem.
P13 is the Sandia fork:
- p13_demo.m runs the problem.
- p13_fd.m the signed distance function.
- p13_fh.m a uniform mesh density function.
- p13_mesh.png a PNG image of the mesh.
- p13_nodes.txt the mesh nodes of the problem.
- p13_triangles.txt the mesh triangles of the problem.
P14 is Marcus Garvie’s Lake Alpha, with Beta Island:
- p14_demo.m runs the problem.
- p14_fd.m the signed distance function.
- p14_fh.m a nonuniform mesh density function.
- p14_mesh.png a PNG image of the mesh.
- p14_nodes.txt the mesh nodes of the problem.
- p14_triangles.txt the mesh triangles of the problem.
P15 is Sangbum Kim’s forward step region:
- p15_demo.m runs the problem.
- p15_fd.m the signed distance function.
- p15_fh.m a nonuniform mesh density function.
- p15_mesh.png a PNG image of the mesh.
- p15_nodes.txt the mesh nodes of the problem.
- p15_triangles.txt the mesh triangles of the problem.
P16 is Kevin Pond’s elbow, a quarter of a circular annulus:
- p16_demo.m runs the problem.
- p16_fd.m the signed distance function.
- p16_fh.m the mesh density function.
- p16_mesh.png a PNG image of the mesh.
- p16_nodes.txt the mesh nodes of the problem.
- p16_triangles.txt the mesh triangles of the problem.
P17 is a rectangular region with a Reuleaux triangle obstacle.
- p17_demo.m runs the problem.
- p17_fd.m the signed distance function.
- p17_fh.m the mesh density function.
- p17_mesh.png a PNG image of the mesh.
- p17_nodes.txt the mesh nodes of the problem.
- p17_triangles.txt the mesh triangles of the problem.
Commentaires récents