[][src]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.

See the user guide for more details and examples.

Representation

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

Half-Edge Graph Figure

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 notated $\overrightarrow{AB}$ and $\overrightarrow{BA}$. Together, these arcs form an edge, which is not directed. An edge and its two arcs are together called a composite edge.

Arcs are connected to their neighbors, known as next and previous arcs. A traversal along a series of arcs is a path. The path formed by traversing from an arc to its next arc and so on is a ring. When a face is present within an ring, the arcs will refer to that face and the face will refer to exactly one of the arcs in the ring (this is the leading arc of the face). An arc with no associated face is known as a boundary arc. If either of an edge's arcs is a boundary arc, then that edge is a boundary edge.

A path that terminates is open and a path that forms a loop is closed. Rings are always closed. Paths may be notated using sequence or set notation and both forms are used to describe rings and faces.

Sequence notation is formed from the ordered sequence of vertices that a path traverses, including the source vertex of the first arc and the destination vertex of the last arc. Set notation is similar, but is implicitly closed and only includes the ordered and unique set of vertices traversed by the path. An open path over vertices $A$, $B$, and $C$ is notated as a sequence $\overrightarrow{(A,B,C)}$. A closed path over vertices $A$, $B$, and $C$ includes the arc $\overrightarrow{CA}$ and is notated as a sequence $\overrightarrow{(A,B,C,A)}$ or a set $\overrightarrow{\{A,B,C\}}$.

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.

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:

TypeTraversalExclusiveGeometryTopology
ImmutableYesNoImmutableImmutable
MutableYesYesMutableMutable
OrphanNoNoMutableN/A

Immutable and mutable views behave similarly to references: immutable views cannot mutate a graph and are not exclusive while mutable views may mutate both the geometry and topology of a graph but are exclusive.

Orphan views are similar to mutable views in that they may mutate the geometry of a graph, but they do not have access to the topology of a graph. Because they do not know about other vertices, arcs, etc., an orphan view cannot traverse a graph in any way. These views are most useful for modifying the geometry of a graph and, unlike mutable views, they are not exclusive. Iterators over topological structures in a graph sometimes emit orphan views.

Examples

Generating a graph from a $uv$-sphere:

use decorum::N64;
use nalgebra::Point3;
use plexus::graph::MeshGraph;
use plexus::prelude::*;
use plexus::primitive::generate::Position;
use plexus::primitive::sphere::UvSphere;

let mut graph = UvSphere::default()
    .polygons::<Position<Point3<N64>>>()
    .collect::<MeshGraph<Point3<N64>>>();

Extruding a face in a graph:

use decorum::N64;
use nalgebra::Point3;
use plexus::graph::MeshGraph;
use plexus::prelude::*;
use plexus::primitive::generate::Position;
use plexus::primitive::sphere::UvSphere;

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

Traversing and circulating over a graph:

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

let mut graph = MeshGraph::<Point2<f64>>::from_raw_buffers(
    vec![Tetragon::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_face_orphans() {
    // `face.geometry` is mutable here.
}

Re-exports

pub use Selector::ByIndex;
pub use Selector::ByKey;

Structs

Arc

Graph arc.

ArcKey
ArcOrphan

Orphan view of an arc.

ArcView

View of an arc in a graph.

Edge

Graph edge.

EdgeKey
EdgeOrphan

Orphan view of an edge.

EdgeView

View of an edge in a graph.

Face

Graph face.

FaceKey
FaceOrphan

Orphan view of a face.

FaceView

View of a face in a graph.

MeshGraph

Half-edge graph representation of a mesh.

Path

View of a path in a graph.

Ring

View of a ring in a graph.

Vertex

Graph vertex.

VertexKey
VertexOrphan

Orphan view of a vertex.

VertexView

View of a vertex in a graph.

Enums

GraphError
Selector

Topology selector.

Traits

ArcNormal
EdgeMidpoint
Edgoid

Edge-like structure. Abstracts arcs and edges.

FaceCentroid
FaceNormal
FacePlane
GraphGeometry

Graph geometry.

Rebind
Ringoid

Ring-like structure. Abstracts faces and rings.

VertexCentroid
VertexNormal

Type Definitions

VertexPosition