Struct HalfedgeMesh 

pub struct HalfedgeMesh { /* private fields */ }

Halfedge (doubly-connected edge list) surface mesh of a 2-manifold, with or without boundary, with polygonal faces.

See the module documentation for the layout and the invariants. Navigation queries take ids of live elements; passing an id of a removed element returns stale data rather than panicking, and an id past the arrays panics like slice indexing. Edits check liveness and refuse by name.

Implementations

impl HalfedgeMesh

pub fn flip_edge(&mut self, e: EdgeId) -> Result<(), HalfedgeEditError>

Replace an edge between two triangles by the other diagonal of the quadrilateral they form. Counts, and so the Euler characteristic, are unchanged; the edge keeps its id.

Errors

HalfedgeEditError::BoundaryEdge, HalfedgeEditError::NotATriangle, HalfedgeEditError::WouldDegenerate when the two opposite corners are one vertex, and HalfedgeEditError::EdgeExists when they are already joined.

pub fn split_edge( &mut self, e: EdgeId, position: DVec3, ) -> Result<VertexId, HalfedgeEditError>

Insert a vertex at position on an edge and join it to the opposite corner of each adjacent triangle, so a triangle mesh stays a triangle mesh. A non-triangular adjacent face just gains a side. The Euler characteristic is unchanged.

The old edge keeps its id and runs from its original source to the new vertex.

Errors

HalfedgeEditError::RemovedElement and HalfedgeEditError::TooLarge.

pub fn collapse_edge( &mut self, h: HalfedgeId, ) -> Result<VertexId, HalfedgeEditError>

Collapse halfedge h by merging its source into its target, which keeps its id and position (move it with HalfedgeMesh::set_position). The incident triangles disappear and their remaining sides merge pairwise. Removes one vertex, three edges on an interior edge (two on a boundary edge) and the adjacent faces, so the Euler characteristic is unchanged.

Errors

HalfedgeEditError::NotATriangle when a face around the removed vertex is not a triangle, HalfedgeEditError::LinkCondition when the collapse would pinch the surface, and HalfedgeEditError::WouldDegenerate for a tetrahedron, a lone triangle or a two-triangle pillow.

pub fn split_face( &mut self, f: FaceId, position: DVec3, ) -> Result<VertexId, HalfedgeEditError>

Insert a vertex at position inside a face and fan the face into triangles around it, one per side. The face keeps its id as the triangle on its stored halfedge. The Euler characteristic is unchanged.

Errors

HalfedgeEditError::RemovedElement and HalfedgeEditError::TooLarge.

pub fn split_face_diagonal( &mut self, a: HalfedgeId, b: HalfedgeId, ) -> Result<HalfedgeId, HalfedgeEditError>

Split a face by a new edge from target(a) to target(b), two corners of the same face that are not already joined. Returns the new halfedge running from target(a) to target(b); it stays on the original face, which keeps a, and the other part becomes a new face. The Euler characteristic is unchanged.

This triangulates a polygon one diagonal at a time, for example a hole closed with HalfedgeMesh::fill_hole.

Errors

HalfedgeEditError::NotSameFace (boundary halfedges included), HalfedgeEditError::AdjacentCorners, and HalfedgeEditError::EdgeExists when the corners are joined through another face.

pub fn fill_hole(&mut self, h: HalfedgeId) -> Result<FaceId, HalfedgeEditError>

Close the hole bounded by boundary halfedge h with one new face. The Euler characteristic rises by one.

Errors

HalfedgeEditError::NotBoundary when h already has a face.

impl HalfedgeMesh

pub fn from_tri_mesh(mesh: &TriMesh) -> Result<HalfedgeMesh, HalfedgeBuildError>

Build from an indexed triangle mesh.

Vertex i is mesh.positions[i] and face j is triangle j. Normals and attribute channels are not carried: the halfedge mesh is connectivity plus positions.

Errors

A ragged index buffer, an out-of-range or repeated corner, and every non-manifold or inconsistently wound configuration, each by name.

pub fn from_faces<F>( positions: Vec<DVec3>, faces: &[F], ) -> Result<HalfedgeMesh, HalfedgeBuildError>

where F: AsRef<[u32]>,

Build from positions and polygonal faces, each a loop of position indices wound consistently with its neighbours.

Errors

As HalfedgeMesh::from_tri_mesh, plus faces with fewer than three corners.

pub fn to_tri_mesh(&self) -> Result<TriMesh, HalfedgeEditError>

Indexed triangle mesh of the live elements.

Live vertices keep their relative order, so a mesh that has had no vertex removed keeps its numbering; each triangle starts at its face’s stored halfedge, so building from a TriMesh and converting back reproduces its index buffer exactly.

Errors

HalfedgeEditError::NotATriangle for the first face that is not a triangle; split it with HalfedgeMesh::split_face or HalfedgeMesh::split_face_diagonal first.

pub fn vertex_count(&self) -> usize

Live vertices, including isolated ones.

pub fn edge_count(&self) -> usize

Live edges.

pub fn halfedge_count(&self) -> usize

Live halfedges: twice the edge count.

pub fn face_count(&self) -> usize

Live faces.

pub fn euler_characteristic(&self) -> i64

V - E + F over the live elements (isolated vertices count).

pub fn contains_vertex(&self, v: VertexId) -> bool

Whether the vertex id names a live vertex.

pub fn contains_edge(&self, e: EdgeId) -> bool

Whether the edge id names a live edge.

pub fn contains_halfedge(&self, h: HalfedgeId) -> bool

