olson-sean-k / plexus Goto Github PK

Writing to the geometry of a mesh via an orphan view from an iterator does not appear to work correctly. This involves unsafe code in the iterator, which transmutes a reference to coerce a lifetime, and is probably a good place to look first. Here's an example:

let color = Color::yellow(); // `Copy`.
for mut face in mesh.faces_mut() {
    face.geometry = color;
}
for face in mesh.faces() {
    // This assertion fails and displays nonsense values.
    assert_eq!(color, face.geometry);
}

This looks to be UB.

eccebcc disables testing on the beta Rust toolchain due to dynamic linking errors when running doctests. The lapack feature from Theon uses Intel MKL on Linux and for some reason the library fails to load while executing doctests. See this issue.

CI should test against the beta toolchain. Once this issue is resolved, include the beta toolchain in the test matrix again (revert eccebcc).

It would be useful to be able to create subgraphs that restrict all traversals and manipulations to only part of the mesh. Is there such a functionality currently (cannot seem to find something like this in the docs).

(PS I'm sorry for abusing the issues page to ask for help using plexus. If you prefer I can send emails.)

Currently, there is no way to save or restore Meshes. Serialization support via serde has been completed (not merged at this time), but is questionable and lacks interoperability and domain-specific features. Support for the PLY format should allow Meshes to be persisted to disk and shared with other software.

PLY allows meshes to associate arbitrary properties with their elements. This works well with Plexus' notion of arbitrary geometry. While topology (i.e., elements) will always have the same structure in Plexus, geometry (i.e., properties) can implement optional traits that allow for expression in the PLY format.

The mutation module exposes topological mutations that operate in either immediate or batch modes. The mode determines the way that consistency errors are handled. Batch operations defer certain errors until all mutations are committed, at which point the mesh is checked for consistency.

Some mutations exposed by topological views should really be batch operations. For example, FaceMut::join temporarily removes faces, which could cause intermediate inconsistency but should not necessarily fail, because ultimately the output is consistent. FaceMut cannot use a batch mutation though, because that currently requires ownership of the Mesh.

Is there a way to reconcile this? Is it possible to introduce a third variant of views that take ownership of a Mesh? That could be a bit awkward. Consider:

let face = mesh.into_face(source).unwrap().join(destination).unwrap();
let mesh = face.into_mesh();

Should these kinds of operations be exposed elsewhere (instead of via views)?

let mesh = mesh.join_faces(source, destination).unwrap();

Since you already support three other linear algebra crates ... :)
https://github.com/termhn/ultraviolet

Some graph mutations can be defined in a purely topological way that is still very useful, but currently these operations depend on geometry. For example, face triangulation and edge splitting need not depend on geometry.

Separate these operations into geometric and non-geometric variants. Edge splitting could be provided by split, split_with, and split_at_midpoint functions, where split and split_with either use default geometry (if defined) or geometry provided by a function and split_at_midpoint computes the positional midpoint (as is already done today). Similarly, face triangulation could be provided by triangulate and triangulate_at_centroid functions, where triangulate is implemented simply in terms of bisect.

Perhaps mesh consistency should affect the mesh API. Today, mutations dance around operations that may or may not be safe due to the consistency of a mesh, such as implicitly or explicitly unwrapping connected topology or using circulators. Topological views provide a "raw" API that is available to the graph module, but code must "just know" when to use this instead of the user-facing API.

New types (maybe via additional type parameters) could differentiate consistent and (potentially) inconsistent meshes. Users would only ever see friendly consistent meshes and their related types. Internally, mutation code would be prevented from performing potentially unsound operations and, at the very least, would be forced to explicitly handle Results and Options.

Mutations would need to be based entirely on ownership or mem::replace (to support &mut), because a consistent mesh and an inconsistent mesh would be entirely different types and mutations would need to transition between them. It should be relatively inexpensive to move (shallow copy) a Mesh, because it consists of only three HashMaps. If it becomes too expensive, then that data can be boxed and placed into a container type.

Mutations would need to be seriously refactored if they are no longer able to freely traverse topology. Instead, any required keys or other information would need to be gathered before a mesh goes into a mutable, inconsistent state.

