The Central Idea

A mesh is a discrete geometric representation of a domain.

Instead of working with one complicated continuous region, we represent it as many simpler connected elements:

\[ \boxed{ \text{domain} \longrightarrow \text{vertices, edges, faces, and elements} }. \]

The mesh approximates or exactly respects the geometry while creating a structure suitable for computation.

Mesh Components

In a two-dimensional mesh, the main components are:

In three dimensions, additional volumetric elements are required.

Connectivity Matters as Much as Coordinates

A mesh is not merely a list of points.

It must also record which points are connected.

For a triangular element with vertex indices

\[ (i,j,k), \]

the mesh stores the three vertices

\[ P_i,\qquad P_j,\qquad P_k \]

together as one face.

Triangular Meshes

A triangular mesh divides a two-dimensional region into triangles.

Neighboring triangles meet along shared edges or vertices, and their interiors do not overlap.

Triangular meshes are especially common because arbitrary polygonal domains can be triangulated flexibly.

Quadrilateral Meshes

A quadrilateral mesh uses four-sided elements.

Quadrilateral elements can be efficient for some numerical methods and can align naturally with rectangular or layered geometry.

However, generating high-quality quadrilateral meshes over arbitrary domains can be more difficult than generating triangular meshes.

Mixed Meshes

A mesh does not always need to use one element type exclusively.

A mixed mesh may contain:

This allows the mesh to adapt to complicated boundaries or changes in local structure.

Structured Meshes

A structured mesh has a regular connectivity pattern.

A rectangular grid is the simplest example.

Vertices can be indexed by row and column:

\[ P_{i,j}. \]

Neighbor relationships follow predictable index patterns.

Advantages of Structured Meshes

Structured meshes offer:

Limitations of Structured Meshes

Regular connectivity can make structured meshes difficult to fit around:

For such domains, an unstructured mesh is often more flexible.

Unstructured Meshes

An unstructured mesh allows irregular connectivity.

Vertices may have different numbers of neighbors, and element sizes and shapes can vary throughout the domain.

Triangular Delaunay meshes are a common example.

Why Unstructured Meshes Are Useful

Unstructured meshes adapt naturally to:

Mesh Generation Begins with a Domain

A mesh generator needs a description of the region to be meshed.

This may include:

Boundary-Conforming Meshes

A mesh is boundary conforming when its boundary edges follow the intended geometric boundary.

If a polygon edge is a required boundary segment, the mesh should represent that segment through one or more mesh edges.

Boundary conformity is essential when the geometry itself carries physical or topological meaning.

Constrained Triangulation as a Mesh Foundation

A planar domain with required segments can be triangulated using a constrained triangulation.

Required boundaries remain present while additional edges divide the region into triangles.

This provides a natural starting point for triangular mesh generation.

Delaunay-Based Mesh Generation

Delaunay triangulation is widely used as a foundation for mesh generation.

It tends to avoid unnecessarily small angles compared with many alternative triangulations.

The resulting mesh can then be refined where additional resolution or quality is required.

Element Size

A mesh element has a characteristic size.

For a triangle, possible measures include:

The chosen measure depends on the application.

Uniform Meshes

A uniform mesh uses approximately the same element size throughout the domain.

This can be appropriate when:

Nonuniform Meshes

A nonuniform mesh varies element size across the domain.

Small elements may be concentrated near:

Size Fields

A mesh generator may use a desired size function

\[ h(x,y) \]

that specifies the target local element scale.

Smaller values of \(h\) request finer mesh resolution.

Larger values permit coarser elements.

Why Element Shape Matters

Two triangles can have similar area but very different shapes.

Extremely thin or flattened elements can cause problems in:

Minimum Angle

One simple quality measure for a triangle is its smallest interior angle:

\[ \theta_{\min}. \]

Very small values indicate a skinny triangle.

A mesh generator may therefore impose a requirement such as

\[ \boxed{ \theta_{\min}\ge\theta_0 } \]

for some quality threshold \(\theta_0\).

Aspect Ratio

Another quality measure compares characteristic lengths.

An element with one dimension much larger than another has a large aspect ratio.

Whether this is undesirable depends on the application. Some simulations deliberately use elongated elements aligned with directional behavior.

Inradius and Circumradius

For a triangle, let

\[ r \]

be the inradius and

\[ R \]

the circumradius.

The ratio

\[ \frac{R}{r} \]

grows as the triangle becomes more distorted.

Equilateral Triangles as an Ideal

An equilateral triangle has:

Many isotropic triangular mesh-quality measures therefore treat the equilateral triangle as an ideal reference shape.

Mesh Refinement

Refinement replaces coarse mesh structure with smaller elements.

