[][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. A path over vertices $A$, $B$, and $C$ is notated $\overrightarrow{\{A,B,C\}}$. This path notation is used to describe rings and faces.

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

ArcKey
ArcOrphan

Orphan view of an arc.

ArcPayload

Arc payload.

ArcView

View of an arc in a graph.

EdgeKey
EdgeOrphan

Orphan view of an edge.

EdgePayload

Edge payload.

EdgeView

View of an edge in a graph.

FaceKey
FaceOrphan

Orphan view of a face.

FacePayload

Face payload.

FaceView

View of a face in a graph.

MeshGraph

Half-edge graph representation of a mesh.

PathView

View of a path in a graph.

RingView

View of a ring in a graph.

VertexKey
VertexOrphan

Orphan view of a vertex.

VertexPayload

Vertex payload.

VertexView

View of a vertex in a graph.

Enums

GraphError
Selector

Topology selector.

Traits

ArcNormal
CompositeEdge
EdgeMidpoint
FaceCentroid
FaceNormal
FacePlane
GraphGeometry

Graph geometry.

PayloadBinding

A view into a graph that is bound to a payload by its key.

Ring
VertexCentroid
VertexNormal

Type Definitions

VertexPosition