Spatial traits were factored out of Plexus and into Theon for #27. This freed Plexus from the details of abstracting geometry and also allows those abstractions to be shared.

Primitives (n-gons) are closely related to these abstractions. Theon provides geometric queries, but they are currently limited to bounding and simple geometric concepts like rays and axis-aligned bounding boxes. This leaves downstream crates to implement queries like ray-triangle intersection.

This change would not entirely remove the contents of the primitive module. Instead, it would only remove NGon, Polygon, and other types designed to represent primitives. It would also remove re-exported traits from Theon's composite API (like ZipMap). Generation and decomposition would remain in Plexus (since Theon should not be concerned with things like tessellation).

Once these types migrate, Theon can provide a richer API and spatial queries concerning these structures, especially triangles.

Vertex generators are useful when the minimal set of geometric data for a primitive is needed. Plexus also provides index generators so that expensive indexing isn't required. However, because indices depend on the geometric attribute, this leads to a confusing API that could be easy to misuse.

For example, consider a cube. What is the size of the unique set of vertices? There are eight such positions, six such normals, and four such UV-mappings (that could also be six depending on parameterization). At the moment, the API differentiates this by providing indices_for_{attribute} functions:

let cube = Cube::default();
let positions = cube.vertices_with_position().collect::<Vec<_>>();
let indices = cube
    .indices_for_position() // Must match `vertices_with_position`.
    .triangulate()
    .vertices()
    .collect::<Vec<_>>();

This is versatile, but presents an API that requires users to ensure that they pair the correct indices with a given attribute.

Alternatively, generators could always generate all attributes together. This results in a single minimal set of vertices for every primitive. I think I'd prefer to keep attributes decoupled though. With that in mind, what is the value of vertex generators? To simplify the API, generators could only ever generate polygons. To get an index buffer, an indexer would always be used; there would be no other avenue for generating that data.

This is more expensive for the simplest case, but maybe that's okay. This removes a number of functions from the API, unifies index buffers, and results in iterator expressions that always begin with polygons. This should be more consistent.

At the moment, opaque key types like VertexKey and EdgeKey implement From for their inner types (the "raw key" used in HashMaps behind the storage API). By design, it should not be possible to create opaque keys outside of the storage API. That API only creates opaque keys when topologies are inserted.

The From implementation allows user code to create arbitrary opaque keys. For example:

let mut mesh = Mesh::<Point3<f64>>::from_raw_buffers(indeces, vertices).unwrap();
let key: VertexKey = 64u64.into(); // Arbitrary vertex key.
let _ = mesh.vertex(key); // Arbitrary lookup.

The From implementation should probably be replaced by crate-local conversion traits that are not re-exported. Maybe FromInnerKey and IntoOpaqueKey.

rust-windowing/winit#1782

Updating to 0.24.0+ should fix this.

As an aside I'm curious about the use cases for this crate - am I correct in thinking it is primarily used for runtime procedural mesh generation?

Edit: Most of the docs refer to things being in an initial development state - was wondering about what the long term plans look like for this crate.

Traits in geometry::space and geometry::ops allow Plexus to interpret foreign types in a way that represent Euclidean spaces. This is important for providing the spatial operations required for working with meshes.

The geometry::query module begins to expand the scope of these traits. What if an application wants to use Plexus and perform geometric queries (e.g., collision detection) with MeshGraph as well as types from other crates? Today, this code is often duplicated among purpose-built crates.

The alga crate provides a great abstraction over algebraic concepts, including linear algebra and Euclidean spaces. Unfortunately, these types and traits are very general and difficult or impossible to implement for simpler types (e.g., the vector types from cgmath). Moreover, it seems unlikely that many crates will implement these types.

A crate that provides a minimal set of algebraic primitives strictly for Euclidean spaces could provide a lot of value. Such a crate could provide feature flags to implement these traits for commonly used types in the Rust ecosystem (rather than relying on adoption).

In order to support a broad set of simple types, related or composed operations could be used to avoid needing to express certain mathematical relationships. For example, to avoid requiring distinct representations for column and row vectors (duals), operations like Dot could be used in place of proper dual multiplication. This would likely work for crates like cgmath.

