Module plexus::graph

Expand description

Half-edge graph representation of polygonal meshes.

This module provides a flexible representation of polygonal meshes as a half-edge graph. Plexus refers to Half-edges and edges as arcs and edges, respectively. Graphs can store arbitrary data associated with any topological entity (vertices, arcs, edges, and faces).

Graph APIs support geometric operations if vertex data implements the AsPosition trait.

See the user guide for more details and examples.

Representation

A MeshGraph is fundamentally composed of four entities: vertices, arcs, edges, and faces. The figure below summarizes the connectivity of these entities.

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 adjacent arcs, 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. For example, it becomes trivial to find adjacent entities, such as the faces that share a given vertex or the adjacent faces of a given face.

MeshGraphs store entities using associative data structures with strongly typed and opaque keys. These keys are used to refer entities in a graph. Note that paths and rings are not entities and are not explicitly stored in graphs.

Views

MeshGraphs expose views over their entities (vertices, arcs, edges, and faces). Views are a type of smart pointer and bind entity storage with a key for a specific entity. They extend entities with rich behaviors and expose their associated data via get and get_mut functions.

Views provide the primary API for interacting with a MeshGraph’s topology and data. There are three types of views summarized below:

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

Immutable and mutable views behave similarly to Rust’s & and &mut references: immutable views cannot mutate a graph and are not exclusive while mutable views may mutate both the data and topology of a graph but are exclusive.

Orphan views (simply referred to as orphans in APIs) may mutate the data of a graph, but they cannot access the topology of a graph and cannot traverse a graph in any way. This is only useful for modifying the data in a graph, but unlike mutable views, orphan views are not exclusive.

Views perform interior reborrows, which reborrow the reference to storage to construct other views. Immutable reborrows can be performed explicitly using the conversions described below:

Function	Receiver	Borrow	Output
`to_ref`	`&self`	`&_`	Immutable
`into_ref`	`self`	`&*_`	Immutable

It is not possible to explicitly perform a mutable interior reborrow. Such a reborrow could invalidate the source view by performing a topological mutation. Mutable reborrows are performed beneath safe APIs, such as those exposing iterators over orphan views.

Geometric Traits

The GraphData trait is used to specify the types of data stored in entities in a MeshGraph. If the Vertex data implements the AsPosition trait and the positional data implements the appropriate geometric traits, then geometric APIs like split_at_midpoint and poke_with_offset can be used. Abstracting this in generic code involves various traits from theon.

This module provides geometric traits that describe supported geometric operations without the need to express complicated relationships between types representing a Euclidean space. These traits express the geometric capabilites of GraphData. For example, the following generic function requires EdgeMidpoint and subdivides faces in a graph by splitting edges at their midpoints:

use plexus::geometry::AsPositionMut;
use plexus::graph::{EdgeMidpoint, FaceView, GraphData, MeshGraph};
use plexus::prelude::*;
use smallvec::SmallVec;

// Requires `EdgeMidpoint` for `split_at_midpoint`.
pub fn ambo<G>(face: FaceView<&mut MeshGraph<G>>) -> FaceView<&mut MeshGraph<G>>
where
    G: EdgeMidpoint + GraphData,
    G::Vertex: AsPositionMut,
{
    let arity = face.arity();
    let mut arc = face.into_arc();
    let mut splits = SmallVec::<[_; 4]>::with_capacity(arity);
    for _ in 0..arity {
        let vertex = arc.split_at_midpoint();
        splits.push(vertex.key());
        arc = vertex.into_outgoing_arc().into_next_arc();
    }
    let mut face = arc.into_face().unwrap();
    for (a, b) in splits.into_iter().perimeter() {
        face = face.split(a, b).unwrap().into_face().unwrap();
    }
    face
}

Examples

Generating a MeshGraph from a $uv$-sphere:

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

type E3 = Point3<R64>;

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

Extruding a face in a MeshGraph:

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

type E3 = Point3<R64>;

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

Traversing and circulating over a MeshGraph:

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.adjacent_face_orphans() {
    // `face.get_mut()` provides a mutable reference to face data.
}