For example, a triangle may be subdivided by introducing:

Steiner Points

A Steiner point is a new vertex added by the mesh generator rather than supplied as part of the original geometry.

Steiner points allow the generator to improve:

Simple Triangle Subdivision

Suppose triangle \(ABC\) has midpoint

\[ M=\frac{A+B}{2} \]

on edge \(AB\).

Connecting \(M\) to \(C\) replaces the original triangle with

\[ \triangle AMC \]

and

\[ \triangle MBC. \]

Red Refinement

One common refinement pattern introduces the midpoint of every triangle edge.

Connecting those three midpoints divides one triangle into four smaller triangles.

This is sometimes called a red-refinement pattern.

Local Refinement Creates Transition Problems

If only one triangle is subdivided while its neighbor is not, a new midpoint may appear on their shared edge.

If the neighboring triangle does not recognize that point, the mesh can contain a hanging node.

Some numerical methods allow hanging nodes; others require further refinement to restore conformity.

Conforming Meshes

In a conforming mesh, neighboring elements meet face-to-face.

In two dimensions, two triangles may share:

One triangle edge should not terminate in the middle of another edge unless the representation explicitly permits nonconforming structure.

Adaptive Mesh Refinement

Adaptive refinement adds resolution only where it is needed.

A computational model may estimate local error and refine elements whose error exceeds a threshold.

This concentrates computational effort where it has the greatest value.

An Adaptive Refinement Cycle

  1. Solve or evaluate the current model.
  2. Estimate error or geometric inadequacy.
  3. Mark elements for refinement.
  4. Subdivide or retriangulate those regions.
  5. Restore mesh conformity and quality.
  6. Repeat as needed.

Adaptive Coarsening

Refinement adds elements.

Coarsening removes unnecessary resolution.

If a region no longer requires a fine mesh, several small elements may be replaced by fewer larger elements, provided accuracy and topology remain acceptable.

Delaunay Refinement

Delaunay refinement combines Delaunay triangulation with the insertion of additional points.

A typical process identifies triangles that violate size or quality requirements, inserts a new point, and retriangulates locally.

This can produce high-quality unstructured triangular meshes.

Circumcenter Insertion

One Delaunay-refinement strategy inserts the circumcenter of a poor-quality triangle.

This tends to break up a large or badly shaped region and changes nearby Delaunay connectivity.

Boundary constraints require additional care so that refinement does not violate required segments.

Boundary Encroachment

A proposed refinement point can interfere with a constrained boundary segment.

Mesh-generation algorithms often test whether a boundary segment is encroached before inserting interior refinement points.

If necessary, the boundary segment is split first.

Small Input Angles Are Difficult

Very small angles in the input geometry can force skinny elements near the boundary.

This creates a fundamental tension:

\[ \boxed{ \text{preserve geometry} \quad\text{versus}\quad \text{improve element shape} }. \]

A mesh generator cannot always satisfy an arbitrarily strong quality requirement without modifying the domain.

Mesh Smoothing

Instead of changing connectivity, a mesh can sometimes be improved by moving vertices.

Mesh smoothing adjusts vertex locations while preserving the overall topology and required boundaries.

Laplacian Smoothing

A simple smoothing method moves an interior vertex toward the average of its neighboring vertices.

If the neighbors are

\[ P_1,P_2,\ldots,P_k, \]

the average position is

\[ \boxed{ \bar P= \frac{1}{k} \sum_{i=1}^{k}P_i }. \]

The vertex may be moved toward or to this location.

Smoothing Can Create Invalid Elements

Moving a vertex carelessly can invert a neighboring triangle.

An element whose orientation changes sign has crossed through a degenerate zero-area state.

Therefore, smoothing should verify element validity after proposed movement.

Edge Flipping as Mesh Optimization

In a convex quadrilateral formed by two neighboring triangles, one diagonal can be replaced by the other.

This edge flip changes connectivity without adding or removing vertices.

Edge flipping can improve Delaunay quality or other local mesh criteria.

Topological Operations versus Geometric Operations

Mesh improvement can change:

Sophisticated mesh generators combine all three.

Three-Dimensional Meshes

In three dimensions, the domain is divided into volumetric elements.

Common element types include:

Tetrahedral Meshes

A tetrahedron is the three-dimensional analogue of a triangle.

Four noncoplanar points determine a tetrahedron.

Tetrahedral meshes are flexible for complicated three-dimensional boundaries and are widely used in simulation.

Hexahedral Meshes

Hexahedral elements resemble deformed boxes.

They can offer strong numerical performance for some problems, but generating a high-quality all-hexahedral mesh of arbitrary geometry is challenging.

Surface Meshes

Sometimes only a surface needs to be meshed.