This could also allow geometric queries to be implemented in a generic way that works with nalgebra, cgmath, and any types for which users can implement spatial traits. An application using Plexus could also use this factored out crate for geometric queries elsewhere.

Such an API could be difficult to design, and any foreign types would need to provide access to their spatial data, which could involve expensive copies or complex references. For example, how would MeshGraph provide its geometry to this API? The alternative is probably to limit the scope of geometric traits and have users rely on crates that work specifically with their geometric types for queries.

The Unit trait allows some scalar types to determine the vector space (loosely speaking) and position of a primitive by establishing unit bounds. It is used with the type parameter defined on primitives, such as T in Cube<T>. This is a bit inconsistent though, as attributes other than position have no such type parameter and far less variability. It is debatable that scalar types should be specified here (rather than relying on conversions).

Remove these type parameters. Primitives should always generate positions using the same scalar types, just as other attributes do. It may be useful to allow primitives to be generated with various unit length attributes (width, radius, etc.), but this should be done via a different mechanism (perhaps some separate state given to the Generate iterator).

Today, generating positional polygons looks something like this:

Cube::<f32>::with_unit_width().polygons_with_position()

That code would instead look like this:

Cube::new().polygons_with_position()

Optionally, a new API may be exposed that associates some state with an attribute. In this example, the positions could be manipulated by unit bounds:

Cube::new().polygons_with_position_with(Bounds::with_unit_width())

When the mutation API is used to modify a mesh, commit failures are catastrophic: the entire mesh is lost. Today, the results of these mutations are unwrapped, so not only is the mesh lost, but the thread panics.

The mutation API allows a replacement to be used when modifying through a mutable reference. To make these errors recoverable, a clone of the mesh could be used as a replacement, but this could be prohibitively expensive.

Instead, consider using transactional collections for storage. Such a collection would track modifications, present a view of those modifications, and allow them to either be committed or rolled back. If a topological error is detected by the mutation API, then storage can be rolled back and the original mesh can be recovered without too high a cost. It may be possible to refactor the transactional behavior of mutations and share it with storage.

Currently, the mutation API is strictly internal and is not accessible to user code. It is also the only API that directly exposes basic topological operations, including removals. As this API matures, I've considered exposing it directly to enable more advanced usage of Plexus, but I'd like to expose most necessary operations directly via views using a topologically sound API that avoids low-level operations.

At the moment, views do not expose any operations resulting in a net loss of topological structures and provide no direct removal operations. It's not too clear to me how best to accomplish this, but views should expose some way to remove topology! This is deceptively complex. For example, what exactly should happen if a half-edge is removed? When should a removal affect other topological structures? For example, when a face is removed, should only the face be removed, or also its edges and vertices? How does topology collapse or recompose?

Working off of master (060922), the following example fails to compile (with the geometry-nalgebra feature):

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

type P2 = Point2<f64>;

fn main() {
    let graph: MeshGraph<P2> = MeshGraph::from(Tetragon::from(
	[(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)]));

    for f in graph.faces() {
	for v in f.vertices() {
	    dbg!(v.data);
	}
    }
}

with the following errors:

error[E0599]: no method named `vertices` found for struct `plexus::graph::face::FaceView<&plexus::graph::MeshGraph<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>>` in the current scope
   --> src/main.rs:14:13
    |
