# [−][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`

.

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.

`MeshGraph`

s 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

`MeshGraph`

s 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 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. |

PathView | View of a path in a graph. |

RingView | 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 | |

CompositeEdge | |

EdgeMidpoint | |

Entry | A key paired with storage in a graph. |

FaceCentroid | |

FaceNormal | |

FacePlane | |

GraphGeometry | Graph geometry. |

Ring | |

VertexCentroid | |

VertexNormal |

## Type Definitions

VertexPosition |