Struct MeshGraph 

pub struct MeshGraph {
    pub bvh: Bvh,
    pub bvh_workspace: BvhWorkspace,
    pub index_to_face_id: HashMap<u32, FaceId>,
    pub next_index: u32,
    pub vertices: SlotMap<VertexId, Vertex>,
    pub halfedges: SlotMap<HalfedgeId, Halfedge>,
    pub faces: SlotMap<FaceId, Face>,
    pub positions: SecondaryMap<VertexId, Vec3>,
    pub vertex_normals: Option<SecondaryMap<VertexId, Vec3>>,
    pub outgoing_halfedges: SecondaryMap<VertexId, Vec<HalfedgeId>>,
}

Halfedge data structure for representing triangle meshes.

Please see the crate documentation for more information.

Fields

bvh: Bvh

Acceleration structure for fast spatial queries. Uses parry3d’s Bvh to implement some of parry3d’s spatial queries.

bvh_workspace: BvhWorkspace

Used in conjunction with the BVH to accelerate spatial queries.

index_to_face_id: HashMap<u32, FaceId>

Used to map indices stored in the BVH to face IDs.

next_index: u32

Used to compute the next index for a new face

vertices: SlotMap<VertexId, Vertex>

Maps vertex IDs to their corresponding graph node

halfedges: SlotMap<HalfedgeId, Halfedge>

Maps halfedge IDs to their corresponding graph node

faces: SlotMap<FaceId, Face>

Maps face IDs to their corresponding graph node

positions: SecondaryMap<VertexId, Vec3>

Maps vertex IDs to their corresponding positions

vertex_normals: Option<SecondaryMap<VertexId, Vec3>>

Maps vertex IDs to their corresponding normals

outgoing_halfedges: SecondaryMap<VertexId, Vec<HalfedgeId>>

Maps vertex IDs to their corresponding outgoing halfedges (not in any particular order)

Implementations

impl MeshGraph

pub fn boundary_he(&self, he_id: HalfedgeId) -> Option<HalfedgeId>

Return the halfedge or it’s twin depending on which one is boundary, or None if both are not boundary.

pub fn boundary_vertex_order( &mut self, v_id1: VertexId, v_id2: VertexId, ) -> [VertexId; 2]

Returns the vertex order of the boundary halfedge between two vertices. Useful when adding faces on boundaries.

If the edge is not boundary, it always returns [v_id2, v_id1].

pub fn halfedge_from_to( &self, start_vertex_id: VertexId, end_vertex_id: VertexId, ) -> Option<HalfedgeId>

Returns the halfedge from the start vertex to the end vertex, if it exists. None otherwise.

pub fn face_with_vertices( &self, v_id1: VertexId, v_id2: VertexId, v_id3: VertexId, ) -> Option<FaceId>

Returns the face with the given vertices, if it exists. None otherwise.

impl MeshGraph

pub fn add_or_get_edge( &mut self, start_vertex_id: VertexId, end_vertex_id: VertexId, ) -> AddOrGetEdge

Inserts a pair of halfedges and connects them to the given vertices (from and to the halfedge) and each other as twins. If the edge already exists or partially exists, it returns the existing edge while creating any missing halfedges.

See also [add_edge].

pub fn add_edge( &mut self, start_vertex: VertexId, end_vertex: VertexId, ) -> AddEdge

Inserts a pair of halfedges and connects them to the given vertices (from and to the halfedge) and each other as twins. This creates two halfedges wether the vertices already have an edge between them or not.

If you don’t want this, consider using [add_or_get_edge] instead.

pub fn add_halfedge( &mut self, start_vertex: VertexId, end_vertex: VertexId, ) -> HalfedgeId

Inserts a halfedge into the mesh graph. It only connects the halfedge to the given end vertex but not the reverse. It also doesn’t do any other connections.

It does insert into self.outgoing_halfedges.

Use [insert_or_get_edge] instead of this when you can to lower the chance of creating an invalid graph.

impl MeshGraph

