# [−][src]Module plexus::graph

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.

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.

`MeshGraph`

s 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

`MeshGraph`

s 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 circumscribe<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(ByKey(a), ByKey(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. }

## Re-exports

`pub use Selector::ByIndex;` |

`pub use Selector::ByKey;` |

## Structs

ArcKey | Arc key. |

ArcOrphan | Orphan view of an arc entity. |

ArcView | View of an arc entity. |

EdgeKey | Edge key. |

EdgeOrphan | Orphan view of an edge entity. |

EdgeView | View of an edge entity. |

FaceKey | Face key. |

FaceOrphan | Orphan view of a face entity. |

FaceView | View of a face entity. |

MeshGraph | Half-edge graph representation of a polygonal mesh. |

Path | Non-intersecting path. |

Ring | Closed path formed by adjacent arcs. |

VertexKey | Vertex key. |

VertexOrphan | Orphan view of a vertex entity. |

VertexView | View of a vertex entity. |

## Enums

GraphError | Errors concerning |

GraphKey | |

Selector | Entity selector. |

## Traits

ArcNormal | |

ClosedView | |

EdgeMidpoint | |

EntityData | |

FaceCentroid | |

FaceNormal | |

FacePlane | |

GraphData | Graph data. |

Rebind | |

ToArc | |

ToRing | |

VertexCentroid | |

VertexNormal |

## Type Definitions

VertexPosition |