Whether the halfedge id names a halfedge of a live edge.

pub fn contains_face(&self, f: FaceId) -> bool

Whether the face id names a live face.

pub fn vertices(&self) -> impl Iterator<Item = VertexId>

Live vertices in id order.

pub fn edges(&self) -> impl Iterator<Item = EdgeId>

Live edges in id order.

pub fn halfedges(&self) -> impl Iterator<Item = HalfedgeId>

Live halfedges in id order.

pub fn faces(&self) -> impl Iterator<Item = FaceId>

Live faces in id order.

pub fn boundary_halfedges(&self) -> impl Iterator<Item = HalfedgeId>

Live boundary halfedges in id order.

pub fn boundary_loops(&self) -> Vec<HalfedgeId>

One boundary halfedge per hole, each the lowest id on its loop.

pub fn position(&self, v: VertexId) -> DVec3

Position of a vertex.

pub fn set_position(&mut self, v: VertexId, position: DVec3)

Move a vertex. Connectivity is untouched.

pub fn positions(&self) -> &[DVec3]

The position array, indexed by vertex id (removed vertices included).

pub fn next(&self, h: HalfedgeId) -> HalfedgeId

Next halfedge around the same face or hole.

pub fn prev(&self, h: HalfedgeId) -> HalfedgeId

Previous halfedge around the same face or hole.

pub const fn opposite(&self, h: HalfedgeId) -> HalfedgeId

The other halfedge of the same edge.

pub fn target(&self, h: HalfedgeId) -> VertexId

Vertex the halfedge points to.

pub fn source(&self, h: HalfedgeId) -> VertexId

Vertex the halfedge leaves.

pub fn face(&self, h: HalfedgeId) -> Option<FaceId>

Face to the left of the halfedge; None on a boundary halfedge.

pub const fn edge(&self, h: HalfedgeId) -> EdgeId

Edge owning the halfedge.

pub fn edge_halfedge(&self, e: EdgeId, side: u32) -> HalfedgeId

One of the edge’s two halfedges: side 0 or 1.

Panics

When side is greater than 1.

pub fn edge_vertices(&self, e: EdgeId) -> [VertexId; 2]

Both endpoints of an edge, in the direction of its halfedge 2e.

pub fn vertex_halfedge(&self, v: VertexId) -> Option<HalfedgeId>

Stored outgoing halfedge of a vertex; None when isolated.

For a boundary vertex it is the boundary halfedge leaving it.

pub fn face_halfedge(&self, f: FaceId) -> HalfedgeId

Stored halfedge of a face’s loop.

pub fn is_boundary_halfedge(&self, h: HalfedgeId) -> bool

Whether the halfedge has no face.

pub fn is_boundary_edge(&self, e: EdgeId) -> bool

Whether either side of the edge is a boundary.

pub fn is_boundary_vertex(&self, v: VertexId) -> bool

Whether the vertex lies on a hole. Isolated vertices are not boundary.

pub fn is_isolated(&self, v: VertexId) -> bool

Whether the vertex has no incident edge.

pub fn find_halfedge(&self, from: VertexId, to: VertexId) -> Option<HalfedgeId>

Halfedge from from to to, if the edge exists. O(degree).

pub fn outgoing_halfedges( &self, v: VertexId, ) -> impl Iterator<Item = HalfedgeId>

Outgoing halfedges of a vertex in counter-clockwise order (seen with faces wound counter-clockwise), starting at the stored halfedge, so a boundary vertex starts at its boundary halfedge.

pub fn incoming_halfedges( &self, v: VertexId, ) -> impl Iterator<Item = HalfedgeId>

Incoming halfedges of a vertex, the opposites of HalfedgeMesh::outgoing_halfedges in the same order.

pub fn vertex_vertices(&self, v: VertexId) -> impl Iterator<Item = VertexId>

Neighbouring vertices in counter-clockwise order.

pub fn vertex_faces(&self, v: VertexId) -> impl Iterator<Item = FaceId>

Faces around a vertex in counter-clockwise order, holes skipped.

pub fn degree(&self, v: VertexId) -> usize

Number of edges at a vertex. O(degree).

pub fn loop_halfedges(&self, h: HalfedgeId) -> impl Iterator<Item = HalfedgeId>

Halfedges of the loop containing h (a face or a hole), from h.

pub fn face_halfedges(&self, f: FaceId) -> impl Iterator<Item = HalfedgeId>

Halfedges of a face’s loop, from its stored halfedge.

pub fn face_vertices(&self, f: FaceId) -> impl Iterator<Item = VertexId>

Corners of a face in winding order, starting at the source of its stored halfedge.

pub fn face_faces(&self, f: FaceId) -> impl Iterator<Item = Option<FaceId>>

Faces across each edge of a face, None across a boundary.

pub fn face_degree(&self, f: FaceId) -> usize

Number of sides of a face. O(degree).

pub fn compact(&mut self) -> HalfedgeRemap

Renumber live elements densely in their current order and drop the removed ones. Returns the old-to-new mapping so per-element data held by a caller can follow.

pub fn validate(&self) -> Result<(), HalfedgeInvariantError>

Check every structural invariant listed in the module documentation. O(halfedges).

Errors

The first violated invariant found.

Trait Implementations

impl Clone for HalfedgeMesh

fn clone(&self) -> HalfedgeMesh

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for HalfedgeMesh

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl PartialEq for HalfedgeMesh

fn eq(&self, other: &HalfedgeMesh) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl StructuralPartialEq for HalfedgeMesh