mesh_graph/elements/
halfedge.rs

1use tracing::{error, instrument};
2
3use crate::{MeshGraph, error_none};
4
5use super::{FaceId, HalfedgeId, VertexId};
6
7/// A directional edge that points from one vertex to another and is (optionally) part of a face.
8/// If it's not part of a face, it's called a boundary halfedge.
9///
10/// <img src="https://raw.githubusercontent.com/Synphonyte/mesh-graph/refs/heads/main/docs/halfedge/all.svg" alt="Connectivity" style="max-width: 28em" />
11#[derive(Debug, Clone, Copy)]
12#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
13pub struct Halfedge {
14    /// The vertex that this halfedge points to.
15    ///
16    /// <img src="https://raw.githubusercontent.com/Synphonyte/mesh-graph/refs/heads/main/docs/halfedge/end_vertex.svg" alt="Connectivity" style="max-width: 28em" />
17    pub end_vertex: VertexId,
18
19    /// The face associated to this halfedge. `None` if `self` is a boundary halfedge.
20    ///
21    /// <img src="https://raw.githubusercontent.com/Synphonyte/mesh-graph/refs/heads/main/docs/halfedge/face.svg" alt="Connectivity" style="max-width: 28em" />
22    pub face: Option<FaceId>,
23
24    /// This is the halfedge opposite.
25    /// It points backwards compared to this halfedge (from end_vertex to start_vertex).
26    /// After the mesh graph is constructed, this field is always `Some(...)`, meaning
27    /// that every halfedge has a twin.
28    ///
29    /// <img src="https://raw.githubusercontent.com/Synphonyte/mesh-graph/refs/heads/main/docs/halfedge/twin.svg" alt="Connectivity" style="max-width: 28em" />
30    pub twin: Option<HalfedgeId>,
31
32    /// The next halfedge in the face. `None` if `self` is a boundary halfedge.
33    ///
34    /// <img src="https://raw.githubusercontent.com/Synphonyte/mesh-graph/refs/heads/main/docs/halfedge/next.svg" alt="Connectivity" style="max-width: 28em" />
35    pub next: Option<HalfedgeId>,
36}
37
38impl Halfedge {
39    /// Start vertex from which this halfedge points away
40    ///
41    /// <img src="https://raw.githubusercontent.com/Synphonyte/mesh-graph/refs/heads/main/docs/halfedge/start_vertex.svg" alt="Connectivity" style="max-width: 28em" />
42    #[instrument(skip(mesh_graph))]
43    pub fn start_vertex(&self, mesh_graph: &MeshGraph) -> Option<VertexId> {
44        mesh_graph
45            .halfedges
46            .get(self.twin.or_else(error_none!("No twin"))?)
47            .or_else(error_none!("Twin halfedge not found"))
48            .map(|t| t.end_vertex)
49    }
50
51    /// Previous halfedge that shares the same face. `None` if `self` is a boundary halfedge.
52    ///
53    /// <img src="https://raw.githubusercontent.com/Synphonyte/mesh-graph/refs/heads/main/docs/halfedge/prev.svg" alt="Connectivity" style="max-width: 28em" />
54    #[instrument(skip(mesh_graph))]
55    pub fn prev(&self, mesh_graph: &MeshGraph) -> Option<HalfedgeId> {
56        // TODO : this only works for triangle meshes
57        self.next.and_then(|next_id| {
58            mesh_graph
59                .halfedges
60                .get(next_id)
61                .or_else(error_none!("Next halfedge not found"))
62                .and_then(|h| h.next)
63        })
64    }
65
66    /// In counter-clockwise order next halfedge that has the same start vertex
67    ///
68    /// <img src="https://raw.githubusercontent.com/Synphonyte/mesh-graph/refs/heads/main/docs/halfedge/ccw_rotated_neighbour.svg" alt="Connectivity" style="max-width: 28em" />
69    #[instrument(skip(mesh_graph))]
70    pub fn ccw_rotated_neighbour(&self, mesh_graph: &MeshGraph) -> Option<HalfedgeId> {
71        self.prev(mesh_graph).and_then(|prev| {
72            mesh_graph
73                .halfedges
74                .get(prev)
75                .or_else(error_none!("Previous halfedge not found"))
76                .and_then(|h| h.twin.or_else(error_none!("Twin missing")))
77        })
78    }
79
80    /// In clockwise order next halfedge that has the same start vertex
81    ///
82    /// <img src="https://raw.githubusercontent.com/Synphonyte/mesh-graph/refs/heads/main/docs/halfedge/cw_rotated_neighbour.svg" alt="Connectivity" style="max-width: 28em" />
83    #[instrument(skip(mesh_graph))]
84    pub fn cw_rotated_neighbour(&self, mesh_graph: &MeshGraph) -> Option<HalfedgeId> {
85        mesh_graph
86            .halfedges
87            .get(self.twin.or_else(error_none!("Twin missing"))?)
88            .and_then(|h| h.next)
89    }
90
91    /// Length of the halfedge squared.
92    #[instrument(skip(mesh_graph))]
93    pub fn length_squared(&self, mesh_graph: &MeshGraph) -> f32 {
94        self.len_sqr_inner(mesh_graph).unwrap_or_else(|| {
95            error!("Halfedge invalid. Defaulting to zero length");
96            0.0
97        })
98    }
99
100    fn len_sqr_inner(&self, mesh_graph: &MeshGraph) -> Option<f32> {
101        let start = mesh_graph.positions.get(self.start_vertex(mesh_graph)?)?;
102        let end = mesh_graph.positions.get(self.end_vertex)?;
103
104        Some(start.distance_squared(*end))
105    }
106
107    /// Length of the halfedge.
108    #[inline(always)]
109    pub fn length(&self, mesh_graph: &MeshGraph) -> f32 {
110        self.length_squared(mesh_graph).sqrt()
111    }
112
113    /// Returns `true` if there is no face adjacent to this halfedge.
114    #[inline]
115    pub fn is_boundary(&self) -> bool {
116        self.face.is_none()
117    }
118
119    /// Returns `true` if the start or end vertex is a boundary vertex.
120    #[instrument(skip(mesh_graph))]
121    pub fn is_adjacent_to_boundary(&self, mesh_graph: &MeshGraph) -> bool {
122        if let Some(start_vertex) = self.start_vertex(mesh_graph) {
123            mesh_graph
124                .vertices
125                .get(start_vertex)
126                .or_else(error_none!("Start vertex not found"))
127                .map(|v| v.is_boundary(mesh_graph))
128                .unwrap_or(false)
129                || mesh_graph
130                    .vertices
131                    .get(self.end_vertex)
132                    .or_else(error_none!("End vertex not found"))
133                    .map(|v| v.is_boundary(mesh_graph))
134                    .unwrap_or(false)
135        } else {
136            error!("Start vertex ID not found");
137            false
138        }
139    }
140}
mesh_graph/elements/halfedge.rs

mesh_graph/elements/
halfedge.rs