A curved surface may be approximated by triangular or quadrilateral faces.

As the elements become smaller, the piecewise-flat mesh can approximate the underlying smooth surface more closely.

Geometric Approximation Error

A mesh can introduce geometric error when curved boundaries are replaced by straight edges or planar faces.

Refinement near curvature reduces this discrepancy.

Thus mesh density may be driven by geometry even before any physical model is considered.

Mesh Resolution versus Computational Cost

Finer meshes usually provide more geometric and numerical detail.

But they also increase:

Mesh design is therefore an optimization problem.

Mesh Independence

In numerical simulation, one often checks whether results stabilize as the mesh is refined.

If important outputs change very little between sufficiently fine meshes, the computation may be considered approximately mesh independent.

This is a numerical validation concept, not a guarantee of physical model correctness.

Mesh Data Structures

A useful mesh representation may store:

Indexed Triangle Meshes

Suppose the vertex array is

\[ P_0,P_1,\ldots,P_m. \]

A triangle may be represented by indices

\[ (2,7,5). \]

This means the triangle uses vertices

\[ P_2,\qquad P_7,\qquad P_5. \]

Shared vertices need only be stored once.

Consistent Element Orientation

In a planar triangular mesh, vertices are often listed consistently counterclockwise.

For triangle \(ABC\),

\[ \operatorname{orient}(A,B,C)>0 \]

then indicates the expected orientation.

A negative sign may reveal an inverted element.

Mesh Adjacency

Two triangular elements are adjacent when they share an edge.

Adjacency is useful for:

Boundary Labels

Mesh boundaries may carry different meanings.

One portion may represent:

A mesh often stores labels so later computations can distinguish these conditions.

Mesh Generation in GIS

Spatial modeling may use meshes to represent:

Triangulated irregular networks are a classic terrain representation.

Triangulated Irregular Networks

A triangulated irregular network, or TIN, represents a surface using irregularly spaced sample points connected into triangles.

Dense triangles can be used where terrain changes rapidly, while sparse triangles can represent flatter regions.

Mesh Generation in Computer Graphics

Graphics meshes represent object surfaces using connected polygons, especially triangles.

Mesh generation may arise from:

Mesh Generation in Engineering

Engineering analysis often begins with a geometric model and converts it into a finite mesh.

The mesh becomes the discrete computational domain for approximating stresses, temperatures, fluid flow, electromagnetic fields, and other quantities.

Numerical Robustness

Mesh generation combines many geometric predicates:

Small numerical errors can therefore affect connectivity and validity.

Near-Degenerate Elements

A triangle with nearly collinear vertices has very small area:

\[ \left| \operatorname{orient}(A,B,C) \right| \approx0. \]

Such elements can be geometrically fragile and numerically undesirable.

Inverted Elements

If a triangle is expected to be counterclockwise but satisfies

\[ \operatorname{orient}(A,B,C)<0, \]

the element is inverted relative to the intended orientation.

Inversion often indicates invalid smoothing, deformation, or connectivity.

Duplicate Vertices

Duplicate coordinates can create:

Deduplication is therefore a common preprocessing step.

Nonmanifold Mesh Structure

In an ordinary two-dimensional manifold mesh, an interior edge is shared by exactly two elements.

If three or more triangles share the same edge, the structure is nonmanifold.

Whether that is invalid depends on the application, but most standard surface and finite-element meshes expect manifold connectivity.

Verifying a Two-Dimensional Mesh

A candidate mesh should be checked for:

Area Verification

If a bounded domain is completely meshed by nonoverlapping triangles, then

\[ \boxed{ \operatorname{Area}(D) = \sum_i \operatorname{Area}(T_i) }. \]

An area mismatch is strong evidence of missing or overlapping elements.

Common Error: Equating More Elements with a Better Mesh

A finer mesh is not automatically better.

Poorly shaped elements can remain poor even when there are many of them.

Mesh quality depends on shape, size distribution, boundary fidelity, and the needs of the computation.

Common Error: Refining Everywhere

Uniform refinement can waste computational resources in regions that do not require additional resolution.

Adaptive refinement targets local geometric or numerical need instead.

Common Error: Ignoring Boundary Constraints

An otherwise attractive Delaunay triangulation can be unacceptable if it fails to preserve required boundaries.

Constrained geometry must be treated as part of the mesh specification.

Common Error: Allowing Hanging Nodes Accidentally

Local refinement can create a vertex in the middle of a neighboring element's edge.

If nonconforming structure is not supported, additional refinement is needed to restore face-to-face connectivity.

Common Error: Moving Boundary Vertices Freely during Smoothing

A boundary vertex may represent important geometry.

Moving it without constraint can distort the intended domain.