14  |       for v in f.vertices() {
    |                  ^^^^^^^^ method not found in `plexus::graph::face::FaceView<&plexus::graph::MeshGraph<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>>`
    | 
   ::: /home/mason/.cargo/git/checkouts/plexus-5bab751eb553978e/0609252/plexus/src/graph/face.rs:50:1
    |
50  | / pub struct Face<G>
51  | | where
52  | |     G: GraphData,
53  | | {
...   |
58  | |     pub(in crate::graph) arc: ArcKey,
59  | | }
    | | -
    | | |
    | | doesn't satisfy `<_ as std::iter::Iterator>::Item = _`
    | |_doesn't satisfy `_: plexus::primitive::decompose::Vertices<_>`
    |   doesn't satisfy `_: std::iter::Iterator`
...
109 |   pub struct FaceView<B>
    |  _-
    | |_|
    | |_|
    | |
110 | | where
111 | |     B: Reborrow,
112 | |     B::Target: AsStorage<Face<Data<B>>> + Parametric,
113 | | {
114 | |     inner: View<B, Face<Data<B>>>,
115 | | }
    | | -
    | |_|
    | |_doesn't satisfy `<_ as std::iter::Iterator>::Item = _`
    | |_doesn't satisfy `_: plexus::primitive::decompose::Vertices<_>`
    |   doesn't satisfy `_: std::iter::Iterator`
    |
    = note: the method `vertices` exists but the following trait bounds were not satisfied:
            `<plexus::graph::face::FaceView<&plexus::graph::MeshGraph<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>> as std::iter::Iterator>::Item = _`
            which is required by `plexus::graph::face::FaceView<&plexus::graph::MeshGraph<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>>: plexus::primitive::decompose::Vertices<_>`
            `plexus::graph::face::FaceView<&plexus::graph::MeshGraph<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>>: std::iter::Iterator`
            which is required by `plexus::graph::face::FaceView<&plexus::graph::MeshGraph<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>>: plexus::primitive::decompose::Vertices<_>`
            `<&plexus::graph::face::FaceView<&plexus::graph::MeshGraph<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>> as std::iter::Iterator>::Item = _`
            which is required by `&plexus::graph::face::FaceView<&plexus::graph::MeshGraph<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>>: plexus::primitive::decompose::Vertices<_>`
            `&plexus::graph::face::FaceView<&plexus::graph::MeshGraph<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>>: std::iter::Iterator`
            which is required by `&plexus::graph::face::FaceView<&plexus::graph::MeshGraph<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>>: plexus::primitive::decompose::Vertices<_>`
            `<&mut plexus::graph::face::FaceView<&plexus::graph::MeshGraph<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>> as std::iter::Iterator>::Item = _`
            which is required by `&mut plexus::graph::face::FaceView<&plexus::graph::MeshGraph<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>>: plexus::primitive::decompose::Vertices<_>`
            `&mut plexus::graph::face::FaceView<&plexus::graph::MeshGraph<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>>: std::iter::Iterator`
            which is required by `&mut plexus::graph::face::FaceView<&plexus::graph::MeshGraph<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>>: plexus::primitive::decompose::Vertices<_>`
            `<plexus::graph::face::Face<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>> as std::iter::Iterator>::Item = _`
            which is required by `plexus::graph::face::Face<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>: plexus::primitive::decompose::Vertices<_>`
            `plexus::graph::face::Face<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>: std::iter::Iterator`
            which is required by `plexus::graph::face::Face<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>: plexus::primitive::decompose::Vertices<_>`
            `<&plexus::graph::face::Face<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>> as std::iter::Iterator>::Item = _`
            which is required by `&plexus::graph::face::Face<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>: plexus::primitive::decompose::Vertices<_>`
            `&plexus::graph::face::Face<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>: std::iter::Iterator`
            which is required by `&plexus::graph::face::Face<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>: plexus::primitive::decompose::Vertices<_>`
            `<&mut plexus::graph::face::Face<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>> as std::iter::Iterator>::Item = _`
            which is required by `&mut plexus::graph::face::Face<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>: plexus::primitive::decompose::Vertices<_>`
            `&mut plexus::graph::face::Face<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>: std::iter::Iterator`
            which is required by `&mut plexus::graph::face::Face<nalgebra::geometry::point::Point<f64, nalgebra::base::dimension::U2>>: plexus::primitive::decompose::Vertices<_>`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0599`.
error: could not compile `plexus-demo`.

To learn more, run the command again with --verbose.

I get similar errors for f.arcs() and f.edges().

graph.vertices() works fine, however.

Today, mutations do not perform very much validation. FaceMutation is probably the most sophisticated, and ensures that consistent meshes are manifolds, but the most basic invariants for vertices, edges, and faces are not rigorously examined.

This could be accomplished by introducing some kind of JournaledStorage type that wraps (and owns) storage and tracks all accessed topologies. During a commit, any touched topologies can be examined for basic consistency. For example, any touched edges must have an opposite edge. Using a wrapper ensures that no accesses are missed.

This issue completely contradicts #16 and the title just about says it all. 😛

Effective slot map implementations like those found in the slotmap crate have some limitations that are difficult (expensive) to work around. Mainly, keys are entirely opaque and their generation is intrusive, meaning that it relies on embedded structures in the slot map that must be mutated. Shrinking the allocation used to store items invalidates keys and requires rekeying (as seen in #19).

In #16, I presumed that slot maps would have better performance than hash maps, but I never tested this. I've recently done some preliminary testing using variations on this benchmark and hash maps using the AHash function seem to consistently beat slot maps by a 25% margin. I've tested this against various slot map variants, different iteration sizes, and different subdivision depths.

One benchmark is certainly not enough to definitively claim that hash maps will yield better general performance! However, these results are still promising and suggest that hash maps may not be trounced by slot maps in this application. Importantly, hash maps have additional useful properties that slot maps lack.

1. Hash maps can be resized trivially (though they generally require memory overhead).
2. Hash maps have stable keys.
3. Keys are generated separately from hash maps.
4. HashMap supports non-Copy items on stable Rust.

The journaling described in #19 becomes trivial to implement using exclusively hash maps. Providing a shrink_to_fit API for MeshGraph would become much simpler and more efficient, as it would not require rekeying. Cloning becomes trivial to implement, but rekeying may still be a good idea to avoid identical keys between independent graphs.

I plan to continue some testing.

MeshGraph implements a half-edge graph data structure. This structure is typically limited to compact and oriented manifold representations.

Plexus uses the concept of rings (previously called interior paths) to help mitigate these limitations (among other uses) by not requiring that faces be present in a consistent graph. This provides some support for non-continuous surfaces, unbounded composite edges, and other features. Some non-manifold structures can be approximated, but traversals and constraints become a challenge.

Perhaps MeshGraph can migrate to a non-manifold representation like Blender's bmesh or the radial edge data structure. This complicates some scenarios, but is generally more flexible than half-edge representations and still offers fairly efficient adjacency queries. It should be possible to reuse graph abstractions (e.g., storage, views, etc.) to implement such a data structure.

Alternatively, both representations can be provided by Plexus. This would obviously require some changes to the organization of modules and types.

MeshGraph, despite being based on a half-edge graph design, supports some non-manifold and non-compact topologies. Below are some observations about these features that may need to be revisited to avoid degenerate behavior.

One of the most obvious examples of this is the concept of rings, which may not be associated with a face and allow for explicit gaps in a graph. Additionally, graphs allow for unbounded edges, which are edges that participate in no faces at all. This interacts strangely with rings, because a lone edge forms a single ring in which a face may be inserted.

A ring requires only two arcs at a minimum. This is different from a face, which must be composed of at least three vertices and three arcs. Some code assumes that rings and faces are identical in this respect. For example, rings and faces share circulator implementations which use a lower bound size hint of three. More critically, mutations do not detect rings with an arity of two when attempting to insert faces. I'm not sure yet, but this probably leads to latent errors or, in the worst case, get_or_insert_face being capable of corrupting a graph.

MeshGraph also supports singularities. A singularity is a vertex that is shared by more than one face where none of the faces share any other topology. This forms a non-manifold "pinwheel" structure. This was previously disallowed, but I relaxed this constraint. However, it requires detection and special behavior for certain operations.

At the very least, it would probably be best for graphs to reject unbounded edges. It's also worth keeping in mind that gaps in a surface can also be represented geometrically: using () or Option<_> for face geometry is one way to model a wireframe or a surface with gaps, respectively.

Mutating the topology of a Mesh may leave the mesh in an invalidate state if a failure occurs, with no way for client code to recover. Mutating operations should probably guard against this and validate the operation before performing any mutations.

It may not always be possible to ensure that a failure does not occur after beginning a mutation though. What should Mesh do if it is "mangled" after a failure? Is there some way to make mutations transactional? Is there some mechanism that client code can use to recover?

Kvark made a really cool crate called mint that's designed to help ecosystem authors deal with math types generically without having to make specific implementations for each crate.

I didn't look too closely at Plexus, but it looks like it might be able to benefit from going through mint instead of enabling specific features for cgmath and nalgebra!

A 2D half-edge graph can be useful. Technically, Plexus already supports this in some fashion because the geometric data in a graph is arbitrary. However, none of the geometric traits are implemented for 2D types like Duplet or Point2. This should work rather naturally, with some traits being general enough to support both 2D and 3D and others, like Cross, will prevent 2D meshes from exposing nonsense operations like face extrusion.

It may also be useful to provide 2D primitive generators like circles and squares. This is a bit trickier, because these primitives can also exist in 3D, and it isn't clear how best to support that.

I'm a Rust n00b but I have 25+ years of experience working with geometry in C/C++ (e.g. using libs like OpenMesh). The reference docs for Plexus are extremely thin even for someone like me. I.e. I have to do a lot of trial and error when using this crate.

It would really be helpful if there were some more examples. Maybe some code that shows how to convert an indexed mesh, loaded e.g. from an OBJ, into a graph and then perform some basic topology modifying operation on it – like collapsing an edge or extruding a face.

Half-edges store a VertexKey that references a destination vertex. That is, if a half-edge goes from a source vertex a to a destination vertex b (originating at vertex a and "pointing" to vertex b), then the VertexKey it stores will be for vertex b. Vertices store an EdgeKey for their originating edge, if any.

Some code assumes the opposite, and uses the VertexKeys of a target half-edge and its next half-edge as if they were the vertices spanned by that half-edge. These are actually the vertices spanned by the next half-edge.

Code should either attempt to complete a loop of half-edges or deconstruct the EdgeKey to find the VertexKeys that comprise a half-edge instead.

The graph API, especially views and mutations, relies on an input parameter (typically named G) that specifies the GraphGeometry of an associated graph type (a MeshGraph or raw Core). These parameters are somewhat redundant, because a graph should always have associated geometry that can be expressed via a trait and an associated type. Both MeshGraph and Core have input parameters for specifying geometry, for example.

In particular, views require client code to plumb a type parameter into more than one place. Consider this generic function:

fn is_planar<G>(face: FaceView<&MeshGraph<G>, G>) -> bool
where
    G: GraphGeometry,
    G::Vertex: AsPosition,
{
    ...
}

Notice that the parameter G occurs twice in the FaceView type. This is a bit cumbersome and technically incorrect, as these parameters are always intended to be the same.

It should be possible to remove these additional parameters, but at the cost of somewhat more verbose and complex type bounds when defining view and mutation types. However, this could make user code more ergonomic.

I've experimented a bit and I think an API like this could work. It introduces a new trait and patterns for defining view types:

pub trait Geometric {
    type Geometry: GraphGeometry;
}

impl<B> Geometric for B
where
    B: Reborrow,
    B::Target: Geometric,
{
    type Geometry = Geometry<B::Target>;
}

impl<G> Geometric for MeshGraph<G>
where
    G: GraphGeometry,
{
    type Geometry = G;
}

impl<...> Geometric for Core<...>
where
    ...,
{
    ...
}

pub type Geometry<M> = <M as Geometric>::Geometry;

Note that using an associated type might be more verbose or require an explicit lifetime to ensure that the geometry type lives as long as a borrow of the view, because the parameter G is no longer an input parameter. See the position function in the gist for an example of this. Requiring 'static is also possible, but I'd prefer to avoid that.

The IndexVertices trait can be used to index arbitrary streams of vertex data, but requires that the arity of the topology (polygons) is constant (i.e., all triangles or all quads). It should be possible to index streams with variable arity and, for example, generate a Mesh with a mix of triangles and quads. The UvSphere primitive generates both triangles and quads, but currently must be triangulated before conversion into a MeshBuffer or Mesh.

Provide a mechanism for preserving the original topology of such generators when indexing/converting into a Mesh. (Note that this really don't apply to MeshBuffer, which is meant mostly for rendering pipelines that typically expect a constant arity anyway.)

Arcs and faces provide some of the most important topological mutations for MeshGraphs. The mutation API is mostly comprised of mutations over arcs and faces. However, arc mutations generalize to paths and paths should probably become the primary mechanism for these mutations. For example, extruding and bridging individual arcs is limiting; extruding a boundary path is a more powerful abstraction.

The mutation API and view APIs should shift to expose mutations for Paths. For starters, here are some useful mutations that Path should probably provide:

• Extrude
  Extruding a boundary path inserts three additional edges and inserts a face within the ring formed from the path and those edges, extruding an "edge" formed from the path's arcs into a single arc. This is related to bridging, which arcs already support, but the API for bridging is difficult to design for paths.
• Fill
  Filling a boundary arc inserts an edge between its endpoints and inserts a face into the ring formed by the edge and the path. Extrusion never joins existing arcs and this operation provides a mechanism to join together faces over existing topology.
• Split
  Splitting a path creates a boundary between the arcs along the path, copying any vertex and edge data as needed. This creates rings and, geometrically, "cuts" a surface. Splitting may or may not produce disjoint sub-graphs.

Arcs can still expose these operations by converting into a path and reusing that implementation. Some exclusive operations for arcs are still important, of course, such as collapsing.

Plexus uses the term arity to refer to the edge count of polygons. There are two orthogonal concerns that are sometimes conflated or otherwise unclear in APIs:

• The different natures of the arity of primitive types like NGon and mesh types like MeshGraph. At runtime, primitive types have a singular arity while meshes may have a compound arity formed from their parts (this could be a singular value or a range of values).
• The arities that a type statically supports vs. the arity that a value has at runtime. This can be modeled with an associated constant and an arity function over &self, respectively.

For example, the ConstantArity trait is implemented by primitive types that have a singular arity and so arity is expressed as a single usize. In this case, static and dynamic arity are implied by this trait: they are the same singular value. But what about dynamic types and mesh types? At the moment, this is not described by a trait and the naming would likely clash with the ConstantArity trait and Arity type.

It would probably be good to codify this and use a consistent taxonomy in APIs. It may be helpful for types to be able to specify an associated type for representing arity that in turn implements some common traits. Perhaps something like the following:

pub trait StaticArity {
    type Static;

    const ARITY: Self::Static;
}

pub trait DynamicArity: StaticArity {
    type Dynamic; // Distinct from `Static`. Consider the `Polygon` type.

    fn arity(&self) -> Self::Dynamic;
}

// Implemented by primitive types with fixed arity, like `NGon([T; 3])`. Bikeshed...
pub trait ConstantArity: StaticArity<Static = usize> {}

// Prevent alternative implementations of `DynamicArity` for types that implement
// `ConstantArity`.
impl<T> DynamicArity for T
where
    T: ConstantArity,
{
    type Dynamic = <T as StaticArity>::Static;

    fn arity(&self) -> Self::Dynamic {
        Self::ARITY
    }
}

Of course, documenting this would also be necessary.

Half-edges are only paired with an opposite when a face is present on each side. Half-edges have no opposite along boundaries (where a boundary is an edge belonging to a face with no opposing face). In open meshes, this breaks circulators, which rely on traversing opposing edges. What's worse, there is no indication that something has gone wrong. Given a Mesh called mesh that forms a single triangle, only the interior of the face would have half-edges. This code would fail:

// Get a vertex in the triangle.
let vertex = mesh.vertices().nth(0).unwrap();
// Today, each vertex would have exactly one incoming edge, but this would fail
// with a count of zero.
assert_eq!(1, vertex.incoming_edge().count());

Circulators should always work as expected or at least indicate failure. The correct thing to do is probably to represent every edge with opposing half-edges, not only when opposing faces are present. It may also be helpful to track boundary edges.

MeshGraphs only expose half-edges. There is no notion of a composite edge in the public API and half-edges have independent geometry. This can make working with edge geometry somewhat awkward, as a composite edge's geometry is the combination of the geometry of its two half-edges.

Consider providing some notion of composite edges with singular geometry. For example, half-edges could share a singular geometry by referencing a shared composite edge. This could be a more natural representation. Internally, this would require a CompositeEdge topology to provide this geometry for half-edges.

With no directly associated geometry, half-edges would no longer have any kind of mutable iterators (orphan views) and could only expose geometry by reading their associated composite edge. A CompositeEdgeView type may only need to support consistent storage, as such a type wouldn't be very useful or necessary when mutating the topology of a mesh.

Consider replacing the use of HashMap with a slot map in Storage. This could improve performance (benchmarks?). This crate looks promising.

However, edges currently use keys built from their corresponding vertex keys, which is incompatible with slot maps (because it requires being able to specify the key). Examine this pattern to see if it can be removed or modified or if continuing to use HashMap for edges is a better approach.

I have a mesh where every face is an equilateral triangle, and I want to replace every triangle with four smaller equal-sized triangles. In theory this should be straightforward with a half-edge data structure: subdivide every edge, then for each new vertex, add an edge to the vertex two steps along each incident edge loop, then fill in the new faces and erase the old ones.

The half-edge data structure provided by plexus, however, doesn't seem to expose a way to do this; I can subdivide edges easily enough, but introducing totally new edges and adding/removing faces appears to be impossible. There's a triangulate method which does something similar, but it relies on private interfaces to work. What's the intended approach for this sort of problem?

The faces of meshes are not always planar. Some geometric computations use adjacent edges or other means to determine vectors with the assumption that a face is planar. To mitigate error, it may be a good idea to rely more heavily on centroids instead of adjacent points. Centroids provide a compromise when a face is wildly non-planar, and will often yield better results than sampling just a few points along a perimeter.

At the moment, all Results use () as the error type, which cannot be used to identify or get information about an error condition. Use more informative error types. Consider using the failure crate or, if that doesn't work out, error-chain.

The Geometry trait is used to specify the geometric attributes associated with topological structures in a MeshGraph:

pub trait Geometry {
    type Vertex: Attribute;
    type Arc: Attribute + Default;
    type Edge: Attribute + Default;
    type Face: Attribute + Default;
}

Each associated type requires the Attribute trait. This trait provides no methods and only requires Clone. This trait should be removed, because it provides virtually no functionality and disallows users from using types outside of their own crate as attributes due to coherence rules. For example, this test uses f32 for face geometry and could not be written outside of the Plexus crate, because it would not be possible to implement Attribute for f32.

Triangulating a graph constructed by subdividing a simple face appears to cause corruption. I discovered this while experimenting with the subdivide example, which demonstrates this function:

pub fn circumscribe<G>(face: FaceView<&mut MeshGraph<G>, G>) -> FaceView<&mut MeshGraph<G>, G>
where
    G: EdgeMidpoint<Midpoint = VertexPosition<G>> + GraphGeometry,
    G::Vertex: AsPosition,
{
    // Split each edge, stashing the vertex key and moving to the next arc.
    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();
    }
    // Split faces along the vertices from each arc split.
    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();
    }
    // Return the central face of the subdivision.
    face
}

Using this function, the following code causes a panic when calling triangulate:

let mut graph = MeshGraph::<Point2<f64>>::from_raw_buffers(
    vec![NGon([0usize, 1, 2, 3])],
    vec![(-1.0 -1.0), (1.0, -1.0), (1.0, 1.0), (-1.0, 1.0)],
)
.unwrap();
let key = graph.faces().nth(0).unwrap().key();
// Subdivide the face twice.
circumscribe(circumscribe(graph.face_mut(key).unwrap()));
graph.triangulate(); // PANIC!

So far, it seems that the subdivisions work as intended. The number of vertices and faces is correct and so is the arity of the faces. However, triangulation suddenly fails when it encounters a face with arity 11. That's very strange:

1. Triangulation is implemented using splits, which should be independent of other faces; the arity of faces elsewhere in the graph should not be affected.
2. After the subdivisions, there are only 12 vertices in the graph, so a face with arity 11 would include all but one of them.

I suspect that something is wrong in the mutation API (specifically FaceSplitSnapshot and split_with_snapshot), but I'm not sure. For example, maybe the snapshot is failing to identify the perimeters for the two newly inserted faces for the split.