pub fn add_face_from_positions(&mut self, a: Vec3, b: Vec3, c: Vec3) -> AddFace

pub fn add_face_from_halfedge_and_position( &mut self, he_id: HalfedgeId, opposite_vertex_pos: Vec3, ) -> Option<AddFace>

Returns None when an edge already has two faces

pub fn add_face_from_halfedge_and_vertex( &mut self, he_id: HalfedgeId, vertex_id: VertexId, ) -> Option<AddFace>

Returns None when the edge described by he_id already has two faces

pub fn add_face_from_vertices( &mut self, v_id1: VertexId, v_id2: VertexId, v_id3: VertexId, ) -> AddFace

Creates a face from three vertices.

pub fn add_face_from_halfedges( &mut self, he_id1: HalfedgeId, he_id2: HalfedgeId, ) -> Option<AddFace>

Creates a face from two halfedges.

pub fn add_face( &mut self, he1_id: HalfedgeId, he2_id: HalfedgeId, he3_id: HalfedgeId, ) -> FaceId

Inserts a face into the mesh graph. It connects the halfedges to the face and the face to the first halfedge. Additionally it connects the halfedges’ next loop around the face.

impl MeshGraph

pub fn add_vertex(&mut self, position: Vec3) -> VertexId

Inserts a vertex and it’s position into the mesh graph. It doesn’t do any connections.

impl MeshGraph

pub fn make_outgoing_halfedge_boundary_if_possible( &mut self, vertex_id: VertexId, )

Ensure that if one of the outgoing halfedges of this vertex is a boundary halfedge, then it will be the one in [Vertex::outgoing_halfedge].

The method [Vertex::is_boundary] relies on this.

pub fn make_all_outgoing_halfedges_boundary_if_possible(&mut self)

Ensure that if one of the outgoing halfedges of any vertex is a boundary halfedge, then it will be the one in [Vertex::outgoing_halfedge].

The method [Vertex::is_boundary] relies on this.

impl MeshGraph

pub fn make_vertex_neighborhood_manifold( &mut self, vertex_id: VertexId, ) -> VertexNeighborhoodCleanup

Ensure that the neighborhood of a vertex is manifold.

It removes flaps (two neighboring coincident triangles) and splits the given vertex in two if there are non-neighboring degenerate triangles or edges.

See Freestyle: Sculpting meshes with self-adaptive topology DOI 10.1016/j.cag.2011.03.033 Chapters 3.2 and 5.1

pub fn make_vertex_neighborhood_manifold_inner( &mut self, vertex_id: VertexId, removed_vertices: &mut Vec<VertexId>, removed_halfedges: &mut Vec<HalfedgeId>, removed_faces: &mut Vec<FaceId>, ) -> Option<Vec<VertexId>>

pub fn remove_degenerate_faces( &mut self, vertex_id: VertexId, removed_vertices: &mut Vec<VertexId>, removed_halfedges: &mut Vec<HalfedgeId>, removed_faces: &mut Vec<FaceId>, ) -> Option<VertexId>

impl MeshGraph

pub fn faces_share_edge(&self, face_id1: FaceId, face_id2: FaceId) -> bool

Test if two faces have at least one halfedge in common.

pub fn faces_share_all_vertices( &self, face_id1: FaceId, face_id2: FaceId, ) -> bool

Test if two faces share all vertices.

pub fn halfedges_share_all_vertices( &self, halfedge_id1: HalfedgeId, halfedge_id2: HalfedgeId, ) -> bool

Test if two halfedges share all vertices.

pub fn vertices_share_position( &self, vertex_id1: VertexId, vertex_id2: VertexId, ) -> bool

Test if two vertices have the exact same position.

impl MeshGraph

pub fn collapse_until_edges_above_min_length( &mut self, min_length_squared: f32, marked_vertices: &mut HashSet<VertexId>, )

Collapses edges until all edges have a length above the minimum length.

This will schedule necessary updates to the BVH but you have to call refit_bvh() after the operation.

