Module plexus::graph

Half-edge graph representation of meshes.

This module provides a flexible representation of meshes as a half-edge graph. Half-edges and edges are referred to as arcs and edges, respectively. Meshes can store arbitrary geometric data associated with any topological structure (vertices, arcs, edges, and faces).

Geometry is vertex-based, meaning that geometric operations depend on vertices exposing some notion of positional data. See the geometry module and AsPosition trait. If geometry does not have this property, then spatial operations will not be available.

Representation

A MeshGraph is conceptually composed of vertices, arcs, edges, and faces. The figure below summarizes the connectivity in a MeshGraph.

Arcs are directed and connect vertices. An arc that is directed toward a vertex A is an incoming arc with respect to A. Similarly, an arc directed away from such a vertex is an outgoing arc. Every vertex is associated with exactly one leading arc, which is always an outgoing arc. The vertex toward which an arc is directed is the arc's destination vertex and the other is its source vertex.

Every arc is paired with an opposite arc with an opposing direction. Given an arc from a vertex A to a vertex B, that arc will have an opposite arc from B to A. Such arcs are typically labeled AB and BA. Together, these arcs form an edge, which is not directed. Occassionally, the term "edge" may refer to either an arc or an edge. Edges are typically labeled AB+BA.

Arcs are connected to their neighbors, known as next and previous arcs. When a face is present in the contiguous region formed by a perimeter of vertices and their arcs, the arcs will refer to that face and the face will refer to exactly one of the arcs in the interior. An arc with no associated face is known as a boundary arc. If both of an edge's arcs are boundary arcs, then that edge is a disjoint edge.

Together with vertices and faces, the connectivity of arcs allows for effecient traversals of topology. For example, it becomes trivial to find neighboring topologies, such as the faces that share a given vertex or the neighboring faces of a given face.

MeshGraphs store topological data using associative collections and mesh data is accessed using keys into this storage. Keys are exposed as strongly typed and opaque values, which can be used to refer to a topological structure, such as VertexKey. Topology is typically manipulated using a view, such as VertexView (see below).

Topological Views

MeshGraphs expose views over their topological structures (vertices, arcs, edges, and faces). Views are accessed via keys or iteration and behave similarly to references. They provide the primary API for interacting with a MeshGraph's topology and geometry. There are three types summarized below:

Type	Traversal	Exclusive	Geometry	Topology
Immutable	Yes	No	Immutable	Immutable
Mutable	Yes	Yes	Mutable	Mutable
Orphan	No	No	Mutable	N/A

Immutable and mutable views behave similarly to references. Immutable views cannot mutate a mesh in any way and it is possible to obtain multiple such views at the same time. Mutable views are exclusive, but allow for mutations.

Orphan views are similar to mutable views, but they only have access to the geometry of a single topological structure in a mesh. Because they do not know about other vertices, arcs, etc., an orphan view cannot traverse the topology of a mesh in any way. These views are most useful for modifying the geometry of a mesh and, unlike mutable views, multiple orphan views can be obtained at the same time. Orphan views are mostly used by mutable circulators (iterators).

Immutable and mutable views are both represented by view types, such as FaceView. Orphan views are represented by an oprhan view type, such as OrphanFaceView.

Circulators

Topological views allow for traversals of a mesh's topology. One useful type of traversal uses a circulator, which is a type of iterator that examines the neighbors of a topological structure. For example, the face circulator of a vertex yields all faces that share that vertex in order.

Mutable circulators emit orphan views, not mutable views. This is because it is not possible to instantiate more than one mutable view at a time. If multiple mutable views are needed, it is possible to use an immutable circulator to collect the keys of the target topology and then lookup each mutable view using those keys.

Examples

Generating a mesh from a UV-sphere:

use nalgebra::Point3;
use plexus::graph::MeshGraph;
use plexus::prelude::*;
use plexus::primitive::sphere::UvSphere;

let mut graph = UvSphere::new(16, 16)
    .polygons_with_position()
    .collect::<MeshGraph<Point3<f32>>>();

Extruding a face in a mesh:

use nalgebra::Point3;
use plexus::graph::MeshGraph;
use plexus::prelude::*;
use plexus::primitive::sphere::UvSphere;

let mut graph = UvSphere::new(16, 16)
    .polygons_with_position()
    .collect::<MeshGraph<Point3<f32>>>();
let key = graph.faces().nth(0).unwrap().key(); // Get the key of the first face.
graph.face_mut(key).unwrap().extrude(1.0).unwrap(); // Extrude the face.

Traversing and circulating over a mesh:

use nalgebra::Point2;
use plexus::graph::MeshGraph;
use plexus::prelude::*;
use plexus::primitive::Quad;

let mut graph = MeshGraph::<Point2<f32>>::from_raw_buffers(
    vec![Quad::new(0u32, 1, 2, 3)],
    vec![(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)],
)
.unwrap();
graph.triangulate();

// Traverse an arc and use a circulator to get the faces of a nearby vertex.
let key = graph.arcs().nth(0).unwrap().key();
let mut vertex = graph
    .arc_mut(key)
    .unwrap()
    .into_opposite_arc()
    .into_next_arc()
    .into_destination_vertex();
for mut face in vertex.neighboring_orphan_faces() {
    // `face.geometry` is mutable here.
}

Re-exports

pub use Selector::ByIndex;

pub use Selector::ByKey;

Structs

ArcKey
ArcNeighborhood	Keys for topology forming an arc.
ArcPayload	Arc payload.
ArcView	View of an arc.
EdgeKey
EdgePayload	Edge payload.
EdgeView	View of an edge.
FaceKey
FaceNeighborhood
FacePayload	Face payload.
FaceView	View of a face.
InteriorPathView	View of an interior path.
MeshGraph	Half-edge graph representation of a mesh.
OrphanArcView	Orphan view of an arc.
OrphanEdgeView	Orphan view of an edge.
OrphanFaceView	Orphan view of a face.
OrphanVertexView	Orphan view of a vertex.
VertexKey
VertexPayload	Vertex payload.
VertexView	View of a vertex.

Enums

GraphArity
GraphError
Selector	Topology selector.