Boundary smoothing should preserve or project vertices back onto the underlying geometric boundary.

Common Error: Ignoring Inverted Elements after Vertex Motion

A smoothing step that improves one local measure can cause a neighboring triangle to invert.

Candidate vertex movement should therefore be followed by validity checks.

Common Error: Treating Every Application as Isotropic

Some problems have strong directional behavior.

In such cases, elongated elements aligned with the dominant direction may be more efficient than nearly equilateral elements.

The appropriate quality metric depends on the intended computation.

A Reliable Procedure for Basic Triangular Mesh Generation

  1. Validate and deduplicate the domain geometry.
  2. Identify outer boundaries, holes, and internal constraints.
  3. Choose a target size or size field.
  4. Construct a constrained triangulation.
  5. Inspect element size and quality.
  6. Insert Steiner points where refinement is needed.
  7. Retriangulate locally.
  8. Apply smoothing or edge flips when useful.
  9. Verify boundary conformity, orientation, adjacency, and coverage.

A Reliable Procedure for Adaptive Meshing

  1. Generate an initial valid mesh.
  2. Compute or estimate local error.
  3. Mark elements requiring refinement.
  4. Refine the marked region.
  5. Restore conformity where required.
  6. Improve poor element shapes.
  7. Recompute the model or error estimate.
  8. Repeat until the stopping criterion is satisfied.

A Reliable Procedure for Mesh Verification

  1. Check every element for nonzero measure.
  2. Check orientation consistency.
  3. Check that edges do not cross improperly.
  4. Check interior and boundary adjacency.
  5. Check required boundary segments.
  6. Check for unintended holes or overlaps.
  7. Compare total element measure with the domain measure when practical.
  8. Evaluate quality statistics before numerical use.

Practice 1: Mesh Components

Name the three basic kinds of objects in a two-dimensional triangular mesh.

Practice 2: Structured or Unstructured?

A rectangular grid has vertices indexed by row and column with predictable neighbor relationships. Is it structured or unstructured?

Practice 3: Element Orientation

A triangular mesh is intended to use counterclockwise vertex order. What sign should

\[ \operatorname{orient}(A,B,C) \]

have for a valid element?

Practice 4: Refinement

What is a Steiner point?

Practice 5: Hanging Node

A midpoint is inserted on one triangle's edge, but the neighboring triangle is left unchanged. What mesh issue may result?

Practice 6: Triangle Quality

Which is generally more desirable for an isotropic mesh: a triangle with angles

\[ 60^\circ,\ 60^\circ,\ 60^\circ \]

or one with angles

\[ 2^\circ,\ 89^\circ,\ 89^\circ? \]

Practice 7: Adaptive Refinement

What is the main computational advantage of refining only where error or geometric detail requires it?

Practice 8: Boundary Conformity

If a river segment must remain explicitly represented in a GIS mesh, what kind of triangulation concept is useful?

Practice 9: Inverted Element

A triangle expected to be counterclockwise changes from positive orientation to negative orientation after smoothing. What happened?

Practice 10: Why Mesh?

Give two reasons for converting a continuous geometric domain into a mesh.

Practice Answers

Practice 1

The three basic components are

\[ \boxed{ \text{vertices, edges, and triangular elements} }. \]

Practice 2

The regular indexing and predictable connectivity make it

\[ \boxed{\text{structured}}. \]

Practice 3

For counterclockwise ordering,

\[ \boxed{ \operatorname{orient}(A,B,C)>0 }. \]

Practice 4

A Steiner point is a new mesh vertex introduced by the algorithm rather than supplied in the original geometry.

Practice 5

The midpoint can become

\[ \boxed{\text{a hanging node}}. \]

Practice 6

For an isotropic triangular mesh, the equilateral triangle is generally preferable:

\[ \boxed{ 60^\circ,\ 60^\circ,\ 60^\circ }. \]

Practice 7

Adaptive refinement concentrates computational resources where they are needed instead of increasing resolution everywhere.

Practice 8

A

\[ \boxed{\text{constrained triangulation}} \]

can preserve the required river segment.

Practice 9

The element became

\[ \boxed{\text{inverted}}. \]

Practice 10

Valid answers include:

What to Remember

Mesh generation converts continuous geometry into a discrete connected structure suitable for computation.

The broader computational principle is that a good discrete representation preserves the important structure of the continuous problem while reducing it to manageable local pieces.

Where We Go Next

Mesh generation creates discrete geometric structure. The next lesson asks how computational systems use such structure to determine whether moving or stationary objects contact, overlap, or pass through one another.

Collision Detection develops broad-phase and narrow-phase tests, bounding volumes, intersection predicates, and geometric strategies for detecting contact efficiently.