pub fn can_collapse_edge(&mut self, halfedge_id: HalfedgeId) -> bool

pub fn collapse_edge_inner( &mut self, halfedge_id: HalfedgeId, twin_id: HalfedgeId, start_v_id: VertexId, end_v_id: VertexId, center_pos: Vec3, ) -> CollapseEdge

pub fn collapse_edge(&mut self, halfedge_id: HalfedgeId) -> CollapseEdge

Collapse an edge in the mesh graph.

This moves the start vertex of the edge to the center of the edge and removes the end vertex and the adjacent and opposite faces.

It also performs a cleanup afterwards to remove flaps (faces that share the same vertices).

Returns the vertices, halfedges and faces that were removed.

impl MeshGraph

pub fn flip_edge(&mut self, halfedge_id: HalfedgeId)

Flips this edge so that it represents the other diagonal described by the quad formed by the two incident triangles.

    *                    *
   / \                  / \
  /   \                / ‖ \
 /     \              /  ‖  \
* ===== *     =>     *   ‖   *
 \     /              \  ‖  /
  \   /                \ ‖ /
   \ /                  \ /
    *                    *

pub fn make_twins(&mut self, he_id1: HalfedgeId, he_id2: HalfedgeId)

Makes two halfedges twins of each other. Doesn’t change anything else

pub fn remove_outgoing_halfedge( &mut self, vertex_id: VertexId, halfedge_id: HalfedgeId, )

Removes the outgoing halfedge from a vertex. Doesn’t change anything else.

pub fn add_outgoing_halfedge( &mut self, vertex_id: VertexId, outgoing_halfedge: HalfedgeId, )

Adds the outgoing halfedge to a vertex and overrides the vertex.outgoing_halfedge

pub fn smooth_vertices(&mut self, vertices: impl IntoIterator<Item = VertexId>)

Smooths the position of the vertex by computing the average of its own and its neighbors’ positions and moving it there. Also called Laplacian Smoothing.

pub fn smooth_vertex(&mut self, vertex_id: VertexId)

Smooth the position of the vertex by computing the average of its own and its neighbors’ positions and moving it there. Also called Laplacian Smoothing.

Note: If you want to smooth multiple vertices, use the smooth_vertices method instead of calling this method multiple times.

impl MeshGraph

pub fn merge_vertices_one_rings( &mut self, vertex_id1: VertexId, vertex_id2: VertexId, flip_threshold_sqr: f32, marked_halfedges: &mut HashSet<HalfedgeId>, marked_vertices: &mut HashSet<VertexId>, ) -> MergeVerticesOneRing

Merge two vertices by connecting their 1-rings.

The vertices are deleted on top of everything that is returned in the removed_... fields.

See Freestyle: Sculpting meshes with self-adaptive topology DOI 10.1016/j.cag.2011.03.033 Chapters 3.2 and 5.1

impl MeshGraph

pub fn triangle(&self, shape_id: u32) -> Triangle

impl MeshGraph

pub fn remove_face( &mut self, face_id: FaceId, ) -> (Vec<VertexId>, Vec<HalfedgeId>)

Deletes a face from the mesh graph.

It also deletes the vertices and halfedges that are no longer connected to any other faces.

Returns the ids of the removed vertices and halfedges.

pub fn remove_only_vertex(&mut self, vertex_id: VertexId)

Deletes only a vertex, without deleting any faces or halfedges connected to it.

pub fn remove_only_halfedge(&mut self, he_id: HalfedgeId)

Deletes only a halfedge, without deleting any faces or vertices connected to it. This also doesn’t delete or update any twin

pub fn remove_only_halfedge_and_twin(&mut self, he_id: HalfedgeId)

impl MeshGraph

pub fn subdivide_until_edges_below_max_length( &mut self, max_length_squared: f32, marked_halfedge_ids: &mut HashSet<HalfedgeId>, marked_vertex_ids: &mut HashSet<VertexId>, )

Subdivide all edges until all of them are <= max_length. Please note that you have to provide the squared value of max_length.

