DDG Mesh | Guowei Lu

What is a Mesh?

A mesh is a crucial structure in computational geometry and computer graphics, widely used to represent and analyze shapes, surfaces, and volumes. To fully understand a mesh, let’s explore its components and related concepts in detail.

Convex Set

A subset \(S \subset \mathbb{R}^n\) is convex if, for any two points \(p, q \in S\), the line segment connecting \(p\) and \(q\) lies entirely within \(S\).

Convex Hull: The convex hull \(\text{conv}(S)\) of a set \(S\) is the smallest convex set containing \(S\).

Simplex

A simplex is a fundamental building block of meshes, defined as the convex hull of \(k+1\) affinely independent points. Examples include:

0-simplex: A point.
1-simplex: A line segment.
2-simplex: A triangle.
3-simplex: A tetrahedron.

Affine Independence

Points \(p_1, p_2, \dots, p_k\) are affinely independent if the vectors \(p_2 - p_1, p_3 - p_1, \dots, p_k - p_1\) are linearly independent.

Barycentric Coordinates

Any point \(p\) inside a simplex can be expressed as a convex combination of its vertices:

\[p = \sum_{i=0}^k t_i v_i, \quad \text{where } \sum_{i=0}^k t_i = 1 \text{ and } t_i \geq 0.\]

The coefficients \(t_i\) are the barycentric coordinates of \(p\).

Standard \(n\)-Simplex

The standard \(n\)-simplex in \(\mathbb{R}^{n+1}\) is:

\[\sigma = (x_0, x_1, \dots, x_n) \in \mathbb{R}^{n+1} \mid \sum_{i=0}^n x_i = 1, \ x_i \geq 0 \ \forall i.\]

Simplicial Complex

A simplicial complex is a collection of simplices that satisfies the following rules:

The intersection of any two simplices is either empty or another simplex in the complex.
Every face of a simplex in the complex is also part of the complex.

Face of a Simplex

A face is any simplex formed by a subset of the vertices of a given simplex.

Abstract Simplicial Complex

This describes the combinatorial relationships between vertices and simplices without their geometric embedding. For example, an undirected graph \(G = (V, E)\) can be interpreted as an abstract simplicial complex:

0-simplices: Vertices.
1-simplices: Edges.

Applications

Simplicial complexes and meshes have diverse applications, including:

Topological Data Analysis (TDA): Examining data connectivity using techniques like persistent homology to study features such as connected components and holes across scales.
Material Science: Investigating medium-range order in materials like glass.
Neuroscience: Analyzing structural and functional networks in the brain.
Computer Graphics: Representing 3D objects for rendering and simulations.

Vertices, Edges, and Faces

For simplicial complexes:

Vertices: Points (0-simplices).
Edges: Line segments (1-simplices).
Faces: Triangles (2-simplices).

For triangle meshes, these elements are often represented as:

\(V\): The set of vertices.
\(E\): The set of edges.
\(F\): The set of faces.

Anatomy of a Simplicial Complex

Closure: smallest simplicial complex containing a given set of simplices
Star: union of simplices containing a given subset of simplices
Link: closure of the star minus the star of the closure

Oriented Simplicial Complex

An oriented simplicial complex assigns an ordering to the vertices of each simplex:

For a 1-simplex (edge), orientation specifies the direction (e.g., \(a \to b\) vs. \(b \to a\)).
For a 2-simplex (triangle), orientation depends on the vertex order (e.g., \((a, b, c)\) vs. \((b, c, a)\)).

Relative Orientation

Two oriented simplices share the same relative orientation if their common face has opposite orientations when viewed from each simplex.

Simplicial Complex and Manifold

A simplicial complex is a mathematical structure that represents objects by dividing them into simple building blocks like vertices, edges, triangles, and higher-dimensional simplices. It is widely used in computational geometry to model surfaces and other topological spaces.

A manifold is a topological space that locally resembles Euclidean space. For a 2-manifold, this means every point has a neighborhood that looks like a 2D disk. In the context of simplicial complexes, a simplicial surface is a 2-dimensional simplicial complex that satisfies the following properties:

Local Disk Structure: The link of every vertex forms a single loop of edges, and the star of every vertex forms a combinatorial disk made of triangles.
Orientability: The surface must have a consistent orientation across all its simplices, meaning you can define a continuous “normal” direction everywhere.

Simplicial Complex and Nonmanifold Configurations

Not all simplicial complexes are manifolds. Nonmanifold configurations violate the local disk property, such as:

An edge shared by three or more triangles.
A vertex where multiple disconnected “cones” of simplices meet.

Such configurations are considered nonmanifold, as their local neighborhoods do not resemble Euclidean space.

The Möbius Band: A Special Case

The Möbius band is an example of a 2-manifold that challenges our intuition.

Manifold Property: The Möbius band is a 2-manifold because every point has a neighborhood that locally looks like a 2D disk. If you zoom in on any part of the Möbius band, it behaves like a typical 2D surface.
Non-Orientability: Unlike a standard simplicial surface, the Möbius band is non-orientable. If you move along the surface in a continuous loop, the “normal” direction flips. This makes it impossible to define a consistent orientation across the entire band.
Simplicial Representation: While you can represent the Möbius band using a simplicial complex, it would not qualify as a simplicial surface under the usual assumption of orientability.

By understanding meshes and their foundational components, we gain deeper insights into their structure and practical uses, from analyzing data to simulating physical systems and rendering realistic virtual environments.