This will schedule necessary updates to the QBVH but you have to call refit_bvh() after the operation.

pub fn subdivide_edge( &mut self, halfedge_id: HalfedgeId, ) -> Option<SubdivideEdge>

Subdivides an edge by computing it’s center vertex. This also subdivides any adjacent triangles and makes sure everything is properly reconnected. Works only on triangle meshes.

Returns the id of the new halfedge which goes from the center vertex to the original edge’s end vertex. And also return the halfedges that are created by subdividing the adjacent faces. Only one of the two twin halfedges per face subdivision is returned. In total the number n of halfedges returned is 1 <= n <= 3. (The one from dividing the halfedge and at most 2 from dividing the two adjacent faces).

Also returns the created vertex id.

impl MeshGraph

pub fn apply_quat(&mut self, quat: Quat)

Apply a quaternion rotation to the mesh graph (positions and normals).

After this you should probably call rebuild_bvh to update the bounding volume hierarchy.

pub fn apply_projection(&mut self, projection: Mat4)

Apply a projection to the mesh graph (positions and normals).

After this you should probably call rebuild_bvh to update the bounding volume hierarchy.

pub fn apply_transform(&mut self, transform: Mat4)

Apply a transform matrix to the mesh graph (positions and normals).

After this you should probably call rebuild_bvh to update the bounding volume hierarchy.

impl MeshGraph

pub fn halfedges_map( &mut self, predicate: impl Fn(f32) -> bool, ) -> HashMap<HalfedgeId, f32>

impl MeshGraph

pub fn new() -> Self

Create a new empty mesh graph

pub fn triangles(vertex_positions: &[Vec3]) -> Self

Create a triangle mesh graph from vertex positions. Every three positions represent a triangle.

Vertices with the same position are merged into a single vertex.

pub fn indexed_triangles( vertex_positions: &[Vec3], face_indices: &[usize], ) -> Self

Create a triangle mesh graph from vertex positions and face indices. Every chunk of three indices represents a triangle.

pub fn compute_vertex_normal(&mut self, vertex_id: VertexId)

Computes the vertex normal from neighboring faces

pub fn compute_vertex_normals(&mut self)

Computes the vertex normals by averaging over the computed face normals

pub fn normalize_vertex_normals(&mut self)

Ensures that the vertex normals are all normalized

pub fn optimize_bvh_incremental(&mut self)

Calls the optimize_incremental method of the BVH.

pub fn refit_bvh(&mut self)

Recomputes the bounding boxes of the BVH. This is necessary when the mesh is modified.

pub fn rebuild_bvh(&mut self)

Rebuilds the BVH from scratch

pub fn rebuild_outgoing_halfedges(&mut self)

Trait Implementations

impl Clone for MeshGraph

fn clone(&self) -> MeshGraph

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl CompositeShape for MeshGraph

fn map_part_at( &self, shape_id: u32, f: &mut dyn FnMut(Option<&Pose>, &dyn Shape, Option<&dyn NormalConstraints>), )

Applies a function to one sub-shape of this composite shape.

fn bvh(&self) -> &Bvh

Gets the acceleration structure of the composite shape.

impl Default for MeshGraph

fn default() -> MeshGraph

Returns the “default value” for a type.

impl From<&MeshGraph> for VertexIndexBuffers

fn from(mesh_graph: &MeshGraph) -> VertexIndexBuffers

Converts to this type from the input type.

impl From<IcoSphere> for MeshGraph

fn from(isosphere: IcoSphere) -> Self

Converts to this type from the input type.

impl From<Quad> for MeshGraph

fn from(quad: Quad) -> Self

Converts to this type from the input type.

impl From<Triangle> for MeshGraph

fn from(triangle: Triangle) -> Self

Converts to this type from the input type.

impl PointQuery for MeshGraph

fn project_local_point(&self, point: Vec3, solid: bool) -> PointProjection

Projects a point on self.

fn project_local_point_and_get_feature( &self, _point: Vec3, ) -> (PointProjection, FeatureId)

Projects a point on the boundary of self and returns the id of the feature the point was projected on.

fn project_local_point_with_max_dist( &self, pt: Vec3, solid: bool, max_dist: f32, ) -> Option<PointProjection>

Projects a point onto the shape, with a maximum distance limit.

fn project_point_with_max_dist( &self, m: &Pose3, pt: Vec3, solid: bool, max_dist: f32, ) -> Option<PointProjection>

Projects a point on self transformed by m, unless the projection lies further than the given max distance.

fn distance_to_local_point(&self, pt: Vec3, solid: bool) -> f32

Computes the minimal distance between a point and self.

fn contains_local_point(&self, pt: Vec3) -> bool

Tests if the given point is inside of self.

fn project_point(&self, m: &Pose3, pt: Vec3, solid: bool) -> PointProjection

Projects a point on self transformed by m.

fn distance_to_point(&self, m: &Pose3, pt: Vec3, solid: bool) -> f32

Computes the minimal distance between a point and self transformed by m.

fn project_point_and_get_feature( &self, m: &Pose3, pt: Vec3, ) -> (PointProjection, FeatureId)

Projects a point on the boundary of self transformed by m and returns the id of the feature the point was projected on.

fn contains_point(&self, m: &Pose3, pt: Vec3) -> bool

Tests if the given point is inside of self transformed by m.

impl PointQueryWithLocation for MeshGraph

fn project_local_point_and_get_location_with_max_dist( &self, point: Vec3, solid: bool, max_dist: f32, ) -> Option<(PointProjection, Self::Location)>

Projects a point on self, with a maximum projection distance.

type Location = Face

Additional shape-specific projection information

fn project_local_point_and_get_location( &self, point: Vec3, solid: bool, ) -> (PointProjection, Self::Location)

Projects a point on self.

fn project_point_and_get_location( &self, m: &Pose3, pt: Vec3, solid: bool, ) -> (PointProjection, Self::Location)

Projects a point on self transformed by m.

fn project_point_and_get_location_with_max_dist( &self, m: &Pose3, pt: Vec3, solid: bool, max_dist: f32, ) -> Option<(PointProjection, Self::Location)>

Projects a point on self transformed by m, with a maximum projection distance.

impl RayCast for MeshGraph

fn cast_local_ray( &self, ray: &Ray, max_time_of_impact: f32, solid: bool, ) -> Option<f32>

Computes the time of impact between this transform shape and a ray.

fn cast_local_ray_and_get_normal( &self, ray: &Ray, max_time_of_impact: f32, solid: bool, ) -> Option<RayIntersection>

Computes the time of impact, and normal between this transformed shape and a ray.

fn intersects_local_ray(&self, ray: &Ray, max_time_of_impact: f32) -> bool

Tests whether a ray intersects this transformed shape.

fn cast_ray( &self, m: &Pose3, ray: &Ray, max_time_of_impact: f32, solid: bool, ) -> Option<f32>

Computes the time of impact between this transform shape and a ray.

fn cast_ray_and_get_normal( &self, m: &Pose3, ray: &Ray, max_time_of_impact: f32, solid: bool, ) -> Option<RayIntersection>

Computes the time of impact, and normal between this transformed shape and a ray.

fn intersects_ray(&self, m: &Pose3, ray: &Ray, max_time_of_impact: f32) -> bool

Tests whether a ray intersects this transformed shape.

impl TypedCompositeShape for MeshGraph

type PartShape = Triangle

type PartNormalConstraints = ()

fn map_typed_part_at<T>( &self, shape_id: u32, f: impl FnMut(Option<&Pose>, &Self::PartShape, Option<&Self::PartNormalConstraints>) -> T, ) -> Option<T>

fn map_untyped_part_at<T>( &self, shape_id: u32, f: impl FnMut(Option<&Pose>, &dyn Shape, Option<&dyn NormalConstraints>) -> T, ) -> Option<T>